數據結構之線性表課件-資料下載頁

【導讀】線性表是由有限數目的相同類型元素組成的。第一個元素只有一個后繼元素而無前驅元素；線性表的元素個數n稱為這個表的長度，當。線性表在計算機內存中采用各元素順序存。儲的方式，這種存儲結構叫做向量。號就可以計算出該元素在內存中的地址。在編程時以一維數組表示線性表最簡單，又Score={sdudent1，50，student2，60，[注意]線性表和集合的區別。限序列，當n=0時，線性表為空，即為空表。若n>0,則a1是第1個結點，an是最后一個結點。鄰元素之間存在一種序偶關系。遞增或遞減的順序重新排列；邏輯順序與物理順序一致，在順序表L=（a1,a2,…性表中n個元素均須向后移動一個單元，原來的n減少到n-1.素均維持不變，這是最好的情況。刪除時最少的循環次數為0次，最多為n-1次，用數量級的形式表示線性表插入、刪除運算。的時間復雜性均為O。

　　

【正文】 ， B后移； 若 Aexp=Bexp, 則兩結點的系數相加，若和不為 0，修改 A結點的系數， A,B后移；若為 0，刪除兩結點。 A,B后移。 例 ? 一個單鏈表 L(至少有一個結點 )，其頭結點指針為 head，編寫一個函數將 L倒置。 ?基本思想：從頭到尾遍歷單鏈表 L，并設置 3個附加指針 p、 q、 r, p指向當前處理的結點， q指向 p的后繼， r指向 q的后繼， q、 r的作用是為了防止倒置指針時，下一個結點丟失而設置的。 最后將第一個結點的 next域置為 NULL，并將頭指針指向最后一個結點。 例3.1算法 void invert(node *head) { node *p,*q,*r。 p=head。 q=pnext。 while(q!=NULL) /*沒有后繼時停止 */ { r=qnext。 qnext=p。 p=q。 q=r。 } headnext=NULL。 head=p。 } 例 ?有兩個循環單鏈表，頭指針分為 head1和 head2，編寫函數將鏈表 head2鏈接到鏈表 head1之后，鏈接后的鏈表仍保持是循環鏈表的形式。 ?解：先找到兩個表的表尾，將 head2放入鏈表head1的表尾，然后將 head1放入原 head2鏈表的表尾。 h e a d 1 a 1 a n a 2 h e a d 2 b 1 b n b 2 例3.2算法 link(node *head1, *head2) { node *p,*q。 p=head1。 while(pnext!=head1) p=pnext。 q=head2。 while(qnext!=head2) q=qnext。 pnext=head2。 qnext=head1。 } 例 ?給出在雙鏈表中第 i個結點 (i≥0)之后插入一個元素為 x的結點的函數。 ?解：在前面雙鏈表一節中，已經給出了在一個結點之前插入一個新結點的方法，在一個結點之后插入一個新結點的思想與前面是一樣的。 例3.3算法 void insert(dnode *head,int i,x) { dnode *s,*p。 int j。 s=(dnode *)malloc(sizeof(dnode))。 /*建立一個待插入的結點 ， 由 s指向 */ sdata=x。 if(i==0) /*如 i=0,將 s所指結點插入到表頭后返回 */ { snext=head。 headprior=s。 head=s。 } 例3.3算法續 else { p=head。 /*查找第 i個結點 ， 由 p指向 */ j=1。 while(p!=NULL amp。amp。 ji) { j++。 p=pnext。 } if(p!=NULL) /*若查找成功 ， 把 s插入到 p之后 */ if(pnext==NULL) /*若 p是最后一個結點，則直接把 s結點鏈入 */ 例3.3算法續 { pnext=s。 snext=NULL。 sprior=p。 } else { snext=pnext。 pnextprior=s。 pnext=s。 sprior=p。 } else printf(“未找到 !\n”)。 } } 返回 小結 ?單鏈表 ?循環鏈表 ?雙向鏈表 ?雙向循環鏈表 ?十字鏈表 返回 習題與練習 ?一、基礎知識題 1. 試比較順序表與鏈表的優缺點。 2. 試分析單鏈表與雙鏈表的優缺點。 3. 為什么在單循環鏈表中設置尾指針比設置頭指針更好？ 4. 寫出在循環雙鏈表中的 p所指結點之后插入一個 s所指結點的操作。 5. 寫出在單鏈表中的 p所指結點之前插入一個 s所指結點的操作。 6. 請利用鏈表來表示下面一元多項式 781194)( 3811 ????? xxxxxA?二、算法設計題 1. 有一個有 n個結點的單鏈表，設計一個函數將第 i1個結點與第 i個結點互換，但指針不變。 2. 設計一個函數，查找單鏈表中數值為 x的結點。 3. 已知一個單鏈表，編寫一個刪除其值為 x的結點的前趨結點的算法。 4. 已知一個單鏈表，編寫一個函數從此單鏈表中刪除自第 i個元素起的 length個元素。 5. 已知一個遞增有序的單鏈表，編寫一個函數向該單鏈表中插入一個元素為 x的結點，使插入后該鏈表仍然遞增有序。 6. 已知一個單鏈表，編寫一個函數將此單鏈表復制一個拷貝。 7. 有一個共 10個結點的單鏈表，試設計一個函數將此單鏈表分為兩個結點數相等的單鏈表。 8. 與上題相同的單鏈表，設計一個函數，將此單鏈表分成兩個單鏈表，要求其中一個仍以原表頭指針head1作表頭指針，表中順序包括原線性表的第一、三等奇數號結點；另一個鏈表以 head2為表頭指針，表中順序包括原單鏈表第二、四等號結點。 9. 已知一個指針 p指向單循環鏈表中的一個結點，編寫一個對此單循環鏈表進行遍歷的算法。 10. 已知一個單循環鏈表，編寫一個函數，將所有箭頭方向取反。 11. 在雙鏈表中，若僅知道指針 p指向某個結點，不知頭指針，能否根據 p遍歷整個鏈表？若能，試設計算法實現。 12. 試編寫一個在循環雙向鏈表中進行刪除操作的算法，要求刪除的結點是指定結點 p的前趨結點。