数据结构入门学习（全是干货）——线性结构

数据结构入门学习（全是干货）——线性结构

1.1 引子：多项式表示

例子：一元多项式及其运算

多项式的基本运算包括：

1. 多项式相加
2. 多项式相减
3. 多项式相乘

分析——如何表示多项式

在实现多项式运算时，关键在于如何表示多项式。其表示的关键数据包括：

1. 多项式项数 n：表示多项式中有多少项。
2. 各项的系数 ai 和对应的指数 i：每项的系数与指数配对存储，ai 的下标 i 表示其对应的指数。

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

顺序存储是一种简单的存储方式。每一项按顺序从最高次项到常数项存储在一个数组中，即使其中某些项的系数为 0，也会占用存储空间。

注解：不管中间的项是否为 0，顺序存储依然为其分配空间。

例子：对于最高次指数为 2000 的多项式，尽管其中有许多零项，依然需要 2001 个存储位置。因为下标从 0 开始，所以是 2001 而不是 2000。

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

在这种方法中，只存储多项式的非零项，且按照指数的大小排序。指数较大的项排在前面，指数较小的项排在后面。

多项式相加过程： 从头开始，比较两个多项式当前项的指数。如果指数相等，则将系数相加；如果不相等，则保留指数较大的项。

这里的(11，8)是(15，8)与(-4，8)的结合结果，因为指数一样，所以可以结合为一个

例子：对于多项式15x^8 与 -4x^8，两者的指数相同，合并后为 11x^8。

这种方法可以有效节省存储空间，且操作效率不算差。

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

链表是一种更灵活的存储方式，适用于稀疏多项式。每个节点存储多项式中的一个非零项，包括：

1. 系数域 coef：存储系数。
2. 指数域 expon：存储指数。
3. 指针域 link：指向下一个非零项。

链表节点按指数递减顺序链接。比较两个多项式时，逐项比较其指数，指数大的项先输出；如果指数相等，则将系数相加。

//代码演示
typedef struct PolyNode*Polynomial;
struct PolyNode{int coef;int expon;Polynomial link;
}

---

1.2 线性表及顺序存储

线性表：由相同类型的数据元素构成的有序列表，表中每个元素都有一个位置。

线性表的基本特征

1. 表的长度：表中元素的个数。
2. 空表：没有元素的线性表称为空表。
3. 表头和表尾：表的起始位置称为表头，结束位置称为表尾。

多项式表示问题的启示

1. 同一个问题可以有不同的表示（存储）方法，通常可以使用链表或数组来存储。
2. 有一类共性问题：如何高效组织和管理有序线性序列。

---

1.3 线性表的顺序存储实现

线性表的顺序存储是通过数组的连续存储空间依次存放各个元素。

typedef struct LNode*List;
struct LNode{ElementType Data [MAXSIZE];//定义了一个数组，数组的分类类型是ElementTypeint List;//代表线性表的最后一个元素，这样的一个结构就可以抽象的实现一个线性表
};
struct LNode L;//定义一个变量L
List PtrL;//还有一个变量PtrL//访问下标为i的元素：L.Data[i]或PtrL->Data[i]//线性表的长度：L.Last+1或PtrL->Last+1

主要操作的实现

1. 初始化（MakeEmpty）：建立一个空的线性表。

   List MakeEmpty()
   {List PtrL;PtrL = (List)malloc(sizeof(struct LNode));//通过malloc申请这样子一个结构PtrL->Last = -1;//Last设置为-1，因为Last是代表最后一个元素。Last为0是代表这个表有一个元素放在第一个位置，没元素就设置为-1，然后把这个结构的指针返还回来return PtrL;
   }
   

2. 查找：在表中查找元素。

   
   //科普小知识
   find函数用于查找数组中的某一个指定元素的位置。比如：有一个数组[0, 0, 5, 4, 4]；
   问：元素5的在什么位置，find函数 返回值 为 2；find （数组名 + 起始查找元素的位置， 数组名 + 结束查找的元素位置， 想要查找的元素）int Find(ElementType X, List PtrL)//List PtrL是线性表结构的指针
   {int i = 0;while(i <= PtrL ->Last && PtrL->Data[i]! = X )i++if(i > PtrL->Last)  return -1;//如果没找到，返回-1else return i;//找到后返回的是存储位置
   }
   查找成功的平均比较次数为(n+1)/2,平均时间性能为O(n)
   

