《线性表的链式表示和实现》由会员分享，可在线阅读，更多相关《线性表的链式表示和实现（37页珍藏版）》请在金锄头文库上搜索。
1、第第2 2章章 线性表线性表2.1 2.1 线性表的逻辑结构线性表的逻辑结构 2.2 2.2 线性表的顺序表示和实现线性表的顺序表示和实现2.3 2.3 线性表的链式表示和实现线性表的链式表示和实现2.4 2.4 一元多项式的表示和相加一元多项式的表示和相加12.3 2.3 线性表的链式表示和实现线性表的链式表示和实现2.3.1 2.3.1 链表的表示链表的表示2.3.2 2.3.2 链表的实现链表的实现2.3.3 2.3.3 一个带头结点的单链表类型一个带头结点的单链表类型2.3.4 2.3.4 其它形式的链表其它形式的链表2(1)链式存储结构特点：链式存储结构特点：其其结结点点在在存存储储
2、器器中中的的位位置置是是随随意意的的，即即逻逻辑辑上上相邻的数据元素在物理上不一定相邻。相邻的数据元素在物理上不一定相邻。如何实现？ 通过指针指针指针指针来实现！让每个存储结点都包含两部分：让每个存储结点都包含两部分：数据域数据域和和指针域指针域指针指针数据数据指针指针数据数据数据数据指针指针或或样式：样式：数据域：数据域：存储存储元素数值数据元素数值数据指针域：指针域：存储直接后继或存储直接后继或者直接前驱的存储位置者直接前驱的存储位置设计思想：牺牲空间效率换取时间效率设计思想：牺牲空间效率换取时间效率设计思想：牺牲空间效率换取时间效率设计思想：牺牲空间效率换取时间效率2.3.1 2.3.1
3、 链表的表示链表的表示3链表存放示意图如下： a1heada2/an讨论讨论1 1：每个存储结点都包含两部分：数据域和每个存储结点都包含两部分：数据域和讨论讨论2 2：在单链表中，除了首元结点外，任一结点的在单链表中，除了首元结点外，任一结点的存储位置由存储位置由 指示。指示。 其直接前驱结点的链域的值其直接前驱结点的链域的值(2) (2) 与链式存储有关的术语与链式存储有关的术语：1 1）结点）结点：数据元素的存储映像。由数据域和指针域两数据元素的存储映像。由数据域和指针域两部分组成；部分组成；2 2）链表）链表： n n 个结点由个结点由指针链指针链组成一个链表。它是线性组成一个链表。它是
4、线性表的链式存储映像表的链式存储映像，称为线性表的链式存储结构称为线性表的链式存储结构。只包含一个指针域的称为单链表或线性链表只包含一个指针域的称为单链表或线性链表指针域指针域43 3）头指针、头结点和首元结点的区别）头指针、头结点和首元结点的区别头指针头指针头结点头结点首元结点首元结点a1heada2infoan首元结点首元结点是指链表中存储线性表第一个数据元素是指链表中存储线性表第一个数据元素a a1 1的的结点。结点。头结点头结点是在链表的首元结点之前是在链表的首元结点之前附设附设的一个结点；数的一个结点；数据域内只放空表标志和表长等信息，它不计入据域内只放空表标志和表长等信息，它不计入
5、表长度。表长度。头指针头指针是指向链表中第一个结点（或为头结点、或为是指向链表中第一个结点（或为头结点、或为首元结点）的指针；首元结点）的指针；示意图如下：示意图如下：5讨论讨论2 2： 在链表中设置在链表中设置头结点头结点有什么好处？有什么好处？讨论讨论1 1： 如何表示如何表示空表空表？因为任何元素结点都有前驱结点，而在做插入和删因为任何元素结点都有前驱结点，而在做插入和删除操作时，都需修改其前驱结点的指针域，因此对首元除操作时，都需修改其前驱结点的指针域，因此对首元结点可以统一处理。即简化插入和删除操作；结点可以统一处理。即简化插入和删除操作；表头指针是指向头结点的非空指针，因此空表和非
6、表头指针是指向头结点的非空指针，因此空表和非空表的处理一样。空表的处理一样。无头结点时，当无头结点时，当头指针头指针的值为的值为空空时表示空表；时表示空表；头指针头指针无头结点无头结点头指针头指针头结点头结点有头结点有头结点有头结点时，当有头结点时，当头结点头结点的的指针域为空指针域为空时表示空表。时表示空表。头结点不计入头结点不计入头结点不计入头结点不计入链表长度！链表长度！链表长度！链表长度！6一个线性表的逻辑结构为：一个线性表的逻辑结构为：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANGZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存
7、），其存储结构用储结构用单链表单链表表示如下，表示如下，请问其请问其头指针的值头指针的值是多少是多少？存储地址存储地址数据域数据域指针域指针域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25答：答：头指针头指针是指向链表是指向链表中中第一个第一个结点的指针，结点的指针，因此关键是要寻找因此关键是要寻找第一第一个结点的地址。个结点的地址。7ZHAOH31称：头指针称：头指针H的值是的值是31（3 3）举例）举例例例1：7 现现有有一一个个具具有有五五个个元元素素的的线线性性表表L=23L=23，1717，4747，0505，31
8、31，若若它它以以链链接接方方式式存存储储在在下下列列100100119119号号地地址址空空间间中中，每每个个结结点点由由数数据据（占占2 2个个字字节节）和和指指针针（占（占2 2个字节个字节）组成，如下图所示。）组成，如下图所示。其其中中指指针针X X，Y Y，Z Z的的值值分分别别为为多多少少？该该线线性性表表的的首首结结点起始地址为多少？末结点的起始地址为多少？点起始地址为多少？末结点的起始地址为多少？Z Z47474747Y Y3131V V23232323X X1717U U05051001001001001191191191191041041041041081081081081
9、16116116116112112112112116116116116NULL(0)NULL(0)NULL(0)NULL(0)100100100100108108108108112112112112答：答：X=X= Y= Y= Z= Z= , , 首址首址= = 末址末址= = 。例例2 2：8讨论讨论: : 链表的数据元素有链表的数据元素有两个域两个域，不再是简单数据，不再是简单数据类型，编程时该如何表示？类型，编程时该如何表示？因每个结点至少有两个分量，且数据类型通常不因每个结点至少有两个分量，且数据类型通常不一致，所以要采用一致，所以要采用结构结构数据类型。数据类型。答：答：设每个结点用
10、变量设每个结点用变量nodenodenodenode表示，表示，其指针用其指针用p p p p表示，两个分量分表示，两个分量分别用别用datadatadatadata和和* * * *nextnextnextnext表示，这两表示，这两个分量如何赋值？个分量如何赋值？p*next*nextdatadatanodenode方式方式1： 直接表示为直接表示为 node.dataaa；node.next=q;q;方式方式2：p指向结点首地址指向结点首地址 p-data=aa; p-next=q q; 方式方式3：p指向结点首地址指向结点首地址 (*p).data=aa； (*p).nextq;q;9
11、单链表的抽象数据类型描述如下单链表的抽象数据类型描述如下（参见教材（参见教材P28P28）：typedef struct LNode ElemType data; /数据域 struct LNode *next; /指针域LNode, *LinkList; / *LinkList为Lnode类型的指针Q1Q1：第一行的第一行的LNodeLNode 与最后一行的与最后一行的LNodeLNode是不是一回事？是不是一回事？A1A1：不是。前者不是。前者LNodeLNode是结构名，后者是结构名，后者LNodeLNode是对整个是对整个structstruct类型的一种类型的一种“缩写缩写”，是一种
12、，是一种“新定义名新定义名”，它只，它只是对现有类型名的补充，而不是取代。是对现有类型名的补充，而不是取代。请注意：请注意：typedeftypedef不可能不可能创造任何新的数据类型，创造任何新的数据类型，而仅仅是在原有的数据类而仅仅是在原有的数据类型中命名一个新名字，其型中命名一个新名字，其目的是使你的程序更易阅目的是使你的程序更易阅读和移植。读和移植。10Q2Q2： 那为何两处要同名那为何两处要同名( (LNodeLNode和和LNodeLNode）？太不严谨）？太不严谨了吧？了吧？A2A2：同名是为了表述起来方便。因为描述的对象相同，同名是为了表述起来方便。因为描述的对象相同，方便阅读
13、和理解。方便阅读和理解。Q3Q3：结构体中间的那个：结构体中间的那个structstruct LNodeLNode是何意？是何意？A3A3：在：在“缩写缩写” LNodeLNode还没出现之前，只能用原始的还没出现之前，只能用原始的struct LNodestruct LNode来进行变量说明。此处说明了指针分量来进行变量说明。此处说明了指针分量的数据类型是的数据类型是struct LNodestruct LNode。返返 回回112.3.2 2.3.2 链表的实现链表的实现（1 1） 单链表的存取单链表的存取（2 2） 单链表的插入单链表的插入（3 3） 单链表的删除单链表的删除（4 4）
14、单链表的建立单链表的建立12（1 1） 单链表的存取单链表的存取思路：思路：要存取第要存取第i i个数据元素，必须从头指针起一直找到个数据元素，必须从头指针起一直找到该结点的指针该结点的指针p p，然后才能执行，然后才能执行 p-data=new_value p-data=new_value 。修改第修改第i i个数据元素的操作函数可写为：个数据元素的操作函数可写为：Status GetElem_L(LinkList L, int i, ElemType e)p=L-next; j=1; /带头结点的链表while(p&jnext; +j;if ( !p | | ji ) return ERR
15、OR; /i不合法 p-data =e; /若是读取则为：e=p-data; return OK;/ GetElem_L缺点：缺点：想寻找单链表中第想寻找单链表中第i i个元素，只能从头指针开个元素，只能从头指针开始逐一查询（始逐一查询（顺藤摸瓜顺藤摸瓜），无法随机存取），无法随机存取 。13在链表中第在链表中第i i个位置前插入一个元素个位置前插入一个元素x 的示意图如下：的示意图如下：X Xsai-1aip链表插入的核心语句：链表插入的核心语句：Step 1Step 1：s-next=p-next;s-next=p-next;p-nexts-next思考：思考：思考：思考：Step1Ste
16、p1Step1Step1和和和和2 2 2 2能互换么？能互换么？能互换么？能互换么？X 结点的生成方式：结点的生成方式：s=(Lnode*)malloc(m);s-data= x ;s-next= ?aiai-1p插插插插 入入入入 X X （2 2） 单链表的插入单链表的插入Step2: p-next=s;Step2: p-next=s;14 Status ListInsert_L(LinkList L, int i, ElemType e) / LinstInsert_L算法的时间复杂度为算法的时间复杂度为: :O(ListLength(L)p = L; j = 0;while (p &
17、 j next; +j; / 寻找第 i-1 个结点if (!p | j i-1) return ERROR; /i不合法 s = (LinkList)malloc(sizeof(LNode) s-data = e; s-next = p-next; p-next = s; / / 插入插入return OK;15在链表中删除某元素在链表中删除某元素ai的示意图如下：的示意图如下：ai+1 ai-1 aip删除动作的核心语句（要借助辅助指针变量删除动作的核心语句（要借助辅助指针变量q q）：）：q = p-next; /首先保存首先保存a ai i的指针，靠它才能找到的指针，靠它才能找到a a
18、i+1i+1 p-next(p-next) - nextq（3 3） 单链表的删除单链表的删除P-next=q-next；/将将a ai-1i-1与与a ai+1i+1两结点相连两结点相连, ,淘汰淘汰a ai i结点结点free(q); 16 Status ListDelete_L(LinkList L, int i, ElemType &e) / 删除以 L 为头指针(带头结点)的单链表中第 i 个结点 / ListDelete_L算法的时间复杂度为算法的时间复杂度为: :O(ListLength(L)p = L; j = 0;while (p-next & j next; +j; / 寻
19、找第 i 个结点，并令 p 指向其前趋if (!(p-next) | j i-1) return ERROR; / 删除位置不合理q = p-next; p-next = q-next; /删除并释放结点 e = q-data; free(q);return OK;17空间效率分析空间效率分析链表中每个结点都要增加一个指针空间，相当于总共链表中每个结点都要增加一个指针空间，相当于总共增加了增加了n n 个整型变量，空间复杂度为个整型变量，空间复杂度为 O(n)O(n)。在在n n个结点的单链表中要删除已知结点个结点的单链表中要删除已知结点* *P P，需找到它，需找到它的的 ，其时间复杂度，其
20、时间复杂度 。 前驱结点的地址前驱结点的地址/ /指针指针O(nO(n) )练习：练习：18操作步骤：操作步骤：一、建立一个一、建立一个“空表空表”；二、输入数据元素二、输入数据元素a an n， 建立结点并插入；建立结点并插入；三、输入数据元素三、输入数据元素a an-1n-1， 建立结点并插入表头；建立结点并插入表头；ananan-1四、依次类推，直至输入四、依次类推，直至输入a a1 1为止为止。（4 4）单链表的建立）单链表的建立例如：逆位序输入例如：逆位序输入 n n 个数据元素的值，建立带头结个数据元素的值，建立带头结点的单链表。点的单链表。链表是一个动态的结构，它不需要预先分配空
21、间，因链表是一个动态的结构，它不需要预先分配空间，因此生成链表的过程是一个结点此生成链表的过程是一个结点“逐个插入逐个插入” ” 的过程。的过程。19void CreateList_L(LinkList &L, int n) / 逆序输入 n 个数据元素，建立带头结点的单链表 / CreateList_L算法的时间复杂度算法的时间复杂度为:O(Listlength(L)L = (LinkList) malloc (sizeof (LNode);L-next = NULL; / 先建立一个带头结点的单链表for (i = n; i 0; -i) p = (LinkList) malloc (si
22、zeof (LNode); scanf(&p-data); / 输入元素值 p-next = L-next; L-next = p; / 插入20算法要求：算法要求：已知：已知：线性表线性表 A A和和B B，分别由单链表，分别由单链表 LaLa和和Lb Lb 存储，其中存储，其中数据元素按值非递减有序排列（即已经有序）；数据元素按值非递减有序排列（即已经有序）；要求：要求：将将A A和和B B归并为一个新的线性表归并为一个新的线性表C , CC , C的数据元素仍的数据元素仍按值非递减排列。设线性表按值非递减排列。设线性表C C由单链表由单链表 Lc Lc 存储。存储。假设：假设：A=A=（
23、3 3，5 5，8 8，1111），），B=B=（2 2，6 6，8 8，9 9，1111）预测：预测：合并后的合并后的C =C =（2, 3, 5, 6, 8, 8, 9, 112, 3, 5, 6, 8, 8, 9, 11，1111）例：两个链表的归并（教材例：两个链表的归并（教材P31P31例）例）算法设计：算法设计：算法主要包括搜索、比较、插入三个操作：算法主要包括搜索、比较、插入三个操作：搜索：搜索：需要设立三个指针来指向需要设立三个指针来指向La La 、LbLb和和LcLc链表；链表；21La3 5 8 11 Lb2 6 8 119 PaPbPaPbPaPa、PbPb用于搜索用于
24、搜索LaLa和和LbLb， PcPc指向新链表当前结点。指向新链表当前结点。归并过程示意如下：归并过程示意如下：Lc=LaPbPaPaPb比较：比较：比较比较LaLa和和LbLb表中结点数据的大小；表中结点数据的大小；插入：插入：将将LaLa和和LbLb表中数据较小的结点插入新链表表中数据较小的结点插入新链表Lc Lc 。请注意链表的特点，仅改变指针便可实现请注意链表的特点，仅改变指针便可实现数据的移动数据的移动, ,即即“数据不动，指针动数据不动，指针动”22 void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc)/已知单链线性表La
25、和Lb的元素按值非递减排列。归并为Lc后也按值非递减排列。 free(Lb); /释放Lb的头结点 /MergeList_L pc-next = pa ? ? ? ? pa: pb ; /插入非空表的剩余段 while(pa&pb) /将pa 、pb结点按大小依次插入Lc中 if (pa-datadata) pc-next=pa; pc=pa; pa=pa-next; else pc-next=pb; pc=pb; pb=pb-next pa=LaLa-next; pb=LbLb-next; Lc=pc=La； /有头结点注：注：注：注：LcLcLcLc用的是用的是用的是用的是LaLaLaLa
26、的头指针的头指针的头指针的头指针思考：思考：重复的数据元素不需要插入，怎么修改？重复的数据元素不需要插入，怎么修改？23用上述定义的单链表实现线性表的操作时，存在的用上述定义的单链表实现线性表的操作时，存在的问题问题：改进链表的设置：改进链表的设置：1 1单链表的表长是一个隐含的值；单链表的表长是一个隐含的值； 1. 1. 增加增加“表长表长”、“表尾指针表尾指针” 和和 “当前位置的指当前位置的指针针” 三个数据域；三个数据域； 2. 2. 将基本操作中的将基本操作中的“位序位序 i i ”改变为改变为“指针指针 p p ”。2 2在单链表的最后一个元素之后插入元素时，需遍历在单链表的最后一
27、个元素之后插入元素时，需遍历整个链表；整个链表；3 3在链表中，元素的在链表中，元素的“位序位序”概念淡化，结点的概念淡化，结点的“位位置置”概念加强。概念加强。返返 回回24typedef struct LNode /结点类型 Elemtype data; struct LNode *next; *Link, *Positiontypedef struct /链表类型 Link head, tail; /分别指向链表头尾结点 int len; /链表中元素个数（长度） Linklist;2.3.3 2.3.3 一个带头结点的线性链表类型定义如下：一个带头结点的线性链表类型定义如下：（用类（用
28、类C C语言，见语言，见P37P37）：）：结点的结点的结构结构表结构表结构基本操作（略）基本操作（略）返返 回回25单链表中查找只能从前往后，而不能从后往前查。为了单链表中查找只能从前往后，而不能从后往前查。为了查找方便，提高查找速度，可以在结点上增加一个指针查找方便，提高查找速度，可以在结点上增加一个指针域，用来存结点的直接前驱，这样的链表称为域，用来存结点的直接前驱，这样的链表称为双向链表双向链表。其其结点的结构结点的结构为：为：priordatanexttypedef struct DuLNode ElemType data; /数据域 struct DuLNode *prior; /
29、前驱指针域 struct DuLNode *next; /后继指针域 DuLNode , *DuLinkList ; 双向链表类型的定义如下：双向链表类型的定义如下：2.3.4 2.3.4 其它形式的链表其它形式的链表 1. 1. 双向链表双向链表26 最后一个结点的指针域的指针又指回第一个结点的最后一个结点的指针域的指针又指回第一个结点的链表。从表中任一结点出发均可找到表中其它结点链表。从表中任一结点出发均可找到表中其它结点 a1 a2 . an 2. 2. 循环链表循环链表 和单链表的差别仅在于，判别链表中最后一个结和单链表的差别仅在于，判别链表中最后一个结点的条件不再是点的条件不再是“后
30、继是否为空后继是否为空”，而是，而是“后继是后继是否为头结点否为头结点”即即p-next?=headhead273.3.双向循环链表双向循环链表空表空表非空表非空表 a1 a2 . anhead-prior=head-next=headhead28插入操作：插入操作：设设p p已指向第已指向第 i 元素，请在第元素，请在第 i 元素元素前前插入插入元素元素x ai-1的后继从的后继从 ai ( ( 指针是指针是p)变为变为 x（指针是指针是s) : s-next = p ; p-prior-next = s ; ai 的前驱从的前驱从 ai-1 ( 指针是指针是p-prior)变为变为 x (
31、 指针是指针是s); s-prior = p -prior ; p-prior = s ; 注意：要注意：要修改双向修改双向指针指针！x sai-1 ai p指针域的变化指针域的变化：29指针域的变化：指针域的变化： ai-1的后继由的后继由 ai 变为变为 ai+1( (指针指针 p -next );); p -prior-next = p-next ; ai+1 的前驱由的前驱由 ai 变为变为ai-1 (指针指针 p - prior ); p-next-prior = p -prior ; ai-1 ai+1 ai p删除操作：删除操作：设设p指向第指向第i个元素个元素, ,删除第删除第
32、i个元素个元素注意：要注意：要修改双向修改双向指针！指针！30动态链表样式：动态链表样式：静态链表样式：静态链表样式：指针指针数据指针指针数据指针指针数据指示指示数据指示指示数据指示指示数据指示指示数据指示指示数据数组中每个元数组中每个元素都至少有两素都至少有两个分量，属于个分量，属于结构型数组结构型数组。常用于无指针常用于无指针类型的高级语类型的高级语言中。言中。用一片连续空间（一维数组）实现链式存储，这种用一片连续空间（一维数组）实现链式存储，这种方式称为方式称为静态链表静态链表。具体实现方法：具体实现方法：定义一个结构型数组（每个元素都含定义一个结构型数组（每个元素都含有有数据域数据域和
33、和指示域指示域），就可以完全描述链表，），就可以完全描述链表，指示域指示域就相当于动态链表中的指针就相当于动态链表中的指针, ,指示结点在数组中的相指示结点在数组中的相对位置。对位置。4.4.静态链表静态链表31 静态单链表的类型定义如下：静态单链表的类型定义如下：#define MAXSIZE 1000 /预分配链表的最大长度 typedef struct ElemType data ; /数据域 int cur ; /指示域 component ,SLinkListMAXSIZE; /这是一维结构型数组前例前例1 1：一：一线性表线性表 S S = ( ZHAO, QIAN, SUN, L
34、I, = ( ZHAO, QIAN, SUN, LI, ZHOU, WU )ZHOU, WU )，用静态链表如何表示？，用静态链表如何表示？说明说明1 1：假设假设S S为为SLinkListSLinkList型变量，则型变量，则SMAXSIZESMAXSIZE 为一为一个静态链表；个静态链表；S0.curS0.cur则表示第则表示第1 1个结点在数组中的位置。个结点在数组中的位置。32说明说明2 2：如果数组的第如果数组的第i i个分量表示链表的第个分量表示链表的第k k个结点，个结点，则：则：Si.dataSi.data表示第表示第k k个结点的数据；个结点的数据； Si.curSi.cu
35、r 表示第表示第k+1k+1个结点个结点( (即即k k的直接后继的直接后继) )的位置。的位置。data1 1ZHAO3LI5QIAN6WU0ZHOU4SUN20 01 12 23 34 45 56 610001000curi头结点头结点头结点头结点说明说明3 3：静态链表的插入与删除静态链表的插入与删除操作与普通链表一样，不需要移操作与普通链表一样，不需要移动元素，只需修改指示器就可以动元素，只需修改指示器就可以了。了。例如：在线性表例如：在线性表 S = ( ZHAO, S = ( ZHAO, QIAN, SUN, LI, ZHOU, WU )QIAN, SUN, LI, ZHOU, W
36、U )的的QIAN, SUNQIAN, SUN之间之间插入新元素插入新元素插入新元素插入新元素LIULIU，可以这样实现：可以这样实现：33Step1:Step1:将将QIANQIAN的指示器原内容备份到临时变量的指示器原内容备份到临时变量temptemp：temp = S3.cur；Step2:Step2:将将QIANQIAN的指示器换为新元的指示器换为新元素素LIULIU的位置：的位置：S3.cur = S3.cur = 7 7；Step3:Step3:将将LIULIU的指示器变为后的指示器变为后继继SUNSUN的位置：的位置：SS7 7.cur = temp.cur = temp ；da
37、ta2SUN4ZHOU0WU6QIAN5LI3ZHAO1 10 01 12 23 34 45 56 610001000curi头结点头结点头结点头结点LIULIU6 67 77 734本节小结本节小结1.1.线性结构线性结构( (包括表、栈、队、数组）的定义和特点包括表、栈、队、数组）的定义和特点：仅一个首、尾结点，其余元素仅一个直接前驱和一个仅一个首、尾结点，其余元素仅一个直接前驱和一个 直接后继。直接后继。2. 2. 线性表线性表逻辑结构逻辑结构：“一对一一对一” 存储结构：存储结构：顺序、链式顺序、链式运运 算：算：修改、插入、删除修改、插入、删除3.3.顺序存储顺序存储特征：特征：逻辑
38、上相邻，物理上也相邻；逻辑上相邻，物理上也相邻；优点：优点：随机查找修改快随机查找修改快 O(1)O(1)缺点：缺点：插入、删除慢插入、删除慢 O(n)O(n)改进方案：改进方案：链表存储结构链表存储结构链表存储结构链表存储结构35循环链表的特点：循环链表的特点：从任一结点出发均可找到表中其他从任一结点出发均可找到表中其他结点结点双向链表的特点：双向链表的特点：可方便找到任一结点的前驱可方便找到任一结点的前驱静态链表的特点：静态链表的特点：不用指针也能实现链式存储和运算不用指针也能实现链式存储和运算4.4.链式存储链式存储特征：特征：逻辑上相邻，物理上未必相邻；逻辑上相邻，物理上未必相邻；优点
39、：优点：插入、删除快插入、删除快 O(1)O(1)缺点：缺点：随机查找修改慢随机查找修改慢 O(n)O(n)5.5.几种特殊链表的特点：几种特殊链表的特点：36讨论：讨论： 顺序存储和链式存储的区别和优缺点？顺序存储和链式存储的区别和优缺点？顺序存储时，顺序存储时，逻辑上相邻的数据元素，其物理存放地址逻辑上相邻的数据元素，其物理存放地址也相邻。顺序存储的优点是存储密度大，存储空间利用也相邻。顺序存储的优点是存储密度大，存储空间利用率高且能随机存取；缺点是插入或删除元素时不方便。率高且能随机存取；缺点是插入或删除元素时不方便。链式存储时，链式存储时，相邻数据元素可随意存放，但所占存储空相邻数据元
40、素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。链式存储的优点是插入或删除元素时点间关系的指针。链式存储的优点是插入或删除元素时很方便，使用灵活。缺点是存储密度小，存储空间利用很方便，使用灵活。缺点是存储密度小，存储空间利用率低，且只能顺序存取。率低，且只能顺序存取。顺序表顺序表适宜于做适宜于做查找查找这样的静态操作；这样的静态操作；链表链表宜于做宜于做插入、删除插入、删除这样的动态操作。若线性表的长度变化不大，这样的动态操作。若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；若线性表的长度且其主要操作是查找，则采用顺序表；若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链变化较大，且其主要操作是插入、删除操作，则采用链表。表。37
