数据结构浙大陈姥姥版第一章

迷南。 2023-06-29 05:46 83阅读 0赞

### 文章目录 ###

*  1. 引子
 *   *  //例1
     *  //例2.
     *  //例3.
     *  计算时间
 *  2.数据结构
 *   *  什么是数据结构
     *  抽象数据类型(Abstract Data Type)
     *  例4
 *  3. 算法
 *   *  定义
     *  什么是好的算法
     *  复杂度的渐近表示法
     *  求最大子列和

# 1. 引子 #

## //例1 ##

如何在书架上摆放图书

两个相关操作：

*  新书怎么插入
 *  怎么找到某本指定的书

一. 随便放

a. 哪里有空放哪哪里

b. 查找很麻烦

二. 按照书名的拼音字母顺序放

a. 比如插入《阿Q正传》，书整体需要往前或者往后位移，很类

b. 二分查找

三. 把书架划分为几块区域，每块区域指定摆放某种图书；在每种类别里 面按照书的拼音顺序排放

a. 先定类别，二分查找到确定位置，移动空出位置插入

b. 先定类别，再二分查找

**解决问题方法的效率和数据的组织方式有关**

## //例2. ##

写程序实现一个函数PrintN，使得传入一个正整数为N的参数后，能顺序打印1到N的全部整数

//代码1.1 用C语言循环实现PrintN函数
    void PrintN(int N)
    { 
    	int i ;
        for(i = 0; i < N; i++)
        { 
    		printf("%d \n",i);
        }
    }
    
    
    
    //代码1.2 递归调用
    void PrintN(int N)
    { 
        if(N)
        { 
            PrintN(N-1);
            printf("%d\n",N);
        }
    }
    
    //代码1.3 PrintN测试程序
    int main()
    { 
        int N;
        printf("输入N："); scanf("%d",N);
        PrintN(N);
        
        return 0;
    }

递归的函数对空间的占用很大，会发生非正常终止；

**解决问题方法的效率跟空间的利用效率有关。**

## //例3. ##

计算给定多项式在给定点x处的值

//代码1.4 计算多项式的值的直接法
    double f(int n, double a[], double x)
    { 
    	int i ;
    	double p = a[0];
    	for(i = 1; i <= n; i++)
    		p += (a[i] * pow(x, i));
    	
    	return p;
    }
    
    //代码1.5 秦九韶法
    double f(int n; double a[], double x)
    { 
        int i;
        double p = a[n];
        for(i = n, i > 0; i ++)
            p += a[n - 1] + x * p[n];
    	
        return p;
    }

## 计算时间 ##

**time.h**

**clock()**： 捕捉从程序运行到clock()被调用所耗费时间 ；这里的所耗费时间单位是clock\_tick；时钟一共打的点数ticks

常量**CLK\_TCK** ：时钟每秒的打点数

计算时间：

`durations = (start - stop) / CLK_TCK`

//代码1.6 时间测试函数 clock()
    //计算程序运行时间
    #include <stdio.h>
    #include <time.h>
    
    int main()
    { 
    	time_t start, stop;
        //不在测试范围内的准备工作写在clock()调用之前
    	start = clock();//程序一开始到这里运行的打点数
    	MyFunction();//被测函数
    	stop = clock();//程序一开始到这里运行的打点数
    	duration = (double)(stop - start) / CLK_TCK;//总的打点数除以计算机每秒的打点数，得出程序运行时间
    	return 0;
    }

//代码1.7 计算给定多项式的值
    //直接法
    double f1(int n, double a[], double x)
    { 
        int i ;
       	double p = a[0];
        for(i = 1; i < n; i++)
            p += a[i] * pow(x, i);
    	return p;
    }
    //秦九韶
    double f2(int n, double a[], double x)
    { 
        int i;
        double p = a[n];
        for(i = n ; i > 0; i--)
            p += a[i - 1] + p * x;
        return p;
    }
    
    
    //
    #include<stdio.h>
    #include<time.h>
    #include<math.h>
    clock_t start, stop;
    double duration;
    #define MAX 10//系数
    double f1(int n, double a[], double x);
    double f2(int n, double a[], double x);
    
    int main()
    { 
        int i;
        double a[MAX];//多项式的系数
        int tickN;
        for(i = 0; i < MAX; i ++)
            a[i] = i;
        
        //第一个函数运行时间
        start = clock();
        f1(MAX, a, 1.1);
        stop = clock();
        tickN = stop - start;
        duration = (double)tickN / CLK_TCK;
        printf("ticks number is: %d\n",tickN);
        printf("duration is: %f\n", duration);
        //重复多次运行
        /* start = clock(); for(i = 0; i < MAXKl; i++) { f1(MAX, a, 1.1); } stop = clock(); //平均每次时间 duration = (double)tickN / CLK_TCK / MAXK; */
        //第二个函数运行时间
        start = clock();
        f2(MAX, a, 1.1);
        stop = clock();
        tickN = stop - start;
        duration = (double)tickN / CLK_TCK;
        printf("ticks number is: %d\n",tickN);
        printf("duration is: %f\n", duration);
        
        return 0;
        
    }

