《数据结构与算法(C语言版)》实验指导书（合集）.docx

《《数据结构与算法(C语言版)》实验指导书（合集）.docx》由会员分享，可在线阅读，更多相关《《数据结构与算法(C语言版)》实验指导书（合集）.docx（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、上机实验1多项式的数组表示及运算【实验目的】（1）学会用简单数据类型描述复合数据类型。（2）学会用数组来表示多项式。（3）学会建立新的数据结构。【实验内容】用数组来表示多项式，多项式表示为：Pn（X）= piXel + p2Xe2 + pmXemo其中，Pi是指数为ei的项的非零系数，且满足OW eie2 em= no为了方便计算 机实现多项式的存取，有多项式：F（x）=9x9+x8-7x6+4x3-25x+2将F（x）存入数组中，并在控制台显示。【实验步骤】（1）建立多项式项的数据结构，使用结构体来表示多项式的每一项。（2）定义多项式的数组，完成多项式的输入与输出。（3）代码实现。【参考源代

2、码】项的表示系数指数项的表示系数指数typedef struct int coef; int expn; polynomial;#include#define MAX 100多项式输入函数的声明多项式输出函数的声明void InputPolyO;void OutputPoIy(polynomial aPoly);polynomial aPolyMAX;void main()(InputPolyO;OutputPoly(aPoly);)void InputPolyO上机实验4二叉树的遍历【实验目的】(1)掌握指针变量的含义及使用方法。(2)熟悉二叉树结点的结构。(3)掌握二叉树每一种操作具体实现

3、的方法。(4)学会利用递归的方法实现二叉树的遍历算法。【实验内容】实现对二叉树的如下操作：(1)创立二叉树。(2)先序遍历二叉树。(3)中序遍历二叉树。(4)后序遍历二叉树。(5)按层遍历二叉树。要求能够从键盘上输入建树的结点内容，并且将遍历的结果输出在屏幕上。【实验步骤】(1)在Microsoft Visual C+中创立应用程序L4。(2)在程序中创立二叉树的存储结构BiTNode,以链表作为存储结构。(3)创立CreateBiTree()函数，实现创立二叉树的操作，能够按先序次序从键盘输入结 点内容，空格表示空树。(4)创立PreOrderTraverse。函数，用递归的方法实现先序遍历

4、二叉树的操作。(5)创立InOrdeiTraverse。函数，用递归的方法实现中序遍历二叉树的操作。(6)创立PostOrdeiTraverse()函数，用递归的方法实现后序遍历二叉树的操作。(7)创立LevelOrderTraverse。函数，实现按层遍历二叉树的操作。(8)创立主函数，用switch语句实现从键盘上输入字符，选择要执行的操作。(9)编译连接程序，执行并观察程序的运行效果。【参考源代码】#include stdlib.h#include nstdio.hntypedef struct BiTNodechar data;struct BiTNode *lchild,*rchil

