将以顺序表A中的元素逆置例如原来顺序表A中的元素是

1、第二章 线性表1、将以顺序表A中的元素逆置。例如原来顺序表A中的元素是100，90，80，70，60，50，40，逆置后为40，50，60，70，80，90，100。算法所用的辅助空间要尽量可能地少。用非形式算法描述，并编写C语言程序。答：描述：该顺序表A有N个元素，分别将第1个与第N个对换，第2个与第N1个对换，依此类推第i个与第Ni个对换。C语言程序：#include #include int main(void) char elem100,t; int i, n, t; printf(Please input number(1100):); /*输入要输入的元素的个数*/ 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、设一顺序表中元素值递增有序。写一算法，将元素x插到表中适当地位置，并保持顺序表地有序性，且分析算法地时间复杂度。算法的C语言实现：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; 时间复杂度：O(n)。4、设有两个安元素值递增有序的顺序表A和B（单链表A和B），编一程序将A表和B表归并成一个新的递增有序的顺序表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结点是某双向链表的中间结点，试从下列提供的语句中选出合适的语句序列。(1)在p结点后插入s结点：/7 /12 /3 /6(2)在p结点前插入s结点：/13 /8 /5 /4(3)删除p结点的直接后继结点：q = p-next; p-n

8、ext = q-next; q-next-prior = q-prior; free(q);(4) 删除p结点的直接前趋结点：q = p-prior;p-prior = q-prior;q-prior-next = q-next; free(q);(5)删除p结点：p-prior-next=p-next; p-next-prior=p-prior; free(p);7、设有两个线性表A和B皆是单链表存储结构。同一个表中的元素各不相同，且递增有序。写一算法，构成一个新的线性表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个元素起的k个元素。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,并用返回值表示结果,值为正,表示AB;值为负,表示Anext; p&p-data!=x; p=p-next); return p;/*Locate */12、求链表的长度。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、在无头结点链表L的第i个元素之前插入元素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个元素的位置*/ /*Insert */15、在无头结点链表L中删除第i个元素。Status Delete(LinkList &L, int i) LNode *p;if(i = 1) L = L-next; /*删除第一个元素*/ else p = L;while(-i 1)p = p-next; p-next = p-next

14、-next; /*删除第i个元素*/ /*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是最后一个不大于mink的元素*/ if(p-next != NULL)/*如果还有比mink更大的元素*/ q = p-next;while(q-data next; /*q是第一个不小于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; /*当相邻两元素不相等时,p,q都向后推一步*/ else while(q-data = p-data) free(q); q = q-next; p-next = q;p = q;q = p-next; /*当相邻元素相等时删除多余元素*/ /*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、链表的就地逆置;为简化算法,假设表长大于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的元素逐个插入新表表头*/ q-next = p;s-next = q;L-next = s;/*LinkList_reverse*/分析:本算法的思想是,逐个地把L的当前元素q插入新的链表头部,p为新表表头. 20、把链表A和B合并为C,A和B的元素间隔排列,且使用原存储空间。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的当前元素*/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; /*构造新表头*/*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; /*当发现了一个在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; /*当发现了一个在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、编写算法求两个顺序表中都有的元素并把它存到顺序表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为移动后的位置*/ 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+;/*需保留的元素移动到新位置*/ 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; /*确定最后一个小于u的元素指针r*/ if(r-next-data = u) s = r-next; while(s-data