鏈表操作數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)目錄TOC\o"1—3”\h\u166971選題背景 2232202方案與論證 3258412。1鏈表的概念和作用 3265912。3算法的設(shè)計(jì)思想 4187062。4相關(guān)圖例 5150312.4.1單鏈表的結(jié)點(diǎn)結(jié)構(gòu) 5277712.4。2算法流程圖 5122303實(shí)驗(yàn)結(jié)果 6220343.1鏈表的建立 6258113.2單鏈表的插入 6320213.3單鏈表的輸出 7190563.4查找元素 7135493。5單鏈表的刪除 8325073。6顯示鏈表中的元素個(gè)數(shù)（計(jì)數(shù)) 9165624結(jié)果分析 1098784。1單鏈表的結(jié)構(gòu) 1050594。2單鏈表的操作特點(diǎn) 10204464。2。1順鏈操作技術(shù) 10123154.2。2指針保留技術(shù) 10131654。3鏈表處理中的相關(guān)技術(shù) 10226005設(shè)計(jì)體會(huì)及今后的改進(jìn)意見 1119571參考文獻(xiàn) 1214900附錄代碼： 13

1選題背景陳火旺院士把計(jì)算機(jī)60多年的發(fā)展成就概括為五個(gè)“一”：開辟一個(gè)新時(shí)代-—--信息時(shí)代,形成一個(gè)新產(chǎn)業(yè)-—-—信息產(chǎn)業(yè),產(chǎn)生一個(gè)新科學(xué)—計(jì)算機(jī)科學(xué)與技術(shù)，開創(chuàng)一種新的科研方法-—--計(jì)算方法，開辟一種新文化—計(jì)算機(jī)文化，這一概括深刻影響了計(jì)算機(jī)對(duì)社會(huì)發(fā)展所產(chǎn)生的廣泛而深遠(yuǎn)的影響。數(shù)據(jù)結(jié)構(gòu)和算法是計(jì)算機(jī)求解問題過(guò)程的兩大基石。著名的計(jì)算機(jī)科學(xué)家P.Wegner指出，“在工業(yè)革命中其核心作用的是能量,而在計(jì)算機(jī)革命中其核心作用的是信息”.計(jì)算機(jī)科學(xué)就是“一種關(guān)于信息結(jié)構(gòu)轉(zhuǎn)換的科學(xué)”.信息結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)）是計(jì)算機(jī)科學(xué)研究的基本課題，數(shù)據(jù)結(jié)構(gòu)又是算法研究的基礎(chǔ)。2方案與論證2。1鏈表的概念和作用鏈表是一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，鏈表屬于線性表,采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，也是常用的動(dòng)態(tài)存儲(chǔ)方法。鏈表中的數(shù)據(jù)是以結(jié)點(diǎn)來(lái)表示的，每個(gè)結(jié)點(diǎn)的構(gòu)成:元素（數(shù)據(jù)元素的映象）+

