时间戳

首页 > 技术文章 > 浙大MOOC《数据结构》随笔

浙大MOOC《数据结构》随笔

eesaltedfish 2021-04-21 21:34 原文

第一讲 基本概念

1.1 什么是数据结构

  1. 图书摆放问题：

    1. 新书如何插入？

      先定类别，再二分查找

    2. 怎么找到指定某本书？

      二分查找

  2. 写程序实现一个函数PrintN

    1. 循环实现

      void PrintN(int N) {
	int i;
	for (i = 1; i <= N; i++) {
		printf("%d\n", i);
	}
	return;
}

    2. 递归实现

      void PrintN(int N) {
	if (N) {
		PrintN(N - 1);
		printf("%d\n", N);
	}
	return;
}

    3. 二者对比

      递归的程序对空间的占用有时候可能是非常恐怖的

      上述函数将所占用的空间都占用了还不够，所以就非正常中止。

      得出结论，解题的效率也与占用空间有关。

  3. 写程序计算给定多项式在给定x处的值

    1. 硬算

      \[% MathType!MTEF!2!1!+- % feaahqart1ev3aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbWexLMBbXgBd9gzLbvyNv2CaeHbl7mZLdGeaGqiFv0Je9sqqr % pepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9vqaqpepm0xbba9pwe9Q8fs % 0-yqaqpepae9pg0FirpepeKkFr0xfr-xfr-xb9adbaqaaeGaciGaai % aabeqaamaabaabauaakeaacaWGMbWaaeWaaeaacaWG4baacaGLOaGa % ayzkaaGaeyypa0JaamyyamaaBaaaleaacaaIWaaabeaakiabgUcaRi % aadggadaWgaaWcbaGaaGymaaqabaGccaWG4bGaey4kaSIaaiOlaiaa % c6cacaGGUaGaey4kaSIaamyyamaaBaaaleaacaWGUbGaeyOeI0IaaG % ymaaqabaGccaWG4bWaaWbaaSqabeaacaWGUbGaeyOeI0IaaGymaaaa % kiabgUcaRiaadggadaWgaaWcbaGaamOBaaqabaGccaWG4bWaaWbaaS % qabeaacaWGUbaaaaaa!59BF! f\left( x \right) = {a_0} + {a_1}x + ... + {a_{n - 1}}{x^{n - 1}} + {a_n}{x^n}\ \]

      double f(int n, double a[], double x) {
	int i;
	double p = a[0];
	for (i = 1; i <= n; i++) {
		p += (a[i] * pow(x, i));
		return p;
	}
}

    2. 分配律

      \[% MathType!MTEF!2!1!+- % feaahqart1ev3aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbWexLMBbXgBd9gzLbvyNv2CaeHbl7mZLdGeaGqiFv0Je9sqqr % pepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9vqaqpepm0xbba9pwe9Q8fs % 0-yqaqpepae9pg0FirpepeKkFr0xfr-xfr-xb9adbaqaaeGaciGaai % aabeqaamaabaabauaakeaacaWGMbWaaeWaaeaacaWG4baacaGLOaGa % ayzkaaGaeyypa0JaamyyamaaBaaaleaacaaIWaaabeaakiabgUcaRi % aadIhadaqadaqaaiaadggadaWgaaWcbaGaaGymaaqabaGccqGHRaWk % caWG4bWaaeWaaeaacaGGUaGaaiOlaiaac6cadaqadaqaaiaadggada % WgaaWcbaGaamOBaiabgkHiTiaaigdaaeqaaOGaey4kaSIaamiEamaa % bmaabaGaamyyamaaBaaaleaacaWGUbaabeaaaOGaayjkaiaawMcaaa % GaayjkaiaawMcaaiaac6cacaGGUaGaaiOlaaGaayjkaiaawMcaaaGa % ayjkaiaawMcaaaaa!5D25! f\left( x \right) = {a_0} + x\left( {{a_1} + x\left( {...\left( {{a_{n - 1}} + x\left( {{a_n}} \right)} \right)...} \right)} \right)\ \]

      double f(int n, double a[], double x) {
	int i;
	double p = a[n];
	for (i = n; i > 0; i--) {
		p = a[i - 1] + x * p;
		return p;
	}
}

    3. 通过重复运算计算二者计算时长（Tick值），发现前者比后者慢了一个数量级

  4. 所以到底什么是数据结构

    1. 数据对象在计算机中的组织方式

      数据结构有逻辑结构和物理结构

    2. 数据对象必定与一定操作有关，这种操作即为算法

    3. 描述数据结构有个很好的方法“抽象数据类型（Abstract Data Type）”

      1. 数据类型
        1. 数据对象集
        2. 数据集合相关联的操作集
      2. 抽象：描述数据类型的方法不依赖于具体实现
        1. 与存放数据的机器无关
        2. 与数据存储的物理结构无关
        3. 与实现操作的算法和编程语言无关

1.2 什么是算法

  1. 算法（Algorithm）

    • 一个有限指令集
    • 接收一些输入（有些情况不需要输入）
    • 产生输出
    • 一定在有限步骤后终止
    • 每一条指令必须
      • 有充分明确的目标，不可以有歧义
      • 计算机能处理的范围之内
      • 描述应不依赖于任何一种计算机语言以及具体的实现手段

  2. 什么是好的算法？

    1. 空间复杂度S(n)

      占用存储单元的长度

      PrintN程序中，循环解法只需要占据固定空间，而递归解法占据N倍空间

    2. 时间复杂度T(n)

      耗费时间的长度

      多项式题目：

      image-20210420195835100

    考虑复杂度时，一般考虑的是最坏复杂度

    image-20210420200053961

    若有两段算法分别有复杂度T1(n)=O(f1(n))和T2(n)=O(f2(n))，则

    ​ T1(n)+T2(n)=max(O(f1(n)),O(f2(n)))

    ​ T1(n)*T2(n)=O(f1(n) * f2(n))

    若T(n)是关于n的k阶多项式，那么T(n)=theta(n^k)

    一个for循环的时间复杂度等于循环次数乘以循环体代码的复杂度

    if-else结构的复杂度取决于if的条件判断复杂度和分支部分的复杂度，总体复杂度取三者中最大

1.3 最大子列和问题

题目：

给定N个整数的序列{A1，A2，...，An}，求函数

