C语言数据结构——线性表的应用

前言

这篇算是对线性表的算法的补充，学完前两篇之后才可以看这一篇。其中有几个操作前几篇文章提到过，但是这里还是要在提一次。

线性表的合并

这个线性表的合并举个简单的例子就是有两个集合A，B，求AUB，且不按数据大小排序。

算法步骤

①分辨获取L1的表长和L2的表长。

②从L2中的第1个数据元素开始，循环L2.length次执行以下操作：

从L2中查找第i个数据元素（1≤i≤L2.length）个数据元素赋给e；
在L1中查找元素e，如果不存在，则将e插在表L1的最后。

void MergeList(List& L1, List& L2) {
	//将所有在L2中但不在L1中的元素插入到L1中
	for (int i = 1; i <= L2.length; i++) {
		GetElem(L2, i, e);           //取L2中第i个数据元素赋给e
		if (!LocateElem(L1, e));     //L1中不存在和e相同的数据元素
		ListInsert(L1, L1.length, e);//将e插在L1的最后
	}
}

时间复杂度：①当采用顺序存储结构时，在每次循环中，GetElem和ListInsert这两个操作所执行的时间和表长无关，LocateElem的执行时间和表长L1.length成正比，因此，时间复杂度为O（L1.length*L2.length）；

②当采用链式结构时，在每次循环中，GetElem的执行时间和表长L2.length成正比，而LocateElem和ListInsert这两个操作的执行时间和表长L1.length成反比，因此，假设L1.length大于L2.length，时间复杂度为O（L1.length*L2.length）。

有序表的合并

这个和上一个算法线性表的合并只相差在数据元素是否有序排列，相当于是集合A，B求AUB，且AUB的数据元素是按照大小顺序排列的且遇到相同的数据元素都留下来。

有序表的合并分为顺序表的合并和链表的合并。

顺序有序表的合并

算法步骤

初始化：
- 初始化三个指针 i, j, k 分别指向 L1 的起始位置、L2 的起始位置和顺序表 L3 的起始位置。
- i = 0, j = 0, k = 0。
- 其中表L3的表长为L1表长和L2表长的和。
比较与插入：
- 比较 L1[i] 和 L2[j] 的值。
- 如果 L1[i] <= L2[j]，则将 L1[i] 放入 L3[k]，并将 i 和 k 各自加1。
- 否则，将 L2[j] 放入 L3[k]，并将 j 和 k 各自加1。
重复：
- 重复上述比较与插入的过程，直到其中一个数组的所有元素都被处理完。
剩余元素处理：
- 如果 L1 中还有剩余元素（即 i < m），则将 L1 中剩余的元素依次放入 L3 中。
- 如果 L2 中还有剩余元素（即 j < n），则将 L2 中剩余的元素依次放入 L3 中。
完成：
- 当两个顺序表的所有元素都被处理完毕后，合并过程结束，L3 即为最终的合并表。

int Merge(SqList &L1,SqList &L2){
	SqList L3;
	L3.elem=new ElemType[L1.length+L2.length];
	if(L3.elem==NULL){
		return ERROR;
	}
	int i=0,j=0,k=0;
	while(i<L1.length&&j<L2.length){
		if(L1.elem[i]<=L2.elem[j]) {
			L3.elem[k++]=L1.elem[i++];
		}
		else{
			L3.elem[k++]=L2.elem[j++];
		}
	}
	//复制L1中剩余的元素
	while(i<L1.length){
		L3.elem[k++]=L1.elem[i++];
	} 
	//复制L2中剩余的元素
	while(j<L2.length){
		L3.elem[k++] = L2.elem[j++];
	} 
	L3.length = k;
	for (i = 0; i < L3.length; i++) {
		cout << L3.elem[i] << endl;
	}
	return 0;
}

顺序表：时间复杂度为 O(m + n)，其中 m 和 n 分别是两个输入顺序表的长度。

链式有序表的合并

