PAGEPAGE6/62一、簡答題試描述頭指針、頭結點、開始結點的區別、并說明頭指針和頭結點的作用。【答】頭指針：是指向鏈表中的第一個結點的指針。頭結點：在開始結點之前附加上的一個結點。開始結點：鏈表的第一個結點。據元素。序表；當常常需要插入、刪除的時候，適合采用鏈表。【答】在單循環鏈表中，設置尾指針，可以更方便的判斷鏈表是否為空。4．在單鏈表、雙鏈表和單循環鏈表中，若僅知道指針p指向某結點，不知道頭指針，能否將結點*p從相應的鏈表中刪去?【答】本題分三種情況討論：1、單鏈表：當知道指針p指向某結點時，能夠根據該指針找到其直接后繼，但是不知道頭指針，因此不能找到該結點的直接前趨，因此，無法刪除該結點。2、雙鏈表：根據指針p可以找到該結點的直接前趨和直接后繼，因此，能夠刪除該結點。3、單循環鏈表：和雙鏈表類似，根據指針p也可以找到該結點的直接前趨和直接后繼，因此，也可以刪除該結點。5．下述算法的功能是什么?LinkListDemo(LinkList*L)/*L是無頭結點單鏈表*/{LNode*Q,*P;if(L&&L->next){Q=L;L=L->next;P=L;while(P->next)P=P->next;P->next=Q;Q->next=NULL;}returnL;}/*Demo*/【答】將原來的第一個結點變成末尾結點，原來的第二個結點變成鏈表的第一個結點。二、算法設計題(a0,a1,...an-1)就地逆置的操作，所謂"就地"指輔助空間應為O(1)。【答】分兩種情況討論如下。①順序表：點互換，如此反復，就可將整個表逆置了。算法如下：voidreverlist(sequenlist*L){datatypet;/*設置臨時空間用于存放data*/inti;for(i=0;i<L->length/2;i++){ t=L->data[i];/**/L->data[i]=L->data[L->length-1-i];L->data[L->length-1-i]=t;}}②鏈表：可以利用指針的指向轉換來達到表逆置的目的。算法是這樣的：LinkList*reverselist(LinkList*head)/*將head所指的單鏈表逆置*/{LNode*p,*q;/*設置兩個臨時指針變量*/if((head->next!=NULL)&&(head->next->next!=NULL))/*當鏈表不是空表或單結點時*/{p=head->next;q=p->next;p->next=NULL;將開始結點變成終端結點*/while(q)/*每次循環將后一個結點變成開始結點{p=q;q=q->next;p->next=head->next;head->next=p;}returnhead;}returnhead;/*如是空表或單結點表，直接返回head*/}順序表LxL中，并使L【答】因已知順序表L是遞增有序表，所以只要從頭找起找到第一個比它大（或相等）的結點數據，把x插入到這個數所在的位置就是了。算法如下：voidInsertIncreaseList(Sequenlist*L,Datatypex){inti;for(i=0;i<L->length&&L->data[i]<x;i++);/*查找并比較,分號不能少*/InsertList(L,x,i);/*調用順序表插入函數*/}順序表LxL【答】類似于第2題，讀者可自行完成，這里不在贅述。L1L2mn【答】算法如下：LinkList*Link(LinkList*L1,LinkList*L2){/*將兩個單鏈表連接在一起*/LNode*p,*q;p=L1;while(p->next)p=p->next;/*查找終端結點*/p->next=q->next;/*將L2的開始結點鏈接在L1之后*/returnL1;}本算法的主要操作時間花費在查找L1的終端結點上，與L2的長度無關，所以本算的法時間復雜度為：O(m)BAB值遞減有序的單鏈表C，并要求輔助空間為O(1)，請分析算法的時間復雜度。【答】根據已知條件，A和B是兩個遞增有序表，所以我們可以以A表為基礎，按照插入單個元素的辦法把B表的元素插入A表中，完成后，將表逆置就得到了一個按元素值遞減有序的單鏈表C了。算法如下：LinkList*MergeSort(LinkList*A,LinkList*B){/*歸并兩個遞增有序表為一個遞減有序表*/LNode*pa,*pb,*qa,*qb;pa=A;pb=B;qa=A->next;qb=B->next;while(qa{if(qb->data<qa->data){/*當B中的元素小于A中當前元素時，插入到它的前面*/pb=qb;qb=qb->next;/*指向B中下一元素*/pa->next=pb;pb->next=qa;pa=pb;}elseif(qb->data>=pa->data&&qb->data<=qa->data){/*當B中元素大于等于AA元素插入到A*/pa=qa;qa=qa->next; /*保存Apb=qb;qb=qb->next; /*保存B的后一元素位置a->next=pb; /*插入元素*/pb->next=qa;}else{/*如果B中元素總是更大,指針移向下一個A元素*/pa=qa;qa=qa->next;}}if(qb)/*如果A表已到終端而B表還有結點未插入*/{/*B表接到Apa->next=qb;}C=reverselist(A);調用前面所設計的逆置函數*/return C; /*返回新的單鏈表C,已是遞減排列}該算法的時間復雜度分析如下：算法中只有一個while循環，在這個循環中，按照最壞的情況是B元素既有插到A的最前的，也有插到最后的，也就是說需要把A中元素和B中元素全部檢查比較過，這時的所費時間就是m+n.而新鏈表的長度也是m+n+1(有頭結點)，這樣逆置函數的執行所費時間為m+n+1。所以可得整個算法的時間復雜度為：m+n+m+n+1=2(m+n)+1=O(m+n)6．已知由單鏈表表示的線性表中，含有三類字符的數據元素(如：字母字符、數字字符和其它字符)，試編寫算法構造三個以循環鏈表表示的線性表，使每個表中只含同一類的字符，且利用原表中的結點空間作為這三個表的結點空間，頭結點可另辟空間。【答】本題分為兩個部分，第一部分是刪除重復結點，第二部分鏈表的分解。首先看第一部分：要刪除重復結點，有兩種方式，第一種方式：先取開始結點中的重復上述過程直到最后一個結點。第二種方式：將單鏈表按值的大小排序，排好后的結點按相同的刪除。我們這里給出第一種方式的算法，如下所示：voidsc(LinkList*head){LinkList*p,*q,*w;p=head->next;while(p!=NULL){q=p->next;w=p;while(q!=NULL){/*比較p所指節點的值與鏈表中后續節點的值，不相等q指針后移,相等則刪除*/if(p->data!=q->data) {w=q;q=q->next;}else{w->next=q->next;w=q;q=q->next;}}p=p->next;}}中；以此類推，直到所有的節點都檢測完畢。具體算法如下：voidsplit(LinkList*ha){LinkList*hb,*hc,*ra,*rb,*rc,*p;charc;hb=(linklist*)malloc(sizeof(linklist));hc=(linklist*)malloc(sizeof(linklist));p=ha->next;ra=pa;ra->next=NULL;rb=hb;rb->next=NULL;rc=hc;rc->next=NULL;while(p!=ha){c=p->data;if((c>=‘a’&&c<=‘z’)||(c>=‘C’&&c<=‘Z’)){ra->next=p;ra=p;}elseif(c>=‘0’&&c<=‘9’{rb->next=p;rb=p;}else{rc->next=p;rc=p;}p=p-