济南大学数据结构课件 第二章.pptVIP

2．3．1 线性链表 线性表的链式表示------是可以用一组任意的存储单元存储线性表的数据元素。 以链式结构存储的线性表称之为线性链表。 特点是该线性表中的数据元素可以用任意的存储单元来存储。线性表中逻辑相邻的两元素的存储空间可以是不连续的。为表示逻辑上的顺序关系，对表的每个数据元素除存储本身的信息之外，还需存储一个指示其直接后继的信息。这两部分信息组成数据元素的存储映象，称为结点。 例： 线性表 （赵，钱，孙，李，周，伍，张，王）的链式表示 （赵，钱，孙，李，周，吴，郑，王）的链式表示 链表相关的名称 结点: 两部分信息组成，存储数据元素信息的数据域，存储直接后继存储位置信息的指针域。 作业: 1、p17 2.14 ; 2、引入头结点的原因？ 3、如何逆置一个单链表为一个新表？ 2：链表的逆置问题。 3：链表的合并问题（注意空间和时间的要求） 4：结构的选择问题。 5：链表的起始条件，判断条件，特点等 类型表示: #define MAXSIZE 1000 typedef struct { ElemType data ； int cur ； } component ，SLinkList[MAXSIZE] ； data表示数据元素信息； cur代替指针指示结点在数组中的相对位置。 zhao qian sun li zhou 0 1 2 3 4 5 6 1 4 3 5 2 0 插入和删除操作 1) 在第i=4个结点前插入新元素 jin 添加新元素jin，并指向原第i=4个结点 jin 3 修改第3个结点的指向 找到第i-1=3个结点，记住第i=4个结点的位置3 3 6 2) 删除第2个结点 zhao qian sun li zhou 0 1 2 3 4 5 6 1 2 3 4 5 0 jin 4 6 找到第2个结点，记住下一个结点的位置 找到第1个结点 3 3 修改指向 2. 循环链表 表中最后一个节点的指针域指向头结点，形成一个环。 a1 … an Head 0 空表: Head 从表的任意结点出发均可以找到表中的其他结点。 优点: Head-next=head 例，取循环链表第 i 个元素。 p = L-next ；j = 1 ； while ( p L j i ) { p = p-next ；++j ； } if ( p = L || j i ) return ERROR ； e = p-data ； return OK ； Status GetElem_L ( LinkList L，int i，ElemType e ) { } 操作与线性单链表基本一致，差别只是在于算法中的循环结束条件不是p是否为空，而是p是否等于头指针。 有时为了方便某些操作，通常在循环链表中设立尾指针。 … Tail1 … Tail2 Tail1-next = p Tail2-next = Tail1-next p = Tail2-next p 例如顺次合并两个线性表。 3. 双向链表 在循环链表中寻找结点的直接后继很简单，只需要O(1)；但要寻找结点的直接前趋就要从表头指针找起，需要O(n)。 双向链表的结点有两个指针域: 一个指向直接后继，一个指向直接前趋。 prior data next 类型表示: typedef struct DuLNode{ ElemType data ； struct DuLNode * prior ； struct DuLNode * next ； } DuLNode ，* DuLinkList ； prior data next A C Head B 性质: 设d 是指向某个结点的指针，则有 d d-next-prior = d-prior-next = d 操作: 只涉及单向的操作与单链基本相同，但插入、删除操作变化很大。 空表: Head 指令 1) 插入 X s 第一步： 找到要在之前插入的结点，p记录。 第一步： 1. s-prior = p-prior ； 2. p-prior-next = s ； 3. s-next = p ； 4. p-prior = s ； A B p 一定注意指令的顺序！ 2 1 3 4 2) 删除 A C B 1. 找到要删除的结点，p记录。 p 2. p-prior-next = p-next ； 3. p-next