三．线性表类型的实现——链式映象
1．单链表定义：用一组地址任意的存储单元存放线性表种的元素，以元素（数据的映象）+指针（指示后继元素存储位置的）= 结点（表示数据元素）
以“结点的序列”表示线性表——称作链表
以线性表中第一个数据元素a1的存储地址作为线性表的地址，称作线性表的头指针。
2．单链表的C语言描述
Typedef struct Lnode{
ElemType data; //数据域
Struct Lnode *next //指针域
}Lnode, *LinkList;
1． 操作的实现
a. 线性表的操作GetElem(L, i, &e)
在链表中的实现：
基本操作为：使指针p始终指向线性表中第j个数据元素
status GetElem_L(LinkList L, int pos,
ElemType &e)
{
p = L->next; j = 1; //初始化，p指向第一个结点，j为计数器
while(p && j<pos){p =
p->next; ++j;}
//指针向后查找，直到p指向第pos个元素或p为空
if(!p || j>pos)
return ERROR; //第pos个元素不存在
e = p->data; //取第pos个元素
return OK;
}
时间复杂度O（ListLength(L)）
b. 线性表的操作ListInsert(&L, i, e)
在链表中的实现：
基本操作：找到线性表中第i-1个结点，修改其指向后继的指针
有序对<a(i-1), a(i)>变为<a(i-1), e>和<e, a(i)>
status ListInsert_L(LinkList L, int
pos, ElemType e)
{
p = L; j=0;
while(p&& j<pos-1)
{p= p->next; ++j;} //寻找第pos-1个结点
if(!p || j>pos-1)
return ERROR; //pos小于1或者大于表长
s = (LinkList)malloc(sizeof(LNode));
//生成新结点
s->data = e;
s->next = p->next; //插入L中
p->next = s;
return OK;
}
时间复杂度O（ListLength(L)）
c. 线性表的操作ListDelete(&L, i, &e)
基本操作：找到线性表中第I-1个结点，修改其指向后继的指针
有序对<a(i-1), a(i)>变为<a(i), a(i+1)>和< a(i-1), a(i+1)>
status ListDelete_L(LinkList L, int
pos , ElemType &e)
{
p = L;
j= 0;
while(p->next &&
j<pos-1)
{p = p->next; ++j;} //寻找第pos个结点，并令p指向其前驱
if(!(p->next) || j>pos-1)
return ERROR; //删除位置不合理
q = p->next;
p->next = q->next; //删除并释放结点
e = q->data;
free(q);
return OK;
}
时间复杂度O（ListLength(L)）
d.线型表的操作：建立链表CreateList_L(….)，从后往前建立链表
void CreateList_l(LinkList& L, int n)
{
L = (LinkList)malloc(sizeof(LNode));
L->next = NULL; //先建立一个带头结点的单链表
for(i = 0; i>0; --i)
{
p = (LinkList)malloc(sizeof(LNode));
scanf(&p->data); //输入元素值
p->next = L->next; //插入到表头
L->next = p;
}
}
时间复杂度：O(ListLength(L));
e.线型表的操作：删除链表ListDelete_L(LinkList
L, int pos, ElemType &e)
{
p = L;
j = 0;
while(p->next && j< pos-1) //寻找第pos个结点，并令p指向其前驱
{
p = p->next;
++j;
}
if(!(p->next) || j>pos-1) //删除位置不合理
return ERROR;
q = p->next; //删除并释放结点
p->next = q->next;
e = q->data;
free(q);
return OK;
}
时间复杂度：O(ListLength(L));
对链表操作的最重要的就是一个指向结点的指针和一个计数器。
用线型表表示集合，应首先尽量对集合进行排序，提高运行效率。
用上述定义的单链表实现线型表的操作时，存在问题：
1． 链表的表长是一个隐含的值；
2． 在单链表的最后一个元素最后插入元素时，需遍历整个链表；
3．在链表中，元素的“位序”概念淡化，结点的“位置”概念强化。
改进链表的设置：
1．
加“表长”，“表尾指针”和“当前位置的指针”三个数据域
2．
基本操作由“位序”改为“指针”
四．一个带头结点的线型链表类型
typedef struct LNode{ //结点类型
ElemType data;
Struct LNode *next;
}*Link, *Position;
结点的基本操作：
status MakeNode(Link &p, ElemType e);
//分配由p指向的值为e的结点，并返回OK；
//失败，返回ERROR
void FreeNode(Link& p); 释放p指向的结点
typedef struct{ //链表类型
Link head , tail; //指向头结点和最后一个结点
Int len; //链表的长度
Link current; //指向当前访问的结点的指针，初始位置指向头结点
} LinkList;
链表的基本操作：
status InitList(LinkList& L);
//构造一个空的线型链表L，头指针，尾指针和当前指针均指向头结点，表长0
status DestroyList(LinkList& L);
//销毁线型链表L
引用操作：
status ListEmpty(LinkList L); //判表空
int ListLength(LinkList L); //求表长
status Prior(LinkList L); //改变当前指针指向其前驱
status Next(LinkList L); //改变当前指针指向其后继
ElemType GetCueElem(LinkList L); //返回当前指针所指的数据元素
Status LocatePos(LinkList L, int I); //
Status LocateElem(LinkList L, ElemType e, status(*compare)(ElemType,
ElemType)); //若存在与e
//满足函数判定关系的选素，则移动当前指针到第一个满足条件
//的元素，并返回OK；否则，返回ERROR
Status ListTraverse(LinkList L, status (*visit)()); //依次对每个元素调用函数visit
加工型操作：
status ClearList(LinkList& L); //重置为空表
status SetCurElem(LinkList& L, ElemType e); //更新当前指针所指数据元素
status Append(LinkList &L, Link s); //一串结点链接在最后一个结点之后
status InsAfter(LinkList &L, ElemType
e); //元素e插入到当前指针之后
status DelAfter(LinkList &L, ElemType*
e); //删除当前指针之后的结点
例如：
status InsAfter(LinkList& L, ElemType e)
{
if(! L.current) return Error;
if(! MakeNode(s, e) ) return Error;
s->next = L.current->next;
L.current->next = s;
return OK;
}
status DelAfter(LinkList& L, ElemType& e)
{
if(! (L.current &&
L.current->next) )
return Error;
q = L.current->next;
L.current->next = q->next;
e = q->data;
FreeNode(q);
return OK;
}
利用上述定义的线型链表可以完成线型表的其他操作：
例一：插入结点
status ListInsert_L(LinkList L, int I,
ElemType e)
{
//在带头结点的单链线型表L的第I个元素之前插入元素e
if(! LocatePos(L, I-1) ) return Error; // I不合法
if(InsAfter(L, e)) return OK;
//插入在第I-1个结点之后
else return Error;
}
例二，合并两个链表到第三个链表中
void MergerList_L(LinkList& La,
LinkList &Lb, LinkList& Lc, int(*compare)(ElemType, ElemType) )
{
if(! InitList(LC) ) return Error; //存储空间分配失败
LocatePos(La, 0);
LocatePos(Lb, 0); //当前指针指向头结点
If(DelAfter(La, e) ) a = e;
Else
a = MAXC; // MAXC为常量最大值
If((DelAfter(Lb, e) ) b = e;
Else
b = MAXC; // a 和b为两表中当前比较的元素
While( !(a == MAXC && b == MAXC) )
//La 和 Lb非空
{
if((*compare)(a, b) <= 0) // a <= b
{
InsAfter(Lc, a);
If(DelAfter(La, el) a = el;
Else a = MAXC;
}
else
//a > b
{
InsAfter(Lc, b);
If(DelAfter(Lb, el) b = el;
Else b = MAXC;
}
}
DestroyList(La);
DestroyList(Lb); //销毁La 和 Lb
Return OK;
}
五．其他形式的链表：
1． 双向链表：
typedef struct DuLNode{
ElemType data; //数据域
Struct DuLNode *prior;
//指向前驱的指针
Struct DuLNode *next; //指向后继的指针
}DuLNode, *DuLinkList;
2． 循环链表；
最后一个结点的指针域的指针又指向第一个结点的链表。
六．一元多项式的表示
ADT Polynomial{
数据对象：D = { a(i) | a(i) ∈ TermSet , I = 1, 2, 3,……,m,
m>0}
{TermSet
中的每个元素包含一个表示系数的实数和表示指数的整数}
数据关系：R = {< a(i-1),a(i)> | a(i-1),
a(i) ∈ D, 且a（i-1）中的指数值
< a(i)中的指数值， i = 1,2,….n}
基本操作：
CreatePolyn(&P, m);
输入m项的系数和指数，建立一元多项式P
DestroyPolyn(&P);
初始条件：一元多项式p已存在
操作结果：销毁一元多项式
PrintPolyn(&P);
初始条件：一元多项式p已存在
操作结果：打印一元多项式p
AddPolyn(&Pa, &Pb)
初始条件：一元多项式pa , pb已存在
操作结果：pa = pa + pb，并销毁pb
SubtractPolyn(&Pa, &Pb)
初始条件：一元多项式pa , pb已存在
操作结果：pa = pa – pb, 并销毁pb
MultiplyPolyn(&Pa, &Pb)
初始条件：一元多项式pa , pb已存在
操作结果：pa = pa * pb, 并销毁pb
PolynLength(&P)
初始条件：一元多项式p已存在
操作结果：返回p中的项数
}ADT Polynomial
如此定义的多项式可以看成始一个有序表，则多项式定义中的各个操作均可利用有序表操作来完成。
抽象类型数据Polynomial的实现
typedef
struct{//项的表示，多项式的项作为LinkList的数据元素
float coef; //系数
int expn; //指数
}term, ElemType; //两个类型名：term用于本ADT，ElemType为LinkList的数
//据对象名
typedef LinkList polynomial; //用带表头结点的有序链表表示多项式
int cmp(term a , term b) //比较多项式的项，a的指数值<b的指数值 返回-1
//
a的指数值 〉b的指数值 返回0
//
a的指数值 = b的指数值 返回1
例：创建一个一元多项式
void CreatePolyn(polynomial &p, int m)
{
//输入m项的系数和指数，建立表示一元多项式的有序链表P
InitList(P);
e.coef = 0.0;
e.expn = -1;
SetCurElem(P, e) //置头结点的数据元素
For(i=1; i<= m ; i++) //依次输入m个非零项
{
Scanf(e.coef, e.expn);
If(! LocateElem(P, e, (*cmp)() ) //当前链表中不存在该指数项
InsAfter(P, e); //在第一个大于插入项指数的数据项前插入
//新的数据项
}
}
七．本章小结：
了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示的存储结构是顺序结构和链式结构。用前者表示的线性表为顺序表，用后者表示的线性表为链表。
熟练掌握这两类存储结构的描述方法，以及线性表的各种基本操作的实现。
比较两种线性表的不同特点和使用场合。当表的数据元素之间的关系不发生变化，则使用顺序表较好，反之则利用链表较好。
