《《数据结构》实验指导(09-10一)》由会员分享，可在线阅读，更多相关《《数据结构》实验指导(09-10一)（17页珍藏版）》请在金锄头文库上搜索。
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）多项
2、式的输出， 3）多项式的相加运算，4）多项式的乘积运算。解题思路： 以线性表来描述一元多项式，存储结构采用单链表，每个结点存储多项式中某一项的系数和 指数，建立单链表时指数低的结点列于指数高的结点之后，即线性表的元素按指数递减有序排列。 在多项式求和运算时，将指数相同的项的系数相加，其和非 0 则存储该项。乘积运算时，运用循 环将 2 个多项式的各项交叉相乘，存储每 2 项的积（系数的积，指数的和）于新建立的结点，之 后将这些结点中指数相同的各项系数之和非 0 的项合并为 1 个结点，最后释放多余的临时结点。 实现步骤： 以 C+ Builder 环境为例，实现步骤如下： 1新建一个 Win3
3、2 Console Application 程序项目。 2在代码编辑窗口编写程序代码，含义如注释说明： #include #include typedefstruct 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) / 循环建立各项结点，直到输入指数是零为止 coutx; / 输入系数couty; / 输入指数if(x) q=new mulpoly;q-coef=x; q-exp=y; / 存系数和指数p-next=q; / 前驱的 next 指向新建结点p=q; / 下一个结点的前驱即当前结点if(ynext=NULL; / 最后一项结点无后继return h; / 返回头指针 void output(mulpoly *h) / 遍历单链表，输出一元多项式的函数 mulpoly *p;coutnext;if(p=NULL) coutcoef;if(p-exp!=0) coutexp1) coute
5、xp;p=p-next;while(p!=NULL) / 逐项输出后续各项 if(p-coef0) coutcoef;if(p-exp!=0) coutexp1) coutexp;p=p-next;coutnext; pb=b-next;while(pa!=NULL)q-coef=pa-coef; q-exp=pa-exp; pa=pa-next;pc-next=q; pc=q;else if(pa-expexp) / 被加项的指数较小 q=new mulpoly;q-coef=pb-coef; q-exp=pb-exp; pb=pb-next;pc-next=q; pc=q;else if(
6、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;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 的剩余项
7、 q=new mulpoly;q-coef=pb-coef; q-exp=pb-exp; pb=pb-next;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，乘积亦为 0 c= new mulpoly; /
8、 建立结果多项式单链表的头结点pc=c;pa=a-next;maxe=(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-next; / 暂存乘积的第一项地址for(j=maxe; j=0; j-)
9、 / 合并指数相同的各项 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) / 释放第一次乘积运算的各项结点 p=pc;pc=pc-next;delete p; / free(p);return c; void main() / 主函数 mulpoly *ha, *h
10、b, *hc, *hd;cout const short int n=8; char chn=A,B,C,D,E,F,G,H; double wn=0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11; typedefstruct node double weight;short int parent,lch,rch;huffnode; / 哈夫曼树结点的数据类型 typedefstruct codenode short int coden;short int start;huffcodenode; / 字符的哈夫曼编码信息的数据类型 huffnode htree2*
11、n-1; / 哈夫曼树 huffcodenode hcoden; / 哈夫曼编码表 short int p1,p2;void select_2_small(huffnode *ht,int m) / 选择 2 棵根结点权值最小的二叉树的函数 short int j,k;p1=-1; p2=-1;for(j=0; jhtp2.weight) / 交换 p1 和 p2，使 p1 的权值小于 p2 的 p1=p1+p2;p2=p1-p2;p1=p1-p2;for(k=j+1; k=n) / 搜索直到叶子为止 if(*q=0) p1=htreep1.lch;else p1=htreep1.rch;q+
12、;switch (p1) case 0: cout #define infinity 9999 / 定义无穷大 const int mx=infinity; char station9=A,B,C,D,E,F,G,H,I; / 顶点列表 int adjmat99=mx, 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,
13、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, mx, mx, mx, mx, mx, mx; / 带权的邻接矩阵int prev9; / 存储各最短路径终点的前驱站点的向量 int dist9; / 存储各最短路径的长度的向量void path_Dijkstra() / Dijkstra 算法求解最短路径的函数 int set9=0; / set 向量表示已求得最短路径的终点的集合int i,j
14、,v,min;for(i=0; i #include typedefstruct node int data; / 表示一个整数int next; / 指示下一个结点的指针（下标）sqlist_node;/ 用于链式基数排序的静态链表的结点类型void output(int L) / 输出数组中 100 个整数的函数 for(int i=0; i=0;i-) heap_sift(L,i,n-1); / 反复筛选，建初始堆for (i=n-1;i0;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; j0; j-) / 从第 3 位关键字开始 distribute(R,p,j,f,e); / 分配操作collect(R,p,j,f,e); / 收集操作 void output_sqlist(sqlist_node *R,int p) / 遍历静态链表，输出 100 个整数的函数 int m=0
