数据结构-结构类型

从事计算机，想要深入学习，不得不涉及到数据结构，重拾起大学时代的这门课程，话说也只是刚刚毕业两个月，但此时的学习完全靠自觉了。

数据结构是一门讨论“描述现实世界实体的数学模型（非数值计算）及其上的操作在计算机中如何表示和实现”的学科。也就是说，数据结构就是按照逻辑关系组织起来的一批数据，此处的数据定义为一个运算的集合，是按一定存储方式将其存在计算机中，而结构就是实体+关系。计算机应用系统中的两个关键问题，

（1）表示：对象及其关系在计算机中的表示。只有对象及其相互关系以存储在计算机中，才能被进一步处理。

（2）操作：对对象进行处理、访问。

数据结构中的基础概念

1、数据：数据是描述客观事物的数值、字符以及能输入机器且能够被处理的各种符号集合。其中包括整型、实型、布尔型、图像、字符、声音、一切可能输到计算机中的符号集合。

2、数据元素：组成数据的基本单位，是数据集合的个体。在计算机中作为一个整体进行考虑处理。通常用“结点”来表示。

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

4、数据结构（书面定义）：指相互之间存在一种或多种特定关系的数据元素集合，是带有结构的数据元素的集合。它指的是数据元素之间的相互关系，即数据的组织元素。换言之，按某种逻辑关系组织起来的一批数据，按一定的映像方式把它存放在计算机存储器中，并在这些数据上定义了一个运算集合，这就叫做数据结构。其中，运算集合：增删改查。

5、数据类型（Date Type）:数据类型是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称。

6、原子类型：其值不可分解。如C语言中的标准类型（指针类型）。

7、结构类型：其值是由若干成分按某种结构组成的。

8、抽象数据类型（Abstract Data Type）：值基于一类逻辑关系的数据类型以及定义在这个类型之上的一组操作。它确定了一个模型，但将模型的实现细节隐藏起来，并定义了一组运算，也将运算的实现过程隐藏起来。

（1）抽象数据类型三要素：数据对象、元素关系、元素集合。一经定义可多次使用。

（2）ADT两个特征，

数据抽象：用ADT描述程序处理的实体时，强调其本质的特征，它所能完成的功能以及它和外部用户的接口。（即外界使用它的方法）

数据封装：将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。

9、数据结构中存在着逻辑结构和存储结构。逻辑结构指的是数据元素之间逻辑关系的描述。其形式化描述：Data_Structure=(D,R)，D指的是数据元素的有限集，R指的是D上关系的有限集。四类基本的结构：集合结构、线性结构、数、图。

集合结构：结构中的数据元素之间除了同属于一个集合的关系外，无任何关系。

线性结构：结构中的数据元素之间一对一的线性结构。

树型：结构中的数据元素之间一对多的层次关系。

图型：结构中的数据元素之间多对多的任意关系。

存储结构指的是逻辑结构在计算机中的存储映像，是逻辑结构在计算机中的实现，它包括数据元素的表示和关系的表示。其中，数据元素的表示：用若干二进制“位串”表示，数据元素的关系的表示：分为顺序映像和非顺序映像。

10、数据结构中不可避免的需要算法，算法的特性：有限性、正确性、输入、输出、可行性，正确性、可读性、健壮性、高效率和低存储量。

11、语句频度：该语句在一个算法中重复执行的次数。

 

例题：换硬币问题，编写程序用一元人名币换成一分、二分、五分的硬币共五十个。

分析：假设一分、二分、五分硬币各x、y、z枚，则有x+y+z=50，x+2y+5z=100

方法一：三重循环

#include<stdio.h>
main()
{
	int i,j,k;
	for(i=0;i<=50;i++)
		for(j=0;i<=50;j++)
		{
			for(k=0;k<=50;k++)
			{
				if(i+j+k==50&&i+2*j+5*K==100)
					printf("%d,%d,%d\n"i,j,k);
			}
		}
}	//循环次数51*51*51，时间复杂度O(n^3)

 

方法二：两重循环

5分硬币有总数减去1分2分的数量

#include<stdio.h>
main()
{
	int i,j,k;
	for(i=0;i<=50;i++)
		for(j=0;j<=50;j++)
		{
			k=50-i-j;
			if(i+2*j+5*k==100)
				printf("%d,%d,%d\n",i,j,k);
		}
}	//循环次数51*51，时间复杂度O(n^2)

 

方法三：单循环

简化方程组：y+4z=50,那么z的数量不超过13

#include<stdio.h>
main()
{
	int i,j,k;
	for(k=0;k<13;k++)
	{
		j=50-4*k;
		i=50-j-k;
		printf("%d,%d,%d\n",i,j,k);
	}
}	//循环次数13，时间复杂度O(1)

可得出结论：算法的设计至关重要！