数据结构实验报告-答案

1、数据结构 （C 语言版 ） 实验报告专业班级学号姓名实验1实验题目：单链表的插入和删除实验目的：了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。实验要求：建立一个数据域定义为字符串的单链表，在链表中不允许有重复的字符串；根据输入的字符串，先找到相应的结点，后删除之。实验主要步骤：1、分析、理解给出的示例程序。2、调试程序，并设计输入数据（如： bat，cat，eat，fat ，hat，jat ， lat，mat，#），测 试程序的如下功能：不允许重复字符串的插入；根据输入的字符串，找到相应的结点并删除。3、修改程序：（1）增加插入结点的功能。（2）将建立链表

2、的方法改为头插入法。程序代码：#i nclude#i nclude#i nclude#i ncludetypedef struct node示意图:headheadNULLhead心得体会：本次实验使我们对链表的实质了解更加明确了，对链表的一些基本操作也更加熟练了。另外实验指导书上给出的代码是有一些问题的，这使我们认识到实验过程中不能想当然的直接编译执行，应当在阅读并完全理解代码的基础上再执行，这才是实验的意义所在。实验2实验题目：二叉树操作设计和实现实验目的： 掌握二叉树的定义、性质及存储方式，各种遍历算法。实验要求：采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍

3、历 的操作，求所有叶子及结点总数的操作。实验主要步骤：1、分析、理解程序。2、 调试程序，设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点（空指针）， 女口 ABD#CE#F#建立二叉树，求出先序、中序和后序以及按层次遍历序列，求所有叶子及结点总数。实验代码#i nclude#i nclude#i nclude20ertex=a; irstedge=NULL; irstedge;G-adjlisti.firstedge=s; irstedge;G-adjlistj.firstedge=s; ertex); irstedge; ertex); ey Rj.key 是终止一次划分函数 =w

4、hile(R0.keyRj.key); eyRj+1=R0;ey= ey ，则Ri+=Rj; ey，则Rj-=Ri; =快速排序 =void QuickSort(SeqList R,int low,int high) high 快速排序int pivotpos; high 做一次划分，得到基准记录的位置 QuickSort(R,low,pivotpos-1); eyRk.key)k=j; high调整为大根堆，除 Rlow 外，其余结点均满足堆性质int large; ey0;i-)Heapify(R,i,n); n调整为大根堆n 进行堆排序，不妨用 R0 做暂存单元int i;BuildHe

5、ap(R); n 构造为初始大根堆for(i=n;i1;i-) i 进行堆排序，共做 n-1 趟。R0=R1; R1=Ri;Ri=R0; i-1重新调整为堆，仅有 R1 可能违反堆性质。m和 Rm+1.high归并成有序的序列Rlow.high=void Merge(SeqList R,int low,int m,int high) int i=low,j=m+1,p=0; ey=Rj.key)? Ri+:Rj+;while(i=m) highn做一趟归并排序 =void MergePass(SeqList R,int length) int i;for(i=1;i+2*length-1=n;

6、i=i+2*length)Merge(R,i,i+length-1,i+2*length-1); n做二路归并排序 =void MergeSort(SeqList R)int length;for(length=1;lengthn;length*=2) ey); ey);/=主函数 void main() int i; SeqList R; input_int(R); printf(t* printf(t1 printf(t2 printf(t3 printf(t4 printf(t5 printf(t6 printf(t7 printf(t* scanf(%d,&i); / switch (

7、i) case 1: InsertSort(R); break; / case 2: BubbleSort(R); break;case 3: QuickSort(R,1,n); break; / case 4: SelectSort(R); break;case 5: HeapSort(R); break;/case 6: MergeSort(R); break; case 7: exit(0); / printf(Sort reult:); output_int(R);* Select *n);Insert Sortn);Bubble Sortn);Quick Sortn);Straigh

8、t Selection Sortn);Heap Sortn);Merge Sortn);Exitn);*n);输入整数 1-7 ，/选择排序方式值为 1，直接插入排序值为 2，冒泡法排序 值为 3，快速排序值为 4，直接选择排序 值为 5，堆排序值为 6，归并排序 值为 7 ，结束程序实验结果：Please input num(int):10 Plase input 10 integer:265 30175112993786374269476438*Select*1: Insert Sort2: Bubble Sort3: Quick Sort4: Straight Selection Sor

9、t5: Heap Sort6: Merge Sort7: Exit* 1129, 265, 301, 751, 937, 863, 742, 694, 76, 438,129, 265, 301, 751, 863, 937, 742, 694, 76, 438,129, 265, 301, 742, 751, 863, 937, 694, 76, 438,129, 265, 301, 694, 742, 751, 863, 937, 76, 438,76, 129, 265, 301, 694, 742, 751, 863, 937, 438,76, 129, 265, 301, 438,

10、694, 742, 751, 863, 937,Sort reult: 76, 129, 265, 301, 438, 694, 742, 751, 863, 937,2 76,129,265,301,751,438,937,863,742,694, 76,129,265,301,438,751,694,937,863,742, 76,129,265,301,438,694,751,742,937,863,76,129,265,301,438,694,742,751,863,937,Sort reult: 76, 129, 265, 301, 438, 694, 742, 751, 863,

11、937,376,129,265,751,937,863,742,694,301,438,76,129,265,751,937,863,742,694,301,438,76,129,265,438,301,694,742,751,863,937,76,129,265,301,438,694,742,751,863,937,76,129,265,301,438,694,742,751,863,937,76,129,265,301,438,694,742,751,863,937,Sort reult: 76, 129, 265, 301, 438, 694, 742, 751, 863, 937,

12、476,301,751,129,937,863,742,694,265,438,76,129,751,301,937,863,742,694,265,438,76,129,265,301,937,863,742,694,751,438,76,129,265,301,438,863,742,694,751,937,76,129,265,301,438,694,742,863,751,937,76,129,265,301,438,694,742,751,863,937,Sort reult: 76, 129, 265, 301, 438, 694, 742, 751, 863, 937, 5863

13、,694,751,265,438,301,742,129, 76,937,751,694,742,265,438,301, 76,129,863,937,742,694,301,265,438,129, 76,751,863,937,694,438,301,265, 76,129,742,751,863,937,438,265,301,129, 76,694,742,751,863,937,301,265, 76,129,438,694,742,751,863,937,265,129, 76,301,438,694,742,751,863,937,129, 76,265,301,438,694

14、,742,751,863,937,76,129,265,301,438,694,742,751,863,937,Sort reult: 76, 129, 265, 301, 438, 694, 742, 751, 863, 937,6265,301,129,751,863,937,694,742, 76,438,129,265,301,751,694,742,863,937, 76,438,129,265,301,694,742,751,863,937, 76,438,76,129,265,301,438,694,742,751,863,937,Sort reult: 76, 129, 265, 301, 438, 694, 742, 751, 863, 937,7Press any key