《数据结构》实验指导(09-10一)

1、实验一 线性表及其应用实验目的（1）掌握线性表的插入、删除、查找等基本操作设计与实现（2）学习利用线性表提供的接口去求解实际问题（3）熟悉线性表的的存储方法实验环境（1）Windows 2000，或WindowsXP（简体中文）（2）Turbo C 3.0及以上，或Turbo Pascal 5.5及以上，或Visual C+ 6.0，或C+ Builder 6.0，或Visual C# 2005及以上，或Delphi 6.0及以上操作系统环境和编程环境（集成开发环境）任选以上所列之一。实验内容设计一个实现一元多项式简单运算的程序。要求完成：1）多项式的建立，2）多项式的输出，3）多项式的相加运

2、算，4）多项式的乘积运算。解题思路：以线性表来描述一元多项式，存储结构采用单链表，每个结点存储多项式中某一项的系数和指数，建立单链表时指数低的结点列于指数高的结点之后，即线性表的元素按指数递减有序排列。在多项式求和运算时，将指数相同的项的系数相加，其和非0则存储该项。乘积运算时，运用循环将2个多项式的各项交叉相乘，存储每2项的积（系数的积，指数的和）于新建立的结点，之后将这些结点中指数相同的各项系数之和非0的项合并为1个结点，最后释放多余的临时结点。实现步骤：以C+ Builder环境为例，实现步骤如下：1新建一个Win32 Console Application程序项目。2在代码编辑窗口编写

3、程序代码，含义如注释说明：#include <iostream.h>#include <cmath.h>typedef struct node / 定义单链表结点的数据类型mulpoly double coef; / 表示系数 int exp; / 表示指数 struct node *next; / 指向下一项结点的指针 mulpoly;mulpoly *create() / 逐项输入系数和指数，建立单链表的函数 mulpoly *h, *p, *q; h=new mulpoly; / 建立头结点 p=h; / 头结点作为初始的前驱 double x,y; while(

4、1) / 循环建立各项结点，直到输入指数是零为止 cout<<"Input a coefficient: " cin>>x; / 输入系数 cout<<"Input an exponent: " cin>>y; / 输入指数 if(x) q=new mulpoly; q->coef=x; q->exp=y; / 存系数和指数 p->next=q; / 前驱的next指向新建结点 p=q; / 下一个结点的前驱即当前结点 if(y<1e-6) break; p->next=NUL

5、L; / 最后一项结点无后继 return h; / 返回头指针void output(mulpoly *h) / 遍历单链表，输出一元多项式的函数 mulpoly *p; cout<<"Y=" p=h->next; if(p=NULL) cout<<"0" / 多项式为0 else / 输出多项式的第1项 cout<<p->coef; if(p->exp!=0) cout<<"X" if(p->exp>1) cout<<""

6、<<p->exp; p=p->next; while(p!=NULL) / 逐项输出后续各项 if(p->coef>0) cout<<"+" cout<<p->coef; if(p->exp!=0) cout<<"X" if(p->exp>1) cout<<""<<p->exp; p=p->next; cout<<endl;mulpoly *poly_add(mulpoly *a,mulpol

7、y *b) / 两个多项式求和的函数 mulpoly *c, *pa, *pb, *pc, *q; c=new mulpoly; / 建立结果多项式单链表的头结点 pc=c; pa=a->next; pb=b->next; while(pa!=NULL)&&(pb!=NULL) if(pa->exp>pb->exp) / 被加项的指数较大 q=new mulpoly; q->coef=pa->coef; q->exp=pa->exp; pa=pa->next; pc->next=q; pc=q; else if(

8、pa->exp<pb->exp) / 被加项的指数较小 q=new mulpoly; q->coef=pb->coef; q->exp=pb->exp; pb=pb->next; pc->next=q; pc=q; else if(fabs(pa->coef+pb->coef)>1e-8) / 指数相同，系数之和非零 q=new mulpoly; q->coef=pa->coef+pb->coef; q->exp=pa->exp; pa=pa->next; pb=pb->next;

