1、 Chapter 2 線性表線性表練習(xí)：練習(xí)：找出以下算法中的錯誤和低效之處，并將它改寫為一個找出以下算法中的錯誤和低效之處，并將它改寫為一個 既正確又高效的算法。既正確又高效的算法。 int Deletek(SeqList *L, int i, int k) /*從順序表從順序表L中刪除第中刪除第i個元素起的個元素起的k個元素個元素*/ 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; 改進：改進：int Deletek(SeqList *L, int i, int k) /*從順序表從順序表L中刪除第中刪除第i個元素起的個元素起的k個元素個元素*/ int count,j; if (i0|kL-size) printf(“n參數(shù)不合法！參數(shù)不合法！”); return 0; else /*刪除刪除k個元素個元素*/ for(j=i+k;jsize;j+) L-listj-k=L-listj; L-size-=k; return 1; 2010考研題：考研題： 設(shè)將設(shè)將n(n1)個整數(shù)存放到一維數(shù)組個整數(shù)存放到一維數(shù)組R中。試設(shè)計一個在中。試設(shè)計一個在

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

4、以用兩個函數(shù)實現(xiàn)。一個是逆置函數(shù)算法可以用兩個函數(shù)實現(xiàn)。一個是逆置函數(shù)reverse()， 它將給定的數(shù)據(jù)逆置。另一個是循環(huán)左移函數(shù)它將給定的數(shù)據(jù)逆置。另一個是循環(huán)左移函數(shù)leftShift()， 它調(diào)用它調(diào)用reverse()函數(shù)三次，實現(xiàn)相應(yīng)功能。函數(shù)三次，實現(xiàn)相應(yīng)功能。(2)(2)算法實現(xiàn)算法實現(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é)點的結(jié)點*/ free(s); else p=s; 補充：補充：已知一個帶頭結(jié)點的遞增有序單鏈表已知一個帶頭結(jié)點的遞增有序單鏈表L，試編寫一高效，試編寫一高效 算法：刪除該鏈表中所有元素值大于算法：刪除該鏈表中所有元素值大于x且小于且小于y的結(jié)點。的結(jié)點。補充：補充： 已知兩個帶表頭結(jié)點的非遞減有序單鏈表，頭指針分別已知兩個帶表頭結(jié)點的非遞減有序單鏈表，頭指針分別 為為la和和lb，試編寫算法，先將兩個表合并為一個帶表頭結(jié)點，試編寫算法，先將兩個表合并為一個帶表頭結(jié)點 的非遞減有序單鏈表，然后刪除表中結(jié)點值（的非遞減有序單鏈表

6、，然后刪除表中結(jié)點值（data值）相同值）相同 的冗余結(jié)點，最后返回新單鏈表的頭指針。的冗余結(jié)點，最后返回新單鏈表的頭指針。 要求新單鏈表利用原來兩個鏈表的結(jié)點空間，不另外生要求新單鏈表利用原來兩個鏈表的結(jié)點空間，不另外生 成新結(jié)點。成新結(jié)點。void ListMergeDelete(SLNode *la, SLNode *lb, SLNode *lc) SLNode *pa,*pb,*pc; /*歸并兩個有序表歸并兩個有序表*/ (*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é)點刪除冗余結(jié)點*/ 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（判斷兩個集合是否存在包含關(guān)系）（判斷兩個集合是否存在包含關(guān)系） int ListSetInclude(SLNode

8、*L1, SLNode *L2) /*判斷帶頭結(jié)點的單鏈表判斷帶頭結(jié)點的單鏈表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; 補充作業(yè)補充作業(yè)1：創(chuàng)建單鏈表（從表頭創(chuàng)建單鏈表（從表頭-表尾）表尾） int ListCreate(SLNode *la, int n)

9、 /*從鍵盤輸入從鍵盤輸入n個數(shù)，建立以個數(shù)，建立以la為頭指針的帶頭結(jié)點的單鏈表為頭指針的帶頭結(jié)點的單鏈表*/ 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é)點新結(jié)點p插入在表尾插入在表尾*/ q-next=NULL; return 1; 補充作業(yè)補充作業(yè)2： 已知一個帶頭結(jié)點的循環(huán)雙向鏈表，從第二個結(jié)點已知一個帶頭結(jié)點的循環(huán)雙向鏈表，從第二個

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

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