线性表的链式表示和实现

1、1第第2 2章章 线性表线性表22.3 2.3 线性表的链式表示和实现线性表的链式表示和实现3 链式存储结构特点：链式存储结构特点：其结点在存储器中的位置是随意的，即逻辑上其结点在存储器中的位置是随意的，即逻辑上相邻的数据元素在物理上不一定相邻。相邻的数据元素在物理上不一定相邻。如何实现？ 通过来实现！让每个存储结点都包含两部分：让每个存储结点都包含两部分：数据域数据域和和指针域指针域指针指针数据数据指针指针指针指针或或样式：样式：数据域：数据域：存储存储元素数值数据元素数值数据指针域：指针域：存储直接后继或存储直接后继或者直接前驱的存储位置者直接前驱的存储位置2.3.1 2.3.1 链表的表

2、示链表的表示4链表存放示意图如下： a1heada2/an讨论讨论1 1：每个存储结点都包含两部分：数据域和每个存储结点都包含两部分：数据域和讨论讨论2 2：在单链表中，除了首元结点外，任一结点的在单链表中，除了首元结点外，任一结点的存储位置由存储位置由 指示。指示。 其直接前驱结点的链域的值其直接前驱结点的链域的值(2) (2) 与链式存储有关的术语与链式存储有关的术语：1 1）结点）结点：数据元素的存储映像。由数据域和指针域两数据元素的存储映像。由数据域和指针域两部分组成；部分组成；2 2）链表）链表： n n 个结点由个结点由指针链指针链组成一个链表。它是线性组成一个链表。它是线性表的链

3、式存储映像表的链式存储映像，称为线性表的链式存储结构称为线性表的链式存储结构。只包含一个指针域的称为单链表或线性链表只包含一个指针域的称为单链表或线性链表指针域指针域53 3）头指针、头结点和首元结点的区别）头指针、头结点和首元结点的区别头指针头指针头结点头结点首元结点首元结点a1heada2infoan首元结点首元结点是指链表中存储线性表第一个数据元素是指链表中存储线性表第一个数据元素a a1 1的的结点。结点。头结点头结点是在链表的首元结点之前是在链表的首元结点之前附设附设的一个结点；数的一个结点；数据域内只放空表标志和表长等信息，它不计入据域内只放空表标志和表长等信息，它不计入表长度。表

4、长度。头指针头指针是指向链表中第一个结点（或为头结点、或为是指向链表中第一个结点（或为头结点、或为首元结点）的指针；首元结点）的指针；示意图如下：示意图如下：6讨论讨论2 2： 在链表中设置在链表中设置头结点头结点有什么好处？有什么好处？讨论讨论1 1： 如何表示如何表示空表空表？因为任何结点都有前驱结点，而在做插入和删除操因为任何结点都有前驱结点，而在做插入和删除操作时，都需修改其前驱结点的指针域，作时，都需修改其前驱结点的指针域，因此对首元结点因此对首元结点可以统一处理。即简化插入和删除操作；可以统一处理。即简化插入和删除操作；表头指针是指向头结点的非空指针，因此空表和非表头指针是指向头结

5、点的非空指针，因此空表和非空表的处理一样。空表的处理一样。无头结点时，当无头结点时，当头指针头指针的值为的值为空空时表示空表；时表示空表；头指针头指针无头结点无头结点头指针头指针头结点头结点有头结点有头结点有头结点时，当有头结点时，当头结点头结点的的指针域为空指针域为空时表示空表。时表示空表。7一个线性表的逻辑结构为：一个线性表的逻辑结构为：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANGZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存），其存储结构用储结构用单链表单链表表示如下，表示如下，请问其请问其头指针的值头指针的值是多少？是多少？存

6、储地址存储地址数据域数据域指针域指针域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25答：答：头指针头指针是指向链表是指向链表中中第一个第一个结点的指针，结点的指针，因此关键是要寻找因此关键是要寻找第一第一个结点的地址。个结点的地址。7ZHAOH31称：头指针称：头指针H的值是的值是31（3 3）举例）举例例例1：8 现有一个具有五个元素的线性表现有一个具有五个元素的线性表L=23L=23，1717，4747，0505，3131，若它以链接方式存储在下列若它以链接方式存储在下列100100119119号地号地址址空间中，每个结

