【正文】 用于存儲線性結(jié)構。a1稱為_第一個_結(jié)點，an稱為__最后一個_結(jié)點，i稱為ai在線性表中的_位置__。2．線性結(jié)構的基本特征是：若至少含有一個結(jié)點，則除起始結(jié)點沒有直接__前驅(qū)_外，其他結(jié)點有且僅有一個直接__前驅(qū)_；除終端結(jié)點沒有直接__后繼_外，其他結(jié)點有且僅有一個直接_后繼__。4．線性表的邏輯結(jié)構是__線性_結(jié)構，其所含結(jié)點的個數(shù)稱為線性表的___長度_。6．非空的單循環(huán)鏈表head的尾結(jié)點(由指針p所指)滿足__ pnext= head _____。8．對于一個具有n個結(jié)點的單鏈表，在p所指結(jié)點后插入一個結(jié)點的時間復雜度為__O(1)__，在給定值為x的結(jié)點后插入新結(jié)點的時間復雜度為__ O(n)__。10．在順序表中插入或刪除一個元素，平均需要移動_一半_元素，具體移動的元素個數(shù)與__元素的位置_有關。12．在一個長度為n的向量中刪除第i(1≤i≤n)個元素時，需向前移動__ ni __個元素。14．在一個帶頭結(jié)點的單循環(huán)鏈表中，p指向尾結(jié)點的直接前驅(qū)，則指向頭結(jié)點的指針head可用p表示為head=__ pnextnext ；___。16．在單鏈表中，若p和s是兩個指針，且滿足pnext與s相同，則語句pnext=snext的作用是_刪除__s指向的結(jié)點。19．在雙循環(huán)鏈表中，若要在指p所指結(jié)點前插入s所指的結(jié)點，則需執(zhí)行下列語句：snext=p； sprior=pprior；__ ppriornext __=s；pprior=s；20．在單鏈表中，若要在p所指結(jié)點之前插入s所指的結(jié)點，可進行下列操作： snext=___ pnext __； pnext=s； temp=pdata； pdata=__ sdata ___； sdata=__ temp _；四、應用題1．描述以下三個概念的區(qū)別：頭指針，頭結(jié)點，首元結(jié)點(第一個元素結(jié)點)。為了操作方便，通常在鏈表的首元結(jié)點之前附設一個結(jié)點，稱為頭結(jié)點。2．何時選用順序表，何時選用鏈表作為線性表的存儲結(jié)構為宜？答：從空間上來看，當線性表的長度變化較大、難以估計其規(guī)模時，選用動態(tài)的鏈表作為存儲結(jié)構比較合適，但鏈表除了需要設置數(shù)據(jù)域外，還要額外設置指針域，因此當線性表長度變化不大、易于事先確定規(guī)模時，為了節(jié)約存儲空間，宜采用順序存儲結(jié)構。對于頻繁進行插入和刪除操作的線性表，宜采用鏈表作為存儲結(jié)構。具體移動的次數(shù)取決于表長和插入、刪除的結(jié)點的位置。但若設置的是頭指針，表尾進行插入或刪除操作，需要遍歷整個鏈表，時間復雜度為O(n)。雙鏈表上刪除p所指向的結(jié)點的時間復雜度為O(1)，單循環(huán)鏈表上刪除p所指向的結(jié)點的時間復雜度為O(n)。amp。 while(pnext) p=pnext； pnext=q。7．如果有n個線性表同時共存，并且在處理過程中各表的長度會發(fā)生動態(tài)變化，線性表的總長度也會自動地改變。因為順序表是靜態(tài)存儲結(jié)構，只能預先分配，不能隨著線性表長度的改變而變化。8．若線性表的總數(shù)基本穩(wěn)定，且很少進行插入、刪除操作，但要求以最快的方式存取線性表的元素，應該用哪種存儲結(jié)構？為什么？答：應選用順序存儲結(jié)構。五、算法設計題假設算法中用到的順序表和鏈表結(jié)構如下：define maxsize 100。 int length } SeqList。 struct node2 *next } LinkedList 。答：(1)順序表的就地逆置 分析：分別用兩個整型變量指向順序表的兩端，同時向中間移動，移動的同時互換兩個下標指示的元素的值。 Ldata[i]=[j]。 } } (2)鏈表的就地逆置 分析：本算法的思想是逐個地把L的當前元素r插入到新的鏈表頭部。答：分析：先找到x的正確插入位置，然后將大于x的元素從后向前依次向下移動，最后將x插入到其位置上，同時順序表長度增1。 while((i=Llength1)amp。(x=Ldata[i])) i++； ／／找正確的插入位置for(k=Llength1。答：分析：此問題的關鍵是在鏈表中找到x的插入位置，因此需要兩個指針一前一后地依次向后移動。amp。答：分析：對不帶頭結(jié)點的鏈表操作時，要注意對第一個結(jié)點和其他結(jié)點操作的不同。 while(p!=NULLamp。ji1) ／／找到第i1個元素 {p=p—next；j++；} if(i=0||p==NULL) printf(”插入位置不正確＼n”)； else {q=(LinkedList*)malloc(sizeof(LinkedList))；q—data=x； if(i==1) {q—next=L；L=q；} ／／在第一個元素之前插入 else{q—next=p—next；p—next=q；} ／／在其他位置插入 } }5．設A、B是兩個線性表，其表中元素遞增有序，長度分別為m和n。答：(1)分析：用三個變量i、j、k分別指示A、B、C三個順序表的當前位置，將A、B表中較小的元素寫入C中，直到有一個表先結(jié)束。SeqList *Seqmerge(SeqList A，SeqList B，SeqList *C){／／有序順序表A和B歸并成有序順序表C i=0；j=0；k=0； ／／i，i，k分別為順序表A，B，C的下標 while(imamp。jn) {if([i][j]) ／／A中當前元素較小 {Cdata[k]=[il；i++； ] else {Cdata[k]=[j]。k++；} ／／B表長度大于A表 else for(t=i；tm；t++) {Cdata[k]=[t]；k++；} ／／A表長度大于B表 Clength=m+n； return C。amp。6．設指針la和lb分別指向兩個不帶頭結(jié)點的單鏈表的首結(jié)點，設計從表la中刪除第i個元素起共len個元素，并將這些元素插入到lb中第j個結(jié)點之前的算法。然后在lb中找到第j個結(jié)點，將p所指向的la表中的第i個及q所指向的最后一個共len個結(jié)點插入到lb中。amp。 k++； } if(!p) exit(0)； q=p；k=l； ／／p指向la表中第i個結(jié)點 while(qamp。klen) {q=q—next； k++；} ／／查找la表中第i+len1個結(jié)點 if(!q) exit(0)； if(pre==la) la=q—next； ／／i=1的情況 else pre—next=q—next； ／／完成刪除 ／／將從la中刪除的結(jié)點插入到lb中 if(j==1) {qnext=lb； lb=p； } ／／j=1時 else { r=lb。amp。答：LinkedList delete(LinkedList *L，int min，int max) {／／刪除遞減有序單鏈表L中值大于min且小于max的結(jié)點 q=L； if(minmax) {printf(”minmax＼n”)；exit(0)；} else p=L—next； ／／q始終指向p的前驅(qū)while(p—data=max) ／／當前元素大于或等于max，則p、q依次向后移動 {q=p；p=p—next；} while((p!=NULL)amp。(p一datamin)) {／／當前元素的值比min大同時比max小，刪除p指向的結(jié)點 q—next=p—next， free(p)；p=q—next； } return L； }．8．編寫一個算法將一個頭結(jié)點指針為pa的單鏈表A分解成兩個單鏈表A和B，其頭結(jié)點指針分別為pa和pb，使得A鏈表中含有原鏈表A中序號為奇數(shù)的元素，而B鏈表中含有原鏈表A中序號為偶數(shù)的元素，且保持原來的相對順序。void depose(LinkedList *A，LinkedList *B){／／單鏈表A分解成元素序號為奇數(shù)的單鏈表A和元素序號為偶數(shù)的單鏈表B p=Anext； B=(LinkedList*)malloc(sizeof(LinkedList))； r=B； while(p!=NULLamp。pnext!=NULL) {q=p—next； ／／q指向偶數(shù)序號的結(jié)點 p—next=q—next； ／／將q從A表中刪除 r—next=q； ／／將q結(jié)點鏈接到B鏈表的末尾 r=q； ／／r總是指向B鏈表的最后—用順序表實現(xiàn)并寫出C的算法。SeqLiSt *intersection(SeqList A，SeqList B，SeqList *C){／／求元素依值遞增有序排列的順序表A、B的交集C i=0； j=0；k=0； while((i=)amp。(j=)) {if([i]==[j]) ／／找到值相同的元素 {Cdata[k]=[i]； ／／相同元素寫入C表中 k++；i++；j++； } else if([i][j]) i++；／／A、B表當前元素不等，值較小的下標增1 else j++； } Clength=k； return C； }11．假設在長度大于1的單循環(huán)鏈表中，既無頭結(jié)點也無頭指針。答：分析：因為既不知道此單循環(huán)鏈表的頭指針，也不知道其尾指針，所以找s的前驅(qū)就只能從s開始，順次向后尋找。答：int number(Linkedlist *head) {／／計算單循環(huán)鏈表中結(jié)點的個數(shù) p=head—next； i=0； while(p!=head) {i++；p=pnext；} return i； }13．已知由單鏈表表示的線性表中，含有三類字符的數(shù)據(jù)元素(如：字母字符、數(shù)字字符和其他字符)，試編寫算法構造三個以循環(huán)鏈表表示的線性表，使得每個表中只含有同一類的字符，且利用原表中的結(jié)點空間作為這三個表的結(jié)點空間，頭結(jié)點可另辟空間。q指向p的下一個結(jié)點，根據(jù)*p的數(shù)據(jù)域的值將其插入到不同的鏈表上。void change(LinkedList *L，LinkedList *pa，LinkedList *pb，LinkedList *pc){／／分解含有三類字符的單鏈表為三個以循環(huán)鏈表表示的線性表，使其分別含有三類字符 p=L—next； pa=L； pa—next=pa； ／／分別構造三個單循環(huán)鏈表 pb=(LinkedList*)malloc(sizeof(LinkedList))； pc=(LinkedList*)malloc(sizeof(LinkedList))； pb—next=pb；pc—next=pc； while(p!=L) {q=p—next；amp。amp。試對順序表編寫實現(xiàn)上述操作的算法(注：題中未特別指明同一表中的元素值各不相同)。 ／／i指示A中元素原來的位置，m為移動后的位置 while(iAlengthamp。iamp。k) {if([j][k]) j++； else if([j][k]) k++。amp。amp。 i++；／／跳過相同的元素 } } while(iAlength) Adata[m++]=Adata[i++]； ／／A的剩余元素重新存儲 A1ength=m； }15．雙循環(huán)鏈表中，設計滿足下列條件的算法。(2)刪除值為x的結(jié)點。typedef struct Node {DataType data； struct Node *prior，*next；}DLNode，*DLinkedList；void DLinsertl(DLinkedList L，int x，int y){ ／／在雙循環(huán)鏈表中插入結(jié)點p=Lnext； while(p!=Lamp。pdata!=x) p=pnext； ／／在鏈表中查找值為x的結(jié)點 if(pdata==x) ／／找到值為x的結(jié)點 {q=pprior； ／／q指向值為x的結(jié)點的前驅(qū) s=(DLinkedList)malloc(sizeof(DLNode))； sdata=y； snext=p； sprior=q； ／／將y插入到q與p指向的結(jié)點之間 pprior=s；qnext=s； } else{printf(”沒有值為x的結(jié)點”)；exit(0)；} }void DLDelete(DLinkedList L，int x){／／在雙循環(huán)鏈表中刪除結(jié)點 p=Lnext； while(p!=Lamp。pdata!=x)p=pnext； if(pdata==x) {ppriornext=pnext；pnextprior=pprior；free(p)；} else{printf(”沒有值為x的結(jié)點”)；exit(0)；}}16．設有一個雙循環(huán)鏈表，其中有一結(jié)點的指針為p，編寫算法將p與其右邊的一個結(jié)點進行交換。每當鏈表進行一次LocateNode(L，x)操作時令元素值為x的結(jié)點中freq域的值加l，并調(diào)整表中結(jié)