數(shù)據(jù)結(jié)構(gòu)第二章 線性表part9

1、 2-2 已知一個順序表中的元素按元素值非遞減已知一個順序表中的元素按元素值非遞減有序排列，編寫一個函數(shù)刪除表中多余的值相同有序排列，編寫一個函數(shù)刪除表中多余的值相同的元素。的元素。算法思想：算法思想： 由于順序表中的元素按元素值非遞減有序排由于順序表中的元素按元素值非遞減有序排列，值相同的元素必為相鄰的元素。列，值相同的元素必為相鄰的元素。 因此，依次比較相鄰兩個元素，若值相等，因此，依次比較相鄰兩個元素，若值相等，則刪除其中一個，否則繼續(xù)向后查找。則刪除其中一個，否則繼續(xù)向后查找。實現(xiàn)本題功能的函數(shù)如下：實現(xiàn)本題功能的函數(shù)如下：void del (SqList A, int n) / 表長

2、為表長為n int i=0, j; while (in-2) if (Ai!=Ai+1) i+ ; / 元素值不相等，繼續(xù)向下找元素值不相等，繼續(xù)向下找 else for (j=(i+2);j=n;j+) Aj-1=Aj; / 刪除第刪除第i+1個元素個元素 n-; / 表長減表長減1 2-3 已知一個順序表已知一個順序表A中有中有n個元素，且任何元個元素，且任何元素均不為素均不為0，將，將A拆成兩個線性表拆成兩個線性表B和和C，使，使A中大中大于于0 的元素存放在的元素存放在B中，小于中，小于0的元素存放在的元素存放在C中。中。算法思想：算法思想： 依次遍厲依次遍厲A的元素，判斷當前的元素值

3、，大的元素，判斷當前的元素值，大于于0 者賦給者賦給B（假設有（假設有p個元素），小于個元素），小于0 者賦給者賦給C（假設有（假設有q個元素）。個元素）。實現(xiàn)本題功能的函數(shù)如下：實現(xiàn)本題功能的函數(shù)如下：void ret (SqList A, int n, SqList B, int p, SqList C, int q) int i; p=0;q=0; for (i=0;i0 p+; Bp=Ai; if (Ai0) q+; Cq=Ai; 2-4 已知在一維數(shù)組已知在一維數(shù)組A1,m+n中依次存放著兩中依次存放著兩個順序表個順序表 ( a1,a2,am) 和和 (b1,b2,bn)，編寫一，編

4、寫一個 函 數(shù) 將 兩 個 線 性 表 的 位 置 互 換 ， 即 把個 函 數(shù) 將 兩 個 線 性 表 的 位 置 互 換 ， 即 把(b1,b2,bn)放到（放到（a1,a2,am)的前面。的前面。算法思想：算法思想： 由于順序表的插入與刪除操作需要移動大量的由于順序表的插入與刪除操作需要移動大量的元素，所用時間多，這里采用先將：元素，所用時間多，這里采用先將： A: ( a1,a2,am,b1,b2,bn)的所有元素逆置，即使之變?yōu)椋旱乃性啬嬷?，即使之變?yōu)椋?A:(bn, b2 , b1 ,am, , a2, a1)然后將然后將(bn, b2 , b1 )逆置為逆置為(b1,b2,b

5、n),將將(am, , a2, a1)逆置為逆置為( a1,a2,am )，便得到最終結(jié)果：便得到最終結(jié)果： A: (b1,b2,bn, a1,a2,am )先編寫一個逆置的函數(shù)如下，其功能是逆置先編寫一個逆置的函數(shù)如下，其功能是逆置A中的中的Al到到Ah部分。部分。逆置的函數(shù)如下：逆置的函數(shù)如下：void invert (SqList A, int l, int h) int i,x; for (i=l;i=(l+h)/2;i+) x=Ai;Ai=Al+h-i;Al+h-i=x; /將將Ai與與Al+h-i元素互換元素互換 實現(xiàn)本題功能的函數(shù)如下：實現(xiàn)本題功能的函數(shù)如下：void excha