5、d;BiTNode,* BiTree;void CreateB iTree(B iTree &T)/按先序次序输入，构造二叉链表表示的二叉树T,空格表示空树char ch;scanf(H%cn,&ch);if(ch=p T=NULL;elseif (!(T=(BiTNode*)malloc(sizeof(BiTNode) exit(-l);T-data=ch;CreateBiTree(T-lchild);CreateBiTree(T-rchild);)/CreateBiTreevoid PreOrderTraverse(B iTree T) 先序遍历if(T)printfC%c n,T-dat

6、a);PreOrderTraverse(T-lchild);PreOrderTraverse(T-rchild);)/PreOrderTra versevoid InOrderTraverse(BiTree T) 中序遍历if(T)InOrderTraverse(T-lchild);printf(u%c n,T-data);InOrderTraverse(T-rchild);) /InOrderTraversevoid PostOrderTraverse(BiTree T) 后序遍历if(T)PostOrderTraverse(T-lchild);PostOrderTraverse(T-rch

7、ild);printf(n%c n,T-data);) /PostOrderTraversevoid LevelOrderTraverse(B iTree T) 按层遍历const int MaxLength=100;BiTree QMaxLength|;QO=T；int front=0,rear=l; while(frontdata); Q rear+=Q front -lchild; Q rear+=Q front -rchild; front+4-;) else front+;) /Level OrderTraversevoid main()(BiTree T=NULL;char sel

8、ect;while(l)printf(请选择要执行的操作：nn);printf(l .创立二叉树 n)printf(“2.二叉树的递归遍历算法(前、中、后)n”)；printf(3.二叉树的层序遍历算法n);printf(0 .退出 n); fflush(stdin);scanf(n%cn,&select);fflush(stdin); switch(select) (case *0*:return;case T:printf(”请按先序次序输入各结点的值，以空格表示空树(输入时可连续输入)：nn);CreateBiTree(T);printf(nnM);break;case 2:printf

9、(先序遍历PreOrderTraverse(T);printf(n 中序遍历:)；InOrderTraverse(T);printf(n 后序遍历PostOrderTraverse(T);printf(HnnH);break;case 3:printf(层序遍历LevelOrderTraverse(T);printf(Hnnn);break;default:printf(请确认选择项八nn);/end switch/end while/end main【实验结果】运行例如：构建如下二叉树，并且将其遍历的结果输出在屏幕上。步骤1：输入1,按Enter键，等待创立二叉树。步骤2：按先序方式构建二叉

10、树，输入：abd(空两格)e(空两格)c(空两格)，按Enter键确认 输入。步骤3：输入2,按Enter键，观察显示结果。步骤4：输入3,按Enter键，观察显示结果。步骤5：输入0,退出循环程序。运行结果如附图4所示。要执行的操作二叉2愧序遍历:a b d e c 中任遍历:d b e a c 后序遍历:d e b c a精选岑 k .创缸 卡.二叉机的递归遍历 5 .二叉树的层序遍历1(刖、礼后)中、后)cr C:INDOSsyste-32cd. exe附图4上机实验4运行结果作 操 的一tW层 执见的的 要二M g叉叉出 选创二二退 f - - - L 二12303后中一层 执叉的的

11、要二作 操 的g叉叉出 选创二二退 请1.B.3.S;历历 遍遍 归序常选接要执丘的操作：k创硅二叉树，,二叉狗的襦归遍历篡花(前、中、后)藤叉树的层序遍历算法按先序次序输入各结点的值，以空格表示空树输入时可连续输入)： abd e c(前、历历 遍遍【实验总结】在创立二叉树时应注意程序的编写，在参考程序中，使用空格来表示空树、所以在创立 时，如果结点的子树为空时，一定要输入空格，方能成功创立二叉树。当然，也可用其他的 字符(如“肥)代替空格表示空树，但是一定要在程序中进行相应的编写与说明。参考程序中，在主程序中先创立了一个空树T,然后调用CreateBiTree()创立二叉树，由 于T需要在

12、后面进行遍历，它的内容要求是可以返回的，所以必须使用引用调用，在创立 CreateBiTree。时应注意形参的设置。编程时尤其应注意scanf()函数的c “格式带来的缓冲区的问题，因为使用 c “格式接收 的是字符，空格和转义字符都为有效字符。而创立二叉树时，完成输入后有一个回车操作表 示结束输入、创立完成，这个时候一定不要忘了使用“fflush(stdin)； ”语句来清空缓冲区，否 那么会将回车符作为一个字符接收，这样可能会造成后续程序出问题。建议使用scanf()函数的 “c”格式接收一个字符时，要在其后加上“fflush(stdin)； ”语句，这样能防止问题的出现。但 在参考程序中

13、，CreateBiTree。函数中的scanf()后并没有“fflush(stdin)； ，这样做是为了能连 续从键盘获取字符，并且把空格也作为字符接收，但是在完成创立后，后面的scanf()函数在 接收字符前必须使用“fflush(stdin)； ”完成缓冲区的清空操作。上机实验6哈夫曼编码【实验目的】(1)熟悉哈夫曼树的存储结构。(2)掌握哈夫曼树构建的算法。(3)掌握哈夫曼树的遍历方法。(4)掌握哈夫曼编码算法。【实验内容】实现哈夫曼编码算法：根据给定的权值数组，构建带权路径长度最小的哈夫曼树，然后 输出对应的哈夫曼编码。【实验步骤】(1)在Microsoft Visual C+中创立应

14、用程序L6。(2)在程序中定义哈夫曼树的存储结构tnodepointer。(3)编写函数select。,实现在给定的n个元素的结点数组中，找出权值最小的两个元素， 返回其下标。(4)编写huffmancoding。，实现构建哈夫曼树，并返回哈夫曼编码。(5)编写哈夫曼编码的输出函数output。(6)编写主函数，初始化结点的权值数组，调用huffmancoding()函数，输出哈夫曼编码。(7)编译连接程序，执行并观察程序的运行效果。【参考源代码】#include #include #include typedef struct哈夫曼树结点的类型int weight,parent,lchild

15、,rchild; tnode,tnodepointer;void select(tnodepointer HT,int n,int &sl,int &s2)在数组HT的前n个parents的元素中，找出权最小的两个元素并将其下标分别赋给si、 s2int i;sl=0;for(i=0;in&HTi.parent !=0;i+)略过已经加入树的结点sl=i+l;for(i=0;in;i+)用s 1保存权最小的元素的下标if(HTi. weightHTs 1. weight&HTi .parent=0)sl=i;s2=0;for(i=0;in&(s2=sl |HTi,parent !=0);i+)

16、 s2 = i+1;for(i=0;in;i+)用s2保存权次小的元素的下标if(HTi.weightweight =*w;TEMP-parent = 0;TEMP-lchild = 0;TEMP-rchild = 0; ) for(intm=2*n-l;TEMPparent =0;for(int i=n;i2*n-l;i+)/设置各个结点的值，构建哈夫曼树( int sl,s2; select(HT,i,sl,s2); /在数组HT的前n个parent=0的元素中，找出权最小的两个 元素并将其下标分别赋给si、s2HTsl.parent =i;HTs2.parent =i;HTi.lchil

17、d =sl;HTi.rchild =s2;HTi.weight =HTsl.weight +HTs2.weight;)char *str=(char *)malloc(n*sizeof(char);/str用于临时存放哈夫曼编码char *huffmancode=(char *)maUoc(n*sizeof(char *);for(int i=0;in;i+)构建哈夫曼编码int start=n-1;strstart=,O,;int c=i,temp=HTc.parent;t em p=0表示该结点为根结点t em p=0表示该结点为根结点while(temp!=O)if(HTtemp.lch

18、ild =c)str-start=O；elsestr-start-T;c=temp;temp=HTc.parent;huffmancodei=(char*)malloc(n-start)*sizeof(char); strcpy(huffmancodei,&strstart);)free (HT);free(str);return huffmancode;void output(char *p,int n)void output(char *p,int n)输出数组p中各元素指向的字符串for(int i=0;in;i+)printf(n%s n,pi);printf(nnn);void ma

19、in()/测试int w卜5,29,7,8,14,23,3,11;char *p=huffmancoding(w,8);printf(与权值对应的huffman编码为：n);output(p,8);)【运行结果】参考源码中设置的权值为w=5,29,7,8,14,23,3,11程序运行结果如附图7所示。c、C: I!0)0TSsyst e32cd. exe与权值对应的huf f man编科 为:0001 10 1110 1111 110 01 0000 001请按任意键继续. . 附图7上机实验6运行结果【实验总结】该算法的关键之一是select。函数的实现，即如何在给定的n个元素的结点数组中，

20、找出 权值最小的两个元素，返回其下标。构建哈夫曼树时，利用了哈夫曼树的链接表来保存树的左右孩子信息和父结点信息。在返回哈夫曼编码时，从树根遍历到树的叶子结点，这样逆向构建哈夫曼编码。上机实验7快速排序【实验目的】(1) 了解内部排序的方法。(2)掌握快速排序的基本思想。(3)学会用快速排序实现对无序数组的排序。(4)比照不同排序方法的优劣。【实验内容】(1)使用快速排序算法将无序数列(10,168,23,7,67,5,4,45,0,97)按由小到大顺序排列， 并在屏幕显示。(2)在上述实验的基础上，统计排序的次数并比拟快速排序与其他排序的优劣。【实验步骤】(1)分析快速排序的基本思想，通过一趟

21、排序将待排记录分割成独立的两个局部，其 中一局部记录的关键字均比另一局部记录的关键字小，那么可分别对这两局部记录继续进行排 序，以使整个序列有序。(2)选取数组中的一个记录作为枢轴(或支点)，建议选择数组元素的中间数。(3)代码实现。【参考源代码】#include #define N 10int count=0;int Partition(int a,int low,int high)(int privotlndex = (low+high)/2; 中间数int temp=aprivotlndex;count+;printf(第(1次中间数:%dnn,count,temp);aprivotTn

22、dex=ahigh;ahigh=temp;int pivotkey=temp;while(lowhigh)(while(lowhigh&alow=pivotkey)+low;ahigh=alow;while(low=pivotkey)-high;printf(多项式的建立11输入一元多项式(以0, 0标志结束)n)；prints系数与指数之间用空格，输完后按回车。n)int i=0;do (printf(第d项系数和指数：”,i+l);scanf(,%d%d,&aPolyi.coef,&aPolyi.expn);if(aPolyi.coef=0&aPolyi.expn=0) break;i+；

23、while (i0)printf(n%d%s%dn,aItem0.coef,nxAn,aItem0.expn);else if(aItem0.expn=0) printf(n %dn,aItem0 .coef);elseprintf(d%s%c%d%c”,altem0.coefjx/v?(,altem0.expn,);)for(int i = 1; i != MAX; i+) (if(altemi.coef0)(if(aItemi.expn0)printf(n%c%d%s%dn/+aItemi.coef,nxA，aItemi.expn);else if(altemi.expn=0)printf

24、(,%c%d7+altemi.coef);elseprintf(”c%d%s%c%d%c,altemi.coefjx 八 altemi.expn,); )else if(altemi.coef0)alow=ahigh;)ahigh=pivotkey;printf(第 d 次排序结果:,count);for(int i=0;iN;+i)printf(n%d n,ai);printf(nnn);return high;)void QuickSort(int a| ,int low,int high)int pivotloc;if(lowhigh)(pivotloc=Partition(a,low,

25、high);QuickSort(a,low,pivotloc-1);QuickSort(a,pivotloc+1 ,high);)void main()int dataN= 10,168,23,7,67,5,4,45,0,97;printf(原始的无序数组：”)；for(int i=0;iN;+i)printf(u%d n,datai);printf(nnn);QuickSort(data,0,N-1);printf(由小到大的有序数组：”)；for(int i=0;i:184组.。数.168234 75 75 75 75 7：023 7 677 45 5 445 23 1045 23 104

26、5 23 1010 23 4510 23 454 5 7 105 4 45 0 9767 97 16867 97 16867 97 16867 97 16867 97 16867 97 16823 45 67 97 1682d附图8上机实验7运行结果【实验总结】快速排序是交换排序的另一种方法，是对冒泡排序的一种改进。通过对快速排序算法的 实现，进一步学习了交换排序算法的基本思想。快速排序的平均时间为Aver(n)=nlog2n,其 中n为待排序列中记录的个数。实验证明，在同数量级的排序中，就平均时间而言，快速排序是目前被认为最好的一种 内部排序方法。上机实验8折半查找【实验目的】(1)熟悉顺序

27、存储结构。(2)掌握查找的有关方法。(3)学会分析查找的性能。(4)掌握折半查找算法的实现方法。【实验内容】实现折半查找算法：要求能够实现用户从键盘输入一个有序的整数数组，然后从键盘指 定一个整型的搜索值n,如果找到，那么在屏幕输出该值的位置，否那么，输出“没有找到搜索值 n”。【实验步骤】(1)在Microsoft Visual C+中创立应用程序L8。(2)创立折半查找函数BinarySearch。，实现折半查找算法。(3)创立主函数，实现从键盘上输入数据创立一个按从低到高排列的整型数组，并且 调用B inary Search。完成查找。(4)编译连接程序，执行并观察程序的运行结果。【参考

28、源代码】#include #include #define MAX 10int BinarySearch(int a,int key) 折半查找int low=0;int high=MAX;while(lowa|mid|) low=mid+l;else high二mid-1;)return -1;/Binary Searchvoid main()int found,value,aMAX;printf(”请按从低到高的顺序输入10个整型数据，以空格分隔，回车结束：n) for(int i=0;i32d. eze-|口316 ，布 9 8 3 5 0 0 X - 0空 91T4-220F- 蜘期珈

29、如期蜘江短 TH仅匕日匕日匕日匕日匕日匕日匕日7分一 立项之继 如系系系系系系普 贮需瑞瑞喘酸附图1上机实验1运行结果【实验总结】通过多项式的数组表示及运算的实验,读者应初步学会用简单数据类型描述复合数据类 型。作为数据结构的第一个实验，认真掌握实验的开发环境，为后续实验打下基础。上机实验2串的匹配算法及实现【实验目的】(1) 了解串的相关概念。(2)掌握串的有关存储方法。(3)熟悉串的基本操作。(4)通过串匹配算法的实现，掌握朴素的模式匹配算法。【实验内容】实现朴素的模式匹配算法：要求能够实现从键盘输入主串S和子串T,并且能够从键盘指 定S的第pos位为开始匹配的位置，如果匹配成功，那么在屏

30、幕输出S中符合匹配的位置，即S中 与T匹配的子序列第一个字符的序号，否那么，返回0。【实验步骤】(1)在Microsoft Visual C+中创立应用程序L2。(2)在程序中创立字符串的存储函数InitStr。，使用数组的0号单元存储字符串的长度。(3)创立字符串的匹配函数Index。(4)创立主函数，实现从键盘上输入主串S、子串T,并能够指定开始匹配的位置。(5)编译连接程序，执行并观察程序的运行效果。【参考源代码】#include #include #define MAXSIZE 100/字符串的最大存储长度typedef char SStringMAXSIZE+l; / 使用0号单元存

31、储长度void InitStr(SString rs)char stmpMAXSIZE;int i;gets(stmp);rsO=strlen(stmp);for (i=l;i=rs0;i+)rsi=stmpi-l;rsi 尸 0;int Index(SString S, SString T, int pos)/返回T在S中第pos个字符后首次出现的位置，假设不存在那么返回0int i = posj = 1;while(i = S0 &jT0)return i-T0J;/匹配成功返回T在S中第pos个字符后首次出现的位置else return 0; / Indexvoid main ()(SS

32、tring sstr;SString dstr;int pos;int n;printf(请输入主串：”)； InitStr(sstr);printf(请输入子串:)； InitStr(dstr);printf(”请输入开始匹配的位置：”); scanf(n%dn,&pos);n=Index(sstr, dstr, pos); printf(n%dnn,n);)【运行结果】运行例如：主串输入：sit please子串输入：please匹配位置输入：2运行结果如附图2所示。c. C:VI!TOOSsyste32cd. exe请施入主串：sit please 请输入子串：please 请输入开始匹

33、配的位置：2主11任意键继续.附图2上机实验2运行结果【实验总结】编程时应注意，存储字符串有一个转换的过程，通过InitStr。函数，将键盘上获取的字符 串转换成符合要求的存储结构，使得存储字符串数组的第一位为字符串的长度，这样方便了 Index。函数的编写，在比拟时能够更直观地使用数组的下标进行操作，而不用再作相应的考 虑与转换。编写程序时应注意数组长度的设置，在保证有足够存储空间的情况下不必定义过长，参 考源代码中指定的是100,编程者可根据实际情况自行设置其大小。在编写Index。函数时， 应注意回退指针的计算，以免造成匹配出错的情况。上机实验3八皇后问题【实验目的】(1) 了解回溯算法

34、的思路：从一条路往前走，能进那么进，不能进那么退回来，换一条路 再试。(2)通过对八皇后问题的解决，掌握回溯算法的应用。【实验内容】在8X8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于 同一行、同一列或同一斜线上，问有多少种摆法。【实验步骤】(1)算法分析：数组a、b、c分别用来标记冲突。数组a代表列冲突，a0ka代表第0列到第7列，如果某列上已经有皇后，那么为1,否 那么为0。数组b代表主对角线冲突，为bi-j+7,即b0b14,如果某条主对角线上已经有皇后， 那么为1,否那么为0。数组c代表从对角线冲突，为ci+j,即c0c14,如果某条从对角线上已经有皇后, 那

35、么为1，否那么为0。(2)优化算法：第一个皇后在14格，最后乘以2,即为总解数。(3)代码实现。【参考源代码】#include nstdio.hnstatic char Queen88;static int a8j;static int b15;记录总的棋盘状态数 参数i代表行棋盘初始化，空格为*,放置皇后的地方为static int c15;static int iQueenNum=O;void qu(int i);int main()int iLine,iColumn;for(iLine=0;iLine8 ;iLine+)aiLine=O;aiLine=O;列标记初始化，表示无列冲突for

36、(iColumn=0;iColumn8;iColumn+)QueeniLineiColumn=*;)for(iLine=0;iLine 15;iLine+) /主、从对角线标记初始化，表示没有冲突b iLine =c| iLine =0;qu(o)；return 0;)void qu(int i)int iColumn;for(iColumn=0;iColumn8;iColumn+)if(aiColumn=0&bi-iColumn+7=0&ci+iColumn=0) /如果无冲突QueeniiColumn=,; aiColumn=l;bi-iColumn+7=l; ci+iColumn=l;i

37、f(i7)qu(i+l);else放皇后标记，下一次该列上不能放皇后标记，下一次该主对角线上不能放皇后/标记，下一次该从对角线上不能放皇后如果行还没有遍历完，进入下一行否那么输出输出棋盘状态int iLine,iColumn;printf(第d种状态为：n,+iQueenNum);for(iLine=0;iLine8;iLine+)for(iColumn=0;iColumn8;iColumn4-+)printf(n%c n,QueeniLineiColumn);printf(nnH);)printf(,nnH);)如果前次的皇后放置导致后面的放置无论如何都不能满足要求，那么回溯，重QueeniiColumn=*;aiColumn=0;bi-iColumn+7=0;ci+iColumn=0;)【运行结果】运行结果如附图3所示。附图3上机实验3运行结果【实验总结】通过八皇后问题，了解了回溯算法的思路。在问题求解中有些被求解的问题不仅其环境 或条件随着时间不断变化，甚至连其求解的目标也随时间变化而变化。因此，在问题搜索过程 中,如果遇到困难需要回溯搜索，可能要按时间的顺序来搜索，那么优先搜索，即回溯到最新发 生的事件上。通过对八皇后问题的解决，掌握