數(shù)據(jù)結(jié)構(gòu)課程設(shè)計實驗報告E10914060 劉晨晨

實驗一.線性表逆置：一.問題描述

分別以不同存儲結(jié)構(gòu)實現(xiàn)線性表的就地逆置。線性表的就地逆置就是在原表的存儲空間內(nèi)將線性表（a1,a2,a3,……an）〔an,an-1，……a2,a1）.二．基本要求用順序存儲結(jié)構(gòu)實現(xiàn)線性表的就地逆置，并將結(jié)果輸出。三.數(shù)據(jù)結(jié)構(gòu)的設(shè)計:

由于線性表在內(nèi)存中是線性存儲的,故設(shè)計其數(shù)據(jù)結(jié)構(gòu)類型如下:structwork{

chara:

structwork*next;}說明:由于本實驗重在算法的實現(xiàn),故將線性表設(shè)計的很簡單,以便于操作.四.函數(shù)說明：1.函數(shù)revers(structwork*head):功能說明:實現(xiàn)線性表在內(nèi)存中的逆置.算法設(shè)計:首先在函數(shù)中定義與線性表相同數(shù)據(jù)結(jié)構(gòu)的指針p,q,s.然后讓p和s都指向從形參獲取的線性表頭指針head,讓q作為p的后繼指針指向p->next,

此時就可以讓第一個節(jié)點分離出來，即讓s->next=NULL.接下來一個循環(huán)是真正實現(xiàn)線性表的逆置;最后讓參數(shù)head指向逆置后的表頭,然后做為返回值返回.2.函數(shù)print(structwork*head):功能說明:從屏幕依次輸出線性表的成員.算法設(shè)計:定義一個結(jié)構(gòu)體指針,并讓它賦值為從形參傳來的頭指針,即讓它指向線性表的頭節(jié)點;接下來一個循環(huán)是依次輸出線性表的成員,并讓p向后移位,即p=p->next,直至p為空指針,退出循環(huán).五.具體設(shè)計：

1.函數(shù)revers():代碼如下:structwork*revers(structwork*head){structwork*p,*q,*s;

/*定義指針變量,用于逆置轉(zhuǎn)換*/p=head;s=head;q=p->next;s->next=NULL;

/*先讓第一個節(jié)點斷開*/while(q){

p=q;

/*讓p后移*/

q=q->next;

/*p也后移*/

p->next=s;

/*s起中間作用*/

s=p;}head=p;

/*讓head當(dāng)頭指針*/returnhead;}2.print函數(shù):代碼如下:voidprint(structwork*head)

{

structwork*p;

/*定義結(jié)構(gòu)體指針*/

p=head;

/*讓p指向線性表的頭節(jié)點*/

while(p!=NULL)

/*循環(huán)開始*/

{

printf("%c",p->a);

p=p->next;

/*讓p后移*/

}

printf("\n");

}

3.main()函數(shù):

代碼如下:intmain(){structwork*run;

/*定義結(jié)構(gòu)體變量run用于執(zhí)行函數(shù)*/structwork*pointer1,*pointer2,*head;/*結(jié)構(gòu)體指針用于創(chuàng)建線性表*/pointer1=pointer2=(structwork*)malloc(length);/*以下為線性表的創(chuàng)建*/scanf("%c",&pointer1->a);head=NULL;while(pointer1->a!='0'){if(head==NULL)head=pointer1;elsepointer2->next=pointer1;pointer2=pointer1;pointer1=(structwork*)malloc(length);scanf("%c",&pointer1->a);}pointer2->next=NULL;

/*線性表創(chuàng)建結(jié)束*/printf("逆置前：\n");print(head);

/*屏幕輸出*/run=revers(head);

/*執(zhí)行逆置函數(shù)*/printf("逆置后：\n");print(run);

/*屏幕輸出*/return0;}程序如下：#include<stdio.h>#include<malloc.h>#definelengthsizeof(structwork)structwork{chara;structwork*next;};structwork*revers(structwork*head){structwork*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;returnhead;}voidprint(structwork*head)

