算法與數(shù)據(jù)結(jié)構(gòu)實驗報告25323

1、201 5- 201 6學(xué)年第二學(xué)期算法與數(shù)據(jù)結(jié)構(gòu)課程實驗報告專業(yè)軟件工程學(xué)生姓名成曉偉班級軟件141學(xué)號1410075094實驗學(xué)時16實驗教師徐秀芳信息工程學(xué)院實驗一單鏈表的基本操作一、實驗?zāi)康?. 熟悉C語言上機環(huán)境，進(jìn)一步掌握 C語言的基本結(jié)構(gòu)及特點。2. 掌握線性表的各種物理存儲表示和 C語言實現(xiàn)。3. 掌握單鏈表的各種主要操作的 C語言實現(xiàn)。4. 通過實驗理解線性表中的單鏈表存儲表示與實現(xiàn)。二、主要儀器及耗材普通計算機三、實驗內(nèi)容與要求1、用C語言編寫一個單鏈表基本操作測試程序。（1）初始化單鏈表（2）創(chuàng)建單鏈表（3）求單鏈表長度（4）輸出單鏈表中每一個結(jié)點元素（5）指定位置插入某

2、個元素（6）查找第i個結(jié)點元素的值（7）查找值為e的結(jié)點，并返回該結(jié)點指針（8）刪除第i個結(jié)點（9）銷毀單鏈表2、實驗要求（1）程序中用戶可以選擇上述基本操作。程序啟動后，在屏幕上可以菜單形式顯示不同功能，當(dāng)按下不同數(shù)字后完成指定的功能，按其他鍵，則顯示錯誤后重新選擇。（2） 要求用線性表的順序存儲結(jié)構(gòu)，帶頭結(jié)點的單鏈表存儲結(jié)構(gòu)分別實現(xiàn)。（3）主函數(shù)實現(xiàn)對基本操作功能的調(diào)用。3、主要代碼（1）初始化單鏈表LinkList *lnitList（） /創(chuàng)建一個空鏈表,初始化線性表Lin kList *L;L=（Li nkList *）malloc（sizeof（L in kList）;L->

