1、 Chapter 2 線性表線性表練習(xí)：練習(xí)：找出以下算法中的錯(cuò)誤和低效之處，并將它改寫為一個(gè)找出以下算法中的錯(cuò)誤和低效之處，并將它改寫為一個(gè) 既正確又高效的算法。既正確又高效的算法。 int Deletek(SeqList *L, int i, int k) /*從順序表從順序表L中刪除第中刪除第i個(gè)元素起的個(gè)元素起的k個(gè)元素個(gè)元素*/ int count,j; if (i0|kL-size) printf(“n參數(shù)不合法！參數(shù)不合法！”); return 0; else for (count=1;countsize;j=i+1;j-) L-listj-1=L-listj; L-size-;

2、 return 1; 改進(jìn)：改進(jìn)：int Deletek(SeqList *L, int i, int k) /*從順序表從順序表L中刪除第中刪除第i個(gè)元素起的個(gè)元素起的k個(gè)元素個(gè)元素*/ int count,j; if (i0|kL-size) printf(“n參數(shù)不合法！參數(shù)不合法！”); return 0; else /*刪除刪除k個(gè)元素個(gè)元素*/ for(j=i+k;jsize;j+) L-listj-k=L-listj; L-size-=k; return 1; 2010考研題：考研題： 設(shè)將設(shè)將n(n1)個(gè)整數(shù)存放到一維數(shù)組個(gè)整數(shù)存放到一維數(shù)組R中。試設(shè)計(jì)一個(gè)在中。試設(shè)計(jì)一個(gè)在

3、時(shí)間和空間兩方面盡可能高效的算法，將時(shí)間和空間兩方面盡可能高效的算法，將R中的序列循環(huán)左中的序列循環(huán)左 移移P（0Pn）個(gè)位置，即將）個(gè)位置，即將R中的數(shù)據(jù)由（中的數(shù)據(jù)由（x0,x1,xn-1）變）變 換為（換為（xp,xp+1,xn-1,x0,x1,xp-1）。）。 (1) (1)算法設(shè)計(jì)思想算法設(shè)計(jì)思想 先將先將n個(gè)數(shù)（個(gè)數(shù)（x0,x1,xp,xn-1）原地逆置，得到）原地逆置，得到 （xn-1,xp,xp-1, x0），然后再將前），然后再將前n-p個(gè)和后個(gè)和后p個(gè)元素分個(gè)元素分 別原地逆置，得到最終結(jié)果：別原地逆置，得到最終結(jié)果：xp,xp+1,xn-1,x0,x1,xp-1。 算法可

4、以用兩個(gè)函數(shù)實(shí)現(xiàn)。一個(gè)是逆置函數(shù)算法可以用兩個(gè)函數(shù)實(shí)現(xiàn)。一個(gè)是逆置函數(shù)reverse()， 它將給定的數(shù)據(jù)逆置。另一個(gè)是循環(huán)左移函數(shù)它將給定的數(shù)據(jù)逆置。另一個(gè)是循環(huán)左移函數(shù)leftShift()， 它調(diào)用它調(diào)用reverse()函數(shù)三次，實(shí)現(xiàn)相應(yīng)功能。函數(shù)三次，實(shí)現(xiàn)相應(yīng)功能。(2)(2)算法實(shí)現(xiàn)算法實(shí)現(xiàn) void reverse(int r, int left, int right) int i=left, j=right, temp; /*i等于左邊界等于左邊界left，j等于右邊界等于右邊界right*/ while(i0 & pnext!=NULL) s=p-next; if (s-da

5、ta=x) p-next=s-next; /*刪除值為刪除值為x的結(jié)點(diǎn)的結(jié)點(diǎn)*/ free(s); else p=s; 補(bǔ)充：補(bǔ)充：已知一個(gè)帶頭結(jié)點(diǎn)的遞增有序單鏈表已知一個(gè)帶頭結(jié)點(diǎn)的遞增有序單鏈表L，試編寫一高效，試編寫一高效 算法：刪除該鏈表中所有元素值大于算法：刪除該鏈表中所有元素值大于x且小于且小于y的結(jié)點(diǎn)。的結(jié)點(diǎn)。補(bǔ)充：補(bǔ)充： 已知兩個(gè)帶表頭結(jié)點(diǎn)的非遞減有序單鏈表，頭指針分別已知兩個(gè)帶表頭結(jié)點(diǎn)的非遞減有序單鏈表，頭指針分別 為為la和和lb，試編寫算法，先將兩個(gè)表合并為一個(gè)帶表頭結(jié)點(diǎn)，試編寫算法，先將兩個(gè)表合并為一個(gè)帶表頭結(jié)點(diǎn) 的非遞減有序單鏈表，然后刪除表中結(jié)點(diǎn)值（的非遞減有序單鏈表

