1、第二章 線性表1、將以順序表A中的元素逆置。例如原來順序表A中的元素是100，90，80，70，60，50，40，逆置后為40，50，60，70，80，90，100。算法所用的輔助空間要盡量可能地少。用非形式算法描述，并編寫C語言程序。答：描述：該順序表A有N個(gè)元素，分別將第1個(gè)與第N個(gè)對(duì)換，第2個(gè)與第N1個(gè)對(duì)換，依此類推第i個(gè)與第Ni個(gè)對(duì)換。C語言程序：#include #include int main(void) char elem100,t; int i, n, t; printf(Please input number(1100):); /*輸入要輸入的元素的個(gè)數(shù)*/ scanf(%

2、d, &n); printf(*n); printf(Please input element:n);/*輸入元素*/ flushall(); for(i=0; in; +i) scanf(%c, &elemi); for(i=0; in; +i) printf(%c , elemi); printf(n); for(i=0; in/2; +i) t = elemi; elemi = elemn-i-1; elemn-i-1 = t; for(i=0; in; +i) printf(%c , elemi); getch(); return 0; 2、寫一算法輸出已知順序表A中元素的最大值和次最

3、大值。用非形式算法描述，并編寫C語言程序。 #include #include void printFstAndSndValue(SeqList sq) int firstmax = 0; int secondmax = 0; int i = 0; if(sq.last = -1) printf(“List is empty!”); return;firstmax = sq.data0;secondtmax = 0; for(i=1; i=sq.last; +i) if(firstmax sq.datai) firstmax = sq.datai;else if(secondmax sq.da

4、tai) scondmax = sq.datai;printf(“%d %d”, firstmax, secondmax);3、設(shè)一順序表中元素值遞增有序。寫一算法，將元素x插到表中適當(dāng)?shù)匚恢茫⒈３猪樞虮淼赜行蛐?，且分析算法地時(shí)間復(fù)雜度。算法的C語言實(shí)現(xiàn)：int *Insert_SeqList(SeqList *L, datatype x) int i, j, t = 1; for(i=0; ilast; +i) if(L-datai datai = x) for(j=L-last; ji; -j) L-dataj = L-dataj-1; L-datai = x; t = 0; break

5、; if(t 0) L-datai+1 = x; 時(shí)間復(fù)雜度：O(n)。4、設(shè)有兩個(gè)安元素值遞增有序的順序表A和B（單鏈表A和B），編一程序?qū)表和B表歸并成一個(gè)新的遞增有序的順序表C（單鏈表），值相同的元素均保留在C表中。C程序：#include #include int main(void) int A8=1,3,4,6,8,12,34,37; int B9=14,16,17,19,26,30,41,88,91; int C17; int i = 0;int j = 0;int k = 0; printf(A array:); for(i=0; i8; +i) printf(%d , Ai

6、); printf(n); printf(B array:); for(j=0; j9; +j) printf(%d , Bj); printf(n); i = 0; j = 0; while(i8) & (j9) if(Ai Bj) Ck+ = Ai+; else if(Bj Ai) Ck+ = Bj+; else Ck+ = Ai+; while(i 8) Ck+ = Ai+; while(j 9) Ck+ = Bj+; printf(C array:); for(k=0; knext = s;/2 p-next = p-next-next;/3 p-next = s-next;/4 s-

7、next = p-next;/5 s-next = L;/6 s-next = p;/7 s-next = NULL;/8 q = p;/9 while(p-next != Q) p = p-next;/10 while(q-next != NULL) q = q-next;/11 p = q;/12 p = L;/13 L = s;/14 L = p;6、已知p結(jié)點(diǎn)是某雙向鏈表的中間結(jié)點(diǎn)，試從下列提供的語句中選出合適的語句序列。(1)在p結(jié)點(diǎn)后插入s結(jié)點(diǎn)：/7 /12 /3 /6(2)在p結(jié)點(diǎn)前插入s結(jié)點(diǎn)：/13 /8 /5 /4(3)刪除p結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)：q = p-next; p-n

8、ext = q-next; q-next-prior = q-prior; free(q);(4) 刪除p結(jié)點(diǎn)的直接前趨結(jié)點(diǎn)：q = p-prior;p-prior = q-prior;q-prior-next = q-next; free(q);(5)刪除p結(jié)點(diǎn)：p-prior-next=p-next; p-next-prior=p-prior; free(p);7、設(shè)有兩個(gè)線性表A和B皆是單鏈表存儲(chǔ)結(jié)構(gòu)。同一個(gè)表中的元素各不相同，且遞增有序。寫一算法，構(gòu)成一個(gè)新的線性表C，使C為A和B的交集，且C中的元素也遞增有序。void new(LinkList A LinkList B)LinkLi

