[課件]數(shù)據(jù)結構第二章線性表.ppt

第二章 線性表,線性結構特點：在數(shù)據(jù)元素的非空有限集中 存在唯一的一個被稱作“第一個”的數(shù)據(jù)元素 存在唯一的一個被稱作“最后一個”的數(shù)據(jù)元素 除第一個外，集合中的每個數(shù)據(jù)元素均只有一個前驅 除最后一個外，集合中的每個數(shù)據(jù)元素均只有一個后繼,2.1 線性表的類型定義（P18-19） 定義：一個線性表是n個數(shù)據(jù)元素的有限序列,例 英文字母表（A,B,C,Z)是一個線性表,特征：（P19） 元素個數(shù)n表長度，n=0空表 1in時 ai的直接前驅是ai-1，a1無直接前驅 ai的直接后繼是ai+1，an無直接后繼 i為數(shù)據(jù)元素ai在線性表中的位序,2.2 線性表的順序存儲結構 順序表： 定義：用一組地址連續(xù)的存儲單元存放一個線性表叫 元素地址計算方法： LOC(ai)=LOC(a1)+(i-1)*L LOC(ai+1)=LOC(ai)+L 其中： L一個元素占用的存儲單元個數(shù) LOC(ai)線性表第i個元素的地址 LOC(a1)起始地址，基地址 特點： 實現(xiàn)邏輯上相鄰物理地址相鄰 實現(xiàn)隨機存取 實現(xiàn)：可用C語言的一維數(shù)組實現(xiàn),#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 Typedef struct ElemType * elem; int length; int listsize; SqList;,數(shù)據(jù)元素不是簡單類型時,可定義結構體數(shù)組,動態(tài)申請內(nèi)存 L.elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType);,插入 定義：線性表的插入是指在第i（1i n+1）個元素之前插入一個新的數(shù)據(jù)元素x，使長度為n的線性表,變成長度為n+1的線性表,需將第i至第n共（n-i+1)個元素后移,算法,Ch2_1.c,x,算法時間復雜度T(n) 設Pi是在第i個元素之前插入一個元素的概率，則在長度為n的線性表中插入一個元素時，所需移動的元素次數(shù)的平均次數(shù)為：,刪除 定義：線性表的刪除是指將第i（1i n）個元素刪除，使長度為n的線性表,變成長度為n-1的線性表,需將第i+1至第n共（n-i)個元素前移,算法,Ch2_2.c,算法評價 設Qi是刪除第i個元素的概率，則在長度為n的線性表中刪除一個元素所需移動的元素次數(shù)的平均次數(shù)為：,故在順序表中插入或刪除一個元素時，平均移動表的一半元素，當n很大時，效率很低,合并順序表 已知順序表La和Lb的順序按值非遞減排列，歸并La和Lb得到新的順序表Lc，Lc的元素也按值非遞減排列 基本操作是“復制”，設2個指針i和j，分別指向2個表當前處理的元素，當i不大于j時復制i所指元素到Lc中，否則復制j所指元素到Lc中,Ch2_3.c,順序存儲結構的優(yōu)缺點 優(yōu)點 邏輯相鄰，物理相鄰 可隨機存取任一元素 存儲空間使用緊湊 缺點 插入、刪除操作需要移動大量的元素 預先分配空間需按最大空間分配，利用不充分 表容量難以擴充,2.3 線性表的鏈式存儲結構 特點： 用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素 利用指針實現(xiàn)了用不相鄰的存儲單元存放邏輯上相鄰的元素 每個數(shù)據(jù)元素ai，除存儲本身信息外，還需存儲其直接后繼的信息 結點 數(shù)據(jù)域：元素本身信息 指針域：指示直接后繼的存儲位置,例 線性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG),43,13,1,NULL,37,7,19,25,頭指針,實現(xiàn),typedef struct LNode ElemType data; struct LNode *next; LNode,*LinkList;,LNode *h,*p;,(*p)表示p所指向的結點 (*p).datap-data表示p指向結點的數(shù)據(jù)域 (*p).nextp-next表示p指向結點的指針域,生成一個新結點：p=(LinkList) malloc ( sizeof ( Lnode ); 系統(tǒng)回收p結點：free(p),線性鏈表 定義：結點中只含一個指針域的鏈表叫，也叫單鏈表,頭結點：在單鏈表第一個結點前附設一個結點叫 頭結點指針域為空表示線性表為空,單鏈表的基本運算 查找：查找單鏈表中是否存在結點X，若有則返回指向X結點的指針；否則返回NULL 算法描述,算法評價,插入：在線性表兩個數(shù)據(jù)元素a和b間插入x，已知p指向a,s-next=p-next;,p-next=s;,算法描述,算法評價,Ch2_4.c,算法描述,算法評價,刪除：單鏈表中刪除b，設p指向a,p-next=p-next-next;,Ch2_5.c,動態(tài)建立單鏈表算法：設線性表n個元素已存放在數(shù)組a中，建立一個單鏈表，h為頭指針,算法描述,算法評價,Ch2_6.c,單鏈表特點 它是一種動態(tài)結構，整個存儲空間為多個鏈表共用 不需預先分配空間 指針占用額外存儲空間 不能隨機存取，查找速度慢,循環(huán)鏈表(circular linked list) 循環(huán)鏈表是表中最后一個結點的指針指向頭結點，使鏈表構成環(huán)狀 特點：從表中任一結點出發(fā)均可找到表中其他結點，提高查找效率 操作與單鏈表基本一致,循環(huán)條件不同 單鏈表p或p-next=NULL 循環(huán)鏈表p或p-next=h,雙向鏈表（double linked list） 單鏈表具有單向性的缺點 結點定義,typedef struct DuLNode ElemType tata; struct DuLNode *prior,*next; DuLNode ,*DuLinkList;,p-prior-next= p= p-next-proir;,刪除,算法描述,算法評價：T(n)=O(1),p-prior-next=p-next;,p-next-prior=p-prior;,Status ListDelete_Dul(DuLinkList return OK ,Status ListInsert_Dul(DuLinkList return OK ,算法描述,算法評價：T(n)=O(1),插入,2.4 線性表的應用舉例 一元多項式的表示及相加 一元多項式的表示：,可用線性表P表示,但對S(x)這樣的多項式浪費空間,用數(shù)據(jù)域含兩個數(shù)據(jù)項的線性表表示,其存儲結構可以用順序存儲結構