{

structwork*p;

p=head;

while(p!=NULL)

{

printf("%c",p->a);

p=p->next;

}

printf("\n");

}intmain(){

structwork*run;

structwork*pointer1,*pointer2,*head;

pointer1=pointer2=(structwork*)malloc(length);

scanf("%c",&pointer1->a);

head=NULL;

while(pointer1->a!='0')

{

if(head==NULL)head=pointer1;

elsepointer2->next=pointer1;

pointer2=pointer1;

pointer1=(structwork*)malloc(length);

scanf("%c",&pointer1->a);

}

pointer2->next=NULL;printf("逆置前：\n");

print(head);run=revers(head);printf("逆置后：\n");print(run);return0;}運行如下：六.實驗總結(jié)：線性表逆置是看似比較簡單的實驗，然而卻需認(rèn)真思考細(xì)心操作，不然易出錯。實驗二.哈希表設(shè)計:問題描述：針對某個集體（比如你所在的班級）中的“人名”設(shè)計一個哈希表，使得平均查找長度不超過R，完成相應(yīng)的建表和查表程序。基本要求：假設(shè)人名為中國人姓名的漢語拼音形式。待填入哈希表的人名共有30個，取平均查找長度的上限位。哈希函數(shù)用除留余數(shù)法構(gòu)造，用線性探測再散列法處理沖突。三．程序如下：#include<stdio.h>

#include<conio.h>

#include<ctype.h>

#defineL50/*定義哈希表長*/

#defineM47/*定義p值*/

#defineN30/*定義名單長*/

charz[22];

structold{char*name;char*py;intk;};

structoldoldlist[L];/*原始表*/

structhterm

{char*name;char*py;

intk;intsi;

};

structhtermhlist[L];/*哈希表*/

inti,adr,sum,d;

charch1;

floataverage;

/**********************************/

voidchash()

{for(i=0;i<L;i++)

{hlist[i].name="";

hlist[i].py="";

hlist[i].k=0;

hlist[i].si=0;

};

for(i=0;i<N;i++)

{sum=0;

adr=(oldlist[i].k)%M;

d=adr;

if(hlist[adr].si==0)

{hlist[adr].k=oldlist[i].k;

hlist[adr].name=oldlist[i].name;

hlist[adr].py=oldlist[i].py;

hlist[adr].si=1;

}

else

{do

{d=(d+((oldlist[i].k))%10+1)%M;/*偽隨機(jī)*/

sum=sum+1;

}

while(hlist[d].k!=0);

hlist[d].k=oldlist[i].k;

hlist[d].name=oldlist[i].name;

hlist[d].py=oldlist[i].py;

hlist[d].si=sum+1;

}

}

}

/***************************************/

voidfindhlist()

{ints0;charr,g;

clrscr();/*清屏*/

for(r=0;r<20;r++){z[r]=0;};

gotoxy(1,1);printf("RESEARCH.....");

gotoxy(5,10);printf("inputthespellofname:");

gotoxy(5,12);scanf("%s",z);

s0=0;

for(r=0;r<20;r++){s0=z[r]+s0;};

gotoxy(5,13);printf("%d",s0);

/*for(i=0;i<L;i++)*/

sum=1;

adr=s0%M;

d=adr;

if(hlist[adr].k==s0)

{

gotoxy(18,18);printf("");

gotoxy(18,18);printf("%s",hlist[d].name);

gotoxy(18,19);printf("%s",hlist[d].py);

gotoxy(18,20);

printf("find%dtimes",sum);

getch();

}

else

{if(hlist[adr].k==0)

{gotoxy(18,18);

printf("nothingaboutit!");

getch();

}

else

{g=0;

for(i=0;g==0;i++)

{d=(d+s0%10+1)%M;/*偽隨機(jī)*/

sum=sum+1;

if(hlist[d].k==0)

{gotoxy(18,18);

printf("nothingaboutit!");

g=1;getch();

};

gotoxy(18,18);

printf("%s",hlist[d].name);

gotoxy(18,19);

printf("%s",hlist[d].py);

gotoxy(18,20);

printf("find%dtimes",sum);

getch();

if(hlist[d].k==s0)

{g=1;

gotoxy(18,21);

printf("find%dtimesuntilsuccess!",sum);

getch();

};

};

};

};

}

/***************************************/

voidinp()/*輸入表*/

{

char*f;

intr,s0;

oldlist[0].name="A";oldlist[0].py="apple";

oldlist[1].name="B";oldlist[1].py="bus";

oldlist[2].name="C";oldlist[2].py="cat";

oldlist[3].name="D";oldlist[3].py="dog";

oldlist[5].name="E";oldlist[5].py="egg";

oldlist[6].name="F";oldlist[6].py="fly";

oldlist[7].name="G";oldlist[7].py="good";

oldlist[8].name="H";oldlist[8].py="hurt";

oldlist[9].name="I";oldlist[9].py="int";

oldlist[10].name="J";oldlist[10].py="joy";

oldlist[11].name="K";oldlist[11].py="keep";

oldlist[12].name="L";oldlist[12].py="long";

oldlist[13].name="M";oldlist[13].py="make";

oldlist[14].name="N";oldlist[14].py="net";

oldlist[15].name="O";oldlist[15].py="out";

oldlist[16].name="P";oldlist[16].py="pour";

oldlist[17].name="Q";oldlist[17].py="queen";

oldlist[18].name="R";oldlist[18].py="run";

oldlist[19].name="S";oldlist[19].py="sun";

oldlist[20].name="T";oldlist[20].py="tea";

oldlist[21].name="U";oldlist[21].py="until";

oldlist[22].name="V";oldlist[22].py="vection";

oldlist[23].name="W";oldlist[23].py="water";

oldlist[24].name="X";oldlist[24].py="xray";

oldlist[25].name="Y";oldlist[25].py="you";

oldlist[26].name="Z";oldlist[26].py="zoo";

oldlist[27].name="AA";oldlist[27].py="aah";

oldlist[28].name="BB";oldlist[28].py="bbc";

oldlist[29].name="CC";oldlist[29].py="cch";

/*請在此輸入數(shù)據(jù),同時修改程序開頭的MLN*/

for(i=0;i<N;i++)

{

s0=0;

f=oldlist[i].py;

for(r=0;*(f+r)!='\0';r++){s0=*(f+r)+s0;};

oldlist[i].k=s0;

};

}

/****************************************/

voiddhash()/*顯示哈希表*/