\[% MathType!MTEF!2!1!+- % feaahqart1ev3aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbWexLMBbXgBd9gzLbvyNv2CaeHbl7mZLdGeaGqiFv0Je9sqqr % pepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9vqaqpepm0xbba9pwe9Q8fs % 0-yqaqpepae9pg0FirpepeKkFr0xfr-xfr-xb9adbaqaaeGaciGaai % aabeqaamaabaabauaakeaacaWGMbWaaeWaaeaacaWGPbGaaiilaiaa % dQgaaiaawIcacaGLPaaacqGH9aqpciGGTbGaaiyyaiaacIhacaGG7b % GaaGimaiaacYcadaaeWbqaaiaadgeadaWgaaWcbaGaam4Aaaqabaaa % baGaam4Aaiabg2da9iaadMgaaeaacaWGQbaaniabggHiLdGccaGG9b % aaaa!5389! f\left( {i,j} \right) = \max \{ 0,\sum\limits_{k = i}^j {{A_k}} \} \ \]

的最大值。

算法1-暴力求解法

int MaxSubseqSum1(int A[], int N) {
	int ThisSum, MaxSum = 0;
	int i, j, k;
	for (i = 0; i < N; i++) {
		for (j = i; j < N; j++) {	//遍历所有f(i,j)
			ThisSum = 0;
			for (k = i; k <= j; k++)	//计算求和函数
				ThisSum += A[k];
				if (ThisSum > MaxSum)	//MaxSum更新
					MaxSum = ThisSum;
		}
	}
	return MaxSum;
}

算法复杂度：O(N^3)

算法2-递加

int MaxSubseqSum1(int A[], int N) {
	int ThisSum, MaxSum = 0;
	int i, j, k;
	for (i = 0; i < N; i++) {
		ThisSum = 0;
		for (j = i; j < N; j++) {	//每次循环一次，就加一次，没必要每次都从头开始加
			ThisSum += A[j];
			if (ThisSum > MaxSum)
				MaxSum = ThisSum;
		}
	}
	return MaxSum;
}

算法复杂度：O(N^2)

算法3-分而治之

4 -3 5 -2 -1 2 6 2

4 5 2 6

​ 6 8

​ 11

int Max3(int A, int B, int C)
{ /* 返回3个整数中的最大值 */
	return A > B ? A > C ? A : C : B > C ? B : C;
}

int DivideAndConquer(int List[], int left, int right)
{ /* 分治法求List[left]到List[right]的最大子列和 */
	int MaxLeftSum, MaxRightSum; /* 存放左右子问题的解 */
	int MaxLeftBorderSum, MaxRightBorderSum; /*存放跨分界线的结果*/

	int LeftBorderSum, RightBorderSum;
	int center, i;

	if (left == right) { /* 递归的终止条件，子列只有1个数字 */
		if (List[left] > 0)  return List[left];
		else return 0;
	}

	/* 下面是"分"的过程 */
	center = (left + right) / 2; /* 找到中分点 */
	/* 递归求得两边子列的最大和 */
	MaxLeftSum = DivideAndConquer(List, left, center);
	MaxRightSum = DivideAndConquer(List, center + 1, right);

	/* 下面求跨分界线的最大子列和 */
	MaxLeftBorderSum = 0; LeftBorderSum = 0;
	for (i = center; i >= left; i--) { /* 从中线向左扫描 */
		LeftBorderSum += List[i];
		if (LeftBorderSum > MaxLeftBorderSum)
			MaxLeftBorderSum = LeftBorderSum;
	} /* 左边扫描结束 */

	MaxRightBorderSum = 0; RightBorderSum = 0;
	for (i = center + 1; i <= right; i++) { /* 从中线向右扫描 */
		RightBorderSum += List[i];
		if (RightBorderSum > MaxRightBorderSum)
			MaxRightBorderSum = RightBorderSum;
	} /* 右边扫描结束 */

	/* 下面返回"治"的结果 */
	return Max3(MaxLeftSum, MaxRightSum, MaxLeftBorderSum + MaxRightBorderSum);
}

int MaxSubseqSum3(int List[], int N)
{ /* 保持与前2种算法相同的函数接口 */
	return DivideAndConquer(List, 0, N - 1);
}

算法复杂度：O(NlogN)

算法4-在线处理

int MaxSubseqSum1(int A[], int N) {
	int ThisSum, MaxSum = 0;
	int i;
	ThisSum = MaxSum = 0;
	for (i = 0; i < N; i++) {
		ThisSum += A[i];	//向右累加
		if (ThisSum > MaxSum) {
			MaxSum = ThisSum;	//发现更大和则更新当前结果
		}
		else if (ThisSum < 0) {	//如果当前子列和为负数
			ThisSum = 0;	//则不可能使和后面的部分和增大，抛弃之（关键是此时MaxSum不变！）
		}
	}
	return MaxSum;
}

算法复杂度：O(N)

第二讲 线性结构

2.1 线性表及其实现

例题 如何表示多项式？

方法一：顺序存储结构直接表示

例如：

\[% MathType!MTEF!2!1!+- % feaahqart1ev3aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbWexLMBbXgBd9gzLbvyNv2CaeHbl7mZLdGeaGqiFv0Je9sqqr % pepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9vqaqpepm0xbba9pwe9Q8fs % 0-yqaqpepae9pg0FirpepeKkFr0xfr-xfr-xb9adbaqaaeGaciGaai % aabeqaamaabaabauaakeaacaWGMbWaaeWaaeaacaWG4baacaGLOaGa % ayzkaaGaeyypa0JaaGinaiaadIhadaahaaWcbeqaaiaaiwdaaaGccq % GHsislcaaIZaGaamiEamaaCaaaleqabaGaaGOmaaaakiabgUcaRiaa % igdaaaa!4BAD! f\left( x \right) = 4{x^5} - 3{x^2} + 1 \]

表示成：

image-20210421190749102

那如果对于多项式：

\[% MathType!MTEF!2!1!+- % feaahqart1ev3aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbWexLMBbXgBd9gzLbvyNv2CaeHbl7mZLdGeaGqiFv0Je9sqqr % pepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9vqaqpepm0xbba9pwe9Q8fs % 0-yqaqpepae9pg0FirpepeKkFr0xfr-xfr-xb9adbaqaaeGaciGaai % aabeqaamaabaabauaakeaacaWGMbWaaeWaaeaacaWG4baacaGLOaGa % ayzkaaGaeyypa0JaamiEaiabgUcaRiaaiodacaWG4bWaaWbaaSqabe % aacaaIYaGaaGimaiaaicdacaaIWaaaaaaa!4A75! f\left( x \right) = x + 3{x^{2000}} \]

