数据结构每章经典实验.doc

数据结构实验 实验一：线性表及其应用 1．实验名称：线性表及其应用 要求：a.掌握线性表的各种存储结构实现。 b.掌握各种存储结构上进行插入、删除等操作的算法。 c.通过线性表结构解决现实中的一些问题。 实验内容：编写算法实现顺序表的逆置，即要求把顺序表A中的数据元素序列（a0,a1,…,an-1）就地逆置为（an-1,an-2,…,a0），并把逆置后的数据元素存储到顺序表中。 2. 将有序线性表La={2,4,6,7,9}，Lb={1,5,7,8}，合并为Lc={1,2,4,5,6,7,7,8,9} 3通讯录管理 菜单内容 程序运行后，给出如下六个菜单的内容和输入提示： 1.通讯录的建立 2.通讯者结点的插入 3.通讯者结点的查询 4.通讯者结点的删除 5.通讯者结点的输出 0.退出管理系统 请选择0－5： Typedef struct{ char num[5];//编号 char name[9]; //姓名 char sex[3];//性别 char addr[31];//地址 } 实验：顺序栈基本操作 一 、实验目的 1．熟悉并能实现栈的定义和基本操作。 2．了解和掌握栈在递归和非递归算法的应用。 二 、实验要求 1．进行栈的基本操作时要注意栈“后进先出”的特性。 2．编写完整程序完成下面的实验内容并上机运行。 3．整理并上交实验报告。 三、实验内容 1．编写程序任意输入栈长度和栈中的元素值，构造一个顺序栈，对其进行清空、销毁、入栈、出栈以及取栈顶元素操作。 . 将从键盘输入的字符序列逆置输出. 比如，从键盘上输入：tset a si sihT；算法将输出：This is a test 3. .对于给定的十进制正整数N，转换成对应的八进制正整数 4．编写程序实现表达式求值，即验证某算术表达式的正确性，若正确，则计算该算术表达式的值。 主要功能描述如下： 1)、从键盘上输入表达式。 2)、分析该表达式是否合法： 是数字，则判断该数字的合法性。若合法，则压入数据到堆栈中。 是规定的运算符，则根据规则进行处理。在处理过程中，将计算该表达式的值。 若是其它字符，则返回错误信息。 3)、若上述处理过程中没有发现错误，则认为该表达式合法，并打印处理结果。 四、思考与提高 1．如果一个程序中要用到两个栈，为了不发生上溢错误，就必须给每个栈预先分配一个足够大的存储空间。若每个栈都预分配过大的存储空间，势必会造成系统空间紧张。如何解决这个问题？ 2．栈的存储结构在判别栈空与栈满时，所依据的条件？ La、Lb，编写程序实现将La、Lb合并成一个有序单链表Lc。 合并思想是：程序需要3个指针：pa、pb、pc，其中pa，pb分别指向La表与Lb表中当前待比较插入的结点，pc 指向Lc表中当前最后一个结点。依次扫描La和Lb中的元素，比较当前元素的值，将较小者链接到*pc之后，如此重复直到La或Lb结束为止，再将另一个链表余下的内容链接到pc所指的结点之后。 3．构造一个单链表L，其头结点指针为head，编写程序实现将L逆置。（即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。） 四、思考与提高 1．如果上面实验内容2中合并的表内不允许有重复的数据该如何操作？ 2．如何将一个带头结点的单链表La分解成两个同样结构的单链表Lb，Lc，使得Lb中只含La表中奇数结点，Lc中含有La表的偶数结点？ 实验5：排序算法的程序实现 一、 实验目的 1．掌握简单插入排序、快速排序、堆排序算法并加以应用。认真阅读和掌握和本实验相关的教材内容实现下述种算法，并用以下无序序列加以验证： 49，38，65，97，76，13，27，49简单插入排序快速排序堆排序试以 L.r[k+1] 作为监视哨改写中给出的直接插入排序算法。其中， L.r[1..k] 为待排序记录且 kMAXSIZE 。// 对 L 中的元素按关键字递增次序进行直接插入排序(监视哨设在表尾)void insertsort(table *L) 2-(必做)3．试设计一个算法，使得在O(n)的时间内重排数组，将所有取负值的关键字放在所有取非负值的关键字之前。　归并排序的另一策略是，先对待排序序列扫描一遍，找出并划分为若干个最大有序子列，将这些子列作为初始归并段。试写一个算法在结构上实现这一策略。 兰国旗问题：设有一个仅由红、白、兰这三种颜色的条块组成的条块序列。请编写一个时间复杂度为O(n)的算法，使得这些条块按红、白、兰的顺序排好，即排成荷兰国旗图案。3种颜色（0，1，2）在一个数组里，每次只可交换一次，扫描一后，三种颜色自然分开，应为颜色为：红，白，蓝，（荷兰国旗的颜色）所也叫荷兰国旗问题0, 2, 1