線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)

1、數(shù)學(xué)與計(jì)算科學(xué)學(xué)院實(shí) 驗(yàn) 報(bào) 告實(shí)驗(yàn)項(xiàng)目名稱 線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn) 所屬課程名稱 數(shù)據(jù)結(jié)構(gòu) 實(shí) 驗(yàn) 類 型 驗(yàn)證型 實(shí) 驗(yàn) 日 期 2013.10.31 班 級(jí) 信計(jì)1201 學(xué) 號(hào) 201253100109 姓 名 成 績(jī) 一、實(shí)驗(yàn)概述：【實(shí)驗(yàn)?zāi)康摹?、了解線性表的邏輯結(jié)構(gòu)特征：總存在第一個(gè)和最后一個(gè)元素；除第一個(gè)元素外，每個(gè)元素總存在唯一一個(gè)直接前驅(qū)元素；除最后一個(gè)元素外，每個(gè)元素總有唯一一個(gè)直接后繼元素。2、掌握單鏈表的基本操作在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)【實(shí)驗(yàn)原理】1、線性鏈表特點(diǎn)：是一種動(dòng)態(tài)分配存儲(chǔ)結(jié)構(gòu)，每一個(gè)結(jié)點(diǎn)的指示域指向其直接后繼結(jié)點(diǎn)（尾結(jié)點(diǎn)除外）；指針為數(shù)據(jù)元素之間的邏輯關(guān)系的映

2、像。2、線性表的單鏈表存儲(chǔ)結(jié)構(gòu)：typedef struct LNodeElemType data;struct LNode *next;LNode,*LinkList;【實(shí)驗(yàn)環(huán)境】VC + 6.0二、實(shí)驗(yàn)內(nèi)容：【實(shí)驗(yàn)方案】編寫(xiě)主函數(shù)，調(diào)用線性鏈表的初始化建空表、查找、插入和刪除算法，調(diào)制運(yùn)行，得出結(jié)果?！緦?shí)驗(yàn)過(guò)程】（實(shí)驗(yàn)步驟、記錄、數(shù)據(jù)、分析）1、輸入線性鏈表的初始化建空表、查找、插入、刪除算法以及主函數(shù)：/線性表的單鏈表存儲(chǔ)結(jié)構(gòu)typedef struct LNodeElemType data;struct LNode *next;LNode,*LinkList;void CreateLi

3、st_L(LinkList &L,int n)/逆位序輸入n個(gè)元素的值，建立帶表頭結(jié)點(diǎn)的單鏈線性表L。/CreateList_LStatus GetElem_L(LinkList L,int i,ElemType &e)/L為帶頭結(jié)點(diǎn)的單鏈表的頭指針。/當(dāng)?shù)趇個(gè)元素存在時(shí)，其值賦給e并返回OK,否則返回ERROR/GetElem_LStatus ListInsert_L(LinkList &L,int i,ElemType e)/在帶頭結(jié)點(diǎn)的單鏈線性表L中第i個(gè)位置之前插入元素e/ListInsert_LStatus ListDelete_L(LinkList &

4、;L,int i,ElemType &e)/在帶頭結(jié)點(diǎn)的單鏈線性表L中，刪除第i個(gè)元素，并由e返回其值/ListDelete_Lvoid main()2、保存并開(kāi)始調(diào)試，出現(xiàn)如下錯(cuò)誤：error C2065: 'i' : undeclared identifiererror C2065: 'p' : undeclared identifier即i,p未定義，因i是整型，p是鏈表，故需在前面先進(jìn)行定義：int i;LinkList p;在scanf(&p->data); /輸入元素值 中出現(xiàn)錯(cuò)誤：error C2664: 'scanf

5、' : cannot convert parameter 1 from 'int *' to 'const char *'.不能將參數(shù)1從'int *'到 'const char *'，因p->data表示的是一個(gè)數(shù)，故需說(shuō)明輸入的是一個(gè)十進(jìn)制數(shù)，應(yīng)修改為：scanf(“%d”,&p->data)；在Status ListInsert_L(LinkList &L,int i,ElemType e)int;p=L; j=0;while(p&&j<i-1)p=p->nex

6、t;+j; if(!p|j>i-1) return ERROR; s=(LinkList)malloc(sizeof(LNode); s->data=e;s->next=p->next; p->next=s;return OK;/ListInsert_L中也出現(xiàn)錯(cuò)誤：error C2065: 'p' : undeclared identifier；error C2440: '=' : cannot convert from 'struct LNode *' to 'int'； error C2065:

7、 's' : undeclared identifier；主要是由于在該編碼中p,s表示的是鏈表，但沒(méi)給它們進(jìn)行定義，不能直接把鏈表賦給它們，因此需在前面對(duì)它們進(jìn)行定義：LinkList p,s;3、把錯(cuò)誤修正過(guò)來(lái)后，運(yùn)行：輸入一個(gè)數(shù)5，表示鏈表空間數(shù)，回車(chē)，再輸入任意五個(gè)數(shù)字如：1 2 3 4 5，回車(chē)，得到：5 4 3 2 1，完成了鏈表的建立，并把鏈表倒轉(zhuǎn)過(guò)來(lái)；輸入數(shù)字3，表示查找鏈表中的第三個(gè)元素，回車(chē)得出結(jié)果，完成鏈表查找算法；輸入2 45，表示在鏈表第二個(gè)元素前插入45，回車(chē)得結(jié)果，完成鏈表插入算法；再輸入4，表示刪除鏈表第四個(gè)元素，回車(chē)得結(jié)果，完成鏈表的刪除算法；

8、最終完成鏈表的初始化建空表、查找、插入和刪除的算法。【實(shí)驗(yàn)結(jié)論】（結(jié)果）【實(shí)驗(yàn)小結(jié)】（收獲體會(huì)）在這次上機(jī)實(shí)驗(yàn)中，在進(jìn)行調(diào)制時(shí)，自己慢慢調(diào)試，漸漸地了解了那些錯(cuò)誤什么意思，如何修改，最終完成了線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)，對(duì)線性鏈表的初始化建空表、查找、插入、和刪除算法有了進(jìn)一步了解。三、指導(dǎo)教師評(píng)語(yǔ)及成績(jī)：評(píng) 語(yǔ)評(píng)語(yǔ)等級(jí)優(yōu)良中及格不及格1.實(shí)驗(yàn)報(bào)告按時(shí)完成,字跡清楚,文字?jǐn)⑹隽鲿?邏輯性強(qiáng)2.實(shí)驗(yàn)方案設(shè)計(jì)合理3.實(shí)驗(yàn)過(guò)程（實(shí)驗(yàn)步驟詳細(xì),記錄完整,數(shù)據(jù)合理,分析透徹）4實(shí)驗(yàn)結(jié)論正確. 成 績(jī)： 指導(dǎo)教師簽名： 批閱日期：附錄1：源 程 序#include<stdio.h>#include

