【数据结构-C语言】绪论

一、前言

数据结构部分是根据严蔚敏老师的《数据结构-C语言版第2版》书中内容整理的。

二、基本概念和术语

2.1 数据元素、数据项和数据对象

数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。

数据元素：是数据的基本单位。也称为元素、记录等。数据元素用于完整的描述一个对象。

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

2.2 数据结构

数据结构：是相互之间存在一种或者多种特定关系的数据元素的集合。数据结构是带“结构”的数据元素的集合，结构就是指数据元素之间存在的关系。

2.2.1 逻辑结构

四类基本结构：集合结构（除了“属于同一集合”的关系外，无其他关系）、线性结构（一对一）、树形结构（一对多）、图形结构（多对多）。

线性结构：线性表、栈和队列（有特殊限制的线性表）、字符串、数组（线性表的推广）、广义表。

非线性表：树、二叉树、有向图、无向图。

2.2.2 存储结构

数据元素在计算机中有两种基本的存储结构，分别是顺序存储和链式存储。

顺序存储：借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。通常使用数组类型来描述。所有元素依次存放在一片连续的存储空间中。

链式存储：需要给每个节点附加指针字段，用于存放后续元素的存储地址。所以通常要借助于指针类型来描述。

2.3 时间复杂度

定理：在计算时间复杂度时，可以忽略所有低次幂项和最高次幂的系数，这样可以简化算法分析，也体现出了增长率的含义。

一般都是用最坏时间复杂度来计算。

void Func1(int N)
{
	int count = 0;
	for (int i = 0; i < N; ++i)    // 第一段
	{
		for (int j = 0; j < N; ++j)
		{
			++count;
		}
	}
	for (int k = 0; k < 2 * N; ++k)   // 第二段
	{
		++count;
	}
	int M = 10;
	while (M--)       // 第三段
	{
		++count;
	}
	printf("%d\n", count);
}

最坏情况：F(N) = N² + 2 * N + 10，此时，我们要忽略低次幂项和常数以及最高次幂的系数这样就得到了N²，所以Func1的时间复杂度为：O(N²)。