数据结构课程设计

教学单位计算机与信息科学学院学生学号014301754127数据结构（课程设计）学生姓名专业名称软件工程指导教师2016年5月28日1目录1．多项式的基本运算...............................................11.1实验目的.....................................................11.2实验内容.....................................................11.3实验方法.....................................................11.4实验结果.....................................................71.5小结........................................................72．栈的应用—逆波兰式求值.........................................72.1实验目的.....................................................72.2实验内容.....................................................72.3实验方法.....................................................82.4实验结果....................................................142.5小结.......................................................153．图的应用—简易的社交网络图....................................153.1实验目的....................................................153.2实验内容....................................................153.3实验方法....................................................163.4实验结果....................................................173.5小结.......................................................174.课程设计四、哈夫曼编码.........................................174.1实验目的....................................................174.2实验内容....................................................174.3实验方法....................................................184.4实验结果....................................................234.5小结.......................................................235.哈希表的相关运算...............................................245.1实验目的....................................................245.2实验内容....................................................245.3实验方法....................................................245.4实验结果...................................................275.5小结.......................................................286.排序方法......................................................286.1实验目的...................................................286.2实验内容....................................................286.3实验方法....................................................286.4实验结果....................................................336.5小结.......................................................3311．多项式的基本运算1.1实验目的掌握线性表的链式存储结构和线性表的典型应用—多项式求和、差运算，通过实验进一步加深对线性表的存储结构的理解与熟悉。1.2实验内容链式存储结构的实现：已知：f(x)=100x＾100+5x＾50-30x＾10+10,g(x)=150x＾90-5x＾50+40x＾20+20x＾10+3x,求和与差。解题思路：定义一个结构体数组，p存储系数,q存储指数。分别输出两次输入的多项式。将两次输入的多项式的指数按从大到小的顺序进行排列，同时相应的系数要进行交换。输出时如果进行如果当前该项与下一项的的系数相同，将两项系数相加后输出，并跳过下一项，如果不相等，直接输出。输出时需注意的问题：当系数为0时，该项不输出当系数为负数时，不要再在前面输出+。1.3实验方法#includestdio.h#includemalloc.h#defineMAX20//多项式最多项数typedefstruct//定义存放多项式的数组类型{doublecoef;//系数intexp;//指数}PolyArray;typedefstructpnode//定义单链表结点类型，保存多项式中的一项，链表构成多项式{doublecoef;//系数intexp;//指数structpnode*next;}PolyNode;voidDispPoly(PolyNode*L)//输出多项式{2boolfirst=true;//first为true表示是第一项PolyNode*p=L-next;while(p!=NULL){if(first)first=false;elseif(p-coef0)printf(+);if(p-exp==0)printf(%g,p-coef);elseif(p-exp==1)printf(%gx,p-coef);elseprintf(%gx^%d,p-coef,p-exp);p=p-next;}printf(\n);}voidDestroyList(PolyNode*&L)//销毁单链表{PolyNode*p=L,*q=p-next;while(q!=NULL){free(p);p=q;q=p-next;}free(p);}voidCreateListR(PolyNode*&L,PolyArraya[],intn)//尾插法建表{PolyNode*s,*r;inti;L=(PolyNode*)malloc(sizeof(PolyNode));//创建头结点L-next=NULL;r=L;//r始终指向终端结点,开始时指向头结点for(i=0;in;i++){s=(PolyNode*)malloc(sizeof(PolyNode));//创建新结点s-coef=a[i].coef;s-exp=a[i].exp;r-next=s;//将*s插入*r之后3r=s;}r-next=NULL;//终端结点next域置为NULL}voidSort(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-next-expp-exp)q=q-next;//在有序表中找插入*p的前驱结点*qp-next=q-next;//将*p插入到*q之后q-next=p;p=r;}}}voidAdd(PolyNode*ha,PolyNode*hb,PolyNode*&hc)//求两有序集合的并，完成加法{PolyNode*pa=ha-next,*pb=hb-next,*s,*tc;doublec;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;}4elseif(pa-exppb-exp){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*)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=(PolyNode*)malloc(sizeof(PolyNode));//复制结点s-exp=pa-exp;s-coef=pa-coef;tc-next=s;tc=s;pa=pa-next;}tc-next=NULL;}//**************voidminus(PolyNode*ha,PolyNode*hb,PolyNode*&hc)//求两有序集合的并，完成减法{PolyNode*pa=ha-next,*pb=hb-next,*s,*tc;doublec;hc=(PolyNode*)malloc(sizeof(PolyNode));//创建头结点tc=hc;5while(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;}elseif(pa-exppb-exp){s=(PolyNode*)malloc(sizeof(PolyNode));//复