9、<stdlib.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef int ElemType;typedef struct LNodeElemType data;struct LNode *next;LNode,*LinkList;void CreateList_L(LinkList &L,int n)/逆位序輸入n個(gè)元素的值，建立帶表頭結(jié)點(diǎn)的單鏈線性表L。int i;LinkL

10、ist p;L=(LinkList) malloc(sizeof(LNode);L->next=NULL; /先建立一個(gè)代表頭結(jié)點(diǎn)的單鏈表for(i=n;i>0;-i)p=(LinkList) malloc(sizeof(LNode); /生成新結(jié)點(diǎn)scanf("%d",&p->data); /輸入元素值p->next=L->next;L->next=p;/CreateList_LStatus GetElem_L(LinkList L,int i,ElemType &e)/L為帶頭結(jié)點(diǎn)的單鏈表的頭指針。/當(dāng)?shù)趇個(gè)元素存在時(shí)

11、，其值賦給e并返回OK,否則返回ERRORint j;LinkList p;p=L->next;j=1; /初始化，p指向第一個(gè)結(jié)點(diǎn)，j為計(jì)數(shù)器while(p&&j<i) /順指針向后查找，直到p指向第i個(gè)元素或p為空p=p->next;+j;if(!p|j>i)return ERROR; /第i個(gè)元素不存在e=p->data; /取第i個(gè)元素return OK;/GetElem_LStatus ListInsert_L(LinkList &L,int i,ElemType e)/在帶頭結(jié)點(diǎn)的單鏈線性表L中第i個(gè)位置之前插入元素eLinkL

12、ist p,s;int j;p=L; j=0;while(p&&j<i-1)p=p->next;+j; /尋找第i-1個(gè)結(jié)點(diǎn)if(!p|j>i-1) return ERROR; /i小于1或者大于表長(zhǎng)加1s=(LinkList)malloc(sizeof(LNode); /生成新結(jié)點(diǎn)s->data=e;s->next=p->next; /插入L中p->next=s;return OK;/ListInsert_LStatus ListDelete_L(LinkList &L,int i,ElemType &e)/在帶頭結(jié)點(diǎn)

13、的單鏈線性表L中，刪除第i個(gè)元素，并由e返回其值LinkList p,q;int j;p=L;j=0;while(p->next &&j<i-1) /尋找第i個(gè)結(jié)點(diǎn)，并令p指向其前趨p=p->next;+j;if(!(p->next)|j>i-1)return ERROR; /刪除位置不合理q=p->next; p->next=q->next; /刪除并釋放結(jié)點(diǎn)e=q->data; free(q);return OK;/ListDelete_Lvoid main()LinkList L;LinkList p; int n,i

14、; scanf("%d",&n); CreateList_L(L,n); for(p=L->next;p!=NULL;p=p->next)printf("%d ",p->data);printf("n"); ElemType e; scanf("%d",&i); GetElem_L(L,i,e);printf("e=%dn",e);scanf("%d%d",&i,&e);ListInsert_L(L,i,e); for(p=L

15、->next;p;p=p->next)printf("%d ",p->data);printf("n");scanf("%d",&i);ListDelete_L(L,i,e);for(p=L->next;p;p=p->next)printf("%d ",p->data);printf("n");附錄2：實(shí)驗(yàn)報(bào)告填寫(xiě)說(shuō)明 1實(shí)驗(yàn)項(xiàng)目名稱：要求與實(shí)驗(yàn)教學(xué)大綱一致。2實(shí)驗(yàn)?zāi)康模耗康囊鞔_，要抓住重點(diǎn)，符合實(shí)驗(yàn)教學(xué)大綱要求。3實(shí)驗(yàn)原理：簡(jiǎn)要說(shuō)明本實(shí)驗(yàn)項(xiàng)目所涉及的理論知識(shí)。4實(shí)驗(yàn)環(huán)境：實(shí)驗(yàn)用的軟、硬件環(huán)境。5實(shí)驗(yàn)方案（思路、步驟和方法等）：這是實(shí)驗(yàn)報(bào)告極其重要的內(nèi)容。概括整個(gè)實(shí)驗(yàn)過(guò)程。對(duì)于驗(yàn)證性實(shí)驗(yàn)，要寫(xiě)明依據(jù)何種原理、操作方法