數(shù)據(jù)結構之線性表課件(存儲版)
【正文】 r e a r r e a r 雙向鏈表 ?雙向鏈表中每個結點除了有向后指針外，還有指向其前一個結點的指針，這樣形成的鏈表中有兩條不同方向的鏈，因此從某一結點均可向兩個方向訪問。 } Dblinklist。 p ① ② 4654)( 2345 ????? xxxxxAxxxxxB ???? 245 623)( 多項式的加法 運算規(guī)則 ? 將二個一元多項式中所有指數(shù)相同項的系數(shù)相加，相加后，若和不為零，則構造 “和多項式”中的一項； ? 若和為零，則“和多項式”中無此項； ? 所有指數(shù)不相同的項均考貝到“和多項式”中。 把多項式 B(x)加到 A(x)中。 q=pnext。 ?解：先找到兩個表的表尾，將 head2放入鏈表head1的表尾，然后將 head1放入原 head2鏈表的表尾。 } 例 ?給出在雙鏈表中第 i個結點 (i≥0)之后插入一個元素為 x的結點的函數(shù)。 head=s。 snext=NULL。 2. 試分析單鏈表與雙鏈表的優(yōu)缺點。 6. 已知一個單鏈表，編寫一個函數(shù)將此單鏈表復制一個拷貝。 12. 試編寫一個在循環(huán)雙向鏈表中進行刪除操作的算法，要求刪除的結點是指定結點 p的前趨結點。 4. 已知一個單鏈表，編寫一個函數(shù)從此單鏈表中刪除自第 i個元素起的 length個元素。 } else printf(“未找到 !\n”)。 p=pnext。 if(i==0) /*如 i=0,將 s所指結點插入到表頭后返回 */ { snext=head。 pnext=head2。 head=p。 例3.1算法 void invert(node *head) { node *p,*q,*r。 Struct pnode *next。 (pnext) prior=pprior。 struct dbnode *prior。 delete_seqlist(josephus_seq, s1+1) } 2. 帶尾指針的循環(huán)鏈表 ?另一種方法是不設頭指針而改設尾指針，這樣無論是找頭結點還是尾結點都很方便。 struct Jnode *next。 ?空表頭結點除指針以外的數(shù)據(jù)域是沒有用的，但為了將此結點與一般結點相區(qū)別，常常是將其賦以一個特別的數(shù)據(jù)，以與一般結點相區(qū)別。 如： slinklist sl[maxsize]。 } 刪除算法續(xù) if (p=NULL) { printf (“x不存在 ” ) return(null)。 elementtype x。 /*表的頭部 ， 即 k=1 head=s。 {linklist *p,*pre,*s。 int k=0。 ?實現(xiàn)插入算法主要完成三個基本操作： 1) 在單鏈表上找到插入位置 ， 即找到第 i個結點 。 /*計數(shù)器置初值 */ p=head。 struct lnode *next； }linklist ?一個結點是由兩個域 data和 next組成的記錄 , data是結點的數(shù)據(jù)域， next是結點的鏈域。 該語句的作用？ } } if (i=) printf(“i值錯 ！ \n”)。 Int LocateDeleteSeqlist(list sl。 else { for (k=i。 k=i1。 ?線性表的邏輯結構 線性表的元素類型是多樣的，但同一線性表中的元素必須是同一類型，且相鄰元素之間存在一種序偶關系。 ?每個線性表元素叫做這個向量的一個分量。 ?線性表在計算機內(nèi)存中采用各元素順序存儲的方式，這種存儲結構叫做向量。 其形式化的定義為： S=（ D， R） 其中： D是由 n個元素組成的集合， R是定義在集合 D上的一種關系。 else { for (k=。 2. 元素的刪除 (Delete) 在順序表 L=（ a1,a2,… ,ai,…,an ）中刪除第 i個結點，使成為 L=（ a1,a2,…,ai 1, ai+1,…, an ） 基本思想 ：要求刪除第 i個數(shù)據(jù)元素，由于線性表元素在數(shù)組中必須連續(xù)排列，中間不能有空單元， 故將此元素刪除后，它后面的所有元素都需要向前移動一個單元，且數(shù)據(jù)元素總數(shù)由原來的 n減少到 n1. 刪除 函數(shù) Int delete(list L, int i) /*刪除順序表中第 I個結點 { int k； if (i1||i) printf(“i值錯 ！ \n”)。 ?刪除一個值為 X的元素 基本思想 ：在線性表中，查找到值為 X的元素 ai，將 i 之后的元素前移一個位置，且線性表的長度減 1。 break。 h e a d a 1 a 2 a i a n ∧ 單鏈表的類型定義 ?單鏈表的的結點類型定義如下： typedef struct Lnode { elementtype data。 ?假設 head是單鏈表的頭指針，計算一個已建立好的單鏈表的結點個數(shù)的算法如下： 計算結點個數(shù)算法 int length(head) /*求表 head的長度 */ { int count=0。 2. 插入 ?所謂插入是指在單鏈表中第 i個結點 (i≥0)之后插入一個元素為 x的結點。 head a1 a 2 a i a n ∧ a i +1 S x P insert(head) /*在第 i個結點 后 插入結點 S { linklist *p=head。 結點之 前 插入 X int k。 If (pre==null) /*插入的結
法律信息相關推薦
鄂ICP備17016276號-1