2第二章 線性表1

第二章線性表,線性結(jié)構(gòu)特點：在數(shù)據(jù)元素的非空有限集中存在唯一的一個被稱作“第一個”的數(shù)據(jù)元素存在唯一的一個被稱作“最后一個”的數(shù)據(jù)元素除第一個外，集合中的每個數(shù)據(jù)元素均只有一個前驅(qū)除最后一個外，集合中的每個數(shù)據(jù)元素均只有一個后繼,2.1線性表的類型定義（P18-19）定義：一個線性表是n個數(shù)據(jù)元素的有限序列,例英文字母表（A,B,C,.Z)是一個線性表,特征：（P19）元素個數(shù)n表長度，n=0空表1next表示p指向結(jié)點的指針域,生成一個新結(jié)點：p=(LinkList)malloc(sizeof(Lnode);系統(tǒng)回收p結(jié)點：free(p),線性鏈表定義：結(jié)點中只含一個指針域的鏈表叫，也叫單鏈表,頭結(jié)點：在單鏈表第一個結(jié)點前附設(shè)一個結(jié)點叫頭結(jié)點指針域為空表示線性表為空,單鏈表的基本運算查找：查找單鏈表中是否存在結(jié)點X，若有則返回指向X結(jié)點的指針；否則返回NULL算法描述,算法評價,插入：在線性表兩個數(shù)據(jù)元素a和b間插入x，已知p指向a,s-next=p-next;,p-next=s;,算法描述,算法評價,算法描述,算法評價,刪除：單鏈表中刪除b，設(shè)p指向a,p-next=p-next-next;,動態(tài)建立單鏈表算法：設(shè)線性表n個元素已存放在數(shù)組a中，建立一個單鏈表，h為頭指針,算法描述,算法評價,Ch2_3.c,單鏈表特點它是一種動態(tài)結(jié)構(gòu)，整個存儲空間為多個鏈表共用不需預先分配空間指針占用額外存儲空間不能隨機存取，查找速度慢,循環(huán)鏈表(circularlinkedlist)循環(huán)鏈表是表中最后一個結(jié)點的指針指向頭結(jié)點，使鏈表構(gòu)成環(huán)狀特點：從表中任一結(jié)點出發(fā)均可找到表中其他結(jié)點，提高查找效率操作與單鏈表基本一致,循環(huán)條件不同單鏈表p或p-next=NULL循環(huán)鏈表p或p-next=h,雙向鏈表（doublelinkedlist）單鏈表具有單向性的缺點結(jié)點定義,typedefstructDuLNodeElemTypetata;structDuLNode*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;,StatusListDelete_Dul(DuLinkListreturnOK,StatusListInsert_Dul(DuLinkListreturnOK,算法描述,算法評價：T(n)=O(1),插入,2.4線性表的應用舉例一元多項式的表示及相加一元多項式的表示：,可用線性表P表示,但對S(x)這樣的多項式浪費空間,用數(shù)據(jù)域含兩個數(shù)據(jù)項的線性表表示,其存儲結(jié)構(gòu)可以用順序存儲結(jié)構(gòu)，也可以用單鏈表,單鏈表的結(jié)點定義,typedefstructnodeintcoef,exp;structnode*