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

1、 2-2 已知一個(gè)順序表中的元素按元素值非遞減已知一個(gè)順序表中的元素按元素值非遞減有序排列，編寫一個(gè)函數(shù)刪除表中多余的值相同有序排列，編寫一個(gè)函數(shù)刪除表中多余的值相同的元素。的元素。算法思想：算法思想： 由于順序表中的元素按元素值非遞減有序排由于順序表中的元素按元素值非遞減有序排列，值相同的元素必為相鄰的元素。列，值相同的元素必為相鄰的元素。 因此，依次比較相鄰兩個(gè)元素，若值相等，因此，依次比較相鄰兩個(gè)元素，若值相等，則刪除其中一個(gè)，否則繼續(xù)向后查找。則刪除其中一個(gè)，否則繼續(xù)向后查找。實(shí)現(xiàn)本題功能的函數(shù)如下：實(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個(gè)元素個(gè)元素 n-; / 表長減表長減1 2-3 已知一個(gè)順序表已知一個(gè)順序表A中有中有n個(gè)元素，且任何元個(gè)元素，且任何元素均不為素均不為0，將，將A拆成兩個(gè)線性表拆成兩個(gè)線性表B和和C，使，使A中大中大于于0 的元素存放在的元素存放在B中，小于中，小于0的元素存放在的元素存放在C中。中。算法思想：算法思想： 依次遍厲依次遍厲A的元素，判斷當(dāng)前的元素值

3、，大的元素，判斷當(dāng)前的元素值，大于于0 者賦給者賦給B（假設(shè)有（假設(shè)有p個(gè)元素），小于個(gè)元素），小于0 者賦給者賦給C（假設(shè)有（假設(shè)有q個(gè)元素）。個(gè)元素）。實(shí)現(xiàn)本題功能的函數(shù)如下：實(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中依次存放著兩中依次存放著兩個(gè)順序表個(gè)順序表 ( a1,a2,am) 和和 (b1,b2,bn)，編寫一，編

4、寫一個(gè) 函 數(shù) 將 兩 個(gè) 線 性 表 的 位 置 互 換 ， 即 把個(gè) 函 數(shù) 將 兩 個(gè) 線 性 表 的 位 置 互 換 ， 即 把(b1,b2,bn)放到（放到（a1,a2,am)的前面。的前面。算法思想：算法思想： 由于順序表的插入與刪除操作需要移動(dòng)大量的由于順序表的插入與刪除操作需要移動(dòng)大量的元素，所用時(shí)間多，這里采用先將：元素，所用時(shí)間多，這里采用先將： 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 )先編寫一個(gè)逆置的函數(shù)如下，其功能是逆置先編寫一個(gè)逆置的函數(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元素互換元素互換 實(shí)現(xiàn)本題功能的函數(shù)如下：實(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 編寫一個(gè)函數(shù)用不多于編寫一個(gè)函數(shù)用不多于3n2的平均比較次的平均比較次數(shù)，在一個(gè)順序表中找出最大和最小值的元素。數(shù)，在一個(gè)順序表中找出最大和最小值的元素。算法思想：算法思想： 如果在查找出最大和最小值的元素時(shí)各掃描如果在查找出最大和最小值的元素時(shí)各掃描一遍所有元素，則至少要比較一遍所有元素，則至少要比較2n次，為此，使用次，為此，使用一躺掃描找出最大和最小值的元素。一躺掃描找出最大和最小值的元素。實(shí)現(xiàn)本題功能的函數(shù)如下

7、：實(shí)現(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ù)為這時(shí)比較的次數(shù)為n-1，另外，每次都要比較，另外，每次都要比較Aimax）條件均成立，不會(huì)再執(zhí)行）條件均成立，不會(huì)再執(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 有一個(gè)單鏈表（不同結(jié)點(diǎn)的數(shù)據(jù)域值可能相有一個(gè)單鏈表（不同結(jié)點(diǎn)的數(shù)據(jù)域值可能相同），其頭指針為同），其頭指針為head，編寫一個(gè)函數(shù)計(jì)算數(shù)據(jù)，編寫一個(gè)函數(shù)計(jì)算數(shù)據(jù)域?yàn)橛驗(yàn)?x 的結(jié)點(diǎn)個(gè)數(shù)。的結(jié)點(diǎn)個(gè)數(shù)。算法思想：算法思想： 本題是通過遍歷該鏈表的每個(gè)結(jié)點(diǎn)，每遇到本題是通過遍歷該鏈表的每個(gè)結(jié)點(diǎn)，每遇到一個(gè)數(shù)據(jù)域?yàn)橐粋€(gè)數(shù)據(jù)域?yàn)閤的結(jié)點(diǎn)，結(jié)點(diǎn)個(gè)數(shù)加的結(jié)點(diǎn)，結(jié)點(diǎn)個(gè)數(shù)加1，結(jié)點(diǎn)個(gè)數(shù)，結(jié)點(diǎn)個(gè)數(shù)存儲(chǔ)在變量存儲(chǔ)在變量n中。中。實(shí)現(xiàn)本題功能的函數(shù)如下：實(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 已知一個(gè)單鏈表如圖所示，編寫一個(gè)函數(shù)將已知一個(gè)單鏈表如圖所示，編寫一個(gè)函數(shù)將該單鏈表復(fù)制一個(gè)拷貝。該單鏈表復(fù)制一個(gè)拷貝。算法思想：算法思想： 依次查找該單鏈表（其頭指針為依次查找該單鏈表（其頭指針為head1）中的）中的每個(gè)結(jié)點(diǎn)，對(duì)每個(gè)結(jié)點(diǎn)復(fù)制一個(gè)新結(jié)點(diǎn)并鏈接到每個(gè)結(jié)點(diǎn)，對(duì)每個(gè)結(jié)點(diǎn)復(fù)制一個(gè)新結(jié)點(diǎn)并鏈接到新的單鏈表（其頭指針為新的單鏈表（其頭指針為head2）中。）中。 a1 ai . an head實(shí)現(xiàn)本題功能的函數(shù)如下：實(shí)現(xiàn)本題功能的函數(shù)如下：void copy ( LinkList

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

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

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

13、寫一個(gè)函已知一個(gè)循環(huán)單鏈表如圖所示，編寫一個(gè)函數(shù)將所有箭頭方向取反。數(shù)將所有箭頭方向取反。算法思想：算法思想： 從頭到尾掃描循環(huán)單鏈表從頭到尾掃描循環(huán)單鏈表L，將第一個(gè)結(jié)點(diǎn)的，將第一個(gè)結(jié)點(diǎn)的next域域置為置為NULL，將第二個(gè)結(jié)點(diǎn)的，將第二個(gè)結(jié)點(diǎn)的next域指向第一個(gè)結(jié)點(diǎn)，將域指向第一個(gè)結(jié)點(diǎn)，將第三個(gè)結(jié)點(diǎn)的第三個(gè)結(jié)點(diǎn)的next域指向第二個(gè)結(jié)點(diǎn)，如此等等，直到最域指向第二個(gè)結(jié)點(diǎn)，如此等等，直到最后一個(gè)結(jié)點(diǎn)，便用后一個(gè)結(jié)點(diǎn)，便用head指向它，這樣達(dá)到了本題的要求。指向它，這樣達(dá)到了本題的要求。因?yàn)椴皇瞧胀▎捂湵恚耘卸ㄗ詈笠粋€(gè)結(jié)點(diǎn)時(shí)不能用因?yàn)椴皇瞧胀▎捂湵?，所以判定最后一個(gè)結(jié)點(diǎn)時(shí)不能用p-n

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

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

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

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

