数据结构——概述

什么是数据结构?

我们在学习C语言的时候编写过一些程序,程序由两部分组成,第一是解决问题的办法,也就是算法,第二就是在解决问题的过程中会产生一定量的数据,这些数据元素之间的关系、数据怎样存储以及对数据的操作(增删改查)就构成了数据结构。

数据结构

数据

数据是一个类似集合的概念,数据有多个数据元素组成,数据元素则由数据项来进行描述,数据项是数据的最小单位。这里打个比方,比如所有人是数据,则每一个人都是数据元素,每个人可以用身高、体重、外貌等来描述,这则是数据项。在计算机系统中,数据已不是单纯的数值。

结构

结构是数据元素之间的关系和存储方式,数据间的关系叫做逻辑结构,存储方式叫存储结构。

逻辑结构(元素和元素之间的关系)

1.线性关系

数据元素之间是一对一的关系,一个数据元素只和另一个数据元素有关系,这对应了逻辑结构中的线性结构,比如线性表(顺序表、链表、栈、队列)。

2.层次关系

数据元素之间的关系是一对多,一个数据元素对应多个数据元素,这种关系在逻辑结构中叫树状结构,比如树、二叉树、平衡树。

3.网状关系

个元素之间关系错综复杂,互相有关联,形成多对多的局势,好像结成了一张网,在逻辑结构中称为图状结构。

存储结构(数据的逻辑结构在计算机中的具体实现)

1.顺序存储结构

顺序存储结构相当于C语言中的一维数组,数据存储在一段连续的内存空间

2.链式存储结构

和顺序存储结构相反,数据存储在内存中空间的不同位置,每一个数据元素包含数据域和指针域,数据域用来存放数据,指针域存放下一个数据元素的地址,这样就能通过地址把所有数据链接起来,所以叫链式存储。

3.索引存储结构

索引存储结构类似于手机电话簿,把同一姓氏的人的联系方式存放到一块,虽然这样便于数据的查找,但是对数据的操作工作量明显增大,因为不仅要对数据文件进行修改,还要对索引表进行修改。

4.散列存储结构

操作

对数据的操作即对数据的增删改查。

算法

上文提到过,算法就是解决问题的办法,算法和数据结构便构成了程序。算法的设计取决于逻辑结构,算法的实现则依赖于数据的存储结构。

算法的特性

算法的特性包括有穷性、确定性、无二义性、可行性、输入、输出,这些特性都见名知意。

如何判断一个算法的好坏?

判断一个算法的好坏可以从正确性、易读性、健壮性、高效性四个方面判断,其中健壮性是指算法的容错性,高效性就要从时间复杂度和空间复杂度两方面评价。

时间复杂度:

时间复杂度的计算公式为:T(n) = O(f(n)),其中f(n) 表示每行代码执行次数之和,比如有以下代码

for(i=0;i<n;i++)
for(j=0;j<=i;j++)
printf(“ok\n”)

其中可重复执行语句的次数f(n)=n^2/2+n/2,在时间复杂度的计算中只保留最高项,然后用最高项除以最高项的系数,即f(n)=n^2。所以,这里的时间复杂度可表示为T(n) = O(n^2)。

空间复杂度:

空间复杂度也就是占用空间大小,在有限的空间内做到更多的是自然是最好的,一般将算法的辅助空间作为衡量空间复杂度的标准。

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