数据结构小结（一）总论

我就是我 2022-08-18 12:22 130阅读 0赞

## 目录 ##

第一章 导论与说明

第二章 链表

第三章 队列与栈

第四章 串

第五章 多维数组与广义表与散列表

第六章 树，二叉树，AVL树，查找树

第七章 图论算法

第八章 排序算法分析

第九章 内存管理算法

## 概念总结 ##

数据：

数据是描述客观事物的数值,字符以及能够输入到计算机中且能被处理的各种符号集合。

数据元素：

数据元素是组成数据的基本单位，是数据集合的个体，在计算机中通常作为一个整体进行考虑和处理。

数据对象：

数据对象是性质相同的数据元素的集合。

数据结构：

数据结构是指互相之间存在一种或多种特定关系的数据元素集合。

数据与数据关系。

数据类型：

数据类型是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称。

## 数据结构的基本类型 ##

集合结构：

各个数据元素之间除了属于一个集合关系外，无任何关系。

线性结构：

结构中的数据元素之间存在着一对一的线性关系。

树形结构：

结构中的数据元素之间存在一对多的层次关系。

图状结构：

结构中的数据元素之间存在着多对多的任意关系。

## 算法的基本概念 ##

算法的特性：

有穷性，确定性，可行性，有输入，有输出。

算法的评价标准：

正确性，可读性，健壮性（鲁棒性），高效率与低存储量需求。

## 时间复杂度计算方法 ##

求解算法的时间复杂度的具体步骤是：

⑴ 找出算法中的基本语句；

算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。

⑵ 计算基本语句的执行次数的数量级；

只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。

⑶ 用大Ο记号表示算法的时间性能。

将基本语句执行次数的数量级放入大Ο记号中。

如果算法中包含嵌套的循环，则基本语句通常是最内层的循环体，如果算法中包含并列的循环，则将并列循环的时间复杂度相加。例如：

for (i=1; i<=n; i++)

x++;

for (i=1; i<=n; i++)

for (j=1; j<=n; j++)

x++;

第一个for循环的时间复杂度为Ο(n)，第二个for循环的时间复杂度为Ο(n2)，则整个算法的时间复杂度为Ο(n+n2)=Ο(n2)。

常见的算法时间复杂度由小到大依次为：

Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)

Ο(1)表示基本语句的执行次数是一个常数，一般来说，只要算法中不存在循环语句，其时间复杂度就是Ο(1)。Ο(log2n)、Ο(n)、Ο(nlog2n)、Ο(n2)和Ο(n3)称为多项式时间，而Ο(2n)和Ο(n!)称为指数时间。计算机科学家普遍认为前者是有效算法，把这类问题称为P类问题，而把后者称为NP问题。

这只能基本的计算时间复杂度，具体的运行还会与硬件有关。

发表评论取消回复

表情：

评论列表（有 0 条评论，130人围观）

还没有评论，来说两句吧...

相关阅读

相关 Python 序列详解（一）总论

目录 1. 分类 2. 通用操作 2.1 索引 2.2 切片 2.3 相加 2.4 相乘

迷南。/ 2022年12月13日 04:06/ 0 赞/ 233 阅读

相关数据结构小结（一）总论

目录第一章导论与说明第二章链表第三章队列与栈第四章串第五章多维数组与广义表与散列表第六章树，二叉树，AVL树，查找树第七章图论算法

我就是我/ 2022年08月18日 12:22/ 0 赞/ 131 阅读

相关结构体小结2

结构体与指针和链表结构体的声明结构体是一种类型，其中包含数个不同的类型变量 struct student \{ char name\[20\]; i

叁歲伎倆/ 2022年08月07日 13:39/ 0 赞/ 185 阅读

相关 XML——小结一

一、What——是什么？ XML是标准通用标记语言 (SGML) 的子集，非常适合 Web 传输。XML 提供统一的方法来描述和交换独立于应用程序或供应

客官°小女子只卖身不卖艺/ 2022年06月05日 12:52/ 0 赞/ 220 阅读

相关小结1

1、select 0和select 1区别 select 0，返回结果为0 select 1，返回结果为1 select 0 from tableA，返回与tab

系统管理员/ 2022年05月14日 03:44/ 0 赞/ 224 阅读

相关数据结构——电话本-链表-带头结点

//电话簿 //功能：保存，插入，删除，输出电话号码信息， include<stdio.h> include<stdlib.h>

àì夳堔傛蜴生んèń/ 2022年04月22日 02:20/ 0 赞/ 267 阅读

相关贪吃蛇小游戏总论

引言：一个月前完成了贪吃蛇小游戏，作为一个用来练手的项目，自己的确成长了不少，打算就这个项目写点东西，后来工作太忙，再加上一些原因，一直到现在才有空写下来，贪吃蛇小游戏分为总论

比眉伴天荒/ 2022年04月10日 07:18/ 0 赞/ 1099 阅读

相关备考历程小结一

备考历程小结一随着考试周的结束，我大学所有的考试已经结束了。接下来还有一个夏季学期和毕业论文了，毕业论文在考研结束后再搞，目前只有一个夏季学期会影响到我，但不会耽误太

梦里梦外;/ 2022年01月21日 03:19/ 0 赞/ 231 阅读

相关 Python02_流程控制及数据结结构

\----------------- 流程控制 -------------------- 条件判断语法：单分支 if <con

超、凢脫俗/ 2021年11月01日 03:36/ 0 赞/ 237 阅读

相关【数据结构】（单链表）带头结点删除最小值元素

> 算法思想：while 循环找出最小节点的前驱节点以及最小值节点之后删除即可 void Delete_Min(LNode &head ){

叁歲伎倆/ 2021年10月29日 22:08/ 0 赞/ 304 阅读