数据结构与算法：基础概述

前言:

以下的所有内容,只有大体提纲,没有详细内容 只作为本人只是体系梳理.大家想知道详细内容自行查阅相关书籍!

数据结构的相关概念和术语

数据:信息的载体,是描述客观事物属性的数,字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合.

数据元素:是数据的基本单位

结构:数据元素之间的关系称为结构

数据项:若干数据项组成数据元素(表格中的姓名 性别 年龄就是数据项)

数据对象:是具有相同性质的数据元素的集合

抽象数据类型:是指一个数学模型及定义在该模型上的一组操作

举个例子:做表格的时候,张三,男 ,汉族等等为数据项.张三的所有信息加起来一条就是数据元素.所有人的数据元素就是数据对象.

数据结构三要素(研究数据结构应该从这三方面分析)

逻辑结构(集合结构 线性结构 树状结构 网络结构)

存储结构(顺序存储 链式存储 索引存储 散列存储)

数据的运算(运算的定义是针对逻辑结构的,指出运算的功能,运算的实现是针对存储结构的,指出运算的具体操作步骤)

算法的基本概念

算法是对特定问题求解步骤的一种描述,它是指令的有限序列,其中每条指令表示一个或多个操作.

算法的五个特性(有穷性 确定性 可行性 输入 输出)

设计一个好的算法应该具有(正确性 可读性 健壮性 效率与低存储)

算法效率的度量(时间复杂度 空间复杂度)对于这些概念不再展开说,有想了解的可以自行查阅

程序=数据结构+算法

数据结构是把问题信息化,将信息存入计算机

算法是处理信息,解决实际问题

线性表

线性表 分为 顺序存储---->顺序表

链式存储---->单链表 指针实现

------->双链表 指针实现

-------->循环链表 指针实现

--------->静态链表 借助数组实现

(想做一个表的,但是没找到那个功能)

线性表是具有相同数据类型的n个数据元素的有限序列.

1>元素个数有限

2>元素具有逻辑上的顺序性

3>每个元素有相同的存储空间

4>仅讨论元素之间的逻辑关系,不考虑元素究竟表示什么内容

线性表的基本操作(创销 ,增删改查)

线性表的特点:

1)元素个数有限

2)元素具有逻辑上的顺序性,在序列中各元素排序有先后次序

3)元素都是数据元素,每个元素都是单个元素

4)元素的数据类型都相同,每个元素都占有大小相同的存储空间

5)元素具有抽象性(仅讨论元素间的逻辑关系,而不考虑元素表示什么内容)

线性表是一种逻辑结构,表示在元素之间一对一的相邻关系,顺序表和链表是指存储结构,两者属于不同层面的概念.

线性表的位序是从1开始,而数组元素的下标是从0开始

线性表的顺序表示-----顺序表

顺序表:是用一组地址连续的存储单元依次存储线性表中的数据元素.使逻辑上相邻和2个元素物理位置上也相邻.

顺序表的特点

1)随机访问

2)存储密度高.每个结点只存储数据元素

3)插入和删除需要移动大量的元素.

4)拓展容量不方便

5)顺序表容易实现,任何高级语言都有数组类型,链表的操作是基于指针的.

6)静态分配时,装满就不能再扩充,加入新的元素会出现内存溢出.因此需要预先分配.太大容易闲置浪费,太小容易溢出.

动态分配虽然可以扩充,但需要移动大量元素,操作效率低.内存中没有更大块的内存空间会导致分配失败.

顺序表适用于表长可以估计,不需要经常增删

静态链表是用数组实现的也叫游标实现法

线性表的链式表示---链式表

不需要在逻辑上相邻的在物理上也相邻,不需要移动元素值需要修改指针就行.每个链表的结点除了存放自身的信息以外还需要存放一个指向后继的指针(数据域和指针域),所以要是删除整个链表的时候就需要注意了,如果直接把指向下一个的指针删掉就找不到下一个该删谁了

单链表

解决了:顺序表需要大量连续空间的问题.

带来了:附加指针域会带来较大的空间开销,元素离散分布不能达到随机存取.

循环单链表

和单链表的区别就是,最后的结点不是空,而是指向了头结点

双链表

解决了:单链表只有一个指向后继的指针

循环双链表

双链表的前驱指针还要指向尾结点

栈和队列

栈(顺序栈 链栈 共享栈)

对列(循环队列 链式队列 双端队列)

栈首先是一种线性表,是一种只允许在一端插入或删除的线性表(先进后出)

队列也是一种线性表 一端插入,另一端删除(先进先出)

栈的主要应用

1)匹配 括号成对,一定条件可以消除,变化诸如此类的题目用栈最简单.

2)表达式求值(前缀,后缀) 这个例子的精髓在于"遍历"大家好好体会

3)递归

老生常谈的话题了.递归需要满足的条件 (递归体 递归出口)

递归的精髓在于能不能把原始问题转化为属性相同但是规模较小的问题.递归虽然很简单,但是效率低.如果遇到解不出来的算法题目,用递归一般情况效率比较低,但是我们要遵循"先完成,再完美"的原则.可以暴力解决.

递归算法转换为非递归算法,通常需要借助栈来实现(大家自己试)

队列的主要应用

1)遍历(树 图)

2)主机与外设速度不匹配的问题(主机与打印机)

3)多用户引起的资源竞争的问题(CPU)

数组与线性表的关系:数组是线性表的推广,一维数组可以看做一个线性表.二维数组可以看做什么?(大家自己想想).

数组一旦被定义,维数和维界就不能被改变了.

接下来就是数组的存储了.

多维数组有2种映射方式(行优先 列优先)

矩阵的压缩存储(学过线性代数应该对于矩阵不陌生,此处不介绍数学概念,只研究存储方式)

对称矩阵(只存主对角线和下三角区)

三角矩阵(主对角线,上下常量)

稀疏矩阵(三元组 行 列 值)

注意点:

1>n个不同的元素进栈,合理的出栈顺序个数--->卡特兰数(我不会打公式,大家自己查一下)

栈和队列实际上都是线性表的应用和推广,基础内容虽然不多,但是在这一部分题目很多变,很灵活.根据实际情况,也会出现空间换时间,需注意.