數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-單鏈表

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)目 錄1 選題背景22 方案與論證32.1 鏈表的概念和作用32.3 算法的設(shè)計(jì)思想42.4 相關(guān)圖例52.4.1 單鏈表的結(jié)點(diǎn)結(jié)構(gòu)52.4.2 算法流程圖53 實(shí)驗(yàn)結(jié)果63.1 鏈表的建立63.2 單鏈表的插入63.3 單鏈表的輸出73.4 查找元素73.5 單鏈表的刪除83.6 顯示鏈表中的元素個(gè)數(shù)（計(jì)數(shù)）94 結(jié)果分析104.1 單鏈表的結(jié)構(gòu)104.2 單鏈表的操作特點(diǎn)104.2.1 順鏈操作技術(shù)104.2.2 指針保留技術(shù)104.3 鏈表處理中的相關(guān)技術(shù)105 設(shè)計(jì)體會(huì)及今后的改進(jìn)意見(jiàn)11參考文獻(xiàn)12附錄代碼：131 選題背景陳火旺院士把計(jì)算機(jī)60多年的發(fā)展成就概括為五

2、個(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ī)求解問(wèn)題過(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)，也是常

3、用的動(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)的序列”表示線性表稱作線性鏈表（單鏈表）單鏈表是鏈?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)稱為鏈表（Linked List）。鏈表的具體存儲(chǔ)表示為： 用一組任意的存儲(chǔ)單元來(lái)存放線性表的結(jié)點(diǎn)（這組存儲(chǔ)單元既可以是連續(xù)的，也可以是不連續(xù)的） 鏈表中結(jié)點(diǎn)的邏輯次

4、序和物理次序不一定相同。為了能正確表示結(jié)點(diǎn)間的邏輯關(guān)系，在存儲(chǔ)每個(gè)結(jié)點(diǎn)值的同時(shí)，還必須存儲(chǔ)指示其后繼結(jié)點(diǎn)的地址（或位置）信息（稱為指針（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)的直接后繼的地址（位置）的指針域（鏈域）注意：鏈表通過(guò)每個(gè)結(jié)點(diǎn)的鏈域?qū)⒕€性表的n個(gè)結(jié)點(diǎn)按其邏輯順序鏈接在一起的。每個(gè)結(jié)點(diǎn)只有一個(gè)鏈域的鏈表稱為單鏈表（Single Linked List）。3、頭指針head和終端結(jié)點(diǎn)指針域的表示單鏈表中每個(gè)結(jié)

5、點(diǎn)的存儲(chǔ)地址是存放在其前趨結(jié)點(diǎn)next域中，而開始結(jié)點(diǎn)無(wú)前趨，故應(yīng)設(shè)頭指針head指向開始結(jié)點(diǎn)。注意：鏈表由頭指針唯一確定，單鏈表可以用頭指針的名字來(lái)命名。終端結(jié)點(diǎn)無(wú)后繼，故終端結(jié)點(diǎn)的指針域?yàn)榭眨碞ULL。2.2 實(shí)驗(yàn)的基本要求（軟硬件） 用VC+6.0軟件平臺(tái)，操作系統(tǒng)：Windows XP 硬件：內(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è)遍歷查找的算

6、法，通過(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域 圖2-1 單鏈表的結(jié)點(diǎn)結(jié)構(gòu)2.4.2 算法流程圖 如圖2-2所示，為此算法流程圖： 開始定義結(jié)構(gòu)體Node構(gòu)建各種對(duì)鏈表操作

7、的函數(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)表示鏈域中的指針

8、，于是鏈表就可以更直觀的畫成用箭頭鏈接起來(lái)的結(jié)點(diǎn)序列，如下圖所示：ABCDE H圖4-1 單鏈表的示例圖4.2 單鏈表的操作特點(diǎn) 4.2.1 順鏈操作技術(shù) 從“頭”開始，訪問(wèn)單鏈表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ù)稱

9、為“指針保留技術(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)意見(jiàn)通過(guò)這次實(shí)驗(yàn)加深了我對(duì)于單鏈表的進(jìn)一步了解，了解到了單鏈表在內(nèi)存中的存儲(chǔ)結(jié)構(gòu)，最重要的是學(xué)會(huì)了如何運(yùn)用C語(yǔ)言將單鏈表的建立，插入、刪除、添加等操作。在程序?qū)崿F(xiàn)中也遇到了一些困難，在

