數據結構教程 第六課 線性表的順序表示和實現
責任編輯:chineselng    瀏覽:2264次    時間: 2008-04-05 22:52:00      

摘要:本課主題: 線性表的順序表示和實現 教學目的: 掌握線性表的順序表示和實現方法 教學重點: 線性表的順序表示和實現方法 教學難點: 線性表的順序存儲的實現方法 授課內容: 復習 1、存儲結構 邏輯結構 “數據結構”定義中的“關系”指數據間的邏輯關系,故也..

分享到:

本課主題: 線性表的順序表示和實現

教學目的: 掌握線性表的順序表示和實現方法

教學重點: 線性表的順序表示和實現方法

教學難點: 線性表的順序存儲的實現方法

授課內容:

復習

1、存儲結構

邏輯結構   “數據結構”定義中的“關系”指數據間的邏輯關系,故也稱數據結構為邏輯結構。
存儲結構   數據結構在計算機中的表示稱為物理結構。又稱存儲結構。
順序存儲結構
鏈式存儲結構

2、線性表的類型定義

一、線性表的順序表示

用一組地址連續的存儲單元依次存儲線性表的數據元素。C語言中的數組即采用順序存儲方式。

2000:0001
2000:0003
2000:0005
2000:0007
2000:0009
2000:0011
2000:0013
2000:0015
2000:0017
...
2000:1001
2000:1003
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1
                               
                               
                               
a[9]
1
2
3
4
5
6
7
8
9
 
 
 

假設線性表的每個元素需占用l個存儲單元,并以所占的第一個單元的存儲地址作為數據元素的存儲位置。則存在如下關系:

LOC(ai+1)=LOC(ai)+l

LOC(ai)=LOC(a1)+(i-1)*l

式中LOC(a1)是線性表的第一個數據元素的存儲位置,通常稱做線性表的起始位置基地址。常用b表示。

線性表的這種機內表示稱做線性表的順序存儲結構或順序映象。

稱順序存儲結構的線性表為順序表。順序表的特點是以元素在計算機內物理位置相鄰來表示線性表中數據元素之間的邏輯關系。

二、順序存儲結構的線性表類C語言表示:

線性表的動態分配順序存儲結構

#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10

typedef struct{

ElemType *elem; //存儲空間基址

int length; //當前長度

int listsize; //當前分配的存儲容量以一數據元素存儲長度為單位

}SqList;

三、順序存儲結構的線性表操作及C語言實現:

順序表的插入與刪除操作:

序號 數據元素 序號 數據元素   序號 數據元素 序號 數據元素
1
2
3
4
5
6
7
8
9
 
 
 
12
13
21
24
28
30
42
77
 
 
 
 

 

 


<-25

 

1
2
3
4
5
6
7
8
9
 
 
 
12
13
21
24
25
28
30
42
77
 
 
 
 
1
2
3
4
5
6
7
8
9
 
 
 
12
13
21
24
28
30
42
77
 
 
 
 

 

 

->24

1
2
3
4
5
6
7
8
9
 
 
 
12
13
21
28
30
42
77
 
 
 
 
 
插入前n=8;插入后n=9;   刪除前n=8;刪除后n=7;

順序表的插入算法

status ListInsert(List *L,int i,ElemType e) {

struct STU *p,*q;

if (i<1||i>L->length+1) return ERROR;

q=&(L->elem[i-1]);

for(p=&L->elem[L->length-1];p>=q;--p)

*(p+1)=*p;

*q=e;

++L->length;

return OK;

}/*ListInsert Before i */

順序表的合并算法

void MergeList(List *La,List *Lb,List *Lc) {

ElemType *pa,*pb,*pc,*pa_last,*pb_last;

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

Lc->listsize = Lc->length = La->length + Lb->length;

pc = Lc->elem =

(ElemType *)malloc(Lc->listsize * sizeof(ElemType));

if(!Lc->elem) exit(OVERFLOW);

pa_last = La->elem + La->length - 1;

pb_last = Lb->elem + Lb->length - 1;

while(pa<=pa_last && pb<=pb_last) {

if(Less_EqualList(pa,pb)) *pc++=*pa++;

else *pc++=*pb++;

}

while(pa<=pa_last) *pc++=*pa++;

while(pb<=pb_last) *pc++=*pb++;

}

順序表的查找算法

int LocateElem(List *La,ElemType e,int type) {

int i;

switch (type) {

case EQUAL:

for(i=0;i<length;i++)

if(EqualList(&La->elem[i],&e))

return 1;

break;

default:

break;

}

return 0;

}

順序表的聯合算法

void UnionList(List *La, List *Lb) {

int La_len,Lb_len; int i; ElemType e;

La_len=ListLength(La); Lb_len=ListLength(Lb);

for(i=0;i<Lb_len;i++) {

GetElem(*Lb,i,&e);

if(!LocateElem(La,e,EQUAL))

ListInsert(La,++La_len,e);

}

}

三、C語言源程序范例

四、總結

線性表的順序表示

順序表的插入算法

順序表的合并算法

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

暫時還沒有任何評論

亚洲AV国产AV手机在线