数据结构与算法系列文章目录

---

---

一、线性表及其实现

1、多项式的表示

【例】一元多项式及其运算

​ 一元多项式：$f(X)=a_0+a_{1}x+\cdots +a_{n-1}{x}^{n-1}+a_n{x}^n$

主要运算：多项式相加、相减、相乘等

【分析】多项式的关键数据：

	> 多项式项数n>> 各项系数a<sub>i</sub>及指数i

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

数组各分量对应多项式各项：

​ a[i]：项xⁱ的系数a_i

例如： $f(X)=4x^5-3x^2+1$

表示成：

下标i	0	1	2	3	4	5	…
a[i]	1	0	-3	0	0	4	…

两个多项式相加：两个数组对应分量相加

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

每个非零项$a_i{x}^i$涉及两个信息：系数$a_i$和指数i

可以将一个多项式看成是一个$(a_i,i)$二元组的集合。

用结构数组表示：数组分量是由系数$a_i$、指数i组成的结构，对应一个非零项

例如：$P_1(x)=9x^{12}+15x^7+3x^2$和$P_2(x)=26x^{19}-4x^8-13x^6+82$

下标i	0	1	2	…
系数ai	9	15	3	——
指数i	12	8	2	——

下标i	0	1	2	3	…
系数ai	26	-4	-13	82	——
指数i	19	8	6	0	——

相加过程：可以从头开始，比较两个多项式当前对应项的指数

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

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

结点：

Struct PolyNode
{int coef;int expon;Polynomial link;
}PolyNode* Polynomial;

【例如】 $P_1(x)=9x^{12}+15x^7+3x^2$和$P_2(x)=26x^{19}-4x^8-13x^6+82$

【链表存储形式】

2、什么是线性表

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

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

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

  • 类型名称：线性表（List）
  • 数据对象集：线性表时$n(\ge 0)$个元素构成的有序序列$(a_1,a_2,\cdots ,a_n)$
  • 操作集：线性表$L\in List$，整数i表示位置，元素$X\in 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前插入一i个新元素X；
    • 5、**void Delete(int i, List L): **删除指定位序i的元素；
    • 6、**int Length(List L): **返回线性表L的长度n。

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

利用数组的连续存储空间顺序存放相信白哦的各元素

sruct LNode
{ElementType Data[MAXSIZE];int Last;
}LNode L;
LNode* PtrL = &L;

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

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

主要操作的实现

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

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

3.2查找

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

查找成功的平均次数为**(n+1)/2**，平均时间性能为O(n)。

3.3插入

第$i(1\le i\le n+1)$个位置上插入一个值为X的新元素

void Insert(ElementType X, int i, List PtrL)
{if (PtrL->Last == MAXSIZE - 1){cout << "表满" << endl;return;}if (i < 1 || i > PtrL->Last + 2){cout << "位置不合法" << endl;return;}for (int j = PtrL->Last; j >= i - 1; j--){PrtL->Data[j + 1] = PtrL->Data[j];PrtL->Data[i - 1] = X;PrtL->Last++;return;}
}

平均移动次数为n/2，平均时间性能为O(n)。

3.4删除

删除表的第$i(1\le i\le n)$个位置上的元素

void Delete(int i, List PtrL)
{if (i < 1 || i > PtrL->Last + 1){cout << "不存在该元素" << endl;return;}for (int j = i; j <= PtrL->Last; j++){PtrL->Data[j - 1] = PtrL->Data[j];PtrL->Laast--;}return;
}

平均移动次数为**(n-1)/2**，平均时间习能为O(n)。

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

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

故插入、删除不需要移动数据元素，只需要修改“链”。

struct LNode
{ElementType Data;List Next;
}LNode L;
LNode* PtrL = &L;

主要操作的实现：

4.1求表长

int Length(LNode* PtrL)
{LNode* p = PtrL;int j = 0;while (p){p = p->Next;j++;}return j;
}

时间性能为O(N)。

4.2查找

• 按序号查找：FindKth

LNode* FindKth(int K, LNode* PtrL)
{LNode* p = PtrL;int i = 1;while (p != NULL && i < K){p = p->Next;i++;}if (i == K){return p;}else{return NULL:}
}

