数据结构----第二章线性表1

注意：数据结构三要素--逻辑结构、数据的运算、存储结构（物理结构）

一、线性表的基本操作

Tips：对数据的操作（记忆思路）--创销、增删改查；

          C语言函数的定义--<返回值类型>函数名（<参数1类型>参数1，<参数2类型>参数2，......)

          实际开发中，可根据实际需求定义其他的基本操作

          函数名和参数的形式、命名都可改变（命名要有可读性）

 二、顺序表

 1.顺序表的实现----静态分配

 2.顺序表的实现---动态分配

 

 顺序表的特点：1.随机访问，即可以在O（1）时间内找到第i个元素。代码实现：data[i-1]；静态、动态分配都一样

2.存储密度高，每个节点只存储数据元素

 3.拓展容量不方便（即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高）

4.插入，删除操作不方便，需要移动大量元素

                   

 3.顺序表的插入删除

1）插入

注意位序、数组下标的关系，并从后面的元素依次移动

如果出现顺序表已经存满的情况，代码可以做如下修改

2）插入操作的时间复杂度

3）删除

 

 

 4.顺序表的按位查找

 5.顺序表的按值查找

 

 三、单链表

一、单链表的定义

1.什么是单链表？

2. 用代码定义一个单链表

 

 

 3.不带头结点的单链表

 4.带头结点的单链表

 5.不带头结点vs带头结点

 二、单链表的插入与删除

1.按位序插入（带头结点）--平均时间复杂度：0（n）

 

 

 

 

 2.按位序插入（不带头结点）

 3.指定结点的后插操作

 

 直接调用后插操作的函数就可以了

 4.指定结点的前插操作

1）传入头指针

 2）不传入头指针

 

 5.按位序删除（带头结点）

 

 6.指定结点的删除

如果不带头结点，删除第一个元素，是否需要特殊处理？

 

 7.封装的好处

小功能模块化，代码逻辑清晰

 三、单链表查找（基于带头结点的情况）

1.按位查找

 

 

 2.封装（基本操作）的好处

避免重复代码，简洁，易维护

 3.按值查找

 

 4.求表的长度

 

 四、单链表的建立

 

 

头插法，尾插法：核心就是初始化操作，指定结点的后插操作