實驗報告2(單鏈表)

信息學(xué)院高級語言程序設(shè)計上機實驗報告學(xué)號：134120337姓名：王靖班級：計科13B實驗時間：2014.10.22實驗性質(zhì)：□綜合性實驗□設(shè)計性實驗□驗證實驗實驗內(nèi)容：鏈表的創(chuàng)建、插入等操作題目來源：□教材頁題□教師補充□自選題目主要功能描述：用一組任意的存儲單元來存放線性表的結(jié)點，這組存儲單元可以是連續(xù)的，也可以是非連續(xù)的，甚至是零散分布在任何位置上的，從而實現(xiàn)鏈表的創(chuàng)建（頭插法、尾插法），在鏈表中實現(xiàn)結(jié)點的插入、查找（按序號查找、按值查找）和刪除的操作。設(shè)計分析：定義結(jié)點指針類型：結(jié)點包括兩個域，即數(shù)據(jù)域（用來存儲結(jié)點的值）和指針域（用來存儲數(shù)據(jù)元素的直接后繼的地址）。鏈表的創(chuàng)建（1）頭插入法：從一個空表開始，每次讀入數(shù)據(jù)，生成新結(jié)點，將讀入數(shù)據(jù)存放到新結(jié)點的數(shù)據(jù)域中，然后將新結(jié)點插入到當(dāng)前鏈表的表頭結(jié)點之后，直到讀入結(jié)束標(biāo)志為止；（2）尾插入法：將新結(jié)點依次插到當(dāng)前單鏈表的表尾上；鏈表元素查找（1）按序號查找：從單鏈表的頭指針L出發(fā)，開始順著鏈域掃描，用j做作為計數(shù)器，當(dāng)掃描次數(shù)j=要查找的序號時為止；（2）按值查找：從單鏈表的頭指針指向的頭結(jié)點出發(fā)，順鏈逐個將結(jié)點值和給定值進行比較，返回查找結(jié)果；鏈表元素插入：找到要插入的位置，申請新結(jié)點并將其數(shù)據(jù)域的值置為要插入的值，最后進行插入操作；鏈表元素的刪除：通過計數(shù)方式找到要刪除的結(jié)點的前一個結(jié)點p，刪除p->next并釋放結(jié)點空間。典型測試數(shù)據(jù)輸入：輸出：預(yù)期結(jié)果：Heat->1->2->3->4->5->NULLHeat->1->2->3->4->5->NULL22Heat->1->9->2->3->4->5->NULLHeat->1->2->3->4->5->NULL程序及運行結(jié)果正誤判斷：□非常好□正確，還可改進□基本正確，還需改進□還有錯誤不足之處或設(shè)計經(jīng)驗小結(jié)：該試驗中程序的設(shè)計思路基本正確，但在程序設(shè)計時，考慮到計算機對程序的讀取速度，還可進一步改進，使該程序更簡潔明了且程序運行效率提高，實現(xiàn)完該程序的設(shè)計后，讓我掌握了單鏈表的結(jié)點結(jié)構(gòu)以及對結(jié)點的數(shù)據(jù)域和指針域的運用水平提高，我個人認(rèn)為鏈表的創(chuàng)建中，用了兩種插入法（頭插入法和尾插入法），這樣，我們在以后作其他程序需要用到鏈表時，可更輕松方便地根據(jù)情況運用兩種插入法創(chuàng)建鏈表。任課教師評語：教師簽字：年月日源程序（1）流程圖：略（2）程序：#include"stdio.h"#include"stdlib.h"typedefintElemType;typedefstructNode//定義結(jié)點類型{ ElemTypedata; structNode*next;}Node,*LinkList;voidInitList(LinkList*L)//表初始化{ *L=(LinkList)malloc(sizeof(Node)); (*L)->next=NULL;}voidCreateFromHead(LinkListL)//頭插入法{ Node*s; intc=0,flag; printf("請逆序輸入一串?dāng)?shù)字，以負(fù)數(shù)結(jié)束："); while(flag) { scanf("%d",&c); if(c>-1) { s=(Node*)malloc(sizeof(Node)); s->data=c; s->next=L->next; L->next=s; } elseflag=0; }}voidCreateFromTail(LinkListL)//尾插入法{ Node*r,*s; intc=0,flag; r=L; printf("請順序輸入一串?dāng)?shù)字，以負(fù)數(shù)結(jié)束："); while(flag) { scanf("%d",&c); if(c>-1) {}voidoutput(LinkListL)//鏈表輸出{ Node*p; p=L->next; printf("Head->"); if(p==NULL) printf("NULL!"); while(p!=NULL) { printf("%d->",p->data); p=p->next; } printf("NULL\n"); system("pause"); }voidListLength(LinkListL)//計算單鏈表的長度{ Node*p; p=L; intj=0; if(p->next==NULL) printf("NULL!"); while(p!=NULL) { p=p->next; j++; } printf("單鏈表的長度為：%d\n",j); system("pause");}voidCharu(LinkListL,inti,ElemTypee)//插入結(jié)點{ intj=1; Node*p;Node*s; p=L; printf("請輸入要插入的位置："); scanf("%d",&i); if(i<=0)printf("無法找到插入位置?。?); printf("請輸入插入的值："); scanf("%d",&e); printf("\n"); while(p!=NULL&&j<i) printf("|[2]尾部插入|\n"); printf("|[3]輸出鏈表|\n"); printf("|[4]序號查找|\n"); printf("|[5]按值查找|\n"); printf("|[6]插入結(jié)點|\n"); printf("|[7]刪除結(jié)點|\n"); printf("|[8]鏈表長度|\n"); printf("|[0]退出\n"); scanf("%d",&t); switch(t) { case0: { break; } case1: { InitList(&L); CreateFromHead(L); output(L); break; } case2: { InitList(&L); CreateFromTail(L); output(L); break; } case3: { output(L); break; } case4: {inti; Get(L,i); system("pause"); break; } case5: { ElemTypee;Get1(L,e); system("pause"); break; } case6: s=(Node*)malloc(sizeof(Node)); s->data=c; r->next=s; r=s; } else { r->next=NULL; flag=0; } }}voidGet(LinkListL,inti)//按序號查找{ intj; printf("請輸入查找值的序號："); scanf("%d",&i); Node*p; if(i<=0)printf("ERROR!"); p=L;j=0; while((p->next!=NULL)&&(j<i)) { p=p->next; j++; } if(i==j)printf("查找的值為：%d\n",p->data); elseprintf("ERROR!");}voidGet1(LinkListL,ElemTypee)//按值查找{intj; printf("請輸入要查找的值："); scanf("%d",&e); Node*p; p=L->next;j=1; while(p!=NULL) { if(p->data!=e){ p=p->next; } else { printf("該值的序列號為：%d\n",j); break;} j++; }; if(p==NULL)printf("找不到該值??！"); { p=p->next; j++; } if(!p) { printf("插入不合理?。?); } s=(Node*)malloc(sizeof(Node)); s->data=e; s->next=p->next; p->next=s;}voidShanchu(LinkListL,inti,ElemType*e)//刪除結(jié)點{ Node*p,*r; intj=1; p=L; printf("請輸入要刪除的位置："); scanf("%d",&i); while(p->next!=NULL&&j<i) { p=p->next; j++; } if(!(p->next)) { printf("刪除的位置不合理??！"); } r=p->next; p->next=r->next; *e=r->data; printf("刪除的值為：%d\n",r->data); free(r); }voidmain()//主函數(shù){ LinkListL; intt; while(t!=0) { system("cls"); printf("|請輸入選擇|\n"); printf("|[1]頭部插入|\n"); {