算法與數(shù)據(jù)結(jié)構(gòu) C語言版 第二版 (陳守孔 孟佳娜 武秀川 著) 機械工業(yè)出版社課后答案 第2章 線性表

第2章 線性表 一、基礎(chǔ)知識題2.1 試述頭指針、頭結(jié)點、元素結(jié)點、首元結(jié)點的區(qū)別，說明頭指針和頭結(jié)點的作【解答】指向鏈表第一個結(jié)點（或為頭結(jié)點或為首元結(jié)點）的指針稱為頭指針。“頭指針”具有標(biāo)識一個鏈表的作用，所以經(jīng)常用頭指針代表鏈表的名字，如鏈表L既是指鏈表的名字是L，也是指鏈表的第一個結(jié)點的地址存儲在指針變量L中，頭指針為“NULL”則表示一個空表。有時，我們在整個線性鏈表的第一個元素結(jié)點之前加入一個結(jié)點，稱為頭結(jié)點，它的數(shù)據(jù)域可以不存儲任何信息（也可以做監(jiān)視哨或存放線性表的長度等附加信息），指針域中存放的是第一個數(shù)據(jù)結(jié)點的地址，空表時為空。 “頭結(jié)點”的加入，使插入和刪除等操作方便統(tǒng)一。元素結(jié)點即是數(shù)據(jù)結(jié)點，至少包括元素自身信息和其后繼元素的地址兩個域。首元結(jié)點是指鏈表中第一個數(shù)據(jù)元素的結(jié)點；為了操作方便，通常在鏈表的首元結(jié)點之前附設(shè)一個結(jié)點，稱為頭結(jié)點。 2.2分析順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)的優(yōu)缺點，說明何時應(yīng)該利用何種結(jié)構(gòu)?！窘獯稹繌目臻g上來看，當(dāng)線性表的長度變化較大，難以估計其規(guī)模時，選用動態(tài)的鏈表作為存儲結(jié)構(gòu)比較合適，但鏈表除了需要設(shè)置數(shù)據(jù)域外，還要額外設(shè)置指針域，因此當(dāng)線性表長度變化不大，易于事先確定規(guī)模時，為了節(jié)約存儲空間，宜采用順序存儲結(jié)構(gòu)。從時間上看，順序表具有按元素序號隨機訪問的特點，在順序表中按序號訪問數(shù)據(jù)元素的時間復(fù)雜度為O(1)；而鏈表中按序號訪問的時間復(fù)雜度為O(n)。所以如果經(jīng)常按序號訪問數(shù)據(jù)元素，使用順序表優(yōu)于鏈表。在順序表中做插入刪除操作時，平均移動大約表中一半的元素，因此n較大時順序表的插入和刪除效率低。在鏈表中作插入、刪除，雖然也要找插入位置，但操作主要是比較操作。從這個角度考慮顯然鏈表優(yōu)于順序表?？傊?，兩種存儲結(jié)構(gòu)各有長短，選擇那一種存儲結(jié)構(gòu)，由實際問題中的主要因素決定。 2.3 分析在順序存儲結(jié)構(gòu)下插入和刪除結(jié)點時平均需要移動多少個結(jié)點?！窘獯稹科骄苿颖碇写蠹s一半的結(jié)點，插入操作平均移動 個結(jié)點，刪除操作平均移動 個結(jié)點。具體移動的次數(shù)取決于表長和插入、刪除的結(jié)點的位置。 2.4 為什么在單循環(huán)鏈表中常使用尾指針，若只設(shè)頭指針，插入元素的時間復(fù)雜度如何？【解答】單循環(huán)鏈表中無論設(shè)置尾指針還是頭指針都可以遍歷表中任一個結(jié)點。設(shè)置尾指針時，若在表尾進行插入元素或刪除第一元素，操作可在O(1)時間內(nèi)完成；若只設(shè)置頭指針，表尾進行插入或刪除操作，需要遍歷整個鏈表，時間復(fù)雜度為O(n)。 2.5 在單鏈表、雙鏈表、單循環(huán)鏈表中，若知道指針p指向某結(jié)點，能否刪除該結(jié)點，時間復(fù)雜度如何？【解答：】以上三種鏈表中，若知道指針p指向某結(jié)點，都能刪除該結(jié)點。雙鏈表刪除p所指向的結(jié)點的時間復(fù)雜度為O(1)，而單鏈表和單循環(huán)鏈表上刪除p所指向的結(jié)點的時間復(fù)雜度均為O(n)。 2.6 下面算法的功能是什么？LinkedList Unknown(LinkedList la) LNode *q，*p; if(la && la->next) q=la; la=la->next; p=la; while(p->next) p=p->next; p->next=q; q->next=null; return la; 【解答】將首元結(jié)點刪除并插入到表尾（設(shè)鏈表長度大于1）。 2.7 選擇題：在循環(huán)雙鏈表的*p結(jié)點之后插入*s結(jié)點的操作是（ ）la、p->next=s; s->prior=p; p->next->prior=s; s->next=p->next;B、p->next=s; p->next->prior=s; s->prior=p; s->next=p->next;lc、s->prior=p; s->next=p->next; p->next:=s; p->next->prior=s; D、s->prior=p; s>next=p>next; p>next->prior =s; p->next=s; 【解答】D 2.8 選擇題：若某線性表最常用的操作是存取任一指定序號的元素和在最后進行插入和刪除運算，則利用（ ）存儲方式最節(jié)省時間。la順序表 B雙鏈表 lc帶頭結(jié)點的雙循環(huán)鏈表 D單循環(huán)鏈表【解答】la 二、算法設(shè)計題2.9 設(shè)ha和hb分別是兩個帶頭結(jié)點的非遞減有序單鏈表的頭指針，試設(shè)計算法， 將這兩個有序鏈表合并成一個非遞增有序的單鏈表。要求使用原鏈表空間，表中無重復(fù)數(shù)據(jù)。【題目分析】因為兩鏈表已按元素值非遞減次序排列，將其合并時，均從第一個結(jié)點起進行比較，將小的鏈入鏈表中，同時后移鏈表工作指針，若遇值相同的元素，則刪除之。該問題要求結(jié)果鏈表按元素值非遞增次序排列，故在合并的同時，將鏈表結(jié)點逆置。LinkedList Union(LinkedList ha,hb) ha,hb分別是帶頭結(jié)點的兩個單鏈表的頭指針，鏈表中的元素值按遞增序排列本算法將兩鏈表合并成一個按元素值遞減次序排列的單鏈表,并刪除重復(fù)元素 pa=ha->next; pa是鏈表ha的工作指針pb=hb->next; pb是鏈表hb的工作指針 ha->next=null; ha作結(jié)果鏈表的頭指針，先將結(jié)果鏈表初始化為空 while(pa!=null && pb!=null) 當(dāng)兩鏈表均不為空時作 while(pa->next && pa->data=pa->next->data) u=pa->next; pa->next=u->next; free(u)刪除pa鏈表中的重復(fù)元素while(pb->next && pb->data=pb->next->data) u=pb->next; pb->next=u->next; free(u)刪除pb鏈表中的重復(fù)元素 if(pa->data<pb->data) r=pa->next; 將pa 的后繼結(jié)點暫存于r pa->next=ha->next; 將pa結(jié)點鏈于結(jié)果表中，同時逆置ha->next=pa;pa=r; 恢復(fù)pa為當(dāng)前待比較結(jié)點 else if(pb->data<pa->data)r=pb->next; 將pb 的后繼結(jié)點暫存于rpb->next=ha->next; 將pb結(jié)點鏈于結(jié)果表中，同時逆置ha->next=pb;pb=r; 恢復(fù)pb為當(dāng)前待比較結(jié)點 elseu=pb;pb=pb->next;free(u)刪除鏈表pb和pa中的重復(fù)元素 / while(pa!=null && pb!=null) if(pa) pb=pa; 避免再對pa寫下面的while語句 while(pb!=null) 將尚未到尾的表逆置到結(jié)果表中 r=pb->next; pb->next=ha->next; ha->next=pb; pb=r; return ha 算法Union結(jié)束 2.10              設(shè)la是一個雙向循環(huán)鏈表，其表中元素遞增有序。試寫一算法插入元素x，使表中元素依然遞增有序?！締栴}分析】雙向鏈表的插入與單鏈表類似，但需修改雙向指針。 DLinkedList DInsert(DLinkedList la, ElemType x) 在遞增有序的雙向循環(huán)鏈表la中插入元素x，使表中元素依然遞增有序 p=la->next; p指向第一元素 la->data=MaxElemType;MaxElemType是和x同類型的機器最大值，用做監(jiān)視哨 while(p->data<x) 尋找插入位置 p=p->next  s=(DLNode *)malloc(sizeof(DLNode);申請結(jié)點空間 s->data=x; s->prior=p->prior; s->next=p; 將插入結(jié)點鏈入鏈表p->prior->next=s; p->prior=s; 2.11              設(shè)p指向頭指針為la的單鏈表中某結(jié)點，試編寫算法，刪除結(jié)點*p的直接前驅(qū)結(jié)點?！绢}目分析】設(shè)*p是單鏈表中某結(jié)點，刪除結(jié)點*p的直接前驅(qū)結(jié)點，要找到*p的前驅(qū)結(jié)點的前驅(qū)*pre。進行如下操作：u=pre->next; pre->next=u->next;free(u);LinkedList LinkedListDel(LinkedList la，LNode *p)刪除單鏈表la上的結(jié)點*p的直接前驅(qū)結(jié)點,假定*p存在pre=la; if(pre-next=p) printf(“*p是鏈表第一結(jié)點，無前驅(qū)n”)  exit(0)  while(pre->next->next !=p) pre=pre->next;u=pre->next; pre->next=u->next; free(u);return(la); 2.12              設(shè)計一算法，將一個用循環(huán)鏈表表示的稀疏多項式分解成兩個多項式，使這兩個多項式各自僅有奇次冪或偶次冪項，并要求利用原鏈表中的結(jié)點空間來構(gòu)造這兩個鏈表。【題目分析】設(shè)循環(huán)鏈表表示的多項式的結(jié)點結(jié)構(gòu)為： typedef struct node int power; 冪 float coef; 系數(shù) ElemType other; 其他信息 struct node *next; 指向后繼的指針 PNode,*PolyLinkedList;則可以從第一個結(jié)點開始，根據(jù)結(jié)點的冪是奇數(shù)或偶數(shù)而將其插入到奇次冪或偶次冪項的鏈表中。假定用原鏈表保存偶次冪，要為奇次冪的鏈表生成一個表頭，為了保持鏈表中結(jié)點的原來順序，用一個指針指向奇次冪鏈表的表尾，注意鏈表分解時不能“斷鏈”。void PolyDis(PolyLinkedList poly)將poly表示的多項式鏈表分解為各含奇次冪或偶次冪項的兩個循環(huán)鏈表PolyLinkedList poly2=(PolyLinkedList)malloc(sizeof(PNode); poly2表示只含奇次冪的多項式 r2=poly2; r2是只含奇次冪的多項式鏈表的尾指針 r1=poly; r1是只含偶次冪的多項式鏈表當(dāng)前結(jié)點的前驅(qū)結(jié)點的指針 p=poly->next; 鏈表帶頭結(jié)點，p指向第一個元素 while(p!=poly) if(p->power % 2)處理奇次冪 r=p->next; 暫存后繼 r2->next=p; 結(jié)點鏈入奇次冪鏈表r2=p; 尾指針后移 p=r; 恢復(fù)當(dāng)前待處理結(jié)點 else 處理偶次冪 r1->next=p; r1=p; p=p->next; r->next=poly2; r1->next=poly; 構(gòu)成循環(huán)鏈表 PolyDis 2.13              以帶頭結(jié)點的雙向鏈表表示的線性表L=(a1，a2，an)，試寫一時間復(fù)雜度為O(n)的算法，將L改造為L=(a1，a3，an，a4，a2)?！绢}目分析】分析結(jié)果鏈表，易見鏈表中位置是奇數(shù)的結(jié)點保持原順序，而位置是偶數(shù)的結(jié)點移到奇數(shù)結(jié)點之后，且以與原來相反的順序存放。因此，可從鏈表第一個結(jié)點開始處理，位置是奇數(shù)的結(jié)點保留不動，位置是偶數(shù)的結(jié)點插入到鏈表尾部，并用一指針指向鏈表尾，以便對偶數(shù)結(jié)點“尾插入”。DLinkedList DInvert(DLinkedList L) 將雙向循環(huán)鏈表L位置是偶數(shù)的結(jié)點逆置插入到鏈表尾部 p=L->next; p指向第一元素 Q=p->prior; Q指向最后一個元素 pre=L  pre指向鏈表中位置為奇數(shù)的結(jié)點的前驅(qū) r=L  r指向鏈表中偶數(shù)結(jié)點的尾結(jié)點 i=0  i記錄結(jié)點序號 while(p != Q) 尋找插入位置 i+ if(i%2) 處理序號為奇數(shù)的結(jié)點p->prior=pre pre->next=p pre=p; p=p->next;else 處理序號為偶數(shù)的結(jié)點 u=p  記住當(dāng)前結(jié)點 p=p->next p指向下個待處理結(jié)點 u->prior=r->prior; 以下4個語句將結(jié)點插入鏈表尾 u->next=r; r->prior->next=u; r->prior=u; r=u; 指向新的表尾 2.14              設(shè)單向鏈表的頭指針為head，試設(shè)計算法，將鏈表按遞增的順序就地排序?！绢}目分析】本題中的“就地排序”，可理解為不另辟空間，這里利用直接插入原則把鏈表整理成遞增有序鏈表。LinkedList LinkListInsertSort(LinkedList head) head是帶頭結(jié)點的單鏈表，本算法利用直接插入原則將鏈表整理成遞增的有序鏈表 if(head->next!=null) 鏈表不為空表 p=head->next->next; p指向第一結(jié)點的后繼head->next->next=null;直接插入原則認為第一元素有序，然后從第二元素起依次插入while(p!=null) r=p->next; 暫存p的后繼 q=head; while(q->next && q->next->data<p->data)q=q->next;查找插入位置 p->next=q->next; 將p結(jié)點鏈入鏈表 q->next=p; p=r;  2.15              已知遞增有序的三個單鏈表分別代表集合A，B和C，設(shè)計算法實現(xiàn)A=A（BC），并使結(jié)果鏈表仍保持遞增。要求算法的時間復(fù)雜度為O(|A|+|B|+|C|)。其中，|A|為集合A的元素個數(shù)?！绢}目分析】本題首先求B和C的交集，即求B和C中共有元素，再與A求并集，同時刪除重復(fù)元素，以保持結(jié)果A遞增。LinkedList union(LinkedList A,B,C)A、B和C均是帶頭結(jié)點的遞增有序的單鏈表,本算法實現(xiàn)A=A(BC)使結(jié)果表A保持遞增有序pa=A->next;pb=B->next;pc=C->next;設(shè)置三個工作指針 pre=A; pre指向結(jié)果鏈表中當(dāng)前待合并結(jié)點的前驅(qū) A->data=MaxElemType;同類型元素最大值，起監(jiān)視哨作用while(pa | pb && pc) while(pb && pc) if(pb->data<pc->data) pb=pb->next; else if(pb->data>pc->data) pc=pc->next; else break; B表和C表有公共元素 if(pb && pc) while(pa && pa->data<pb->data)先將A中小于B，C公共元素部分鏈入 pre->next=pa;pre=pa;pa=pa->next; if(pre->data!=pb->data)pre->next=pb;pre=pb;pb=pb->next;pc=pc->next; elsepb=pb->next;pc=pc->next; 若A中已有B，C公共元素，則不再存入結(jié)果表 while(pa|pb&&pc) if(pa) pre->next=pa;else pre->next=null; 當(dāng)B，C無公共元素，將A中剩余鏈入算法Union結(jié)束 2.16              順序表la與lb非遞減有序，順序表空間足夠大。試設(shè)計一種高效算法，將lb中元素合到la中，使新的la的元素仍保持非遞減有序。高效指最大限度地避免移動元素?！绢}目分析】順序存儲結(jié)構(gòu)的線性表的插入，其時間復(fù)雜度為O(n)，平均移動近一半的元素。線性表la和lb合并時，若從第一個元素開始，一定會造成元素后移，這不符合本題“高效算法”的要求。應(yīng)從線性表的最后一個元素開始比較，大者放到最終位置上。設(shè)兩線性表的長度各為m和n ，則結(jié)果表的最后一個元素應(yīng)在m+n位置上。這樣從后向前，直到第一個元素為止。SeqList Union(SeqList la, SeqList lb)la和lb是順序存儲的非遞減有序線性表，本算法將lb合并到la中，元素仍非遞減有序 m=la.last;n=lb.last;m，n分別為線性表la和lb的長度 k=m+n-1; k為結(jié)果線性表的工作指針（下標(biāo)） i=m-1;j=n-1; i，j分別為線性表la和lb的工作指針（下標(biāo)） while(i>=0 && j>=0) if(la.datai>=lb.dataj) la.datak-=la.datai-; else la.datak-=lb.dataj-; while(j>=0) la.datak-=lb.dataj-; la.last=m+n; return la; 【算法討論】算法中數(shù)據(jù)移動是主要操作。在最佳情況下（lb的最小元素大于la的最大元素），僅將lb的n個元素移（拷貝）到la中，時間復(fù)雜度為O（n），最差情況，la的所有元素都要移動，時間復(fù)雜度為O（m+n）。因數(shù)據(jù)合并到la中，所以在退出第一個while循環(huán)后，只需要一個while循環(huán)，處理lb中剩余元素。第二個循環(huán)只有在lb有剩余元素時才執(zhí)行，而在la有剩余元素時不執(zhí)行。本算法 “最大限度的避免移動元素”，是“一種高效算法”。 2.17              已知非空線性鏈表由head指出，試寫一算法，將鏈表中數(shù)據(jù)域值最小的那個結(jié)點移到鏈表的最前面。要求：不得額外申請新的鏈結(jié)點?！绢}目分析】 本題要求將鏈表中數(shù)據(jù)域值最小的結(jié)點移到鏈表的最前面。首先要查找最小值結(jié)點。將其移到鏈表最前面，實質(zhì)上是將該結(jié)點從鏈表上摘下（不是刪除并回收空間），再插入到鏈表的最前面。LinkedList Delinsert(LinkedList head）本算法將非空線性鏈表head中數(shù)據(jù)域值最小的那個結(jié)點移到鏈表的最前面p=head->next；p是鏈表的工作指針pre=head； pre指向鏈表中數(shù)據(jù)域最小值結(jié)點的前驅(qū)q=p； q指向數(shù)據(jù)域最小值結(jié)點，初始假定是第一結(jié)點while （p->next） if（p->next->data<q->data）pre=p；q=p->next； 找到新的最小值結(jié)點 p=p->next； if(q!=head->next) 若最小值是第一元素結(jié)點，則不需再操作pre->next=q->next； 將最小值結(jié)點從鏈表上摘下q->next=head->next； 將q結(jié)點插到鏈表最前面head->next=q； Delinsert 2.18 設(shè)la是帶頭結(jié)點的非循環(huán)雙向鏈表的指針，其結(jié)點中除有prior，data和next外，還有一訪問頻度域freq，其值在鏈表初始使用時為0。當(dāng)在鏈表中進行ListLocate(la，x)運算時，若查找失敗，則在表尾插入值為x的結(jié)點；若查找成功，值為x的結(jié)點的freq值增1，并要求鏈表按freq域值非增（遞減）的順序排列，且最近訪問的結(jié)點排在頻度相同的結(jié)點的后面，使頻繁訪問的結(jié)點總是靠近表頭。試編寫符合上述要求的ListLocate(la，x)運算的算法，返回找到結(jié)點的指針。 【題目分析】首先在雙向鏈表中查找數(shù)據(jù)值為x的結(jié)點，查到后，將結(jié)點從鏈表上摘下，然后再順結(jié)點的前驅(qū)鏈查找該結(jié)點的位置。 DLinkList ListLocate(DLinkedList L，ElemType x) L是帶頭結(jié)點的按訪問頻度遞減的雙向鏈表,本算法先查找數(shù)據(jù)x查找成功時結(jié)點的訪問頻度域增1，最后將該結(jié)點按頻度遞減插入鏈表中DLinkList p=L->next,q; p為L表的工作指針，q為p的前驅(qū)，用于查找插入位置 while(p && p->data!=x) p=p->next; 查找值為x的結(jié)點 if(!p) printf(“不存在所查結(jié)點n”); exit(0); else p->freq+; 令元素值為x的結(jié)點的freq域加1 p->next->prior=p->prior; 將p結(jié)點從鏈表上摘下 p->prior->next=p->next;q=p->prior; 以下查找p結(jié)點的插入位置 while(q !=L && q->freq<p->freq) q=q->prior; p->next=q->next; q->next->prior=p; 將p結(jié)點插入 p->prior=q; q->next=p； return(p); 返回值為x的結(jié)點的指針 算法結(jié)束  2.19              三個帶頭結(jié)點的線性鏈表la、lb和lc中的結(jié)點均依元素值自小至大非遞減排列（可能存在兩個以上值相同的結(jié)點），編寫算法對la表進行如下操作：使操作后的la中僅留下三個表中均包含的數(shù)據(jù)元素的結(jié)點，且沒有值相同的結(jié)點，并釋放所有無用結(jié)點。限定算法的時間復(fù)雜度為O（m+n+p），其中m、n和p分別為三個表的長度。【題目分析】 留下三個鏈表中公共數(shù)據(jù)，首先查找兩表la和B中公共數(shù)據(jù)，再去lc中找有無該數(shù)據(jù)。要消除重復(fù)元素，應(yīng)記住前驅(qū)，要求時間復(fù)雜度O（m+n+p），在查找每個鏈表時，指針不能回溯。LinkedList lcommon（LinkedList la，lb，lc）本算法使la表留下la、lb和lc三個非遞減有序表共同結(jié)點，無重復(fù)元素pa=la->next；pb=lb->next；pc=lc->next；pa,pb和pc分別是la,lb和lc三個表的工作指針pre=la；la->data=MaxElemType pre是la表當(dāng)前結(jié)點的前驅(qū)結(jié)點的指針,頭結(jié)點作監(jiān)視哨while（pa && pb && pc） 當(dāng)la,lb和lc表均不空時，查找三表共同元素 while(pa&&pa->data=pre->data) u=pa; pa=pa->next; free(u);/刪la中相同元素while（pb && pc） if（pb->data<pc->data）pb=pb->next; 結(jié)點元素值小時，后移指針 else if（pb->data>pc->data）pc=pc->next； else break ;處理lb和lc表元素值相等的結(jié)點 if(pb && pc)while（pa && pa->data<pc->data）u=pa；pa=pa->next；free（u）； if(pa && pa->data>pc->data)pb=pb->next; pc=pc->next; else if(pa && pa->data=pc->data)pc，pa和pb對應(yīng)結(jié)點元素值相等 pre->next=pa；pre=pa；pa=pa->next；將新結(jié)點鏈入la表 pb=pb->next；pc=pc->next； 鏈表的工作指針后移 pc，pa和pb對應(yīng)結(jié)點元素值相等 while（pa && pb && pc）pre->next=null； 置新la表表尾while（pa!=null） 刪除原la表剩余元素。u=pa；pa=pa->next；free（u）； 算法結(jié)束【算法討論】 算法中l(wèi)a表、lb表和lc表均從頭到尾（嚴格說lb、lc中最多一個到尾）遍歷一遍，算法時間復(fù)雜度符合O（m+n+p）。算法主要由while（pa && pb && pc）控制。三表有一個到尾則結(jié)束循環(huán)。要注意頭結(jié)點的監(jiān)視哨的作用，否則第一個結(jié)點要特殊處理。算法最后要給新la表置結(jié)尾標(biāo)記，同時若原la表沒到尾，還應(yīng)釋放剩余結(jié)點所占的存儲空間。