算法与数据结构实验

实验一 有序单链表的合并

一、 实验目的

1. 掌握单链表的原理与基本操作方法。

2. 掌握线性表的基本操作：插入、删除、查找等在链式

存储结构上的运算。

二、 实验要求

1. 认真设计本实验的程序。上机调试运行本程序。

2. 保存和打印出程序的运行结果，并结合程序进行分析。

三、 实验内容

1. 建立两个已排序的线性链表。

2. 将两个链表合并为一个新的有序的线性链表。

选作实验：一元多项式加法

实验二 栈的基本操作和应用

一 实验目的

1． 掌握串、堆栈的原理、表示及实现方法。

2． 掌握堆栈的基本操作，判断堆栈空、满，入栈和出栈操作。

二 实验要求

1． 认真设计本实验的程序，上机调试运行本程序。

2． 保存或打印出程序的运行结果，记录程序调试过程中出现的问题，对问

题加以分析。

三 实验内容

1． 用键盘输入一字符序列，存入一字符数组中。 2． 利用堆栈判断其是否中心对称（回文数据），并输出结果。

选作实验：算数表达式求值

1. 输入一算数表达式（数据自定）。 2. 利用堆栈实现该算数表达式求值。

实验三 二叉树的建立和层次遍历

一 实验目的

1． 掌握二叉树的原理、表示及实现方法。

2． 掌握二叉树的基本操作，二叉树的建立、遍历方法。

二 实验要求

1． 认真设计本实验的程序，上机调试运行本程序。

2． 保存或打印出程序的运行结果，记录程序调试过程中出现的问题，对问

题加以分析。

三 实验内容

1． 按先序遍历序列建立链式存储结构的二叉树。 2． 对该二叉树按层次进行遍历，并输出结果。

选作实验：对二叉树按中序或后序进行遍历

实验四 图的建立和基本操作

一 实验目的

1． 掌握图的原理与基本操作方法。

2． 掌握图的基本操作：图的建立,遍历方法。

二 实验要求

1． 认真设计本实验的程序，上机调试运行本程序。

2． 保存或打印出程序的运行结果，记录程序调试过程中出现的问题，对问

题加以分析。

三 实验内容

1． 输入图的顶点数据和邻接矩阵，建立该图的邻接表。 2． 对该图进行深度优先遍历，输出相应结果。

选作实验：对该图进行广度优先遍历