

首页  思维导图  详情



计算机考研线性表数据结构知识框架笔记

2022-11-01 11:42:06   0  举报





AI智能生成

计算机考研线性表数据结构知识框架笔记

计算机考研

线性表

模版推荐

作者其他创作

大纲/内容

线性表

定义【逻辑结构】

相同数据类型占空间一样大&nbsp; 有限序列

数据元素的位序从1开始

基本操作【运算】

&amp; 对参数的修改结果永久赋值

L.length=0 顺序表初始化长度为0 必须做以免脏数据受影响

物理/存储结构

顺序表（顺序存储）

定义

逻辑相邻物理位置也相邻

相同数据类型占空间一样大有限序列

sizeof(ElemType) 元素大小

实现

静态分配

动态分配

L.data=(ElemType *)malloc (sizeof(ElemType) * initSize)&lt;br&gt;//申请一整片连续的储存空间&nbsp; ElemType=int

基本操作

插入 O(n)&nbsp;

先移动后面元素

删除O(n)

先移动前面元素

查找

按位O(1)

静态分配

动态分配

按值O(n)

结构体不能直接 == 判断

特点

随机访问 O(1)内找到第i个元素

储存密度高每个节点之存储数据元素

拓展容量不方便

插入、删除操作需要移动大量元素

链表（链式存储）

单链表

定义

数据元素+下一个节点的指针

分支主题

LinkList —— 强调这是一个单链表

LNode * —— 强调这是一个结点

初始化

带头结点

空表判断 L-&gt;next==NULL&nbsp; 方便

不带头结点

空表判断 L==NULL 不方便

优缺点

不要求大片连续空间改变容量方便【优点】

不可随机存储耗费一定空间存指针无法逆向检索【缺点】

基本操作

插入

按位序插入O(1)

带头结点【头结点看成第0个结点】

不带头结点

指定结点前插

指定结点后插

删除O(n)

删除第i个结点 == 找到第i-1个结点将其指针指向第i+1个结点释放第i个结点

按位序删除

指定节点

查找

按位O(n)

按值O(n)

双链表

定义

&nbsp; &nbsp; 头尾指针

基本操作O(n)

前插

后插

销毁与删除

遍历

循环链表

循环单链表

定义

分支主题

循环双链表

定义

分支主题

基本操作

插入

删除

静态链表

定义

数据元素 + 指向下一个结点的数组下标(游标)

优缺点

增删不许移动大量元素【优点】&lt;br&gt;不可随机存储容量固定不变只能从头依次查找【缺点】&lt;br&gt;

应用场景

不支持指针的低级语言

数据元素固定不变【操作系统的文件分配表FAT】

&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;顺序表和链表对比&lt;br&gt;【逻辑结构、储存结构、基本操作、效率】

分支主题

增删改查——左顺右链

创

删

改

查

使用场景

表长难以预估经常要增删元素 —— 链表

表厂可以预估查找操作较多 —— 顺序表

 Collect

Get Started

线性表_计算机数据结构考研

 Collect

Get Started

串_计算机数据结构考研

 Collect

Get Started

数据结构与算法知识框架计算机二级公共基础笔记

 Collect

Get Started

排序_计算机数据结构考研





0 条评论

下一页