• 按值查找：Find

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

平均时间性能O(N)。

4.3插入

LNode* Insert(ElementType X, int i, LNode* PtrL)
{LNode* p, s;if (i == 1){s = new LNode(Data = X, Next = PrtL);return s;}p = FindKth(i - 1, PtrL);if (p == NULL){cout << "参数 i 错误" << endl;return NULL;}else{s = new LNode(Data = X, Next = PrtL);p->Next = s;return PtrL;}
}

平均查找次数为n/2，平均时间性能为O(n)。

4.4删除

LNode* Delete(int i, LNode* PtrL)
{LNode* p, s;if (i == 1){s = PtrL;if (PtrL != NULL){PtrL = PtrL->Next;}else{return NULL;}return PtrL;}p = FindKth(i - 1, PtrL);if (p == NULL){cout << "不存在i-1该元素" << endl;return NULL;}else if (p->Next == NULL){cout << "不存在i该元素" << endl;return NULL:}else{s = p->Next;p->Next = s->Next;return PtrL;}
}

平均查找次数为n/2，平均时间性能为O(n)。

4.5案例：单链表的逆转

• 现有一条单链表L，进行每K个结点就要逆转的操作

//伪代码
Ptr reverseL(Ptr head, int K)
{cnt = 1;new = head->next;old = new->next;while (cnt < K){tmp = old->next;old->next = new;new = old;old = tmp;cnt++;}head->next->next = old;return new;
}

• 测试数据
  • 有尾巴不反转
  • 边界测试
    • 地址取到上下界
    • 正好全反转
    • K = N全反转
    • K = 1不用反转
    • 最大（最后剩K - 1不反转）、最小N
  • 有多余结点

5、广义表

• 广义表（Generalized List）
  • 广义表时线性表的推广
  • 对于线性表而言，n个元素都是基本的单元素；
  • 广义表中，这些元素不仅可以是单元素，也可以是另一个广义表

6、多重链表

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

  • 多重链表中结点的指针域会有多个，如前面例子包含了Next和SubList两个指针域；
  • 但包含两个指针域的链表并不一定是多重链表，比如双向链表
  • 有广泛的用途：基本上如树、图这样相对复杂的数据结构都可以采用多重链表方式实现存储

• 例子

• 多重链表图

• 表示域Tag区分头结点和非零元素结点

二、堆栈

1、什么是堆栈

• 什么是堆栈

  • 堆栈（Stack）：具有一定操作约束的线性表；只在一端（栈顶、Top）做插入、删除
  • 插入数据：入栈（Push）
  • 删除数据：出栈（Pop）
  • 后入先出：Last In First Out （LIFO）

• 堆栈的抽象数据类型描述

  • **类型名称：**堆栈（Stack）
  • **数据对象集：**一个有0个或多个元素的有穷线性表
  • **操作表：**长度为MaxSize的堆栈$S\in Stack$，堆栈元素$item\in ElementType$
    • **Stack CreateStack(int MaxSize): **生成空堆栈，其最大长度为MaxSize
    • **int IsFull(Stack S, int MaxSize): **判断堆栈S是否已满
    • **void Push(Stack S): **将元素item压入堆栈
    • **int IsEmpty(Stack S): **判断堆栈S是否为空
    • **ElementType Pop(Stack S): **删除并返回栈顶元素

• 后缀表达式：运算符号位于两个运算数之后，如$abc\times +de/-$

• 中缀表达式：运算符号位于两个运算数之间，如$a+b\times c-d/e$

• 后缀表达式求值策略：从左到右“扫描”，逐个处理运算数和运算符号，每个运算符号处理左边最近两个运算数；

2、栈的顺序存储实现

2.1一个数组实现一个堆栈

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

• 定义

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

• 入栈

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

• 出栈