9、 pc->next=q; pc=q; else / 系数之和为零 pa=pa->next; pb=pb->next; while(pa!=NULL) / 链接多项式a的剩余项 q=new mulpoly; q->coef=pa->coef; q->exp=pa->exp; pa=pa->next; pc->next=q; pc=q; while(pb!=NULL) / 链接多项式b的剩余项 q=new mulpoly; q->coef=pb->coef; q->exp=pb->exp; pb=pb->next;

10、 pc->next=q; pc=q; pc->next=NULL; return c; / 返回头结点mulpoly *poly_multiply(mulpoly *a,mulpoly *b) / 两个多项式乘积的函数 mulpoly *c, *pa, *pb, *pc, *q, *p; int j, maxe; double m_coef; if(a->next=NULL)|(b->next=NULL) return NULL; / 某个多项式为0，乘积亦为0c= new mulpoly; / 建立结果多项式单链表的头结点 pc=c; pa=a->next; m

11、axe=(a->next->exp)+(b->next->exp); / 最高指数 while(pa!=NULL) / 双层循环使之各项相乘 pb=b->next; while(pb!=NULL) q= new mulpoly; / 为存储每次乘积建立一个结点 q->coef=(pa->coef)*(pb->coef); q->exp=pa->exp+pb->exp; pc->next=q; pc=q; pb=pb->next; pa=pa->next; pc->next=NULL; pa=c; pc=c

12、->next; / 暂存乘积的第一项地址 for(j=maxe; j>=0; j-) / 合并指数相同的各项 p=pc; m_coef=0.0; while(p!=NULL) if(p->exp=j) m_coef+=p->coef; p=p->next; if(fabs(m_coef)>1e-6) / 系数之和非零，建立新的结点存储结果项 q=new mulpoly; q->coef=m_coef; q->exp=j; pa->next=q; pa=q; pa->next=NULL; while(pc!=NULL) / 释放第一次乘

13、积运算的各项结点 p=pc; pc=pc->next; delete p; / free(p); return c;void main() / 主函数 mulpoly *ha, *hb, *hc, *hd; cout<<"Input each item of a multipoly:n" ha=create(); cout<<"Input each item of another multipoly:n" hb=create(); hc=poly_add(ha,hb); cout<<"The sum o

14、f a multipoly: " output(ha); cout<<" and another one: " output(hb); cout<<" is: " output(hc); cout<<endl; hd=poly_multiply(ha,hb); cout<<" Their multiply is: " output(hd);cout<<endl; return;3保存程序项目。在D盘根目录上建立一个以学号命名的文件夹，将程序项目的各种文件保存其中。4

15、编译、调试和执行。以上例程的运行结果如下图所示：实验二 哈夫曼树及哈夫曼编码译码的实现实验目的（1）掌握树的有关操作算法（2）熟悉树的基本存储方法（3）学习利用树求解实际问题实验环境（1）Windows 2000，或WindowsXP（简体中文）（2）Turbo C 3.0及以上，或Turbo Pascal 5.5及以上，或Visual C+ 6.0，或C+ Builder 6.0，或Visual C# 2005及以上，或Delphi 6.0及以上操作系统环境和编程环境（集成开发环境）任选以上所列之一。实验内容已知某通信系统中只使用A、B、C、D、E、F、G、H等8种字符，且各字符使用的频率依

16、次为0.05、0.29、0.07、0.08、0.14、0.23、0.03、0.11，试设计和输出其哈夫曼编码，并实现编码和译码的运算。解题思路：以上述8种字符作为叶子结点，各字符使用的频率作为各叶子结点的权值，用Hunffman算法构建哈夫曼树。采用顺序存储结构（数组）存储哈夫曼树及构树过程的信息，由于8个叶子结点的哈夫曼树共有15个结点，数组的大小为15。在构成哈夫曼树之后，为求哈夫曼编码需从叶子出发走一条从叶子到根的路径，而为译码需从根出发走一条从根到叶子的路径。则对于每个节点，既需知其双亲的信息，又需知其左、右孩子的信息。由此，数组元素结点应包含权值weight、双亲指针（下标）pare

