数据结构初认识

el/2024/4/13 14:48:45

一、基本概念

数据 是对客观事物的符号表示,在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据的含义极为广泛,如图像、声音等都可以通过编码而归之于数据的范畴。

数据元素 是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。

数据项 一个元素可由若干个数据项组成。如:一本书的书目信息作为一个数据元素,那么书目信息的每一项(如:书名、作者名等)为一个数据项。数据项是数据不可分割的最小单位。

数据对象 是性质相同的数据元素的集合,是数据的一个子集。

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

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

通常有四类基本结构:

1>集合

2>线性结构

3>树形结构

4>图状结构或网状结构

数据结构的形式定义;数据结构是一个二元组

Data_Structure = (D,S)

D是数据元素的有限集,S是D上关系的有限集。

数据结构在计算机中的表示(又称映像)称为数据的物理结构,又称存储结构。它包括数据元素的表示和关系的表示。在计算机中表示信息的最小单位是二进制数的一位,叫做位(bit)。在计算机中,我们可以用一个由若干位组合起来形成的一个位串表示一个数据元素(如用一个字长的位串表示一个整数,用8位二进制数表示一个字符等),通常称这个位串为元素(element)或结点(node)。当数据元素由若干数据项组成时,位串中对应于各个数据项的子位串称为数据域(data field)。因此,元素或结点可看成是数据元素在计算机中的映像。

数据元素之间的关系在计算机中有两种不同的表示方法:顺序映像和非顺序映像,并由此得到两种不同的存储结构:顺序存储结构和链式存储结构。顺序映像的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。非顺序映像的特点是借助指示元素存储地址的指针( pointer)表示数据元素之间的逻辑关系。
 

 二、算法和算法设计

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

             5个重要基本特征:有穷性,确定性,可行性,输入,输出

好的算法设计要求:

正确性,可读性,健壮性,效率与低存储量需求。

2.算法效率的度量

一般情况下,算法中基本操作重复执行的次数是问题规模n的某函数f(n),算法的时间度量记作:

 T( n )=O( f ( n ) )

它随着问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称为算法的渐进时间复杂度,简称时间复杂度

显然,被称做问题的基本操作的原操作应是其重复执行次数和算法的执行时间成正比的原操作,多数情况下它是最深层循环内的语句中的原操作,它的执行次数和包含它的语句的频度相同。语句的频度(frequency count)指的是该语句重复执行的次数,例如,在下列3个程序段中:
(a){ ++ x;s = 0;}

(b) for (i= 1; i<=n; ++ i){++ x; s += x; }

(c) for (j=1, j<=n;++j)
        for (k= 1: k<= n; ++k){++ x;s += x;}
含基本操作“x增1”的语句的频度分别为1,n和n^2,则这3个程序段的时间复杂度分别为O(1),O(n)和O(n^2),分别称为常量阶,线性阶和平方阶。算法还可能呈现的时间复杂度有对数阶O(log n)、指数阶O(2^n)等。不同数量级时间复杂度的性状如图所示。从图中可见,我们应该尽可能选用多项式阶O(n^k)的算法,而不希望用指数阶的算法。

 由于算法的时间复杂度考虑的只是对于问题规模n的增长率,则在难以精确计算基本操作执行次数(或语句频度)的情况下,只需求出它关于n的增长率或阶即可。

经常遇到的时间复杂度
(1)O(1)没有循环,要么有循环,但是循环退出条件和问题规模之间没有关系——循环次数是一个常数
(2)O(n)有循环,并且循环的次数与问题规模之间没有关系(控制循环的变量每次+1或者-1来执行)
(3)O(n^2)循环嵌套
(4)O(logn)油循环,并且循环次数与问题规模之间有关系(控制循环的变量每次*2,或者/2来执行)
 

关于时间复杂度有两个省略规则:

1.我们只保留最高项

2.不要系数

类似于算法的时间复杂度,以空间复杂度(space complexity)作为算法所需存储空间的量度,记作
S(n)  = S( f ( n ) )
其中n为问题的规模(或大小)。一个上机执行的程序除了需要存储空间来寄存本身所用指令﹑常数、变量和输入数据外,也需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。若输入数据所占空间只取决于问题本身,和算法无关,则只需要分析除输入和程序之外的额外空间,否则应同时考虑输入本身所需空间(和输人数据的表示形式有关)。若额外空间相对于输入数据量来说是常数﹐则称此算法为原地工作,如果所占空间量依赖于特定的输人,则除特别指明外,均按最坏情况来分析。

