【数据结构陈越版笔记】2.1 引子【第2章 数据结构实现基础】

2.1 引子

数据结构的处理方法是从具体应用中抽象出共性的数据组织与操作方法，进而采用某种具体的程序涉及语言实现相应的数据存储与操作。
【例】给日常处理的数据进行统计分析
类型名称：统计数据集
数据对象集：N个元素 { x 1 , x 2 , . . . , x N } \{x_{1},x_{2},...,x_{N}\} {x1​,x2​,...,xN​}的集合S
操作集：

1. ElementType Average(S, N)：求S中N个元素的平均数；
2. ElementType Max(S, N)：求S中N个元素的最大值；
3. ElementType Min(S, N)：求S中N个元素的最小值；
4. ElementType Median(S, N)：求S中N个元素的中位数，这里的中位数指的是如果将S中的元素按从小到大的顺序依次排列，处在中间位置（$\lceil \mathrm{N}/2\rceil$，大于等于N/2的最小整数）的那个元素。

（1）数据存储：对于上述问题，其数据对象是集合S，这也是最简单的一种数据组织方式。今后会有更复杂的组织方式如树和图等。
（2）操作实现：在确定数据的存储方式后，数据结构涉及的另一个问题是相关的操作（运算）如何实现。这些操作的实现需要利用程序涉及语言提供的另一个功能，即流程设计功能。在程序中，我们可以将程序的某个功能设计为函数，这一方面降低了程序设计的复杂性，另一方面也提高了程序设计的重用性。
【代码2.1】Average函数的实现

double Average(int S[], int N)
{
	int sum = 0;
	for(int i = 0; i < N; i++)
	{
		sum+=S[i];
	}
	return (double)((double)(Sum))/((double)(N));
}

这个代码简单，不给出运行结果了
而对于中位数Median(S, N)问题则相对比较复杂，设法用一个循环简单地实现，有两种基本的解决思路。
方法1：基于排序，首先将集合S（数组）中的元素从大到小排序，取第$\lceil \mathrm{N}/2\rceil$（大于等于N/2的最小整数）处的元素就是中位数。
方法2：基于问题分解，求集合中位数的问题实际上就是另一个问题的特殊情况，即求集合中的第K大数问题。当$K=\lceil \mathrm{N}/2\rceil$时，集合的第K大数就是中位数。这个问题当然也可以用排序解决，但还有另一种更巧妙的方法，基本思路是：用一个基准数e将集合S分解为不包含e在内的两个小集合$S_1$和$S_2$，其中$S_1$的任何元素均大于等于e，$S_2$的任何元素均小于e，记$|S|$代表集合S元素的个数，这样，如果$|S_1|\ge K$，则说明第K大数在$S_1$中；如果$|S_1|$恰好等于K-1，说明e是第K大数；否则第K大数在$S_2$中，并且是$S_2$中的第$K-|S_1|-1$大数。然后，可以用类似的思路继续在$S_1$或$S_2$中查找，详见【LeetCode215】数组中的第K个最大元素，最后令$K=N/2$即可