数据结构课程设计(共35页).docx

《数据结构课程设计(共35页).docx》由会员分享，可在线阅读，更多相关《数据结构课程设计(共35页).docx（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上教学单位计算机与信息科学学院学生学号 7数据结构（课程设计）学生姓名专业名称软件工程指导教师2016年5月28日专心-专注-专业目录1多项式的基本运算1.1 实验目的掌握线性表的链式存储结构和线性表的典型应用多项式求和、差运算，通过实验进一步加深对线性表的存储结构的理解与熟悉。1.2 实验内容链式存储结构的实现：已知：f(x)=100x100+5x50-30x10+10, g(x)=150x90-5x50+40x20+20x10+3x,求和与差。解题思路：定义一个结构体数组，p存储系数,q存储指数。分别输出两次输入的多项式。将两次输入的多项式的指数按从大到小的顺序进行

2、排列，同时相应的系数要进行交换。输出时如果进行如果当前该项与下一项的的系数相同，将两项系数相加后输出，并跳过下一项，如果不相等，直接输出。输出时需注意的问题：当系数为0时，该项不输出当系数为负数时，不要再在前面输出+。1.3实验方法#include #include #define MAX 20 /多项式最多项数typedef struct /定义存放多项式的数组类型 double coef; /系数 int exp; /指数 PolyArray;typedef struct pnode /定义单链表结点类型，保存多项式中的一项，链表构成多项式 double coef; /系数 int exp

3、; /指数struct pnode *next; PolyNode;void DispPoly(PolyNode *L) /输出多项式 bool first=true; /first为true表示是第一项 PolyNode *p=L-next;while (p!=NULL) if (first)first=false;else if (p-coef0)printf(+);if (p-exp=0)printf(%g,p-coef);else if (p-exp=1)printf(%gx,p-coef);elseprintf(%gx%d,p-coef,p-exp); p=p-next; print