17、nt、左孩子指针lch、右孩子指针rch。同时，另定义一个存储哈夫曼编码结果的二维数组。为使每一个字符编码都不是另一个字符编码的前缀，规定哈夫曼树中左分枝以“0”编码，右分枝以“1”编码。实现步骤：以C+ Builder环境为例，实现步骤如下：1新建一个Win32 Console Application程序项目。2在代码编辑窗口编写程序代码，含义如注释说明：#include <iostream.h>const short int n=8;char chn='A','B','C','D','E','

18、;F','G','H'double wn=0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11;typedef struct node double weight; short int parent,lch,rch; huffnode; / 哈夫曼树结点的数据类型typedef struct codenode short int coden; short int start; huffcodenode; / 字符的哈夫曼编码信息的数据类型huffnode htree2*n-1; / 哈夫曼树huffcodenode hcoden

19、; / 哈夫曼编码表short int p1,p2;void select_2_small(huffnode *ht,int m) / 选择2棵根结点权值最小的二叉树的函数 short int j,k; p1=-1; p2=-1; for(j=0; j<m; j+) / 先找出前面2个无双亲（即未合并的）结点的位置 if(htj.parent=-1) if(p1=-1) p1=j; else p2=j; break; if(htp1.weight>htp2.weight) / 交换p1和p2，使p1的权值小于p2的 p1=p1+p2; p2=p1-p2; p1=p1-p2; for

20、(k=j+1; k<m; k+) / 在其它结点中寻找根结点权值更小的二叉树 if(htk.parent!=-1) continue; else if(htk.weight<htp1.weight) p2=p1; p1=k; else if(htk.weight<htp2.weight) p2=k;void create_huffman_tree() / 建立哈夫曼树的函数 short int i; for(i=0; i<2*n-1; i+) / 初始化哈夫曼树 if(i<n) htreei.weight=wi; htreei.parent=-1; htreei.

21、lch=htreei.rch=-1; for(i=n; i<2*n-1; i+) / 构建哈夫曼树 select_2_small(htree,i); htreei.lch=p1; htreei.rch=p2; htreei.weight=htreep1.weight+htreep2.weight; htreep1.parent=i; htreep2.parent=i; void make_huffman_code() / 生成哈夫曼树的函数 short int i, child, father; for(i=0; i<n; i+) child=i; / 从叶子开始 father=h

22、treei.parent; hcodei.start=n-1; while(father!=-1) / 查找直到哈夫曼树根结点的路径 if(htreefather.lch=child) hcodei.codehcodei.start=0; / 左分枝编码为0 else hcodei.codehcodei.start=1; / 右分枝编码为1 hcodei.start-; child=father; father=htreefather.parent; hcodei.start+; / 校正编码的起始位置 void encode_process(char *sp) / 编码过程 cout<

23、<"Text："<<sp<<" and its Huffman codes：" while(*sp) p1=*sp-'A' for(short int j=hcodep1.start; j<n; j+) cout<<hcodep1.codej; sp+; cout<<endl;void decode_process(char *sp) / 译码过程 short int num; char ch,*q; cout<<"nHuffman codes："

24、<<sp<<" and its text：" while(*sp) num=1; ch=*sp; q=sp; while(*sp=ch)&&(num<4) / 分割编码 sp+; num+; p1=2*n-2; / 从哈夫曼树根结点开始 while(p1>=n) / 搜索直到叶子为止 if(*q='0') p1=htreep1.lch; else p1=htreep1.rch; q+; switch (p1) case 0: cout<<'A' break; case 1: co

25、ut<<'B' break; case 2: cout<<'C' break; case 3: cout<<'D' break; case 4: cout<<'E' break; case 5: cout<<'F' break; case 6: cout<<'G' break; default: cout<<'H' sp+; cout<<endl;void main() / 主函数 cre

