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