数据结构-线性表
2020-06-01 17:07:33 2 举报AI智能生成
自己考研期间画的数据结构框架图，参考了大话数据结构和王道的数据结构的书，希望可以帮到大家，大家多多点赞
作者其他创作
大纲/内容
线性表
定义
n个相同元素的有限序列
特点
元素个数有限
逻辑上顺序性
单个数据元素
类型相同
抽象性
基本操作
实现方式
(分类)
(分类)
顺序存储
顺序表
定义
特点
a. 线性表的逻辑顺序与物理顺序一致
b. 数据元素之间的关系是以元素在计算机“物理位置相邻”来体现
基本操作
插入
移动次数n/2
时间复杂度：o(n)
删除
移动次数（n-1）/2
时间复杂度：o(n)
查找
移动次数(n+1)/2
时间复杂度：o(1)
链式存储
单链表
定义
头指针作用
标记，更方便的进行操作
记录数据，链表长度等
操作
结点的实现
动态分配：malloc
动态释放：free
判断非空
L->next!=null
建立
头插
（可实现逆序）
（可实现逆序）
效果
过程
1.建立一个空表
2.插入An，创建结点并插入(先插入a1，然后a2插入到a1前面，以此类推，后面所有的元素都插入到地上一个元素前面)
3.插入An-1，创建结点并插入
4.如此类推，直到A1
尾插
效果
过程
每次把结点插入到链表的尾部
评价
算法复杂度为o(n),
查找
按值查找
按序号查找
评价
算法复杂度o(n)
插入
前插
后插
评价
算法复杂度o(n)
删除
（双指针操作）
（双指针操作）
实现1(找前)
实现2（删后）
评价
算法复杂度o(n)
评价
总体操作算法复杂度均为o(n)
双链表
定义
为了克服单链表的单向性设立
每个结点有两个指针域，一个指前，一个指后
为了方便插入和删除数据而设立的
与单链表相比，访问相邻节点更方便
操作
插入
删除
循环链表
定义
操作
判断
判断是否非空
head->next==head
判断是否为尾结点
p->next==head（p为非头结点）
如果插入和删除仅仅在表的两端发生，可采用带表尾指针的循环链表
插入
表尾可以插入新节点，O(1)
表头插入相当于表尾插入
删除
表尾删除要找前驱，复杂度o(n)
在表头可以直接删除，复杂度为o(1)
静态链表
定义
借助数组来描述线性表的链式存储结构，结点也有数据域和指针域
特点
所有元素都存储在一个连续的空间段，但是相邻的两个元素不一定处于一个相邻的空间
修改指针域就可以实现删除和插入操作，但不能随机访问
一次分配所有空间，删除插入不用释放分配空间
效果
优缺点比较
顺序表
没有指针，不用花费额外开销
读取访问简单便利
插入删除o(n),查找o(1)
链表
无需事先了解线性表长度
长度动态变化
能适应经常的插入和删除
插入删除o(1),查找o(n)
常见算法
两个有序链表的和并
设有一组初始记录关键字序列（K1，K2，…，Kn），
要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分，
其中左半部分的每个关键字均小于Ki，右半部分的每个关键字均大于等于Ki。
要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分，
其中左半部分的每个关键字均小于Ki，右半部分的每个关键字均大于等于Ki。
删除单链表中多余结点
对列表进行插入排序
链式结构上实现简单选择排序算法
顺序存储结构上实现求子串算法
将所有奇数移到所有偶数之前的算法
判断单链表中元素是否是递增的算法。
0 条评论
下一页