在开始讲这个算法的具体实现之前，咱先来个施法前摇，讲一下顺序表和链表的有序表的合并有什么不同。

首先，单链表LA，LB都是链式存储结构，链表之间的结点都是通过指针来连接的，所以在进行合并操作时不需要另外开辟新的内存空间，可以直接利用原来两个表的存储空间，合并的过程中把LA，LB两个表中的结点重新连接即可。

算法步骤

①指针pa和pb初始化，分别指向LA和LB的第一个结点。

②LC的结点取值为LA的头结点。

③指针pc初始化，指向LC的头结点。

④当指针pa和pb均未达到相应的表尾时，则依次比较pa和pb所指向的元素值，从LA或LB中摘取元素值较小的结点插入LC的最后。

⑤将非空表的剩余段插入pc所指结点之后。

⑥释放LB的头结点。

void MergeList_L(LinkList& LA, LinkList& LB, LinkList& LC) {
	//已知单链表LA和LB的元素按值非递减排列
	//归并LA和LB得到新的单链表LC,LC的元素也按值非递减排列
	LNode* pa;
	LNode* pb;
	LNode* pc;
	pa = LA->next;  
	pb = LB->next;  
	LC = LA;        //用LA的头结点作为LC的头结点
	pc = LC;        //pc的初值指向LC的头结点
	while (pa && pb) {
		//LA和LB均未到达表尾，依次“摘取”两表中值较小的结点插入到LC的最后
		if (pa->elem <= pb->elem) {  //摘取pa的结点
			pc->next = pa;   //将pa所指结点链接到pc所指结点之后
			pc = pa;         //pc指向pa
			pa = pa->next;   //pa指向下一个结点
		}
		else {//摘取pb的结点
			pc->next = pb;   //将pb所指结点链接到pc所指结点之后
			pc = pb;         //pc指向pb
			pb = pb->next;   //pb指向下一节点
		}
	}
	pc->next = pa ? pa : pb; //将非空表的剩余段插入到pc所指结点之后
	delete LB;               //释放LB的头结点
}

这里面的pc=pa和pc=pb的操作是为了更新指针pc，使其指向新链表LC中最新添加的结点。目的是确保pc始终指向LC的当前最后一个结点，从而能够在下一次迭代时正确的将下一个元素链接到LC的末尾。

线性表表示多项式

先讲一元多项式的例子。

根据之前写的讲线性表的文章，可以把一元多项式抽象成一个线性表。

先简单的来说，对于一个一元多项式来说，它最主要是由系数和指数组成的，我们可以把这两个值由一个数组来表示，数组的下标0，1，2......来表示指数，系数就是数组里面存储的元素。

例如多项式1+2x+3x²-5x³可以用数组表示为：

图片待补充

用这个玩意进行多项式相加的算法就很容易实现，只需要把两个数组相应的分量项相加就可以了。

接下来就是稀疏多项式了，对于稀疏多项式，也能抽象成线性表，结合着前文讲的归并的操作，可以看出，稀疏多项式的相加和两个有序表的归并极其相似，不同之处仅在于有序表的归并只会出现小于等于和大于这两种情况，而稀疏多项式在相加的时候要考虑大于、小于和等于这三种情况。

这篇文章先讲单链表的表示稀疏多项式，这也是最常用的方法。

首先还是先定义一下多项式的数据结构：

typedef struct PNode {
	float cof;   //系数
	int exp;     //指数
	struct PNode *next;
}PNode,*Poly;

多项式的创建

这个多项式的创建和单链表的创建极其相似，前者就比后者多了一个比大小。

算法步骤：

①创建一个只有头结点的空链表。

②根据输入的多项式系数n，重复执行以下操作：

生成一个新结点*s；
输入多项式当前项的系数和指数赋给新结点*s的数据域；
设置一个前驱指针pre，用于指向待找到的第一个大于输入项指数的结点的前驱，pre初始化时指向头结点；
指针q初始化，指向首元结点；
循环向下逐个比较链表当中当前结点的指数与输入项的指数，找到第一个大于输入项指数的结点*q；
将输入项结点*s插入结点*q之前。