3、 next=NULL;return L;(2) 創(chuàng)建單鏈表/頭插法void CreateListF(Li nkList *L)Lin kList *s;int i=1,a=0;while(1)printf("輸入第d個元素(0表示終止)",i+);scan f("%d",&a);if(a=0)break;s=(L in kList *)malloc(sizeof(Li nkList); s->data=a;s->n ext=L->n ext;L->n ext=s;(3) 求鏈表長度int ListLe ngth(L in

4、kList *L) /求鏈表長度int n=0;Lin kList *p=L;while(p-> next!=NULL)p=p->n ext;n+;return( n);(4) 在指定位置插入元素int In sertList(L in kList *L,i nt i,ElemType e)Li nkList *p=L,*s;int j=0;while(p!=NULL&&j<i-1)p=p->n ext;j+;/找出要插入的位置的前一個位置if(p=NULL)return 0;elses=(L in kList *)malloc(sizeof(Li nk

5、List); s->data=e;s->n ext=p->n ext;p->n ext=s; return 1;(5) 輸出鏈表void DispList(Li nkList *L) /輸出鏈表Lin kList *p=L->n ext;while(p!=NULL) prin tf("%d",p->data);p=p->n ext;prin tf("n");(6) 查找鏈表中指定元素int GetElem(Li nkList *L,i nt i) /查找鏈表中指定元素Lin kList *p=L;int j=0;

6、while(j<i&&p!=NULL)j+；p=p->n ext; if(p=NULL) return 0;elsereturn p->data;(7) 查找值是e的結(jié)點并返回該指針Lin kList *LocateElem(Li nkList *L,ElemType e)/查找值是e的結(jié)點并返回該指針int i=1;Lin kList *p=L;while(p!=NULL)if(p->data=e) return p;if(p=NULL) return NULL;刪除元素(8) 刪除元素int ListDelete(LinkList *L,int i,

7、ElemType *e) /Lin kList *p=L,*q;int j=0;while(p!=NULL&&j<i-1) p=p->n ext;j+； /找到要刪除元素地址的前一個地址if(p=NULL) return 0; / 不能刪除elseq=p->n ext;*e=q->data;p->n ext=q->n ext; free(q); / 刪除成功 return 1;(9) 銷毀鏈表void DestroyList(Li nkList *L)銷毀鏈表Lin kList *pre=L,*p=L->n ext; while(p!=

8、NULL)free(pre);pre=p; p=pre->n ext;free(pre);ma in函數(shù)：int mai n()Lin kList *L;ElemType e;int i;L=I ni tList();CreateListF(L);DispList(L);printf("輸入要查找的元素位置:n");sca nf("%d",&i);e=GetElem(L,i);prin tf("%dn",e);printf("單鏈表長度為:%dn",ListLength(L);printf("

9、;輸入要刪除元素的位置:");sca nf("%d",&i);if (i>ListLe ngth(L)printf("超出范圍重新輸入");scan f("%d",&i);if(ListDelete(L,i,&e)=0) printf("未找到元素n");else DispList(L);printf("輸入插入元素的位置和值：");sca nf("%d%d",&i,&e);In sertList(L,i,e);Disp

10、List(L);return 0;4、測試數(shù)據(jù)及測試結(jié)果輸入：23 56 12 28 45輸出：' H :謹(jǐn)矚結(jié)構(gòu)嘗埶雲(yún)一；久實輕d。n li目n bia<?Pe b i-285-12 4 0 止止止止止止 示-巫不示示示-_M _M- -M-0 遠(yuǎn)匹兀元元兀 第鰲蠶 入入入入入廣黯黔拿的位置8125623俞入插入元素的位置和値M&&2S125B23ress anu Iceu to cont inue四、注意事項1、存儲結(jié)構(gòu)定義和基本操作盡可能用頭文件實現(xiàn)。2、采用縮進(jìn)格式，加足夠多的注釋。3、注意循環(huán)條件、邊界條件等。4、善于發(fā)現(xiàn)問題、分析問題、解決問題，并總結(jié)

11、思考。5、對于算法描述及實現(xiàn)完全理解。五、拓展提高1、若L為帶頭結(jié)點的單鏈表，刪除最大值結(jié)點2、將兩個單鏈表合并為一個單鏈表實驗二循環(huán)鏈表的基本操作一、實驗?zāi)康氖炀氄莆站€性表的基本操作在鏈?zhǔn)窖h(huán)存儲結(jié)構(gòu)上的實現(xiàn)。二、主要儀器及耗材普通計算機三、實驗內(nèi)容1、在上一次單鏈表基本操作的基礎(chǔ)上，修改程序，將其改為單循環(huán)鏈表，并實 現(xiàn)相關(guān)操作。（1）初始化單循環(huán)鏈表（2）創(chuàng)建單循環(huán)鏈表（3）求單循環(huán)鏈表長度（4）輸出單循環(huán)鏈表中每一個結(jié)點元素（5）指定位置插入某個元素（6）查找第i個結(jié)點元素的值（7）查找值為e的結(jié)點，并返回該結(jié)點指針（8）刪除第i個結(jié)點（9）銷毀單循環(huán)鏈表2、實驗要求（1）程序中用戶可

12、以選擇上述基本操作。程序啟動后，在屏幕上可以菜單形式顯示不同功能，當(dāng)按下不同數(shù)字后完成指定的功能，按其他鍵，則顯示錯誤后重新選擇。（2）要求用不帶頭結(jié)點的循環(huán)鏈表實現(xiàn)。（3）具體功能測試由主函數(shù)實現(xiàn)。3、主要代碼（1）初始化單循環(huán)鏈表void in itLi nkList（L in kList L）初始化循環(huán)單鏈表L=（L in kList）malloc（sizeof（LNode）;L-> next=L;創(chuàng)建一個空表（2）創(chuàng)建單循環(huán)鏈表Lin kList creat（Li nkList L）/給循環(huán)鏈表賦值Lin kList p,q,r;int N,i=O;/prin tf("

13、請輸入第4 個值:",+i); while(1)printf(" 請輸入第c個值：",+i); scan f("%d",&N); 輸入節(jié)點的值 if(N=O)/ 以0為結(jié)尾break;if(i=1)/當(dāng)只有一個節(jié)點時給p節(jié)點分配內(nèi)存空間p=(Li nkList)malloc(sizeof(LNode); p->date =N;p-> next =NULL;q=p;else/當(dāng)節(jié)點不為1時r=(L in kList)malloc(sizeof(LNode); r->date =N;r->next =NULL;q-&

14、gt;n ext =r; q=r;/if(q!=NULL)q-> next =p;/將尾節(jié)點指向頭節(jié)點完成循環(huán)L=p;return L;/ 返回頭指針(3) 打印循環(huán)鏈表void prin t(Li nkList L)/打印循環(huán)鏈表Lin kList p;/prin tf("*n");P=L；/prin tf("*n ”);if(p=NULL)當(dāng)鏈表尾空表時printf("這是一個空表n");while(p->next!=L)只有當(dāng)p節(jié)點不為尾節(jié)點是打印節(jié)點中的數(shù)據(jù)域/prin tf("*n");prin tf(

15、"%d ",p->date);p=p->n ext ;prin tf("%dn",p->date );/打印尾節(jié)點中的數(shù)據(jù)(4) 求鏈表的長度int len gth(L in kList L)/ 求鏈表的長度Lin kList p;/prin tf("*n");int n=1;/prin tf("*n");p=L;/prin tf("*n");while(p->next!=L)當(dāng)p節(jié)點不為尾節(jié)點時計數(shù)n+;/prin tf("*n");p=p->

16、n ext;return n;/返回鏈表長度/prin tf("%d*n", n);(5) 刪除指定位置的節(jié)點Lin kList del(L in kList L,i nt flag)/刪除指定位置的節(jié)點Lin kList p,q;int i;p=L;q=L->n ext ;int i=1;if(flag=1) 當(dāng)刪除節(jié)點為頭結(jié)點時while(q->next !=L)讓 p節(jié)點為尾節(jié)點q=q->n ext ;L=p->next ;/頭結(jié)點為 L->NEXT節(jié)點q-> next =L;/讓尾節(jié)點指向新的頭結(jié)點free(p);/ 釋放 pel

17、sefor(i=1;i<flag-1;i+)讓p和q節(jié)點到達(dá)指定位置p=p->n ext ;q=q->n ext ;p->n ext =q->n ext ;free(q);/ 刪除q節(jié)點return L;/ 返回頭指針(6) 查找第i個結(jié)點元素的值int search1(Li nkList L,i nt flag)/按照節(jié)點的位置返回節(jié)點中的數(shù)據(jù)Lin kList p;int i;p=L;for(i=1;i<flag;i+)/循環(huán)找到節(jié)點的位置p=p->n ext;return p->date;/ 返回節(jié)點的數(shù)據(jù)(7) 查找值為e的結(jié)點，并返回該

18、結(jié)點指針int search2(Li nkList L,i nt data)/按照數(shù)據(jù)來查找節(jié)點的位置Lin kList p;int i=1;P=L;while(1)if(p->date=data)當(dāng)查找到數(shù)據(jù)域與查找的數(shù)據(jù)相同是跳出循環(huán)break;elsei+；p=p->n ext;return i;(8) 刪除第i個結(jié)點Lin kList in sert(L in kList L,i nt falg,i nt data)/指定位置插入元素Lin kList p,s;int i;p=L;s=(Li nkList)malloc(sizeof(LNode);for(i=1;i<

19、falg;i+)尋找位置p=p->n ext;s->date=data; 將 data 賦值給 s 節(jié)點s->n ext=p->n ext;p->n ext=s;return L;(9) 銷毀單循環(huán)鏈表Lin kList destroy(Li nkList L)/銷毀循環(huán)鏈表Lin kList p,q; p=L->n ext ; while(p!=L) q=p->n ext ; free(p); p=q； free(L); L=NULL; return L; ma in函數(shù): int main()Lin kList L=NULL;int m,k,Cas

20、e,Le ngth,DAT1,flag,P,e;prin tf("*1.創(chuàng)建一個循環(huán)鏈表*n");prin tf("*2.打印所創(chuàng)建的循環(huán)鏈表*n");prin tf("*3.插入節(jié)點*n");prin tf("*4.刪除節(jié)點*n");prin tf("*5.求循環(huán)的長度*n");prin tf("*6.查找第i節(jié)點*n");prin tf("*7.查找某個值得節(jié)點*n");prin tf("*8.銷毀鏈表*n");prin tf(&q

21、uot;*9.刪除最大節(jié)點*n");prin tf("*10.退出程序*n");for(;)printf("請輸入操作的序號n");sca nf("%d",&Case);switch(Case)case 1: in itL in kList(L);L=creat(L); break; case 2: prin t(L);break;case 3: printf("請輸入需要插入的位置(之后)及其數(shù)據(jù)n");sea nf("%d%d",&m,&k);L=i nse

22、rt(L,m,k);prin t(L);break;case 4: printf("請輸入需要刪除的節(jié)點n");sca nf("%d",&Case);L=del(L,Case);prin t(L);/prin tf("%d",Le ngth);break;case 5: Len gth=le ngth(L);printf("循環(huán)的長度是 %dn",Length);break;case 6: printf("請輸入需要查找的節(jié)點序號：")；sca nf("%d", &a

23、mp;flag);DAT 仁 search1(L,flag);printf("所查找的節(jié)點數(shù)據(jù)為%dn",DAT1);break;case 7: printf("輸入需要查找的值n");sca nf("%d",&e);P=search2(L,e);printf("所查找的位置是%dn",P);break;case 8: L=destroy(L);prin t(L); break;/case 10:case 9: exit(0);break;return 0;4、測試數(shù)據(jù)及測試結(jié)果輸入：1 2 3 4 5輸出

24、：四、注意事項1、存儲結(jié)構(gòu)定義和基本操作盡可能用頭文件實現(xiàn)2、采用縮進(jìn)格式，加足夠多的注釋。3、注意循環(huán)條件、邊界條件等。五、拓展提高1、雙向鏈表中間結(jié)點P后插入新結(jié)點S的算法;2、刪除雙向鏈表中間結(jié)點P后的結(jié)點Q的算法;實驗三棧的基本操作及應(yīng)用一、實驗?zāi)康?掌握棧的順序表示和基本操作實現(xiàn)；2熟練掌握棧的基本操作；3、會用棧解決一些實際應(yīng)用；4、掌握十進(jìn)制數(shù)轉(zhuǎn)化為N進(jìn)制整數(shù)的工作原理。二、主要儀器及耗材普通計算機三、實驗內(nèi)容1、棧的基本運算(1) InitStack(SqStack *s) /初始化棧(2) Push(SqStack *s, SEIemType e)入棧操作(3) pop(Sq

25、Stack *s, SElemType e)出棧操作(4) GetTop(SqStack *s, SElemType e)取棧頂元素(5) lsEmpty(SqStack *s) /判斷是否為空(6) GetLength(SqStack *s) /求棧的長度2、 創(chuàng)建一個長度為100的順序棧T,每個數(shù)據(jù)元素的類型為字符型 char。 編寫代碼，利用棧的基本運算和順序棧T，正序輸入并存儲26個英文字母A乙然后逆序輸出。3、利用棧的基本運算，寫出十進(jìn)制轉(zhuǎn)化為二進(jìn)制(八進(jìn)制呢？十六進(jìn)制呢？ N進(jìn)制呢？)的具體實現(xiàn)，并輸出。4、實驗要求(1) 程序中用戶可以選擇上述基本操作。程序啟動后，在屏幕上可以菜

26、單形式顯示不同功能，當(dāng)按下不同數(shù)字后完成指定的功能，按其他鍵，則顯示錯誤后重新選擇。(2) 要求用不帶頭結(jié)點的循環(huán)鏈表實現(xiàn)。(3) 具體功能測試由主函數(shù)實現(xiàn)。5、主要代碼(1) 初始化棧void InitStack(sqStack *s)初始化棧，構(gòu)造一個空棧 s->base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType);動態(tài)分配存儲空間if(!s->base)exit(O);/ 存儲分配失敗s->top=s->base; ?？諛?biāo)記 s->stacksize=STACK_INIT_SIZE;(2) 取棧頂元素

27、int GetTop(sqStack *s, ElemType e) 取棧頂元素*(s->top)=e;return e;(3) 元素入棧void push(sqStack *s,ElemType e)元素入棧if(s->top-s->base>=s->stacksize)s->base=(ElemType*)realloc(s->base,(s->stacksize+STACK_INIT_SIZE)*siz eof(ElemType);/棧滿,追加存儲空間if(!s->base)exit(0);*(s->top)=e;/輸入元素 e

28、s->top+;/ 棧頂指針 +(4) 元素出棧void pop(sqStack *s,ElemType *e)/ 出棧if(s->top=s->base)retur n; *e=*-(s->top);(5) 求棧的長度int stackle n( sqStack s)/棧的長度retur n( s.top-s.base);(6) 判斷是否?？読nt stackempty(sqStack *s)/判斷是否?？読f(s->top=s->base)return 1;elsereturn 0;(7) 十進(jìn)制轉(zhuǎn)化為八進(jìn)制void conv ersio n() /十進(jìn)

29、制轉(zhuǎn)化為八進(jìn)制sqStack s;int n,t;ElemType e;In itStack(& s);printf("請輸入正整數(shù):");scan f("%d",&n);t=n;while( n)push(&s, n%8);n=n/8;printf(" 十進(jìn)制瞅化為八進(jìn)制為:",t);while(!stackempty(&s)pop(&s,&e);prin tf("%d",e);prin tf("n");(8) 二進(jìn)制轉(zhuǎn)化為十進(jìn)制void Bi

30、ntoDec()二進(jìn)制轉(zhuǎn)化為十進(jìn)制ElemType ch;sqStack s;in t le n,i,sum=0;In itStack(& s);printf("請輸入二進(jìn)制數(shù)，輸入#表示結(jié)束！ n");scan f("%c",&ch);while(ch!=#)push(&s,ch);sca nf("%c",&ch);getchar(); /清除緩沖區(qū)len=stackle n( s);printf("棧的當(dāng)前容量是：dn",len);for(i=0;i<le n;i+)pop

31、(&s,&ch); sum=sum+(ch-48)*pow(2,i);printf("轉(zhuǎn)化為十進(jìn)制數(shù)是%dn",sum);(9) 26個字母逆序輸出void AZZA()/字母逆序輸出ElemType ch26,e;sqStack s;in t le n,i;for(i=0;i<26;i+) chi='A'+i;In itStack(& s);for(i=0;i<26;i+)push(&s,chi);len=stackle n( s);printf("棧的當(dāng)前容量是：dn",len);while

32、(!stackempty(&s)pop(&s,&e);prin tf("%c",e);prin tf("n");main函數(shù) int main() AZZA(); prin tf("n");Bi ntoDec(); prin tf("n");conv ersi on(); return 0;6測試數(shù)據(jù)及測試結(jié)果輸入：1034輸出： 71 TH;遲嵋結(jié)構(gòu)。凸四棧七曲棧的當(dāng)前容量是;“YXUUUTSHQPONNLKJIHGFEDCBA幘輸入二進(jìn)制數(shù)，輸入表示結(jié)朿!轉(zhuǎn)切驢器漱進(jìn)制為=42Press

33、 any key to continue四、注意事項1、存儲結(jié)構(gòu)定義和基本操作盡可能用頭文件實現(xiàn)。2、注意?？蘸蜅M的條件判斷。3、進(jìn)制轉(zhuǎn)換時余數(shù)的存儲及輸出。五、拓展提高*1、輸入一個包含（和）的字符串，檢測括號是否匹配（其中括號 中能嵌套括號），并輸出括號是否匹配的信息（匹配，缺少左括號，缺少右括號）*2、輸入一個整數(shù)表達(dá)式，計算出其值，然后輸出。（學(xué)習(xí)表達(dá)式的后綴形式及后綴表達(dá)式的計算方法）*3、漢諾塔問題求解。實驗四隊列的基本操作及應(yīng)用一、實驗?zāi)康?會定義順序隊列和鏈隊的結(jié)點類型；2熟練隊列的入隊和出隊代表的實際意義；3、掌握兩種存儲結(jié)構(gòu)下隊列的基本操作：入隊、出隊和輸出隊列等；4、熟

34、悉C語言中函數(shù)的定義和調(diào)用。二、主要儀器及耗材普通計算機三、實驗內(nèi)容1、建立隊列并輸出2、插入元素后輸出隊列3、刪除元素后輸出隊列要求：在輸入數(shù)據(jù)的過程中程序做相應(yīng)的是否繼續(xù)輸入的提示。每個功能用 不同函數(shù)實現(xiàn)4、實驗要求(1) 程序中用戶可以選擇上述基本操作。程序啟動后，在屏幕上可以菜單形式顯示不同功能，當(dāng)按下不同數(shù)字后完成指定的功能，按其他鍵，則顯示錯誤后重新選擇。(2) 要求用不帶頭結(jié)點的循環(huán)鏈表實現(xiàn)。(3) 具體功能測試由主函數(shù)實現(xiàn)。5、主要代碼(1) 初始化隊列/*初始化*/void In itQueue(sqQueue *&q)q=(sqQueue *)malloc(sizeof(sqQueue);動態(tài)分配存儲空間q->fron t=q->rear=0;/*初始化隊列,構(gòu)造一個空隊列*/(2) 判斷隊列是否為空