線性表的邏輯結(jié)構(gòu)及其基本操作【精品-ppt】(已修改)
2025-10-25 19:01 本頁面
【正文】 2021/11/12 1 ? 線性表的邏輯結(jié)構(gòu)及其基本操作 ? 線性表的順序存儲(chǔ)結(jié)構(gòu) ? 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) ? 靜態(tài)鏈表 ? 應(yīng)用實(shí)例 第二章 線性表 2021/11/12 2 . 線性表的邏輯結(jié)構(gòu)及其基本操作 線性表是 n(n=0)個(gè)相同類型數(shù)據(jù)元素 a0, a1, ? ， an1構(gòu)成的有限序列。 形式化定義： Linearlist = (D, R) 其中： }1,2,1,|,{|,}{}0,1,1,0,|{0110?????????????? niDaaaaNNRnniDaaDiiiiii??D0為某個(gè)數(shù)據(jù)對(duì)象的集合 N為線性表長(zhǎng)度 2021/11/12 3 線性表的主要操作 ? 初始化 ? 求長(zhǎng)度 ? 取元素 ? 定位 ? 插入 ? 刪除 2021/11/12 4 例：利用線性表的基本運(yùn)算實(shí)現(xiàn)清除 L中多余的重復(fù)節(jié)點(diǎn) 。 PURGE(Linear_list *L) { int i=1,j,x,y。 while (iLENGTH(L)) { x=GET(L,i)。 j=i+1。 while (j=LENGTH(L)) { y=GET(L,j)。 if (x==y) DELETE(L,j)。 else j++。 } i++。 } } 2021/11/12 5 線性表的順序存儲(chǔ)結(jié)構(gòu) 順序表 設(shè)線性表的基地址為： LOC(a1),ai的存儲(chǔ)地址為： LOC(ai) = LOC(a0)＋ i*k 1=i=n a0 a1 ai an1 ? ? a0 a1 ai an1 ? ? 0 1 n1 Loc(a0) Loc(a0)+k i Loc(a0)+i*k Loc(a0)+(n1)*k 2021/11/12 6 線性表的定義為： typedef int datatype。 //假定線性表元素的類型為整型 define maxsize 1024 //假定線性表的最大長(zhǎng)度為 1024 typedef struct { datatype data[maxsize]。 int last。 //指向最后結(jié)點(diǎn)的位置 } sequenlist。 2021/11/12 7 先定義結(jié)構(gòu)類型，再定義變量名 struct student { int num。 char name[20]。 char sex。 int age。 float score。 char addr[30]。 }； Struct student student1, student2。 C語言中定義結(jié)構(gòu)的方法 2021/11/12 8 在聲明類型的同時(shí)定義結(jié)構(gòu)變量 struct student { int num。 char name[20]。 char sex。 int age。 float score。 char addr[30]。 } student1, student2。 2021/11/12 9 直接定義結(jié)構(gòu)變量 struct { int num。 char name[20]。 char sex。 int age。 float score。 char addr[30]。 } student1, student2。 2021/11/12 10 例： define MAXSIZE最大元素個(gè)數(shù) typedef struct { char Name[20]。 char Sex。 int Age。 float fareAmount。 } datatype。 2021/11/12 11 線性表元素的插入（在線性表 L中第 i個(gè)位置前插入新元素 x） int INSERT(sequenlist *L,datatype x,int i) { int j。 if (((*L).last)=maxsize－ 1) { printf(“overflow\n”)。 return NULL。} //溢出 else if((i1)||(i((*L).last)＋ 1) { printf(“error\n”)。 return NULL。} //非法位置 else { for(j=(*L).last。j=i1。j) (*L).data[j+1]＝ (*L).data[j]。 (*L).data[i1]＝ x。 (*L).last＝ (*L).last+1。 } return(1)。 } 2021/11/12 12 線性表元素的刪除 （在線性表 L中刪除第 i個(gè)元素） int DELETE(sequenlist *L,int i) { int j。 if ((i1)||(i(*L).last+1)) { printf(“error\n”)。 return NULL。} //非法位置 else { for(j=i。 j=(*L).last。 j++) (*L).data[j1]＝ (*L).data[j]。 (*L).last。 //表長(zhǎng)減 1 } return(1)。 } 2021/11/12 13 插入 n/2 刪除 (n1)/2 按序號(hào)檢索 O(1) 按內(nèi)容檢索 n/2 算法復(fù)雜性分析 2021/11/12 14 順序表的優(yōu)點(diǎn)： ?無須為表示節(jié)點(diǎn)間的邏輯關(guān)系而增加額外的存儲(chǔ)空間 ?可以方便的隨機(jī)存取表中的任一節(jié)點(diǎn) 順序表的缺點(diǎn)： ?插入和刪除運(yùn)算不方便 ?由于要求占用連續(xù)的存儲(chǔ)空間，存儲(chǔ)分配只能預(yù)先進(jìn)行 2021/11/12 15 線性表的鏈?zhǔn)酱鎯?chǔ) h h 不帶頭節(jié)點(diǎn)的鏈表 帶頭節(jié)點(diǎn)的鏈表 2021/11/12 16 單鏈表結(jié)點(diǎn)的定義： typedef int datatype。 typedef struct node { datatype data。 struct node *next。 } linklist。 節(jié)點(diǎn)的申請(qǐng) p＝ malloc(sizeof(linkist))。 節(jié)點(diǎn)的釋放 free(p)。 202
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1