目录：
1.顺序有序表的合并
        重复式合并
        不重复式合并
2.链式有序表的合并
        重复式合并
        不重复式合并
3.链式有序表的反序合并
4.两个递增链表的交集
5.两个递增链表的差集
6.6.稀疏多项式的合并

1.顺序有序表的合并

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.length+Lb.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.elem+La.length-1;//指向A集合的尾元素 ElemType *pb_last=Lb.elem+Lb.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.length+Lb.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.elem+La.length-1;//指向A集合的尾元素 ElemType *pb_last=Lb.elem+Lb.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++; }

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,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的头结点 }

3.链式有序表的反序合并

已知有两个有序集合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<stdio.h> #include<iostream> using namespace std; #define OK 1 #define ERROR 0 #define MAXSIZE 100 typedef int Status; typedef int ElemType; typedef struct LNode{ElemType data;struct LNode *next; }LNode,*LinkList; Status InitList(LinkList &L)//初始化单链表 {L=new LNode;L->next=NULL;return OK; } void CreateList(LinkList &L,int n)//创建顺序表函数，初始化前几个元素 {LinkList p,q;q=L;for(int i=n;i>0;i--){p=new LNode;cin>>p->data;p->next=NULL;q->next=p;q=p;} } void TraverseList_L(LinkList l)//遍历集合 {l=l->next;while(l){if(l->next!=NULL)cout<<l->data<<",";elsecout<<l->data; l=l->next;} } void MergeList(LinkList &La,LinkList &Lb)//两链表合并 {LinkList pa,pb,p;pa=La->next;pb=Lb->next; La->next=NULL;while(pa&&pb)//两集合如果都没到最后那么进行此循环进行，按照从小到大的顺序将结点依次相连 {if(pa->data<=pb->data){p=pa->next;pa->next=La->next;La->next=pa;pa=p; }else{p=pb->next;pb->next=La->next;La->next=pb;pb=p;}}while(pa){p=pa->next;//把pa的后继暂存于ppa->next=La->next;//将pa结点链接于结果表中，同时实现倒置La->next=pa;pa=p;}while(pb){p=pb->next;pb->next=La->next;La->next=pb;pb=p;}delete Lb;//释放Lb的头结点 } int main() { LinkList La;LinkList Lb;InitList(La);InitList(Lb);int n;int m;cout<<"请输入在表A中添加的元素个数：";cin>>n; CreateList(La,n);cout<<"请输入在表B中添加的元素个数：";cin>>m; CreateList(Lb,m);cout<<"两表合并后的表c元素依次为："; MergeList(La,Lb);TraverseList_L(La); }

4.两个递增链表的交集

已知有两个有序集合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; } }

5.两个递增链表的差集

我们有两个链表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; } }

6.稀疏多项式的合并

比如我们有两个多项式A(x)=7+3x+9x⁸+5x¹⁷,B(x)=8x+22x⁷-9x⁸,要求把他们俩相加合并

#include<iostream> using namespace std; typedef struct PNode{float coef;//系数 int expn;//指数 struct PNode *next; }PNode,*Polynomial; void CreatePolyn(Polynomial &P,int n)//输入n项系数和指数，建立多项式有序链表P {Polynomial s,pre,p,q;P=new PNode;//建立一个带头结点的单链表 P->next=NULL;for(int i=1;i<=n;i++){s=new PNode;//生成新的结点 cin>>s->coef>>s->expn;pre=P;//pre用于保存q的前驱，初值为头结点 q=P->next;//q初始化指向第一个有元素的结点 while(q&&q->expn<s->expn)//通过比较指数找到第一个大于输入项指数的项*q {pre=q;q=q->next;}s->next=q;//把新的结点s插在q和前驱结点之间 pre->next=s;} } void AddPolyn(Polynomial &pa,Polynomial &pb)//计算多项式的和 {float sum; Polynomial p1,p2,p3,r;p1=pa->next;//p1,p2分别指向第一个有元素的结点 p2=pb->next;p3=pa;//p3就是运算后的结果链表的头指针，初始值为pa while(p1&&p2)//p1和p2均为非空 {if(p1->expn==p2->expn)//如果两个指数相同 {sum=p1->coef+p2->coef;//系数相加 if(sum!=0){p1->coef=sum;//修改pa当前结点的系数值为两项系数之和 p3->next=p1;// 将修改后的pa当前结点链在p3之后，p3指向p1 p3=p1;p1=p1->next;r=p2;p2=p2->next;delete r;}else{r=p1;p1=p1->next;delete r;r=p2;p2=p2->next;delete r;}}else if(p1->expn<p2->expn){p3->next=p1;p3=p1;p1=p1->next;}else{p3->next=p2;p3=p2;p2=p2->next;}} p3->next=p1?p1:p2;delete pb; } void print(Polynomial L1)//依次打印各个结点的系数和指数 {L1=L1->next;while(L1){cout<<endl<<L1->coef<<" "<<L1->expn<<endl; L1=L1->next;} } int main() {Polynomial L1;Polynomial L2;int n;int m;cout<<"请输入第一个链表的元素个数和各个元素的系数和指数值:";cin>>n; CreatePolyn(L1,n);cout<<"请输入第一个链表的元素个数和各个元素的系数和指数值:";cin>>m;CreatePolyn(L2,m);AddPolyn(L1,L2);cout<<"------------------------运行结果为----------------------------------\n"; print(L1); }

总结

以上是生活随笔为你收集整理的线性表应用之线性表算法设计六大经典案例的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。