那么需要一个长度为2001的数组，这样会导致很多的无效位。

方法二：顺序存储结构表示非零项

例如：

\[% MathType!MTEF!2!1!+- % feaahqart1ev3aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbWexLMBbXgBd9gzLbvyNv2CaeHbl7mZLdGeaGqiFv0Je9sqqr % pepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9vqaqpepm0xbba9pwe9Q8fs % 0-yqaqpepae9pg0FirpepeKkFr0xfr-xfr-xb9adbaqaaeGaciGaai % aabeqaamaabaabauaakeaacaWGMbWaaeWaaeaacaWG4baacaGLOaGa % ayzkaaGaeyypa0JaaGyoaiaadIhadaahaaWcbeqaaiaaigdacaaIYa % aaaOGaey4kaSIaaGymaiaaiwdacaWG4bWaaWbaaSqabeaacaaI4aaa % aOGaey4kaSIaaG4maiaadIhadaahaaWcbeqaaiaaikdaaaaaaa!4F0A! f\left( x \right) = 9{x^{12}} + 15{x^8} + 3{x^2} \]

可以表示为：

image-20210421191016472

方法三：链表结构存储非零项

链表中每个结点存储多项式中的一个非零项，包括系数和指数两个数据域以及一个指针域。

data data pointer
coef expon link 
typedef struct PolyNode *Polynomial;
struct PolyNode{
	int coef;
	int expon;
	Polynomial link;
};

则方法二中的多项式可以表示成：

image-20210421192036843

1. 什么是线性表

多项式表示问题的启示：

  1. 同一个问题可以有不同的表示（存储）方法；
  2. 有一类共性问题：有序线性列表的组织和管理。

“线性表（Linear List）”：由同类型数据元素构成有序序列的线性结构

  • 表中元素个数称为线性表的长度；
  • 线性表没有元素时，成为空表；
  • 表起始位置称表头，表结束位置称表尾。

2. 线性表的抽象数据类型描述

类型名称：线性表（List）

数据对象集：线性表是n（>=0）个元素构成的有序序列（a1，a2，...，an）

操作集：线性表L属于List，整数i表示位置，元素X属于ElementType，线性表基本操作主要有：

  1. List MakeEmpty()：初始化一个空线性表L；
  2. ElementType FindKth(int K，List L)：根据位序K，返回响应元素；
  3. int Find(ElementType X，List L)：在线性表L中查找X的第一次出现位置；
  4. void Insert(ElementType X，int i，List L)：在位序i前插入一个新元素X；
  5. void Delete(int i，List L)：删除指定位序i的元素；
  6. int Length(List L)：返回线性表L的长度n。

3. 线性表的顺序存储实现

利用数组的连续存储空间顺序存放线性表的各元素

image-20210421193311339

typedef struct LNode *List;
struct LNode{
	ElementType Data[MAXSIZE];
	int Last;
};
struct LNode L;
List Ptrl;

访问下标为i的元素：L.Data[i]或Ptrl->Data[i]

线性表的长度：L.Last+1或Ptrl->Last+1

  • 主要操作的实现

  1. 初始化（建立空的顺序表）

    List MakeEmpty() {
	List PtrL;
	PtrL = (List)malloc(sizeof(struct LNode));
	PtrL->Last = -1;
	return PtrL;
}

  2. 查找

    List Find(ElementType X, List PtrL) {
	int i = 0;
	while (i <= PtrL->Last&&PtrL->Data[i] != X)
		i++;
	if (i > PtrL->Last)
		return -1; //如果没找到，返回-1
	else
		return i; //否则返回当前存储位置
}

  3. 插入（第i个位置上插入一个值为X的新元素，插入之前元素后移）

    void Insert(ElementType X, int i, List PtrL) {
	int j;
	if (PtrL->Last == MAXSIZE - 1) {	//先判断表空间有没有满
		printf("表满");
		return;
	}
	if (i<1 || i>PtrL->Last + 2) {		//检查插入位置的合法性
		printf("位置不合法");
		return;
	}
	for (j = PtrL->Last; j >= i - 1; j--)	//将ai~an倒序向后移动
		PtrL->Data[j + 1] = PtrL->Data[j];
	PtrL > Data[i - 1] = X;	//新元素插入
	PtrL->Last++;	//Last仍指向最后元素
	return;
}

  4. 删除（删除表的第i个位置上的元素，删除之后元素前移）

void Delete(int i, List PtrL) {
	int j;
	if (i<1 || i>PtrL->Last + 1) {
		printf("不存在第%d个元素",i);	//检查空表及删除位置的合法性
		return;
	}
	for (j = i; j <= PtrL->Last; j++)	//将ai+1~an顺序向前移动
		PtrL->Data[j - 1] = PtrL->Data[j];
	PtrL->Last--;	//Last仍指向最后元素
	return;
}

4. 线性表的链式存储实现

不要求逻辑上相邻的两个元素物理上也相连；通过“链”建立起数据元素之间的逻辑关系。

  • 插入、删除不需要移动数据元素，只需要修改“链”
