引子:多项式表示 #
【例】一元多项式及其运算 #
一元多项式：$f(x)=a_{0}+a_{1}x+…+a_{n-1}x^{n-1}+a_{n}x^{n}$
主要运输：多项式相加、相减、相乘等
【分析】如何表示多项式？
多项式的关键数据：
- 多项式项数n
- 各项系数$a_{i}$及指数$i$
方法1：顺序存储结构直接表示 #
数组各分量对应多项式各项：
$a[i]$:项$x^{i}$的系数$a_{i}$
例如： $f(x)=4x^{5}-3x^{2}+1$
两个多项式相加：两个数组对应分量相加
+
问题：如何表示多项式$x+3x^{2000}$?
方法2：顺序存储结构表示非零项 #
每个非零项$a_{i}x^{j}$涉及两个信息：系数$a_{i}$和指数$i$
可以将一个多项式看成是一个$(a_{i},j)$二元组的集合
用结构数组表示：数组分量是由系数$a^{i}$、指数$i$组成的结构，对应一个非零项
PS：按指数大小有序存储
相加过程： #
从头开始，比较两个多项式当前对应项的指数，从大到小加起来
P1:(9,12)(15,8)(3,2)
P2:(26,19)(-4,8)(-13,6)(82,0)
P3(P2+P1):(26,19)(9,12)(11,8)（-13，6）（3，2）（82，0）
方法3：链表结构存储非零项 #
链表中每个结点存储多项式中的一个非零项，包括系数和指数两个数据域以及一个指针域
| coef | expon | link |
|---|
typedef struct PolyNode*Ploynomial
struct PloyNode
{
int coef;
int expon;
Polynomial link;
}启示：
- 同一个问题可以有不同的表示（存储）方法
- 有一类共性问题：有序线性序列的组织和管理
线性表及顺序存储 #
“线性表（Linear List）”：由同类型数据元素构成有序序列的线性结构
- 表中元素个数称为线性表的长度
- 线性表没有元素时，称为空表
- 表起始位置称为表头，表结束位置称为表尾
类型名称：线性表（List）
数据对象集：线性表是n(≥0)个元素构成的有序序列（$a_{1},a_{2},…,a_{n}$）
操作集：线性表L∈List，整数i表示位置，元素X∈ElementType，线性表基本操作主要有：
- List MakeEmpty()：初始化一个空线性表L；
- ElementType FindKth（int K，List L）：根据位序K，返回相应元素；
- int Find（ElementType X，List L）：在线性表L中查找X的第一次出现位置；
- void Insert（ElementType X，int i， List L）：在位序i前插入一个新元素X；
- void Delete(int i,List L):删除指定位序i的元素；
- int Length(List L):返回线性表L的长度n
最简单的实现方式：
利用数组的连续存储空间顺序存放线性表的各元素
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
主要操作的实现
- 初始化（建立空的顺序表）
List MakeEmpty（）
{
List Ptrl;
Ptrl=(List)malloc(sizeof(struct LNode));
Ptrl->Last=-1;
return PtrL;
}- 查找
int 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;//找到后返回的是存储位置
}
//这样查找成功的平均比较次数为(n+1)/2，平均时间性能为0(n).顺序存储的插入和删除 #
- 插入（第i(1≤i≤n+1)个位置上插入一个值为X的新元素）
先移动（从后往前到n一个一个挪走），再插入
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--)
PtrL->Data[j+1]=PtrL->Data[j];//将ai到an倒序向后移动
PtrL->Data[i-1]=X;//插入新元素
PtrL->Last++//Last仍指向最后元素
return;
}
//平均移动次数为n/2，平均时间性能为O（n）- 删除（删除表的第i(1≤i≤n)个位置上的元素）
将元素删除后把后面的元素依次前移
coid Delete(int i, List PtrL)
{
int j;
if(i<1||i>PtrL->Last+1)//检查空表及删除位置的合法性
{
printf("不存在第{0}个元素",i)；
return;
}
for(j=i;j<=PtrL->Last;j++)
PtrL->Data[j-1]=PtrL->Data[j];//将ai+1到an顺序向前移动
PtrL->Last--;//让Last仍指向最后元素
return;
}
//平均移动次数为（n-1）/2，平均时间性能为O(n);链式存储及查找 #
不要求逻辑上相邻的两个元素物理上也相邻；通过“链”建立起数据元素之间的逻辑关系
插入、删除不需要移动数据元素，只需要修改链
typedef struct LNode*List;
struct LNode
{
ElementType Data;
List Next;
}
struct Lnode L;
List PtrL;主要操作的实现
- 求表长
//遍历法求表长
int Length(List PtrL)
{
List p=PtrL;//p指向表的第一个结点
int j=0;
while(p)
{
p=p->Next;
j++;//当前p指向的是第j个结点
}
return j;
时间性能为O（n）- 查找
（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;
}链式存储的插入和删除 #
- 插入
（在第i-1（1≤i≤n+1）个结点后插入一个值为X的新结点）
（1）先构造一个新结点，用s指向；
（2）再找到链表的第i-1个结点，用p指向；
（3）然后修改指针，插入结点（p之后插入新结点是s）
插入操作的实现：
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;
}
}- 删除（删除链表的第i（1≤i≤n）个位置上的结点）
（1）先找到链表的第i-1个结点，用p指向
（2）再用指针s指向要被删除的结点(p的下一个结点)
（3）然后修改指针，删除s所指结点
（4）最后释放s所指结点的空间
删除操作的实现：
List Delete(int i,List PtrL)
{
List p,s;
if(i==1)
{
s=PtrL;
if(PtrL~=NULL)PtrL=PtrL->Next;
else return NULL;
free(s);
return PtrL;
}
p=FindKth(i-1,PtrL);
if(p==NULL)
{
printf("第{0}个结点不存在",i-1);
return NULL;
}
elseif(p->Next==NULL)
{
printf("第{0}个结点不存在",i);
}
else
{
s=p->Next;
p->Next=s->Next;
free(s);
return PtrL;
}
}广义表与多重链表 #
【例】之前已经表示了一元多项式，那么二元多项式如何表示？
如：$P(x,y)=9x^{12}y^{2}+4x^{12}+15x^{8}y^{3}-x^{8}y+3x^{2}$
【分析】可以把二元多项式看作是关于x的一元多项式
$P(x,y)=(9y^{2}+4)x^{12}+(15y^{3}-y)x^{8}+3x^{2}$
相当于一元多项式时的常量系数变成了关于y的一元多项式
$P(x,y)=ax^{12}+bx^{8}+cx^{2}$
如果把上述多项式用“复杂”链表表示：
【关于复杂链表的图片】
多项式中常量的位置变为指针，指向关于y的一元多项式，这种表就被称为广义表
广义表（Generalized List） #
- 广义表是线性表的推广
- 对线性表来说，n个元素都是基本的单元素
- 广义表中，这些元素不仅可以是单元素也可以是另一个广义表
广义表可能遇到的问题：一个域有可能是一个不能分解的单元素，也有可能是一个指针
typedef struct GNode *GList;
struct GNode{
int Tag; //标志域：0表示结点是单元素，1表示结点是广义表
union{ //子表指针域Sublist与单元素数据域Data复用，即共用存储空间
ElementType Data;
Glist SubList;
}URegion;
Glist Next;//指向后继节点
}使用c语言的union来实现共用空间，通过tag来判断特定域是单元素还是另一个广义表
| Tag | Data | Next |
|---|---|---|
| Tag | SubList | Next |
多重链表 #
多重链表：链表中的节点可能同时隶属多个链
- 多重链表中结点的指针域会有多个，如前面例子包含了Next和SubList两个指针域；
- 但包含两个指针域的链表不一定是多重链表，比如双向链表就不是多重链表
** 多重链表有广泛的用途：
基本上如树、图这样相对复杂的数据结构都可以采用多重链表方式实现存储
【例】矩阵可以用二维数组表示，但二维数组表示有两个缺陷
- 数组的大小需要实现确定
- 对于“稀疏矩阵”，将造成大量的存储空间浪费
【A和B两个矩阵图】
【分析】采用一种典型的多重链表——十字链表来存储稀疏矩阵
- 只存储矩阵非0元素项，结点的数据域：行坐标Row、列坐标Col、数值Value
- 每个结点通过两个指针域，把同行、同列串起来：
- 行指针（或称为向右指针）Right
- 列指针（或称为向下指针）Down
【矩阵A的多重链表图】
- 用一个标识域Tag来区分头结点和非0元素结点
- 头结点的标识值为”Head”,矩阵非0元素结点的标识值为“Term”
- 结点的总体结构：Tag->Down||URegion||Right
- 矩阵非0元素结点：Term—>Down||Row/Col->Value||Right
- 头结点：Head->Down||Next||Right
什么是堆栈 #
是一种线性结构，也是一种特殊的线性表
计算机如何进行表达式求值 #
【例】算术表达式$5+6/2-34$,正确理解： $5+6/2-34=5+3-34=8-34=8-12=-4$
有两类对象构成的：
- 运算数，如2、3、4
- 运算符号，如加减乘除
- 不同运算符号的优先级不一样
把运算符号放在两个运算数后面，称为后缀表达式
- 中缀表达式：运算符位于两个运算数中间，如$a+b*c-d/e$
- 后缀表达式L:运算符号位于两个运算数之后，如$abc*+de/-$
后缀表达式的求值： #
【例】$62/3-42+=？$ $6/2-3+42=8$
后缀表达式求值策略：从左向右“扫描”，逐个处理运算数和运算符号