26、ate_huffman_tree(); make_huffman_code(); cout<<"-n" for(int i=0; i<n; i+) cout<<chi<<": " for(short int j=hcodei.start; j<n; j+) cout<<hcodei.codej; cout<<endl; cout<<"-n" char bw="BHCDFEBBGAF" encode_process(bw); char

27、 hs="10100000000111101111010001110001110" decode_process(hs); return;3保存程序项目。在D盘根目录上建立一个以学号命名的文件夹，将程序项目的各种文件保存其中。4编译、调试和执行。以上例程的运行结果如下图所示：实验三 Dijkstra最短路径实验目的（1）掌握图的有关图相关操作算法（2）熟悉图的基本存储方法（3）了解掌握图的基本术语实验环境（1）Windows 2000，或WindowsXP（简体中文）（2）Turbo C 3.0及以上，或Turbo Pascal 5.5及以上，或Visual C+ 6.0，

28、或C+ Builder 6.0，或Visual C# 2005及以上，或Delphi 6.0及以上操作系统环境和编程环境（集成开发环境）任选以上所列之一。实验内容已知某交通网中，由站点A（源点）出发到达B、C、D、E、F、G、H、I等8个站点（终点）的可能路径如下有向连通网所示。编程计算和输出从A出发到达其它8个站点的最短路径和路径的长度。解题思路：这是一个典型的单源点最短路径问题，可以利用Dijkstra算法求解。有向连通的交通网信息，可以采用带权的邻接矩阵存储。运用Dijkstra算法计算出各最短路径上每个终点的前驱站点以及各最短路径的长度，再利用栈通过回溯的方法输出最短路径。实现步骤：以

29、C+ Builder环境为例，实现步骤如下：1新建一个Win32 Console Application程序项目。2在代码编辑窗口编写程序代码，含义如注释说明：#include <iostream.h>#define infinity 9999 / 定义无穷大const int mx=infinity;char station9='A','B','C','D','E','F','G','H','I' / 顶点列表int adjmat99=m

30、x, 40, 20, mx, 30, mx, mx, mx, mx, mx, mx, mx, 10, mx, mx, mx, mx, mx, mx, mx, mx, mx, mx, 25, mx, 40, mx, mx, mx, mx, mx, mx, mx, 10, mx, mx, mx, mx, mx, 10, mx, 15, 25, mx, mx, mx, mx, mx, mx, mx, mx, mx, mx, 30, mx, mx, mx, mx, mx, mx, mx, mx, 20, mx, mx, mx, mx, mx, mx, mx, mx, 35, mx, mx, mx, m

31、x, mx, mx, mx, mx, mx; / 带权的邻接矩阵int prev9; / 存储各最短路径终点的前驱站点的向量int dist9; / 存储各最短路径的长度的向量void path_Dijkstra() / Dijkstra算法求解最短路径的函数 int set9=0; / set向量表示已求得最短路径的终点的集合 int i,j,v,min; for(i=0; i<9; i+) disti=adjmat0i; if(disti!=mx) previ=0; else previ=-1; set0=1; / 集合set初始时仅包含源点 for(i=1; i<9; i+)

32、 min=mx; for(j=0; j<9; j+) / 查找当前的最短路径及终点v if(setj=0)&&(distj<min) min=distj; v=j; setv=1; / 终点v并入集合set for(j=0; j<9; j+) / 修正路径长度增加后的最短路径 if(setj=0)&&(distv+adjmatvj<distj) distj=distv+adjmatvj; prevj=v; void output_path(int v) / 输出源点到某一终点v的最短路径（独立完成） 建立栈空间; 初始化栈; 顶点u初始化

33、为终点v; while u非源点 u入栈; u改为u最为终点的前驱站点; 输出源点;while 栈非空 输出出栈站点; 输出最短路径的长度;void main() int i; path_Dijkstra(); / 计算最短路径 for(i=1; i<9; i+) output_path(i); / 输出各最短路径 return;3保存程序项目。在D盘根目录上建立一个以学号命名的文件夹，将程序项目的各种文件保存其中。4编译、调试和执行。以上例程的运行结果如下图所示：实验四 快速、堆、基数排序算法设计实验目的（1）熟悉排序的基本概念（2）掌握常用的排序方法和各种排序方法的实现（3）比较掌握