顺序存储的插入和删除

插入操作：在第 i（1 ≤ i ≤ n+1）个位置上插入一个值为 X的新元素。新元素放在第 i−1 个位置之前。

步骤：

1. 把 i−1 之后的所有元素后移一位，腾出空间。
2. 将新元素 X 插入到第 i−1 个位置。
3. 

//插入操作实现
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--)//List是最后一个元素的位置PtrL->Data[j+1] = PtrL->Data[j];//将a1~an倒序向后移动PtrL->Data[i-1] = X;//新元素插入PtrL->Last++;//Last仍指向最后元素return;
}
//平均移动次数为n/2，平均时间性能为O(n)

删除操作：删除第 i（1 ≤ i ≤ n）个位置上的元素。删除时，将 i 之后的所有元素前移一位。

接下来我们来介绍一下另外一个操作：删除如果把后移数组元素的循环for ( j = PtrL->Last; j >= i-1; j-- )PtrL->Data[j+1]=PtrL->Data[j];改为for ( j = i-1; j <= PtrL->Last; j++ )PtrL->Data[j+1]=PtrL->Data[j];那会是什么后果？分量Data[i-1]到Data[Ptrl->Last+1]都是同一个值，即移之前Data[i-1]的值

删除(删除表中的第i(1 <= i <= n)个位置上的元素)

//删除掉这个元素后就空出来一个位置了，这种时候就需要从左往右的顺序往前挪
//删除操作实现
void Detele(int i,List PtrL)//已知PtrL这个线性表
{int j;if( i < 1 || i > PtrL->Last+1){printf("不存在第%d个元素",i);return;}for(j = i;j <= PtrL->Last;j++)PtrL->Data[j-1] = PtrL->Data[j];//将a的下标(i+1)~an顺序往前移动PtrL->Last--;//Last仍指向最后元素return;
}
//平均移动次数为(n-1)/2,平均时间性能为O(n)

---

1.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)按序号查找：FindKth;采用类似链表的遍历方法
   List FindKth(int K,List PtrL)
   {List p = PtrL;//首先把p这个临时变量设置为链表的表头int i = 1;while(p != NULL && i < K){p = p->Next;//让指针往后挪一位i++;}if( i == K ) return p;//找到第K个，返回指针else return NULL;//否则返回空
   }
   //(2)按值查找：Find
   List Find(ElementType X,List PtrL)
   {List p = PtrL;while(p != NULL && p -> Data != X)p = p->Next;return p;
   }
   //返回的是两种结果，不是p就是NULL，调用Find函数，发现它返回值等于NULL，就说明没找着
   

---

1.5 链式存储的插入和删除

插入操作：在第i（1 ≤ i ≤ n+1）个节点后插入一个值为 X 的新节点。插入操作不需要移动数据，只需修改指针。

//(1)先构造一个新结点，用s指向;  这个时候可以用malloc这个函数来申请一块空间
//(2)再找到链表的第i-1个结点，用p指向;
//(3)然后修改指针，插入结点(p之后插入新结点是s)//下图中的操作步骤：让s指向下一个结点，p的Next附给s的Next
//如果修改指针的两个步骤交换了一下哎，会发生什么？(语句执行顺序为：(1) p->Next=s;  (2) s->Next=p->Next;)
//答案：s->Next指向s,从而不能正确完成插入

