《數據結構B》實驗報告系計算機與電子專業電子科學與技術2008級01__班姓名岳恒學號200811850282010年10月9日上機題目：鏈式存儲實驗詳細設計實驗目的：理解鏈表的邏輯結構和存儲結構，熟練掌握鏈表的相關操作。1、問題描述鏈表是用一組任意的存儲單元來依次存儲線性表中的各個數據元素，這些存儲單元可以是連續的，也可以是不連續的。用鏈接存儲結構表示線性表的一個元素時至少要有兩部分信息:一是這個數據元素的值，二是這個數據元素的直接后繼的存儲地址。這兩部分信息一起組成了鏈表的一個結點。數據域用來存放數據元素的值；指針域（又稱鏈域）用來存放該數據元素的直接后繼結點的地址。鏈表正是通過每個結點的指針域將線性表的n個結點按其邏輯次序鏈接成為一個整體。通常用箭頭表示鏈域中的指針，于是單鏈表就可以直觀地畫成用箭頭鏈接起來的結點序列，單鏈表中每個結點的存儲地址存放在其直接前驅的指針域中，因此訪問單鏈表的每一個結點必須從表頭指針開始進行。對單鏈表的操作主要有：建立單鏈表、查找（按序號查找、按值查找）、插入一個結點、刪除一個結點、求表長等。2、數據結構設計單鏈表的結點結構如下：typedefstructnode{/*單鏈表結點結構*/ElemTypedata;/*ElemType可以是任何相應的數據類型如int,char等*/structnode*next;}LinkList;3、功能（函數）設計鏈表的基本操作：InitList1(LinkList*&head)//初始化不帶頭結點的鏈表頭指針AddHead1(LinkList*&head,ElemTypex)//使用表首添加法，向頭指針為head的鏈表中插入一個結點，其值為xInitList(LinkList*&head)//初始化帶頭結點的鏈表頭指針AddHead(LinkList*head,ElemTypex)//使用表尾添加法，向頭指針為head的鏈表中插入一個結點，其值為xCreatList(LinkList*head,intn)//生成含有n個結點的單鏈表output(LinkList*head)//輸出單鏈表GetNode(LinkList*head,inti)//在帶頭結點的單鏈表中查找第i個結點，找到返回該結點指針，否則返回NULLLocateNode(LinkList*head,ElemTypex)//在帶頭結點的單鏈表中查找值為x的結點，找到返回結點指針，否則返回NULLInsertNode(LinkList*head,inti,ElemTypex)//在帶頭結點的單鏈表中第i個結點位置上插入值為x的結點DeleteNode1(LinkList*head,ElemTypex)//在帶頭結點的單鏈表中刪除值為x的結點DeleteNode(LinkList*head,inti)//在帶頭結點的單鏈表中刪除第i個結點Length(LinkList*head)//在帶頭結點的單鏈表中求表的長度InsertOrder(LinkList*head,intx)//在有序單鏈表L中插入值為x的結點，插入后仍然有序union1(LinkList*head,LinkList*B,LinkList*&C)//A和B是兩個帶頭結點的遞增有序的單鏈表，本算法將兩表合并成，一個帶頭結點的遞增有序單鏈表C,利用原表空間。4、界面設計指導用戶按照正確的格式輸入數據。5、編碼實現#include<stdio.h>#include<iostream.h>#include<process.h>typedefintElemType;#defineMaxSize100typedefstruct{ElemTypedata[MaxSize];intfront;intrear;}CircSeqQueue;voidQueueInitial(CircSeqQueue*pQ)//創建一個由指針pQ所指向的空順序循環隊列{pQ->front=pQ->rear=0;}intIsEmpty(CircSeqQueue*pQ)//判斷隊列是否為空{returnpQ->front==pQ->rear;}intIsFull(CircSeqQueue*pQ)////判斷隊列是否已滿{return(pQ->rear+1)%MaxSize==pQ->front;}voidEnQueue(CircSeqQueue*pQ,ElemTypee)//若隊列不滿則元素e進隊{if(IsFull(pQ)){printf(”隊列益處!\n");return;}pQ->rear=(pQ->rear+1)%MaxSize;pQ->data[pQ->rear]=e;}ElemTypeDeQueue(CircSeqQueue*pQ)//若循環隊列不為空，則刪除隊頭元素，并返回他的值{if(IsEmpty(pQ)){printf(”空隊列!\n");exit(1);}pQ->front=(pQ->front+1)%MaxSize;returnpQ->data[pQ->front];}ElemTypeGetFront(CircSeqQueue*pQ)//若循環隊列不為空,則返回隊頭元素的值{if(IsEmpty(pQ)){printf(”空列隊!\n");exit(1);}returnpQ->data[(pQ->front+1)%MaxSize];}voidMakeEmpty(CircSeqQueue*pQ)//將由指針pQ所指向的隊列變為空隊{pQ->front=pQ->rear=0;}voidoutput1(){inti;for(i=0;i<10;i++)printf("");for(i=0;i<31;i++)printf("*");printf("\n");}voidmainpp(){inti;output1();for(i=0;i<10;i++)printf("");printf("*");printf("l.元素進隊”)；for(i=0;i<16;i++)printf("");printf("*");printf("\n");for(i=l；i<ll；i++)printf("")；printf("*")；printf("2.元素出隊”)；for(i=0；i<l6；i++)printf("")；printf("*")；printf("\n")；for(i=l；i<ll；i++)printf("")；printf("*")；printf("3.讀隊首元素”)；for(i=0；i<l4；i++)printf("")；printf("*")；printf("\n")；for(i=l；i<ll；i++)printf("")；printf("*")；printf("4.列隊置空”)；for(i=0；i<l6；i++)printf("")；printf("*")；printf("\n")；for(i=l；i<ll；i++)printf("")；printf("*")；printf("0.退出”)；for(i=0；i<8；i++)printf("")；printf("*")；printf("\n")；outputl()；}voidmain(){intk,m,n,i；CircSeqQueue*pQ；ElemTypee；pQ=newCircSeqQueue；QueueInitial(pQ)；mainpp()；while(k){printf("請選擇0--4：")；scanf(”％d",&m);//getchar()；switch(m){case0:return;case1:{printf（"請輸入入隊元素的個數：”）；scanf（"%d",&n）;printf（"輸入元素，入隊:\n"）;for（i=0；i<n；i++）{scanf（"%d"，&e）;EnQueue（pQ，e）;}break;}case2:{printf（"請輸入出隊元素的個數：”）；scanf（"%d"，&n）;printf（"輸入元素，出隊:\n"）;for（i=0;i<n;i++）{e=DeQueue（pQ）;printf（"%d\n"，e）;}break;}case3:{printf（"取出隊首元素：\n"）;e=GetFront（pQ）;printf（"%d\n"，e）;break;}case4:{printf（"隊列已置空!\n"）;MakeEmpty（pQ）;printf（"\n"）;break;}default:return;}printf（"繼續運行嗎？Y（1）/N（0）:"）;scanf（"%d",&k）;if（!k）return;}}調試分析調試過程中主要遇到哪些問題？是如何解決的？刪除多余元素——將i和j搞混，導致計數啥亂了；誤將==寫成=，結果根本就沒有運行刪除算法；在每次刪除之后沒有j--，結果當重復多個元素之后，只能刪除一個元素，后來明白，每刪除一個元素，j--,才能使j指向再次重復