6、，然后刪除表中結(jié)點(diǎn)值（data值）相同值）相同 的冗余結(jié)點(diǎn)，最后返回新單鏈表的頭指針。的冗余結(jié)點(diǎn)，最后返回新單鏈表的頭指針。 要求新單鏈表利用原來兩個(gè)鏈表的結(jié)點(diǎn)空間，不另外生要求新單鏈表利用原來兩個(gè)鏈表的結(jié)點(diǎn)空間，不另外生 成新結(jié)點(diǎn)。成新結(jié)點(diǎn)。void ListMergeDelete(SLNode *la, SLNode *lb, SLNode *lc) SLNode *pa,*pb,*pc; /*歸并兩個(gè)有序表歸并兩個(gè)有序表*/ (*lc)=la; pa=la-next; pb=lb-next; pc=la； while(pa&pb) if (pa-datadata) pc-next=pa;

7、 pc=pa; pa=pa-next; else pc-next=pb; pc=pb; pb=pb-next; if(pa) pc-next=pa; else pc-next=pb; free(lb); /*刪除冗余結(jié)點(diǎn)刪除冗余結(jié)點(diǎn)*/ pa=(*lc)-next; while(pa) pb=pa-next; while(pb&pb-data=pa-data) pc=pb; pb=pb-next; free(pc); pa-next=pb; pa=pb; 書書P46. 2-21（判斷兩個(gè)集合是否存在包含關(guān)系）（判斷兩個(gè)集合是否存在包含關(guān)系） int ListSetInclude(SLNode

8、*L1, SLNode *L2) /*判斷帶頭結(jié)點(diǎn)的單鏈表判斷帶頭結(jié)點(diǎn)的單鏈表L1中的數(shù)據(jù)元素是否都是單鏈表中的數(shù)據(jù)元素是否都是單鏈表L2 中的數(shù)據(jù)元素中的數(shù)據(jù)元素*/ SLNode *p1,*p2; p1=L1-next; while(p1!=NULL) p2=L2-next; while(p2!=NULL& p2-data!=p1-data) p2=p2-next; if(p2=NULL) return 0; p1=p1-next; return 1; 補(bǔ)充作業(yè)補(bǔ)充作業(yè)1：創(chuàng)建單鏈表（從表頭創(chuàng)建單鏈表（從表頭-表尾）表尾） int ListCreate(SLNode *la, int n)

9、 /*從鍵盤輸入從鍵盤輸入n個(gè)數(shù)，建立以個(gè)數(shù)，建立以la為頭指針的帶頭結(jié)點(diǎn)的單鏈表為頭指針的帶頭結(jié)點(diǎn)的單鏈表*/ int i; SLNode *p, *q; if (*la)=(SLNode*)malloc(sizeof(SLNode)=NULL) printf(“內(nèi)存空間不足！內(nèi)存空間不足！n”); return 0; q=*la; for (i=0; idata); q-next=p; q=p; /*新結(jié)點(diǎn)新結(jié)點(diǎn)p插入在表尾插入在表尾*/ q-next=NULL; return 1; 補(bǔ)充作業(yè)補(bǔ)充作業(yè)2： 已知一個(gè)帶頭結(jié)點(diǎn)的循環(huán)雙向鏈表，從第二個(gè)結(jié)點(diǎn)已知一個(gè)帶頭結(jié)點(diǎn)的循環(huán)雙向鏈表，從第二個(gè)

10、結(jié)點(diǎn) 至表尾遞增有序。編寫一個(gè)算法，將第一個(gè)結(jié)點(diǎn)刪除并至表尾遞增有序。編寫一個(gè)算法，將第一個(gè)結(jié)點(diǎn)刪除并 插入表中適當(dāng)位置，使整個(gè)鏈表遞增有序。插入表中適當(dāng)位置，使整個(gè)鏈表遞增有序。 void ListDIDL(DLNode *h) DLNode *p,*s; p=h-next; if (p!=h) h-next=p-next; p-next-prior=h; /*刪除鏈表中的第一個(gè)結(jié)點(diǎn)，刪除鏈表中的第一個(gè)結(jié)點(diǎn)， else return; 并用并用p指針保存指針保存*/ s=h-next; while(s!=h&p-datas-data) s=s-next; /*查找查找p結(jié)點(diǎn)的插入位置結(jié)點(diǎn)的插

11、入位置*/ p-prior=s-prior; s-prior-next=p; p-next=s; s-prior=p; /*p結(jié)點(diǎn)插入在結(jié)點(diǎn)插入在s結(jié)點(diǎn)之前結(jié)點(diǎn)之前*/ 2009考研題：考研題：已知一個(gè)帶頭結(jié)點(diǎn)的單鏈表，假設(shè)該鏈表只給已知一個(gè)帶頭結(jié)點(diǎn)的單鏈表，假設(shè)該鏈表只給出了頭指針，在不改變鏈表的前提下，請(qǐng)?jiān)O(shè)計(jì)一個(gè)盡可能高效出了頭指針，在不改變鏈表的前提下，請(qǐng)?jiān)O(shè)計(jì)一個(gè)盡可能高效的算法，查找鏈表中倒數(shù)第的算法，查找鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)（個(gè)結(jié)點(diǎn)（k為正整數(shù)），若查找成為正整數(shù)），若查找成功，算法輸出該結(jié)點(diǎn)的功，算法輸出該結(jié)點(diǎn)的data域的值，并返回域的值，并返回1，否則，只返回，否則，只返回0。 int Locatek(SLNode *h, in