教学单位计算机与信息科学学院学生学号014301754127数据结构（课程设计）学生姓名专业名称软件工程指导教师2016年5月28日目录1．多项式的基本运算 (1)1.1 实验目的 (1)1.2 实验内容 (1)1.3 实验方法 (1)1.4 实验结果 (7)1.5 小结 (7)2．栈的应用—逆波兰式求值 (7)2.1 实验目的 (7)2.2 实验内容 (7)2.3 实验方法 (8)2.4 实验结果 (14)2.5 小结 (15)3．图的应用—简易的社交网络图 (15)3.1 实验目的 (15)3.2 实验内容 (15)3.3 实验方法 (16)3.4 实验结果 (17)3.5 小结 (17)4 .课程设计四、哈夫曼编码 (17)4.1 实验目的 (17)4.2 实验内容 (17)4.3 实验方法 (18)4.4 实验结果 (23)4.5 小结 (23)5 .哈希表的相关运算 (24)5.1 实验目的 (24)5.2 实验内容 (24)5.3 实验方法 (24)5.4 实验结果 (27)5.5 小结 (28)6 .排序方法 (28)6.1 实验目的 (28)6.2 实验内容 (28)6.3 实验方法 (28)6.4 实验结果 (33)6.5 小结 (33)1．多项式的基本运算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实验方法#include <stdio.h>#include <malloc.h>#define MAX 20 //多项式最多项数typedef struct //定义存放多项式的数组类型{double coef; //系数int exp; //指数} PolyArray;typedef struct pnode //定义单链表结点类型，保存多项式中的一项，链表构成多项式{double coef; //系数int exp; //指数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->coef>0)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;}printf("\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; i<n; i++){s=(PolyNode *)malloc(sizeof(PolyNode));//创建新结点s->coef=a[i].coef;s->exp=a[i].exp;r->next=s; //将*s插入*r之后r=s;}r->next=NULL; //终端结点next域置为NULL}void 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->next->exp>p->exp)q=q->next; //在有序表中找插入*p的前驱结点*qp->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->exp>pb->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->exp<pb->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;}//**************void minus(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->exp>pb->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->exp<pb->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;}//**************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("原多项式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.5 小结这次实验让我进一步对线性表的存储结构有了更深层次的理解，对解决问题的方法有了更多的认识2．栈的应用—逆波兰式求值2.1 实验目的掌握栈的特点及其描述方法；掌握栈的各种基本操作；掌握栈的一个经典应用-逆波兰式求值问题。