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