本課主題： 線(xiàn)性表的順序表示和實(shí)現
教學(xué)目的： 掌握線(xiàn)性表的順序表示和實(shí)現方法
教學(xué)重點(diǎn)： 線(xiàn)性表的順序表示和實(shí)現方法
教學(xué)難點(diǎn)： 線(xiàn)性表的順序存儲的實(shí)現方法
授課內容：
復習
1、存儲結構
邏輯結構 “數據結構”定義中的“關(guān)系”指數據間的邏輯關(guān)系，故也稱(chēng)數據結構為邏輯結構。
存儲結構 數據結構在計算機中的表示稱(chēng)為物理結構。又稱(chēng)存儲結構。
順序存儲結構
鏈式存儲結構
2、線(xiàn)性表的類(lèi)型定義
一、線(xiàn)性表的順序表示
用一組地址連續的存儲單元依次存儲線(xiàn)性表的數據元素。C語(yǔ)言中的數組即采用順序存儲方式。
2000:0001
2000:0003
2000:0005
2000:0007
2000:0009
2000:0011
2000:0013
2000:0015
2000:0017
...
2000:1001
2000:1003
0000000000000001
0000000000000010
0000000000000011
0000000000000100
0000000000000101
0000000000000110
0000000000000111
0000000000001000
0000000000001001
a[9]1
2
3
4
5
6
7
8
9
假設線(xiàn)性表的每個(gè)元素需占用l個(gè)存儲單元，并以所占的第一個(gè)單元的存儲地址作為數據元素的存儲位置。則存在如下關(guān)系：
LOC(ai+1)=LOC(ai)+l
LOC(ai)=LOC(a1)+(i-1)*l
式中LOC(a1)是線(xiàn)性表的第一個(gè)數據元素的存儲位置，通常稱(chēng)做線(xiàn)性表的起始位置或基地址。常用b表示。
線(xiàn)性表的這種機內表示稱(chēng)做線(xiàn)性表的順序存儲結構或順序映象。
稱(chēng)順序存儲結構的線(xiàn)性表為順序表。順序表的特點(diǎn)是以元素在計算機內物理位置相鄰來(lái)表示線(xiàn)性表中數據元素之間的邏輯關(guān)系。
二、順序存儲結構的線(xiàn)性表類(lèi)C語(yǔ)言表示：
線(xiàn)性表的動(dòng)態(tài)分配順序存儲結構
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef struct{
ElemType *elem; //存儲空間基址
int length; //當前長(cháng)度
int listsize; //當前分配的存儲容量以一數據元素存儲長(cháng)度為單位
}SqList;
三、順序存儲結構的線(xiàn)性表操作及C語(yǔ)言實(shí)現：
順序表的插入與刪除操作：
序號數據元素序號數據元素 序號數據元素序號數據元素
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;
}
順序表的聯(lián)合算法
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語(yǔ)言源程序范例
四、總結
線(xiàn)性表的順序表示
順序表的插入算法順序表的合并算法