typedef struct LNode *List;
struct LNode {
	ElementType Data;
	List Next;
};
struct LNode L;
List PtrL;

  1. 求表长

    int Length(List PtrL) {
	List p = PtrL;		//p指向表的第一个结点
	int j = 0;
	while (p) {
		p = p->Next;
		j++;			//当前p指向的第j个结点
	}
	return j;
}

    通过遍历的方式求表长，较麻烦，时间复杂度为O(n)

  2. 查找

    1. 按型号查找

      List FindKth(int K, List PtrL) {
	List p = PtrL; //设置表头
	int i = 1;
	while (p != NULL && i < K) {
		p = p->Next;
		i++;
	}
	if (i == K)
		return p;	//找到K，返回指针
	else
		return NULL;	//否则返回空
}

    2. 按值查找

      List Find(ElementType X, List PtrL) {
	List p = PtrL;
	while (p != NULL && p->Data != X)
		p = p->Next;
	return p;
}

    3. 插入（在第i-1个节点后插入一个值为X的新节点）

      1. 先构造一个新节点，用s指向；
      2. 再找到链表的第i-1个节点，用p指向；
      3. 然后修改指针，插入节点（p之后插入新节点是s）

      image-20210421205222366

      List Insert(ElementType X, int i, List PtrL) {
	List p, s;
	if (i == 1) {	//新节点插入在表头
		s = (List)malloc(sizeof(struct LNode));	//申请、填装节点
		s->Data = X;
		s->Next = PtrL;
		return s;	//返回执行插入操作后的头指针
	}
	p = FindKth(i - 1, PtrL);	//查找第i-1个节点
	if (p == NULL) {			//第i-1个不存在，不能插入
		printf("参数i错");
		return NULL;
	}
	else {
		s = (List)malloc(sizeof(struct LNode));	//申请、填装节点
		s->Data = X;
		s->Next = p->Next;	//新节点插入在第i-1个节点的后面
		p->Next = s;
		return PtrL;
	}
}

    4. 删除（删除链表的第i个位置上的节点）

      1. 先找到链表的第i-1个节点，用p指向；
      2. 再用指针s指向要删除的节点（p的下一个节点）；
      3. 然后修改指针，删除s所指节点；
      4. 最后释放s所指节点的空间。

      image-20210421212305002

      List Delete(int i, List PtrL) {
	List p, s;
	if (i == 1) {	//若要删除的是表的第一个节点
		s = PtrL;	//s指向第一个节点
		if (PtrL != NULL)
			PtrL = PtrL->Next;	//从链表中删除
		else
			return NULL;
		free(s);	//释放被删除节点
		return PtrL;
	}
	p = FindKth(i - 1, PtrL);	//查找第i-1个节点
	if (p == NULL) {
		printf("第%d个节点不存在", i - 1);
		return NULL;
	}
	else if (p->Next == NULL) {
		printf("第%d个节点不存在", i);
		return NULL;
	}
	else {
		s = p->Next;		//s指向第i个节点
		p->Next = s->Next;	//从链表中删除
		free(s);			//释放内存
		return PtrL;
	}
}

5. 广义表

例题：如何表示一个二元多项式？

\[% MathType!MTEF!2!1!+- % feaahqart1ev3aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbWexLMBbXgBd9gzLbvyNv2CaeHbl7mZLdGeaGqiFv0Je9sqqr % pepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9vqaqpepm0xbba9pwe9Q8fs % 0-yqaqpepae9pg0FirpepeKkFr0xfr-xfr-xb9adbaqaaeGaciGaai % aabeqaamaabaabauaakeaacaWGqbGaaiikaiaadIhacaGGSaGaamyE % aiaacMcacqGH9aqpcaaI5aGaamiEamaaCaaaleqabaGaaGymaiaaik % daaaGccaWG5bWaaWbaaSqabeaacaaIYaaaaOGaey4kaSIaaGinaiaa % dIhadaahaaWcbeqaaiaaigdacaaIYaaaaOGaey4kaSIaaGymaiaaiw % dacaWG4bWaaWbaaSqabeaacaaI4aaaaOGaamyEamaaCaaaleqabaGa % aG4maaaakiabgkHiTiaadIhadaahaaWcbeqaaiaaiIdaaaGccaWG5b % Gaey4kaSIaaG4maiaadIhadaahaaWcbeqaaiaaikdaaaaaaa!5C81! P(x,y) = 9{x^{12}}{y^2} + 4{x^{12}} + 15{x^8}{y^3} - {x^8}y + 3{x^2} \]

上述二元多项式可以用“复杂”链表表示：

  1. 将二元多项式看成关于x的一元多项式

    \[% MathType!MTEF!2!1!+- % feaahqart1ev3aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbWexLMBbXgBd9gzLbvyNv2CaeHbl7mZLdGeaGqiFv0Je9sqqr % pepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9vqaqpepm0xbba9pwe9Q8fs % 0-yqaqpepae9pg0FirpepeKkFr0xfr-xfr-xb9adbaqaaeGaciGaai % aabeqaamaabaabauaakeaacaWGqbGaaiikaiaadIhacaGGSaGaamyE % aiaacMcacqGH9aqpdaqadaqaaiaaiMdacaWG5bWaaWbaaSqabeaaca % aIYaaaaOGaey4kaSIaaGinaaGaayjkaiaawMcaaiaadIhadaahaaWc % beqaaiaaigdacaaIYaaaaOGaey4kaSYaaeWaaeaacaaIXaGaaGynai % aadMhadaahaaWcbeqaaiaaiodaaaGccqGHsislcaWG5baacaGLOaGa % ayzkaaGaamiEamaaCaaaleqabaGaaGioaaaakiabgUcaRiaaiodaca % WG4bWaaWbaaSqabeaacaaIYaaaaaaa!5AF2! P(x,y) = \left( {9{y^2} + 4} \right){x^{12}} + \left( {15{y^3} - y} \right){x^8} + 3{x^2} \]

  2. 先用一个单链表表示关于x的一元多项式

  3. 每个链表的第一个数据位再用另一个链表表示

广义表（Generalized List）

  • 广义表是线性表的推广
  • 对于线性表而言，n个元素都是基本的单元素
  • 广义表中，这些元素不仅可以是单元素也可以是另一个广义表
typedef struct GNode *GList;
struct GNode {
	int Tag;	//标志域：0表示结点是单元素，1表示结点是广义表
	union {		//子表指针域Sublist与单元素数据域Data复用，即共用存储空间
		ElementType Data;
		GList SubList;
	}URegion;
	GList Next;	//指向后继结点
};

6. 多重链表

多重链表：链表中的节点可能同时隶属于多个链

  • 多重链表中节点的指针域会有多个，如前面例子包含了Next和SubList两个指针域；
  • 但包含两个指针域的链表并不一定是多重链表，比如双向链表

多重链表用途广泛：树、图可以采用多重链表实现存储

例题：矩阵可以用二维数组表示，但二维数组表示有两个缺陷：

  • 一是数组的大小需要实现确定；
  • 对于“稀疏矩阵”，将造成大量的存储空间浪费。

分析：采用一种典型的多重链表——十字链表来存储稀疏矩阵

  • 只存储矩阵非零元素项

    节点的数据域：行坐标Row、纵坐标Col、数值Value

  • 每个节点通过两个指针域，把同行、同列串起来；

    • 行指针（或称为向右指针）Right
    • 列指针（或称为向下指针）Down

