數據結構教程 第八課 線性表的鏈式表示與實現
責任編輯:chineselng    瀏覽:2269次    時間: 2008-04-05 23:01:21      

摘要:本課主題: 線性表的鏈式表示與實現 教學目的: 掌握線性鏈表、單鏈表、靜態鏈表的概念、表示及實現方法 教學重點: 線性鏈表之單鏈表的表示及實現方法。 教學難點: 線性鏈表的概念。 授課內容: 一、復習順序表的定義。 二、線性鏈表的概念: 以鏈式結構存儲的線..

分享到:

本課主題: 線性表的鏈式表示與實現

教學目的: 掌握線性鏈表、單鏈表、靜態鏈表的概念、表示及實現方法

教學重點: 線性鏈表之單鏈表的表示及實現方法。

教學難點: 線性鏈表的概念。

授課內容:

一、復習順序表的定義。

二、線性鏈表的概念:

以鏈式結構存儲的線性表稱之為線性鏈表。

特點是該線性表中的數據元素可以用任意的存儲單元來存儲。線性表中邏輯相鄰的兩元素的存儲空間可以是不連續的。為表示邏輯上的順序關系,對表的每個數據元素除存儲本身的信息之外,還需存儲一個指示其直接衙繼的信息。這兩部分信息組成數據元素的存儲映象,稱為結點。

2000:1000
2000:1010
2000:1020
2000:1030
2000:1040
2000:1050
2000:1060
...
2000:4000
頭指針2000:1006 2000:1030
a3 2000:1040
a6 NULL
a1 2000:1060
a4 2000:1050
a5 2000:1020
a2 2000:1010
數據域 指針域
   
 
 
 
<-數據域+指針域
 
 
 
 
 

例:下圖是若干抽屜,每個抽屜中放一個數據元素和一個指向后繼元素的指針,一號抽屜中放線性表的第一個元素,它的下一個即第二個元素的位置標為5,即放在第5個抽屜中,而第三個放在2號抽屜中。第三個元素即為最后一個,它的下一個元素的指針標為空,用0表示。

用線性鏈表表示線性表時,數據元素之間的邏輯關系是由結點中的指針指示的

二、線性鏈表的存儲實現

struct LNODE{

ElemType data;

struct LNODE *next;

};

typedef struct LNODE LNode;

typedef struct LNODE * LinkList;

頭指針與頭結點的區別:

頭指針只相當于結點的指針域,頭結點即整個線性鏈表的第一個結點,它的數據域可以放數據元素,也可以放線性表的長度等附加信息,也可以不存儲任何信息。

三、線性表的操作實現(類C語言)

1初始化操作

Status Init_L(LinkList L){

if (L=(LinkList *)malloc(sizeof(LNode)))

{L->next=NULL;return 1;}

else return 0;

}

2插入操作

Status ListInsert_L(LinkList &L,int i,ElemType e){

p=L,j=0;

while(p&&j<i-1){p=p->next;++j;}

if(!p||j>i-1) return ERROR;

s=(LinkList)malloc(sizeof(LNode));

s->data=e;s->next=p->next;

p->next=s;

return OK;

}//ListInsert_L

3刪除操作

Status ListDelete_L(LinkList &L,int i,ElemType &e){

p=L,j=0;

while(p&&j<i-1){p=p->next;++j;}

if(!p->next||j>i-1) return ERROR;

q=p->next;p->next=q->next;

e=q->data;free(q);

return OK;

}//ListDelete_L

4取某序號元素的操作

Status GetElem_L(LinkList &L,int i,ElemType &e){

p=L->next,j=1;

while(p&&j<i){p=p->next;++j;}

if(!p||j>i) return ERROR;

e=p->data;

return OK;

}//GetElem_L

5歸并兩個單鏈表的算法

void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){

//已知單鏈線性表La和Lb的元素按值非遞減排列

//歸并后得到新的單鏈線性表Lc,元素也按值非遞減排列

pa=La->next;pb=Lb->next;

Lc=pc=La;

while(pa&&pb){

if(pa->data<=pb->data){

pc->next=pa;pc=pa;pa=pa->next;

}else{pc->next=pb;pc=pb;pb=pb->next;}

}

pc->next=pa?pa:pb;

free(Lb);

}//MergeList_L

C語言實現的例子。

四、總結

1、線性鏈表的概念。

2、線性鏈表的存儲

3、線性鏈表的操作

】【打印繁體】【投稿】 【收藏】 【推薦】 【舉報】 【評論】 【關閉】【返回頂部
發表評論
帳  號: 密碼: (新用戶注冊)
驗 證 碼:
表 情:
內  容:
發表評論
用戶評價(0)

暫時還沒有任何評論

亚洲AV国产AV手机在线