大话数据结构 【三】线性表3

单链表的整表删除

也就是在内存中把它释放掉

思路：

q变量没有存在的必要？

循环体内直接写即可

 

 

解释：

p是一个结点，有数据域和指针域，free(p)时，把整个结点全删了

q的作用，使下一个结点得到了记录，便于等当前结点释放后，把下一个结点拿回来补充

 

 

 

单链表结构与顺序存储结构优缺点

 

数据结构选择经验

 

静态链表

【其实就是给没有指针的高级语言设计的一种实现单链表能力的方法】

用数组描述的链表

让数组的元素都是由两个数据域组成                                【即每一个下标对应一个data和一个cur】

data ——> 存放数据元素

cur——> 存放该元素的后继在数组中的下标【相当于next指针】

 

 #为了方便插入数据，通常会把数组建立的大些【以有空闲空间，避免插入时溢出】

#对于不提供结构struct的语言，可以使用一对并行数组data,cur处理

#有些是把第二个元素作为头结点，原理相同，只是取得存放位置不同

此时图示，相当于初始化数组的状态，代码：

 

 假设已将数据“甲乙丙丁..”等存入静态列表

 

 1.插入

 要解决的：

如何用静态模拟动态链表结构的存储空间的分配，需要时申请，不需要时释放

 操作的是数组，不存在像动态链表的结点申请 malloc（）和释放 free（）问题，所以，实现它

 

 

 

 2.删除

 

 

 

 3.优缺点

 

 

【学习其思路】

 

 

 

 

 

 

循环链表

 

解决了一个很麻烦的问题：

如何从某一个结点开始，访问到链表的全部结点

 

 为了使空链表与非空链表的处理一致，通常设一个头结点【并不是说循环链表一定要头结点】

 

解释：

　　　　　　想象一下，链表就像排队入场的运动员，一个接一个的入场，第一个运动员手里举着铭牌。

　　　　　　每个运动员代表一个节点。第一个运动员是头节点。铭牌是头指针。头指针不包含数据，不是节点。

　　　　　　如果让运动员，从线性排队（线性链表）转换成环形排队（环形链表）的话，最后一个运动员应该紧靠着第一个运动员，而不是紧靠着铭牌。因为铭牌不是节点。

　　　　　　链表里，形成链状的东西，是节点。每个节点链接着下一个节点，尾节点链接着头节点。虽然头指针有时候长的像个节点，但是因为它没有真实的数据，只能算作头指针，而不是节点。

 循环链表带有头结点的空链表：

 

 

循环链表和单链表的差异：——> 在于循环的条件判断上

单链表：判断p—>next是否为空

循环链表：判断p—>next不等于头结点，则循环未结束

 

 单链表中，有了头结点时，可以用O（1）的时间访问第一个结点，但对于访问最后一个结点需要O（n）时间

实现用O（1）时间访问到最后一个结点——>  用指向终端结点的尾指针表示循环链表

 

 用尾指针实现循环链表的合并

 

 

 

 

 

 

双向链表

在单链表的每个结点中，再设置一个指向其前驱结点的指针域

 

               

 

 很多操作和单链表相同，多了反向遍历查询等

 

在插入和删除时，要更改两个指针变量

 

插入

 删除