6、ng (SqList A, int m, int n) invert(A, 0, m+n-1); invert(A,0,n-1); invert(A,n,m+n-1); 2-5 編寫一個函數(shù)用不多于編寫一個函數(shù)用不多于3n2的平均比較次的平均比較次數(shù)，在一個順序表中找出最大和最小值的元素。數(shù)，在一個順序表中找出最大和最小值的元素。算法思想：算法思想： 如果在查找出最大和最小值的元素時各掃描如果在查找出最大和最小值的元素時各掃描一遍所有元素，則至少要比較一遍所有元素，則至少要比較2n次，為此，使用次，為此，使用一躺掃描找出最大和最小值的元素。一躺掃描找出最大和最小值的元素。實現(xiàn)本題功能的函數(shù)如下

7、：實現(xiàn)本題功能的函數(shù)如下：void maxmin (SqList A, int n) int max,min,i; max=A0;min=A0; for (i=1;imax) max=Ai; else if (Aimax）條件均不成立，）條件均不成立，這時比較的次數(shù)為這時比較的次數(shù)為n-1，另外，每次都要比較，另外，每次都要比較Aimax）條件均成立，不會再執(zhí)行）條件均成立，不會再執(zhí)行else的的比較，所以總的比較次數(shù)為：比較，所以總的比較次數(shù)為： n-1 平均比較次數(shù)為：平均比較次數(shù)為： (2(n-1)+n-1) /2=3n /2-3/2 所以該函數(shù)的平均比較次數(shù)不多于所以該函數(shù)的平均比較次

8、數(shù)不多于3n/2 2-6 有一個單鏈表（不同結(jié)點的數(shù)據(jù)域值可能相有一個單鏈表（不同結(jié)點的數(shù)據(jù)域值可能相同），其頭指針為同），其頭指針為head，編寫一個函數(shù)計算數(shù)據(jù)，編寫一個函數(shù)計算數(shù)據(jù)域為域為 x 的結(jié)點個數(shù)。的結(jié)點個數(shù)。算法思想：算法思想： 本題是通過遍歷該鏈表的每個結(jié)點，每遇到本題是通過遍歷該鏈表的每個結(jié)點，每遇到一個數(shù)據(jù)域為一個數(shù)據(jù)域為x的結(jié)點，結(jié)點個數(shù)加的結(jié)點，結(jié)點個數(shù)加1，結(jié)點個數(shù)，結(jié)點個數(shù)存儲在變量存儲在變量n中。中。實現(xiàn)本題功能的函數(shù)如下：實現(xiàn)本題功能的函數(shù)如下：int count ( LinkList head) LNode *p; int n=0; p=head; whil

9、e (p!=NULL) if (p-data=x) n+; p=p-next; return(n); 2-7 已知一個單鏈表如圖所示，編寫一個函數(shù)將已知一個單鏈表如圖所示，編寫一個函數(shù)將該單鏈表復制一個拷貝。該單鏈表復制一個拷貝。算法思想：算法思想： 依次查找該單鏈表（其頭指針為依次查找該單鏈表（其頭指針為head1）中的）中的每個結(jié)點，對每個結(jié)點復制一個新結(jié)點并鏈接到每個結(jié)點，對每個結(jié)點復制一個新結(jié)點并鏈接到新的單鏈表（其頭指針為新的單鏈表（其頭指針為head2）中。）中。 a1 ai . an head實現(xiàn)本題功能的函數(shù)如下：實現(xiàn)本題功能的函數(shù)如下：void copy ( LinkList

10、 head1, LinkList head2) LNode *p,*q; head2=(Lnode *)malloc(sizeof(Lnode); /建立頭結(jié)點建立頭結(jié)點 q=head2;p=head1; while (p!=NULL) s=(Lnode *)malloc(sizeof(Lnode); /復制一個新結(jié)點復制一個新結(jié)點 s-data=p-data; q-next=s; /把把s鏈接到鏈接到q之后之后 q=s; p=p-next; q-next=NULL; /將最后一個結(jié)點的將最后一個結(jié)點的next域置為域置為NULL p=head2; /刪除頭結(jié)點刪除頭結(jié)點 head2=head

11、2-next; free(p); 2-8 有一個單鏈表（至少有一個結(jié)點），其頭指有一個單鏈表（至少有一個結(jié)點），其頭指針為針為head，編寫一個函數(shù)將，編寫一個函數(shù)將L逆置，即最后一個結(jié)逆置，即最后一個結(jié)點變成第一個結(jié)點，原來倒數(shù)第二個結(jié)點變成第點變成第一個結(jié)點，原來倒數(shù)第二個結(jié)點變成第二個結(jié)點，如此等等。二個結(jié)點，如此等等。算法思想：算法思想： 從頭到尾掃描單鏈表從頭到尾掃描單鏈表L，將第一個結(jié)點的，將第一個結(jié)點的next域置為域置為NULL，將第二個結(jié)點的，將第二個結(jié)點的next域指向第一個域指向第一個結(jié)點，將第三個結(jié)點的結(jié)點，將第三個結(jié)點的next域指向第二個結(jié)點，域指向第二個結(jié)點，如此

12、等等，直到最后一個結(jié)點，便用如此等等，直到最后一個結(jié)點，便用head指向它，指向它，這樣達到了本題的要求。這樣達到了本題的要求。實現(xiàn)本題功能的函數(shù)如下：實現(xiàn)本題功能的函數(shù)如下：Void invert ( LinkList head) LNode *p,*q,*r; p=head; q=p-next; while (q!=NULL) /當當L沒有后續(xù)結(jié)點時終止沒有后續(xù)結(jié)點時終止 r=q-next; q-next=p; p=q; q=r; head-next=NULL; head=p; / p指向指向L的最后一個結(jié)點，現(xiàn)改為頭結(jié)點的最后一個結(jié)點，現(xiàn)改為頭結(jié)點 2-9 已知一個循環(huán)單鏈表如圖所示，編

13、寫一個函已知一個循環(huán)單鏈表如圖所示，編寫一個函數(shù)將所有箭頭方向取反。數(shù)將所有箭頭方向取反。算法思想：算法思想： 從頭到尾掃描循環(huán)單鏈表從頭到尾掃描循環(huán)單鏈表L，將第一個結(jié)點的，將第一個結(jié)點的next域域置為置為NULL，將第二個結(jié)點的，將第二個結(jié)點的next域指向第一個結(jié)點，將域指向第一個結(jié)點，將第三個結(jié)點的第三個結(jié)點的next域指向第二個結(jié)點，如此等等，直到最域指向第二個結(jié)點，如此等等，直到最后一個結(jié)點，便用后一個結(jié)點，便用head指向它，這樣達到了本題的要求。指向它，這樣達到了本題的要求。因為不是普通單鏈表，所以判定最后一個結(jié)點時不能用因為不是普通單鏈表，所以判定最后一個結(jié)點時不能用p-n

14、ext=NULL作為條件，而是用作為條件，而是用q指向第一個結(jié)點，以指向第一個結(jié)點，以p!=q作為條件。作為條件。heada1a2an實現(xiàn)本題功能的函數(shù)如下：實現(xiàn)本題功能的函數(shù)如下：void invert ( LinkList head) LNode *p,*q,*r; p=head; q=p-next; /指向數(shù)據(jù)為指向數(shù)據(jù)為a1的結(jié)點的結(jié)點 while (p!=q) /p不是第一個結(jié)點時循環(huán)不是第一個結(jié)點時循環(huán) r=head; while (r-next!=p) r=r-next; p-next=r; /結(jié)點的結(jié)點的next逆向逆向 p=p-next; q-next=head; / 數(shù)據(jù)域

15、為數(shù)據(jù)域為a1的結(jié)點的結(jié)點next指向指向head所指的結(jié)點所指的結(jié)點 2-10 有一個有序單鏈表（從小到大排列），其有一個有序單鏈表（從小到大排列），其頭指針為頭指針為head，編寫一個函數(shù)向該鏈表中插入一，編寫一個函數(shù)向該鏈表中插入一個元素為個元素為x的結(jié)點，使插入后該鏈表仍然有序。的結(jié)點，使插入后該鏈表仍然有序。算法思想：算法思想： 先建立一個待插入的結(jié)點，然后依次與鏈表先建立一個待插入的結(jié)點，然后依次與鏈表中的各結(jié)點的數(shù)據(jù)域比較大小，找到插入該結(jié)點中的各結(jié)點的數(shù)據(jù)域比較大小，找到插入該結(jié)點的位置，最后插入該結(jié)點。的位置，最后插入該結(jié)點。實現(xiàn)本題功能的函數(shù)如下：實現(xiàn)本題功能的函數(shù)如下：L

16、node *insertorder ( LinkList head, int x) LNode *s ,*p,*q; s=(Lnode *)malloc(sizeof(Lnode); /建立一個待插入的結(jié)點建立一個待插入的結(jié)點 s-data=x;s-next=NULL; if (head=NULL | xdata /若單鏈表為空或若單鏈表為空或x小于第一個結(jié)點的小于第一個結(jié)點的data域域 s-next=head; head=s; else q=head; / 為為s結(jié)點尋找插入插入位置，結(jié)點尋找插入插入位置， / p指向待比較的結(jié)點，指向待比較的結(jié)點，q指向指向p的前驅(qū)的前驅(qū) p=q-nex

17、t; while (p!=NULL & xp-data) /若若x小于小于p所指結(jié)點的所指結(jié)點的data域值，則退出域值，則退出while循環(huán)循環(huán) if (xp-data) q=p; p=p-next; s-next=p; /將將s結(jié)點插入到結(jié)點插入到q和和p之間之間 q-next=s; return(head); 2-11 有兩個循環(huán)單鏈表，鏈表頭指針分別為有兩個循環(huán)單鏈表，鏈表頭指針分別為head1和和head2，編寫一個函數(shù)將鏈表，編寫一個函數(shù)將鏈表head1鏈接到鏈接到head2之后，鏈之后，鏈接后的鏈表仍保持是循環(huán)鏈表形式。接后的鏈表仍保持是循環(huán)鏈表形式。算法思想：算法思想：

18、 先找到兩鏈表的尾指針，將第一個鏈表的尾指針與第二先找到兩鏈表的尾指針，將第一個鏈表的尾指針與第二個鏈表的第一個結(jié)點鏈接起來，再使之成為循環(huán)的。個鏈表的第一個結(jié)點鏈接起來，再使之成為循環(huán)的。a1a2ana1a2anhead1head2實現(xiàn)本題功能的函數(shù)如下：實現(xiàn)本題功能的函數(shù)如下：LNode *link ( LinkList head1, LinkList head2) LNode *p,*q; p=head1; /找到找到head1的表尾，用的表尾，用p指向它指向它 while (p-next!=head1) p=p-next; q=head2; /找到找到head2的表尾，用的表尾，用q指

19、向它指向它 while (q-next!=head2) q=q-next; p-next=head2; /將將head2鏈表鏈接到鏈表鏈接到head1鏈表之后鏈表之后 q-next=head1; /仍保持是循環(huán)鏈表仍保持是循環(huán)鏈表 return (head1); / 數(shù)據(jù)域為數(shù)據(jù)域為an的結(jié)點的結(jié)點next指向指向head所指的結(jié)點所指的結(jié)點 2-12 某百貨公司倉庫中有一批電視機，按其價格從高某百貨公司倉庫中有一批電視機，按其價格從高到低的次序構(gòu)成一個循環(huán)單鏈表，每個結(jié)點有價格，數(shù)量到低的次序構(gòu)成一個循環(huán)單鏈表，每個結(jié)點有價格，數(shù)量和鏈指針三個域，現(xiàn)新到和鏈指針三個域，現(xiàn)新到m臺價格為臺價格為h的電視機，編寫一個的電視機，編寫一個函數(shù)修改原循環(huán)鏈表。函數(shù)修改原循環(huán)鏈表。算法思想：算法思想： 先建立一個待插入的結(jié)點，然后在循環(huán)單鏈表中找到先建立一個待插入的結(jié)點，然后在循環(huán)單鏈表中找到插入的位置，再把該結(jié)點插入。插入的位置，再把該結(jié)點插入。依題意建立如下鏈表結(jié)構(gòu)：依題意建立如下鏈表結(jié)構(gòu)： struct list float price; / 價格域價格域 int number; / 數(shù)量域數(shù)量域 struct list *