数据结构与算法_数据的表示

阳光穿透心脏的1/2处 2021-12-11 02:09 275阅读 0赞

**数据 – 程序的操作对象，用于描述客观事物 int a ,int b**  
**数据的特点：  
可以输入到计算机  
可以被计算机程序处理**  
**数据是一个抽象的概念，将其进行分类后得到程序设计语言中的类型。如：int，float，char等等**  
**数据元素：组成数据的基本单位 array\[1\],array\[2\],这就是数据元素。**  
**数据项：一个数据元素由若干数据项组成**  
**数据对象 – 性质相同的数据元素的集合**

## 数据的基本概念及研究意义 ##

**数据是一个抽象的概念，将其进行分类后得到程序设计语言中的类型。如：int，float，char等等**  
**数据元素：组成数据的基本单位 array\[1\],array\[2\],这就是数据元素。**  
**数据项：一个数据元素由若干数据项组成**  
**数据对象 – 性质相同的数据元素的集合**  
下图是把数据结构的基本概念用一个图的关系进行了讲解，请看下图。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkxNjc1NQ_size_16_color_FFFFFF_t_70]

## 数据结构的逻辑关系 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkxNjc1NQ_size_16_color_FFFFFF_t_70 1]  
数据之间有四种关系，集合、线性、树形和图行。

## 数据的存储结构 ##

**顺序、链式、索引和散列**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkxNjc1NQ_size_16_color_FFFFFF_t_70 2]

## 算法 ##

**算法是特定问题求解步骤的描述**  
**在计算机中表现为指令的有限序列**  
**算法是独立存在的一种解决问题的方法和思想**  
**对于算法而言，语言并不重要，重要的是思想**  
**算法和数据结构区别**  
数据结构只是静态的描述了数据元素之间的关系  
高效的程序需要在数据结构的基础上设计和选择算法  
程序=数据结构+算法

## 大O表示法 ##

**理论依据：**  
**//算法最终要编译成计算机指令。  
//每一个指令在具体的计算机上运行的时间是固定的。  
//通过具体的N的步骤就可以推到出算法的时间复杂度。  
//大O表示方法的推倒,**  
下面的代码是大O表示法在程序中的推倒过程。

long sum1(int n)     // 2*n+3   O(n)
    {
    	long ret = 0;                               // 1
    	int* array = (int*)malloc(n * sizeof(int)); //1
    	int i = 0;                    //1
    	for (i = 0; i < n; i++)//n
    	{
    		array[i] = i + 1;
    	}
    	for (i = 0; i < n; i++)//n  
    	{
    		ret += array[i];
    	}
    	free(array);//1
    	return ret;
    }
    long sum2(int n)// n+2   O(n)
    {
    	long ret = 0;
    	int i = 0;
    	for (i = 1; i <= n; i++)
    	{
    		ret += i;
    	}
    	return ret;
    }
    
    long sum3(int n)   // 2次     O(1)
    {
    	long ret = 0;
    	if (n > 0)
    	{
    		ret = (1 + n) * n / 2;
    	}
        	return ret;
    }

**程序分析，sum1执行了 2\*n+3 次，sum2执行了n+2次，sum3执行了 // 2次。  
所以sum1和sum2的时间复杂度是O(n)，sum3的时间复杂度是O(1)**  
**注意：**  
注意1：判断一个算法的效率时，往往只需要关注操作数量的最高次项，其它次要项和常数项可以忽略。  
注意2：在没有特殊说明时，我们所分析的算法的时间复杂度都是指最坏时间复杂度。  
**大O表示法：**  
算法效率严重依赖于操作(Operation)数量  
在判断时首先关注操作数量的**最高次项**  
操作数量的估算可以作为**时间复杂度的估算**  
**O(5) = O(1)  
O(2n + 1) = O(2n) = O(n)  
O(n2+ n + 1) = O(n2)  
O(3n3+1) = O(3n3) = O(n3)**  
常见时间复杂度  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkxNjc1NQ_size_16_color_FFFFFF_t_70 3]  
**关系**  
![在这里插入图片描述][20190712141925578.png]

## **算法的空间复杂度** ##

**算法的空间复杂度通过计算算法的存储空间实现**  
S(n) = O(f(n))  
其中，n为问题规模，f(n))为在问题规模为nn时所占用存储空间的函数  
大O表示法同样适用于算法的空间复杂度  
当算法执行时所需要的空间是常数时，空间复杂度为O(1)  
空间与时间的策略  
多数情况下，算法执行时所用的时间更令人关注  
如果有必要，可以通过增加空间复杂度来降低时间复杂度  
同理，也可以通过增加时间复杂度来降低空间复杂度。

## 空间换时间 ##

**把中间的运算结果缓存下来，这样的思想就是典型的控件换时间**  
算法思路如下：  
![在这里插入图片描述][20190713152621853.png]

void search(int a[], int len)
    {
    	int sp[1000] = { 0 };// 全部赋值0；
    	int max = 0;
    	for (int i = 0; i < len; i++) //利用数组元素和数组下标之间的关系
    	{
    		int index = a[i] - 1;
    		sp[index]++;
    	}
    	for (int i = 0; i < 1000; i++)  //找到数组出现最多的一个数字，存到max中，
    	{
    		if (max < sp[i])
    		{
    			max = sp[i];
    			cout << "出现最多的次数是:"<<max << endl;
    		}
    	}
    	for (int i = 0; i < 1000; i++)
    	{
    		if (max == sp[i])
    		{
    			printf("%d\n", i + 1);
    		}
    	}
    
    }
    
    int main()
    {
    	int array[] = { 1,3, 1, 3, 4, 5, 100, 6, 6, 2, 3, 3, 3 };
    	//cout <<"数组的长度"<< sizeof(array) << endl;   //数组的长度是52.
    	//cout << "数组的类型" << sizeof(*array) << endl;   //数组的长度是52.
    	int len = sizeof(array) / sizeof(*array);
    	search(array, len);
    	system("pause");
    	return 1;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkxNjc1NQ_size_16_color_FFFFFF_t_70]: /images/20211210/d119fad7cc954f79be46313befc703e8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkxNjc1NQ_size_16_color_FFFFFF_t_70 1]: /images/20211210/d58d36061afc490784f9bf77ec96ef5c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkxNjc1NQ_size_16_color_FFFFFF_t_70 2]: /images/20211210/86f37e45efd3483aad5d435755b5c5d1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkxNjc1NQ_size_16_color_FFFFFF_t_70 3]: /images/20211210/e4c67a3b88724543b590d0fa3d9de94c.png
[20190712141925578.png]: /images/20211210/e9b88d6097cb401caadcaf44976b7965.png
[20190713152621853.png]: /images/20211210/a62863bc0c4649ed909a8ba8162b4a15.png