7、点由数据（占空间中，每个结点由数据（占2 2个字节个字节）和指针）和指针（占（占2 2个字节个字节）组成，如下图所示。）组成，如下图所示。其中指针其中指针X X，Y Y，Z Z的值分别为多少？该线性表的首结的值分别为多少？该线性表的首结点起始地址为多少？末结点的起始地址为多少？点起始地址为多少？末结点的起始地址为多少？答：答：X=X= Y= Y= Z= Z= , , 首址首址= = 末址末址= = 。例例2 2：9讨论讨论: : 链表的数据元素有链表的数据元素有两个域两个域，不再是简单数据，不再是简单数据类型，编程时该如何表示？类型，编程时该如何表示？因每个结点至少有两个分量，且数据类型通常不

8、因每个结点至少有两个分量，且数据类型通常不一致，所以要采用一致，所以要采用结构结构数据类型。数据类型。答：答：设每个结点用变量设每个结点用变量表示，表示，其指针用其指针用 表示，两个分量分表示，两个分量分别用别用和和表示，这两表示，这两个分量如何赋值？个分量如何赋值？p方式方式1： 直接表示为直接表示为 node.data；node.next=方式方式2：p指向结点首地址指向结点首地址 p-data=; p-next= ; 方式方式3：p指向结点首地址指向结点首地址 (*p).data=； (*p).next10单链表的抽象数据类型描述如下单链表的抽象数据类型描述如下（参见教材（参见教材P28

9、P28）：typedef struct LNode ElemType data; /数据域 struct LNode *next; /指针域LNode, *LinkList; / *LinkList为Lnode类型的指针Q1Q1：第一行的第一行的LNodeLNode 与最后一行的与最后一行的LNodeLNode是不是一回事？是不是一回事？A1A1：不是。前者不是。前者LNodeLNode是结构名，后者是结构名，后者LNodeLNode是对整个是对整个structstruct类型的一种类型的一种“缩写缩写”，是一种，是一种“新定义名新定义名”，它只，它只是对现有类型名的补充，而不是取代。是对现有

