当前位置：网站首页>线性表（顺序表和链表）

线性表（顺序表和链表）

2022-08-02 18:48:00 【没有人会真的躺平】

2.1线性表的定义和基本操作

线性表的定义

在这里插入图片描述

线性表的基本操作

在这里插入图片描述
只有c++支持引用，c语言不支持引用。

2.2-1顺序表的定义（静态分配在栈区，动态分配申请的堆区的空间）

顺序表的定义

在这里插入图片描述

顺序表的实现——静态分配（使用静态数组）

在这里插入图片描述

顺序表的实现——动态分配

在这里插入图片描述

2.2-2顺序表的插入删除

顺序表的插入

在这里插入图片描述

顺序表的删除

在这里插入图片描述

2.2-3顺序表的查找

按位查找

在这里插入图片描述

按值查找

在这里插入图片描述

2.3-1 单链表的定义

在这里插入图片描述

不带头结点的单链表

在这里插入图片描述

带头结点的单链表

在这里插入图片描述

2.3-2 单链表的插入删除

按照位序插入

带头节点

在这里插入图片描述

下图 i 为位序，至少为1

不带头节点

在这里插入图片描述

指定结点的后插操作

在这里插入图片描述

指定结点的前插操作

第一种办法：循环查找p的前驱 q，再对q后插
在这里插入图片描述

第二种方法：在要前插的那个节点后边插入一个节点，交换这两个节点的数据，相当于实现前插了

按位序删除（带头结点）

在这里插入图片描述

指定结点的删除

在这里插入图片描述

2.3-3单链表的查找

在这里插入图片描述

按位查找

在这里插入图片描述

按值查找

按值查找只能从头往后扫描
在这里插入图片描述

2.3-4 单链表的建立（尾插法和头插法）

尾插法

初始化单链表
在这里插入图片描述
每次从头循环到尾，去添加一个新节点，很费时间

所以可以确定一个指针 r 直接指向最后一个节点。边添加节点，边移动表尾指针 r

头插法

在这里插入图片描述

2.3-5 双链表

在这里插入图片描述

双链表的初始化

在这里插入图片描述

双链表的插入

在这里插入图片描述

双链表的删除

在这里插入图片描述

双链表的遍历

在这里插入图片描述

2.3-6 循环链表

循环单链表

在这里插入图片描述

循环双链表

在这里插入图片描述

2.3-7 静态链表

定义一个静态链表

在这里插入图片描述
下图是定义静态链表的一般方法

下图是王道书上定义静态链表的方法，SLinkList[MaxSize]像java中定义数组SLinkList[ ]

证明了图中结论

简单基本操作的实现

在这里插入图片描述

下图和上图一样，只是多一些笔记

2.3-8 顺序表的链表的比较

在这里插入图片描述

下图声明数组啥的在栈区，系统自动回收；malloc申请堆区内存，需要自己去释放申请的内存空间。

开放式问题

版权声明
本文为[没有人会真的躺平]所创，转载请带上原文链接，感谢
https://blog.csdn.net/qq_32480989/article/details/125985099

边栏推荐

猜你喜欢

随机推荐