實驗報告二——單鏈表

1、數(shù)據(jù)單鏈表結(jié)構(gòu)實驗報吿二單鏈表實驗二一單鏈表分校：上海第二工業(yè)大學班級：09安全01_學號：0 姓名：禹永根日期：2010/11/23 程序名：一、上機實驗的問題和要求：單鏈表的查找、插入與刪除。設訃算法，實現(xiàn)線性結(jié)構(gòu)上的單鏈表的產(chǎn)生以及元素的 查找、插入與刪除。具體實現(xiàn)要求：1. 從鍵盤輸入20個整數(shù)，產(chǎn)生不帶表頭的單鏈表，并輸入結(jié)點值。2. 從鍵盤輸入1個整數(shù)，在單鏈表中查找該結(jié)點的位宜。若找到，則顯示“找 到了”；否則，則顯示“找不到”。3. 從鍵盤輸入2個整數(shù)，一個表示欲插入的位置i,另一個表示欲插入的數(shù)值X, 將x插入在對應位置上，輸出單鏈表所有結(jié)點值，觀察輸岀結(jié)果。4. 從鍵盤輸入

2、1個整數(shù)，表示欲刪除結(jié)點的位巻，輸出單鏈表所有結(jié)點值，觀 察輸出結(jié)果。5. 將單鏈表中值重復的結(jié)點刪除，使所得的結(jié)果表中個結(jié)點值均不相同，輸岀 單鏈表所有結(jié)點值，觀察輸出結(jié)果。6. 刪除英中所有數(shù)據(jù)值為偶數(shù)的結(jié)點，輸出單鏈表所有結(jié)點值，觀察輸出結(jié)果。7. 把單鏈表變成帶表頭結(jié)點的循環(huán)鏈表，輸出循環(huán)單鏈表所有結(jié)點值，觀察輸 岀結(jié)果。8. ()將單鏈表分解成兩個單鏈表A和B,使A鏈表中含有原鏈表中序號為 奇數(shù)的元素，而B鏈表中含有原鏈表中序號為偶數(shù)的元素，且保持原來的相對順序， 分別輸出單鏈表A和單鏈表B的所有結(jié)點值，觀察輸出結(jié)果。二、程序設計的基本思想，原理和算法描述：(包括程序的結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)

3、，輸入/輸出設計，符號名說明等)用一組地址任意的存儲單元存放線性表中的數(shù)據(jù)元素。以元素（數(shù)據(jù)元素的映象）+指針（指示后繼元素存儲位置）二結(jié)點（表 示數(shù)據(jù)元素 或 數(shù)據(jù)元素的映象）以“結(jié)點的序列”表示線性表 稱作線性鏈表（單鏈表）單鏈表是指數(shù)據(jù)接點是單向排列的。一個單鏈表結(jié)點，其結(jié)構(gòu)類 型分為兩部分：（1）、數(shù)據(jù)域：用來存儲本身數(shù)據(jù)。（2）、鏈域或稱為指針域：用來存儲下一個結(jié)點地址或者說指向其 直接后繼的指針。1、單鏈表的查找對單鏈表進行查找的思路為：對單鏈表的結(jié)點依次掃描，檢測其數(shù)據(jù)域是否是我們所 要查好的值，若是返回該結(jié)點的指針，否則返回NULL。2、單鏈表的插入因為在單鏈表的鏈域中包含了后

4、繼結(jié)點的存儲地址，所以當我們實現(xiàn)的時候，只要知 道該單鏈表的頭指針，即可依次對每個結(jié)點的數(shù)據(jù)域進行檢測。假設在一個單鏈表中存在2個連續(xù)結(jié)點p、q （其中p為q的直接前驅(qū)），若我們需要在 p、q之間插入一個新結(jié)點s,那么我們必須先為s分配空間并賦值，然后使p的鏈域存儲s 的地址，s的鏈域存儲q的地址即可。（p->link=s:s->link=q）,這樣就完成了插入操作。3、單鏈表的刪除刪除運算思想方法刪除運算是將表的第i個結(jié)點刪去。具體步驟：找到a i-1的存儲 位置P令p-next指向a i的直接后繼結(jié)點釋放結(jié)點a i的空間，將貝歸還給"存儲池"。三、源程序及注

5、釋:include <>#include <>單鏈表的左義：typedef int DataType;/DataType可以是任何相應的數(shù)據(jù)類型如int, float或chartypedef struct node/結(jié)點類型左義 DataType data;結(jié)點的數(shù)據(jù)域stmet node *next;/結(jié)點的指針域JListNodc;int a10;void main()int i;DataTypc key;DataType x;LinkList head:ListNode *p;LinkList CreateList(void)y/ 單鏈表的建立void Print

