线性表的应用（线性表、有序表的合并，多项式运算）
线性表的合并
求解一般集合的并集问题。
【问题描述】已知两个集合A和B，现要求一个新的集合A=A∪B。例如:设A={1，2，5，9}；B={2，6，7}；合并后为A={1，2，5，9，6，7} 。
【算法步骤】 O（m * n）
①分别获取LA,LB的表长m,n。
②从LB的第一个元素开始，循环n次执行以下操作:
从LB中取第i个值，然后赋给e；在LA中查找e，如果LA中没有该值，就插入到LA最后，表长++。void MergeList(List &LA,List &LB)
{
int m=ListLength(LA),n=ListLength(LB);
for(int i=1;i<=n;i++)
{
ElemType e;
GetElem(LB,i,e);
if(!LocateElem(LA,e))
ListInsert(LA,++m,e);
}
}
注：具体实现可以采用顺序模式，也可以采用链表形式。
有序表的合并
求解有序集合（递增或者递减）的并集，得出的线性表也应该为有序表。
【问题描述】已知两个集合A和B，数据元素按值递增有序排列，现要求一个新的集合C=A∪B。使C中的数据元素仍按值递增有序排列。例如：A={1，5，7，9，11}； B={1，2，5，6，8，10}。则C={1，1，2，5，5，6，7，8，9，10，11}。
【问题分析】可以用两个线性表LA和LB分别表示集合A和集合B，不同的是，此例子LA和LB有序，这样就没必要从LB中取元素，然后遍历LA了，只需要比较第一个元素的大小就可以了。具体步骤如下：
顺序有序表的合并 O（m+n）
注：因为需要新开辟空间、所有空间复杂度较高
【算法步骤】
计算LC的表长（LA、LB的表长相加）为合并后的新表分配一个数组空间初始化a、b、c，分别代表LA、LB、LC的下标当下标均未达到表长的时候，比较LA[a]、LB[b]元素值，谁大谁插入到LC中，下标相应++若LA的下标没有达到LA末尾，则依次插入后续元素若LB的下标没有达到LB末尾，则依次插入后续元素void MergeList_Sq(Sqlist LA,Sqlist LB,Sqlist &LC)
{
LC.length=LA.length+LB.length;
LC.data=new ElemType[LC.length];
int c=0,a=0,b=0;
while(a<LA.length&&b<LB.length)
{
if(LA.data[a]<=LB.data[b])
LC.data[c++]=LA.data[a++];
else
LC.data[c++]=LB.data[b++];
}
while(a<LA.length)
LC.data[c++]=LA.data[a++];
while(b<LB.length)
LC.data[c++]=LB.data[b++];
}
链式有序表的合并 O（m+n）
注：归并LA和LB得到单链表LC。因为链表结点之间的关系是通过指针指向建立起来的，所以用链表进行归并并不需要开辟新的存储空间，可以直接利用原来两个表的存储空间，合并过程只需把LA和LB的结点重新链接即可。空间复杂度较低，O（1）。
【算法步骤】
结点重新链接过程 如上图所示， 结点的重新链接过程已经很明确了（图是本人用flash做的……小声bb）。详细步骤如下：
指针pa、pb和pc初始化，分别指向LA、LB首元结点、LC头结点（LC的结点取值为LA的头结点）当pa、pb均没达到表尾时，则比较pa、pb所指元素值，从LA或LB中摘取元素较小的结点插入到LC最后将非空表的剩余段插入到pc所指结点之后释放LB头结点void MergeList_L(LinkList &LA,LinkList &LB,LinkList &LC)
{
LNode *pa,*pb,*pc;
pa=LA->next;
pb=LB->next;
LC=LA;
pc=LC;
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;
}
稀疏多项式运算
【问题描述】多项式的简单相加，对应指数相同的系数相加即可。例如多项式 与多项式 相加可得：。
【问题分析】
稀疏多项式的相加主要有两个相关数值，系数与指数，所以该问题可以抽象成一个线性表，和顺序存储结构相比，链式存储结构更加灵活，空间复杂度也较低，所以我们将采用单链表的基本操作来实现稀疏多项式的运算。
根据多项式相加的运算规则：对于两个多项式中所有的指数相同的项，对应系数相加，若其和不为0，则作为“和多项式”中的一项插入到“和多项式”链表中去；对于两个多项式中指数不相同的项，则将指数值较小的项插入到“和多项式”链表中去。“和多项式”链表中的结点无需生成，而应该从两个多项式链表中摘取。
【案例实现】用链表表示多项式，其中包括系数(coef)和指数(expn)两个数据域以及一个指针域(next)。
typedef struct PNode{
float coef;
int expn;
struct PNode *next;
}PNode,*Polynomial;
多项式的创建 O（n^2）
【问题分析】类似于链表的创建方法（尾插法），区别在于该链表是一个有序表，每项的位置要经过比较才能确定。通过比较，找到第一个大于该输入项指数的项，将输入项插到此项前面，保证有序。
【算法步骤】
①创建一个只有头结点的空链表
②循环n次执行以下操作:
生成一个新结点*s，并输入多项式当前项的系数和指数赋给新结点*s的数据域；设置一个前驱指针pre，用于指向待找元素（第一个大于输入项指数的结点）的前驱，pre的初值指向头结点；指针q初始化，指向首元结点；从头开始遍历链表，比较当前结点与输入项指数，找到第一个大于输入项指数结点*q；将输入项结点*s插入到*q之前，*pre之后。void CreatPolyn(Polynomial &P,int n)
{
P=new PNode;
P->next=NULL;
for(int i=1;i<=n;i++)
{
PNode *s=new PNode;
cin >> s->coef >> s->expn;
PNode *pre=P;
PNode *q=P->next;
while(q&&q->coef<s->coef)
{
pre=q;
q=q->next;
}
s->next=q;
pre->next=s;
}
}
多项式相加 O（m+n）
【问题分析】对于两个多项式中所有的指数相同的项，对应系数相加，若其和不为0，则作为“和多项式”中的一项插入到“和多项式”链表中去；对于两个多项式中指数不相同的项，则将指数值较小的项插入到“和多项式”链表中去。“和多项式”链表中的结点无需生成，而应该从两个多项式链表中摘取。
【算法步骤】
①指针p123初始化，分别指向pa和pb首元结点，pa的头结点
②当p1和p2均未到达相应表尾时，则循环比较p1和p2所指结点对应的指数，有下列三种情况
当指数相等时，对应系数相加，若和不为0，则修改p1所指结点的系数值，同时删除p2所指结点，若和为0，则删除p1和p2所指结点当p1->expn < p2->expn时，则应把p1插入到“和多项式”链表中去当p1->expn > p2->expn时，则应把p2插入到“和多项式”链表中去void AddPolyn(Polynomial &Pa,Polynomial &Pb)
{
PNode *p1,*p2,*p3;
p1=Pa->next;
p2=Pb->next;
p3=pa;
while(p1&&p2)
{
if(p1->expn==p2->expn)
{
int sum=p1->coef+p2->coef;
if(sum!=0)
{
p1->coef=sum;
p3->next=p1;
p3=p1;
p1=p1->next;
PNode *r=p2;
p2=p2->next;
delete r;
}
else
{
PNode *r;
r=p1; p1=p1->next; delete r;
r=p2; p2=p2->next; delete r;
}
}
else if(p1->expn<p2->coef)
{
p3->next=p1;
p3=p1;
p1=p1->next;
}
else
{
p3->next=p2;
p3=p2;
p2->next=p2;
}
}
p3->next=p1?p1:p2;
delete Pb;
}
具体实现代码请访问：https://blog.csdn.net/lesileqin/article/details/88379112
本博客内容借鉴于：
《数据结构》 作者：严蔚敏
相关知识
草花粉特异性抗体在过敏和对过敏原特异性免疫疗法的反应中的线性表位结合模式。,Frontiers in Allergy
乡村的院子没有围墙,只有矮矮的
从0实现 BT 下载 ：1 种子的解析
python二级选择题与分析（8）
热加工影响拟穴青蟹肌肉过敏原致敏性及其分子机理研究
如何用Stata完成（shui）一篇经济学论文（六）：合并
线性表L=(a1，a2，…，an)用数组表示，假定删除表中任何一元素的
NOIP初赛知识点复习总结
妊娠合并病毒性肝炎
位运算
网址: 线性表的应用（线性表、有序表的合并，多项式运算） https://m.huajiangbk.com/newsview1137597.html
| 上一篇: 团体程序设计天梯赛 |
下一篇: 表达同学友情的句子 |
