数据结构1
what:
数据结构
系统软件设备
基础硬件设备
数据:
数据:数据对象(数据元素(数据项【many】))
算法评价指标:
时间复杂度:代码执行的数量级
空间复杂度:代码执行所占空间的数量级
数据结构三要素:
数据逻辑结构:
- 线性结构:线性表,数组,栈和队列,广义表,串
- 非线性结构:树(二叉树),图(有向,无向),集合,网
数据的存储结构:
- 顺序存储:只能按照顺序存储的称位顺序存储(计算机基础知识)
- 链式存储:可以不按照顺序存储的存储结构
- 索引存储:在存储数据时,附加索引来保证查询(数据库)
- 三列存储:按照关键字进行计算存储(哈希表)
数据的运算:
- 算数运算:+ - *
- 逻辑运算:与或非
顺序表:
定义:一组地址连续的存储单元紧密相连并形成线性表,把逻辑上紧密相连的数据,实现在物理上也紧密相连。
随机存取:使用者仅需要提供内存地址就可以获取该内存中存放的数据内容,在这里首先需要获取的是初始内存地址,即存放第一个数据元素的内存地址
问题:
已知有一个顺序表长度n,获取第3个位置的元素需要几次操作?
已知有一个顺序表长度n,获取一个等于3的元素需要几次操作?
已知有一个顺序表长度n,删除表尾元素需要几次操作?
已知有一个顺序表长度n,向表里面插入数据需要几次操作?
链表:
定义:一组地址并非紧密相连的数据存储形成的线性表,其数据相邻但地址不一定相邻。
优点:更容易实现存储空间的碎片化利用,但是需要更多的存储空间来存放下一个元素的地址。
指针:指向某一地址的一个索引。
头节点:数据节点前面的一个节点。
问题:
已知有一个顺序表长度n,获取第3个位置的元素需要几次操作?
已知有一个顺序表长度n,获取一个等于3的元素需要几次操作?
已知有一个顺序表长度n,删除表尾元素需要几次操作?
已知有一个顺序表长度n,向表里面插入数据需要几次操作?
链表是否随机存取?(随机存取概念)
考虑链表的插入和删除的时间复杂度?考虑顺序表的插入和删除的时间复杂度?
指针概念加深
顺序表中按值查找的时间复杂度?
单链表
链表中节点的结构:data(存放数据)next(存放指针)
优点和缺点:插入删除等基本操作比较快,占双倍空间
头节点:链表第一个位置之前的节点,但是不存放数据
头指针:指向链表中第一个节点的指针
头节点的必要性:在第一个位置反复插入删除操作会比较方便如果头节点不存在,则会?
头节点的好处,操作统一化demo:删除链表中值为2的节点,并获取这个链表
加入头节点的链表形式:
问题:
1、新建一个链表,并插入若干节点(头插法,尾插法)
2、向链表中插入一个节点到指定位置
3、删除链表中特定值的节点4、查找链表
双链表:
节点结构:pre data next
优点和缺点:
双链表中的插入和删除:
判空?
循环链表
一些题目:(什么样链表适合干什么样的活,算法!)
(1)要求一个线性表,可以快速插入和删除,并且可以反映数据之间的逻辑关系,采用存储:链表
(2)一个链表常用的操作是在末尾插入节点和删除节点,选用最省时间的链表:
A、带头节点双循环链表
B、单循环链表
C、带尾指针的单循环链表
D、单链表
解析:
A:1、头节点pre 2、双链表4步插入(5)
B:找不到插入位置
C:单链表2步插入(2)
D:找不到
(2变式)一个线性表常用的操作是在末尾插入节点和删除节点,选用最省时间的线性表:顺序表
线性结构:
栈:限制性线性表,严格遵循先进后出,后进先出
队列:限制性线性表,严格遵循先进先出,后进后出
数组:数组是开发编程中最常用的数据结构,按顺序存放,随机存取,与存储结构中的顺序存储有一些混淆
广义表:类似于数学中集合形式的存在,具有两种操作head和tail
串:字符串,仅考察数目
栈:(先进后出)
定义:只能在一端插入或删除的线性表
栈顶:可操作(压栈【进栈】 弹栈【出栈】)
栈底:不可
共享栈(判满选择):两个顺序栈共享一个一维数组空间,分别为0号栈、1号栈(一般0号栈从数组的第一个元素开始向后存储,1号栈从最后一个元素向前存储)
给一串数字,1,2,3,按顺序进栈,有多少种出栈方式?(5)
给出n个数字,按顺序进栈,有多少种出栈方式?(公式)
栈的应用:
递归 计组(寄存器【优先级低的扔栈里】、运算器)
题:运算符栈和操作数栈
运算符栈(比较 isp 和 icp)
当栈顶的 isp < 当前符号的 icp 的时候就入栈,否则出栈,注意#不占位