指針(指示后繼元素存儲(chǔ)位置)，元素就是存儲(chǔ)數(shù)據(jù)的存儲(chǔ)單元,指針就是連接每個(gè)結(jié)點(diǎn)的地址數(shù)據(jù)。以“結(jié)點(diǎn)的序列”表示線性表稱作HYPERLINK”http：///view/2705992。htm”\t"_blank”線性鏈表（單鏈表)單鏈表是鏈?zhǔn)酱嫒〉慕Y(jié)構(gòu)，為找第i個(gè)數(shù)據(jù)元素，必須先找到第i-1個(gè)數(shù)據(jù)元素。因此，查找第i個(gè)數(shù)據(jù)元素的基本操作為:移動(dòng)指針，比較j和i單鏈表1、鏈接存儲(chǔ)方法鏈接方式存儲(chǔ)的線性表簡(jiǎn)稱為鏈表（LinkedList）。鏈表的具體存儲(chǔ)表示為：①用一組任意的HYPERLINK”http：///view/1223079。htm"\t"_blank”存儲(chǔ)單元來(lái)存放線性表的結(jié)點(diǎn)(這組存儲(chǔ)單元既可以是連續(xù)的，也可以是不連續(xù)的）②鏈表中結(jié)點(diǎn)的邏輯次序和物理次序不一定相同。為了能正確表示結(jié)點(diǎn)間的邏輯關(guān)系，在存儲(chǔ)每個(gè)結(jié)點(diǎn)值的同時(shí)，還必須存儲(chǔ)指示其后繼結(jié)點(diǎn)的地址(或位置）信息（稱為HYPERLINK”/view/159417.htm”\t”_blank”指針（pointer)或鏈（link)）注意：鏈?zhǔn)酱鎯?chǔ)是最常用的存儲(chǔ)方式之一，它不僅可用來(lái)表示線性表，而且可用來(lái)表示各種非線性的數(shù)據(jù)結(jié)構(gòu)。2、鏈表的結(jié)點(diǎn)結(jié)構(gòu)┌───┬───┐│data│next│└───┴───┘data域--存放結(jié)點(diǎn)值的數(shù)據(jù)域next域—-存放結(jié)點(diǎn)的直接后繼的地址（位置）的HYPERLINK”http：///view/159417.htm”指針域（鏈域）注意：①鏈表通過(guò)每個(gè)結(jié)點(diǎn)的鏈域?qū)⒕€性表的n個(gè)結(jié)點(diǎn)按其邏輯順序鏈接在一起的。②每個(gè)結(jié)點(diǎn)只有一個(gè)鏈域的鏈表稱為單鏈表（SingleLinkedList）。3、頭指針head和終端結(jié)點(diǎn)指針域的表示單鏈表中每個(gè)結(jié)點(diǎn)的存儲(chǔ)地址是存放在其前趨結(jié)點(diǎn)next域中,而開始結(jié)點(diǎn)無(wú)前趨，故應(yīng)設(shè)頭指針head指向開始結(jié)點(diǎn).注意：鏈表由頭HYPERLINK”http：///view/159417。htm”指針唯一確定，單鏈表可以用頭指針的名字來(lái)命名.終端結(jié)點(diǎn)無(wú)后繼，故終端結(jié)點(diǎn)的指針域?yàn)榭眨碞ULL。2。2實(shí)驗(yàn)的基本要求（軟硬件）用VC++6。0軟件平臺(tái)，操作系統(tǒng):WindowsXP硬件：內(nèi)存要求:內(nèi)存大小在256MB，其他配置一般就行。2。3算法的設(shè)計(jì)思想（a）定義一個(gè)創(chuàng)建鏈表的函數(shù)，通過(guò)該頭插法創(chuàng)建一個(gè)帶頭結(jié)點(diǎn)的鏈表，在接下來(lái)的鏈表操作中使用。(b）定義輸出鏈表的算法，遍歷結(jié)點(diǎn)的指針域判斷是否為空，如果不為空則輸出其數(shù)據(jù)域,直到指針域?yàn)榭諡橹埂＃╟）定義一個(gè)遍歷查找的算法，通過(guò)遍歷的數(shù)據(jù)域，分別與要查詢的元素進(jìn)行比較，如果查找到則返回并輸出，如入查找失敗則返回錯(cuò)誤提示信息。（d)定義插入結(jié)點(diǎn)的算法，首先查找指針域?yàn)榭盏慕Y(jié)點(diǎn)，并申請(qǐng)空間插入在結(jié)點(diǎn)的后邊，并且將其指針域置空。（e）定義刪除節(jié)點(diǎn)的操作，這個(gè)算法用于對(duì)鏈表中某個(gè)多余節(jié)點(diǎn)的刪除工作，其關(guān)鍵在于前驅(qū)結(jié)點(diǎn)的保留,查找到需刪除的結(jié)點(diǎn)，將其刪除,并將其后繼結(jié)點(diǎn)連到其前驅(qū)結(jié)點(diǎn).

2。4相關(guān)圖例2。4.1單鏈表的結(jié)點(diǎn)結(jié)構(gòu)如圖2—1所示，為單鏈表的結(jié)點(diǎn)結(jié)構(gòu)示意圖：Data域Next域Data域Next域圖2-1單鏈表的結(jié)點(diǎn)結(jié)構(gòu)2。4。2算法流程圖如圖2—2所示，為此算法流程圖：開始開始定義結(jié)構(gòu)體Node構(gòu)建各種對(duì)鏈表操作的函數(shù)（插入、刪除、查找、輸出），并寫出相應(yīng)的算法及實(shí)現(xiàn)過(guò)程定義結(jié)構(gòu)體Node構(gòu)建各種對(duì)鏈表操作的函數(shù)（插入、刪除、查找、輸出），并寫出相應(yīng)的算法及實(shí)現(xiàn)過(guò)程創(chuàng)建一個(gè)單鏈表，用于之前所定義的函數(shù)對(duì)其進(jìn)行操作按要求輸出結(jié)果結(jié)束圖2—2算法流程圖

3實(shí)驗(yàn)結(jié)果3.1鏈表的建立圖3—1鏈表的建立3。2單鏈表的插入圖3-2單鏈表的插入

3.3單鏈表的輸出圖3-3輸出單鏈表元素3.4查找元素圖3-4查找成功圖3-5查找失敗3.5單鏈表的刪除圖3—6刪除成功圖3-6刪除失敗3。6顯示鏈表中的元素個(gè)數(shù)（計(jì)數(shù)）圖3-7輸出長(zhǎng)度