9、st C;LNode *a, *b, *c, *ap, *bp;a = A-next;b = B-next;c = C-next;while(a-next!=NULL) & (b-next!=NULL)c = (LNode *)malloc(sizeof(LNode);if(a-data data)c-next = a;c = c-next;ap = a-next;free(a);a = ap;elsec-next = b;c = c-next;bp = b-next;free(b);b = bp;while(a-next != NULL) c = (LNode *)malloc(sizeof

10、(LNode);c-next = a;c = c-next;ap = a-next;free(a);a = ap; while(b-next != NULL) c = (LNode *)malloc(sizeof(LNode);c-next = b;c = c-next;bp = b-next;free(b);b = bp;c-next = NULL;return 0;8、刪除線性表a中第i個(gè)元素起的k個(gè)元素。Status DeleteK(SeqList &a,int i,int k)if(i1) | (ka.length) return INFEASIBLE; for(count=1; i+

11、count-1 va.listsize) return ERROR; +va.length;for(i=va.length-1; va.elemix&i=0; -i) va.elemi+1 = va.elemi; va.elemi+1 = x;return OK;/*Insert_SqList */10、比較字符表A和B,并用返回值表示結(jié)果,值為正,表示AB;值為負(fù),表示Anext; p&p-data!=x; p=p-next); return p;/*Locate */12、求鏈表的長(zhǎng)度。int Length(LinkList L) LNode* p; for(k=0, p=L; p-nex

12、t; p=p-next, +k); return k;/*Length */13、把鏈表hb接在ha后面形成鏈表hc。void ListConcat(LinkList ha,LinkList hb,LinkList &hc) LNode *p;hc = ha;p = ha;while(p-next != NULL) p = p-next; p-next = hb;/*ListConcat */14、在無頭結(jié)點(diǎn)鏈表L的第i個(gè)元素之前插入元素b。Status Insert(LinkList &L,int i,int b) LNode *p = L;LNode *q = (LinkList*)mal

13、loc(sizeof(LNode);q.data = b; if(i = 1) q.next = p;L = q; /*插入在鏈表頭部*/ else while(-i 1) p = p-next; q-next = p-next;p-next = q; /*插入在第i個(gè)元素的位置*/ /*Insert */15、在無頭結(jié)點(diǎn)鏈表L中刪除第i個(gè)元素。Status Delete(LinkList &L, int i) LNode *p;if(i = 1) L = L-next; /*刪除第一個(gè)元素*/ else p = L;while(-i 1)p = p-next; p-next = p-next

14、-next; /*刪除第i個(gè)元素*/ /*Delete */16、刪除元素遞增排列的鏈表L中值大于mink且小于maxk的所有元素。Status Delete_Between(Linklist &L,int mink,int maxk)LNode *p = L;LNode *q;while(p-next-data next; /*p是最后一個(gè)不大于mink的元素*/ if(p-next != NULL)/*如果還有比mink更大的元素*/ q = p-next;while(q-data next; /*q是第一個(gè)不小于maxk的元素*/ p-next=q; /Delete_Between 17

15、、刪除元素遞增排列的鏈表L中所有值相同的元素。Status Delete_Equal(Linklist &L) LNode *p = L-next;LNode *q = p-next; /*p,q指向相鄰兩元素*/ while(p-next) if(p-data != q-data) p = p-next;q = p-next; /*當(dāng)相鄰兩元素不相等時(shí),p,q都向后推一步*/ else while(q-data = p-data) free(q); q = q-next; p-next = q;p = q;q = p-next; /*當(dāng)相鄰元素相等時(shí)刪除多余元素*/ /*else*/ /*w

16、hile*/*Delete_Equal */18、順序表的就地逆置。void reverse(SeqList &A) for(i=1, j=A.length; ij; +i, -j) A.elemi A.elemj; /*reverse */19、鏈表的就地逆置;為簡(jiǎn)化算法,假設(shè)表長(zhǎng)大于2。void LinkList_reverse(Linklist &L) LNode *p = L-next;LNode *q = p-next;LNode *s = q-next;p-next = NULL; while(s-next) q-next = p;p = q;q = s;s = s-next; /

17、*把L的元素逐個(gè)插入新表表頭*/ q-next = p;s-next = q;L-next = s;/*LinkList_reverse*/分析:本算法的思想是,逐個(gè)地把L的當(dāng)前元素q插入新的鏈表頭部,p為新表表頭. 20、把鏈表A和B合并為C,A和B的元素間隔排列,且使用原存儲(chǔ)空間。void merge1(LinkList &A, LinkList &B, LinkList &C) LNode* s; LNode *p = A-next;LNode *q = B-next;C = A; while(p!=NULL) & (q!=NULL) s = p-next;p-next = q; /*將

18、B的元素插入*/ if(s != NULL) t = q-next;q-next = s; /*如A非空,將A的元素插入*/ p = s;q = t;/*while*/*merge1 */21、把元素遞增排列的鏈表A和B合并為C,且C中元素遞減排列,使用原空間。void reverse_merge(LinkList &A, LinkList &B, LinkList &C) LNode *pa = A-next;LNode *pb = B-next;LNode *pc;LNode *pre = NULL; /*pa和pb分別指向A,B的當(dāng)前元素*/while(pa!=NULL) | (pb!=

19、NULL)if(pa-datadata) | (pb=NULL)pc = pa;q = pa-next;pa-next = pre;pa = q; /*將A的元素插入新表*/elsepc = pb;q = pb-next;pb-next = pre;pb = q; /*將B的元素插入新表*/pre = pc;C = A;A-next = pc; /*構(gòu)造新表頭*/*reverse_merge*/分析:本算法的思想是,按從小到大的順序依次把A和B的元素插入新表的頭部pc處,最后處理A或B的剩余元素. 22、求元素遞增排列的順序表A和B的元素的交集并存入C中。void SqList_Interse

20、ct(SeqList A,SeqList B,SeqList &C) int i = 1;int j = 1;int k = 0;while(A.elemi0) & (B.elemj0)if(A.elemi B.elemj) +j;if(A.elemi = B.elemj) C.elem+k = A.elemi; /*當(dāng)發(fā)現(xiàn)了一個(gè)在A,B中都存在的元素,*/ +i;+j; /*就添加到C中*/ /*while*/*SqList_Intersect */23、求元素遞增排列的鏈表A和B的元素的交集并存入C中。void LinkList_Intersect(LinkList A,LinkList

21、B,LinkList &C) LNode *p = A-next;LNode *q = B-next;LNode*pc=(LNode*)malloc(sizeof(LNode);while(p!=NULL) & (q!=NULL)if(p-data data) p = p-next; else if(p-data q-data) q = q-next; else s = (LNode*)malloc(sizeof(LNode); s-data = p-data; pc-next = s;pc = s; p = p-next;q = q-next; /*while*/ C = pc;/*Link

22、List_Intersect */24、求元素遞增排列的順序表A和B的元素的交集并存回A中。void SqList_Intersect_True(SeqList &A,SeqList B) int i = 1;int j = 1;int k = 0;while(A.elemi0) & (B.elemj0)if(A.elemi B.elemj) +j; else if(A.elemi != A.elemk) A.elem+k = A.elemi; /*當(dāng)發(fā)現(xiàn)了一個(gè)在A,B中都存在的元素*/ +i;+j; /*且C中沒有,就添加到C中*/ /*while*/while(A.elemk) A.ele

23、mk+ = 0; /*SqList_Intersect_True */25、求元素遞增排列的鏈表A和B的元素的交集并存回A中。void LinkList_Intersect_True(LinkList &A,LinkList B) LNode* p = A-next;LNode* q = B-next;LNode* pc = A; while(p!=NULL) & (q!=NULL) if(p-data data) p = p-next; else if(p-data q-data) q = q-next; else if(p-data != pc-data) pc = pc-next; pc

24、-data = p-data; p = p-next;q = q-next; /*while*/*LinkList_Intersect_True */26、編寫算法求兩個(gè)順序表中都有的元素并把它存到順序表C中。void SqList_Intersect_Delete(SeqList &A, SeqList B, SeqList C) int i = 0;int j = 0;int k = 0;int same = 0;int m = 0;/*i指示A中元素原來的位置,m為移動(dòng)后的位置*/ while(iA.length) & (jB.length) & (kC.length) if(B.ele

25、mj C.elemk) +k; else same = B.elemj;/*找到了相同元素same*/ while(B.elemj = same) +j; while(C.elemk = same) +k;/*j,k后移到新的元素*/ while(iA.length) & (A.elemisame) A.elemm+ = A.elemi+;/*需保留的元素移動(dòng)到新位置*/ while(iA.length) & (A.elemi=same) +i;/*跳過相同的元素*/ /*while*/ while(i next;LNode *q = C-next;LNode *r = A-next;int u;while(p!=NULL) & (q!=NULL) & (r!=NULL) if(p-data data) p = p-next; else if(p-data q-data) q = q-next; else u = p-data; /*確定待刪除元素u*/ while(r-next-data next; /*確定最后一個(gè)小于u的元素指針r*/ if(r-next-data = u) s = r-next; while(s-data