6、List(LinkList head);/單鏈表的打印LinkList LocateNode(LinkList head.DataType key);LinkList GetNode(LinkList headjnt i);void InsertList(LinkList head,DataTqpe i);/單鏈表的插入單鏈表的刪除/刪除單鏈表中重復值/刪除單鏈表中偶數(shù)值修改為循環(huán)單鏈表循環(huán)單鏈表的打印void DeleteList(LinkList headjnt i);void DeleteManyList(LinkList head);void DcleteEvenList(

7、LinkList head);void ChangeCircList(LinkList head);void PrintCircList(LinkList head);printf("建立單鏈表，輸入10個值：”)； head=CreateList();建立單鏈表PrintList(head);打印單鏈表printf(unM);printfC*輸入要査找的值：”)； scanf(H%dH,&key);p=LocateNode(head,key); 單鏈表查找 printf(,rnH);printfC'in輸入欲查找結(jié)點的位置：”)；scanf(,%d,&i);

8、p=GetNode(headj);printf(,rnH);printf(niH輸入欲插入元素的位置：”)； scanf(n%dH.&i): printf(uifl輸入欲插入的元素:°);scanf(H%dM.&x);InsertList(head.xJ);/ 單鏈表插入PrintList(head);打印單鏈表printf(HnM);printf("請輸入欲刪除結(jié)點的位置：”)； scanf(H%d&i);DeleteList(head.i);單鏈表刪除PrintList(head);打印單鏈表printf(,rnM);DeleteManyList

9、(head); 刪除重復值PrintList(head);打印單鏈表DeleteEvenList(head); 刪除偶數(shù)值PrintList(head);打印單鏈表ChangeCircList(head); /修改為循環(huán)單鏈表PrintCircList(head); 打印循環(huán)單鏈表/void DivideList(LinkList head.LinkList *A,LinkList *B);分割成兩個單鏈表DivideList(head, &A. &B);PrintList(A);PrintList(B);*/單鏈表的建立：LinkList CreateList(void)in

10、t i;head=NULL;r=NULL;for(i=0;i<10;i 卄)s=(ListNode *)malloc(sizeof(ListNode); scanf(”d”、&ai);s->data=ai;if(head=NULL)head=s;else r->next=s;r=s;if(r!=NULL)r->next=NULL;return head;單鏈表的打印：void PrintList(LinkList head)ListNode *p;p=hcad;while(p)printf(M%d *p->data);p=p->next;/單鏈表的査

11、找1:ListNode *p=head;int i=0;while(p&&p->data!=key)p=p->next;i+；if(i<20)printf(”找到了 “)；elseprintf("找不到”)；return p;/單鏈表的査找2：LinkList GetNode(LinkList headjnt i)intj;ListNode *p;p=hcad;j=l;while(p->next&&jvi)p=p->next;j卄；printf("第d 結(jié)點的值為%d",i,p->data);re

12、turn p;elsereturn NULL:單鏈表的插入：void InsertList(LinkList head,DataType i)ListNode 水p,*s;intj；p=hcad;j=l;while(p&&jvil)p=p->next;j+;)if(p=NULL)printf("插入的位置非法n");exit(O);)s=(ListNode *)malloc(sizeof(ListNode);s->data=x;s->next=p->next;p->next=s;單鏈表的刪除：void DeleteL

13、ist(LinkList i)ListNode *p,*r;intj；p=hcad;j=l;while(p&&jvil)p=p->next;j+；if(p->next=NULLIIj>i-1)printf("刪除位置非法n”);exit(O);r=p->next;p->ncxt=r->next;free(r);刪除單鏈表中重復值：void DeleteManyList(LinkList head)/在此插入必要的語句LinkList pqtcmp;p=head->next;while(p->next)q

14、=p;while(q)if(q->next->data=p->data) temp=q->next; q->next=temp->next; free(temp);elseq=q->next;)p=p->next;)刪除單鏈表中偶數(shù)值：void DeleteEvenList(LinkList head)(在此插入必要的語句LinkList p.temp;p=head; while(p)(if(p->next->data%2=0)temp=p->next; p->next=temp->next;elsep=p->

15、next:)/修改為循環(huán)單鏈表：void ChangeCircList(LinkList head)在此插入必要的語句LinkList p;p=hcad->next;while(p->next)p=p->next; p->next=head;)/循環(huán)單鏈表的打?。簐oid PrintCircList(LinkList head)(在此插入必要的語句LinkList p;p=head->next; while(p->next!=head)printf("%d *p->data); p=p->next;四、運行輸出結(jié)果:單鏈表的建立建立單鏈表，輸入10個值：丄234563$992 .