数据结构和数据类型两个概念有区别吗:

数据结构定义了一组按某些关系结合在一起的数组元素。

数据类型不仅定义了一组带结构的数据元素,而且还在其上定义了操作。

八大排序算法:
1.冒泡排序(沉石排序)

2.二路归并排序

3.直接插入排序

4.希尔排序

5.堆排序

6.基数排序(桶排序)

7.快速排序

8.选择排序
 


http://www.ngui.cc/el/4994643.html

相关文章

Ubuntu 安装Tools

点击光盘&#xff0c;里面有个VMwareTools的文件&#xff0c;将文件拖入下载中 单击右键&#xff0c;选择在终端中打开 .pl可执行文件 安装软件需要切换到管理员权限 sudo su

类和对象的初始化(构造函数与析构函数)

有对象一定要有空间&#xff0c;有空间不一定有对象。 class Empty {}; int main() {Empty e;cout << sizeof(e) << endl;//1字节return 0; } 虽然此对象没任何属性和方法&#xff0c;但是要创建一个对象&#xff0c;就必须在地址空间标识此对象&#xff0c;就必…

共用数据的保护

C有不少措施保护数据的安全性,如private保护类的数据成员等。但对于一些共用的数据&#xff0c;如函数实参与形参等,我们可以在不同的场合通过不同的途径访问同一个数据对象。有时不经意的误操作会改变数据的值。 一、常对象 既要使数据能在函数间共享&#xff0c;又要保证它…

对象的动态建立和释放,赋值和复制

一、对象的动态建立和释放 利用new运算符可以动态地分配对象空间&#xff0c;delete运算符释放对象空间。 动态分配对象的一般形式: new 类名; 用new运算符动态分配得到的对象是无名的,它返回一个指向新对象的指针的值&#xff0c;即所分配的内存单元的起始地址。程序通过这…

文件查看命令和用户管理命令

文件查看命令 cat 1.用于查看文件数据 cat a.txt 2.合并文件 cat a.txt b.txt > c.txt 3.向文件中写入数据 cat > d.txt 这样写入数据有一点需要注意&#xff1a;cat > d.txt 输入数据时&#xff0c;会先将d.txt中的数据清空。 cat >> d.txt 向文件的末…

左值右值,柔性数组

一、右值、左值 在c中&#xff0c;左值就是可以被赋值的&#xff0c;右值就是不可被赋值的 在c11标准下: 所有的值必属于左值、右值两者之一。 右值分为纯右值和将亡值 在C11中可以取地址的、有名字的就是左值&#xff0c;反之&#xff0c;不能取地址的、没有名字的就是右值&a…

C++统一初始化和输入输出

一、c统一初始化 C语言中初始化一个量只有赋值语句这一种办法 c中初始化方式比较多 #include<iostream> using namespace std;int main() {int a 10;//c语言中初始化只有赋值语句这一种方法//以下都是c初始化的方法int b(10);//这样有点像对象初始化的形式int c{ 10 …

如何判断是以c++方式编译还是c方式编译

如何判断是以c方式编译还是c方式编译&#xff1f; 通过宏判断&#xff0c;c方式编译有宏 _cplusplus c中没有_cplusplus 在程序中可以利用开关语句&#xff08;探测宏&#xff09; #ifdef _cplusplusprintf("c"); #elseprintf("c"); #endif

关于log4j和slf4j的使用说明

1.log4j是日志类基础&#xff0c;slf4j需要依赖他&#xff0c;同时还需要一个log4j和slf4j的媒介来整合他们俩。简而言之&#xff0c;log4jslf4j&#xff08;slf4j--log4j&#xff09;三位一体才能爽歪歪&#xff01; 2.三者的版本如何搭配选择&#xff1f;答案是&#xff0c;…

通过jug 2.0.jar的成功下载的猜想

1.maven的配置为以下方式时&#xff0c;下载出错 <dependency> <groupId>org.safehaus.jug</groupId> <artifactId>jug</artifactId> <version>2.0.0</version> </dependency> 2.maven以以下配置时&#…