数据结构课程设计报告(课题中的技术路线怎么写)

教材:严为民和吴伟民写的《数据结构》。

但书中的算法都是伪算法(不是程序)，都是解决问题的思路。

具体程序在高逸凡主编的书里有。

黄国宇写的数据结构也可以。

数据结构概述

定义:

我们如何把现实中大量复杂的问题放到一个具体的数据结构中？

并且特定的存储结构被保存在主存储器(存储器)中，并且在

在此基础上，实现某种功能(如查找一个元素，删除一个

元素，对所有元素进行排序)，以及所执行的相应操作

相应的运算也叫算法。

例如，要保存班级中学生的信息，可以使用数组。

但是如果保存了一万个学生的信息，就不会有这么大的连续空空间了，

它可以使用链表来实现。如果保存人员列表，使用链表就不知道他们之间的关系。

谁是领导者？这个结构需要使用树形结构。

再比如交通地图，在几个站点之间修建道路，需要使用地图结构来实现。

解决两个问题:1。把复杂的问题转化为数据以及如何存储数据(如何保存个体，

如何保存个人之间的关系)

2.数据操作

数据结构=个人存储+个人关系存储

算法=对存储数据的操作(对数据的操作取决于特定的存储结构)

程序=数据存储+数据操作+能被计算机执行的语言。

算法:

换句话说:解决问题的方法和步骤

衡量算法的标准:

1.时间复杂度:程序要执行的大概次数(一般核心步骤是循环)，

不是执行的时间。

因为机器性能不同，状态也不同。

2:空之间的复杂度

算法在执行过程中占用的最大内存。

3.困难

难度低，大家更容易理解。

4.鲁棒性，能够处理各种非法输入。

2017年11月8日13时25分42秒

数据结构的状态

数据结构是软件专业的核心课程。堆栈内存和堆内存是不存在的，只是

分配内存的方法是不同的。

很重要，很难，内化的课程。

基本原理

学习数据结构两种学习方法

1.只学伪算法，不看具体实现方法。

2.用编程语言实现，用指针C/C++语言。

最重要的是链表各部分之间的知识，指针知识。

针

指针的重要性:

指针是C语言的灵魂。

定义:地址，存储单元的数量。从零开始的非负整数，range0 – 4G-1

指针就是地址，地址就是指针。

指针是存储内存单元地址的变量。

指针的本质是一个操作受限的非负整数。

通过CPU地址总线、数据总线和控制总线，它与存储器一起存储数据。

等待读取操作。内存是CPU唯一可以访问的大容量存储设备。

存储器有8位，分别是0-4G-1。但是编号为0的内存

单元格不存储有用的数据，所以所有没有指向的指针都必须指向NULL，所以不能

没有意义。

分类:

1:基本类型指针(参见源代码)

内存是在操作系统的统一管理下使用的！

1.软件运行前需要向操作系统申请存储空，在内存空中空闲。

当空够用时，操作系统会分配一段内存空并将软件存储在外存中。

一份保存在内存空，软件开始运行！

2.软件运行过程中，该内存空占用的内存不再分配给其他软件。

