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

1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(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í) 學(xué) 號(hào) 姓 名 成 績(jī) 一、實(shí)驗(yàn)概述：【實(shí)驗(yàn)?zāi)康摹?.線性表的邏輯結(jié)構(gòu)特征 1.1 總存在第一個(gè)和最后一個(gè)元素； 1.2 除第一個(gè)元素以外，每個(gè)元素總存在唯一一個(gè)直接前驅(qū)元素； 1.3 除最后一個(gè)元素以外，每個(gè)元素總存在唯一一個(gè)直接后繼元素。2.掌握單鏈表的基本操作在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)。【實(shí)驗(yàn)原理】1.線性鏈表的特點(diǎn) 1.1 線性鏈表是一種動(dòng)態(tài)分配的存儲(chǔ)結(jié)構(gòu)； 1.2 每一個(gè)結(jié)點(diǎn)的指針域指向其直接后繼結(jié)

2、點(diǎn)（偽結(jié)點(diǎn)除外）； 1.3 指針為數(shù)據(jù)元素之間的邏輯關(guān)系的映像。2.線性表的單鏈表存儲(chǔ)結(jié)構(gòu)Typedef struct LNode ElemType data;struct LNode *next;LNode, *LinkList;【實(shí)驗(yàn)環(huán)境】 VC+6.0二、實(shí)驗(yàn)內(nèi)容：【實(shí)驗(yàn)方案】編寫主函數(shù)，調(diào)用線性鏈表的初始化建空表，查找、插入和刪除算法，調(diào)試運(yùn)行，得出結(jié)果?！緦?shí)驗(yàn)過程】（實(shí)驗(yàn)步驟、記錄、數(shù)據(jù)、分析）一典型錯(cuò)誤舉例及改正措施例 錯(cuò)誤分析：過于大意，直接將上一次算法之前的定義之類的內(nèi)C語言復(fù)制過來，導(dǎo)致將線性表的單鏈表存儲(chǔ)結(jié)構(gòu)輸成線性表的動(dòng)態(tài)分配順序存儲(chǔ)結(jié)構(gòu)。然后就出來上述LinkList未

3、定義，L未定義，還有掉分號(hào)，掉括號(hào)之類的各種錯(cuò)誤。二完善主函數(shù)及過程錯(cuò)誤分析 以上輸出窗口這種形式的輸出容易使人輸完一步，然后忘記下一步該干嘛，于是這時(shí)候完善一下主函數(shù)，使得輸出窗口每一步操作之前都加上提示語會(huì)更好。以下是完善主函數(shù)的過程：1.在主函數(shù)每一項(xiàng)輸入之前加上一串漢字提示下一步的操作，于是主函數(shù)部分變?yōu)?然后調(diào)試，發(fā)現(xiàn)報(bào)出如下錯(cuò)誤：（后面還有好多行，這里只列舉一部分）錯(cuò)誤分析：printf后面括號(hào)中的引號(hào)應(yīng)為因?yàn)楦袷?，這里卻輸成中文格式了，故報(bào)出以上錯(cuò)誤。錯(cuò)誤改正之后，調(diào)試：0錯(cuò)誤，0警告。運(yùn)行結(jié)果： 2.觀察上述運(yùn)行結(jié)果發(fā)現(xiàn)，輸出窗口還是不夠完善，這里只有提示下一步的操作，但是沒有

4、顯示操作之后輸出的一串?dāng)?shù)字具體是什么。于是在主函數(shù)中繼續(xù)加相應(yīng)格式的漢字提示，得到：然后調(diào)試：0錯(cuò)誤，0警告。運(yùn)行結(jié)果：至此，主函數(shù)完善完畢。三測(cè)試數(shù)據(jù)1.前面幾次運(yùn)行，單鏈表的數(shù)字都比較簡(jiǎn)單且連續(xù)，于是換些比較復(fù)雜一點(diǎn)的數(shù)字測(cè)試，結(jié)果： 觀察輸出窗口，發(fā)現(xiàn)該組數(shù)據(jù)測(cè)試無誤。2當(dāng)實(shí)際輸入的元素個(gè)數(shù)小于理論上應(yīng)該輸入的個(gè)數(shù)n時(shí)，就按了Enter鍵，第三行不會(huì)顯示任何數(shù)據(jù)，但是有一個(gè)閃動(dòng)光標(biāo)暗示我們還需繼續(xù)輸入，當(dāng)輸入個(gè)數(shù)剛好等于n時(shí)，按Enter鍵，還是一樣會(huì)逆序位輸出原來的單鏈線性表L。 但是當(dāng)實(shí)際輸入元素個(gè)數(shù)大于n時(shí)，會(huì)自動(dòng)逆序位輸出前n個(gè)元素，除了查找元素會(huì)報(bào)錯(cuò)，其他都按前n個(gè)元素輸入正常

