數(shù)據(jù)結構課程設計-單鏈表

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

2、個“一”：開辟一個新時代-信息時代，形成一個新產(chǎn)業(yè)-信息產(chǎn)業(yè)，產(chǎn)生一個新科學-計算機科學與技術，開創(chuàng)一種新的科研方法-計算方法，開辟一種新文化-計算機文化，這一概括深刻影響了計算機對社會發(fā)展所產(chǎn)生的廣泛而深遠的影響。數(shù)據(jù)結構和算法是計算機求解問題過程的兩大基石。著名的計算機科學家P.Wegner指出，“在工業(yè)革命中其核心作用的是能量，而在計算機革命中其核心作用的是信息”。計算機科學就是“一種關于信息結構轉換的科學”。信息結構（數(shù)據(jù)結構）是計算機科學研究的基本課題，數(shù)據(jù)結構又是算法研究的基礎。2 方案與論證2.1 鏈表的概念和作用 鏈表是一種鏈式存儲結構，鏈表屬于線性表，采用鏈式存儲結構，也是常

3、用的動態(tài)存儲方法。鏈表中的數(shù)據(jù)是以結點來表示的，每個結點的構成：元素(數(shù)據(jù)元素的映象) + 指針(指示后繼元素存儲位置)，元素就是存儲數(shù)據(jù)的存儲單元，指針就是連接每個結點的地址數(shù)據(jù)。以“結點的序列”表示線性表稱作線性鏈表（單鏈表）單鏈表是鏈式存取的結構，為找第 i 個數(shù)據(jù)元素，必須先找到第 i-1 個數(shù)據(jù)元素。因此，查找第 i 個數(shù)據(jù)元素的基本操作為：移動指針，比較 j 和 i單鏈表1、鏈接存儲方法鏈接方式存儲的線性表簡稱為鏈表（Linked List）。鏈表的具體存儲表示為： 用一組任意的存儲單元來存放線性表的結點（這組存儲單元既可以是連續(xù)的，也可以是不連續(xù)的） 鏈表中結點的邏輯次

4、序和物理次序不一定相同。為了能正確表示結點間的邏輯關系，在存儲每個結點值的同時，還必須存儲指示其后繼結點的地址（或位置）信息（稱為指針（pointer）或鏈(link)）注意：鏈式存儲是最常用的存儲方式之一，它不僅可用來表示線性表，而且可用來表示各種非線性的數(shù)據(jù)結構。2、鏈表的結點結構data next data域-存放結點值的數(shù)據(jù)域next域-存放結點的直接后繼的地址（位置）的指針域（鏈域）注意：鏈表通過每個結點的鏈域?qū)⒕€性表的n個結點按其邏輯順序鏈接在一起的。每個結點只有一個鏈域的鏈表稱為單鏈表（Single Linked List）。3、頭指針head和終端結點指針域的表示單鏈表中每個結

5、點的存儲地址是存放在其前趨結點next域中，而開始結點無前趨，故應設頭指針head指向開始結點。注意：鏈表由頭指針唯一確定，單鏈表可以用頭指針的名字來命名。終端結點無后繼，故終端結點的指針域為空，即NULL。2.2 實驗的基本要求（軟硬件） 用VC+6.0軟件平臺，操作系統(tǒng)：Windows XP 硬件：內(nèi)存要求：內(nèi)存大小在256MB，其他配置一般就行。 2.3 算法的設計思想（a）定義一個創(chuàng)建鏈表的函數(shù)，通過該頭插法創(chuàng)建一個帶頭結點的鏈表，在接下來的鏈表操作中使用。（b）定義輸出鏈表的算法 ，遍歷結點的指針域判斷是否為空，如果不為空則輸出其數(shù)據(jù)域，直到指針域為空為止。（c）定義一個遍歷查找的算

6、法，通過遍歷的數(shù)據(jù)域，分別與要查詢的元素進行比較，如果查找到則返回并輸出，如入查找失敗則返回錯誤提示信息。（d）定義插入結點的算法，首先查找指針域為空的結點，并申請空間插入在結點的后邊，并且將其指針域置空。 （e）定義刪除節(jié)點的操作，這個算法用于對鏈表中某個多余節(jié)點的刪除工作，其關鍵在于前驅(qū)結點的保留，查找到需刪除的結點，將其刪除，并將其后繼結點連到其前驅(qū)結點。2.4 相關圖例2.4.1 單鏈表的結點結構 如圖2-1所示,為單鏈表的結點結構示意圖：Data域 Next域 圖2-1 單鏈表的結點結構2.4.2 算法流程圖 如圖2-2所示，為此算法流程圖： 開始定義結構體Node構建各種對鏈表操作

