线性表应用之线性表算法设计六大经典案例 -ag凯发k8国际
目录:
1.顺序有序表的合并
重复式合并
不重复式合并
2.链式有序表的合并
重复式合并
不重复式合并
3.链式有序表的反序合并
4.两个递增链表的交集
5.两个递增链表的差集
6.6.稀疏多项式的合并
1.1重复式合并
已知有两个有序集合a和b按照递增有序排列,现在有一个集合c =aub,c也要按照递增有序排列,举例:a={3,5,8,11},b={2,6,8,9,11,15,20},那么c={2,3,5,6,8,8,9,11,11,15,20}
void mergelist(sqlist la,sqlist lb,sqlist &lc) {lc.length=la.lengthlb.length;lc.elem=new elemtype[lc.length];elemtype *pc=lc.elem;//pc指向集合c的第一个元素 elemtype *pa=la.elem;//pa指向集合a的第一个元素 elemtype *pb=lb.elem;//pb指向集合b的第一个元素 elemtype *pa_last=la.elemla.length-1;//指向a集合的尾元素 elemtype *pb_last=lb.elemlb.length-1;//指向b集合的尾元素 while((pa<=pa_last)&&(pb<=pb_last)){if(*pa<=*pb)//比较两个元素大小,小的在前大的在后 *pc=*pa;//赋值的同时指针向后移动 else*pc=*pb;}while(pa<=pa_last)//谁先结束谁再次循环 *pc=*pa;while(pb<=pb_last)*pc=*pb; }1.2不重复式合并
已知有两个有序集合a和b按照递增有序排列,现在有一个集合c =aub,c也要按照递增有序排列,举例:a={3,5,8,11},b={2,6,8,9,11,15,20},那么c={2,3,5,6,8,9,11,15,20}
void mergelist(sqlist la,sqlist lb,sqlist &lc) {lc.length=la.lengthlb.length;lc.elem=new elemtype[lc.length];elemtype *pc=lc.elem;//pc指向集合c的第一个元素 elemtype *pa=la.elem;//pa指向集合a的第一个元素 elemtype *pb=lb.elem;//pb指向集合b的第一个元素 elemtype *pa_last=la.elemla.length-1;//指向a集合的尾元素 elemtype *pb_last=lb.elemlb.length-1;//指向b集合的尾元素 while((pa<=pa_last)&&(pb<=pb_last)){if(*pa<*pb)//比较两个元素大小,小的在前大的在后 *pc=*pa;//赋值的同时指针向后移动 else if(*pa>*pb){*pc=*pb;}else{*pc=*pa;//把两者之一插入即可pb;//两个表的指针都要向后移动lc.length--;//对于长度需要减1}}while(pa<=pa_last)//谁先结束谁再次循环 *pc=*pa;while(pb<=pb_last)*pc=*pb; }已知有两个有序集合a和b按照递增有序排列,现在有一个集合c =aub,c也要按照递增有序排列,举例:a={3,5,8,11},b={2,6,8,9,11,15,20},那么c={2,3,5,6,8,8,9,11,11,15,20}
2.1重复式合并
已知有两个有序集合a和b按照递增有序排列,现在有一个集合c =aub,c也要按照递增有序排列,举例:a={3,5,8,11},b={2,6,8,9,11,15,20},那么c={2,3,5,6,8,8,9,11,11,15,20}
void mergelist(linklist &la,linklist &lb,linklist &lc)//两链表合并 {linklist pa,pb,pc;pa=la->next;pb=lb->next;lc=la;//让la的头结点作为lc的头结点 pc=lc; //pc初始化也指向la的头结点 while(pa&&pb)//两集合如果都没到最后那么进行此循环进行,按照从小到大的顺序将结点依次相连 {if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;}else{pc->next=pb;pc=pb;pb=pb->next;}}pc->next=pa?pa:pb;//当其中一个链表结束,那么插入另外一个链表的剩余的部分 delete lb;//释放lb的头结点 }2.2不重复式合并
已知有两个有序集合a和b按照递增有序排列,现在有一个集合c =aub,c也要按照递增有序排列,举例:a={3,5,8,11},b={2,6,8,9,11,15,20},那么c={2,3,5,6,8,9,11,15,20}
void mergelist(linklist &la,linklist &lb,linklist &lc)//两链表合并 {linklist pa,pb,pc,q;pa=la->next;pb=lb->next;lc=la;//让la的头结点作为lc的头结点 pc=lc; //pc初始化也指向la的头结点 while(pa&&pb)//两集合如果都没到最后那么进行此循环进行,按照从小到大的顺序将结点依次相连 {if(pa->data<pb->data){pc->next=pa;pc=pa;pa=pa->next;}else if(pa->data>pb->data){pc->next=pb;pc=pb;pb=pb->next;}else{pc->next=pa;pc=pa;pa=pa->next;q=pb->next;delete pb;pb=q;}}pc->next=pa?pa:pb;//当其中一个链表结束,那么插入另外一个链表的剩余的部分 delete lb;//释放lb的头结点 }已知有两个有序集合a和b按照递增有序排列,现在有一个集合c =aub,c也要按照递减有序排列,举例:a={3,5,8,11},b={2,6,8,9,11,15,20},那么c={20,15,11,11,11,9,8,8,6,5,3,2}
#include已知有两个有序集合a和b按照递增有序排列,现在有一个集合c =aub,c也要按照递减有序排列,举例:a={3,5,8,11},b={2,6,8,9,11,15,20},那么c={8,11}
void intersection(linklist &la,linklist &lb,linklist &lc) {linklist pa,pb,pc,q;pa=la->next;pb=lb->next;lc=pc=la;while(pa&&pb){if(pa->data==pb->data){pc->next=pa;pc=pa;pa=pa->next;q=pb;pb=pb->next;delete q; } else if(pa->data<pb->data){q=pa;pa=pa->next;delete q;}else{q=pb;pb=pb->next;delete q;}while(pa){q=pa;pa=pa->next;delete q;}while(pb){q=pb;pb=pb->next;delete q;}pc->next=null;delete lb; } }我们有两个链表a,b,差集表示的是指仅在a中出现而不再b中出现的元素所构成的集合,并返回该集合的个数
void difference(linklist &la,linklist &lb,linklist &lc) {linklist pa,pb,pre,q;pa=la->next;pb=lb->next;pre=la;int n=0;while(pa&&pb){if(pa->data<pb->date){n;pre=pa;pa=pa->next;}else if(pa->data>pb->data)pb=pb->next;else{pre->next=pa->next;q=pa;pa=pa->next;delete q;}}while(pa){n;pa=pa->next; } }比如我们有两个多项式a(x)=7 3x 9x8 5x17,b(x)=8x 22x7-9x8,要求把他们俩相加合并
#include总结
以上是ag凯发k8国际为你收集整理的线性表应用之线性表算法设计六大经典案例的全部内容,希望文章能够帮你解决所遇到的问题。
- 上一篇: 剑指offer之斐波那契问题(c /j
- 下一篇: