数据结构之线性表1

2.1 线性表的定义和基本操作

1.线性结构的特点是：在数据元素的非空有限集中，
（1）存在惟一的一个被称做“第一个”的数据元素；
（2）存在惟一的一个被称做“最后一个”的数据元素；
（3）除第一个之外，集合中的每个数据元素均只有一个前驱；
（4）除最后一个之外，集合中每个数据元素均只有一个后继。

2.线性表是一种线性结构，在一个线性表中数据元素的类型是相同的，或者说线性表是
由同一类型的数据元素构成的线性结构。

定义如下：
线性表是具有相同数据类型的 n(n≥0)个数据元素的有限序列，通常记为：
(a1，a2，… ai-1，ai，ai+1，…an)

其中 n 为表长， n＝0 时称为空表。
需要说明的是：ai 为序号为 i 的数据元素（i=1,2,…,n）

通常将它的数据类型抽象为 ElemType，ElemType 根据具体问题而定。
线性表是一个相当灵活的数据结构，它的长度可根据需要增长或缩短，即对线性表的数
据元素不仅可以进行访问，还可进行插入和删除等。

3.抽象数据类型线性表的定义如下：
ADT List{
数据对象：D = { ai | ai∈ElemSet, i=1,2,…,n, n≧0 }
数据关系：R = {<ai-1, ai> | ai-1, ai∈D, i=2,3,…,n }

基本操作：
InitList( &L )
操作结果：构造一个空的线性表 L；
GetElem( L, i, &e )
初始条件：线性表 L 已存在，1≦i≦ListLength(L)
操作结果：用 e 返回 L 中第 i 个数据元素的值；
ListInsert ( L, i, &e )
初始条件：线性表 L 已存在，1≦i≦ListLength(L)
操作结果：在线性表 L 中的第 i 个位置插入元素 e；
LocElem(LA, e, equal( ))
初始条件：线性表 L 已存在，1≦i≦ListLength(L)
操作结果：在线性表 L 中查找是否存在元素 e；
} ADT List

例、假设利用两个线性表 LA 和 LB 分别表示两个集合 A 和 B( 即线性表中的数据元素
即为集合中的成员) ，现要求一个新的集合 A=AUB 。这就要求对线性表作如下操作：扩大
线性表 LA ，将存在于线性表 LB 中而不存在于线性表 LA 中的数据元素插入到线性表 LA
中去。只要从线性表 LB 中依次取得每个数据元素，并依值在线性表 LA 中进行查访，若不
存在，则插入之。

