邓俊辉数据结构第一章:绪论笔记(未完待续)

本文主要是介绍邓俊辉数据结构第一章:绪论笔记(未完待续)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

第一章：绪论

计算机科学的学习重心是：具体地深入思考与分析获得对问题本质的透彻理解，按照长期积淀的框架与模式设计出符合问题内在规律的算法。选用、定制、改进足以支撑算法高效实现的数据结构，并在真实的应用环境中充分测试、调校和改进，构成了计算机高效求解实际问题的典型流程和不二法门。每一位有志于驾驭计算机的学生都应该从这些问题入手，不断学习、反复练习和勤于总结。

1.1 计算机与算法

计算机科学的核心在于研究计算方法的过程与规律，而不仅仅是计算机工具本身。因此，E.Dijkstra以及追随者们更倾斜于这样称呼：计算科学。

1.1.1 埃及人的绳索

问题1：过直线上一点作直线的垂线。方法如下：最后竖线和横线垂直。

问题2：三等分一条线段。如下：水平线段是要被等分的线段。

1.1.3起泡排序

待解决的问题：对n个元素进行升序排序。

算法基本思路：假设对arr[n]进行升序排序。

第一趟：对arr[i]与arr[i+1]，其中0 <= i <= n-2.如果arr[i] > arr[i+1]，那么交换arr[i]和arr[i+1]的值。第一趟结束后，数组的最后一个元素已经是最大的了。

第二趟：对arr[i]与arr[i+1]，其中 0 <= i <= n-3。如果arr[i] > arr[i+1]，那么交换arr[i]和arr[i+1]的值。第二趟结束后，数组的倒数第二个元素已经就位了。

以此类推....

共需要比较n-1趟，那么后n-1个元素都就位，整体也就排好序了。

void bubbleSort(int *arr,int n)
{int compareNum = n - 1;         int i,j;for(j = 1;j < n;j ++)             //共比较 n-1 趟{for(i = 0;i < compareNum; i ++)    //每趟比较compareNum个元素{if(arr[i] > arr[i + 1])swap(arr[i],arr[i+1]);      //c++ 标准库函数swap，作用是交换两个实参}	compareNum --;       //每趟比较的最后compareNum减一，因为下一趟比上一趟少比较一个元素}
}

1.1.4 算法

1.算法

算法：是指基于特定的计算模型，旨在解决某一信息处理问题而设计的一个指令序列。

算法必须具备的3个要素：
（1）输入输出：

输入：对待求解问题的特定实例的某种描述，统称为输入。

输出：经过计算和处理之后的信息即针对输入问题实例的答案。

（2）基本操作、确定性与可行性：

算法应该描述为由若干语义明确的基本操作组成的指令序列，且每个基本操作在对应的计算模型中均可兑现。

子算法：借助基本操作组合解决子问题的算法，即解决子问题的算法。

对现代计算机而言，一个算法满足确定性与可行性仅当可以通过程序设计语言精确地描述。

(3)有穷性与正确性
任意算法都应该在执行有限次基本操作之后终止并给出输出。此即算法的有穷性（finiteness）。

输出就应该符合问题本身实现确定的条件——正确性。