image-20210423204038741

其中：

  • 左上角的Term为稀疏矩阵的入口，4表示4行、5表示5列，7表示共有7个元素；
  • 此处的Term和Head依旧使用Union的方式存储。（由Tag区分）

2.2 堆栈

1. 什么是堆栈

例题：算数表达式5+6/2-3*4，正确理解：

5+6/2-3 * 4=5+3-3 * 4=8-12=-4

  • 由两类对象构成的：
    • 运算数，如2、3、4
    • 运算符号，如+、-、*、/
  • 不同运算符号优先级不一样

2. 后缀表达式

  • 中缀表达式：运算符号位于两个运算数之间。如，a+b*c-d/e；
  • 后缀表达式：运算符号位于两个运算数之后。如，abc*+de/-

例题：62/3-42*+=？

=33-8+=8

后缀表达式求值策略：从左向右“扫描”，逐个处理运算数和运算符号

  1. 遇到运算数怎么办？如何“记住”目前还不未参与运算的数？
  2. 遇到运算符号怎么办？对应的运算数是什么？

启示：需要有种存储方法，能顺序存储运算数，并在需要时“倒序”输出！

3. 堆栈的抽象数据类型描述

堆栈（Stack）：具有一定操作约束的线性表

  • 只在一端（栈顶，Top）做插入、删除
    • 插入数据：入栈（Push）
    • 删除数据：出栈（Pop）
    • 后入先出：Last In First Out（LIFO）

操作集：长度为MaxSize的堆栈S∈Stack，堆栈元素item∈ElementType

  1. Stack CreateStack(int MaxSize)：生成空堆栈，其最大长度为MaxSize；
  2. int IsFull(Stack S, int MaxSize)：判断堆栈S是否已满；
  3. void Push(Stack S, ElementType item)：将元素item压入堆栈；
  4. int IsEmpty(Stack S)：判断堆栈S是否为空；
  5. ElementType Pop(Stack S)：删除并返回栈顶元素

4. 栈的顺序存储实现

栈的顺序存储结构通常由一个一维数组和一个记录栈顶元素位置的变量组成。

#define MaxSize <储存数据元素的最大个数>
typedef struct SNode *Stack;
struct SNode {
	ElementType Data[MaxSize];
	int Top;
};

  1. 入栈

    void Push(Stack PtrS, ElementType item) {
	if (PtrS->Top == MaxSize - 1) {
		printf("堆栈满");
		return;
	}
	else {
		PtrS->Data[++(PtrS->Top)] = item;
		return;
	}
}

  2. 出栈

    ElementType Pop(Stack PtrS){
	if (IsEmpty(PtrS)) {
 	printf("堆栈空");
		return ERROR; /* ERROR是ElementType的特殊值，标志错误 */
	}
	else
		return (PtrS->Data[(PtrS->Top)--]); //返回Top下标的值
}

例题：请用一个数组实现两个堆栈，要求最大地利用数组空间，使数组只要有空间入栈操作就可以成功。

分析：

  • 一种比较聪明的方法是使这两个栈分别从数组的两头开始向中间生长；
  • 当两个栈的栈顶指针相遇时，表示两个栈都满了。

  1. 入栈

    void Push(struct DStack *PtrS, ElementType item, int Tag) {
	if (PtrS->Top2 - PtrS->Top1 == 1) {
		printf("堆栈满");	//先判断堆栈有没有满
		return;
	}
	if (Tag == 1)
		PtrS->Data[++(PtrS->Top1)] = item;
	else
		PtrS->Data[--(PtrS->Top2)] = item;
}

    通过标志位Tag判断是对哪一头进行操作。

  2. 出栈

    ElementType Pop(struct DStack *PtrS, int Tag) {
	if (Tag == 1) {
		if (PtrS->Top1 == -1) {	//先判断堆栈是否为空
			printf("堆栈1空");
			return NULL;
		}
		else return PtrS->Data[(PtrS->Top1)--];	//不为空则返回栈头元素
	}
	else {
		if (PtrS->Top2 == MaxSize) {
			printf("堆栈2空");
			return NULL;
		}
		else return PtrS->Data[(PtrS->Top2)++];
	}
}

5. 堆栈的链式存储实现

栈的链式存储结构实际上就是一个单链表，叫做链栈。

插入和删除操作只能在链栈的栈顶进行。

因为如果是对栈底操作的话，可以插入，但无法删除，因为得不到栈底的上一个元素。

typedef struct SNode *Stack;
struct SNode {
	ElementType Data;
	struct SNode *Next;
};

  1. 堆栈初始化（建立空栈）

    Stack CreateStack( ) 
{ /* 构建一个堆栈的头结点，返回该结点指针 */
    Stack S;

    S = (Stack)malloc(sizeof(struct SNode));
    S->Next = NULL;
    return S;
}

  2. 判断堆栈s是否为空

    bool IsEmpty ( Stack S )
{ /* 判断堆栈S是否为空，若是返回true；否则返回false */
    return ( S->Next == NULL );
}

  3. 插入元素Push

    bool Push( Stack S, ElementType X )
{ /* 将元素X压入堆栈S */
    struct SNode *TmpCell;

    TmpCell = (PtrToSNode)malloc(sizeof(struct SNode));	//申请一个节点
    TmpCell->Data = X;
    TmpCell->Next = S->Next;
    S->Next = TmpCell;
    return true;
}

    因为是链表结构，所以不需要判断链表是否为满 ，链表是通过不断申请空间来插入

  4. 删除元素Pop

    ElementType Pop( Stack S )  
{ /* 删除并返回堆栈S的栈顶元素 */
    struct SNode *FirstCell;
    ElementType TopElem;

    if( IsEmpty(S) ) {
        printf("堆栈空"); 
        return ERROR;
    }
    else {
        FirstCell = S->Next; 		//先将节点赋给一个临时指针
        TopElem = FirstCell->Data;	//将该节点值赋给临时值
        S->Next = FirstCell->Next;	//链表头指向下一个元素
        free(FirstCell);			//释放临时指针
        return TopElem;				//返回数值
    }
}

6. 堆栈应用：表达式求值

基本策略：将中缀表达式转换成后缀表达式，然后求值

如何将中缀表达式转换为后缀？

