線性表的概念及邏輯結(jié)構(gòu)

1、第一節(jié)線性表的概念及邏輯結(jié)構(gòu),第二章 線性表,線性表是N個(gè)數(shù)據(jù)元素的有限序列構(gòu)成的一種線性結(jié)構(gòu)。線性表的形式定義： Linear--List=（D，R） D={a1，a2，……an} R={〈ａi-1，ai〉│i=2..n} n 稱為線性表長度，n=0稱空表； ai為數(shù)據(jù)元素。,,線性表還可以邏輯地表示為： （a1，a2，……an）線性表的特點(diǎn)

2、：唯一首元素；唯一尾元素；除首元素外，任何元素有一個(gè)前驅(qū)；除尾元素外，任何元素有一個(gè)后繼；每個(gè)元素有一位序。,第二節(jié) 線性表的抽象類型定義,,ADT　List {,} ADT List,第三節(jié) 線性表的順序表示和實(shí)現(xiàn),一 順序表示,用一組連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。 設(shè) b 為首地址 L為數(shù)據(jù)元素長度,二 線性表的順序結(jié)構(gòu)實(shí)現(xiàn),線性表由三個(gè)部分組成： 1）一組連續(xù)存儲(chǔ)空間

3、 2）當(dāng)前長度 3）空間大小 用c 語言可描述為：,#define List-Init-Size 100#define Listincrement 10typedef struct {Elemtype *elem；int length；intlistsize；} Sqlist；,初始化一個(gè)線性表,Status Initlist_Sq(Sqlist &L){

4、 L.elem=分配List-Init-Size個(gè)空間; L.length=0; L.listsize= List-Init-Size; return OK;},線性表插入前后狀況,下移一格,三 插入操作的算法實(shí)現(xiàn),Status Listinsert_Sq(Sqlist &L,int i, Elemtype e){ if (iL.length+1) return ERROR; if

5、 (L.length>=L.listsize) { newbase=追加分配新空間 L.elem=newbase; L.listsize+=Listincrement; } for (j=L.length-1;j>=i-1;--j) L.elem[j+1]=L.elem[j]); L.elem[j]=e; ++L.l

6、ength; return OK;},線性表刪除前后狀況,四 刪除操作的算法實(shí)現(xiàn),Status Listdelete_Sq(Sqlist &L,int i, Elemtype &e){ if (iL.length) return ERROR; e= L.elem[i-1]); for (j=i;j>=L.length-1;++j) L.elem[j-

7、1]=L.elem[j]); --L.length; return OK;},五 算法分析,設(shè)在線性表第 i 個(gè)元素前插入一新元素的概率為 Pi，刪除第 i 個(gè)元素的概率為 Qi，元素移動(dòng)為算法的基本操作。則插入和刪除的平均移動(dòng)期望值為： Ei= Pi（n-i+1） Ed= Qi （n-i） 等概率下： Ei

8、=n / 2 Ed =（n-1）/ 2,第四節(jié) 線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn),二 存儲(chǔ)結(jié)構(gòu),線性表的單鏈表存儲(chǔ)結(jié)構(gòu)：typedef struct Lnode { Elemtype data； struct Lnode *next；} Lnode， *Linklist；,三 基本操作實(shí)現(xiàn),1） 取鏈表中第 i 個(gè)元素Status Getelem_L(Linklist L,

9、int i,Elemtype &e) { p=L->next; j=1; while (p&&jnext;++j } if ( !p ‖j>i) return ERROR; e=p->data; return OK; },2） 在 P 所指結(jié)點(diǎn)之后插入新結(jié)點(diǎn),S-〉next=P-〉next

10、；P-〉next=S,,Status Listinsert_L(Linklist &L,int i,Elemtype e) { p=L; j=0; while (p&&jnext;++j } if ( !p ‖j>i-1) return ERROR; new(s); s->data=e; s->

11、;next=p->next; p->next=s; return OK; },3） 刪除 P 所指結(jié)點(diǎn)之后的結(jié)點(diǎn),P,,P -＞ next= P -＞ next -＞ next,,Status Listdelete_L(Linklist &L,int i,Elemtype &e) { p=L; j=0; while (p->nex

12、t&&jnext; ++j } if ( !(p->next) ‖j>i-1) return ERROR; q= p->next ; p->next=q ->next; e=q ->data; free(q); return OK; },四 應(yīng)用舉例

13、 有序表的合并,,Pc,,**C語言算法實(shí)現(xiàn)參見下頁,void Mergelist_L(Linklist &La, Linklist &Lb, Linklist &Lc) { pa=La->next; pb=Lb->next; Lc=pc=La; while (pa&&pb) { if (

14、pa->datadata) { pc->next=pa;pc=pa;pa=pa->next;} else { pc->next=pb;pc=pb;pb=pb->next;} } pc->next =pa?pa:pb; free(Lb);

15、 },第四節(jié) 循環(huán)鏈表,1 單循環(huán)鏈表,單循環(huán)空鏈表,2 雙向鏈表,雙向空鏈表,雙向鏈表結(jié)點(diǎn)結(jié)構(gòu),typedef struct Dublnode{Elemtype data;struct Dublnode *prior ；struct Dublnode *next ；}Dublnode,*Dublinklist ；,雙向鏈表結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)定義,3 雙向鏈表插入一新結(jié)點(diǎn),4 雙向鏈表刪除一

16、結(jié)點(diǎn),,,,① p -＞ prior -＞ next=p -＞ next；② p -＞ next -＞ prior=p -＞ prior；,,數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì),名稱：學(xué)生數(shù)據(jù)管理內(nèi)容：實(shí)現(xiàn)學(xué)生數(shù)據(jù)管理的如下功能,插入刪除查找顯示,錄入存儲(chǔ)裝入修改,數(shù)據(jù)結(jié)構(gòu)：線性表數(shù)據(jù)對象：班或系的學(xué)生記錄學(xué)生記錄：,學(xué)號(hào)姓名年齡性別家庭住址入學(xué)時(shí)間家庭電話號(hào)碼,數(shù)據(jù)控制與數(shù)據(jù)流分析,時(shí)間：第六周至十五周，共二十小時(shí)上機(jī)