//malloc复习区域
#include<malloc.h>或者#include<alloc.h>//两者的内容是完全一样的
如果分配成功：则返回指向被分配内存空间的指针
不然返回指针NULL
同时，当内存不再使用的时候，应使用free()函数将内存块释放掉。
关于：void*,表示未确定类型的指针，c,c++规定void*可以强转为任何其他类型的指针，关于void还有一种说法就是其他任何类型都可以直接赋值给它，无需进行强转，但是反过来不可以
malloc:
malloc分配的内存大小至少为参数所指定的字节数
malloc的返回值是一个指针，指向一段可用内存的起始位置，指向一段可用内存的起始地址，多次调用malloc所分配的地址不能有重叠部分，除非某次malloc所分配的地址被释放掉malloc应该尽快完成内存分配并返回（不能使用NP-hard的内存分配算法）实现malloc时应同时实现内存大小调整和内存释放函数（realloc和free）
malloc和free是配对的，如果申请后不释放就是内存泄露，如果无故释放那就是什么也没做，释放只能释放一次，如果一块空间释放两次或者两次以上会出现错误（但是释放空指针例外，释放空指针也等于什么也没做，所以释放多少次都是可以的。）
2、malloc和new
new返回指定类型的指针，并且可以自动计算所需要的大小。int *p;
p = new int;//返回类型为int* ，分配的大小是sizeof(int)
p = new int[100];//返回类型是int*类型，分配的大小为sizeof(int)*100而malloc需要我们自己计算字节数，并且返回的时候要强转成指定类型的指针。int *p;
p = (int *)malloc(sizeof(int));
1）malloc的返回是void*,如果我们写成了：p=malloc(sizeof(int));间接的说明了（将void转化给了int*，这不合理）
（2）malloc的实参是sizeof(int)，用于指明一个整型数据需要的大小，如果我们写成p=(int*)malloc(1),那么可以看出：只是申请了一个一个字节大小的空间。
（3）malloc只管分配内存，并不能对其进行初始化，所以得到的一片新内存中，其值将是随机的。一般意义上：我们习惯性的将其初始化为NULL，当然也可以使用memset函数。
简单的说：
malloc函数其实就是在内存中找一片指定大小的空间，然后将这个空间的首地址给一个指针变量，这里的指针变量可以是一个单独的指针，也可以是一个数组的首地址，这要看malloc函数中参数size的具体内容。我们这里malloc分配的内存空间在逻辑上是连续的，而在物理上可以不连续。我们作为程序员，关注的是逻辑上的连续，其他的操作系统会帮着我们处理。
下面就来看看malloc具体是怎么实现的。
首先要了解操作系统相关的知识：
虚拟内存地址和物理内存地址
为了简单，现代操作系统在处理物理内存地址时，普遍采用虚拟内存地址技术。即在汇编程序层面，当涉及内存地址时，都是使用的虚拟内存地址。采用这种技术时，每个进程仿佛自己独享一片2N字节的内存，其中N是机器位数。例如在64位CPU和64位操作系统下每个进程的虚拟地址空间为264Byte。
这种虚拟地址空间的作用主要是简化程序的编写及方便操作系统对进程间内存的隔离管理，真实中的进程不太可能如此大的空间，实际能用到的空间大小取决于物理内存的大小。

插入实现操作

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; //这种情况下链表的头指针是不会变的}
}
//平均查找次数是n/2

删除操作：删除链表中第 i（1 ≤ i ≤ n）个位置上的节点。删除操作只需修改指针，不需要移动数据。

//(1)先找到链表的第i-1个结点，用p指向;
//(2)再用指针s指向要被删除的结点(p的下一个结点);
//(3)然后修改指针，删除s所指结点;
//(4)删除的结点(s)的空间要记得free释放掉(重要)，这样内存空间才不会泄漏
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;}
}
//平均时间复杂度也是n/2

---

1.6 广义表与多重链表

广义表（Generalized List）

广义表是线性表的推广形式。与线性表不同，广义表中的元素不仅可以是单个元素，还可以是另一个广义表。

特点：

1. 广义表中的元素可能是不可分解的单元，也可能是另一个广义表。
2. 广义表可以通过使用 C 语言中的 union 来表示，联合不同类型的数据。

typedef struct GNode *GList;
struct GNode{int Tag;//标志域：0表示结点时单元素，1表示结点是广义表   这个Tag就是标志union{//子表指针域Sublist与单元素数据域Data复用，即共同存储空间ElementType Data;GList SubList;}URegion;GList Next;//指向后续结点
};