观察一个简单的例子：2+9/3-5 ->293/+5-

  1. 运算数相对顺序不变
  2. 运算符号顺序发生改变
    • 需要存储“等待中”的运算符号（堆栈）
    • 要将当前运算符号与“等待中”的最后一个运算符号比较

例题：a*(b+c)/d = ?

  1. 将“*”压入堆栈；
  2. "("优先级比“*”高，将"("压入堆栈；
  3. "("一旦压入堆栈，其优先级降到最低，所以“+”压入堆栈；
  4. 遇到“)”，开始弹出运算符，直至遇到"("；
  5. 遇到“/”，依据左侧优先级高原则，所以将“*”弹出，“/”压入堆栈；
  6. 遍历结束，弹出“/”。

中缀表达式如何转换成后缀表达式

  • 从头到尾读取中缀表达式中的每个对象（遍历），对不同对象按不同的情况处理。
    • 运算数：直接输出；
    • 左括号：压入堆栈（入栈后优先级变为最低）；
    • 右括号：将栈顶的运算符弹出并输出，直至遇到左括号（出栈，不输出）；
    • 运算符：
      • 若优先级大于栈顶运算符时，则将它压栈；
      • 若优先级小于栈顶运算符时，则将栈顶运算符弹出并输出，再比较新的栈顶运算符，直至该运算符大于栈顶运算符优先级为止，并压入栈顶；
    • 若各对象处理完毕，则将堆栈中存留的运算符一并输出。

堆栈的其他应用：

  • 函数调用及递归实现
  • 深度优先搜索
  • 回溯算法

2.3 队列及实现

1. 什么是队列

队列（Queue）：具有一定操作约束的线性表

  • 插入和删除操作：只能在一端插入，而在另一端删除

    数据插入：入队列（AddQ）

    数据删除：出队列（DeleteQ）

  • 先来先服务，即先进先出（FIFO）

2. 队列的抽象数据类型描述

操作集：长度为MaxSize的堆栈Q∈Queue，堆栈元素item∈ElementType

  1. Queue CreateStack(int MaxSize)：生成空队列，其最大长度为MaxSize；
  2. int IsFullQ(Queue Q, int MaxSize)：判断队列Q是否已满；
  3. void AddQ(Queue Q, ElementType item)：将元素item压入队列Q中；
  4. int IsEmptyQ(Queue Q)：判断队列Q是否为空；
  5. ElementType DeleteQ(Queue Q)：删除并返回队列头元素

3. 队列的顺序存储实现

队列的顺序存储结构通常由一个一维数组和一个记录队列头元素位置的变量front以及一个记录队列尾元素位置的变量rear组成。

#define MaxSize <储存数据元素的最大个数>
struct QNode {
	ElementType Data[MaxSize];
	int rear;
	int front;
};
typedef struct QNode *Queue;

如果将队列数组首尾相连，那么在存放元素的时候会出现一个问题（如果数组长度为6）：

  • front和rear的差值一共由6种可能：0，1，2，3，4，5
  • 数组元素个数一共有7种可能：0，1，2，3，4，5，6

所以不可能通过6种可能去表示7种可能，因此有一些方法来避免这种问题：

  • 使用额外标记：Size或者Tag；
  • 数组只存放n-1个元素。

以下的程序均采取第二种方式，即数组只存放n-1个元素。

  1. 入队列

    bool AddQ( Queue Q, ElementType X )
{
    if ((Q->Rear+1)%Q->MaxSize == Q->Front) {
        printf("队列满");
        return false;
    }
    else {
        Q->Rear = (Q->Rear+1)%Q->MaxSize;
        Q->Data[Q->Rear] = X;
        return true;
    }
}

    通过取余函数，来保证rear有效（即不超过数组长度）

  2. 出队列

    ElementType DeleteQ( Queue Q )
{
    if (Q->Front == Q->Rear) { 
        printf("队列空");
        return ERROR;
    }
    else  {
        Q->Front =(Q->Front+1)%Q->MaxSize;
        return  Q->Data[Q->Front];
    }
}

    出队列的时候没必要将对应数据元素删除，因为不用清除空间

4. 队列的链式存储实现

队列的链式存储结构也可以用一个单链表实现。插入和删除操作分别在链表的两头进行；

front置于链表头，rear置于链表尾

数据结构：

typedef struct Node *PtrToNode;
struct Node { /* 队列中的结点 */
    ElementType Data;
    PtrToNode Next;
};
typedef PtrToNode Position;

struct QNode {
    Position Front, Rear;  /* 队列的头、尾指针 */
    int MaxSize;           /* 队列最大容量 */
};
typedef struct QNode *Queue;

出队操作

ElementType DeleteQ( Queue Q )
{
    Position FrontCell; 
    ElementType FrontElem;
    
    if  (Q->Front == NULL) {
        printf("队列空");
        return ERROR;
    }
    else {
        FrontCell = Q->Front;
        if ( Q->Front == Q->Rear ) /* 若队列只有一个元素 */
            Q->Front = Q->Rear = NULL; /* 删除后队列置为空 */
        else                     
            Q->Front = Q->Front->Next;
        FrontElem = FrontCell->Data;

        free( FrontCell );  /* 释放被删除结点空间  */
        return  FrontElem;
    }
}

2.4 应用实例：多项式加法运算

采用不带头节点的单向链表，按照指数递减的顺序排列各项

image-20210424200510312

struct PolyNode {
	int coef;		//系数
	int expon;		//指数
	struct PolyNode *link;	//指向下一个节点的指针
};
typedef struct PolyNode *Polynomial;
Polynomial P1, P2;

算法思路：两个指针P1和P2分别指向这两个多项式第一个结点，不断循环：

  • P1->expon == P2>expon：系数相加，若结果不为0，则作为结果多项式对应项的系数。同时，P1和P2都分别指向下一项；
  • P1->expon > P2->expon：将P1的当前项存入结果多项式，并使P1指向下一项；
  • P1->expon < P2->expon：将P2的当前项存入结果多项式，并使P2指向下一项。
  • 当某一多项式处理完时，将另一个多项式的所有结点依次复制到结果多项式中去。

实现程序：

