二、线性表
2.0 线性结构的特点
特点：在数据元素非空的有限集中：
（1）存在唯一的一个被称做“第一个”的数据元素；
（2）存在唯一的一个被称做“最后一个”的数据元素；
（3）出第一个外，集合中的每个数据元素均只有一个前驱；
（4）除最后一个外，集合中每个数据元素均只有一个后继；
2.1线性表的类型定义
线性表：是n个数据元素的有限序列；
记录：一个数据元素由若干个数据项组成
文件：含有大量记录的线性表
直接前驱：当i=1，2，……，n-1，ai有且仅有一个直接后继，当i=2，3，……，n时，ai有且仅有一个直接前驱。
线性表的长度：线性表中元素的个数n；
2.1.1算法
例1：
将LA和LB中的数据元素按值非递减有序排列
代码：
void MergeList(List La, List Lb, List &Lc){
InitList(Lc);//构造一个新的线性表Lc
i=j=1;
k=0;
La_len = ListLength(La);//La表的长度
Lb_len = ListLength(Lb);//Lb表的长度
while((i<=La_len) && (j<=Lb_len)){
GetElem(La,i,ai);
GetElem(Lb,j,bj);
//用ai、bj返回线性表中的i、j位置的值
if(ai<bj){
ListInsert(Lc,++k,ai);//在线性表的i位置插入新的数据元素，长度加一
++i;
}else{
ListInsert(Lc,++k,bj);
++j;
}
}
while(i<=La_len){
GetElem(La,i++,ai);
ListInsert(Lc,++k,ai);
}
while(j<=Lb_len){
GetElem(Lb,j++,bj);
ListInsert(Lc,++k,bj);
}
}
2.2线性表的顺序表示和实现
2.2.1定义：
定义：用一组地址连续的存储单元依此存储线性表的数据元素
2.2.2位置表示
第i+1个数据元素存储位置：
第i个数据元素的存储位置为：
其中
是第一个数据元素的存储位置，又叫起始位置或者基地址。
线性表的这种机内表示叫做顺序存储结构或顺序映像，这种表叫做顺序表
2.2.3顺序存储结构特点：
线性表的顺序存储结构是一种 随机存储 的存储结构
2.2.4优缺点
优点：
随机存取表中任一元素，存储位置可以用一个简单、直观的公式表示；
缺点：
在插入或删除操作时需要移动大量元素。
2.3线性表的链式表示和实现
2.3.1链式存储结构的特点
特点：
用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）
单链表是非随机存储的存储结构
2.3.2线性表链式存储结构定义及相关术语
结点由指针域和数据域构成，指针域中存储的信息称作指针或链想，n个结点链结成一个链表，即为线性表的链式存储结构
静态链表
用数组描述的链表
循环链表
表中最后一个结点的指针域指向头结点，整个链表形成一个环。
有时候会在循环链表中设立尾指针，不设头指针，可以简化某些操作
双向链表
在双向链表的结点中有两个指针域，其一指向直接后继，另一个指向直接前趋
双向链表的插入操作
Status ListInsert_Dul(DuLinkList &L, int i, ElemType e){
//带头结点的双链循环线性表L中第i个位置之前插入元素e
//i的合法值为1<=i<=表长+1
if(!(p = GetElemP_Dul(L,i)))//在L中确定插入位置
{
return ERROR;//p为null，插入位置不合法
}
if(!(s = (DuLinkList)malloc(sizeof(DuLNode))))
return ERROR;
s->data=e;
s->prior=p->prior;
p->prior->next=s;
s->next=p;
p->prior=s;
return OK;
}
双向链表的删除操作
Status ListDelete_DuL(DuLinkList &L, int i, ElemType &e){
//删除带头结点的双链循环线性表L的第i个元素，i的合法值为1<=i<=表长
if(!(p = GetElemP_DuL(L,i)))//在L中确定第i个元素的位置指针p
return ERROR;//p=null，即为第i个元素不存在
e=p->data;
p->prior->next=p->next;
p->next->prior=p->prior;
free(p);
return OK;
}
2.3.4链表优缺点
链表优点：在空间的合理利用上和插入、删除时不需要移动等
成为线性表的首选存储结构
缺点：求表长麻烦，淡化了“位序”概念
2.4一元多项式的表示及相加
一元多项式
对于次数不高的多项式相加，可以采用顺序存储结构
对于次数很高的多项式相加，采用链式存储结构（便于插入和删除数据）
两个一元多项式相乘的算法，可以利用两个一元多项式相加算法来实现。