例子：在广义表中，节点可以既包含数据元素，也包含指向其他广义表的指针。

---

多重链表（Multilist）

多重链表是指链表中的节点可能同时隶属于多个链。每个节点可以有多个指针域，比如 Next 和 SubList。

特点：

1. 多重链表中的节点可能同时在多个链表中，指针域会有多个。
2. 这种结构广泛用于表示复杂的数据结构，如树和图。

稀疏矩阵：矩阵中的0很多，会造成空间浪费

二维数组可以用来表示选课的一种记录

上图中就是用多重链表来表示稀疏矩阵的一种方法

上图中的行与列相互穿插在一起形成十字链表

Head是作为行这个链表的头结点，也作为列这个链表的头结点

Tem：代表稀疏矩阵里面的非零的项

上图：4代表这个稀疏矩阵共有4行，总共有5列，非零项个数总共有7项

通过上图那个指针就可以找到所有列的头节点

在矩阵的多重链表表示中，第i行的head和第i列的head实际上是同一个结点(正确)

1. 用一个标识域Tag来区分头结点和非0元素结点
2. 头节点的标识值为"Head"，矩阵非0元素结点的标识值为"Term"

经过union的串联在一起，他们共性都是有两个指针：一个Down，一个Right。他们不一样的地方在中间部分。所有我们可以把他们union在一起，形成(a)这个结构

以上就是稀疏矩阵用十字链表解决的一种基本思路

---

2.1 堆栈（Stack）

计算机如何进行表达式求值？

有两类对象组成：

1. 运算数：如 2、3、4 等数字。
2. 运算符号：如 +、-、*、/ 等运算符号。

每种运算符号的优先级不同，影响其执行顺序。

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

中缀表达式与后缀表达式表达的运算顺序是相同的，只是写法不同。前缀表达式的特点是，运算符在运算数前。

假设有表达式 a + bc - d / e，其前缀表达式为 - + abc / de。

---

后缀表达式求值策略

后缀表达式的求值过程是从左向右扫描表达式，逐个处理运算数和运算符。以下是计算步骤：

• 例子：

  6 2 / 3 - 4 2 * +
  

  • 先处理 6 2 /，得到 3。
  • 然后处理 3 - 3，得到 0。
  • 接着处理 4 2 *，得到 8。
  • 最后将 0 和 8 相加，得到 8。

算法过程：

1. 遇到运算数：将运算数存入堆栈中，等待参与运算。
2. 遇到运算符号：弹出堆栈中相应数量的运算数，并执行运算，然后将结果压入堆栈中。

堆栈的特点是后入先出，即最后压入堆栈的元素最先弹出。这使得它非常适合处理表达式求值的过程，尤其是在后缀表达式的求值中。堆栈用于临时存储运算数，并在需要时倒序输出，以符合运算符的顺序。

堆栈求值的时间复杂度为 O(N)，其中 N 是表达式的长度。

堆栈是一种特殊的线性表，其操作受到限制，只能在一端（栈顶）进行插入和删除操作。它遵循后入先出（LIFO）原则。

堆栈的基本操作

1. 入栈（Push）：将元素压入栈顶。
2. 出栈（Pop）：将栈顶元素弹出。
3. 栈顶元素：存取栈顶元素。

数据对象集(堆栈)：一个有0个或者多个元素的有穷线性表

操作集(堆栈)：长度为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)：删除并返回栈顶元素;(重点)相当于删除操作，需要判别堆栈有没有满或空。空了就不能删除

按ABC顺序入栈，可以产生CAB这样的出栈序列？不可以，是CBA序列

Push：推(压入)

Pop：弹出

---

2.2 堆栈的顺序存储实现

堆栈的顺序存储通常使用数组实现，栈顶指针指向栈顶元素。