10、單鏈表初始化時(shí)，使用了0作為結(jié)束輸入符，導(dǎo)致單鏈表不能存儲(chǔ)數(shù)據(jù)0；單鏈表中只能存儲(chǔ)相同類型的數(shù)據(jù)，在存儲(chǔ)不同類型的數(shù)據(jù)時(shí)需要改變輸入結(jié)束標(biāo)志，程序通用性比較差。在進(jìn)行程序設(shè)計(jì)的時(shí)候沒(méi)有考慮好刪除和查找的方式，只進(jìn)行了輸入元素的查找和刪除，而且進(jìn)行鏈表的插入時(shí)，只考慮了頭插法在結(jié)尾插入，而沒(méi)有考慮輸入結(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.北

11、京:高等教育出版社,2011.6.2譚浩強(qiáng).C程序設(shè)計(jì)M.北京:清華大學(xué)出版社,2004.6.附錄代碼：結(jié)構(gòu)體定義：#pragma once#include<stdio.h>#include<stdlib.h>enum my_enum_EXIT,_CREATE,_INSERT,_PRINT,_SEARCH,_DELETE,_COUNT,;static int count = 0;typedef int Elemtype;typedef struct Node/*單鏈表結(jié)構(gòu)體的定義*/Elemtype data;struct Node *next;Node, *LinkL

12、ist;void test();/*測(cè)試函數(shù)*/void main_menu();/主菜單函數(shù)void CreatFromHead(LinkList *l);/*頭插法建立單鏈表*/void Insert(LinkList l);/單鏈表的插入void Print(LinkList l);/*單鏈表的輸出*/int Search(LinkList l, Elemtype e);/查找指定的元素void Deletelist(LinkList l, Elemtype e);/刪除元素void Count();/計(jì)數(shù)void CREATE(LinkList *head);void INSERT(L

13、inkList *head);void PRINT(LinkList *head);void SEARCH(LinkList* head);void DELET(LinkList *head);void COUNT();單鏈表操作函數(shù)：#define _CRT_SECURE_NO_WARNINGS#include "linklist.h"void main_menu()printf("t 單鏈表的簡(jiǎn)單操作ttnn");printf("t 1 單鏈表的建立n");printf("t 2 單鏈表的插入n");print

14、f("t 3 單鏈表的輸出n");printf("t 4 單鏈表的查找n");printf("t 5 單鏈表的刪除n");printf("t 6 單鏈表的長(zhǎng)度n");printf("t 0 退出n");void CreatFromHead(LinkList *l)/*頭插法建立單鏈表*/Node *s;int c = 0;int flag = 1;*l = (Node*)malloc(sizeof(Node);if (*l = NULL)printf("申請(qǐng)空間失??！n");

15、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+;else flag = 0;void Insert(LinkList l)/單鏈表的插入int insert = 0;Node * s = NU

16、LL;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+;void Print(LinkList l)/*單鏈表的遍歷*/Node *p;p =

17、 l->next;while (p != NULL)printf("%d ", p->data);p = p->next;printf("n");int Search(LinkList l, Elemtype e)/查找指定的元素while (l != NULL) && (l->data != e)l = l->next;if (l = NULL)return -1;/查找失敗elsereturn 1;/查找成功void Deletelist(LinkList l, Elemtype e)/刪除節(jié)點(diǎn)Node

18、*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;elseq = p;/*保留前驅(qū)節(jié)點(diǎn)*/p = p->next;if (p = NULL)printf("刪除失敗，沒(méi)有找到相應(yīng)的元素n");void Count()printf("單鏈表中一共有%d個(gè)元素n", count);void CREATE(LinkList *head)printf(&qu

19、ot;請(qǐng)建立單鏈表用“0”來(lái)結(jié)束輸入n");CreatFromHead(head);printf("初始化后的單鏈表為：");Print(*head);void INSERT(LinkList *head)Insert(*head);printf("插入后的單鏈表為：");Print(*head);void PRINT(LinkList *head)printf("單鏈表的輸出為：");Print(*head);void SEARCH(LinkList *head)int search = 0;int ret = 0;printf("請(qǐng)輸入需要查找的元素：");scanf("%d", &search);ret = Search(*head, search);if (1 = ret)printf("查找成功n");elseprintf("查找失敗n");void DELET(LinkList *head)int delet = 0;printf("請(qǐng)輸入需要?jiǎng)h除的元