ElementType Pop(Stack PtrS)
{if (PtrS->Top == -1){cout << "堆栈空" << endl;return ERROR; //ERROR是ElementType的特殊值，标志错误}else{return (PtrS->Data[(PtrS->Top)--]);}
}

2.2一个数组实现两个堆栈

• 用一个数组实现两个堆栈，最大地利用数组空间，只要有空间就可以进行入栈操作；
  两个栈分别从数组的两头开始向中间生长；
  当两个栈的栈顶指针相遇时，表示两个栈都满了。

• 定义

#define MaxSize 存储数据元素的最大个数struct DStack
{ElementType Data[MaxSize];int Top1;int Top2;
}S;S.Top1 = -1;
S.Top2 = MaxSize;

• 入栈

void Push(DStack* PtrS, ElementType item, int Tag)
{//Tag作为区分两个堆栈的标志，取值为1和2if (PtrS->Top2 - PtrS->Top1 == 1){cout << "堆栈满" << endl;return;}if (Tag == 1){PtrS->Data[++(PtrS->Top1)] = item;}else{PtrS->Data[--(PtrS->Top2)] = item;}
}

• 出栈

ElementType Pop(DStack* PtrS, int Tag)
{if (Tag == 1){if (PtrS->Top1 == -1){cout << "堆栈1空" << endl;return NULL;}else{return PtrS->Data[(PtrS->Top1)--];}}else{if (PtrS->Top2 == MaxSize){cout << "堆栈2空" << endl;return NULL;}else{return PtrS->Data[(PtrS->Top2)++];}}
}

3、堆栈的链式存储实现

• 栈的链式存储结构实际上就是一个单链表，叫做栈链；插入和删除操作只能在栈链的栈顶进行，栈顶指针Top在链表的头部；栈链的头部可以设置一个头结点，此时头指针将指向头结点；一般地，头结点的数据域没有意义，设立它，是为了操作的统一与方便。

• 定义

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

• 创建链式堆栈

Stack CreateStack()
{Stack S = new SNode;S->Next = NULL;return s;
}

• 判断是否为空

int IsEmpty(Stack S)
{return (S->Next == NULL);
}

• 入栈

void Push(ElementType item, Stack S)
{Stack TmpCell = new SNode;TemCell->Element = item;TemCell->Next = S->Next;S->Next = TmpCell;
}

• 出栈

ElementType Pop(Stack S)
{Stack FirstCell;ElementType TopElem;if (IsEmpty(S)){cout << "堆栈空" << endl;return NULL:}else{FirstCell = S->Next;S->Next = FirstCell->Next;TopElem = FirstCell->Element;return TopElem;}
}

4、堆栈应用：表达式求值

• 中缀表达式如何转换为后缀表达式（从头到尾读取中缀表达式的每个对象，对不同对象按不同的情况处理）

  • 运算数：直接输出；
  • 左括号：压入堆栈；
    • 左括号在栈外时，优先级为最高；
    • 左括号在栈内时，优先级为最低；
  • 右括号：将栈顶的运算符弹出并输出，直到遇到左括号（出栈，不输出）；
  • 运算符：
    • 若优先级大于栈顶运算符时，则把它压栈；
    • 若优先级小于等于栈顶运算符时，将栈顶运算符弹出并输出；再比较新的栈顶运算符，直到该运算符大于栈顶运算符优先级为止，然后将该运算符压栈；
  • 若各对象处理完毕，则把堆栈中存留的运算符一并输出；

• 例子

• 堆栈的其它应用：
  • 函数调用及递归实现
  • 深度优先搜索
  • 回溯算法
  • $\cdots \cdots$

三、队列

1、什么是队列

• 什么是队列

  • **队列（Queue）：**具有一定操作约束的线性表；插入和删除操作，只能在一端插入，而在另一端删除
  • 数据插入：入队列（Add Q）
  • 数据删除：出队列（Delete Q）
  • **先进先出：**FIFO

• 队列的抽象数据类型描述

  • **类型名称：**队列（Queue）
  • **数据对象集：**一个有零个或多个元素的有穷线性表
  • **操作集：**长度为MaxSize的队列 $Q\in Queue$，队列元素 $item\in ElementType$
    • Queue Create(int MaxSize)：生成长度为MaxSize的空队列
    • int IsFullQ(Queue Q, int MaxSize)：判断队列Q是否已满
    • void AddQ(Queue Q, ElementType item):将数据元素item插入队列Q中
    • int IsEmptyQ(Queue Q)：判断队列Q是否为空
    • ElementType DeleteQ(Queue Q)：将队头数据元素从队列中删除并返回

2、队列的顺序存储实现

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

​ 一个正常的工作队列

顺环队列

该结构可以循环使用，对应的要空出一个位置当作那个位置为-1的空间

• 定义

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

• 入队列

void AddQ(Queue PtrQ, ElementType item)
{if ((PrtQ->rear + 1) % MaxSize == PtrQ->front){cout << "队列满" << endl;return;}PtrQ->rear = (PtrQ->rear + 1) % MaxSize;PtrQ->Data[PtrQ->rear] = item;
}

这里使用求模的技巧实现顺环结构的队列

• 出队列

ElementType DeleteQ(Queue PtrQ)
{if (PtrQ->rear == PtrQ->front){cout << "队列空" << endl;return ERROR;}else{PtrQ->front = (PtrQ->front + 1) % MaxSize;return PtrQ->Data[PtrQ->front];}
}

3、队列的链式存储实现

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

• 定义

struct Node 
{ElementType Data;struct Node* Next;
};
struct QNode
{Node* front;Node* rear;
};
typedef QNode* Queue;

• 创建链式队列

Queue creatQueue()
{Queue PtrQ;return PtrQ;
}

• 出队列

ElementType DeleteQ(Queue PtrQ)
{Node* FrontCell;ElementType FrontElem;if (PtrQ->front == NULL){cout << "队列空" << endl;return ERROR;}FrontCell = PtrQ->front;if (PtrQ->front == PtrQ->rear){PtrQ->front = NULL;PtrQ->rear = NULL;}else{PtrQ->front = PtrQ->front->Next;}FrontElem = FrontCell->Data;return FrontElem;
}

• 入队列

void AddQ(ElementType item, Queue PtrQ)
{Node* RearCell;RearCell->Data = item;RearCell->Next = NULL;if (PtrQ->front == PtrQ->rear){PtrQ->front = RearCell;PtrQ->rear = RearCell;return;}PtrQ->rear->Next = RearCell;PtrQ->rear = RearCell;
}

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

**主要思路：**相同指数的项系数相加，其余部分进行拷贝

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

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

• P1->expon == P2->expon：系数相加，若结果不为0，则作为结果多项式对应项的系数；同时，P1和P2都分别指向下一项；

• P1->expon > P2->expon：将P1的当前项存入结果多项式，并使P1指向下一项；

• P1->expon < P2->expon：将P2的当前项存入结果多项式，并使P2指向下一项；

• 当某一多项式处理完后，将另一个多项式的所有结点依次复制到结果多项式中去。

• 定义

struct PolyNode
{int coef;int expon;PolyNode* Next;
};typedef PolyNode* Polynomial;
Polynomial P1, P2;

• 主体函数

Polynomial PolyAdd(Polynomial P1, Polynomial P2)
{Polynomial front, rear;rear = new PolyNode;front = rear;int sum;//P1与P2两个都不为空时，一直执行while (P1 && P2){//compare比较大小switch (compare(P1->expon, P2->expon)){//P1的指数大，返回1case 1:attach(P1->coeef, P1->expon, &rear);//修改P1指向，往下执行P1 = P1->Next;break;//P2的指数大，返回-1case -1:attach(P2->coef, P2->expon, &rear);//修改P2指向，往下执行P2 = P2->Next;break;//P1和P2的指数相等，返回0case 0:sum = P1->coef + P2->coef;//如果系数相加不为0，则创建新结点if (sum != 0){attach(sum, P1->expon, &rear)}P1 = P1->Next;P2 = P2->Next;break;}}//未处理完的多项式for (; P1; P1 = P1->Next){attach(P1->coef, P1->expon, &rear);}for (; P2; P2 = P2->Next){attach(P2->coef, P2->expon, &rear);}//将最后一个结点的链表指向设为NULLrear->Next = NULL;//将空结点舍弃，直接指向多项式首结点front = front->Next;return front;
}

• 其它函数

void attach(int c, int e, Polynomial* pRear)
{//这里的pRear相当于二级指针//创建新结点Polynomial p = new PolyNode;//为新结点赋值p->coef = c;p->expon = e;p->Next = NULL;//让上一个结点的指针域指向新结点//修改rear的指向(*pRear)->Next = p;*pRear = p;
}

5、多项式的相乘和相加运算

5.1题意理解

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

5.2求解思路

• 求解思路

  • 1、多项式表示
  • 2、程序框架
  • 3、读多项式
  • 4、加法实现
  • 5、乘法实现
  • 6、多项式输出

• 1、多项式表示

  • 数组：

    • 编程简单、调试容易
    • 需要事先确定数组大小
    • 一种较好的实现方法是，动态数组

  • 链表：

    • 动态性强
    • 编程略为复杂、调试比较困难
    • 本次选用链表表示

  • 数据结构设计

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

• 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、如何读入多项式

  • rear初值

    • 3.1 rear初值为NULL；
      在attach函数中要判断rear是否为NULL；
    • 3.2 rear指向一个空结点；
      如此函数便不需要作出判断，本次采用这种方法

  • readPoly函数

    Polynomial readPoly()
    {Polynomial P, rear;int c, e, n;P = new PolyNode;P->Next = NULL;rear = P;cout << "多项式的项数为： " << endl;cin >> n;cout << "按幂指数由大到小的顺序输入： " << endl;while (n--){cout << "请分别输入该项的系数与指数： "  << endl;cin >> c;cin >> e;attach(c, e, rear);}P = P->Next;return P;
    }
    

  • attach函数

    void attach(itn c, int e, Polynomial& rear)
    {Polynomial P = new PolyNode;P->c = c;P->e = e;P->Next = NULL;rear->Next = P;rear = P;
    }
    

• 4、如何将两个多项式相加

  • add函数

  Polynomial add(Polynomial P1, Polynomial P2)
  {Polynomial P = new PolyNode;P->Next = NULL:Polynomial rear = P;int sum;while (P1 && P2){switch(compare(P1->expon, P2->expon)){case 1:attach(P1->coef, P1->expon, rear);P1 = P1->Next;break;case -1:attach(P2->coef, P2->expon, rear);P2 = P2->Next;break;case 0:sum = P1->coef + P2->coef;if (sum){attach(sum, P1->expon, rear);P1 = P1->Next;P2 = P2->Next;}break;}}while(P1){attach(P1->coef, P1->expon, rear);P1 = P1->Next;}while(P2){attach(P2->coef, P2->expon, rear);P2 = P2->Next;}P = P->Next;return P;}
  

• 5、如何将两个多项式相乘

  • 方法

    • 将乘法运算转换为加法运算；
      将P1当前项乘以P2多项式，再加到结果多项式里
    • 逐项插入；
      将P1当前项乘以P2当前项，并插入到结果多项式中，关键是要找到插入位置；初始结果多项式由P1第一项乘以P2获得；本次采用方法；

  • mult函数

  Polynomial mult(Polynomial P1, Poltnomial P2)
  {if (!P1 || !P2){return NULL;}Polynomial P, rear, t1, t2;int c, e;P = new PolyNode;P->Next = NULL;rear = P;t1 = P1;t2 = P2;while (t2){//创建初始结果多项式attach(t1->coef * t2->coef, t1->expon + t2->expon, rear);t2 = t2->Next;}t1 = t1->Next;while (t1){t2 = P2;rear = P;while (t2){c = t1->coef * t2->coef;e = t1->expon + t2->expon;//找出rear->Next->expon的值小于等于ewhile (rear->Next && rear->Next->expon > e){rear = rear->Next;}//判断是小于或是等于的情况if (rear->Next && rear->Next->expon == e){//判断coef值是否为零if (rear->Next->coef + c){rear->Next->coef += c;}else{rear->Next = rear->Next->Next; }}else{//若是小于的情况，创建新结点插入Polynomial t = new PloyNode;t->coef = c;t->expon = e;t->Next = rear->Next;rear->Next = t;}t2 = t2->Next;}t1 = t1->Next;}P = P->Next;return P;
  }
  

• 6、如何将多项式输出

void printPoly(Polynomial P)
{if (!P){cout << "0" << endl;return;}while (P){cout << P->coef << " " << P->expon << " ";P = P->Next;}cout << endl;
}