5、運(yùn)行。3.當(dāng)輸入的鏈表中的元素不是數(shù)字而是字母時(shí)會(huì)報(bào)錯(cuò)：【實(shí)驗(yàn)結(jié)論】（結(jié)果）【實(shí)驗(yàn)小結(jié)】（收獲體會(huì)）通過此次上機(jī)實(shí)驗(yàn)，除了對(duì)程序中主函數(shù)的編寫及程序的完善有了很大的突破之外，還熟悉并實(shí)踐了單鏈線性表的逆序位輸出、查找、插入和刪除算法。由于吸取上次教訓(xùn)，此次敲算法時(shí)格外小心注意，因此這次一些語句語法錯(cuò)誤之類的錯(cuò)誤就沒有了，但是對(duì)程序的完善過程卻有了很大感悟，一個(gè)好的程序不僅只是要把結(jié)果運(yùn)行出來，而且要讓人們?cè)诓僮鲿r(shí)更加便捷。三、指導(dǎo)教師評(píng)語及成績(jī)：評(píng) 語評(píng)語等級(jí)優(yōu)良中及格不及格1.實(shí)驗(yàn)報(bào)告按時(shí)完成,字跡清楚,文字?jǐn)⑹隽鲿?邏輯性強(qiáng)2.實(shí)驗(yàn)方案設(shè)計(jì)合理3.實(shí)驗(yàn)過程（實(shí)驗(yàn)步驟詳細(xì),記錄完整,數(shù)據(jù)合理

6、,分析透徹）4實(shí)驗(yàn)結(jié)論正確. 成 績(jī)： 指導(dǎo)教師簽名： 批閱日期：附錄1：源 程 序#include<stdio.h>#include<stdlib.h>#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef int ElemType;typedef struct LNode ElemType data;struct LNode *next;LNode, *LinkList;void CreateList_L(LinkList &L

7、,int n) /逆序位輸入n個(gè)元素的值，建立帶表頭結(jié)點(diǎn)的單鏈線性表L。 int i;LinkList 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,i

8、nt i,ElemType &e) /L為帶表頭結(jié)點(diǎn)的單鏈表的頭指針。/當(dāng)?shù)趇個(gè)元素存在時(shí)，其值賦給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,i

9、nt i,ElemType e) /在帶頭結(jié)點(diǎn)的單鏈線性表L中第i個(gè)位置之前插入元素eLinkList 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; p->next=s;return OK;/ ListInsert_LStatus ListDelet

10、e_L(LinkList &L,int i,ElemType &e) /在帶表頭結(jié)點(diǎn)的單鏈線性表L中，刪除第i個(gè)元素，并由e返回其值int j;LinkList p,q;p=L;j=0;while (p->next&&j<i-1) /尋找第i個(gè)結(jié)點(diǎn)并令p指向其前驅(qū)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;/Li

11、stDelete_Lvoid main() LinkList L,q;int n,i; printf("請(qǐng)輸入您要?jiǎng)?chuàng)建的單鏈線性表L中的元素個(gè)數(shù)："); scanf("%d",&n);CreateList_L(L,n); /創(chuàng)建一個(gè)單鏈線性表Lprintf("您創(chuàng)建的單鏈線性表L為：");for(q=L->next;q!=NULL;q=q->next) printf("%d ",q->data);printf("n");ElemType e; /定義函數(shù)參數(shù)為ElemT

12、ype類型printf("請(qǐng)輸入您需要查找元素的位置i：");scanf("%d",&i);GetElem_L(L,i,e); /查找單鏈線性表L中第i個(gè)位置上的元素，并用e返回其值printf("您查找的元素為：");printf("e=%dn",e); printf("請(qǐng)輸入您需要插入的元素的位置i及相應(yīng)的元素值e：");scanf("%d%d",&i,&e);ListInsert_L(L,i,e); /在單鏈線性表L中第i個(gè)位置之前插入新的數(shù)據(jù)元

13、素eprintf("插入后的單鏈線性表L為：");for(q=L->next;q!=NULL;q=q->next)printf("%d ",q->data);printf("n"); printf("請(qǐng)輸入您需要?jiǎng)h除的元素的位置i：");scanf("%d",&i);ListDelete_L(L,i,e); /刪除單鏈線性表L中第i位置上的數(shù)據(jù)元素printf("刪除第i個(gè)位置上的元素e后的單鏈線性表L為：");for(q=L->next;q!=NULL;q=q->next)printf("%d ",q->data);printf("n");附錄2：實(shí)驗(yàn)報(bào)告填寫說明 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)要說明本實(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)過程。對(duì)于驗(yàn)證性實(shí)驗(yàn)，要寫明依據(jù)何種原理、操作方法進(jìn)行實(shí)驗(yàn)，要寫明需要經(jīng)過哪幾個(gè)步驟來實(shí)現(xiàn)其操作。對(duì)于設(shè)計(jì)性