DS笔记(2)顺序表与链表
一、 顺序表---线性表的顺序存储
1．内涵：
线性表的顺序存储指用一组地址连续的存储
单元依次存储线性表的数据元素。这称为顺序表。
2．特点：
* 存储单元地址连续（需要一段连续空间）
* 逻辑上相邻的数据元素其物理位置也相邻
* 随机存取
* 存储密度为大（100%）
3．优点：
* 不需要额外空间来存储元素之间的关系
* 可以随机存取任一元素
4．缺点：
* 插入和删除运算需要移动大量元素
* 需要一段连续空间
* 预先分配足够大的空间
* 表的容量难以扩充
(可以通过使用动态数组数据类型来描述顺序表而改进最后两个缺点)
5．存储位置的计算
对线性表L,设每个元素占k个存储单元，则有：
递推关系：
LOC(ai+1)=LOC(ai )+k
任一元素ai+1的存储位置：
LOC(ai)=LOC(a1 )+(i-1)*k
(其中1<= i <=ListLength(L))
二、 链表---线性表的链式存储
1．内涵：
线性表的链式存储指用任意的存储单元存放线性表中的元素，每个元素与其前驱和（或）后继之间的关系用指针来存储。这称为链表。
术语：
* 结点
* 数据域
* 指针域
* 头指针
* 头结点
分类：
* 单链表
* 循环链表
* 双向链表
* 双向循环链表
* 静态链表
2．数据类型描述
//----------用结构指针描述------------
typedef struct LNode{
ElemType data //数据域
struct LNode *next //指针域
} Lnode, *LinkList
3．单链表上插入运算的实现T(n)=O(n)
4．链表应用:一元多项式的相加
一元多项式的链式存储结构
//----------用结构指针描述------------
typedef struct Term{
float coef //系数数据域
int expn //指数数据域
struct Term *next //指针域
} Term, *LinkList
一元多项式相加的运算规则
“和多项式”中结点无需另生成，可看成是将多项式B加到
多项式A上。设p和q分别指向多项式A和B中某一结点，比较结点中的指数项：
若p^.exp<q^.exp,则p结点应是“和多项式”中的一项，令p指针向后移；
若p^.exp>q^.exp,则q结点应是“和多项式”中的一项，令q结点插入在p结点之前，且q指针在原来的链表上后移；
若p^.exp=q^.exp,则将两个结点中的系数相加，当和不为零时修改p结点中的系数域，释放q结点；反之，“和多项式”中没有此项，从A表中删去p结点，同时释放p和q结点。
算法如下：
PROC add_poly(VAR pa:polyty; pb:polytp);
p:=pa^.next; q:=pb^.next;
pre:=pa; pc:=pa;
WHILE (p!=NIL)AND (q!=NIL) DO
CASE
p^.exp<q^.exp:
[pre:=p; p:=p^.next];
p^.exp=q^.exp:
[x:=p^.coef+q^.coef;
IF x!=0
THEN [ p^.coef:=x; pre:=p]
ELSE [pre^.next:=p^.next;
dispose(p)];
p:=pre^.next; u:=q;
q:=q^.next; dispose(u)]
p^.exp>q^.exp:
[u:=q^.next; q^.next:=p; pre^.next:=q; pre:=q; q:=u ]
IF q!= NIL THEN pre^.next:= q;
dispose(pb);
ENDP; {add_poly}