上述操作过程可用下列算法描述之。
void union(List &.La, List Lb) {
/扩将所有在线性表 Lb 中但不在 La 中的数据元素插入到 La 中
La _len= ListLength(La); Lb_ len= ListLength(Lb); //求线性表的长度
for (i = 1; i <= Lb_len; i++) {
GetElem( Lb, i , e); //取 Lb 中第 i 个数据元素赋给 e
if (! LocateElem(La，e, equal)) ListInsert( La, + + La_ 1en， e);
// La 中不存在和 e 相同的数据元素，则插入之
} // union

例、已知线性表 LA 和 LB 中的数据元素按值非递减有序排列，现要求将 LA 和 LB 归
并为一个新的线性表 LC ，且 LC 中的数据元素仍按值非递减有序排列。例如，设
LA = (3 , 5, 8, 11)
LB = (2 , 6, 8, 9, 11 , 15 , 20)
则 LC = (2 , 3, 5, 6, 8, 8, 9, 11 , 11 , 15 , 20)
从上述问题要求可知， LC 中的数据元素或是 LA 中的数据元素，或是 LB 中的数据元
素，则只要先设 LC 为空表，然后将 LA 或 LB 中的元素逐个插入到 LC 中即可。为使 LC 中
元素按值非递减有序排列，可设两个指针 i 和 j 分别指向 LA 和 LB 中某个元素，若设 i 当
前所指的元素为 a，j 当前所指的元素为 b，则当前应插入到 LC 中的元素 c 为

显然，指针 i 和 j 的初值均为 1. 在所指元素插入 LC 之后，在 LA 或 LB 中顺序后移。
void MergeList( List La, List Lb, List &.Lc) {
//已知线性表 La 和 Lb 中的数据元素按值非递减排列. //归并 La 和 Lb 得到新的线位表 Lc，Lc 的数据元素也按值非递减排列. InìtList(Lc);
i = j = 1，k = 0, La_ 1en = ListLength(La); Lb_1en= ListLength(Lb), while ((i <=La _len) && (j <= Lb_ 1en)) {//La 和 Lb 均非空
GetElem(La，i , aì); GetE1em(Lb，j , bj);
if (ai <= bj) {Listlnsert(Lc, ++k, ai); ++ i , }
else {Listlnsert(Lc, ++k, bj) , ++ j , }
while (i <= La_ 1en) {
GetElem(La, i++ , ai); ListInsert(Lc, ++k, ai);
while (j <= Lb_ 1en) {
GetElem(Lb，j ++ , bj); LìstInsert(Lc，++ k , bj);
} // MergeList

上述两个算法的时间复杂度取决于抽象数据类型 List 定义中基本操作的执行时间.

假如
GetElem 和 Listlnsert 这两个操作的执行时间和表长无关. LocateElem 的执行时间和表长成
正比，则第一个算法的时间复杂度为 O (ListLength(LA) *ListLength(LB)) ，第二个算法的时
间复杂度则为 O( ListLength(LA) + ListLength(LB))。虽然第二个算法中含 3 个(while)循环语
句，但只有当 i 和 j 均指向表中实际存在的数据元素时，才能取得数据元素的值并进行相
互比较;并且当其中一个线性表的数据元素均已插入到线性表 LC 中后，只要将另外一个线性
表中的剩余元素依次插入即可。因此，对于每一组具体的输入(LA 和 LB) ，后两个(while ) 循
环语句只执行一个循环体。

2.2 线性表的实现

2.2.1 顺序存储

1.顺序表的定义
线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素，用这种存储形式存储的线性表称其为顺序表。

因为内存中的地址空间是线性的，因此，用物理上的相邻实现数据元素之间的逻辑相邻关系是既简单又自然的。

设 a1 的存储地址为 Loc(a1)，每个数据元素占 d 个存储地址，则第 i 个数据元素的地址
为：

Loc(ai)=Loc(a1)+(i-1)*d1≤i≤n
这就是说只要知道顺序表首地址和每个数据元素所占地址单元的个数就可求出第 i 个数
据元素的地址来，这也是顺序表具有按数据元素的序号随机存取的特点
2.顺序表上基本运算的实现
由于高级程序设计语言中的数组类型也有随机存取的特性，因此，通常都用数组来描述
数据结构中的顺序存储结构。

#define MaxSize 100
typedef int ElemType
typedef struct
{ ElemType data[MaxSize];
int length;
} SqList; /*顺序表类型*/

（1）初始化线性表 InitList(L)
该运算的结果是构造一个空的线性表 L。实际上只需将 length 成员设置为 0 即可。

void InitList(SqList *&L) //引用型指针
{
L=(SqList *)malloc(sizeof(SqList));
/*分配存放线性表的空间*/
L->length=0; }

本算法的时间复杂度为 O（1）。

（2）销毁线性表 DestroyList(L)
该运算的结果是释放线性表 L 占用的内存空间。

void DestroyList(SqList *&L)
{
free(L); }

本算法的时间复杂度为 O（1）。
（3）判定是否为空表 ListEmpty(L)
该运算返回一个值表示 L 是否为空表。若 L 为空表,则返回 1,否则返回 0。

int ListEmpty(SqList *L)
{
return(L->length==0); }

本算法的时间复杂度为 O（1）。
（4）求线性表的长度 ListLength(L)
该运算返回顺序表 L 的长度。实际上只需返回 length 成员的值即可。
int ListLength(SqList *L)
{
return(L->length); }
本算法的时间复杂度为 O（1）。
（5）输出线性表 DispList(L)
该运算当线性表 L 不为空时,顺序显示 L 中各元素的值。

void DispList(SqList *L)
{
int i;
if (ListEmpty(L))
return;
for (i=0;i<L->length;i++)
printf("%c",L->data[i]);
printf("\n"); }

（6）求某个数据元素值 GetElem(L,i,e)
该运算返回 L 中第 i(1≤i≤ListLength(L))个元素的值,存放在 e 中。

int GetElem(SqList *L,int i,ElemType &e)
{
if (i<1 || i>L->length)
return 0;
e=L->data[i-1];
return 1; }

本算法的时间复杂度为 O（1）。
（7）按元素值查找 LocateElem(L,e)
该运算顺序查找第 1 个值域与 e 相等的元素的位序。若这样的元素不存在,则返回值为 0。

int LocateElem(SqList *L, ElemType e)
{
int i=0;
while (i<L->length && L->data[i]!=e)
i++;
if (i>=L->length)
return 0;
else
return i+1; }

（8）插入数据元素 ListInsert(L,i,e)
该运算在顺序表 L 的第 i 个位置(1≤i≤ListLength(L)+1)上插入新的元素 e。
思路：如果 i 值不正确,则显示相应错误信息；否则将顺序表原来第 i 个元素及以后元素
均后移一个位置,腾出一个空位置插入新元素,顺序表长度增 1。

int ListInsert(SqList *&L,int i,ElemType e)
{
int j;
if (i<1 || i>L->length+1)
return 0;
i--; /*将顺序表逻辑位序转化为 elem 下标即物理位序*/
for (j=L->length;j>i;j--)
L->data[j]=L->data[j-1];
/*将 data[i]及后面元素后移一个位置*/
L->data[i]=e;
L->length++; /*顺序表长度增 1*/
return 1; }

（9）删除数据元素 ListDelete(L,i,e)
删除顺序表 L 中的第 i(1≤i≤ListLength(L))个元素。
思路：如果 i 值不正确,则显示相应错误信息；否则将线性表第 i 个元素以后元素均向前
移动一个位置,这样覆盖了原来的第 i 个元素,达到删除该元素的目的,最后顺序表长度减 1。

int ListDelete(SqList *&L,int i,ElemType &e)
{
int j;
if (i<1 || i>L->length)
return 0;
i--; /*将顺序表逻辑位序转化为 elem 下标即物理位序*/
e=L->data[i];
for (j=i;j<L->length-1;j++)
L->data[j]=L->data[j+1];
/*将 data[i]之后的元素前移一个位置*/
L->length--; /*顺序表长度减 1*/
return 1;}

3.顺序表的合并问题
对于有序顺序表 La 和 Lb 而言，合并算法的时间复杂度为 O( La. length +Lb. length-1) 。

int MergeList（ SqList La, SqList Lb, SqList *Lc）{
pa=La.elem; pb=La.elem;
Lc->listsize = Lc.length=La.length+ Lb.length;
Pc=Lc->elem =( ElemType*)malloc(Lc.listsize*sizeof(ElemType));
If(!Lc.elem) exit(overfiow);
pa_last= La.elem+La.length-1;
pb_last= Lb.elem+Lb.length-1;
while(pa<=pa_last&&pb<=pb_last){
if(*pa<=*pb) *pc++=*pa++;
else
*pc++=*pb++; }
while(pa<=pa_last) *pc++=*pa++;
while(pb<=pb_last) *pc++=*pb++;}

2.2.2 链式存储

（一）单链表
1.基本概念
线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。

因此，为了表示每个数据元素 ai 与其直接后继数据元素 ai-1 之间的逻辑关系，对数据元素 ai 来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息(即直接后继的存储位置)。这两部分信息组成数据元素 ai 的存储映像，称为结点(node).

它包括两个域: 其中存储数据元素信息的域称为数据域;存储直接后继存储位置的域称为指针域. 指针域中存储的信息称做指针或链。

n 结点(ai (1<=i<=n)的存储影像)链接成链表，即为线性表(a1 ,a2 …,an)的链式存储结构. 又由于此链表的每个结点中只包含一个指针域，故又称线性链表或单链表。
单链表可由头指针惟一确定，在 C 语言中可用"结构指针"来描述。

typedef struct LinkList /*定义单链表结点类型*/
{ ElemType data;
struct LinkList *next; /*指向后继结点*/
} LinkList;

假设 L 是 LinkList 型的变量，则 L 为单链表的头指针，它指向表中第一个结点。若 L
为"空"(L==NULL) ，则所表示的线性表为"空"表，其长度 n 为"零"。有时，我们在单链表的
第一个结点之前附设一个结点，称之为头结点。头结点的数据域可以不存储任何信息，也可
存储如线性表的长度等类的附加信息，头结点的指针域存储指向第一个结点的指针(即第一个
元素结点的存储位置)。如图 (a) 所示，此时，单链表的头指针指向头结点。若线性表为空表，
则头结点的指针域为"空"，如图(b) 所示。

C 语言中的两个标准函数 malloc 和 free 。通常，在设有"指针"数据类型的高级语言中
均存在与其相应的过程或函数。假设 p 和 q 是 LinkList 型的变量，执行 p=(LinkList * ) malloc
( sizeof (LinkList)) 的作用是由系统生成一个 LinkList 型的结点，同时将该结点的起始位置赋
给指针变量 p; 反之，执行 free(q) 的作用是由系统回收一个 LinkList 型的结点。
2.单链表上基本运算的实现
1)建立单链表
●头插法——在链表的头部插入结点建立单链表
链表与顺序表不同，它是一种动态管理的存储结构，链表中的每个结点占用的存储空间
不是预先分配，而是运行时系统根据需求而生成的，因此建立单链表从空表开始，每读入一
个数据元素则申请一个结点，然后插在链表的头部。

void CreateListF(LinkList *&L,ElemType a[],int n)
{ LinkList *s;int i;
L=(LinkList *)malloc(sizeof(LinkList)); /*创建头结点*/
L->next=NULL;
for (i=0;i<n;i++)
{ s=(LinkList *)malloc(sizeof(LinkList));
/*创建新结点*/
s->data=a[i]; s->next=L->next;
/*将*s 插在原开始结点之前,头结点之后*/
L->next=s;
}
}

●尾插法——在单链表的尾部插入结点建立单链表头插入建立单链表简单，但读入的数
据元素的顺序与生成的链表中元素的顺序是相反的，若希望次序一致，则用尾插入的方法。
因为每次是将新结点插入到链表的尾部，所以需加入一个指针 r 用来始终指向链表中的尾
结点，以便能够将新结点插入到链表的尾部。
初始状态，头指针 L=NULL，尾指针 r =NULL; 按线性表中元素的顺序依次读入数据元
素，不是结束标志时，申请结点，将新结点插入到 r 所指结点的后面，然后 r 指向新结点
（注意第一个结点有所不同）。

void CreateListR(LinkList *&L,ElemType a[],int n)
{ LinkList *s,*r;int i;
L=(LinkList *)malloc(sizeof(LinkList));
/*创建头结点*/
r=L; /*r 始终指向终端结点,开始时指向头结点*/
for (i=0;i<n;i++)
{ s=(LinkList *)malloc(sizeof(LinkList));
/*创建新结点*/
s->data=a[i];r->next=s; /*将*s 插入*r 之后*/
r=s;
}
r->next=NULL; /*终端结点 next 域置为 NULL*/
}

单链表的基本运算
（1）初始化线性表 InitList(L)
该运算建立一个空的单链表,即创建一个头结点。

void InitList(LinkList *&L)
{
L=(LinkList *)malloc(sizeof(LinkList)); /*创建头结点*/
L->next=NULL; }

（2）销毁线性表 DestroyList(L)
释放单链表 L 占用的内存空间。即逐一释放全部结点的空间。

void DestroyList(LinkList *&L)
{ LinkList *p=L,*q=p->next;
while (q!=NULL)
{ free(p);
p=q;q=p->next;
}
free(p); }

（3）判线性表是否为空表 ListEmpty(L)
若单链表 L 没有数据结点,则返回真,否则返回假。

int ListEmpty(LinkList *L)
{
return(L->next==NULL); }

（4）求线性表的长度 ListLength(L)
返回单链表 L 中数据结点的个数。

int ListLength(LinkList *L)
{ LinkList *p=L;int i=0;
while (p->next!=NULL)
{ i++;
p=p->next;
}
return(i); }

（5）输出线性表 DispList(L）
逐一扫描单链表 L 的每个数据结点,并显示各结点的 data 域值。

void DispList(LinkList *L)
{ LinkList *p=L->next;
while (p!=NULL)
{ printf("%c",p->data);
p=p->next;
}
printf("\n"); }

(6) 求线性表 L 中指定位置的某个数据元素 GetElem(L,i,&e)
思路：在单链表 L 中从头开始找到第 i 个结点,若存在第 i 个数据结点,则将其 data 域值
赋给变量 e。

int GetElem(LinkList *L,int i,ElemType &e)
{ int j=0;
LinkList *p=L;
while (j<i && p!=NULL)
{ j++;
p=p->next;
}
if (p==NULL)
return 0; /*不存在第 i 个数据结点*/
else /*存在第 i 个数据结点*/
{ e=p->data;
return 1;
}
}

（7）按元素值查找 LocateElem(L,e)
思路：在单链表 L 中从头开始找第 1 个值域与 e 相等的结点,若存在这样的结点,则返回
位置,否则返回 0。

int LocateElem(LinkList *L,ElemType e)
{LinkList *p=L->next;int n=1;while (p!=NULL && p->data!=e)
{ p=p->next;
n++; }
if (p==NULL)
return(0);
else
return(n);}

（8）插入数据元素 ListInsert(&L,i,e)
思路：先在单链表 L 中找到第 i-1 个结点*p,若存在这样的结点,将值为 e 的结点*s 插入到
其后。

int ListInsert(LinkList *&L,int i,ElemType e)
{ int j=0;
LinkList *p=L,*s;
while (j<i-1 && p!=NULL) /*查找第 i-1 个结点*/
{ j++;
p=p->next;
}
if (p==NULL)
return 0; /*未找到位序为 i-1 的结点*/
else /*找到位序为 i-1 的结点*p*/
{ s=(LinkList *)malloc(sizeof(LinkList));
/*创建新结点*s*/
s->data=e;
s->next=p->next; /*将*s 插入到*p 之后*/
p->next=s;
return 1;
}
}

（9）删除数据元素 ListDelete(&L,i,&e)
思路：先在单链表 L 中找到第 i-1 个结点*p,若存在这样的结点,且也存在后继结点,则删
除该后继结点。

int ListDelete(LinkList *&L,int i,ElemType &e)
{ int j=0;
LinkList *p=L,*q;
while (j<i-1 && p!=NULL) /*查找第 i-1 个结点*/
{ j++;
p=p->next;
}
if (p==NULL) return 0; /*未找到位序为 i-1 的结点*/
else /*找到位序为 i-1 的结点*p*/
{ q=p->next; /*q 指向要删除的结点*/
if (q==NULL)
return 0;
/*若不存在第 i 个结点,返回 0*/
p->next=q->next; /*从单链表中删除*q 结点*/
free(q); /*释放*q 结点*/
return 1;
}
}

变形之一：
删除单链表中值为 key 的所有结点。
基本思想：从单链表的第一个结点开始，对每个结点进行检查，若结点的值为 key，则
删除之，然后检查下一个结点，直到所有的结点都检查。
算法描述：

void Delete_LinkList_Node(LinkList *L，int key)
/* 删除以 L 为头结点的单链表中值为 key 的第一个结点 */
{ LinkList *p=L, *q=L–>next;
while ( q!=NULL）
{ if (q–>data==key)
{ p->next=q->next; free(q);
q=p->next; }
else
{ p=q; q=q–>next; }
}
}

变形之二：
删除单链表中所有值重复的结点，使得所有结点的值都不相同。
基本思想：从单链表的第一个结点开始，对每个结点进行检查：检查链表中该结点的所
有后继结点，只要有值和该结点的值相同，则删除之；然后检查下一个结点，直到所有的结
点都检查。
算法描述：

void Delete_Node_value(LinkList *L)
/* 删除以 L 为头结点的单链表中所有值相同的结点 */
{ LinkList *p=L->next, *q, *ptr;
while ( p!=NULL) /* 检查链表中所有结点 */
{ q=p, ptr=p–>next;
/* 检查结点 p 的所有后继结点 ptr */
while (ptr!=NULL)
{if (ptr–>data==p->data)
{ q->next=ptr->next;
free(ptr); ptr=q->next; }
else { q=ptr; ptr=ptr–>next;}
}
p=p->next ;
}
}

3.单链表的合并
设有两个有序的单链表，它们的头指针分别是 La 、 Lb，将它们合并为以 Lc 为头指针
的有序链表。
算法描述

LinkList *Merge_LinkList(LinkList *La， LinkList *Lb)
/*合并以 La, Lb 为头结点的两个有序单链表*/
{ LinkList *Lc, *pa , *pb , *pc, *ptr ;
Lc=La ; pc=La ;
pa=La->next ;
pb=Lb->next ;
while (pa!=NULL && pb!=NULL)
{ if (pa->data<pb->data)
{ pc->next=pa ;
pc=pa ; pa=pa->next ; }
/*将 pa 所指的结点合并，pa 指向下一个结点 */
if (pa->data>pb->data)
{ pc->next=pb ;
pc=pb ; pb=pb->next ; }
/* 将 pa 所指的结点合并，pa 指向下一个结点 */
if (pa->data==pb->data)
{ pc->next=pa ; pc=pa ;
pa=pa->next ;
ptr=pb ; pb=pb->next ; free(ptr) ; }
/* 将 pa 所指的结点合并，pb 所指结点删除 */
}
if (pa!=NULL)
pc->next=pa ;
else
pc->next=pb ; /*将剩余的结点链上*/
free(Lb) ;
return(Lc) ;}

算法分析：若 La ，Lb 两个链表的长度分别是 m，n，则链表合并的时间复杂度为 O(m+n) 。
（二）循环链表
对于单链表而言，最后一个结点的指针域是空指针，如果将该链表头指针置入该指针域，
则使得链表头尾结点相连，就构成了单循环链表。
在单循环链表上的操作基本上与非循环链表相同，只是将原来判断指针是否为 NULL
变为是否是头指针而已，没有其它较大的变化。

对于单链表只能从头结点开始遍历整个链表，而对于单循环链表则可以从表中任意结点
开始遍历整个链表，不仅如此，有时对链表常做的操作是在表尾、表头进行，此时可以改变
一下链表的标识方法，不用头指针而用一个指向尾结点的指针 R 来标识，可以使得操作效
率得以提高。
（三）双向链表
单链表的结点中只有一个指向其后继结点的指针域 next，因此若已知某结点的指针 p，
其后继结点的指针则为 p->next ，而找其前驱则只能从该链表的头指针开始，顺着各结点的
next 域进行，也就是说找后继的时间性能是 O（1），找前驱的时间性能是 O(n)，如果也希
望找前驱的时间性能达到 O（1），则只能付出空间的代价：每个结点再加一个指向前驱的指
针域，结点的结构为如图所示，用这种结点组成的链表称为双向链表。

双向链表的结点及其类型定义

typedef struct DuLinkList
{ ElemType data ;
struct DuLinkList *prior , *next ;
}DuLinkList ;

双向链表结构具有对称性，设 p 指向双向链表中的某一结点，则其对称性可用下式描述：
(p->prior)->next=p=(p->next)->prior ;
结点 p 的存储位置存放在其直接前趋结点 p->prior 的直接后继指针域中，同时也存放在
其直接后继结点 p->next 的直接前趋指针域中。
（1）双向链表中结点的插入：

① 插入时仅仅指出直接前驱结点，钩链时必须注意先后次序是： “先右后左” 。

S=(DuLinkList *)malloc(sizeof(DuLinkList));
S->data=e;
S->next=p->next; p->next->prior=S;
p->next=S; S->prior=p;/* 钩链次序非常重要 */
② 插入时同时指出直接前驱结点 p 和直接后继结点 q，钩链时无须注意先后次序。
S=(DuLinkList *)malloc(sizeof(DuLinkList));
S->data=e;
p->next=S; S->next=q;
S->prior=p; q->prior=S;

（2）双向链表中结点的删除：

设要删除的结点为 p ，删除时可以不引入新的辅助指针变量，可以直接先断链，再释放
结点。

p->prior->next=p->next;
p->next->prior=p->prior;
free(p);

注意：与单链表的插入和删除操作不同的是，在双向链表中插入和删除必须同时修改两
个方向上的指针域的指向。
（四）静态链表
有时，也可借用一维数组来描述线性链表，其类型说明如下所示：
// - - - - -线性表的静态单链表存储结构- - - - -

#define MAXSlZE 1 000 //链表的最大长度
typedef struct {
Elemtype data, int cur, }component, SLinkList[MAXSlZE];

这种描述方法便于在不设"指针"类型的高级程序设计语言中使用链表结构。在如上描述
的链表中，数组的一个分量表示一个结点，同时用游标(指示器 cur) 代替指针指示结点在数
组中的相对位置。数组的第零分量可看成头结点，其指针域指示链表的第一个结点。