Polynomial PolyAdd(Polynomial P1, Polynomial P2) {
	Polynomial front, near, temp;
	int sum;
	rear = (Polynomial)malloc(sizeof(struct PolyNode));
	front = rear;	//由front记录结果多项式表头结点
	while (P1 && P2) {	//当两个多项式均不为空时
		switch (Compare(P1->expon, P2->expon)) {	//相等返回0，大于返回1，小于返回-1
		case 1:
			Attach(P1->coef, P1->expon, &rear);
			P1 = P1->link;
			break;
		case -1:
			Attach(P2->coef, P2->expon, &rear);
			P2 = P2->link;
			break;
		case 0:
			sum = P1->coef + P2->coef;
			if (sum) Attach(sum, P1->expon, &rear);
			P1 = P1->link;
			P2 = P2->link;
			break;
		}
        /*将未处理完的多项式依次加上去*/
		for (; P1; P1 = P1->link) Attach(P1->coef, P1->expon, &rear);
		for (; P2; P2 = P2->link) Attach(P2->coef, P2->expon, &rear);
        /*返回前的扫尾工作*/
		rear->link = NULL; //结果多项式rear赋给NULL
		temp = front;		//通过temp来释放掉上面生成的临时空间点
		front = front->link;	//令front指向结果多项式第一个非零项
		free(temp);	//释放临时空表头结点
		return front;
	}
}

Attach函数：

void Attach(int c, int e, Polynomial *pRear) {
	Polynomial P;
	P = (Polynomial)malloc(sizeof(struct PolyNode));
	P->coef = c;
	P->expon = e;
	P->link = NULL;
	(*pRear)->link = P;
	*pRear = P;
}

将值为c、e的指针插入到(*pRear)后面

2.5 小白专场：多项式乘法

题意理解

设计函数分别求两个一元多项式的乘积与和

已知两个多项式：

\[% MathType!MTEF!2!1!+- % feaahqart1ev3aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbWexLMBbXgBd9gzLbvyNv2CaeHbl7mZLdGeaGqiFv0Je9sqqr % pepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9vqaqpepm0xbba9pwe9Q8fs % 0-yqaqpepae9pg0FirpepeKkFr0xfr-xfr-xb9adbaqaaeGaciGaai % aabeqaamaabaabauaakeaacaaIZaGaamiEamaaCaaaleqabaGaaGin % aaaakiabgkHiTiaaiwdacaWG4bWaaWbaaSqabeaacaaIYaaaaOGaey % 4kaSIaaGOnaiaadIhacqGHsislcaaIYaaaaa!49E1! 3{x^4} - 5{x^2} + 6x - 2 \]

\[% MathType!MTEF!2!1!+- % feaahqart1ev3aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbWexLMBbXgBd9gzLbvyNv2CaeHbl7mZLdGeaGqiFv0Je9sqqr % pepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9vqaqpepm0xbba9pwe9Q8fs % 0-yqaqpepae9pg0FirpepeKkFr0xfr-xfr-xb9adbaqaaeGaciGaai % aabeqaamaabaabauaakeaacaaI1aGaamiEamaaCaaaleqabaGaaGOm % aiaaicdaaaGccqGHsislcaaI3aGaamiEamaaCaaaleqabaGaaGinaa % aakiabgUcaRiaaiodacaWG4baaaa!48F3! 5{x^{20}} - 7{x^4} + 3x \]

多项式和：

\[% MathType!MTEF!2!1!+- % feaahqart1ev3aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbWexLMBbXgBd9gzLbvyNv2CaeHbl7mZLdGeaGqiFv0Je9sqqr % pepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9vqaqpepm0xbba9pwe9Q8fs % 0-yqaqpepae9pg0FirpepeKkFr0xfr-xfr-xb9adbaqaaeGaciGaai % aabeqaamaabaabauaakeaacaaI1aGaamiEamaaCaaaleqabaGaaGOm % aiaaicdaaaGccqGHsislcaaI0aGaamiEamaaCaaaleqabaGaaGinaa % aakiabgkHiTiaaiwdacaWG4bWaaWbaaSqabeaacaaIYaaaaOGaey4k % aSIaaGyoaiaadIhacqGHsislcaaIYaaaaa!4E3B! 5{x^{20}} - 4{x^4} - 5{x^2} + 9x - 2 \]

多项式乘积：

\[% MathType!MTEF!2!1!+- % feaahqart1ev3aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbWexLMBbXgBd9gzLbvyNv2CaeHbl7mZLdGeaGqiFv0Je9sqqr % pepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9vqaqpepm0xbba9pwe9Q8fs % 0-yqaqpepae9pg0FirpepeKkFr0xfr-xfr-xb9adbaqaaeGaciGaai % aabeqaamaabaabauaakeaacaaIXaGaaGynaiaadIhadaahaaWcbeqa % aiaaikdacaaI0aaaaOGaeyOeI0IaaGOmaiaaiwdacaWG4bWaaWbaaS % qabeaacaaIYaGaaGOmaaaakiabgUcaRiaaiodacaaIWaGaamiEamaa % CaaaleqabaGaaGOmaiaaigdaaaGccqGHsislcaaIXaGaaGimaiaadI % hadaahaaWcbeqaaiaaikdacaaIWaaaaOGaeyOeI0IaaGOmaiaaigda % caWG4bWaaWbaaSqabeaacaaI4aaaaOGaey4kaSIaaG4maiaaiwdaca % WG4bWaaWbaaSqabeaacaaI2aaaaOGaeyOeI0IaaG4maiaaiodacaWG % 4bWaaWbaaSqabeaacaaI1aaaaOGaey4kaSIaaGymaiaaisdacaWG4b % WaaWbaaSqabeaacaaI0aaaaOGaeyOeI0IaaGymaiaaiwdacaWG4bWa % aWbaaSqabeaacaaIZaaaaOGaey4kaSIaaGymaiaaiIdacaWG4bWaaW % baaSqabeaacaaIYaaaaOGaeyOeI0IaaGOnaiaadIhaaaa!6F3E! 15{x^{24}} - 25{x^{22}} + 30{x^{21}} - 10{x^{20}} - 21{x^8} + 35{x^6} - 33{x^5} + 14{x^4} - 15{x^3} + 18{x^2} - 6x \]

  • 输入样例：

    4 3 4 -5 2 6 1 -2 0

    3 5 20 -7 4 3 1

  • 输出样例：

    15 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 3 18 2 -6 1

    5 20 -4 4 -5 2 9 1 -2 0