34、常用的排序方法和各种排序方法的时间复杂度实验环境（1）Windows 2000，或WindowsXP（简体中文）（2）Turbo C 3.0及以上，或Turbo Pascal 5.5及以上，或Visual C+ 6.0，或C+ Builder 6.0，或Visual C# 2005及以上，或Delphi 6.0及以上操作系统环境和编程环境（集成开发环境）任选以上所列之一。实验内容随机生成100个取值范围在0到999之间的整数，分别运用快速排序、堆排序和基数排序三种不同的算法编实现对其排序，并比较三种排序算法的时间复杂度。解题思路：随机产生100个0到999的整数存放于分别用于快速排序和堆排序的

35、2个整型数组和一个用于链式基数排序的静态链表之中。为整数序列的输出定义一个输出函数。依据快速、堆和基数排序三种不同的算法分别编写函数程序。实现步骤：以C+ Builder环境为例，实现步骤如下：1新建一个Win32 Console Application程序项目。2在代码编辑窗口编写程序代码，含义如注释说明：#include <iostream.h>#include <conio.h>typedef struct node int data; / 表示一个整数 int next; / 指示下一个结点的指针（下标） sqlist_node;/ 用于链式基数排序的静态链表的

36、结点类型void output(int L) / 输出数组中100个整数的函数 for(int i=0; i<100; i+) if(Li<10) cout<<" " else if(Li<100) cout<<" " cout<<Li; if(i+1) % 10=0) cout<<endl; / 按每行10个输出 else cout<<", " / 否则以逗号间隔 int partition(int L,int j,int k) / 快速排序一趟分割函数，

37、返回分割点位置（独立完成） 选定L中一个整数作为分割点的元素，并暂存; 当前端位置指针j小于后端位置指针k 自后端起向前顺序查找，找出第一个小于作为分割点的整数的位置k; 将Lk移动到j; 自前端起向后顺序查找，找出第一个大于作为分割点的整数的位置j; 将Lj移动到k; 将暂存的作为分割点的整数移动到k或j; / 此时j与k位置重叠 返回k或j;void sort_quick(int L,int s,int t) / 快速排序的递归算法 int m; if(s<t) m=partition(L,s,t); sort_quick(L,s,m-1); sort_quick(L,m+1,t);

38、 void heap_sift(int L,int s,int t) / 堆排序中，Ls.Lt范围内的堆的筛选（独立完成） 暂存根结点Ls; 令i为根结点的下标s; 令j为堆顶Ls的左孩子的下标 当j小于或等于最后一个结点的位置t 如果Li的右孩子存在且大于左孩子Lj, 则令j为右孩子的下标; 若已经是堆，则break; 键值较Ls大的Lj上升至i; 令i为j; 令j为Li的左孩子的下标; 将暂存的Ls下降到i;void sort_heap(int L,int n) / 堆排序 int i; for (i=n/2-1;i>=0;i-) heap_sift(L,i,n-1); / 反复筛选

39、，建初始堆 for (i=n-1;i>0;i-) swap(L0,Li); / 将最大元素(堆顶)L0与最后一个元素Li交换 heap_sift(L,0,i-1); / 重新调整和筛选0.i-1范围内的堆 void distribute(sqlist_node R,int p,int i,int f,int e) / 按第i位关键字的分配算法 int j; for(int j=0; j<10; j+) fj=-1; switch(i) case 1: i=100; break; case 2: i=10; break; case 3: i=1; while(p!=-1) j=(Rp.data/i)%10; / 取记录Rp的第i位关键字 if(fj=-1) fj=p; else Rej.next=p; ej=p; / 队尾指针指向当前队尾 p=Rp.next; / 找下一个记录 void collect(sqlist_node R,int &p,int i,int f,int e) / 完成一趟收集过程的算法 int j=0, t; while(fj=-1) j+; / 找第1个非空队列 p=fj; / 表头指针指向