18、 先找到兩鏈表的尾指針，將第一個(gè)鏈表的尾指針與第二先找到兩鏈表的尾指針，將第一個(gè)鏈表的尾指針與第二個(gè)鏈表的第一個(gè)結(jié)點(diǎn)鏈接起來，再使之成為循環(huán)的。個(gè)鏈表的第一個(gè)結(jié)點(diǎn)鏈接起來，再使之成為循環(huán)的。a1a2ana1a2anhead1head2實(shí)現(xiàn)本題功能的函數(shù)如下：實(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ù)域?yàn)閿?shù)據(jù)域?yàn)閍n的結(jié)點(diǎn)的結(jié)點(diǎn)next指向指向head所指的結(jié)點(diǎn)所指的結(jié)點(diǎn) 2-12 某百貨公司倉庫中有一批電視機(jī)，按其價(jià)格從高某百貨公司倉庫中有一批電視機(jī)，按其價(jià)格從高到低的次序構(gòu)成一個(gè)循環(huán)單鏈表，每個(gè)結(jié)點(diǎn)有價(jià)格，數(shù)量到低的次序構(gòu)成一個(gè)循環(huán)單鏈表，每個(gè)結(jié)點(diǎn)有價(jià)格，數(shù)量和鏈指針三個(gè)域，現(xiàn)新到和鏈指針三個(gè)域，現(xiàn)新到m臺(tái)價(jià)格為臺(tái)價(jià)格為h的電視機(jī)，編寫一個(gè)的電視機(jī)，編寫一個(gè)函數(shù)修改原循環(huán)鏈表。函數(shù)修改原循環(huán)鏈表。算法思想：算法思想： 先建立一個(gè)待插入的結(jié)點(diǎn)，然后在循環(huán)單鏈表中找到先建立一個(gè)待插入的結(jié)點(diǎn)，然后在循環(huán)單鏈表中找到插入的位置，再把該結(jié)點(diǎn)插入。插入的位置，再把該結(jié)點(diǎn)插入。依題意建立如下鏈表結(jié)構(gòu)：依題意建立如下鏈表結(jié)構(gòu)： struct list float price; / 價(jià)格域價(jià)格域 int number; / 數(shù)量域數(shù)量域 struct list *