{charLON=17;

clrscr();

if(LON>L){LON=L;};

gotoxy(1,1);printf("HashTable:");

gotoxy(1,2);printf("address:");

for(i=0;i<LON;i++)

{gotoxy(1,i+3);

printf("%-3d",i);

};

gotoxy(9,2);printf("theH(key)is:");

for(i=0;i<LON;i++)

{gotoxy(10,i+3);

printf("%-6d",hlist[i].k);

};

gotoxy(19,2);printf("name:");

for(i=0;i<LON;i++)

{gotoxy(19,3+i);

printf("%s",hlist[i].name);

};

gotoxy(28,2);printf("spell:");

for(i=0;i<LON;i++)

{gotoxy(28,i+3);

printf("%s",hlist[i].py);

};

gotoxy(40,2);printf("thelength:");

for(i=0;i<LON;i++)

{gotoxy(43,i+3);

printf("%2d",hlist[i].si);

};

gotoxy(53,2);printf("H(key):");

for(i=0;i<LON;i++)

{gotoxy(53,i+3);

printf("%2d",(hlist[i].k)%M);

};

average=0;

for(i=0;i<L;i++)

{average=average+hlist[i].si;};

average=average/N;

gotoxy(10,23);

printf("ASL:ASL(%d)=%f",N,average);

gotoxy(20,24);

printf("anykeytopass");

ch1=getch();

if(L>15)

{

clrscr();

if(LON>L-15){LON=L-15;};

gotoxy(1,1);printf("HashTable:");

gotoxy(1,2);printf("address:");

for(i=0;i<LON;i++)

{gotoxy(1,i+3);

printf("%-3d",i+15);

};

gotoxy(9,2);printf("theH(key)is:");

for(i=0;i<LON;i++)

{gotoxy(10,i+3);

printf("%-6d",hlist[i+15].k);

};

gotoxy(19,2);printf("name:");

for(i=0;i<LON;i++)

{gotoxy(19,3+i);

printf("%s",hlist[i+15].name);

};

gotoxy(28,2);printf("spell:");

for(i=0;i<LON;i++)

{gotoxy(28,i+3);

printf("%s",hlist[i+15].py);

};

gotoxy(40,2);printf("thelength:");

for(i=0;i<LON;i++)

{gotoxy(43,i+3);

printf("%2d",hlist[i+15].si);

};

gotoxy(53,2);printf("H(key):");

for(i=0;i<LON;i++)

{gotoxy(53,i+3);

printf("%2d",(hlist[i+15].k)%M);

};

average=0;

for(i=0;i<L;i++)

{average=average+hlist[i].si;};

average=average/N;

gotoxy(10,23);

printf("ASL:ASL(%d)=%f",N,average);

gotoxy(20,24);

printf("anykeytopass");

ch1=getch();

};

if(L>30)

{

clrscr();

if(LON>L-30){LON=L-30;};

gotoxy(1,1);printf("HashTable:");

gotoxy(1,2);printf("address:");

for(i=0;i<LON;i++)

{gotoxy(1,i+3);

printf("%-3d",i+30);

};

gotoxy(9,2);printf("theH(key)is:");

for(i=0;i<LON;i++)

{gotoxy(10,i+3);

printf("%-6d",hlist[i+30].k);

};

gotoxy(19,2);printf("name:");

for(i=0;i<LON;i++)

{gotoxy(19,3+i);

printf("%s",hlist[i+30].name);

};

gotoxy(28,2);printf("spell:");

for(i=0;i<LON;i++)

{gotoxy(28,i+3);

printf("%s",hlist[i+30].py);

};

gotoxy(40,2);printf("thelength:");

for(i=0;i<LON;i++)

{gotoxy(43,i+3);

printf("%2d",hlist[i+30].si);

};

gotoxy(53,2);printf("H(key):");

for(i=0;i<LON;i++)

{gotoxy(53,i+3);

printf("%2d",(hlist[i+30].k)%M);

};

average=0;

for(i=0;i<L;i++)

{average=average+hlist[i].si;};

average=average/N;

gotoxy(10,23);

printf("ASL:ASL(%d)=%f",N,average);

gotoxy(20,24);

printf("anykeytopass");

ch1=getch();

};

if(L>45)

{

clrscr();

if(LON>L-45){LON=L-45;};

gotoxy(1,1);printf("HashTable:");

gotoxy(1,2);printf("address:");

for(i=0;i<LON;i++)

{gotoxy(1,i+3);

printf("%-3d",i+45);

};

gotoxy(9,2);printf("theH(key)is:");

for(i=0;i<LON;i++)

{gotoxy(10,i+3);

printf("%-6d",hlist[i+45].k);

};

gotoxy(19,2);printf("name:");

for(i=0;i<LON;i++)

{gotoxy(19,3+i);

printf("%s",hlist[i+45].name);

};

gotoxy(28,2);printf("spell:");

for(i=0;i<LON;i++)

{gotoxy(28,i+3);

printf("%s",hlist[i+45].py);

};

gotoxy(40,2);printf("thelength:");

for(i=0;i<LON;i++)

{gotoxy(43,i+3);

printf("%2d",hlist[i+45].