数据结构学习笔记--基础概念

Updated on with 0 views and 0 comments

一、简介

1.1 概念

先知悉以下术语概念

  • 数据 --对客观事物的符号表示,再计算机科学中是指所有能输入到计算机中并被处理的符号的总称
  • 数据元素 --数据的基本单位
  • 数据项 --数据的不可分割的最小的单位
  • 数据对象 --性质相同的数据元素的集合
  • 数据结构 --相互之间存在一种或多种特定关系的数据元素的集合

以一个学生管理系统为例说明上述概念对应的具体项

数据 --学生信息管理系统中存储的所有关于学生的信息构成了数据;

数据元素 --每一个学生的全部信息就是一个数据元素,例如:

学号:2020001
姓名:张三
性别:男
年龄:20
专业:计算机科学与技术
入学年份:2020
联系电话:13812345678
邮箱:zhangsan@example.com

数据项 --在上面的数据元素中,

  • 学号:2020001
  • 姓名:张三
  • 性别:男
  • 年龄:20
  • 专业:计算机科学与技术
  • 入学年份:2020
  • 联系电话:13812345678
  • 邮箱:zhangsan@example.com

每个数据项分别描述了学生的某个具体属性

数据对象 --所有性别相同的学生构成一个数据对象,也可以时所有年龄或者专业相同的学生也可以构成一个数据对象

1.2 数据结构的分类

数据结构按照逻辑结构分为以下几类

  • 集合 --结构中的元素除了同属于一个集合的关系外,没有其他关系
  • 线性结构 --结构中的数据元素之间存在1对1的关系
  • 树形结构 --结构中的元素之间存在1对多的关系
  • 图形结构或网状结构 --结构中的元素之间存在多对多的关系

数据结构按存储结构分为以下几类

  • 链式存储 --存储空间在内存中跳跃
  • 顺序存储 --存储空间在内存中连续
  • 索引存储 --以散列形式存储数据

二、算法和算法分析

2.1 算法

算法是对特定问题求解步骤的一种描述,他的指令是有序序列,一条指令代表一个多多个操作,算法具有以下5个特性

  • 有穷性 算法在执行有穷步之后结束,每一步都在有穷时间内完成
  • 确定性 对于相同的输入,只能得到相同的输出
  • 可行性 算法中描述的操作都是通过已经实现的基本运算来实现有限次来实现的
  • 输入 一个算法可以有0个或者多个输入
  • 输出 一个算法可以有1个或多个输出

2.2 算法的设计要求

  • 正确性 --算法应满足具体问题的需求
  • 可读性 --便于人理解
  • 健壮性 --输入非法数据时,算法也能适当做出反应或进行处理,而不会产生莫名的输出结果
  • 效率与低存储量需求 --效率值算法执行时间,存储需求指的是算法在运行过程中需要的最大存储空间

2.3 算法效率的度量

从算法中选取一种基本操作,以该基本操作的重复执行的次数作为算法的时间度量

例如,在一个N X N的矩阵相乘的算法中,"乘法"运算是"矩阵相乘问题"的基本操作,整个算法的执行时间与该基本操作的重复次数n3成正比,记作T(n)=O(n3)

#include<stdio.h>

int main() {
	int a[3][3] = {
		{1,1,1},
		{1,1,1},
		{1,1,1}
	};
	int b[3][3] = {
		{1,1,1},
		{1,1,1},
		{1,1,1}
	}; 
	int i, j, k;
	int c[3][3];
	for (i = 0; i < 3; i++) {
		for (j = 0; j < 3; j++) {
			c[i][j] = 0;
			for (k = 0; k < 3; k++) {
				c[i][j] += a[i][k] * b[k][j];
			}
			printf("%d ", c[i][j]);
		}
		printf("\n ");
	}
	return 0;
}

一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数f(n),算法时间度量计做T(n)=O(f(n)),他表示随着问题规模n的增长,算法执行时间增长率和f(n)的增长率相同,称作算法的渐进时间复杂度,简称时间复杂度

d8baf40b1406403613299a32d1c5bbd.png

常见的函数增长率

2.4 算法的空间需求

以空间复杂多作为算法所需存储空间的度量,记作S(n) = O(f(n)) 其中n为问题规模,程序除了需要存储空间来寄存本身所用指令、常数、变量和输入数据外,也需要一些对数据进行操作的工作单元和存储一些为实现计算所需的辅助存储空间。


标题:数据结构学习笔记--基础概念
作者:wenyl
地址:http://www.wenyoulong.com/articles/2024/04/24/1713936857669.html