數(shù)據(jù)結(jié)構(gòu)單鏈表實(shí)驗(yàn)報告

1、洛陽理工學(xué)院實(shí)驗(yàn)報告系別計算機(jī)系班級學(xué)號姓名課程名稱數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)日期11.7實(shí)驗(yàn)名稱鏈表的基本操作成績實(shí)驗(yàn)?zāi)康?熟悉掌握線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)，掌握與應(yīng)用查找、插入、刪除等基本操作 算法，訓(xùn)練和提高結(jié)構(gòu)化程序設(shè)計能力及程序調(diào)試能力。實(shí)驗(yàn)條件:計算機(jī)一臺，Visual C+6.0實(shí)驗(yàn)內(nèi)容:1. 問題描述以單鏈表為存儲結(jié)構(gòu)實(shí)現(xiàn)以下基本操作:在第i個元素前插入一個新元素。查找值為x的某個元素。若成功，給出x在表中的位置；不成功給出提示信息。刪除第i個元素，若成功，給出提示信息并顯示被刪元素的值；不成 功給出失敗的提示信息。2. 數(shù)據(jù)結(jié)構(gòu)類型定義 typ edef struct Lin kNodeint

2、Value;Node,*Li nkList;3.模塊劃分（1）（2）（3）（4）struct Lin kNode * Next;初始化鏈表：void In itList(Li nkList * L);創(chuàng)建鏈表：尾插法：int CreateFromTail(LinkList L); 在指定位置插入元素：int In sList(Li nkList L,i nt i,i nt e);在指定位置刪除元素：int DelList(Li nkList L,i nt i,i nt *e); 返回值說明：返回ERRO插入失敗，返回OK插入成功;（5）4.詳細(xì)設(shè)計按位置查找鏈表元素：int GetList(L

3、i nkList L,i nt i,i nt *e);void in it_li nklist(Li nkList *1)/*對單鏈表進(jìn)行初始化*/申請結(jié)點(diǎn)空間*/*l=(Li nkList)malloc(sizeof(Node); /*(*l)->n ext=NULL;/*置為空表*/void CreateFromHead(L in kListL)Node *s;char c;int flag=1;while(flag) /* flag初值為1,當(dāng)輸入"$"時，置flag為0，建表結(jié)束*/c=getchar();if(c!='$')s=(Node*)

4、malloc(sizeof(Node); /*建立新結(jié)點(diǎn)s*/s->data=c;s->next=L->next;/*將s結(jié)點(diǎn)插入表頭*/L->n ext=s;elseflag=0;void CreateFromTail(L in kList L)Node *r, *s;char c;int flag =1; /*表結(jié)束*/設(shè)置一個標(biāo)志，初值為1，當(dāng)輸入"$"時，flag為0，建r=L;入，其初值指向頭結(jié)點(diǎn) */*r指針動態(tài)指向鏈表的當(dāng)前表尾，以便于做尾插while(flag)/*循環(huán)輸入表中元素值，將建立新結(jié)點(diǎn)s插入表尾*/c=getchar();

5、if(c!='$')s=(Node*)malloc(sizeof(Node);s->data=c;r->n ext=s;r=s;elseflag=0;r->next=NULL; /*將最后一個結(jié)點(diǎn)的next鏈域置為空，表示鏈表的結(jié)束*/Node * Get (Lin kList L, i nt i)/*在帶頭結(jié)點(diǎn)的單鏈表 L中查找第i個結(jié)點(diǎn)，若找到(1 < i < n)，則返回該結(jié)點(diǎn) 的存儲位置；否則返回NULL*/int j;Node *p;p=L;j=0; /* 從頭結(jié)點(diǎn)開始掃描*/掃描下一結(jié)點(diǎn)*/while (p->n ext!=NUL

6、L)&&(j<i)p=p->n ext; /*j+； /*已掃描結(jié)點(diǎn)計數(shù)器 */if(i = j)return p; /*找到了第i個結(jié)點(diǎn)*/elsereturn NULL; /*i>n */Node *Locate( Lin kList L,ElemT ype key)/*在帶頭結(jié)點(diǎn)的單鏈表L中查找其結(jié)點(diǎn)值等于key的結(jié)點(diǎn)，若找到則返回該結(jié)點(diǎn)的位置P,否則返回NULL*/Node *p;P=L->n ext; /*從表中第一個結(jié)點(diǎn)開始*/while (p !=NULL)if (p->data!=key)p=p->n ext;elsebrea

7、k; /*找到結(jié)點(diǎn)值=key時退出循環(huán)*/return p;int In sList(L in kList L,i nt i,ElemT ype e)/*在帶頭結(jié)點(diǎn)的單鏈表L中第i個位置插入值為e的新結(jié)點(diǎn)s*/Node *p re,*s;int k;p re=L;k=0;/*從"頭"開始，查找第i-1個結(jié)點(diǎn)*/表未查完且未查到第i-1個時重復(fù)，找到prewhile( pre!=NULL&&k<i-1) /* 指向第i-1個*/pre=pre->n ext;k=k+1;if(! pre) /*位置不合理*/*查找第i-1結(jié)點(diǎn)*/如當(dāng)前位置pre為空

8、表已找完還未數(shù)到第i個，說明插入prin tf("插入位置不合理!")；return ERROR;s=(Node*)malloc(sizeof(Node);/*申請一個新的結(jié)點(diǎn)S */s->data=e;/*值e置入s的數(shù)據(jù)域*/s->n ext=pre->n ext;/*修改指針，完成插入操作*/pre->n ext=s;return OK;int DelList(Li nkList L,i nt i,ElemTy pe *e)/*個元素，并將刪除的元素保存到變量*e中在帶頭結(jié)點(diǎn)的單鏈表L中刪除第*/Node *p re,*r;int k;p re

9、=L;k=0;while( pre-> next!=NULL && k<i-1) p指向它*/*尋找被刪除結(jié)點(diǎn)i的前驅(qū)結(jié)點(diǎn)i-1使pre=pre->n ext;k=k+1;/*查找第i-1個結(jié)點(diǎn)*/if(!( pre-> next)/*即 while 循環(huán)是因?yàn)?p->next=NULL 或iv1 而跳i不合法。*/出的，而是因?yàn)闆]有找到合法的前驅(qū)位置，說明刪除位置printf("刪除結(jié)點(diǎn)的位置i不合理!");return ERROR;修改指針，刪除結(jié)點(diǎn) r*/r=pre->n ext;pre->n ext=pre-

10、>n ext- >n ext; /*e = r->data;free(r); /*釋放被刪除的結(jié)點(diǎn)所占的內(nèi)存空間*/prin tf("成功刪除結(jié)點(diǎn)門;return OK;int ListLength(LinkList L)/*求帶頭結(jié)點(diǎn)的單鏈表 L的長度*/Node *p;int j;P=L->n ext;j=0; /*用來存放單鏈表的長度*/while( p!=NULL)p=p->n ext;return j; /*j為求得的單鏈表長度 */5.測試數(shù)據(jù)及結(jié)果qj 1 CWindow=£ytemS20«bi_ioCppL.w"<<e-n4JLMln杳找J *