求解思路

  1. 多项式的表示

    仅表示非零项

    • 数组：
      • 编程简单、调试容易
      • 但需要事先确定数组大小
    • 链表
      • 动态性强
      • 但编程略为复杂、调试比较困难

    因为题目提前告知了有n项，所以一种比较好的实现方法是：动态数组

    如果使用链表的方法，则数据结构为：

    typedef struct PolyNode *Polynomial;
struct PolyNode{
    int coef;
    int expon;
    Polynomial link;
}

  2. 程序框架搭建

    • main函数
      • 读入多项式1
      • 读入多项式2
      • 乘法运算输出
      • 加法运算输出
    • 需要设计的函数
      • 读多项式
      • 两多项式相乘
      • 两多项式相加
      • 多项式输出
    int main(){
    Polynomial P1,P2,PP,PS;
    
    P1 = ReadPoly();	//返回指针
    P2 = ReadPoly();
    PP = Mult(P1,P2);
    PrintPoly(PP);		//输出
    PS = Add(P1,P2);
    PrintPoly(PS);
    
    return 0;
}

  3. 如何读入多项式

    Polynomial ReadPoly(){
    ...
    scanf("%d",&N);
    ...
    while(N--){
        scanf("%d %d",&c,&e);	//4 3 4 -5 2 6 1 -2 0
        Attach(c,e,&Rear)；
    }
    ...
    return P;	//返回指针
}

    Rear初值是多少？

    • Rear初值为NULL

      在Attach函数中根据Rear是否为NULL做不同处理

      • 为NULL，说明为第一个节点，则分配空间；
      • 否则将新的节点插在Rear后面。

    • Rear指向一个空节点

      这样就不需要判断Rear是否为NULL；

      但最终要将该空节点删除。

    void Attach(int c, int e, Polynomial *pRear){	//Polynomial本身也是指针
    Polynomial P;								//pRear相当于是指针的指针
    
    P = (Polynomial)malloc(sizeof(struct PolyNode));
    P->coef = c;
    P->expon = e;
    P->link = NULL;
    (*pRear)->link = P;			//新申请的P插在Rear后面，(*pRear)表示指针
    *pRear = P;	/*修改pRear值，指向新节点*/
}

    所以读入多项式的程序为：

    Polynomial ReadPoly(){
    Polynomial P, Rear, t;
    int c,e,N;
    
    scanf("%d",&N);
    P = (Polynomial)malloc(sizeof(struct PolyNode));	//链表头空节点
    P->link = NULL;
    Rear = P;
    while(N--){
        scanf("%d %d",&c,&e);
        Attach(c,e,&Rear);		//将当前项插入多项式尾部
    }
    t = P;
    P = P->link;
    free(t);	//删除临时生成的头节点
    return P;
}

  4. 两个多项式相加

    Polynomial Add(Polynomian P1, Polynomial P2){
    ...
    t1 = P1; t2 = P2;
    P = (Polynomial)malloc(sizeof(struct PolyNode));
    P->link = NULL;
    Rear = P;
    while(t1&&t2){	//t1与t2相加
        if(t1->expon == t2->expon){	//系数相等直接相加
            ...
        }
        else if(t1->expon > t2->expon){
            ...
        }
        else{
            ...
        }
    }
    while(t1){	//t1若不为空，则不上t1后半段
        ...
    }
    while(t2){
        ...
    }
    ...
   	return P;
}

  5. 两个多项式相乘

    • 将乘法运算转换为加法运算

      将P1当前项(ci, ei)乘P2多项式，再加到结果多项式里

      t1 = P1；t2 = P2;
P = (Polynomial)malloc(sizeof(struct PolyNode));
P->link = NULL;
Rear = P;
while(t2){
    Attach(t1->coef*t2->coef,t1->expon+t2->expon,&Rear);	//系数相乘，指数相加
    t2 = t2->link;
}

    • 逐项插入

      将P1当前项(c1i,e1i)乘P2当前项(c2i,e2i)，并插入到结果多项式中。关键是要找到插入位置（有序插入）

      初始结果多项式可由P1第一项乘P2获得（加上）

    Polynomial Mult(Polynomial P1, Polynomial P2){
    ...
    t1 = P1;t2 = P2;
    ...
    while(t2){	
    ...	//Part1.先用P1的第一项乘以P2，得到P（初始值，后续再实现有序插入即可）
    }
    t1 = t1->link;
    while(t1){	//双重循环
        t2 = P2;Rear = P;
        while(t2){
            e = t1->expon + t2->expon;
            c = t1->coef*t2->copf;
            ...	//Part2.有序插入
            t2 = t2->link;
        }
        t1 = t1->link;
    }
    ...	//Part3.结果返回
}

    Part1.

    Polynomial P,Rear,t1,t2,t;
int c,e;

if(!P1||!P2)
    return NULL;	//两多项式相乘，一个为空，结果为空

t1 = P1;t2 = P2;
P = (Polynomial)malloc(sizeof(struct PolyNode)); P->link = NULL;
Rear = P;
Rear = P;
while(t2){
    Attach(t1->coef*t2->coef,t1->expon+t2->expon,&Rear);
    t2 = t2->link;
}

    Part2.

    while(Rear>link&&Rear->link->expon > e)	//当前Rear下一项指数是否大于e
    Rear = Rear->link;
if(Rear->link&&Rear->link->expon == e){	//当前Rear下一项指数等于e，则两项合并
    if(Rear->link->coef + c)	//新旧两项系数不为零
        Rear>link->coef += c;	//则直接相加
    else{
        t = Rear->link;			//系数和为零，则释放该节点
        Rear->link = t->link;
        free(t);
    }
}
else{
    t = (Polynomial)malloc(sizeof(struct PolyNode));//当前Rear下一项指数小于e，则新建节点
    t->coef = c;t->expon = e;
    t->link = Rear->link;
    Rear->link = t;Rear = Rear->link;
}

    Part3.

    t2 = P;
P = P->link;
free(t2);

return P;

  6. 多项式输出

    void PrintPoly(Polynomial P){
    int flag = 0;
    if(!P){printf("0 0\n");return;}	//P为空，直接输出0 0
    
    while(P){
        if(!flag)
            flag = 1;	//第一项前面不输出空格
        else
            printf(" ");
        printf("%d %d",P->coef,P->expon);
        P = P->link;
    }
}

推荐阅读