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