《2线性表-1.ppt》由会员分享，可在线阅读，更多相关《2线性表-1.ppt（69页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第2 2章章 线性表线性表 2.1 2.1 线性表的类型定义线性表的类型定义2.2 2.2 线性表的顺序表示和实现线性表的顺序表示和实现2.3 2.3 线性表的链式表示和实现线性表的链式表示和实现2.4 2.4 一元多项式的表示及相加一元多项式的表示及相加4 4）除最后一个结点外，集合中的每个数）除最后一个结点外，集合中的每个数据元素均有且只有一个后继。据元素均有且只有一个后继。线性结构的特点：线性结构的特点：在数据元素的非空有限集中在数据元素的非空有限集中1 1）有且仅有一个开始结点；）有且仅有一个开始结点；2 2）有且仅有一个终端结点；）有且仅有一个终端结点；3 3）除第一个结点外，集合
2、中的每个数据元）除第一个结点外，集合中的每个数据元 素均有且只有一个前驱；素均有且只有一个前驱；线性序列线性序列：线性结构中的所有结点按其线性结构中的所有结点按其关系可以排成一个序列，关系可以排成一个序列，记为记为 (a(a1 1,a ai i ,a,ai+1 i+1,a,an n)2.1 2.1 线性表的类型定义线性表的类型定义 其中：其中：D=D=a ai i|a|ai iDD0 0,i=1,2,i=1,2,n,n0 n,n0 R=N ,N=a R=N ,N=|a|ai-1i-1,a ai i D D0 0,i=2,3,i=2,3,nn D D0 0 为某个数据对象为某个数据对象1.1.线
3、性表线性表1 1）线性表是）线性表是n(nn(n 0)0)个数据元素的有限序列。个数据元素的有限序列。2 2）线性表是一种最常用且最简单的数据结构。）线性表是一种最常用且最简单的数据结构。含有含有n n个数据元素的线性表是一个数据结构：个数据元素的线性表是一个数据结构：List=(D,R)List=(D,R)特性：均匀性，有序性（线性序列关系特性：均匀性，有序性（线性序列关系）3）线性表的长度及空表）线性表的长度及空表线性表中数据元素的个数线性表中数据元素的个数n（n0）定义为）定义为线性表的长度线性表的长度当线性表的长度为当线性表的长度为0 时，称为空表。时，称为空表。ai 是第是第i个数据
4、元素，称个数据元素，称i为为ai 在线性表中的在线性表中的位序。位序。抽象数据类型线性表线性表的定义如下：ADT List 数据对象数据对象：D ai|ai ElemSet,i=1,2,.,n,n0 称 n n 为线性表的表长表长;称 n=0n=0 时的线性表为空表空表。数据关系数据关系：R1|ai-1,aiD,i=2,.,n 记为记为 (a(a1 1，a a2 2,.,.，a ai i，.，a an n)基本操作：基本操作：结构初始化操作结构初始化操作结构销毁操作结构销毁操作引用型操作引用型操作加工型操作加工型操作 ADT List InitList(&L)操作结果：操作结果：构造一个空的线
5、性表构造一个空的线性表 L。初始化操作初始化操作 结构销毁操作结构销毁操作DestroyList(&L)初始条件：初始条件：操作结果：操作结果：线性表线性表 L 已存在。已存在。销毁线性表销毁线性表 L。ListEmpty(L)ListLength(L)PriorElem(L,cur_e,&pre_e)NextElem(L,cur_e,&next_e)GetElem(L,i,&e)LocateElem(L,e,compare()ListTraverse(L,visit()引用型操作引用型操作:ListEmpty(L)初始条件：初始条件：操作结果：操作结果：线性表线性表 L 已存在。已存在。若若
6、 L 为空表，则返回为空表，则返回TRUE，否则，否则FALSE。（线性表判空）（线性表判空）ListLength(L)初始条件：初始条件：操作结果：操作结果：线性表线性表 L 已存在。已存在。返回返回 L 中元素个数。中元素个数。（求线性表的长度）（求线性表的长度）GetElem(L,i,&e)初始条件：初始条件：操作结果：操作结果：线性表线性表 L 已存在，已存在，用用 e 返回返回L中第中第 i 个元素的值。个元素的值。（求线性表中某个数据元素）（求线性表中某个数据元素）且且 1iListLength(L)LocateElem(L,e,compare()初始条件：初始条件：操作结果：操作
7、结果：线性表线性表 L 已存在，已存在，e e 为给定值，为给定值，compare()是元素判定函数。是元素判定函数。返回返回 L 中第中第 1 个与个与 e 满足关系满足关系 compare()的元素的的元素的位序位序。若这样的元素不存在，则返回值为若这样的元素不存在，则返回值为0。（定位函数）PriorElem(L,cur_e,&pre_e)初始条件：初始条件：操作结果：操作结果：线性表线性表 L 已存在。已存在。若若 cur_e 是是 L 的元素，则用的元素，则用pre_e 返回它的前驱，否则返回它的前驱，否则操作失败，操作失败，pre_e无定义。无定义。（求数据元素的前驱）（求数据元素
8、的前驱）NextElem(L,cur_e,&next_e)初始条件：初始条件：操作结果：操作结果：线性表线性表 L 已存在。已存在。若若 cur_e 是是 L 的元素，则用的元素，则用next_e 返回它的后继，否则返回它的后继，否则操作失败，操作失败，next_e无定义。无定义。（求数据元素的后继）ListTraverse(L,visit()初始条件：初始条件：操作结果：操作结果：线性表线性表 L 已存在。已存在。Visit()为某个访问函数。为某个访问函数。依次依次对对 L 中中每个元素调用每个元素调用函数函数visit()。一旦。一旦 visit()失失败，则操作失败。败，则操作失败。（
9、遍历线性表）（遍历线性表）加工型操作加工型操作 ClearList(&L)PutElem(&L,i,e)ListInsert(&L,i,e)ListDelete(&L,i,&e)ClearList(&L)初始条件：初始条件：操作结果：操作结果：线性表线性表 L 已存在。已存在。将将 L 重置为空表。重置为空表。（线性表置空）（线性表置空）PutElem(&L,i,e)初始条件：初始条件：操作结果：操作结果：线性表线性表 L 已存在，已存在，L 中第中第 i 个元素赋值个元素赋值 e e。（改变数据元素的值）（改变数据元素的值）且且 1iListLength(L)ListInsert(&L,i,
10、e)初始条件：初始条件：操作结果：操作结果：线性表线性表 L 已存在已存在，在在 L 的第的第 i 个元素之前个元素之前插入插入新的元素新的元素 e，L 的长度增的长度增1。（插入数据元素）（插入数据元素）且且 1iListLength(L)+1ListDelete(&L,i,&e)初始条件：初始条件：操作结果：操作结果：线性表线性表 L 已存在且非空，已存在且非空，删除删除 L 的第的第 i 个元素，并用个元素，并用 e 返回其值，返回其值，L 的长度减的长度减1。（删除数据元素）1iListLength(L)利用上述定义的线性表类型线性表类型 可以实现其它更复杂的操作例例 2-2例例 2-
11、1 假设:有两个集合集合 A 和和 B 分别用两个线性表线性表 LA 和和 LB 表示，即：线性表中的数据元素即为集合中的成员。现要求一个新的集合现要求一个新的集合A=AB。例例 2-1 算法算法2.1 P20 2.1 P20 要求对线性表作如下操作：扩大线性表 LA，将存在于线性表存在于线性表LB 中中而不存在于线性表不存在于线性表 LA 中中的数据元素插入到线性表插入到线性表 LA 中中去。上述问题可演绎为：1从线性表 LB 中依次察看每个数据元素;2依值在线性表 LA 中进行查访;3若不存在，则插入之。GetElem(LB,i)e LocateElem(LA,e,equal()ListI
12、nsert(LA,n+1,e)(n 表示线性表表示线性表 LA 当前长度当前长度)操作步骤：操作步骤：GetElem(Lb,i,e);/取取Lb中第中第i个数据元素赋给个数据元素赋给e if(!LocateElem(La,e,equal()ListInsert(La,+La_len,e);/La中不存在和中不存在和 e 相同的数据元素，则插入之相同的数据元素，则插入之 La_len=ListLength(La);/求线性表的长度求线性表的长度 Lb_len=ListLength(Lb);for(i=1;i=Lb_len;i+)/for/unionvoid union(List&La,List
13、Lb)则则 归并两个归并两个“其数据元素按值非递减有序其数据元素按值非递减有序排列排列”的有序表的有序表 LA 和和 LB，求得有序表，求得有序表 LC 也具有同样特性。也具有同样特性。设 La=(a1,ai,an),Lb=(b1,bj,bm)Lc=(c1,ck,cm+n)且已由(a1,ai-1)和(b1,bj-1)归并得(c1,ck-1)例例 2-2 算法算法2.2 P21 2.2 P21 k=1,2,m+n1 1初始化初始化 LC LC 为空表；为空表；基本操作：2 2分别从分别从 LALA和和LBLB中取得当前元素中取得当前元素 aiai 和和 bjbj；3 3若若 aibjaibj，则
14、将，则将 aiai 插入到插入到 LC LC 中，否则将中，否则将 bjbj 插入到插入到 LC LC 中；中；4 4重复重复 2 2 和和 3 3 两步，直至两步，直至 LA LA 或或 LB LB 中元素中元素 被取完为止；被取完为止；5 5将将 LA LA 表或表或 LB LB 表中剩余元素复制插入到表中剩余元素复制插入到 LC LC 表中。表中。/La 和 Lb 均非空，i=j=1,k=0 GetElem(La,i,ai);GetElem(Lb,j,bj);if(ai=bj)/将 ai 插入到 Lc 中 ListInsert(Lc,+k,ai);+i;else /将 bj 插入到 Lc
15、 中 ListInsert(Lc,+k,bj);+j;void MergeList(List La,List Lb,List&Lc)/本算法将非递减的有序表 La 和 Lb 归并为 Lcwhile(i=La_len)&(j=Lb_len)/La 和和 Lb 均不空均不空 GetElem(La,i,ai);GetElem(Lb,j,bj);if (ai=bj)ListInsert(Lc,+k,ai);+i;else ListInsert(Lc,+k,bj);+j;/whileInitList(Lc);/构造空的线性表 Lci=j=1;k=0;La_len=ListLength(La);Lb_le
16、n=ListLength(Lb);while(i=La_len)/当La不空时 GetElem(La,i+,ai);ListInsert(Lc,+k,ai);/插入插入 La 表中剩余元素表中剩余元素 while(j=Lb_len)/当Lb不空时 GetElem(Lb,j+,bj);ListInsert(Lc,+k,bj);/插入插入 Lb 表中剩余元素表中剩余元素/MergeList2.2 2.2 线性表的顺序表示和实现线性表的顺序表示和实现 1.1.顺序表顺序表线性表的顺序存储结构线性表的顺序存储结构 (顺序存储的线性表顺序存储的线性表)1 1）在计算机内存中用一组地址连续的存在计算机内存
17、中用一组地址连续的存储单元依次存储线性表中的各个数据元储单元依次存储线性表中的各个数据元素。素。2 2）假设线性表的每个元素需占用假设线性表的每个元素需占用L L个存个存储单元，并以所占的第一个单元的存储储单元，并以所占的第一个单元的存储地址作为数据元素的起始存储位置，则地址作为数据元素的起始存储位置，则线性表中第线性表中第i+1i+1个数据元素的存储位置个数据元素的存储位置LocLoc(a(ai+1i+1)和第和第i i个数据元素的存储位置个数据元素的存储位置Loc(aLoc(ai i)之间满足下列关系：之间满足下列关系：Loc(aLoc(ai+1i+1)=)=Loc(aLoc(ai i)+
18、L)+L 一般来说，线性表的第一般来说，线性表的第i i个元素个元素a ai i的存的存储位置为：储位置为：Loc(aLoc(ai i)=Loc(a)=Loc(a1 1)+(i-1)*L)+(i-1)*L 其中其中Loc(aLoc(a1 1)是线性表的第一个数据元是线性表的第一个数据元素素a a1 1的存储位置，通常称作线性表的的存储位置，通常称作线性表的起起始位置始位置或或基地址基地址。用一组地址连续地址连续的存储单元 依次存放依次存放线性表中的数据元素 a1 a2 ai-1 ai an线性表的线性表的起始地址起始地址，称作线性表的基地址基地址图图2-1 线性表顺序存储结构示意图线性表顺序存
19、储结构示意图用用“物理位置物理位置”相邻来表示线性表中数据相邻来表示线性表中数据元素之间的逻辑关系。有序对元素之间的逻辑关系。有序对 即：即：LOC(ai)=LOC(ai-1)+L 一个数据元素所占存储量一个数据元素所占存储量 根据线性表的顺序存储结构的特点，只要确根据线性表的顺序存储结构的特点，只要确定了存储线性表的起始位置，线性表中任一定了存储线性表的起始位置，线性表中任一数据元素都可随机存取，所以，线性表的顺数据元素都可随机存取，所以，线性表的顺序存储结构是一种序存储结构是一种随机存取随机存取的存储结构。的存储结构。所有数据元素的存储位置均取决于所有数据元素的存储位置均取决于 第一个数据
20、元素的存储位置第一个数据元素的存储位置 LOC(ai)=LOC(a1)+(i-1)L 基地址基地址#define LIST_INIT_SIZE 100 /存储空间的初始分配量存储空间的初始分配量#define LISTINCREMENT 10 /存储空间的分配增量存储空间的分配增量typedef struct ElemType *elem;/存储空间基址存储空间基址 int length;/当前长度当前长度 int listsize;/当前分配的当前分配的存储容存储容量量 /(以以sizeof(ElemType)为单位为单位)SqList;SqList L;/定义定义L变量存放顺序表变量存放顺
21、序表/-线性表的动态分配顺序存储结构线性表的动态分配顺序存储结构-说明：说明：elem数组指针指向线性表的基地址；数组指针指向线性表的基地址；length指示线性表的当前长度；指示线性表的当前长度；listsize指示顺序表当前分配的存储空指示顺序表当前分配的存储空间大小。当空间不足时，再分配的存储间大小。当空间不足时，再分配的存储空间增量为空间增量为 LISTINCREMENT*sizeof(ElemType)例如：顺序表例如：顺序表23 75 41 38 54 62 17L.elemL.length=7L.listsize几个基本操作几个基本操作 初始化初始化 算法算法 2.3 P232.
22、3 P23Status InitList_ Sq(SqList&L)/构造一个空的线性表构造一个空的线性表L L L.elem=(ElemType*)malloc(LIST_INIT_SIZE *sizeof(ElemType);if(!L.elem)exit(Overflow);/存储分配失败存储分配失败 L.length=0;/空表长度为空表长度为0 0 L.listsize=LIST_INIT_SIZE;/初始存储容量初始存储容量 return OK;/InitList_ Sq算法时间复杂度时间复杂度：O(1)顺序表顺序表操作操作 ListInsert_Sq(&L,i,e)的实现：首先分
23、析首先分析:插入元素时，线性表的逻辑结构逻辑结构发生什么变化发生什么变化？(a1,ai-1,ai,an)改变为a1 a2 ai-1 ai ana1 a2 ai-1 ai ean,表的长度增加(a1,ai-1,e,ai,an)插入运算插入运算 算法算法 2.4 P242.4 P24Status Status ListInsert_sq(SqListListInsert_sq(SqList&L,intL,int i,ElemTypei,ElemType e)e)if(iL.length+1)return if(iL.length+1)return ERRORERROR;if(if(L.length
24、L.length=L.listsizeL.listsize)newbasenewbase=(=(ElemTypeElemType*)*)realloc(L.elemrealloc(L.elem,(,(L.listsizeL.listsize+LISTINCREMENTLISTINCREMENT)*)*sizeof(ElemTypesizeof(ElemType););if(!if(!newbasenewbase)exit(OVERFLOWexit(OVERFLOW););/存储分配失败存储分配失败 L.elemL.elem=newbasenewbase;L.listsizeL.listsize
25、+=LISTINCREMENT;+=LISTINCREMENT;说明说明:函数函数reallocrealloc的格式及功能的格式及功能格式：格式：void*void*realloc(voidrealloc(void*p,unsignedp,unsigned size)size)功能：功能：将将p p所指向的已分配内存区域的大所指向的已分配内存区域的大 小改为小改为sizesize。sizesize可以比原来分配的空间大或小。可以比原来分配的空间大或小。注意注意:需将第需将第n(n(即即L.lengthL.length)至第至第i i个元素向后个元素向后移动一个位置。移动一个位置。C C语言中数
26、组下标从语言中数组下标从0 0开始，开始，则表中第则表中第i i个数据元素是个数据元素是L.elemi-1L.elemi-1。O(ListLength(L)插入算法（续）插入算法（续）q=&(L.elemi-1);q=&(L.elemi-1);/q指向第指向第i个元素个元素 for(p=&(L.elemL.length-1);p=for(p=&(L.elemL.length-1);p=q;-pq;-p)*(p+1)=*p;*(p+1)=*p;/第第i个及其后元素后移个及其后元素后移 *q=e;q=e;/插入插入 +L.lengthL.length;/表长增表长增1 1 return OK;re
27、turn OK;/ListInsert_sqListInsert_sq算法时间复杂度算法时间复杂度为为:即即:O(n ):O(n )21 18 30 75 42 56 8721 18 30 75例如：ListInsert_Sq(L,5,66)L.length-10pppq87564266q=&(L.elemi-1);/q 指示插入位置for(p=&(L.elemL.length-1);p=q;-p)*(p+1)=*p;p顺序表的删除操作顺序表的删除操作 算法算法 2.5 P252.5 P25 ListDelete_Sq(&L,i,&e)的实现：首先分析：删除元素时，删除元素时，线性表的逻辑结构
28、发生什么变化？线性表的逻辑结构发生什么变化？(a1,ai-1,ai,ai+1,an)改变为ai+1 an,表的长度减少a1 a2 ai-1 ai ai+1 ana1 a2 ai-1(a1,ai-1,ai+1,an)Status ListDelete_Sq (SqList&L,int i,ElemType&e)/ListDelete_Sqfor(+p;p=q;+p)*(p-1)=*p;/被删除元素之后的元素左移被删除元素之后的元素左移-L.length;/表长减表长减1 1return OK;算法时间复杂度算法时间复杂度为为:O(ListLength(L)p=&(L.elemi-1);/p 为被
29、删除元素的位置为被删除元素的位置e=*p;/被删除元素的值赋给被删除元素的值赋给 eq=L.elem+L.length-1;/表尾元素的位置表尾元素的位置if(i L.length)return ERROR;/删除位置不合法删除位置不合法元素左移元素左移 O(n )21 18 30 75 42 56 8721 18 30 75L.length-10pppq8756p=&(L.elemi-1);q=L.elem+L.length-1;for(+p;p=q;+p)*(p-1)=*p;例如：ListDelete_Sq(L,5,e)p顺序表的插入和删除顺序表的插入和删除算法时间分析算法时间分析考虑移动
30、元素的平均情况考虑移动元素的平均情况:假设在第假设在第 i 个元素之前插入的概率为个元素之前插入的概率为 ，则在长度为则在长度为n 的线性表中的线性表中插入一个元素所需插入一个元素所需移动元素次数的期望值移动元素次数的期望值为：为：若假定在线性表中任何一个位置上进行若假定在线性表中任何一个位置上进行插入插入的概率的概率都是都是相等相等的，则的，则移动元素的期望值移动元素的期望值为为：考虑移动元素的平均情况考虑移动元素的平均情况:假设删除第假设删除第 i 个元素的概率为个元素的概率为 ,则在长度为则在长度为n 的线性表中的线性表中删除一个元素删除一个元素所需所需移动元素次数的期望值移动元素次数的
31、期望值为：为：若假定在线性表中任何一个位置上进行删除若假定在线性表中任何一个位置上进行删除的的概率概率都是都是相等相等的，则的，则移动元素的期望值移动元素的期望值为为：结论结论:在顺序存储结构的线性表中在顺序存储结构的线性表中插入或删除一个元素，平均移动插入或删除一个元素，平均移动表中一半元素。表中一半元素。若表长为若表长为n，则算法，则算法ListInsert_Sq和和ListDelete_Sq的的时间复杂度为时间复杂度为O(n)顺序表的查找顺序表的查找算法算法 2.6 P26 2.6 P26 例如例如：23 75 41 38 54 62 17L.elemL.length=7L.listsi
32、zee=38pppppi 1 2 3 4 1 850p可见，基本操作是，将顺序表中的元素逐个和给定值 e 相比较。int LocateElem_Sq(SqList L,ElemType e,Status(*compare)(ElemType,ElemType)/在顺序表中查在顺序表中查找找第一个满足判定条件的数据元素，第一个满足判定条件的数据元素，/若存在，则返回它的位序，否则返回若存在，则返回它的位序，否则返回 0 0/LocateElem_Sq O(ListLength(L)if(i=L.length)return i;else return 0;算法的算法的时间复杂度时间复杂度为：为：i
33、=1;/i i 的初值为第的初值为第 1 1 元素的位序元素的位序p=L.elem;/p p 的初值为第的初值为第 1 1 元素的存储位置元素的存储位置while(i=L.length&!(*compare)(*p+,e)+i;(*compare)(*p+,e)/找到满足条件的元素/没有找到满足条件的元素 O(n )顺序表的合并运算顺序表的合并运算 算法算法 2.7 P262.7 P26void MergeList_Sq(SqList La,SqList Lb,SqList&Lc)pa=La.elem;pb=Lb.elem;Lc.listsize=Lc.length=La.length+Lb.
34、length;pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType);if(!Lc.elem)exit(OVERFLOW);/存储分配失败存储分配失败 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+;/插入插入La的剩余的剩余 while(pb=pb_last)*pc+=*pb+;/
35、插入插入Lb的剩余的剩余/MergeList_Sq*建立算法建立算法:#define LIST_INIT_SIZE 100Status CreateList_Sq(SqList&L,int n)int i;L.elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int);if(!L.elem)exit(OVERFLOW);/分配失败分配失败 L.length=n;L.Listsize=LIST_INIT_SIZE;for(i=0;in;i+)scanf(%d,&L.elemi);for(i=0;i=La.listsize)return OVERFLOW;while(
36、i La.length&La.elemi=i;j-)La.elemj+1=La.elemj;/后移后移La.elemi=x;/插入插入La.length+;return OK;/OrderInsert_Sq递减插入算法递减插入算法:Status DeOrderInsert_Sq(SqList&La,ElemType x)if(La.length=La.listsize)return OVERFLOW;i=La.length-1;/i i 为最后一个元素下标为最后一个元素下标while(i=0&La.elemi I;j-)La.elemj+1=La.elem j ;/后移后移La.elemi+1
37、=x;/插入插入La.length+;return OK;/DeOrderInsert_Sq4.4.顺序表的分析顺序表的分析1 1）优点）优点顺序表的结构简单顺序表的结构简单顺序表的存储效率高，是紧凑结构顺序表的存储效率高，是紧凑结构顺序表是一个随机存储结构（直接存取结构）顺序表是一个随机存储结构（直接存取结构）2 2）缺点）缺点在顺序表中进行插入和删除操作时，需要移动在顺序表中进行插入和删除操作时，需要移动数据元素，算法效率较低。数据元素，算法效率较低。对长度变化较大的线性表，或者要预先分配较对长度变化较大的线性表，或者要预先分配较大空间或者要经常扩充线性表，给操作带来不大空间或者要经常扩充
38、线性表，给操作带来不方便。方便。原因：数组的静态特性造成原因：数组的静态特性造成作业作业2.12.1 编写程序，建立并显示一个有编写程序，建立并显示一个有1010 个数据元素的顺序线性表。个数据元素的顺序线性表。2.2 2.2 实现顺序线性表的插入、删除实现顺序线性表的插入、删除 算法。算法。顺序表之整体概念：顺序表之整体概念：elem01length-1 listsizelength数组下标 内存状态变量操作算法listsize-1初始化操作插入操作删除操作查找操作排序操作.空闲表区 elem 顺序表之整体概念顺序表之整体概念：顺序表有下列缺点：（1）插入、删除操作时需要移动大量元素，效率较低；（2）最大表长难以估计，太大了浪费空间，太小了容易溢出。因此，在插入和删除操作是经常性操作的应用场合选用顺序存储结构不太合适，此时可以选用链式存储结构，数据元素之间的逻辑关系由结点中的指针来指示。