4結(jié)果分析4。1單鏈表的結(jié)構(gòu)一般情況下,使用鏈表，只關(guān)心鏈表中結(jié)點(diǎn)間的邏輯順序,并不關(guān)心每個(gè)結(jié)點(diǎn)的實(shí)際存儲(chǔ)位置，因此通常情況下用箭頭來(lái)表示鏈域中的指針，于是鏈表就可以更直觀的畫成用箭頭鏈接起來(lái)的結(jié)點(diǎn)序列，如下圖所示：ABABCDE^H圖4—1單鏈表的示例圖4.2單鏈表的操作特點(diǎn)4.2.1順鏈操作技術(shù)從“頭"開始，訪問單鏈表L中的結(jié)點(diǎn)i(p指向該節(jié)點(diǎn))時(shí)，由于第i個(gè)結(jié)點(diǎn)的地址在第i—1個(gè)結(jié)點(diǎn)(pre指向該結(jié)點(diǎn)，為p的前驅(qū)）的指針域中存放，查找必須從單鏈表的“首結(jié)點(diǎn)”開始（p=L)；通過(guò)p=p-〉next并輔助計(jì)數(shù)器來(lái)實(shí)現(xiàn)。4。2。2指針保留技術(shù)通過(guò)對(duì)第i個(gè)結(jié)點(diǎn)進(jìn)行插入、刪除等操作時(shí)，需要對(duì)第i-1個(gè)結(jié)點(diǎn)的指針域進(jìn)行鏈址操作（pre-〉next)，因此在處理過(guò)程中始終需要維持當(dāng)前指針p與其前驅(qū)指針pre的關(guān)系，將這種技術(shù)稱為“指針保留技術(shù)".4.3鏈表處理中的相關(guān)技術(shù)1)單鏈表與多重鏈表的差別在于指針域的個(gè)數(shù)。2）判斷當(dāng)前結(jié)點(diǎn)p是否為表尾。一半鏈表中，p結(jié)點(diǎn)是表尾的條件是：該節(jié)點(diǎn)的后繼結(jié)點(diǎn)為空指針，即p->next==NULL;3)鏈表的長(zhǎng)度并未顯示保存.由于鏈表是動(dòng)態(tài)生成的結(jié)構(gòu)，其長(zhǎng)度要通過(guò)順鏈查找到表尾得到。因此在處理鏈表時(shí)，往往是以當(dāng)前處理結(jié)點(diǎn)p是否為表尾作為控制條件，而不是長(zhǎng)度n作為控制條件。5設(shè)計(jì)體會(huì)及今后的改進(jìn)意見通過(guò)這次實(shí)驗(yàn)加深了我對(duì)于單鏈表的進(jìn)一步了解,了解到了單鏈表在內(nèi)存中的存儲(chǔ)結(jié)構(gòu)，最重要的是學(xué)會(huì)了如何運(yùn)用C語(yǔ)言將單鏈表的建立，插入、刪除、添加等操作.在程序?qū)崿F(xiàn)中也遇到了一些困難，在單鏈表初始化時(shí)，使用了0作為結(jié)束輸入符，導(dǎo)致單鏈表不能存儲(chǔ)數(shù)據(jù)0；單鏈表中只能存儲(chǔ)相同類型的數(shù)據(jù)，在存儲(chǔ)不同類型的數(shù)據(jù)時(shí)需要改變輸入結(jié)束標(biāo)志，程序通用性比較差。在進(jìn)行程序設(shè)計(jì)的時(shí)候沒有考慮好刪除和查找的方式,只進(jìn)行了輸入元素的查找和刪除,而且進(jìn)行鏈表的插入時(shí)，只考慮了頭插法在結(jié)尾插入，而沒有考慮輸入結(jié)點(diǎn)插入等,程序的靈活性比較低。通過(guò)這次課程設(shè)計(jì)，讓我充分認(rèn)識(shí)到數(shù)據(jù)結(jié)構(gòu)在編寫程序方面的重要地位。不僅僅是單鏈表的操作,還有棧和隊(duì)列等特殊的單鏈表操作，以及其他一些常用的數(shù)據(jù)結(jié)構(gòu)對(duì)于程序的效率和內(nèi)存使用有很大的幫助。我希望在接下來(lái)的學(xué)習(xí)中收獲更多的東西.