7、的函數(shù)（插入、刪除、查找、輸出），并寫出相應的算法及實現(xiàn)過程創(chuàng)建一個單鏈表，用于之前所定義的函數(shù)對其進行操作按要求輸出結果結束 圖2-2 算法流程圖3 實驗結果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 顯示鏈表中的元素個數(shù)（計數(shù)）圖3-7輸出長度4 結果分析4.1 單鏈表的結構 一般情況下，使用鏈表，只關心鏈表中結點間的邏輯順序，并不關心每個結點的實際存儲位置，因此通常情況下用箭頭來表示鏈域中的指針

8、，于是鏈表就可以更直觀的畫成用箭頭鏈接起來的結點序列，如下圖所示：ABCDE H圖4-1 單鏈表的示例圖4.2 單鏈表的操作特點 4.2.1 順鏈操作技術 從“頭”開始，訪問單鏈表L中的結點i（p指向該節(jié)點）時，由于第i個結點的地址在第i-1個結點（pre指向該結點，為p的前驅(qū)）的指針域中存放，查找必須從單鏈表的“首結點”開始（p=L）；通過p=p->next并輔助計數(shù)器來實現(xiàn)。4.2.2 指針保留技術 通過對第i個結點進行插入、刪除等操作時，需要對第i-1個結點的指針域進行鏈址操作（pre->next），因此在處理過程中始終需要維持當前指針p與其前驅(qū)指針pre的關系，將這種技術稱

9、為“指針保留技術”。4.3 鏈表處理中的相關技術1）單鏈表與多重鏈表的差別在于指針域的個數(shù)。2）判斷當前結點p是否為表尾。一半鏈表中，p結點是表尾的條件是：該節(jié)點的后繼結點為空指針，即p->next=NULL;3）鏈表的長度并未顯示保存。由于鏈表是動態(tài)生成的結構，其長度要通過順鏈查找到表尾得到。因此在處理鏈表時，往往是以當前處理結點p是否為表尾作為控制條件，而不是長度n作為控制條件。5 設計體會及今后的改進意見通過這次實驗加深了我對于單鏈表的進一步了解，了解到了單鏈表在內(nèi)存中的存儲結構，最重要的是學會了如何運用C語言將單鏈表的建立，插入、刪除、添加等操作。在程序?qū)崿F(xiàn)中也遇到了一些困難，在

10、單鏈表初始化時，使用了0作為結束輸入符，導致單鏈表不能存儲數(shù)據(jù)0；單鏈表中只能存儲相同類型的數(shù)據(jù)，在存儲不同類型的數(shù)據(jù)時需要改變輸入結束標志，程序通用性比較差。在進行程序設計的時候沒有考慮好刪除和查找的方式，只進行了輸入元素的查找和刪除，而且進行鏈表的插入時，只考慮了頭插法在結尾插入，而沒有考慮輸入結點插入等，程序的靈活性比較低。通過這次課程設計，讓我充分認識到數(shù)據(jù)結構在編寫程序方面的重要地位。不僅僅是單鏈表的操作，還有棧和隊列等特殊的單鏈表操作，以及其他一些常用的數(shù)據(jù)結構對于程序的效率和內(nèi)存使用有很大的幫助。我希望在接下來的學習中收獲更多的東西。參考文獻1耿國華.數(shù)據(jù)結構-用C語言描述M.北

11、京:高等教育出版社,2011.6.2譚浩強.C程序設計M.北京:清華大學出版社,2004.6.附錄代碼：結構體定義：#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/*單鏈表結構體的定義*/Elemtype data;struct Node *next;Node, *LinkL

12、ist;void test();/*測試函數(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();/計數(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 單鏈表的簡單操作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 單鏈表的長度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("申請空間失?。");

15、return;(*l)->next = NULL;while (flag)scanf("%d", &c);if (c != 0)s = (Node*)malloc(sizeof(Node);if (s = NULL)printf("申請空間失??！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("請輸入需要插入的元素：");scanf("%d", &insert);s = (Node*)malloc(sizeof(Node);if (s = NULL)printf("申請空間失敗！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é)點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é)點*/p = p->next;if (p = NULL)printf("刪除失敗，沒有找到相應的元素n");void Count()printf("單鏈表中一共有%d個元素n", count);void CREATE(LinkList *head)printf(&qu

19、ot;請建立單鏈表用“0”來結束輸入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("請輸入需要查找的元素：");scanf("%d", &search);ret = Search(*head, search);if (1 = ret)printf("查找成功n");elseprintf("查找失敗n");void DELET(LinkList *head)int delet = 0;printf("請輸入需要刪除的元