2022年数据结构实验报告 .pdf

《2022年数据结构实验报告 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构实验报告 .pdf（11页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、数据结构 (C 语言版 ) 实验报告学院 计算机科学与技术专业 * 学号 * 班级 * 姓名 *指导教师 *名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 11 页 - - - - - - - - - 实验 1实验题目：单链表的插入和删除实验目的：了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。实验要求：建立一个数据域定义为字符串的单链表，在链表中不允许有重复的字符串；根据输入的字符串，先找到相应的结点，后删除之。实验主要步骤：1、分析

2、、理解给出的示例程序。2、调试程序，并设计输入数据（如：bat ，cat ，eat ，fat ，hat ，jat ，lat ，mat，#） ，测试程序的如下功能：不允许重复字符串的插入；根据输入的字符串，找到相应的结点并删除。3、修改程序：（1）增加插入结点的功能。（2）将建立链表的方法改为头插入法。程序代码 :#include#include#include#includetypedef struct node . . 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 1

3、1 页 - - - - - - - - - 示意图：心得体会：本次实验使我们对链表的实质了解更加明确了，对链表的一些基本操作也更加熟练了。另外实验指导书上给出的代码是有一些问题的，这使我们认识到实验过程中不能想当然的直接编译执行，应当在阅读并完全理解代码的基础上再执行，这才是实验的意义所在。latjathatfateatcatbatmatNULLheadlatjathatfateatcatbatmatheadlatjatfateatputcatbatmatheadNULLNULL名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名

4、师精心整理 - - - - - - - 第 3 页，共 11 页 - - - - - - - - - 实验 2实验题目：二叉树操作设计和实现实验目的：掌握二叉树的定义、性质及存储方式，各种遍历算法。实验要求：采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。实验主要步骤：1、分析、理解程序。2、调试程序， 设计一棵二叉树， 输入完全二叉树的先序序列，用#代表虚结点（空指针），如 ABD#CE#F# ，建立二叉树，求出先序、中序和后序以及按层次遍历序列，求所有叶子及结点总数。实验代码#include#include#include#d

5、efine Max 20 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 11 页 - - - - - - - - - ertex=a; irstedge=NULL; irstedge;G-adjlisti.firstedge=s; irstedge; G-adjlistj.firstedge=s; ertex); irstedge; ertex); irstedge; ertex); eyRi-1.key) ey 大于等于有序区中所有的keys ， 则 Ri留在原位 R

6、0=Ri;j=i-1; ey的记录后移 j-; while(R0.keyRj.key); eyRj.key 是终止 Rj+1=R0; ey= ey ，则Ri+=Rj; ey ，则Rj-=Ri; =快速排序 =void QuickSort(SeqList R,int low,int high) high快速排序 int pivotpos; high做一次划分，得到基准记录的位置ABFEDCV6V4V5V7V2V3V1V0V6V4V5V7V2V3V1V0名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - -

7、 - - 第 5 页，共 11 页 - - - - - - - - - QuickSort(R,low,pivotpos-1); eyRk.key)k=j; high调整为大根堆，除Rlow 外，其余结点均满足堆性质 int large; ey0;i-)Heapify(R,i,n); n调整为大根堆n 进行堆排序，不妨用R0 做暂存单元 int i; BuildHeap(R); n构造为初始大根堆 for(i=n;i1;i-) i进行堆排序，共做n-1 趟。R0=R1; R1=Ri;Ri=R0; i-1重新调整为堆，仅有R1 可能违反堆性质。 m和 Rm+1.high归并成有序的序列Rlow.

8、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) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 11 页 - - - - - - - - - int i; for(i=1;i+2*length-1=n;i=i+2*le

9、ngth)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* Select *n); printf(t1: Insert Sortn); printf(t2: Bubble Sortn); printf(t3: Quick Sortn); printf(t4: Straight S

10、election Sortn); printf(t5: Heap Sortn); printf(t6: Merge Sortn); printf(t7: Exitn); printf(t*n); scanf(%d,&i); /输入整数1-7 ，选择排序方式 switch (i)名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 11 页 - - - - - - - - - case 1: InsertSort(R); break; /值为 1，直接插入排序case 2: Bu

11、bbleSort(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):10 Plase input 10

12、integer:265 301 751 129 937 863 742 694 76 438 * Select * 1: Insert Sort 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 11 页 - - - - - - - - - 2: Bubble Sort 3: Quick Sort 4: Straight Selection Sort 5: Heap Sort 6: Merge Sort 7: Exit * 1 129, 265, 301, 751, 937

13、, 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

14、, 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,

15、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,名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 11 页 - - - - - - - - - 76,129,265,301,438,694,742,751,863,937,76,129,

16、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,3

17、01,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,

18、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

19、,694,742,751,863,937, 76,438, 76,129,265,301,438,694,742,751,863,937,名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 11 页 - - - - - - - - - Sort reult: 76, 129, 265, 301, 438, 694, 742, 751, 863, 937,7Press any key to continue运行速度比较：直接排序冒泡排序直接插入冒泡排序快速排序时间复杂度 O(n2)，其中快速排序效率较高其它的效率差不多堆排序 归并排序时间复杂度 (nlogn) ,平均效率都很高心得体会：此次试验了解了各种排序的基本思想，在分析各种排序的程序代码，对程序进行调试执行等等过程中， 锻炼了自己分析数据结构的能力。此次试验然我知道排序的多种方法，也让我知道要编写好一个程序，首先要掌握其基本的思想及算法。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 11 页 - - - - - - - - -