10、类型名的补充，而不是取代。这就是我们在复习这就是我们在复习c语言时讲的语言时讲的自引用结构自引用结构11Q2Q2： 那为何两处要同名那为何两处要同名( (LNodeLNode和和LNodeLNode）？太不严谨）？太不严谨了吧？了吧？A2A2：同名是为了表述起来方便。因为描述的对象相同，同名是为了表述起来方便。因为描述的对象相同，方便阅读和理解。方便阅读和理解。Q3Q3：结构体中间的那个：结构体中间的那个structstruct LNodeLNode是何意？是何意？A3A3：在：在“缩写缩写” LNodeLNode还没出现之前，只能用原始的还没出现之前，只能用原始的struct LNodest

11、ruct LNode来进行变量说明。此处说明了指针分量来进行变量说明。此处说明了指针分量的数据类型是的数据类型是struct LNodestruct LNode。返返 回回122.3.2 2.3.2 链表的实现链表的实现13（1 1） 单链表的存取单链表的存取思路：思路：要存取第要存取第i i个数据元素，必须从头指针起一直找到个数据元素，必须从头指针起一直找到该结点的指针该结点的指针p p，然后才能执行，然后才能执行 p-data=new_value p-data=new_value 。访问第访问第i i个数据元素的操作函数可写为：个数据元素的操作函数可写为：Status GetElem_L(

12、LinkList L, int i, ElemType e)p=L-next; j=1; /带头结点的链表while(p&jnext; +j;if ( !p ji ) return ERROR; /i不合法p-data =e; /若是读取则为：e=p-data; return OK;/ GetElem_L缺点：缺点：想寻找单链表中第想寻找单链表中第i i个元素，只能从头指针开个元素，只能从头指针开始逐一查询（始逐一查询（顺藤摸瓜顺藤摸瓜），无法随机存取），无法随机存取 。14在链表中第在链表中第i i个位置前插入一个元素个位置前插入一个元素x 的示意图如下：的示意图如下：X Xsai-

13、1aip链表插入的核心语句：链表插入的核心语句：p-nexts-nextX 结点的生成方式：结点的生成方式：s=(Lnode*)malloc(m);s-data= x ;s-next= ?aiai-1pX X （2 2） 单链表的插入单链表的插入（重点）重点）15 Status ListInsert_L(LinkList L, int i, ElemType e) / LinstInsert_L算法的时间复杂度为算法的时间复杂度为: :O(ListLength(L)p = L; j = 0;while (p & j next; +j; / 寻找第 i-1 个结点if (!p | j i

14、-1) return ERROR; /i不合法 s = (LinkList)malloc(sizeof(LNode) s-data = e; s-next = p-next; p-next = s; / / 插入插入return OK;16在链表中删除某元素在链表中删除某元素ai的示意图如下：的示意图如下：ai+1 ai-1 aip删除动作的核心语句（要借助辅助指针变量删除动作的核心语句（要借助辅助指针变量q q）：）：q = p-next; /首先保存首先保存a ai i的指针，靠它才能找到的指针，靠它才能找到a ai+1i+1 p-next(p-next) - nextq（3 3） 单链表

15、的删除单链表的删除（重点）重点）p-next=q-next；/将将a ai-1i-1与与a ai+1i+1两结点相连两结点相连, ,淘汰淘汰a ai i结点结点free(q); 17 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; / 寻找第 i 个结点，并令 p 指向其前趋if (

16、!(p-next) | j i-1) return ERROR; / 删除位置不合理q = p-next; p-next = q-next; /删除并释放结点 e = q-data; free(q);return OK;18空间效率分析空间效率分析链表中每个结点都要增加一个指针空间，相当于总链表中每个结点都要增加一个指针空间，相当于总共增加了共增加了n n 个整型变量，空间复杂度为个整型变量，空间复杂度为 O(n)O(n)。在在n n个结点的单链表中要删除已知结点个结点的单链表中要删除已知结点* *P P，需找到它，需找到它的的 ，其时间复杂度，其时间复杂度 。 O(n)O(n)练习：练习：1

17、9操作步骤：操作步骤：一、建立一个一、建立一个“空表空表”；二、输入数据元素二、输入数据元素a an n， 建立结点并插入；建立结点并插入；三、输入数据元素三、输入数据元素a an-1n-1， 建立结点并插入表头；建立结点并插入表头；ananan-1四、依次类推，直至输入四、依次类推，直至输入a a1 1为止为止。（4 4）单链表的建立）单链表的建立例如：例如：头插法头插法输入输入 n n 个数据元素的值，建立带头结个数据元素的值，建立带头结点的单链表。点的单链表。链表是一个动态的结构，它不需要预先分配空间，因链表是一个动态的结构，它不需要预先分配空间，因此生成链表的过程是一个结点此生成链表的

18、过程是一个结点“逐个插入逐个插入” ” 的过程。的过程。头插法建表头插法建表该方法从一个空表开始，重复读入数据，生成新结该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后点，将读入数据存放到新结点的数据域中，然后将将新结点插入到当前链表的表头上新结点插入到当前链表的表头上，直到读入结束标，直到读入结束标志为止。志为止。执 行 的 语 句 组 为 :s next L next； L next s；L(a) 建空表c1ss 指向新申请的结点s data c1(b) 申请新结点并赋值Lci 1s(c) 插入第一个结点Lc2c1cic1s(d) 插入第i个元素21v

19、oid CreateList_L(LinkList &L, int n) / 头插法建立带头结点的单链表 / CreateList_L算法的时间复杂度算法的时间复杂度为:O(Listlength(L)L = (LinkList) malloc (sizeof (LNode);L-next = NULL; / 先建立一个带头结点的单链表for (i = n; i 0; -i) s = (LinkList) malloc (sizeof (LNode); scanf(&s-data); / 输入元素值 s-next = L-next; L-next = s; / 插入尾插法建表尾插

20、法建表该方法是将新结点插入到当前链表的表尾上，为此该方法是将新结点插入到当前链表的表尾上，为此必须必须增加一个尾指针增加一个尾指针r，使其始终指向当前链表的尾，使其始终指向当前链表的尾结点结点rs；r始终指向单链表的表尾L(a) 建空表c1ss 指向新申请的结点空间sdatac1(b) 申请新结点并赋值Lc1s(c) 插入第一个结点Lc2c1rrr nexts；(d) 插入第二个结点sr尾插法尾插法建表建表 void CreateList_L(LinkList &L, int n) tail = L = (LinkList) malloc( sizeof (LNode) );/尾指针初

21、始化为表头指针尾指针初始化为表头指针 L-next = NULL; for( i=n; i0; -i) s = (LinkList) malloc( sizeof (LNode) ); scanf( &s-data); s-next = NULL; tail-next = s; tail = s; 24算法要求：算法要求：已知：已知：线性表线性表 A A和和B B，分别由单链表分别由单链表 LaLa和和Lb Lb 存储存储，其中，其中数据元素按值非递减有序排列（即已经有序）；数据元素按值非递减有序排列（即已经有序）；要求：要求：将将A A和和B B归并为一个新的线性表归并为一个新的线性

22、表C , CC , C的数据元素仍的数据元素仍按值非递减排列。设线性表按值非递减排列。设线性表C C由单链表由单链表 Lc Lc 存储。存储。假设：假设：A=A=（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）例例1 1：两个链表的归并（教材：两个链表的归并（教材P31P31例）例）算法设计：算法设计：算法主要包括搜索、比较、插入三个操作：算法主要包括搜索、比较、插入三个操作：搜索：搜索：需要设立三个指针

23、来指向需要设立三个指针来指向La La 、LbLb和和LcLc链表；链表；请将该例子和请将该例子和ch2-1的的ppt的第的第18页进行比较！页进行比较！25La3 5 8 11 Lb2 6 8 119 PaPbPaPbPaPa、PbPb用于搜索用于搜索LaLa和和LbLb， PcPc指向新链表当前结点。指向新链表当前结点。归并过程示意如下：归并过程示意如下：Lc=LaPbPaPaPb比较：比较：比较比较LaLa和和LbLb表中结点数据的大小；表中结点数据的大小；插入：插入：将将LaLa和和LbLb表中数据较小的结点插入新链表表中数据较小的结点插入新链表Lc Lc 。请注意链表的特点，仅改变指

24、针便可实现请注意链表的特点，仅改变指针便可实现数据的移动数据的移动, ,即即“数据不动，指针动数据不动，指针动”26 void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc)/已知单链线性表La和Lb的元素按值非递减排列。归并为Lc后也按值非递减排列。 free(Lb); /释放Lb的头结点 /MergeList_L pc-next = pa pa: pb ; /插入非空表的剩余段 while(pa&pb) /将pa 、pb结点按大小依次插入Lc中 if (pa-datadata) pc-next=pa;

25、pc=pa; pa=pa-next; else pc-next=pb; pc=pb; pb=pb-next pa=LaLa-next; pb=LbLb-next; Lc=pc=La； /有头结点思考：思考：重复的数据元素不需要插入，怎么修改？重复的数据元素不需要插入，怎么修改？练习：练习：已知已知L是带头结点的非空单链表，指针是带头结点的非空单链表，指针p所指的所指的结点既不是第一个结点，也不是最后一个结点结点既不是第一个结点，也不是最后一个结点l 删除删除*p结点的直接后继结点的语句序列结点的直接后继结点的语句序列 q = p-next; p-next = q-next; free(q);l

26、 删除删除*p结点的直接前驱结点的语句序列结点的直接前驱结点的语句序列 q = L; while( q-next-next != p) q = q-next; s = q-next;/s即所要找到的即所要找到的p的前驱的前驱 q-next = p;/链接链接 free(s);l 删除删除*p结点的语句序列结点的语句序列 q = L; while( q-next != p) q = q-next; q-next = p-next; free(p);l 删除首元结点的语句序列删除首元结点的语句序列 q = L-next; L-next = q-next; free(q);l 删除最后一个结点的语句

27、序列删除最后一个结点的语句序列 while(p-next-next != NULL) p = p-next; q = p-next; p-next = NULL; free(q);29用上述定义的单链表实现线性表的操作时，存在的用上述定义的单链表实现线性表的操作时，存在的问题问题：改进链表的设置：改进链表的设置：1 1单链表的表长是一个隐含的值；单链表的表长是一个隐含的值； 1. 1. 增加增加“表长表长”、“表尾指针表尾指针” 和和 “当前位置的指当前位置的指针针” 三个数据域；三个数据域； 2. 2. 将基本操作中的将基本操作中的“位序位序 i i ”改变为改变为“指针指针 p p ”。2

28、 2在单链表的最后一个元素之后插入元素时，需遍在单链表的最后一个元素之后插入元素时，需遍历整个链表；历整个链表；3 3在链表中，元素的在链表中，元素的“位序位序”概念淡化，结点的概念淡化，结点的“位位置置”概念加强。概念加强。返返 回回30typedef struct LNode /结点类型 Elemtype data; struct LNode *next; *Link, *Positiontypedef struct /链表类型 Link head, tail; /分别指向链表头尾结点 int len; /链表中元素个数（长度） Linklist;2.3.3 2.3.3 一个带头结点的线性

29、链表类型定义如下：一个带头结点的线性链表类型定义如下：（用类（用类C C语言，见语言，见P37P37）：）：结点的结点的结构结构表结构表结构基本操作（略）基本操作（略）返返 回回31 最后一个结点的指针域的指针又指回第一个结点的最后一个结点的指针域的指针又指回第一个结点的链表。从表中任一结点出发均可找到表中其它结点链表。从表中任一结点出发均可找到表中其它结点 a1 a2 . an 1. 1. 循环链表循环链表 和单链表的差别仅在于，判别链表中最后一个结和单链表的差别仅在于，判别链表中最后一个结点的条件不再是点的条件不再是“后继是否为空后继是否为空”，而是，而是“后继是后继是否为头结点否为头结点

30、”即即p-next?=headhead2.3.4 2.3.4 其它形式的链表其它形式的链表32单链表中查找只能从前往后，而不能从后往前查。为了单链表中查找只能从前往后，而不能从后往前查。为了查找方便，提高查找速度，可以在结点上增加一个指针查找方便，提高查找速度，可以在结点上增加一个指针域，用来存结点的直接前驱，这样的链表称为域，用来存结点的直接前驱，这样的链表称为双向链表双向链表。其其结点的结构结点的结构为：为：typedef struct DuLNode ElemType data; /数据域 struct DuLNode *prior; /前驱指针域 struct DuLNode *nex

31、t; /后继指针域 DuLNode , *DuLinkList ; 双向链表类型的定义如下：双向链表类型的定义如下：2.3.4 2.3.4 其它形式的链表其它形式的链表2. 2. 双向链表双向链表设指针p指向某一结点，则双向链表结构的对称性双向链表结构的对称性描述如下描述如下： (pprior)next = p = (pnext)prior,即结点*p的存储位置既存放在其前趋结点*(pprior)的直接后继指针域中，也存放在它的后继结点*(pnext)的直接前趋指针域中ai-1aiai+1p343.3.双向循环链双向循环链表表空表空表非空表非空表 a1 a2 . anhead-prior=he

32、ad-next=headhead35双向链表插入操作（重点）：双向链表插入操作（重点）：设设p p已指向第已指向第 i 元素，请在第元素，请在第 i 元素元素前前插插入元素入元素x ai-1的后继从的后继从 ai ( ( 指针是指针是p)变为变为 x（指针是指针是s) : s-next = p ; p-prior-next = s ; ai 的前驱从的前驱从 ai-1 ( 指针是指针是p-prior)变为变为 x ( 指针是指针是s); s-prior = p -prior ; p-prior = s ; 注意：要修改注意：要修改双向指针！双向指针！x sai-1 ai p指针域的变化指针域的

33、变化：void dinsertbefor(DuLNode *p，ElemType x)DuLNode *s=malloc(sizeof(DuLNode);sdata=x;snext=p; ppriornext=s;sprior=pprior; pprior=s; 问：（问：（1） （2） （3）,（4）位置是否可交换？）位置是否可交换？原则是什么？原则是什么？改成如下代码试试：改成如下代码试试：sprior=pprior;snext=p;ppriornext=s;pprior=s;改成如下代码试试：改成如下代码试试：snext=p;sprior=pprior;pprior=s;ppriorne

34、xt=s;37指针域的变化：指针域的变化： 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个元素个元素, ,删除第删除第i个元素个元素注意：要注意：要修改双向修改双向指针！指针！void ddeletenode(dlistnode *p)ppriornext=pnext; pn

35、extprior=pprior;free(p);39动态链表样式：动态链表样式：静态链表样式：静态链表样式：指针指针数据指针指针数据指针指针数据指示指示数据指示指示数据指示指示数据指示指示数据指示指示数据数组中每个元数组中每个元素都至少有两素都至少有两个分量，属于个分量，属于结构型数组结构型数组。常用于无指针常用于无指针类型的高级语类型的高级语言中。言中。用一片连续空间（一维数组）实现链式存储，这种用一片连续空间（一维数组）实现链式存储，这种方式称为方式称为静态链表静态链表。具体实现方法：具体实现方法：定义一个结构型数组（每个元素都含定义一个结构型数组（每个元素都含有有数据域数据域和和指示域指

36、示域），就可以完全描述链表，），就可以完全描述链表，指示域指示域就相当于动态链表中的指针就相当于动态链表中的指针, ,指示结点在数组中的相指示结点在数组中的相对位置。对位置。4.4.静态链表（自学）静态链表（自学）40 静态单链表的类型定义如下：静态单链表的类型定义如下：#define MAXSIZE 1000 /预分配链表的最大长度 typedef struct ElemType data ; /数据域 int cur ; /指示域 component ,SLinkListMAXSIZE; /这是一维结构型数组前例前例1 1：一：一线性表线性表 S S = ( ZHAO, QIAN, SUN

37、, LI, ZHOU, = ( ZHAO, QIAN, SUN, LI, ZHOU, WU )WU )，用静态链表如何表示？，用静态链表如何表示？说明说明1 1：假设假设S S为为SLinkListSLinkList型变量，则型变量，则SMAXSIZESMAXSIZE 为一为一个静态链表；个静态链表；S0.curS0.cur则表示第则表示第1 1个结点在数组中的位置。个结点在数组中的位置。41说明说明2 2：如果数组的第如果数组的第i i个分量表示链表的第个分量表示链表的第k k个结点，个结点，则：则：Si.dataSi.data表示第表示第k k个结点的数据；个结点的数据； Si.curSi

38、.cur 表示第表示第k+1k+1个结点个结点( (即即k k的直接后继的直接后继) )的位置。的位置。data1 1ZHAO3LI5QIAN6WU0ZHOU4SUN2curi说明说明3 3：静态链表的插入与删除静态链表的插入与删除操作与普通链表一样，不需要移操作与普通链表一样，不需要移动元素，只需修改指示器就可以动元素，只需修改指示器就可以了。了。例如：在线性表例如：在线性表 S = ( ZHAO, S = ( ZHAO, QIAN, SUN, LI, ZHOU, WU )QIAN, SUN, LI, ZHOU, WU )的的QIAN, SUNQIAN, SUN之间之间LIULIU，可以这样

39、实现：可以这样实现：42Step1:Step1:将将QIANQIAN的指示器原内容备份到临时变量的指示器原内容备份到临时变量temptemp：temp = S3.cur；Step2:Step2:将将QIANQIAN的指示器换为新元的指示器换为新元素素LIULIU的位置：的位置：Step3:Step3:将将LIULIU的指示器变为后的指示器变为后继继SUNSUN的位置：的位置：data2SUN4ZHOU0WU6QIAN5LI3ZHAO1 1curi data cur 0 6 1 2 2 a 3 3 b 4 4 c 5 5 d 0 6 7 7 0 li = si.cur; 指针后移操作指针后移操作lMalloc: i = s0.cur; 第一个可用结点位置第一个可用结点位置 if(s0.cur) s0.cur = si.cur;lF