实验指导书(2007级).doc

数据结构实验指导书适用专业：网络工程系网络、信安专业指导教师：王祖俪实验一：线性表的基本操作实验目的：掌握线性表的基本操作：插入、删除、查找以及线性表合并等运算在顺序存储结构的运算。能从实际问题中抽象出线性表结构及其运算的模型实验课时：3课时实验要求：1. 掌握线性表的顺序存储的基本运算的算法和程序2. 掌握线性表链式存储的基本运算的算法3. 根据算法写出对应程序（使用语言没有硬性规定，但推荐使用C）4. 调试成功，并保存程序源代码，以备检查实验内容：1. 设计实现用户通过键盘输入一组数，并输入一个需要插入的数，和插入的位置，完成整个插入。例，输入1，2，3，4再输入5，3。最后程序运行结果为1，2，5，3，4。1) 先写出完成该操作的算法或执行流程2) 以程序方式实现算法3) 数的长短自行先定义，可以用数组存储。4) 注意插入位置的判断2验证上机实现链表的基本操作程序，并结合对应的算法，了解链表的工作情况。#include#include#includestruct mylistint data;struct mylist *next;struct mylist *createlist(void)int x;struct mylist *s,*q,*h;h=(struct mylist *)malloc(sizeof(struct mylist);h-next=NULL;q=h;printf(input number:);scanf(%d,&x);while(x!=0)s=(struct mylist*)malloc(sizeof(struct mylist);s-data=x;q-next=s;printf(input the number:);scanf(%d,&x);s-next=NULL;q=s;return(h);int putlist(struct mylist *head)int i=0;if(head-next=NULL)return 0;while (head-next !=NULL)i+;printf(the %d number in list is:%dn,i,head-next-data);head=head-next;return 1;void main()struct mylist *my,*a;my=createlist();if(putlist(my)=0)printf(the input list is empty!);while(my-next !=NULL)a=my;my=my-next;free(a);printf(over,press any key to end);getch(); 3将第1题所描述问题用链表方式实现，并以实验报告形式提交（报告2）4验证上机实现一元多项式的加法程序，并结合算法理解链表的工作过程和基本操作的实现。#include#include#include#define LEN sizeof(node) typedef struct polynode /*用单链表存储多项式的结点结构*/ int coef; /*多项式的系数*/ int exp; /*指数*/ struct polynode *next; /*它又指向struct polynode类型的数据，以此建立链表*/node; /*意即node*与list同为结构指针类型*/node * create(void) /*用尾插法建立一元多项式的链表的函数*/node *h,*r,*s; int c,e;h=(node *)malloc(LEN); /*建立多项式的头结点，为头结点分配存储空间*/ r=h; /*r指针始终动态指向链表的当前表尾，以便于做尾插入，其初值指向头结点*/printf(coef:);scanf(%d,&c); /*输入系数*/ printf(exp: );scanf(%d,&e); /*输入指数*/while(c!=0) /*输入系数为0时，表示多项式的输入结束*/ s=(node *)malloc(LEN); /*申请新结点*/ s-coef=c; /*申请新结点后赋值*/ s-exp=e; /*申请新结点后赋值*/r-next=s; /*做尾插，插入新结点*/ r=s; /*r始终指向单链表的表尾*/printf(coef:);scanf(%d,&c); printf(exp: );scanf(%d,&e);r-next=NULL; /*将表的最后一个结点的next置NULL，以示表结束*/ return(h);void polyadd(node *polya, node *polyb) /*一元多项式相加函数，用于将两个多项式相加，然后将和多项式存放在多项式polya中，并将多项式ployb删除*/ node *p,*q,*pre,*temp;int sum;p=polya-next; /*令p和q分别指向polya和polyb多项式链表中的第一个结点*/q=polyb-next;pre=polya; /*位置指针，指向和多项式polya*/ while(p!=NULL&q!=NULL) /*当两个多项式均未扫描结束时，执行以下操作*/ if(p-expexp) /*若p指向的多项式指数小于q指的指数*/pre-next=p; /*将p结点加入到和多项式中*/ pre=pre-next; p=p-next; else if(p-exp=q-exp) /*若指数相等，则相应的系数相加*/sum=p-coef+q-coef;if(sum!=0)p-coef=sum; pre-next=p;pre=pre-next;p=p-next;temp=q;q=q-next;free(temp); /b表中删除这个结点 else /*如果系数和为零，则删除结点p与q，并将指针指向下一个结点*/ temp=p-next;free(p);p=temp;temp=q-next;free(q);q=temp; else /*若p指数大于q指数*/ pre-next=q; /*p结点不动，将q结点加入到和多项式中*/pre=pre-next;q=q-next; if(p!=NULL) /*多项式A中还有剩余，则将剩余的结点加入到和多项式中*/ pre-next=p; else /*否则将B的结点加入到和多项式中*/ pre-next=q; void print(node * p) /*输出函数，打印出一元多项式*/ while(p-next!=NULL) p=p-next;printf( %d*x%d,p-coef,p-exp); main() /*主函数*/ node * polya,* polyb; printf(Welcome to use!n); printf(nPlease input the ploya include coef & exp:n); polya=create(); /*调用建立链表函数，创建多项式A*/print(polya);printf(nPlease input the ployb include coef & exp:n); polyb=create(); /*同理，创建B*/ print(polyb);printf(nSum of the poly is:n); polyadd(polya,polyb); /*调用一元多项式相加函数*/print(polya); /*调用输出函数，打印结果*/ printf(n); 4 （课后思考）设计（选做）以程序形式实现A=AB的运算1) 可以以顺序存储来实现，也可以用链表实现2) 自己给定A、B的值实验四 查找实验目的：掌握各种查找方法的过程和算法，能对不同的情况采用不同的查找方法，分析各种方法的性能。实验课时：实验课时：2课时实验要求：1. 掌握各种查找算法及查找过程、实现的时间复杂度2. 能将各种查找算法以程序实现，并在程序中能看到查找的次数3. 写出对应程序（使用语言没有硬性规定，但推荐使用C）4. 调试成功，并保存程序源代码，以备检查实验内容：1. 已知一个有序序列，查找某个元素。1）序列的长短可预先设置2）对有序性进行判断3）完成该程序、递交实验报告2上机实现以下程序，了解哈希表的构成与解决冲突的实现。题目要求：假设人名为姓名的汉语拼音形式，待填入哈希表的人名工有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用伪随机探测再散列法处理冲突。测试数据自定义。 #include#include#define HASH_LEN 50/哈希表的长度#define M 47/随机数#define NAME_NO 30/人名的个数typedef structchar *py;/名字的拼音int k;/拼音所对应的整数NAME;NAME NameListHASH_LEN;/全局变量NAMEtypedef struct/哈希表char *py;/名字的拼音int k;/拼音所对应的整数int si;/查找长度HASH;HASH HashListHASH_LEN;/全局变量HASHvoid InitNameList() /姓名（结构体数组）初始化char *f;int r,s0,i;NameList0.py=wanghui;NameList1.py=mayuelong;NameList2.py=chenzhicheng;NameList3.py=sunpeng;NameList4.py=zengqinghui;NameList5.py=liqingbo;NameList6.py=liujunpeng;NameList7.py=jiangquanlei;NameList8.py=xingzhengchuan;NameList9.py=luzhaoqian;NameList10.py=gaowenhu;NameList11.py=zhuhaoyin;NameList12.py=chenlili;NameList13.py=wuyunyun;NameList14.py=huangjuanxia;NameList15.py=wangyan;NameList16.py=zhoutao;NameList17.py=jiangzhenyu;NameList18.py=liuxiaolong;NameList19.py=wangziming;NameList20.py=fengjunbo;NameList21.py=lilei;NameList22.py=wangjia;NameList23.py=zhangjianguo;NameList24.py=zhuqingqing;NameList25.py=huangmin;NameList26.py=haoyuhan;NameList27.py=zhoutao;NameList28.py=zhujiang;NameList29.py=lixiaojun;for (i=0;iNAME_NO;i+)s0=0;f=NameListi.py;for (r=0;*(f+r)!=0;r+)/* 方法：将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字*/s0=*(f+r)+s0;NameListi.k=s0; void CreateHashList() /建立哈希表int i;for (i=0; iHASH_LEN;i+) HashListi.py=;HashListi.k=0;HashListi.si=0;for (i=0;iHASH_LEN;i+)int sum=0;int adr=(NameListi.k)%M;/哈希函数int d=adr;if(HashListadr.si=0)/如果不冲突HashListadr.k=NameListi.k;HashListadr.py=NameListi.py;HashListadr.si=1;else/冲突dod=(d+NameListi.k%10+1)%M;/伪随机探测再散列法处理冲突sum=sum+1;/查找次数加1while (HashListd.k!=0);HashListd.k=NameListi.k;HashListd.py=NameListi.py;HashListd.si=sum+1;voidFindList() /查找char name20=0; int s0=0,r,sum=1,adr,d;printf(n请输入姓名的拼音:);scanf(%s,name); for (r=0;r20;r+)/求出姓名的拼音所对应的整数(关键字)s0+=namer; adr=s0%M;/使用哈希函数d=adr;if(HashListadr.k=s0)/分3种情况进行判断printf(n姓名:%s关键字:%d查找长度为: 1,HashListd.py,s0); else if (HashListadr.k=0) printf(无此记录!);elseint g=0;dod=(d+s0%10+1)%M;/伪随机探测再散列法处理冲突sum=sum+1;if (HashListd.k=0)printf(无此记录! );g=1;if (HashListd.k=s0)printf(n姓名:%s关键字:%d查找长度为:%d,HashListd.py,s0,sum); g=1;while(g=0); voidDisplay() / 显示哈希表int i;float average=0;printf(nn地址t关键字tt搜索长度tH(key)t 姓名n); /显示的格式for(i=0; i50; i+)printf(%d ,i); printf(t%d ,HashListi.k);printf(tt%d ,HashListi.si);printf(tt%d ,HashListi.k%M);printf(t %s ,HashListi.py);printf(n);for (i=0;iHASH_LEN;i+)average+=HashListi.si; average/=NAME_NO;printf(nn平均查找长度：ASL(%d)=%f nn,NAME_NO,average); void main()char ch1;printf(n哈希表的建