数据结构(C语言版) 实验报告专业班级学号姓名实验1实验题目：单链表的插入和删除实验目的：了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。

实验要求：建立一个数据域定义为字符串的单链表，在链表中不允许有重复的字符串；根据输入的字符串，先找到相应的结点，后删除之。

实验主要步骤：1、分析、理解给出的示例程序。

2、调试程序，并设计输入数据（如：bat，cat，eat，fat，hat，jat，lat，mat，#），测试程序的如下功能：不允许重复字符串的插入；根据输入的字符串，找到相应的结点并删除。

3、修改程序：（1）增加插入结点的功能。

（2）将建立链表的方法改为头插入法。

程序代码:#include""#include""#include""#include""typedef struct node . .示意图：headheadhead心得体会：本次实验使我们对链表的实质了解更加明确了，对链表的一些基本操作也更加熟练了。

另外实验指导书上给出的代码是有一些问题的，这使我们认识到实验过程中不能想当然的直接编译执行，应当在阅读并完全理解代码的基础上再执行，这才是实验的意义所在。

实验2实验题目：二叉树操作设计和实现实验目的：掌握二叉树的定义、性质及存储方式，各种遍历算法。

实验要求：采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。

实验主要步骤：1、分析、理解程序。

2、调试程序，设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点（空指针），如ABD###CE##F##，建立二叉树，求出先序、中序和后序以及按层次遍历序列，求所有叶子及结点总数。

实验代码#include""#include""#include""#define Max 20ertex=a; irstedge=NULL; irstedge;G->adjlist[i].firstedge=s; irstedge;R[i]留在原位j--;}while(R[0].key<R[j].key); ey≥R[j].key 是终止R[j+1]=R[0]; ey<R[j].key){ =======一次划分函数===== int Partition(SeqList R,int i,int j){ ey>= ey < ，则R[i++]=R[j]; ey<= ey > ，则R[j--]=R[i]; ====快速排序===========void QuickSort(SeqList R,int low,int high){ high]快速排序int pivotpos; high]做一次划分，得到基准记录的位置QuickSort(R,low,pivotpos-1); ey<R[k].key)k=j; high]调整为大根堆，除R[low]外，其余结点均满足堆性质int large; ey<R[large+1].key)large++; ey) n]构造为堆int i;for(i=n/2;i>0;i--)Heapify(R,i,n); n]调整为大根堆}n]进行堆排序，不妨用R[0]做暂存单元int i;BuildHeap(R); n]构造为初始大根堆for(i=n;i>1;i--){ i]进行堆排序，共做n-1趟。

R[0]=R[1]; R[1]=R[i];R[i]=R[0]; i-1]重新调整为堆，仅有R[1]可能违反堆性质。

}}m]和R[m+1..high]归并成有序的序列R[low..high]==void Merge(SeqList R,int low,int m,int high){int i=low,j=m+1,p=0; ey<=R[j].key)? R[i++]:R[j++];while(i<=m) high]}n]做一趟归并排序========void MergePass(SeqList R,int length){int i;for(i=1;i+2*length-1<=n;i=i+2*length)Merge(R,i,i+length-1,i+2*length-1); n]做二路归并排序=============== void MergeSort(SeqList R){int length;for(length=1;length<n;length*=2) ey);}ey);}//==========主函数======void main(){int i;SeqList R;input_int(R);printf("\t******** Select **********\n");printf("\t1: Insert Sort\n");printf("\t2: Bubble Sort\n");printf("\t3: Quick Sort\n");printf("\t4: Straight Selection Sort\n");printf("\t5: Heap Sort\n");printf("\t6: Merge Sort\n");printf("\t7: Exit\n");printf("\t***************************\n");scanf("%d",&i); //输入整数1-7，选择排序方式switch (i){case 1: InsertSort(R); break; //值为1，直接插入排序case 2: BubbleSort(R); break; //值为2，冒泡法排序case 3: QuickSort(R,1,n); break; //值为3，快速排序case 4: SelectSort(R); break; //值为4，直接选择排序case 5: HeapSort(R); break; //值为5，堆排序case 6: MergeSort(R); break; //值为6，归并排序case 7: exit(0); //值为7，结束程序}printf("Sort reult:");output_int(R);}实验结果：Please input num(int):10Plase input 10 integer:26530175112993786374269476438******** Select **********1: Insert Sort2: Bubble Sort3: Quick Sort4: Straight Selection Sort5: 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, 694, 742, 751, 863, 937,Sort reult: 76, 129, 265, 301, 438, 694, 742, 751, 863, 937,276,265,301,751,129,937,863,742,694,438,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, 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, 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,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,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 to continue运行速度比较：直接排序冒泡排序直接插入冒泡排序快速排序时间复杂度 O(n2)，其中快速排序效率较高其它的效率差不多堆排序归并排序时间复杂度 (nlogn) ,平均效率都很高心得体会：此次试验了解了各种排序的基本思想，在分析各种排序的程序代码，对程序进行调试执行等等过程中，锻炼了自己分析数据结构的能力。