线性表_计算机数据结构考研
2020-05-18 13:43:01 1 举报AI智能生成
线性表_计算机数据结构考研
作者其他创作
大纲/内容
版权∈ 本人所有
严禁擅自转载和商用 受法律保护
严禁擅自转载和商用 受法律保护
更新记录
2020.5.8 开坑
线性表
定义【逻辑结构】
相同数据类型占空间一样大 有限序列
数据元素的位序 从1开始
基本操作【运算】
& 对参数的修改结果永久赋值
L.length=0 顺序表初始化长度为0 必须做 以免脏数据受影响
物理/存储结构
顺序表（顺序存储）
定义
逻辑相邻 物理位置也相邻
相同数据类型占空间一样大 有限序列
sizeof(ElemType) 元素大小
实现
静态分配
动态分配
L.data=(ElemType *)malloc (sizeof(ElemType) * initSize)
//申请一整片连续的储存空间 ElemType=int
//申请一整片连续的储存空间 ElemType=int
基本操作
插入 O(n)
先移动后面元素
删除O(n)
先移动前面元素
查找
按位O(1)
静态分配
动态分配
按值O(n)
结构体不能直接 == 判断
特点
随机访问 O(1)内找到第i个元素
储存密度高 每个节点之存储数据元素
拓展容量不方便
插入、删除操作需要移动大量元素
链表（链式存储）
单链表
定义
数据元素+下一个节点的指针
LinkList —— 强调这是一个单链表
LNode * —— 强调这是一个结点
初始化
带头结点
空表判断 L->next==NULL 方便
不带头结点
空表判断 L==NULL 不方便
优缺点
不要求大片连续空间 改变容量方便【优点】
不可随机存储 耗费一定空间存指针 无法逆向检索【缺点】
基本操作
插入
按位序插入O(1)
带头结点【头结点看成第0个结点】
不带头结点
指定结点前插
指定结点后插
删除O(n)
删除第i个结点 == 找到第i-1个结点 将其指针指向第i+1个结点 释放第i个结点
按位序删除
指定节点
查找
按位O(n)
按值O(n)
双链表
定义
头尾指针
基本操作O(n)
前插
后插
销毁与删除
遍历
循环链表
循环单链表
定义
循环双链表
定义
基本操作
插入
删除
静态链表
定义
数据元素 + 指向下一个结点的数组下标(游标)
优缺点
增删不许移动大量元素 【优点】
不可随机存储 容量固定不变 只能从头依次查找【缺点】
不可随机存储 容量固定不变 只能从头依次查找【缺点】
应用场景
不支持指针的低级语言
数据元素固定不变【操作系统的文件分配表FAT】
顺序表和链表对比
【逻辑结构、储存结构、基本操作、效率】
【逻辑结构、储存结构、基本操作、效率】
增删改查——左顺右链
创
删
改
查
使用场景
表长难以预估 经常要增删元素 —— 链表
表厂可以预估 查找操作较多 —— 顺序表
章节技巧
0 条评论
下一页