3.软件运行时，操作系统会回收空房间，(注意操作系统和

不知道空这个空留下来的数据以便再次分发到其他软件。

4.综上所述，一个软件分配的空中很有可能存在其他之前的软件。

使用后的剩余数据，这些数据成为垃圾数据。所以，对于一个变量来说，

分配空的内存后要初始化的数组。

2.指针和数组之间的关系(有关详细信息，请参见源文件夹下的“指针”文档)

2.指针和数组

指针和一维数组。

数组名

一维数组名是一个指针常量，

它保存一维数组的第一个元素的地址，

它的值不能更改。

一维数组名指向数组的第一个元素。

下标和指针的关系

a[I]& lt；& lt= = & gt& gt*(a+i) //a指向第一个元素，a+i指向数组中标记为I的元素，然后取地址。

假设指针变量的名字是p。

p+i的值是p+I *(p指向的变量所占用的字节数)

指针变量的操作

指针变量不能加、乘或除。

如果两个指针变量属于同一个数组，它们可以相减。

指针变量可以加减整数，前提是最终结果不能超过指针允许的范围。

p+i的值是p+I *(p指向的变量所占用的字节数)

p-i的值是p-I *(p指向的变量所占用的字节数)

p++ & lt；= = & gtp+1

p-& lt；= = & gtp-1

举个例子

如何通过调优函数修改主调优函数中一维数组的内容【如何定义一维数组】

两个参数

保存数组第一个元素的指针变量。

存储数组元素长度的整数变量。

结构

为什么会有结构？

来表示一些复杂的数据类型，但是单一的基本类型不能满足需要。

例如年龄、性别、学号，

需要用简答数据类型表达一些复杂的东西。

诸如

结构学生

{

int aga

char地址；

迷人的性爱；

};//分号不能省略。分号表示结构定义的结束。

什么是结构？

用户根据实际需要定义的一种复合数据类型。没有对数据的操作(c++中的操作)

如何使用结构？

如何使用结构

两种方式:

struct Student st = {1000，& # 34；张三& # 34；, 20};

结构学生* pst = & st

1.

圣西德

2.

PST->；（同suddenionosphericdisturbance）电离层的突然骚扰

pst指向的结构变量中的成员sid(自己读几遍)

注意事项:

结构变量不能加减乘除，但可以互相赋值。

作为函数参数的常见结构变量和结构指针变量

动态内存分配和释放

动态构造一维数组

假设你动态构造了一个int数组。

int * p =(int *)malloc(int len)；

1.malloc只有一个int参数，表示系统需要分配的字节数。

2.malloc函数的作用是在系统中请求len字节的内存空。如果分配成功，

返回第一个字节的地址，如果分配不成功，则返回NULL。

3.malloc函数只能返回第一个字节的地址，所以我们需要把这个没有任何实

国际意义的第一个字节的地址(俗称干地址)转换成有意义的地址，所以

Malloc前面必须是(数据类型*)，表示没有实际意义的第一个字节的地址。

转换成相应类型的地址。比如:

int * p =(int *)malloc(50)；

将系统分配的50个字节的第一个字节的地址转换为int * type。

地址，更准确地说，是将第一个字节的地址转换成四个字节的地址

p指向前四个字节，p+1指向后四个字节。

P+i指向第(i+1)个字节。P[0]是第一个元素，p[i]是第一个。

I+1元素

double * p =(double *)malloc(80)；

将系统分配的80字节第一个字节的地址转换成double *类型。

地址，更准确地说，是将第一个字节的地址转换成一个8字节的地址

p指向前8个字节，p+1指向后8个字节。

P+i指向第(i+1)个字节。P[0]是第一个元素，p[i]是第一个。

I+1元素

免费(p)

释放p指向的内存，而不是p本身占用的内存。

模块1:线性结构

什么是线性结构？

所有的节点(类似于数组的元素)可以用一条直线串起来。

分类:

线性存储器[阵列]

元素在内存中连续分配。

1:什么是数组？

元素具有相同的类型和相同的大小。

2.阵列的优点和缺点:

与链表相比

脱机存储[链表]

定义:

(1)n个节点离散分布

(2)它们通过指针连接，上一个节点存储下一个节点的地址。

(3)每个节点只有一个前趋节点和一个后继节点。第一个节点没有

前一个节点和尾节点没有后继节点。

链表的重要性:

是我们学习数据结构的基础，比如下面的树(一个节点指向下面的几个节点)。

图(任何节点都可以保存其他节点的地址)

家术语:如(头节点，只有下一个元素的地址)-(1(头节点))-(2)-(5)-(8(尾节点))

第一个节点:第一个有效节点

结束节点:最后一个有效节点。

头节点:第一个有效节点之前的节点(2)头节点不存储有效数据。

(3)添加表头节点的目的是为了方便我们对链表的操作。(4)头节点与其他节点具有相同的数据类型。

头指针:一个指向头节点的指针变量(可能是错的，但它是指向第一个有效节点的指针)

尾指针:指向尾节点的指针变量。

我们在头节点前面加一个无意义的头节点，因为这样可以方便链表的操作。

如果我们想通过函数来处理链表，我们至少应该

您需要接受链表的几个参数:

一个参数，(头指针)头节点的地址。

因为我们可以通过头指针来计算链表的所有其他信息。

(尾节点的指针字段存储为空)

链表的分类:

单向链表

双向链表:每个节点有两个指针字段[指针][数据][指针]

循环链表:可以通过任何节点找到所有其他节点。最后一个。

该节点再次指向第一个节点。

非循环链表

链表算法；

横贯

寻求

Clear 空

破坏

找出长度

分类

删除节点

插入非循环链表的伪算法

(1)r = p->pNext

(2)p->pNext = q；

(3)q->pNext = r；

如何把Q指向的节点放在P指向的节点后面(见图片及以下步骤)

(1)取出p指向的节点的指针字段。

(2)P的指针字段指向q

(3)将P的指针字段(指向P后面的一个元素)的值赋给Q的指针字段，

然后q指向p后面的一个元素。

第二种方法(见同一目录中的图)

q->；p next = p-& gt；pNext

p->；pNext = q；

(1)首先使q指向下一个节点(后一个节点的地址存储在p的指针字段中)

(2)使P的指针字段指向q。

(Q不是节点，是存储节点地址的指针变量)

删除非循环链表节点的伪算法

r = p-& gt；pNext

p->；p next = p-& gt；p next-& gt；pNext//这样写会造成内存泄漏，所以需要释放

免费(r)；

删除链表的一个节点。

(1)找不到第二个节点的地址，所以无法释放，需要先指向它。

然后释放。

(2) p->p next-& gt；pNext //p指针字段指向的元素的指针字段。

学习数据结构的目的和要求:

(1)了解堆栈图树的基本概念

(2)努力掌握链表。

(3)这是给你以后有机会自学数据结构的入门课程。

链表的优缺点:

算法:

窄算法与数据的存储方式密切相关。

一般化的算法与数据存储结构无关。

仿制药:

使用某种技术达到的效果是不同的存储方法执行相同的操作。

(数据的操作与数据的存储方式无关)

具体例子请参考数组和链表的冒泡排序的例子。

也就是数组可以用++符号，而链表需要用地址来找。我们可以在c++中使用运算符

重载会掩盖底层细节。用户会看到相同的操作。

2017年11月11日10时48分56秒

堆栈，线性结构的两个常见应用之一

定义:

一种能实现“先进后出”的存储结构

堆栈类似于一个盒子，先放在底部，最后再取出。

分类:

静态堆栈

如果数组是内核，比如(0)、(1)、(2)、(3)是从上到下保存的。

元素，如果我们要删除元素(2)，就必须先删除前面的元素。

动态堆栈

以链表为内核，在1的头部只能添加或删除一个元素。

栈可以执行哪些操作(算法)？

堆栈

堆

堆栈的应用

(1)函数调用(所有的函数调用都是堆栈推送和堆栈弹出)

所谓函数A调用函数B，就是将A执行的最后一条语句的地址与被调用的函数B进行匹配。

将所有内容压入一个堆栈中执行，执行完后释放堆栈，然后释放地址，执行A函数。

(2)中断(中断一个进程以执行下一个进程)

(3)表达式的求值(表达式和运算符的数值部分会分开存储，用两个栈就可以做一个简单的计算器)

(4)内存分配(动态内存在堆中分配)

(5)缓冲处理

(6)迷宫(游戏中的地图，为什么走到一个部分就走不动了)

线性结构的两个常见应用队列

定义:

一种实现“先进先出”的存储结构

排队类似于买票，先进先出，

只允许一端插入元素，另一端退出，中间的元素不能操作。

队列的分类:

(1)链队列(内核是链表)的前面是后面。

删除队列前面的一个元素(行外)并在后面添加一个元素(行内)。

(2)静态队列(内核是一个数组)

假设数组中有6个元素，编号为0 1 2 3 4 5，

限制数组的一些函数，只在队列头删除，在末尾添加元素。

静态队列通常是循环队列。

循环的解释:

(1)为什么静态队列必须是循环队列？(参见源文件夹下的图)

(2)确定循环队列需要多少个参数？

两个参数

头部指针在前，尾部指针在后

(3)循环队列各参数的含义是什么？

这两个参数在不同的情况下有不同的含义。

建议初学者先记住，慢慢体验。

(1)队列初始化

frontnear和frontnear的值都是零(它们在开始时面向同一个元素0，然后在赋值后改变)

(2)队列不是空

Front表示队列的第一个元素。

Rear表示队列中最后一个有效元素的下一个元素。

(3)队列空

front的值等于rear，但不一定空。

(4)解释循环队列入队的伪算法？(见PPT)

两步:看PPT。

(5)解释循环队列出列的伪算法？(见PPT)

(6)如何判断循环队列是空？

如果前面和后面的值相等，则确定队列必须是空

(7)如何判断循环队列是否已满？(详见PPT)

f的大小和r的大小没有一定的关系，r的值也不一定大于f。

当循环队列存储完全满时，r = f，那么我们就无法判断队列是满的还是空。

有两种解决方法:(1)定义另一个变量，保存有效元素的个数。

(2)始终空在一个位置，即按下F和R时，不能存储数字。

我们采用第二种方法。

排队算法:(1)入队(2)出列

队列的具体应用:

所有与时间有关的操作都与队列有关。

比如任务的等待队列，执行的优先级。

主题:递归

定义:

函数直接或间接地调用自己。

递归满足三个条件:

(1)递归必须有明确的终止条件。

(2)该函数处理的数据规模必须递减。

(3)这个变换一定是可解的。

和递归。

理论上，所有的循环都可以转化为递归。

可以递归实现的，不一定循环实现。

递归的特征:

(1)易于理解

(2)速度慢。

(3)储物空房间大。

周期的特征:

(1)不容易理解

(2)速度快。

(3)储物空房间小。

递归的应用

(1)树和森林以递归方式定义，

(2)树和图的大多数算法都是通过递归实现的。

(3)许多数学公式是递归定义的。

例如，佩波纳奇数列1 1 2 3 5 8 13 21

1: 1+2+3+的总和…+100

2.寻找阶乘

3:河内塔

4:走迷宫。

为什么玩游戏的时候能找到你？为什么我不能走在边缘？

将整个地图分成微小的网格。只要一个一个地穿过格子直到你找到它。

访问，(可以同时设置优先级，比如左右方向优先)，

堆栈和递归知识。

模块二:非线性结构(非线性算法复杂，理论不如线性结构成熟)

树

树的定义:

对于每个节点，根向下指向多个节点(具有层次关系)。

专业定义:

(1)只有一个节点叫做根。

(2)有几棵不相交的子树，它们本身就是一棵树。

流行定义:

(1)树由节点和边组成(边是指针字段)

(2)每个节点只有一个父节点，但可以有多个子节点。

(3)除了一个节点，它没有父节点，称为根节点。

技术术语:

节点父节点(注意父节点只有一个，不能跨越)

一个节点的子代(父节点下的所有子代都可以跨越)表兄弟(不能让父节点成为兄弟)。

深度:从根节点到最低节点的成熟度称为深度。

根是第一级。

叶节点:没有子节点的节点。

非末端节点:它实际上是非叶节点。

程度:

拥有最大子节点的数称为度。

树木的分类:

通用树

任何节点的子节点数量都是无限的。

二叉树

任何节点的子节点数最多为2，子节点的位置

无法改变。

二叉树的分类:

(1)一般二叉树

(2)完全二叉树

在不增加一个树级的前提下，不能再增加一个。

节点的二叉树是完全二叉树。

(3)完整的二叉树(二叉树是为后面的存储结构定义的)

如果只删除了完整二叉树的最低和最右边的节点，

这样的二叉树就是完全二叉树。

完全二叉树是完全二叉树的特例。

森林

n棵不相交的树的集合。

树的存储:

二叉树存储

连续存储[完全二叉树]

找到一个节点的父节点和子节点非常快，判断有多少个子节点。

缺点:内存占用大

链式存储

每个节点分为三个块，左指针，有效数据，右指针((左指针，指向左边元素)(有效数据)(右节点，指向右节点))

通用树存储

(1)父母代表

创建一个双行数组，一行存储有效元素，另一行存储父节点的下表。

(2)儿童代表权

与双清除符号类似，另一行存储子节点。

(3)父母和子女的代表权

第3行，有效元素，存储在中间的父节点的索引，最右边链表形式的子节点。

(4)二叉树表示

将普通树转换成二叉树进行存储。

具体转换方法:

尽量确保任何节点的左指针都指向它的第一个子节点。

右边的指针字段指向它的兄弟节点。

只要满足这个条件，一棵普通的树就可以转化成二叉树。

由普通树转换而来的二叉树没有右子树。

森林储存

一般来说，一棵树必须转换成一个完整的二叉树来存储。(二叉树不是线性结构。存钱时，这是一个先来后到的问题。)

步骤:

(1)将一般树转换成完全二叉树(添加元素)

(2)删除右下方可以删除的节点，转换成完整的二叉树。

问题:保存节点的顺序是什么？非线性结构转化为线性结构。一阶遍历、中阶遍历和后续遍历

如果只保存有效节点的值，按照上面三种方法都找不到原来的二叉树。

所以必须以完整的二叉树结构存储。这样存储空太浪费了，但是有一个巨大的好处:

【教材p124】n个节点的完全二叉树的深度为([log(2)n]+1)。告诉我任何一个

节点的数量，你可以马上知道这个节点有几个子节点，父节点的数量。

树的操作:见示意图“森林转化为二叉树示意图”。JPG”。

先将森林存储为二叉树，再存储二叉树。

树的操作:(重点，其他太难，在这里考)

(1)遍历(按照访问根的顺序)

首先遍历(首先访问根节点)

首先访问根节点，然后是左边的节点，最后是右边的子树。

中间顺序遍历(访问中间的根节点)

以中间顺序遍历左侧子树

再次访问根节点。

以中间顺序遍历右边的子树

后续遍历(最后一次访问根节点)

中间顺序访问左子树

中序访问右子树

再次访问根节点。

(2)通过已知遍历找到二叉树

知道了第一个顺序和中间顺序或者中间顺序和后续顺序，我们就可以恢复原来的二叉树了。

但是，原始二叉树不能通过第一个序列和后续序列恢复。

换句话说:

只有通过首序和中序或者通过中序和后续才能唯一确定二叉树。

app应用

树是数据库中数据组织的一种数据组织形式。

操作系统的子-父进程之间的关系本身就是一棵树(Ctrl+alt+delete包含结束进程树(进程及其创建的子进程))

面向对象语言中类的集成关系

霍夫曼树:一个事物有n种可能值，不同值的可能性不同。最高效的编程方式是什么？

图(未提及)

模块3:搜索和排序

双向搜索

排序:

沸腾

插入

挑选

快速排序

合并分类

分类和搜索。

排序是搜索的前提。

排序是关键。

java容器和数据结构的知识

迭代器接口

地图

哈希表

再谈什么是数据结构？

数据结构研究是一门数据存储和数据操作的学问。

的数据存储分为两部分:

(1)数据存储

(2)个人关系的储存

从某种角度来说，数据存储的核心是个体关系的存储。

个人存储可以忽略不计。

再讨论一下什么是泛型。

相同的逻辑结构(如线性数组和链表，如图所示)

不管逻辑结构物理存储看起来像什么，

我们都可以用它做同样的事情。