4、f(n);void DestroyList(PolyNode *&L) /销毁单链表 PolyNode *p=L,*q=p-next;while (q!=NULL) free(p); p=q; q=p-next; free(p);void CreateListR(PolyNode *&L, PolyArray a, int n) /尾插法建表 PolyNode *s,*r;int i; L=(PolyNode *)malloc(sizeof(PolyNode); /创建头结点 L-next=NULL; r=L; /r始终指向终端结点,开始时指向头结点for (i=0; icoef=ai.coe

5、f;s-exp=ai.exp; r-next=s; /将*s插入*r之后 r=s; r-next=NULL; /终端结点next域置为NULLvoid Sort(PolyNode *&head) /按exp域递减排序 PolyNode *p=head-next,*q,*r;if (p!=NULL) /若原单链表中有一个或以上的数据结点 r=p-next; /r保存*p结点后继结点的指针 p-next=NULL; /构造只含一个数据结点的有序表 p=r;while (p!=NULL) r=p-next; /r保存*p结点后继结点的指针 q=head;while (q-next!=NULL & q

6、-next-expp-exp) q=q-next; /在有序表中找插入*p的前驱结点*q p-next=q-next; /将*p插入到*q之后 q-next=p; p=r; void Add(PolyNode *ha,PolyNode *hb,PolyNode *&hc) /求两有序集合的并，完成加法 PolyNode *pa=ha-next,*pb=hb-next,*s,*tc;double c; hc=(PolyNode *)malloc(sizeof(PolyNode); /创建头结点tc=hc;while (pa!=NULL & pb!=NULL) if (pa-exppb-exp)

7、s=(PolyNode *)malloc(sizeof(PolyNode); /复制结点s-exp=pa-exp;s-coef=pa-coef;tc-next=s;tc=s;pa=pa-next; else if (pa-expexp) s=(PolyNode *)malloc(sizeof(PolyNode); /复制结点s-exp=pb-exp;s-coef=pb-coef;tc-next=s;tc=s;pb=pb-next; else /pa-exp=pb-exp c=pa-coef+pb-coef;if (c!=0) /系数之和不为0时创建新结点 s=(PolyNode *)mallo

8、c(sizeof(PolyNode); /复制结点s-exp=pa-exp;s-coef=c;tc-next=s;tc=s; pa=pa-next;pb=pb-next; if (pb!=NULL) pa=pb; /复制余下的结点while (pa!=NULL) s=(PolyNode *)malloc(sizeof(PolyNode); /复制结点s-exp=pa-exp;s-coef=pa-coef;tc-next=s;tc=s;pa=pa-next; tc-next=NULL;/*void minus(PolyNode *ha,PolyNode *hb,PolyNode *&hc) /求

9、两有序集合的并，完成减法 PolyNode *pa=ha-next,*pb=hb-next,*s,*tc;double c; hc=(PolyNode *)malloc(sizeof(PolyNode); /创建头结点tc=hc;while (pa!=NULL & pb!=NULL) if (pa-exppb-exp) s=(PolyNode *)malloc(sizeof(PolyNode); /复制结点s-exp=pa-exp;s-coef=pa-coef;tc-next=s;tc=s;pa=pa-next; else if (pa-expexp) s=(PolyNode *)malloc

10、(sizeof(PolyNode); /复制结点s-exp=pb-exp;s-coef=pb-coef;tc-next=s;tc=s;pb=pb-next; else /pa-exp=pb-exp c=pa-coef-pb-coef;if (c!=0) /系数之和不为0时创建新结点 s=(PolyNode *)malloc(sizeof(PolyNode); /复制结点s-exp=pa-exp;s-coef=c;tc-next=s;tc=s; pa=pa-next;pb=pb-next; if (pb!=NULL) pa=pb; /复制余下的结点while (pa!=NULL) s=(Poly

11、Node *)malloc(sizeof(PolyNode); /复制结点s-exp=pa-exp;s-coef=pa-coef;tc-next=s;tc=s;pa=pa-next; tc-next=NULL;/*int main() PolyNode *ha,*hb,*hc; PolyArray a= 100,100,5,50,3,10,10,0; PolyArray b= 150,90,5,50,40,20,20,10,3,1;CreateListR(ha,a,4);CreateListR(hb,b,5); printf(原多项式A: );DispPoly(ha); printf(原多项式

12、B: );DispPoly(hb);Sort(ha);Sort(hb); printf(有序多项式A: );DispPoly(ha); printf(有序多项式B: );DispPoly(hb);Add(ha,hb,hc); printf(多项式相加: );DispPoly(hc);DestroyList(hc);minus(ha,hb,hc);printf(多项式相减：);DispPoly(hc);DestroyList(ha);DestroyList(hb);DestroyList(hc);return 0;1.4实验结果1.5 小结这次实验让我进一步对线性表的存储结构有了更深层次的理解，

13、对解决问题的方法有了更多的认识2栈的应用逆波兰式求值2.1 实验目的掌握栈的特点及其描述方法；掌握栈的各种基本操作；掌握栈的一个经典应用-逆波兰式求值问题。2.2 实验内容从键盘敲入一个整数表达式，先将其转化为逆波兰表达式，再计算值。解题思路：逆波兰式又叫后缀表达式，规定把运算符号放在两个操作数的后面。在后缀表达式中，不存在运算符的优先级问题，也不存在任何括号。后缀表达式求值的步骤：1.初始化一个空操作数栈；2.从前到后读取后缀表达式字符。如果是操作数直接入栈。如果读到一个操作符，弹出栈顶元素a和新的栈顶元素b，执行b a，将结果压入栈中；3.最后栈中只剩下一个元素，即表达式的值。2.3实验方

14、法源代码如下：#include#includetypedef structchar s2020;int top;SQ;void copystr(char *a,char *b)int i=0;do bi=ai;i+; while(ai!=0);bi=0;void voidSQ(SQ *s) s-top=-1;int ifempty(SQ *s) return(s-top=-1);void push(SQ *S,char *c)if(S-top=19)printf(over flown);else S-top+;copystr(c,S-sS-top); char *pop(SQ *S)if(if

15、empty(S) printf(over flow!n);return(NULL); elsereturn(S-sS-top-);int judge(char *c) if(c1=0)switch(c0) case +:return(3);case -:return(3);case *:return(2);case /:return(2);default:return(1); elsereturn(1);void write(char *a,char *b,char *c)strcat(a,c);strcat(a,b);int seek(char *c,int start)int signal

16、=1;for(start=start+;cstart!=0&signal!=0;start+) if(cstart=)signal-;else if(cstart=()signal+; if(signal=0)return(start-1);else printf(输入无效式子n);return(-1); void FB(SQ *A,SQ *B)for(;!ifempty(A);) push(B,A-sA-top);pop(A); char *rewrite(char *A) SQ front; SQ back;int i,j,k,flag=0;char *result;char mid20;

17、voidSQ(&front);voidSQ(&back);for(i=0;Ai!=0;) if(Ai=() j=seek(A,i);for(k=i+1;k=2;) flag=0;for(i=0;i=2;) if(judge(front.sfront.top)=1&judge(front.sfront.top-1)=2&judge(front.sfront.top-2)=1) write(front.sfront.top,front.sfront.top-1,front.sfront.top-2);push(&back,front.sfront.top);pop(&front);pop(&fro

18、nt);pop(&front); else push(&back,front.sfront.top);pop(&front); FB(&front,&back);FB(&back,&front); else for(;front.top=2;) if(judge(front.sfront.top)=1&judge(front.sfront.top-1)=3&judge(front.sfront.top-2)=1) write(front.sfront.top,front.sfront.top-1,front.sfront.top-2);push(&back,front.sfront.top);

19、pop(&front);pop(&front);pop(&front); else push(&back,front.sfront.top);pop(&front); FB(&front,&back);FB(&back,&front); result=front.sfront.top;return(result);typedef structchar c20;int top;sq;int execute(char a,char b,char c)switch(a) case(+):return(c-48)+(b-48);case(-):return(c-48)-(b-48);case(*):r

20、eturn(c-48)*(b-48);case(/):return(c-48)/(b-48); void voidsq(sq *s)s-top=-1;int ifsqempty(sq *s)return(s-top=-1);void pushsq(sq *s,char x)if(s-top=19)printf(over flow!n);else s-top=s-top+1;s-cs-top=x; void popsq(sq *s)if(ifsqempty(s)printf(over flow!n);elses-top-;int just(char c) switch(c) case (+):r

21、eturn(0);case (-):return(0);case (*):return(0);case (/):return(0);default:return(1); void restread(sq *a,sq *b)for(;!ifsqempty(a);) pushsq(b,a-ca-top);popsq(a); int calculate(char *c)sq rest,read;int i,re;voidsq(&rest);voidsq(&read);for(i=0;ci!=0;i+)pushsq(&read,ci);for(;read.top=2;) for(;read.top=2

22、;) if(just(read.cread.top)=0&just(read.cread.top-1)=1&just(read.cread.top-2) =1) re=execute(read.cread.top,read.cread.top-1,read.cread.top-2);pushsq(&rest,re+48);popsq(&read);popsq(&read);popsq(&read); else pushsq(&rest,read.cread.top);popsq(&read); restread(&read,&rest);restread(&rest,&read); retur

23、n(read.c0-48);void main()char re20;char a20; printf(请输入算式：n);scanf(%s,a);copystr(rewrite(a),re); printf(逆波兰式：n%sn,re); printf(求值结果：n%dn,calculate(re);2.4实验结果2.5 小结通过这次实验，我对栈的特点及其描述方法有了更深的认识，掌握了栈的基本操作，也对逆波兰求值问题的解决办法有了更深的理解3图的应用简易的社交网络图3.1 实验目的（1） 掌握图的几种存储方法（邻接矩阵、邻接表等）；（2） 掌握图的连通和图中各节点的联系。3.2 实验内容给出如图

24、所示的简易社交连通图：ABCDEF要求：输入A,B,C,D,E,F处的人名，计算某两人之间的陌生度（即权值的大小之和）与连通两人的通路（权值在下面的代码中已给出）。解题思路：直接相连的两个节点间边的权值就是两节点间的亲密度（陌生度），权值越小，节点间越亲密；通过邻接矩阵给出的数值可以求出两节点间的亲密度；通过迪克斯特卡算法可以求出不相邻的两节点间的权值之和和经过的节点，从而达到解决问题的目的。3.3实验方法#includevoid createms()int i,j,s,e;char ch1,ch2;int b1010=0,10,20,30,9999,40,10,0,15,9999,9999,

25、9999,20,15,0,5,9999,50,30,9999,5,0,10,18,9999,9999,9999,10,0,5,40,9999,50,18,5,0;int n=5;int Min=9999;int v,k=0;int low100,vis100;char a10=A,B,C,D,E,F,c1010;printf(请输入顶点数序号：(输入两个序号用“,”隔开，例如A,B)n);printf(n);scanf(%c,%c,&ch1,&ch2);for(i=0;ch1!=ai;i+); for(j=0;ch2!=aj;j+); s=i;e=j;for(i=0;i=n;i+) lowi=

26、bsi;visi=0;lows=0;viss=1;for(i=0;in;i+) for(j=0;j=n;j+) if(!visj&lowjMin) Min=lowj; v=j; if(Min=9999) printf(-1);visv=1;for(j=0;jbvj+lowv) lowj=bvj+lowv;cjk+1=av;Min=9999; printf(%c和%c之间的最短距离为：,as,ae);printf(%dn,lowe);for(i=0;ik;i+) printf(%c,ci); printf(n); void main() createms();3.4实验结果3.5 小结这次实验，

27、我掌握了图的几种存储方法，对图的连通和图中各节点的联系有了更深的理解4 .课程设计四、哈夫曼编码4.1 实验目的用所学的知识构造一棵哈夫曼树并以英文字母出现的次数做权值，遍历哈夫曼树同时输出每个字母的哈夫曼编码。4.2 实验内容构造哈夫曼编码的方法如下：第一步定义一个结点的结构体，包括结点的权值，结点的双亲结点，左孩子，右孩子。并定义两个HTNode,*HuffmanTree为该类型的名字。第二步创建一个Select函数用来选择结点较小的结点权值和下标。实现方法主要利用两个for循环实现。首先判断是否是单个结点如果是跳出for循环如果不是定义p和s记录当前结点的权值和记录当前结点的下标。接着通

28、过一个for循环进行选择把结点权值最小的1 4结点权值和下标记录分别记录在p和s中。第三步构造哈夫曼树和求每个字符的哈夫曼编码。先判断结点个数n是否小于等于1如果是则返回如果大于1则计算出哈夫曼树中共有m=2n-1个结点。然后创建一个HTNode类型的数组HT存储结点个数（结点的相关信息），再定义一个HuffmanTree类型的指针P用来指向数组HT。将HT中前n个单元保存输入的结点信息，后m-n个单元保存为空结点。接着构造哈夫曼树，其实现方法为首先利用Select函数选择权值最小的两个结点s1和s2再将将s1和s2合并从而得到这两个结点的双亲结点保存为i，且双亲结点的权值为s1,s2权值之和

29、。接着从叶子到根逆向求每个字符的哈夫曼编码。其实现方法为：首先创建一个字符指针数组HC和一个字符型指针数组cd用来存储0和1。定义c表示结点序号，f表示c结点的双亲结点序号，接着通过一个for循环将建立好的哈夫曼树的左边赋值为0右边赋值1，再为每一个结点创建一个长度为n-start的字符数组用来存储哈夫曼编码。最后把从cd地址开始且含有NULL结束符的字符串赋值到以HC开始的地址空间。第四步main函数的实现。首先定义一个HuffmanTree类型的HT初始化为空。接着输入哈夫曼权值的个数判断个数是否小于等于1如果小于等于1则输出输入错误,哈夫曼权值的个数要大于1。如果大于1则创建一个w指针数

30、组用来存储结点权值，最后通过调用HuffmanCoding函数输出每个结点的哈夫曼编码。4.3实验方法#include #include #include #include/类型相关变量的定义#define n 100 #define m 2*n-1 typedef struct char ch; char co9; /存放编码int len; CodeNode; typedef CodeNode HuffmanCoden+1; typedefstruct int weight; int left,right,parent; HTNode; typedef HTNode HuffmanTree

31、m+1; int num; void select_min(HuffmanTree T,int k,int &x1,int &x2) /选择权值最小的两个根结点,其序号为x1和x2 int i,j; int min1=1000; for(i=1;i=k;i+) /找最小值if(Ti.weightmin1 &Ti.parent=0) j=i; min1=Ti.weight; x1=j;min1=1000; for (i=1;i=k;i+) /找次小值if(Ti.weightmin1&Ti.parent=0&i!=x1) j=i; min1=Ti.weight; x2=j; int tongji(

32、char *s,int cishu,char str) /统计字符串中各种字母的个数以及字符的种类int i,j,k; char *p; int t27; for(i=1;i=A&*p=Z) k=*p-64; tk+; for(i=1,j=0;i=26;+i) if(ti!=0 ) j+; strj=i+64; /送对应的字母到数组中cishuj=ti; /存入对应字母的权值return j; /j是输入字母种数 void Create_huffmanTree(HuffmanTree ht,HuffmanCode hc,int cishu,char str) /生成哈夫曼树HT int i,s

33、1,s2; for(i=0;i2*num-1;i+) hti.left=0; hti.right=0; hti.parent=0; hti.weight=0; for(i=1;i=num;i+) /输入num个叶结点的权值hti.weight=cishui; for(i=num+1;i=2*num-1;i+) /选择parent为0且权值最小的两个根结点，其序号为s1和s2,i为双亲select_min(ht,i-1,s1,s2); hts1.parent=i;hts2.parent=i; hti.left=s1; hti.right=s2; hti.weight=hts1.weight+ht

34、s2.weight; for(i=0;i=num;i+) hci.ch=stri; /字符的种类i=1;while(i=num) printf(字符%c次数:%8dn,hci.ch,cishui+); void Huffman_bianma(HuffmanTree T,HuffmanCode H) /根据哈夫曼树T求哈夫曼编码H int child,parent,i; /child和parent分别指示t中孩子和双亲char coden; /存放编码int start; /指示码在code中的起始位置codenum=0; /最后一位（第num个）放上串结束符for(i=1;i0) /直至tchild是树根为止 /若tchild是tparent的左孩子,则生成0;否则生成1 if(Tparent.left=child) code-start=0; elsecode-start=1; child=parent; strcpy(Hi.co,&codestart); Hi.len=num-start; void coding(HuffmanCode hc ,char *str) /对str所代表的字符串进行编码并写入文件int i,j; FILE *fp; fp=fopen(codefile.txt,