关于不同结构链表的思考

1、2022-2-211关于不同结构链表的思考2022-2-212链表的不同组织形式l单向向后l单向向前l单向循环l包括向后循环，向前循环的组织方式851012头指针头指针851012头指针头指针尾指针尾指针851012头指针头指针2022-2-213链表的不同组织形式l双向链表61296129struct Node int data ； struct Node *preceding , *next ;2022-2-214* 问题的提出l 链表基本操作中表现出的问题： 边界条件的单独处理！2022-2-215l 以单向、向后链表为例l 链表的边界状态： 空表状态进行插入结点操作 非空表，插入的数据

2、结点作为链表的第一个数据结点 非空表，删除链表中的第一个数据结点l 总结： 边界状态造成了链表每一次操作的检验和相关状态的单独处理。 2022-2-216l 向后链表插入结点边界条件1 向非空表中插入第一个数据结点 初始状态：head != NULL 插入结点： cp 操作：cp-next = head ; head = cp; 比较一般插入结点操作 初始状态：work 指定插入位置 插入结点：cp 操作：cp-next = work-next ; work-next = cp ;2022-2-217l 向后链表插入结点边界条件2 向空表中插入第一个数据结点 初始状态：head = NULL

3、插入结点： cp 操作：head = cp ; 比较一般插入结点操作 初始状态：work 指定插入位置 插入结点：cp 操作：cp-next = work-next ; work-next = cp ;2022-2-218引入带头结点的链表l带头结点链表的逻辑形式1006headX2001100661024491052头指针头结点：链表中的第一个结点，其数据内容为空（无效），链表的第一个有效数据结点总是连接在头结点之后。2022-2-219引入带头结点的链表l带头结点链表的空表状态与设置实现1006headX20011006头指针头结点：链表中的第一个结点，其数据内容为空（无效），链表的第一个

4、有效数据结点总是连接在头结点之后。空表状态的程序设置：cp=(struct Nd*) malloc(sizeof(struct Nd)if(cp=NULL) exit(0);cp-next = NULL;head = cp;2022-2-2110引入带头结点的链表l带头结点链表的边界条件分析1006headX2001100661024491056头指针2466101010421、向空表中插入第一个数据结点、向空表中插入第一个数据结点2、插入结点作为链表的第一个数据结点、插入结点作为链表的第一个数据结点头结点2022-2-2111引入带头结点的链表l向空表中插入第一个数据结点1006headX2

5、0011006头指针空表中存在一个头结点：定位：work = head;cp-next = work-next;work-next = cp; 非空表的插入：定位：work指向插入位置之前的数据结点，插入操作：cp-next = work-next;work-next = cp;6cp2022-2-2112引入带头结点的链表l向非空表中插入第一个数据结点1006headX20011006头指针非空表中存在一个头结点：定位：work = head;cp-next = work-next;work-next = cp; 非空表的插入：定位：work指向插入位置之前的数据结点，插入操作：cp-nex

6、t = work-next;work-next = cp;2cp62022-2-2113引入带头结点的链表l 结论： 在链表中引入头结点，简化了链表的边界状态的特殊处理，能够将边界状态合并为链表的一般状态，简化了链表的基本操作。 检验头结点对于链表结点删除的影响： 删除链表的第一个数据结点 删除链表中唯一的数据结点2022-2-2114无头结点向后链表的结点删除一般操作 定位条件： worknextdata=sdata5689headtailwork2022-2-2115无头结点向后链表结点删除的一般操作需要利用被删除结点的指针作链接 worknext = (worknext)next5689

7、headtailwork2022-2-2116无头结点向后链表结点删除的一般操作需要利用被删除结点的指针作链接 delp=worknext;worknext = (worknext)nextfree(delp)5689headtailwork2022-2-2117无头结点向后链表结点删除的边界分析删除操作发生在链表的边界操作不仅涉及work，而且涉及head或tail569headtailwork2022-2-2118无头结点向后链表结点删除的边界分析1删除第一个数据结点: delp = head; head = head-next; free(delp);569headtaildelp202

8、2-2-2119无头结点向后链表的结点删除边界分析2删除末尾数据结点： delw=work-next; work-next = work-next-next; free(delw);可以归结到一般结点删除处理。569headtailwork2022-2-2120带头结点向后链表的结点删除边界分析1删除第一个数据结点：work = head; delp=work-next; work-next = work-next-next; free(delp);可以归结到一般结点删除处理。X69headtailwork2022-2-2121引入带头结点的链表l删除链表的第一个数据结点1006headX20

9、01100661024491056头指针246610101042头结点非空表中存在一个头结点：定位：work = head; delp = work-next; work-next=delp-next; free(delp);非空表一般结点的删除：定位：work指向被删除结点之前 delp = work-next; work-next=delp-next; free(delp);2022-2-2122引入带头结点的链表l删除链表中唯一的一个数据结点1006headX2001100661024头指针头结点非空表中存在一个头结点：定位：work = head; delp = work-next;

10、work-next=delp-next; free(delp);非空表一般结点的删除：定位：work指向被删除结点之前 del = work-next; work-next=delp-next; free(delp);2022-2-2123链表基本操作小结l 无头结点链表 空表设置 head = NULL 插入：if （链表为空）空表插入操作 else if（插入为首结点） 首结点插入操作，移动头指针 else 一般定位、插入操作 删除：if（链表只有一个数据结点） 删除成为空表特殊操作 else if （删除链表的首届点） 首结点删除单独操作，移动头指针 else 一般定位、删除操作 2022-2-2124链表基本操作小结l 带头结点链表 空表设置 head = cp； cp-next = NULL; 插入：work 定位于插入位置之前的结点； cp = work-next; work-next = cp; 删除：work 定位于被删除结点之前的结点； delp = work-next; work-next = delp-next; free(delp); 2022-2-21252022-2-21262022-2-2127无头结点链表空表设置：head = tail = NULL;带头结点链表空表设置：head = tail =