1、数据结构课程设计实验报告E10914060 刘晨晨实验一.线性表逆置：一.问题描述分别以不同存储结构实现线性表的就地逆置。线性表的就地逆置就是在原表的存储空间内将线性表（a1,a2,a3,an）an,an-1，a2,a1）.二基本要求用顺序存储结构实现线性表的就地逆置，并将结果输出。三.数据结构的设计: 由于线性表在内存中是线性存储的,故设计其数据结构类型如下:struct work char a: struct work *next;说明:由于本实验重在算法的实现,故将线性表设计的很简单,以便于操作.四. 函数说明：1.函数revers(struct work *head):功能说明:实现线
2、性表在内存中的逆置.算法设计:首先在函数中定义与线性表相同数据结构的指针p,q,s.然后让p和s都指向从形参获取的线性表头指针head,让q作为p的后继指针指向p-next, 此时就可以让第一个节点分离出来，即让s-next=NULL.接下来一个循环是真正实现线性表的逆置;最后让参数head指向逆置后的表头,然后做为返回值返回.2.函数print(struct work *head):功能说明:从屏幕依次输出线性表的成员.算法设计:定义一个结构体指针,并让它赋值为从形参传来的头指针,即让它指向线性表的头节点;接下来一个循环是依次输出线性表的成员,并让p向后移位,即p=p-next,直至p为空指
3、针,退出循环.五.具体设计： 1.函数revers():代码如下:struct work *revers(struct work *head)struct work *p,*q,*s; /*定义指针变量,用于逆置转换*/p=head;s=head;q=p-next;s-next=NULL; /*先让第一个节点断开*/while(q) p=q; /*让p后移*/ q=q-next; /*p也后移*/ p-next=s; /*s起中间作用*/ s=p;head=p; /*让head当头指针*/return head;2.print函数:代码如下:void print(struct work *he
4、ad) struct work *p; /*定义结构体指针*/ p=head; /*让p指向线性表的头节点*/ while(p!=NULL) /*循环开始*/ printf(%c,p-a); p=p-next; /*让p后移*/ printf(n); 3.main()函数: 代码如下:int main() struct work *run; /*定义结构体变量run用于执行函数*/struct work *pointer1,*pointer2,*head; /*结构体指针用于创建线性表*/pointer1=pointer2=(struct work *)malloc(length); /*以下
5、为线性表的创建*/scanf(%c,&pointer1-a);head=NULL;while(pointer1-a!=0)if(head=NULL) head=pointer1;else pointer2-next=pointer1;pointer2=pointer1;pointer1=(struct work *)malloc(length);scanf(%c,&pointer1-a);pointer2-next=NULL; /*线性表创建结束*/printf(逆置前：n);print(head); /*屏幕输出*/run=revers(head); /*执行逆置函数*/printf(逆置后
6、：n);print(run); /*屏幕输出*/return 0;程序如下：#include#include#define length sizeof(struct work)struct work char a;struct work *next;struct work *revers(struct work *head)struct work *p,*q,*s;p=head;s=head;q=p-next;s-next=NULL;while(q) p=q; q=q-next; p-next=s; s=p;head=p;return head;void print(struct work *
7、head) struct work *p; p=head; while(p!=NULL) printf(%c,p-a); p=p-next; printf(n); int main() struct work *run; struct work *pointer1,*pointer2,*head; pointer1=pointer2=(struct work *)malloc(length); scanf(%c,&pointer1-a); head=NULL; while(pointer1-a!=0) if(head=NULL) head=pointer1; else pointer2-nex
8、t=pointer1; pointer2=pointer1; pointer1=(struct work *)malloc(length); scanf(%c,&pointer1-a); pointer2-next=NULL;printf(逆置前：n); print(head);run=revers(head);printf(逆置后：n);print(run);return 0; 运行如下：六.实验总结：线性表逆置是看似比较简单的实验，然而却需认真思考细心操作，不然易出错。实验二.哈希表设计:一. 问题描述：针对某个集体（比如你所在的班级）中的“人名”设计一个哈希表，使得平均查找长度不超过R，
9、完成相应的建表和查表程序。 二. 基本要求：假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限位。哈希函数用除留余数法构造，用线性探测再散列法处理冲突。三程序如下：#include #include #include #define L 50 /*定义哈希表长*/ #define M 47 /*定义p值*/ #define N 30 /*定义名单长*/ char z22; struct oldchar *name;char *py;int k; struct old oldlistL;/*原始表*/ struct hterm char *name;char
10、*py; int k;int si; ; struct hterm hlistL;/*哈希表*/ int i,adr,sum,d; char ch1; float average; /*/ void chash() for (i=0;iL;i+) hlisti.name=; hlisti.py=; hlisti.k=0; hlisti.si=0; ; for (i=0;iN;i+) sum=0; adr=(oldlisti.k)%M; d=adr; if(hlistadr.si=0) hlistadr.k=oldlisti.k; hlistadr.name=oldlisti.name; hli
11、stadr.py=oldlisti.py; hlistadr.si=1; else do d=(d+(oldlisti.k)%10+1)%M;/*伪随机*/ sum=sum+1; while (hlistd.k!=0); hlistd.k=oldlisti.k; hlistd.name=oldlisti.name; hlistd.py=oldlisti.py; hlistd.si=sum+1; /*/ void findhlist() int s0;char r,g; clrscr();/*清屏*/ for (r=0;r20;r+)zr=0; gotoxy(1,1);printf(RESEAR
12、CH.); gotoxy(5,10);printf(input the spell of name: ); gotoxy(5,12);scanf(%s,z); s0=0; for (r=0;r20;r+)s0=zr+s0; gotoxy(5,13); printf(%d,s0); /*for (i=0;iL;i+)*/ sum=1; adr=s0%M; d=adr; if(hlistadr.k=s0) gotoxy(18,18);printf( ); gotoxy(18,18);printf( %s,hlistd.name); gotoxy(18,19);printf( %s,hlistd.p
13、y); gotoxy(18,20); printf( find %d times,sum); getch(); else if (hlistadr.k=0) gotoxy (18,18); printf(nothing about it!); getch(); else g=0; for (i=0;g=0;i+) d=(d+s0%10+1)%M; /*伪随机*/ sum=sum+1; if (hlistd.k=0) gotoxy (18,18); printf(nothing about it!); g=1;getch(); ; gotoxy(18,18); printf(%s,hlistd.
14、name); gotoxy(18,19); printf(%s,hlistd.py); gotoxy(18,20); printf(find %d times,sum); getch(); if (hlistd.k=s0) g=1; gotoxy(18,21); printf(find %d times until success!,sum); getch(); ; ; ; ; /*/ void inp() /*输入表*/ char *f; int r,s0; oldlist0.name=A;oldlist0.py=apple; oldlist1.name=B;oldlist1.py=bus;
15、 oldlist2.name=C;oldlist2.py=cat; oldlist3.name=D;oldlist3.py=dog; oldlist5.name=E;oldlist5.py=egg; oldlist6.name=F;oldlist6.py=fly; oldlist7.name=G;oldlist7.py=good; oldlist8.name=H;oldlist8.py=hurt; oldlist9.name=I;oldlist9.py=int; oldlist10.name=J;oldlist10.py=joy; oldlist11.name=K;oldlist11.py=k
16、eep; oldlist12.name=L;oldlist12.py=long; oldlist13.name=M;oldlist13.py=make; oldlist14.name=N;oldlist14.py=net; oldlist15.name=O;oldlist15.py=out; oldlist16.name=P;oldlist16.py=pour; oldlist17.name=Q;oldlist17.py=queen; oldlist18.name=R;oldlist18.py=run; oldlist19.name=S;oldlist19.py=sun; oldlist20.
17、name=T;oldlist20.py=tea; oldlist21.name=U;oldlist21.py=until; oldlist22.name=V;oldlist22.py=vection; oldlist23.name=W;oldlist23.py=water; oldlist24.name=X;oldlist24.py=xray; oldlist25.name=Y;oldlist25.py=you; oldlist26.name=Z;oldlist26.py=zoo; oldlist27.name=AA;oldlist27.py=aah; oldlist28.name=BB;ol
18、dlist28.py=bbc; oldlist29.name=CC;oldlist29.py=cch; /*请在此输入数据,同时修改程序开头的 M L N*/ for (i=0;iL)LON=L; gotoxy(1,1);printf(HashTable: ); gotoxy(1,2);printf(address: ); for(i=0;iLON;i+) gotoxy(1,i+3); printf(%-3d,i); ; gotoxy(9,2);printf(the H(key) is: ); for(i=0;iLON;i+) gotoxy(10,i+3); printf(%-6d,hlist
19、i.k); ; gotoxy(19,2);printf(name: ); for(i=0;iLON;i+) gotoxy(19,3+i); printf(%s,hlisti.name); ; gotoxy(28,2);printf(spell: ); for(i=0;iLON;i+) gotoxy(28,i+3); printf(%s,hlisti.py); ; gotoxy(40,2);printf(the length: ); for(i=0;iLON;i+) gotoxy(43,i+3); printf(%2d,hlisti.si); ; gotoxy(53,2);printf(H(ke
20、y): ); for(i=0;iLON;i+) gotoxy(53,i+3); printf(%2d,(hlisti.k)%M); ; average=0; for (i=0;i15) clrscr(); if (LONL-15)LON=L-15; gotoxy(1,1);printf(HashTable: ); gotoxy(1,2);printf(address: ); for(i=0;iLON;i+) gotoxy(1,i+3); printf(%-3d,i+15); ; gotoxy(9,2);printf(the H(key) is: ); for(i=0;iLON;i+) goto
21、xy(10,i+3); printf(%-6d,hlisti+15.k); ; gotoxy(19,2);printf(name: ); for(i=0;iLON;i+) gotoxy(19,3+i); printf(%s,hlisti+15.name); ; gotoxy(28,2);printf(spell: ); for(i=0;iLON;i+) gotoxy(28,i+3); printf(%s,hlisti+15.py); ; gotoxy(40,2);printf(the length: ); for(i=0;iLON;i+) gotoxy(43,i+3); printf(%2d,
22、hlisti+15.si); ; gotoxy(53,2);printf(H(key):); for(i=0;iLON;i+) gotoxy(53,i+3); printf(%2d,(hlisti+15.k)%M); ; average=0; for (i=0;i30) clrscr(); if (LONL-30)LON=L-30; gotoxy(1,1);printf(HashTable: ); gotoxy(1,2);printf(address: ); for(i=0;iLON;i+) gotoxy(1,i+3); printf(%-3d,i+30); ; gotoxy(9,2);pri
23、ntf(the H(key) is: ); for(i=0;iLON;i+) gotoxy(10,i+3); printf(%-6d,hlisti+30.k); ; gotoxy(19,2);printf(name: ); for(i=0;iLON;i+) gotoxy(19,3+i); printf(%s,hlisti+30.name); ; gotoxy(28,2);printf(spell: ); for(i=0;iLON;i+) gotoxy(28,i+3); printf(%s,hlisti+30.py); ; gotoxy(40,2);printf(the length: ); f
24、or(i=0;iLON;i+) gotoxy(43,i+3); printf(%2d,hlisti+30.si); ; gotoxy(53,2);printf(H(key):); for(i=0;iLON;i+) gotoxy(53,i+3); printf(%2d,(hlisti+30.k)%M); ; average=0; for (i=0;iL;i+) average=average+hlisti.si; average=average/N; gotoxy(10,23); printf(ASL:ASL(%d)=%f,N,average); gotoxy(20,24); printf(any key to pass ); ch1=getch(); ; i
