登录免费注册



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

首页  思维导图  详情



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

2020-05-18 13:43:01   1  举报





AI智能生成

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

计算机考研

数据结构

线性表

考研

大学教育

模版推荐

作者其他创作

大纲/内容

版权∈ 本人所有 <br>严禁擅自转载和商用 受法律保护

更新记录

2020.5.8 开坑

线性表

定义【逻辑结构】

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

数据元素的位序从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 不方便

优缺点

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

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

基本操作

插入

按位序插入O(1)

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

不带头结点

指定结点前插

指定结点后插

删除O(n)

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

按位序删除

指定节点

查找

按位O(n)

按值O(n)

双链表

定义

    头尾指针

基本操作O(n)

前插

后插

销毁与删除

遍历

循环链表

循环单链表

定义

循环双链表

定义

基本操作

插入

删除

静态链表

定义

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

优缺点

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

应用场景

不支持指针的低级语言

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

                   顺序表和链表对比<br>【逻辑结构、储存结构、基本操作、效率】

增删改查——左顺右链

创

删

改

查

使用场景

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

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

章节技巧

 Collect

Get Started

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

 Collect

Get Started

考研数据结构

 Collect

Get Started

图_计算机数据结构考研

 Collect

Get Started

计算机考研数据结构知识点













评论

0 条评论

下一页



图形选择

思维导图

主题

补充说明

AI生成





修改AI描述

去编辑

重新生成

提示 

关闭后当前内容将不会保存，是否继续？

取消

确定

Document