void CreatePolyn(Poly& p, int n) {
	p=new PNode;
	p->next = NULL;
	PNode* s;
	cout << "请输入多项式系数和指数：" << endl;
	for (int i = 0; i < n; i++) {
		s = new PNode;
		cin >> s->cof;
		cin >> s->exp;
		PNode *pre = p;
		PNode *q = p->next;
		while (q && q->exp < s->exp){
			pre = q;
			q = q->next;
		}
		s->next = q;
		pre->next = s;
	}
}

里面的pre指针和q指针都是为了将新创建的s结点准确的插入正确的位置。

需要注意的是，在这段代码中，p 被初始化为一个新的 PNode，但这个节点并没有被用作实际的数据节点。因此，实际的多项式数据是从 p->next 开始的。

多项式的相加

多项式的相加相当于是有序表的归并，只是细节上有些不太相同。这里不再过多解释，直接给出算法步骤

算法步骤：

①初始化：

p1 指向 p 链表的第一个实际数据节点（即 p->next）。

p2 指向 q 链表的第一个实际数据节点（即 q->next）。

pre 用于跟踪结果链表中的最后一个节点，初始时指向 p 的哑结点。

sum 用来暂存两个相同指数项系数相加的结果。

s 用作临时指针，主要用于删除多余的节点。

②遍历和合并：

使用 while (p1 && p2) 循环来处理 p1 和 p2 都非空的情况。

在循环中，比较 p1 和 p2 当前节点的指数 (exp)：

如果 p1->exp == p2->exp，则说明这两个节点有相同的指数，它们的系数应该相加。如果相加后的系数 sum 不为0，则更新 p1 的系数为 sum 并将 p1 节点链接到结果链表中；否则，删除这两个节点。

如果 p1->exp < p2->exp，则 p1 节点应先加入结果链表，因为它的指数较小。

如果 p1->exp > p2->exp，则 p2 节点应先加入结果链表，因为它的指数较小。

③处理剩余节点：

当一个链表遍历完毕后（即 p1 或 p2 变为空），另一个链表可能还有剩余的节点未被处理。这时，将剩余的整个链表直接连接到结果链表的末尾。

这是通过 pre->next = p1 ? p1 : p2; 完成的，这里使用了三元运算符来选择非空的链表。

④清理：

最后，删除 q 的哑结点，因为它不再需要。注意这里删除的是 q 的哑结点，而不是整个 q 链表，因为在前面的操作中，q 链表中的有效节点已经被移动到了 p 中或被删除。

⑤结束：

函数执行完毕后，p 链表包含了两个多项式相加后的结果。

void AddPoly(Poly& p, Poly& q) {
	PNode* p1 = p->next;
	PNode* p2 = q->next;
	PNode* pre = p;
	int sum;
	PNode* s;
	while (p1 && p2) {
		if (p1->exp == p2->exp) {
			sum = p1->cof + p2->cof;
			if (sum != 0) {
				p1->cof = sum;
				pre->next = p1;
				pre = p1;
				p1 = p1->next;
				s = p2;
				p2 = p2->next;
				delete s;
			}
			else {
				s = p1;
				p1 = p1->next;
				delete s;
				s = p2;
				p2 = p2->next;
				delete s;
			}
		}
		else if (p1->exp < p2->exp) {
			pre->next = p1;
			pre = p1;
			p1 = p1->next;
		}
		else{
			pre->next = p2;
			pre = p2;
			p2 = p2->next;
		}
	}
	pre->next = p1 ? p1 : p2;
	delete q;
	}
void PrintPoly(Poly p) {
	PNode* q = p->next;
	while (q) {
		cout << q->cof << " " << q->exp;
		q = q->next;
		if (q) {
			cout << " ";
		}
	}
}