




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
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
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 诊所安全生产自查报告范文
- 安全生产目标考核奖奖惩制度
- 电厂班组安全活动总结
- 消防安全应急演练方案及流程
- 广东省深圳市福田区耀华实验学校2025届物理高一下期末达标测试试题含解析
- 云南省寻甸县第五中学2025届物理高一第二学期期末综合测试模拟试题含解析
- 模特培训师岗位面试问题及答案
- 2025届临川一中实验学校高一物理第二学期期末达标检测模拟试题含解析
- 六年级毕业班学生会议的发言稿
- 公司材料部员工的试用期转正申请书
- 港口装卸作业培训
- 2025年湖北省武汉市中考数学真题(无答案)
- 钳工考试试题及答案
- 2025至2030中国牙科氧化锆块行业发展趋势分析与未来投资战略咨询研究报告
- 拖欠维修费车辆以车抵债协议范本
- 2025至2030中国复印机行业发展趋势分析与未来投资战略咨询研究报告
- 暑假安全家长会4
- 2024年安徽省泗县卫生局公开招聘试题带答案
- 2025年北京市高考化学试卷真题(含答案)
- 2025年重庆市中考化学试卷真题(含标准答案)
- JG/T 202-2007工程管道用聚氨酯、蛭石绝热材料支吊架
评论
0/150
提交评论