參考文獻(xiàn)[1]耿國(guó)華.數(shù)據(jù)結(jié)構(gòu)--用C語(yǔ)言描述［M]。北京:高等教育出版社，2011。6。［2]譚浩強(qiáng)。C程序設(shè)計(jì)[M]。北京:清華大學(xué)出版社,2004。6。附錄代碼:結(jié)構(gòu)體定義：#pragmaonce＃include〈stdio。h>#include〈stdlib.h>enummy_enum{ _EXIT， _CREATE, _INSERT， _PRINT, _SEARCH, _DELETE， _COUNT,}；staticintcount=0；typedefintElemtype；typedefstructNode/*單鏈表結(jié)構(gòu)體的定義*/｛ Elemtypedata; structNode*next;}Node,＊LinkList;voidtest（)；/*測(cè)試函數(shù)＊/voidmain_menu（);//主菜單函數(shù)voidCreatFromHead(LinkList*l);/*頭插法建立單鏈表＊/voidInsert（LinkListl);//單鏈表的插入voidPrint(LinkListl);/*單鏈表的輸出＊/intSearch（LinkListl，Elemtypee);//查找指定的元素voidDeletelist(LinkListl，Elemtypee）；//刪除元素voidCount()；//計(jì)數(shù)voidCREATE（LinkList＊head)；voidINSERT（LinkList*head）；voidPRINT（LinkList＊head）;voidSEARCH(LinkList*head)；voidDELET(LinkList*head);voidCOUNT（）；

單鏈表操作函數(shù):＃define_CRT_SECURE_NO_WARNINGS#include"linklist。h”voidmain_menu(){ printf（”\t單鏈表的簡(jiǎn)單操作\t\t\n\n”); printf(”\t1單鏈表的建立\n"）； printf（”\t2單鏈表的插入\n"）； printf(”\t3單鏈表的輸出\n”); printf（"\t4單鏈表的查找\n"）； printf("\t5單鏈表的刪除\n”)； printf（"\t6單鏈表的長(zhǎng)度\n”)； printf（"\t0退出\n”)；｝voidCreatFromHead（LinkList*l）/*頭插法建立單鏈表＊/｛ Node＊s; intc=0； intflag=1; *l=(Node＊）malloc(sizeof(Node））; if（*l==NULL） ｛ printf（”申請(qǐng)空間失敗！！\n"); return; } （*l)—〉next=NULL; while（flag） ｛ scanf(”%d",&c）; if（c！=0) ｛ s=(Node*)malloc(sizeof(Node）); if（s==NULL) { printf（”申請(qǐng)空間失敗！！\n")； return; } s—〉data=c; s—>next=(＊l)—〉next； (*l)—>next=s; count++; } elseflag=0； }}voidInsert(LinkListl)//單鏈表的插入{ intinsert=0; Node＊s=NULL; printf(”請(qǐng)輸入需要插入的元素："）; scanf("％d",＆insert); s=（Node＊）malloc(sizeof(Node））; if（s==NULL） ｛ printf（"申請(qǐng)空間失敗！！\n”）； return； ｝ while(l—〉next！=NULL) { l=l-〉next； } s->data=insert; s—〉next=l—>next; l—>next=s； count++；｝voidPrint（LinkListl)/＊單鏈表的遍歷*/{ Node*p; p=l—〉next； while(p!=NULL) { printf("%d"，p->data）; p=p—>next; } printf("\n");}intSearch(LinkListl,Elemtypee）//查找指定的元素｛ while((l！=NULL)＆&（l—〉data！=e）） { l=l-〉next; } if(l==NULL) ｛ return—1；//查找失敗 } else { return1；//查找成功 }｝voidDeletelist（LinkListl，Elemtypee）//刪除節(jié)點(diǎn)｛ Node＊p，*r，＊q； p=l—>next;q=l; while（p！=NULL） ｛ if（p-〉data==e） { r=p； p=r-〉next； q—>next=p; count—-； free(r)； break; ｝ else ｛ q=p;/＊保留前驅(qū)節(jié)點(diǎn)＊/ p=p—〉next； } } if（p==NULL) { printf("刪除失敗，沒有找到相應(yīng)的元素\n"); }｝voidCount（){ printf（”單鏈表中一共有%d個(gè)元素\n”，count）；}voidCREATE(LinkList*head){ printf（”請(qǐng)建立單鏈表用“0"來(lái)結(jié)束輸入\n”）; CreatFromHead（head）; printf（"初始化后的單鏈表為:”）； Print(＊head)；｝voidINSERT（LinkList*head）{ Insert(＊head)； printf(”插入后的單鏈表為："）; Print（＊head);｝voidPRINT(LinkList*head){ printf（"單鏈表的輸出為：”）； Print（*head);}voidSEARCH（LinkList*head）｛ intsearch=0； intret=0; printf（”請(qǐng)輸入需要查找的元素："）; scanf(”％d",&search); ret=Search（*head，search); if(1==ret） { printf（"查找成功\n"）; ｝ else ｛ printf(”查找失敗\n”)； }｝voidDELET(LinkList*head)｛ intdelet=0; printf（”請(qǐng)輸入需要?jiǎng)h除的元素："）; scanf("%d”，