鄭州科技學院
數據結構課程設計
設計題目:單鏈表的基本算法應用
所在院系: 信息工程學院
專業班級:16級計算機科學與技術3班
學生姓名:黃 桂 亞
學 號: 201642304696
指導教師:李 瑞 霞
2018年3月13號
目錄
l 單鏈表的簡介
l 課題題目要求
l 需求分析
l 概要設計
l 詳細設計
l 調試分析
l 測試結果
l 總結思考
l 附件
一、單鏈表的簡介
鏈表中的數據是以結點來表示的，每個結點的構成:元素(數據元素的映象) + 指針(指示后繼元素存儲位置)，元素就是存儲數據的存儲單元，指針就是連接每個結點的地址數據。
以"結點的序列"表示線性表稱作線性鏈表(單鏈表)
單鏈表是鏈式存取的結構，為找第 i 個數據元素，必須先找到第 i-1 個數據元素。
因此，查找第 i 個數據元素的基本操作為:移動指針，比較 j 和 i
1、鏈接存儲方法
鏈接方式存儲的線性表簡稱為鏈表(Linked List)。
鏈表的具體存儲表示為:
① 用一組任意的存儲單元來存放線性表的結點(這組存儲單元既可以是連續的，也可以是不連續的)
② 鏈表中結點的邏輯次序和物理次序不一定相同。為了能正確表示結點間的邏輯關系，在存儲每個結點值的同時，還必須存儲指示其后繼結點的地址(或位置)信息(稱為指針(pointer)或鏈(link))
注意:
鏈式存儲是最常用的存儲方式之一，它不僅可用來表示線性表，而且可用來表示各種非線性的數據結構。
2、鏈表的結點結構
┌───┬───┐
│data │ next│
└───┴───┘
data域--存放結點值的數據域
next域--存放結點的直接后繼的地址(位置)的指針域(鏈域)
注意:
①鏈表通過每個結點的鏈域將線性表的n個結點按其邏輯順序鏈接在一起的。
②每個結點只有一個鏈域的鏈表稱為單鏈表(Single Linked List)。
【例】線性表(bat，cat，eat，fat，hat，jat，lat，mat)的單鏈表示如示意圖
3、頭指針head和終端結點指針域的表示
單鏈表中每個結點的存儲地址是存放在其前趨結點next域中，而開始結點無前趨，故應設頭指針head指向開始結點。
注意:
鏈表由頭指針唯一確定，單鏈表可以用頭指針的名字來命名。
終端結點無后繼，故終端結點的指針域為空，即NULL。
4、單鏈表的一般圖示法
由于我們常常只注重結點間的邏輯順序，不關心每個結點的實際位置，可以用箭頭來表示鏈域中的指針，線性表(bat，cat，fat，hat，jat，lat，mat)的單鏈表就可以表示為下圖形式。
5、單鏈表類型描述
typedef char DataType; //假設結點的數據域類型為字符
typedef struct node{ //結點類型定義
DataType data; //結點的數據域
struct node *next;//結點的指針域
}ListNode;
typedef ListNode *LinkList;
ListNode *p;
LinkList head;
6、指針變量和結點變量
①生成結點變量的標準函數
p=( ListNode *)malloc(sizeof(ListNode));
//函數malloc分配一個類型為ListNode的結點變量的空間,并將其首地址放入指針變量p中
②釋放結點變量空間的標準函數
free(p);//釋放p所指的結點變量空間
③結點分量的訪問
利用結點變量的名字*p訪問結點分量
方法一:(*p).data和(*p).next
方法二:p->data和p->next
④指針變量p和結點變量*p的關系
指針變量p的值--結點地址
結點變量*p的值--結點內容
(*p).data的值--p指針所指結點的data域的值
(*p).next的值--*p后繼結點的地址
*((*p).next)--*p后繼結點
鏈表操作中動態存儲分配要使用標準函數，先介紹一下這些函數。
(1)malloc(size)
在內存的動態存儲區申請一個長度為size字節的連續空間。
(2)calloc(n，size)
在內存的動態存儲區申請n個長度為size字節的連續空間，函數返回值為分配空間的首地址。若此函數未被成功執行，函數返回值為0。
(3)free(p)
釋放由指針p所指向的存儲單元，而存儲單元的大小是最近一次調用malloc()或calloc()函數時所申請的存儲空間。
在頭文件\"stdlib.h"中包含了這些函數的信息，使用這些函數時需在程序開頭用文件包含指令#include"stdlib.h"指明。
另請讀者注意，調用動態存儲分配函數返回的指針是指向void類型或char類型的指針，在具體使用時，要根據所指向的數據進行強制類型轉換。
單鏈表的建立有頭插法、尾插法兩種方法。
1.頭插法
單鏈表是用戶不斷申請存儲單元和改變鏈接關系而得到的一種特殊數據結構，將鏈表的左邊稱為鏈頭，右邊稱為鏈尾。頭插法建單鏈表是將鏈表右端看成固定的，鏈表不斷向左延伸而得到的。頭插法最先得到的是尾結點。
由于鏈表的長度是隨機的，故用一個while循環來控制鏈表中結點個數。假設每個結點的值都大于O，則循環條件為輸入的值大于o。申請存儲空間可使用malloc()函數實現，需設立一申請單元指針，但malloc()函數得到的指針并不是指向結構體的指針，需使用強制類型轉換，將其轉換成結構體型指針。剛開始時，鏈表還沒建立，是一空鏈表，head指針為NULL。
鏈表建立的過程是申請空間、得到數據、建立鏈接的循環處理過程。
2.尾插法
若將鏈表的左端固定，鏈表不斷向右延伸，這種建立鏈表的方法稱為尾插法。尾插法建立鏈表時，頭指針固定不動，故必須設立一個搜索指針，向鏈表右邊延伸，則整個算法中應設立三個鏈表指針，即頭指針head、搜索指針p2、申請單元指針pl。尾插法最先得到的是頭結點。
二、課題題目要求
（1）編寫一個程序，實現單鏈表的各種基本運算.
（2）編輯平臺選用MicrosoftVisual++6.0
（3）在設計過程中，按功能定義函數或書寫多個文件，進行板塊設計，各個功能模塊用函數的形式實現。
三、需求分析
建立一個單鏈表，實現單鏈表的初始化，插入，輸出等功能，以確定某個元素在單鏈表中的位置
（1）初始化單鏈表L；
（2）依次采用尾插法插入a,b,c,d,e元素；
（3）輸出單鏈表L；
（4）輸出單鏈表L的長度；
（5）判斷單鏈表L是否為空；
（6）輸出單鏈表L的第3個元素；
（7）輸出元素a的位置；
（8）在第4個元素位置上插入f元素；
（9）輸出單鏈表L；
函數的調用關系
四、概要設計
（1）為了實現上述程序功能，需要定義一個簡化的線性表抽象數據類型：
ADT LinearList {
數據對象：D={i|ai∈IntegerSet,i=0,1,2,…,n,n≥0}
結構關系：R={<ai,ai+1>|ai,ai+1 ∈D}
基本操作：InitList_L(L)
操作前提：L是一個未初始化的線性表
操作結果：將L初始化為一個空的線性表
CreateList_L(L)
操作前提：L是一個已初始化的空表
操作結果：建立一個非空的線性表L
ListInsert_L(L,pos,e)
操作前提：線性表L已存在
操作結果：將元素e插入到線性表L的pos位置
ListDelete_L(L,pos,e)
操作前提：線性表L已存在
操作結果：將線性表L中pos位置的元素刪除，
刪除的元素值通過e返回
LocateList_L(L,e)
操作前提：線性表L已存在
操作結果：在線性表L中查找元素e，
若存在，返回元素在表中的序號位置；
若不存在，返回-1
DestroyList_L(&L)
初始條件：線性表L已存在
操作結果：銷毀線性表
ListEmpty_L(L)
初始條件：線性表已存在
操作結果：若L為空表，則返回ERROR，否則返回FALSE
ListLength_L(L)
初始條件：線性表L已存在
操作結果：返回L中數據元素個數
GetElem_L(L,I,&e)
初始條件：線性表L已存在
操作結果：用e返回L中第i個數據元素值
}
（2） 本程序包含10個函數：
• 主函數main()
• 初始化單鏈表函數InitList_L()
• 顯示單鏈表內容函數DispList_L()
• 插入元素函數ListInsert_L()
• 刪除元素函數ListDelete_L()
• 查找元素函數LocateList_L()
• 創建鏈表函數CreateList_L()
• 鏈表元素長度函數ListLength_L()
• 判斷鏈表是否為空函數ListEmpty_L()
• 取值函數GetElem_L()
各函數間調用關系如下：
( 3) 主函數的偽碼
{ 說明一個單鏈表 L ；
初始化 L ；
建立L ；
顯示L ；
}
五、詳細設計
采用單鏈表實現概要設計中定義的抽象數據類型，有關的數據類型和偽碼算法定義如下：
（1） 類型定義
typedef int ElemType;
typedef struct LNode
{ ElemType data; //數據域
struct LNode *next; //指針域
} LNode,* LinkList;
（2） 基本操作的偽碼算法
● 初始化
Bool InitLinkList(LinkList *L)
{ *L=申請新結點;
如果申請失敗，返回失敗標志；
(*L)->next=NULL;
返回成功標志；
}
● 建立單鏈表
Bool CrtLinkList(LinkList L)
/* L是已經初始化好的空鏈表的頭指針，通過鍵盤輸入元素值，
利用尾插法建單鏈表L */
{ rear=L;
打印輸入提示：“請輸入若干個正整數（用空格分隔），并用 -1 結束：”
讀入一個數x;
當x不是結束標志時，循環做如下處理：
{
申請一個新結點s；
如果申請失敗，返回失敗標志；
將x送到s的data域;
rear->next=s;
rear=s;
讀入下一個數x;
}
rear->next=NULL;
返回成功標志；
}
● 顯示單鏈表（輸出）
void DispLinkList(LinkList L)
{
p=首元素結點地址;
while ( p不空 )
{
打印結點p 的元素值；
p=下一個結點地址;
}
}
● 插入操作
bool InsLinkList(LinkList L, intpos, ElemType e)
/*在帶頭結點的單鏈表L中第pos個位置插入值為e的新結點s*/
{
從“頭”開始，查找第i-1個結點 pre ;
if (查找失敗)
{ 顯示參數錯誤信息;
return ERROR;
}
else
{
申請一個新的結點s ;
將e放入s的數據域;
將s 插到pre 后面;
return OK;
}● 查找操作
int LocLinkList(LinkList L, ElemType e)
/ * 在帶頭結點的單鏈表L中查找其結點值等于e的結點，
若找到則返回該結點的序號位置k，否則返回 -1 */
{
p=首元素結點地址;
while ( p不空 )
if (p->data!=e)
{ p=p->next; k++; }
else break;
if ( p 不空 ) return k;
else return -1;
}
六、調試分析
開始運行時會出現Debug Error，DAMAGE:After Normal block， 搜索后了解到是內存越界操作，檢查后發現內存分配L和S=(LinkList)malloc(sizeof(LNode))寫成了=(LinkList)malloc(sizeof(LinkList))，修改后正常。
七、測試結果
I=4插入元素f
八、總結思考
1、LinkList和ListNode是不同名字的同一個指針類型(命名的不同是為了概念上更明確)
2、*LinkList類型的指針變量head表示它是單鏈表的頭指針
3、ListNode類型的指針變量p表示它是指向某一結點的指針
4、若指針變量p的值為空(NULL)，則它不指向任何結點。此時，若通過*p來訪問結點就意味著訪問一個不存在的變量，從而引起程序的錯誤。
5、有關指針類型的意義和說明方式的詳細解釋
可見，在鏈表中插入結點只需要修改指針。但同時，若要在第 i 個結點之前插入元素，修改的是第 i-1 個結點的指針。
因此，在單鏈表中第 i 個結點之前進行插入的基本操作為:
找到線性表中第i-1個結點，然后修改其指向后繼的指針。
6、插入時，當i在合理范圍時，元素能夠準確插入；當i超出下限時，元素能夠插入，但總是插入第一個位置；當i超出上限時，元素不能插入。
八、附件
#include<stdio.h>
#include<malloc.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define NULL 0
typedef int Status;
typedef int ElemType;
typedef struct LNode {
ElemType data;
struct LNode *next;
}LNode,*LinkList;
Status InitList_L(LinkList &L) { //初始化線性表
L=(LinkList)malloc(sizeof(LNode)); //L指向頭節點，頭節點數據域為空
L->next=NULL;
return OK;
}// InitList_L
Status DispList_L(LinkList &L) { //輸出線性表
LinkList p=L->next;
while(p!=NULL)
{
printf("%c",p->data);
p=p->next;
}
return OK;
} // DispList_L
Status CreateList_L(LinkList &L,ElemType a[],int n) { //尾插法建表
LinkList s,r;int i;
L=(LinkList)malloc(sizeof(LNode));
r=L;
for(i=0;i<n;i++)
{
s=(LinkList)malloc(sizeof(LNode));
s->data=a;
r->next=s;
r=s;
}
r->next=NULL;
return OK;
}// CreateList_L
Status ListLength_L(LinkList L) { //求線性表的長度
LinkList p=L;int n=0;
while(p->next!=NULL)
{
n++;
p=p->next;
}
return(n);
}// ListLength_L
Status ListEmpty_L(LinkList L) { //判斷單鏈表是否為空
return(L->next==NULL);
}// ListEmpty_L
Status DestroyList_L(LinkList &L) { //銷毀線性表
LinkListp=L,q=p->next;
while(q!=NULL)
{
free(p);
p=q;
q=p->next;
}
free(p);
return OK;
}// DestroyList_L
Status GetElem_L(LinkList L, int i, ElemType &e) {
// L為帶頭節點的單鏈表的頭指針。
// 當第i個元素存在時，其值賦給e并返回OK，否則返回ERROR
int j=0;
LinkList p=L;
while(j<i&&p!=NULL)
{
j++;p=p->next;
}
if(p==NULL)
{
return ERROR;
}
else
{
e=p->data;
return OK;
}
}// GetElem_L
Status ListInsert_L(LinkList &L, int i, ElemType e) { //插入數據元素
int j=0;
LinkList p=L,s;
/*
找到插入節點的上一個元素，如果是頭節點則退出，當i=1時表示頭節點，i=2時，表示第一個元素
*/
while(j<i-1&&p!=NULL)
{
j++;
p=p->next;
}
if(p==NULL)
{
return ERROR;
}
else
{
s=(LinkList)malloc(sizeof(LNode));
s->data=e;
s->next=p->next;
p->next=s;
return OK;
}
}// ListInsret_L
Status ListDelete_L(LinkList &L, int i, ElemType &e){ //刪除數據元素
int j=0;
LinkList p=L,q;
while(j<i-1&&p!=NULL) //查找刪除元素的前一個節點
{
j++;
p=p->next;
}
if(p==NULL)
{
return ERROR;
}
else
{
q=p->next; //q為要刪除的元素節點
if(q==NULL)
{
return ERROR;
}
e=q->data; //e為刪除節點的數據區域
p->next=q->next;
free(q);
return OK;
}
}// ListDelete_L
int LocateElem_L(LinkList L, ElemType e) { //按元素值查找元素
LinkList p=L->next;
int i=1;
while(p!=NULL&&p->data!=e)
{
p=p->next;i++;
}
//如果要插入的節點為頭節點，則退出
if(p==NULL)
{
return ERROR;
}
else
{
return(i);
}
}// LocateElem_L
int main() {
ElemTypee,a[5]={'a','b','c','d','e'};
LinkList L;
printf("(1)初始化單鏈表L\n");
InitList_L(L); //初始化單鏈表L
printf("(2)依次采用尾插法插入a,b,c,d,e元素\n");
CreateList_L(L,&a[0],5); //依次采用尾插入法插入a，b，c，d，e元素
printf("(3)輸出單鏈表L：");
DispList_L(L); //輸出單鏈表L
printf("\n");
printf("(4)單鏈表L的長度為：");
printf("%d",ListLength_L(L)); //輸出單鏈表L的長度
printf("\n");
if(ListEmpty_L(L))
{
printf("(5)該單鏈表為空\n");
}
else
{
printf("(5)該單鏈表不為空\n"); //判斷單鏈表L是否為空
}
GetElem_L(L,3,e);
printf("(6)單鏈表L的第三個元素為：");
printf("%c",e); printf("\n"); //輸出單鏈表L的第3個元素
printf("(7)單鏈表L中a的位置為：");
printf("%d",LocateElem_L(L,'a')); //輸出元素'a'的位置
printf("\n");
ListInsert_L(L,4,'f'); //在第4個元素位置插入'f'元素
printf("(8)在第4個元素位置上插入 f 元素\n");
printf("(9)輸出單鏈表L：");
DispList_L(L); //輸出單鏈表L
printf("\n");
return 0;
}
|
