數(shù)據(jù)結(jié)構(gòu)之線性表課件-資料下載頁
2025-08-22 09:01本頁面
【導(dǎo)讀】線性表是由有限數(shù)目的相同類型元素組成的。第一個元素只有一個后繼元素而無前驅(qū)元素；線性表的元素個數(shù)n稱為這個表的長度，當(dāng)。線性表在計算機內(nèi)存中采用各元素順序存。儲的方式，這種存儲結(jié)構(gòu)叫做向量。號就可以計算出該元素在內(nèi)存中的地址。在編程時以一維數(shù)組表示線性表最簡單，又Score={sdudent1，50，student2，60，[注意]線性表和集合的區(qū)別。限序列，當(dāng)n=0時，線性表為空，即為空表。若n>0,則a1是第1個結(jié)點，an是最后一個結(jié)點。鄰元素之間存在一種序偶關(guān)系。遞增或遞減的順序重新排列；邏輯順序與物理順序一致，在順序表L=（a1,a2,…性表中n個元素均須向后移動一個單元，原來的n減少到n-1.素均維持不變，這是最好的情況。刪除時最少的循環(huán)次數(shù)為0次，最多為n-1次，用數(shù)量級的形式表示線性表插入、刪除運算。的時間復(fù)雜性均為O。
【正文】 ， B后移； 若 Aexp=Bexp, 則兩結(jié)點的系數(shù)相加，若和不為 0，修改 A結(jié)點的系數(shù)， A,B后移；若為 0，刪除兩結(jié)點。 A,B后移。 例 ? 一個單鏈表 L(至少有一個結(jié)點 )，其頭結(jié)點指針為 head，編寫一個函數(shù)將 L倒置。 ?基本思想：從頭到尾遍歷單鏈表 L，并設(shè)置 3個附加指針 p、 q、 r, p指向當(dāng)前處理的結(jié)點， q指向 p的后繼， r指向 q的后繼， q、 r的作用是為了防止倒置指針時，下一個結(jié)點丟失而設(shè)置的。 最后將第一個結(jié)點的 next域置為 NULL，并將頭指針指向最后一個結(jié)點。 例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。 } 例 ?有兩個循環(huán)單鏈表，頭指針分為 head1和 head2，編寫函數(shù)將鏈表 head2鏈接到鏈表 head1之后，鏈接后的鏈表仍保持是循環(huán)鏈表的形式。 ?解：先找到兩個表的表尾，將 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個結(jié)點 (i≥0)之后插入一個元素為 x的結(jié)點的函數(shù)。 ?解：在前面雙鏈表一節(jié)中，已經(jīng)給出了在一個結(jié)點之前插入一個新結(jié)點的方法，在一個結(jié)點之后插入一個新結(jié)點的思想與前面是一樣的。 例3.3算法 void insert(dnode *head,int i,x) { dnode *s,*p。 int j。 s=(dnode *)malloc(sizeof(dnode))。 /*建立一個待插入的結(jié)點 ， 由 s指向 */ sdata=x。 if(i==0) /*如 i=0,將 s所指結(jié)點插入到表頭后返回 */ { snext=head。 headprior=s。 head=s。 } 例3.3算法續(xù) else { p=head。 /*查找第 i個結(jié)點 ， 由 p指向 */ j=1。 while(p!=NULL amp。amp。 ji) { j++。 p=pnext。 } if(p!=NULL) /*若查找成功 ， 把 s插入到 p之后 */ if(pnext==NULL) /*若 p是最后一個結(jié)點，則直接把 s結(jié)點鏈入 */ 例3.3算法續(xù) { pnext=s。 snext=NULL。 sprior=p。 } else { snext=pnext。 pnextprior=s。 pnext=s。 sprior=p。 } else printf(“未找到 !\n”)。 } } 返回 小結(jié) ?單鏈表 ?循環(huán)鏈表 ?雙向鏈表 ?雙向循環(huán)鏈表 ?十字鏈表 返回 習(xí)題與練習(xí) ?一、基礎(chǔ)知識題 1. 試比較順序表與鏈表的優(yōu)缺點。 2. 試分析單鏈表與雙鏈表的優(yōu)缺點。 3. 為什么在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指針更好？ 4. 寫出在循環(huán)雙鏈表中的 p所指結(jié)點之后插入一個 s所指結(jié)點的操作。 5. 寫出在單鏈表中的 p所指結(jié)點之前插入一個 s所指結(jié)點的操作。 6. 請利用鏈表來表示下面一元多項式 781194)( 3811 ????? xxxxxA?二、算法設(shè)計題 1. 有一個有 n個結(jié)點的單鏈表，設(shè)計一個函數(shù)將第 i1個結(jié)點與第 i個結(jié)點互換，但指針不變。 2. 設(shè)計一個函數(shù)，查找單鏈表中數(shù)值為 x的結(jié)點。 3. 已知一個單鏈表，編寫一個刪除其值為 x的結(jié)點的前趨結(jié)點的算法。 4. 已知一個單鏈表，編寫一個函數(shù)從此單鏈表中刪除自第 i個元素起的 length個元素。 5. 已知一個遞增有序的單鏈表，編寫一個函數(shù)向該單鏈表中插入一個元素為 x的結(jié)點，使插入后該鏈表仍然遞增有序。 6. 已知一個單鏈表，編寫一個函數(shù)將此單鏈表復(fù)制一個拷貝。 7. 有一個共 10個結(jié)點的單鏈表，試設(shè)計一個函數(shù)將此單鏈表分為兩個結(jié)點數(shù)相等的單鏈表。 8. 與上題相同的單鏈表，設(shè)計一個函數(shù)，將此單鏈表分成兩個單鏈表，要求其中一個仍以原表頭指針head1作表頭指針，表中順序包括原線性表的第一、三等奇數(shù)號結(jié)點；另一個鏈表以 head2為表頭指針，表中順序包括原單鏈表第二、四等號結(jié)點。 9. 已知一個指針 p指向單循環(huán)鏈表中的一個結(jié)點，編寫一個對此單循環(huán)鏈表進行遍歷的算法。 10. 已知一個單循環(huán)鏈表，編寫一個函數(shù)，將所有箭頭方向取反。 11. 在雙鏈表中，若僅知道指針 p指向某個結(jié)點，不知頭指針，能否根據(jù) p遍歷整個鏈表？若能，試設(shè)計算法實現(xiàn)。 12. 試編寫一個在循環(huán)雙向鏈表中進行刪除操作的算法，要求刪除的結(jié)點是指定結(jié)點 p的前趨結(jié)點。
法律信息相關(guān)推薦
鄂ICP備17016276號-1