#define MaxSize <存储数据元素的最大个数>
typedef struct SNode *Stack;
struct SNode{ElementType Data[MaxSize];int Top;//用来指示栈顶的位置，Top不是地址而是一个整型变量，代表了栈顶位置它的数组下标在哪里
};
//(1)入栈
void Push (Stack PtrS, ElementType item)//包含两个参数，一个是堆栈本身，一个是用指针表示PtrS(Stack类型指针，Stack本身就是堆栈的意思)
{if( PtrS -> Top == MaxSize -1 ){//入栈需要判断堆栈满了没有，满了就不能再加了，有极限的。下标从0开始，所以到MaxSize-1就已经满了printf("堆栈满") return;}else{PtrS ->Data[++(PtrS -> Top)] = item;//item放在Top上面的一个位置，这一个语句实际做了两个事情，一是把item放到Top+1这个位置上，同时把Top值加实现了入栈的操作return;}
}
//(2)出栈
ElementType Pop(Stack PtrS)
{if(PtrS -> Top == -1 ){printf("堆栈空");//一样的操作，出栈之前要检查以下是不是空了，空了可就没东西往外掏了return ERROR;//ERROR是ElementType的特殊值，标志错误}else{return(PtrS -> Data[(PriS -> Top)--]);}
}

【例】请用一个数组实现两个堆栈，要求最大地利用数组空间，使数组只要有空间入栈操作就可以成功
//简单将把数组对分的话来做两个堆栈会有一个问题：有一个堆栈满了，但另一个堆栈是空的，还有空余空间
//要求是数组还有空余空间，就允许有入栈操作
//用法就是一个从最左边往里放，另一个从最右边往里放。中间就是空余的大家都可以用//根据刚才讲的方法，用一个数组来表示双堆栈，如果这两个堆栈的栈顶位置分别是top1和top2，那么可以用top1+top2==MaxSize(数组大小）来判别堆栈是否满？不可以
//因为top1跟top2代表的是数组的下标，所以top1代表的距离是中间空余的位置＋top2，top2也是同理//正确的分析：使这两个栈分别从数组的两头开始向中间生长；当两个栈的栈顶指针相遇时，表示两个栈都满了#define MaxSize<存储数据元素的最大个数>struct DStack{ElementType Data[MaxSize];int Top1;//堆栈1的栈顶指针int Top2;//堆栈2的栈顶指针}S;S.Top1 = -1;//这是堆栈1空的位置S.Top2 = MaxSzie;//堆栈2空的位置，数组最后一个位置是MaxSize - 1//Push(弹出)具体操作
void Push (struct DStack *PtrS,ElementType item,int Tag )
{//Tag作为区分两个堆栈的标志，取值为1和2，Tag的值1和2分别代表第一个堆栈跟第二个堆栈if( PtrS -> Top2 - PtrS -> Top1 == 1){printf("堆栈满"); return;}if( Tag == 1)//对第一个堆栈操作PtrS -> Data[++(PtrS -> Top1)] = item;//Top1后面一个位置else//对第二个堆栈进行操作PtrS -> Data[--(PtrS -> Top2)] = item;//Top2前面一个位置
}//Pop(压入)操作
ElementType Pop (struct DStack *PtrS,int Tag )
{//Tag作为区分两个堆栈的标志，取值为1和2，Tag的值1和2分别代表第一个堆栈跟第二个堆栈if( Tag == 1){//对第一个堆栈进行操作if( PtrS -> Top1 == -1){//堆栈1空printf("堆栈1空"); return NULL;}else {return PtrS -> Data [(PtrS -> Top1)--];}}else{//对第二个堆栈操作if( PtrS -> Top2 == MaxSize){//堆栈2空printf("堆栈2空"); return NULL;    }else{return PtrS -> Data[(PtrS -> Top2)++];   }
}

注意：在数组实现中，需要判别堆栈是否已满或为空。

---

2.3 堆栈的链式存储实现

使用链表来实现堆栈时，不需要担心栈满的问题。每次入栈时，动态分配新的节点并插入。

栈的链式存储结构实际上就是一个单链表，叫做链栈。插入和删除操作只能再链栈的栈顶进行。
栈顶指针Top应该再链表的哪一头？若用单向链表实现一个堆栈，链表的头和尾都可以作为top？
只有链表的头才行。链表的尾空余插入，但是删除就有问题，找不到前面的结点了，因为这是单项链表找不到前面的结点typedef struct SNode*Stack;struct SNode{ElementType Data;struct SNode*Next;};

Stack CreateStack()
{//构建一个堆栈的头结点，返回指针Stack S;S = (Stack)malloc(sizeof(struct SNode));s->Next = NULL;return S;
}int IsEmpty(Stack S)
{//判断堆栈s是否为空，若为空函数返回整数1，否则返回0return (S->Next == NULL);
}

void Push(ElementType item,Stack S)
{//将元素item压入堆栈Sstruct SNode *TmpCell;TmpCell = (struct SNode *)malloc(sizeof(struct SNode));TmpCell -> Element = item;TmpCell -> Next = S -> Next;S -> Next = TmpCell;
}

使用链表来进行Push操作的时候不用判别堆栈满不满的问题，因为链表通过不断申请结点空间往里面插

数组实现堆栈的话，数组大小是固定的，存在着满不满的问题

ElementType Pop(Stack S)
{//删除并返回堆栈s的栈顶元素struct SNode *FirstCell;ElementType TopElem;if( IsEmpty (S) ){printf("堆栈空");return NULL;}else{FirstCell = S ->Next;TopElem = FirstCell -> Element;free(FirstCell);return TopElem;}
}

---

2.4 堆栈的应用：表达式求值

堆栈的一个重要应用是用来进行表达式的求值，尤其是后缀表达式（逆波兰表达式）的求值。

回忆：应用堆栈实现后缀表达式求值的基本过程：

1. 从左到右读入后缀表达式的各项(运算符或运算数);

1.运算数：入栈;
2.运算符：从堆栈中弹出适当数量的运算数，计算并结果入栈;
3.最后，堆栈顶上的元素就是表达式的结果值

中缀表达式求值

基本策略：将中缀表达式转化为后缀表达式，然后求值
如何将中缀表达式转化为后缀？
观察一个简单例子：2+9/3-5  ->  2 9 3 / + 5 -
1.运算数相对顺序不变
2.运算符号顺序发生改变1.需要存储"等待中"的运算符号2.要将当前运算符号与"等待中"的最后一个运算符号比较(如果前面的一个运算符号的优先级比我来得高，就说明可以拿来计算，如果优先度比我低，那么当前的运算符号还不能说就直接拿来运算，因为后面可能还有优先级比我高的，所以需要保留起来，这个时候我们就需要一种结构来实现我们运算符号的存储，那结构就是堆栈)输出：2 9 3记下：+ /碰到运算数 我们就把它输出碰到运算符号 我们等着有括号怎么办？
【例】a*(b+c)/d = ?		a b c + * d /
当括号被丢进堆栈里面的时候，它的优先级降到最低，优先算括号里的内容
算数规则：当遇到同一个优先级的时候，它的顺序是从左到右T(N) = O(N)

请试试应用堆栈将中缀表达式2*(6/3+4)-5转换为后缀表达式。在这个转换过程中，堆栈元素最多时元素个数是多少？3个

中缀表达式如何转换为后缀表达式
从头到尾读取中缀表达式的每个对象，对不同对象按不同的情况处理。
1.运算数：直接输出
2.左括号：压入堆栈
3.右括号：将栈顶的运算符弹出并输出，直到遇到左括号(出栈，不输出);
4.运算符：1.若优先级大于栈顶运算符时，则把它压栈;2.若优先级小于等于栈顶运算符时，将栈顶运算符弹出并输出;再比较新的栈顶运算符，直到该运算符大于栈顶运算符优先级为止，然后将该运算符压栈;
5.若各对象处理完毕，则把堆栈中存留的运算符一并输出

堆栈的其他应用：
函数的调用及递归实现
深度优先搜索(图)
回溯算法(老鼠走迷宫案例)等等

---

3 队列及其实现

什么是队列

队列也是一种受限制的线性表，但不同于堆栈，队列遵循先进先出（FIFO）原则。插入操作在队尾进行，删除操作在队头进行。

队列的基本操作

1. 入队（AddQ）：将数据插入队尾。
2. 出队（DeleteQ）：从队头删除数据。

特点

插入和删除操作：只能一端插入，而在另一端删除(一般的线性表都可以在任何位置进行插入和删除)

跟堆栈相比：堆栈插入和删除都是只能在一端

先来先服务(跟堆栈相反)

先进先出：FIFO

队列的抽象数据类型描述类型名称:队列(Queue)数据对象集：一个有0个或多个元素的有穷线性表操作集：长度为MaxSize的队列Q属于Queue，队列元素item属于ElementType1.Queue CreateQueue( int MaxSize )：生成长度为MaxSize的空队列；2.int IsFullQ(Queue Q,int MaxSize)：判断队列Q是否已满;3.void AddQ(Queue Q,int MaxSize)：将数据元素item插入队列Q中4.int IsEmptyQ( Queue Q):判断队列Q是否为空;5.ElementType DeleteQ( Queue Q):将队头元素从队列中删除并返回

---

3.1 队列的顺序存储实现

顺环队列是一种有效的队列实现方法，利用数组的循环结构解决队列满的问题。

队列的顺序存储结构通常由一个一维数组和一个记录队列头元素位置的变量front以及一个记录队列尾元素位置的变量rear组成的#define MaxSize <储存数据元素的最大个数>struct QNode{ElementType Data[MaxSize];int rear;//指针int front;//指针};
typedef struct QNode *Queue;如果空队列开始时front和rear值都是-1，当插入4个元素并删除2个元素后，front和rear值分别是多少？1和3

顺环队列

1.这种方案：堆栈空和满的判别条件是什么？
根据front rear的相对关系(就是他们的距离)来判别的font rear的取值范围是0 -- n-1
2.为什么会出现空，满无法区分？根本原因？
如果大小是n的话，font跟rear的差距的情况就是n种，队列的装载元素的情况有n+1种
解决方案：
(1)使用额外标记：Size或者tag域
当加入一个元素的时候Szie加1，删除一个元素的时候Size减1，通过Size等于0还是等于n就可以知道空的还是满的
使用标记tag 0 1，当我们插入一个元素的时候tag设为1，删除一个元素的时候tag等于0，当front跟rear相等时不清楚空还是满的时候，观察tag，tag就代表了最后一次操作是插入还是删除，就知道是空还是满
(2)仅使用n-1个数组空间(最多放n-1个元素，留一个空位出来就可以避免front跟rear相等的情况)

(1)入队列

void AddQ(Queue PtrQ,ElementType item)//item放到队列中 队列使用Queue的结构指针PtrQ来进行表示
{if((PtrQ -> rear+1)%MaxSize == PtrQ -> front){//具体代换：5+1对6求余为0printf("队列满");return;}PtrQ -> rear = (PtrQ -> rear+1)%MaxSize;PtrQ -> Data[PtrQ -> rear] = item;
}

(2)出队列

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

3.2 队列的链式存储实现

队列的链式存储结构也可以用一个单链表实现。插入和删除操作分别在链表的两头进行；队列指针front和rear应该分别指向链表的哪一头？
队列的front也可以设在链表的尾？错误，不行的 
只能前面做删除(front)，后面做加入(rear)，如果倒过来的话，删掉了就不知道前面一个在哪里了struct Node{ElementType Data;//结点本身的信息struct Node *Next;//把结点串在一起};
struct QNode{//链队列结构struct Node *rear;//指向队尾结点struct Node *front;//指向队头结点
};
typedef struct QNode *Queue;
Queue PtrQ;

不带头结点的链式队列出队操作的示例

ElementType DeleteQ(Queue PtrQ)
{struct Node *FrontCell;ElementType FrontElem;if(PtrQ -> front == NULL){printf("队列空"); return ERROR;}FrontCell = PtrQ -> front;if(PtrQ -> front == PtrQ -> rear)//若队列只有一个元素PtrQ -> front = PtrQ -> rear = NULL;//删除后队列置为空elsePtrQ -> front = PtrQ -> front -> Next;FrontElem = FrontCell -> Data;free(FrontCell);//释放被删除结点空间return FrontElem;
}

---

4 多项式的加法运算实现

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

具体实现代码(数据结构)
struct PolyNode{int coef;//系数int expon;//指数struct PolyNode link;//指向下一个节点的指针
};
typedef struct PolyNode*Polynomial;
Polynomial P1,P2;多项式加法运算(算法思路):
两个指针p1和p2分别指向这两个多项式第一个结点，不断循环：1. P1->expon == P2 -> expon(这里比较的其实是指数)：系数相加，若结果不为0，则作为结果多项式对应项的系数。同时，P1和P2都分别指向下一项2. P1->expon > P2 -> expon：将P1的当前项存入结果多样式，并使P1指向下一项;3. P1->expon < P2 -> expon：将P2的当前项存入结果多样式，并使P2指向下一项;当某一多项式处理完时，将另一个多项式的所有结点依次复制到结果多项式中去

演变过程------------------------分割线

接着是=>

函数实现
Polynomial PolyAdd(Polynomial P1.Polynomial P2)
{Polynomial front,rear,temp;//多项式的头是第一个，尾巴第二个，int sum;rear = (Polynomial) malloc(sizeof(struct PolyNode));//临时申请一个空结点作为结果多项式的表头front = rear;//由front记录结果多项式链表头结点，申请的空间front都指向它while(P1 && P2)//当两个多项式都有非零待处理时(判空)switch(Compare(P1->expon,P2->expon)){//比较P1P2这两个项的所指向的当前这个项的指数，第一个值大返回1，第二个值大返回-1，两个值相等返回0case1://P1大Attach(P1->coef,P1->expon,&rear);//两个参数分别代表我要拷贝的这一项的系数和指数P1 = P1 -> link;break;//形成的新的项把它接到rear的后面，P1往后挪case-1：//P2大Attach(P2->coef,P2->expon,&rear);P2 = P2 -> link;break;case0://一样大sum = P1->coef + P2->coef;if(sum)Attach(sum.P1->expon,&rear);//判定，如果为0就不用加到结果多项式里面去，不为零就把sum作为系数跟对于的指数凑在一起，把他接到rear的后面去P1 = P1 -> link;P2 = P2 -> link;break;}//将未处理完的另一个多项式的所有节点依次复制到结果多项式中去for(;P1;P1 = P1 -> link) Attach(P1->coef,P1->expon,&rear);//第一个for循环处理P1不空，如果不空就是把P1后面的每一项全部Attach(接到结果多项式的后面的意思)，同时把P1往后挪for(;P2;P2 = P2 -> link) Attach(P2->coef,P2->expon,&rear);//如果P1不空的话P2肯定就空了，也就把P2后面的每一项一个一个拷贝到rear的后面去rear ->link = NULL;//指向结果多项式的最后一项temp = front;front = front -> link;//令front指向结果多项式第一个非零项free(temp);//释放临时空表头结点  怎么释放？=>将front赋给temp，然后front往后挪，front原来是指向这个临时的表头结点，这个表头结点的下一项就是我们真正的多项式的第一项 return front;//返回结果多样式中这个单项链表的第一个结点
}问题：如果当前p1指向项的（系数，指数）为（2，4），同时P2指向项为(2，6)，那么循环中的switch是执行哪个case?
case -1

Attach实现
void Attach(int c,int e,Polynomial*pRear)//传进来的是c跟e的系数跟指数。当前最后一个结点的指针位置传进来的是Polynomial这个类型的指针(Polynomial本身也是指针)，所以pRear实际上是指针的指针//C语言是函数常数值传递
{Polynomial P;P = (Polynomial)malloc(sizeof(struct PloyNode));//结点类型是struct PolyNode这个类型P -> coef = c;//对新结点赋值P -> expon = e;P -> link = NULL;(*pRear)->link = P;//把新申请的结点P插到rear的后面*pRear = P;//修改pRear值
}

通过上述各种数据结构，可以高效地实现多项式的加法运算。