函数跑的太快 运行的时间都不到一个tick

解决办法：让被测函数运行充分多次，使得测出的时钟打点次数充分多，最后计算每次被测函数的平均运行的时间即可

**解决问题方法的效率和算法的巧妙程度有关**

# 2.数据结构 #

## 什么是数据结构 ##

## 抽象数据类型(Abstract Data Type) ##

抽象：描述数据类型的方法不依赖具体实现

1. 与存放数据的机器无关
    2. 与数据存储的物理结构无关
    3. 与实现操作的算法和编程语言无关

数据类型

1. 数据对象集
    2. 数据集合相关联的**操作集**

## 例4 ##

矩阵的抽象数据类型定义

类型名称：矩阵(Matrix)

数据对象集：(a, i, j)

操作集：…

# 3. 算法 #

## 定义 ##

算法：algorithm

1.  一个有限指令集
2.  接收一些输入（有些情况不需要输入）
3.  产生输出
4.  一定在有限步骤后终止

//代码1.8
    //选择排序算法的伪码描述
    
    void SelectionSort(int List[], int N)
    { 
        for(i = 0; i < N; i++){ 
            /*从List[i]到List[N - 1]中找到最小元素，并将其位置赋给MinPosition*/
            MinPosition = ScanForMin(List, i, N - 1);
            /*将未排序部分的最小元素换到排序好的最后位置*/
    		Swap(List[i], List[MinPosition]);
        }
    }

## 什么是好的算法 ##

衡量指标:

空间复杂度S(n): 根据算法写成的程序在运行时所占用的存储单元的长度。这个长度往往跟输入的数据规模有关。空间复杂度过高的算法可能导致程序在运行内存超限，造成非正常中断（递归法PrintN)

时间复杂度T(n): 根据算法写成的程序在运行时耗费时间的长度。

分析算法效率时，一般关注以下两种复杂度

*  最坏情况复杂度 T w o r s t ( n ) T\_worst(n) Tworst(n)
 *  平均复杂度 T a v g ( n ) T\_avg(n) Tavg(n)

## 复杂度的渐近表示法 ##

上界 最小的上界

下界 最大的下界

## 求最大子列和 ##

算法1

int MaxSubseqSum1(int A[], int N)
    { 
    	int ThisSum, MaxSum = 0;
    	int i, j, k;
    	for(i = 0; i < N; i++)//序列左端位置
    	{ 
    		for(j = i ; j < N; j++)//序列右端位置
    		{ 
    			ThisSum = 0;//ThisSum是A[i]到A[j]的子列和
    			for(k = i; k < j; k++)
    			{ 
                    if(ThisSum > MaxSum)//如果这个子序列的和更大
    				 	MaxSum = ThisSum;//则更新结果
    			}
    		}
    	}
    	return MaxSum;
    }

复杂度：

T(N) = O(N^3)

算法2

int MaxSubseqSum2(int A[], int N)
    { 
    	int i, j, k;
    	int ThisSum; MaxSum = 0;
    	for(i = 0; i < N; i ++)
    	{ 
    		ThisSum = 0;//是A[i]到A[j]的子列和
    		for(j = i; j < N; j ++)
    		{ 
    			ThisSum += A[j];
                if(ThisSum > MaxSum)//如果刚得到的子列和更大
                    MaxSum = ThisSum;//则更新结果
    		}
    	}
        return MaxSum;
    }

复杂度：

T(N) = O(N^2)

算法3： 分而治之

算法4： 在线处理

int MaxSubseqSum4(int A[], int N)
    { 
    	int i;
    	int ThisSum, MaxSum;
    	ThisSum = MaxSum = 0;
    	for(i = 0; i < N; i ++)
    	{ 
    		ThisSum += A[i];
    		if(ThisSum > MaxSum)
    			MaxSum = ThisSum;
    		else if(ThisSum < 0)//如果当前子列和为负
    			ThisSum = 0;//则不可能使后面的部分和增大，抛弃
    	}
    	return MaxSum;
    }