0-软件技术基础-数据结构(L1-3)-sxdai.ppt

带头结点的单链表 通常情况下，为了运算的统一，常在第一个结点前附设一个结点，称为“头结点”，头指针具有标识作用，因而，常用作链表的名字 * LNode *p; p=（LNode *）malloc(sizeof(LNode))； 则完成了申请一块LNode类型的存储单元的操作，并将其地址赋值给指针变量p。 ∧ H 空表 a1 a2 an ∧ H 　 非空表 … P p-data p-next 带头结点单链表的插入操作 * 线性链表操作：插入元素 * * p指向当前结点，pre表示前一个结点(的指针)。 在*p前(*pre后)插入元素s的语句序列： s-next = pre-next; pre-next = s; ak next ai-1 next ai next pre 带头结点单链表的删除操作 * 图2-8 带头结点的单链表 图2-9 在单链表中删除一个结点 线性链表操作：删除元素 * ai-1 next ai next ai+1 next *p表示当前结点,*pre表示*p的前驱结点 删除*p结点的语句序列为： pre-next = p-next; free( p ); 循环链表 如果链表最后一个结点的指针域指向头结点，整个链表形成一个环，这样的链表称为循环链表。 　　　这样，从表中任一结点出发均可找到表中其它结点，其逻辑状态图如图2-10 * 图2-10 循环单链表 循环链表 循环链表一般设表头结点，这样链表将永不为空，这将使空表和非空表的逻辑状态及运算统一起来。 循环链表的操作和线性链表基本一致，差别仅在于算法中的循环条件不是p或p-next是否为空，而是它们是否等于头指针。 与单链表比较，循环链表有以下特点： (1) 在循环单链表中，从表中任何一个结点出发都能访问到其它所有的结点；而单链表一般把头指针作为入口点，从某一结点出发，只能访问到其所有后继结点。 (2) 循环单链表的空表判定条件是： 　　head-next=head。 * 双向链表 前面讨论的链式存储结构中只有一个指示直接后继的指针域，所以从某结点出发只能顺指针往后查找其它结点。 若要查找结点的直接前趋，则应从头指针出发(或在循环单链表中从p结点出发)一直往后找，直到结点q满足q-next=p，那么q是p的前趋结点。 为克服链表这种单向性的缺点，为有更大的灵活性来操作线性链表，可采用双向链表存储结构。 * 双向链表 在每个结点上增加另一个指向线性表中每个元素的前趋结点的指针域prior，就得到双向链表。其结点的结构如下图所示。 其中，prior是指向前趋结点的指针域；data是数据域；next是指向后继结点的指针域。 * 双向链表结点结构 双向链表 将双向链表的头结点和尾结点链接起来组成双向循环链表。 双向链表的几种不同状态如图2-12，图2-13，图2-14和图2-15所示。 * 图2-12 带头结点的空双向链表 图2-13 带头结点的非空双向链表 双向循环链表 * 图2-14 空的双向循环链表 图2-15 非空双向循环链表 双向链表 在非空双向循环链表中，设p是指向链表中任一结点的指针，则有： p-next-prior = p-prior-next = p 这个等式反映了这种链表的本质，在此链表上进行插入或删除操作是十分方便的。双向链表虽然多花了存储空间，但却换得了操作上的更大灵活性。 双向链表的运算如LENGTH(Head)，GET(Head, i)，LOCATE(Head, x)等操作，仅涉及一个方向的指针，操作类似单链表。但插入INSERT、删除DELETE时要同时修改两个方向的指针。 * 双向链表的插入操作 * 图2-16 在双向链表中插入结点 插入时相关操作序列为： ① s-prior = p-prior; ② (p-prior)-next = s; ③ s-next = p; ④ p-prior = s。 双向链表的删除操作 * 图2-17 在双向链表中删除结点 删除时相关操作序列为： ① (p-prior)-next = p-next; ② (p-next)-prior = p-prior; 线性表－课堂练习 * 1.数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储结构无关，是独立于计算机的。 ( Ｙ/N ) 2.在线性表中，数据的存储方式有顺序和链接两种。 3.线性链表的地址 ( )。 (A) 必须连续 (B) 部分地址必