数据结构与算法基础笔记CPP代码(排序未写完)
基本概念和术语[*]数据
[*]是能输入计算机且能被计算机处理的各种符号的集合
[*]信息的载体
[*]是对客观事物符号化的表示
[*]能够被计算机识别、存储和加工
包括数值数据和非数值数据
[*]数据元素是组成数据的基本单位
[*]也简称为元素，或称为记录、结点或顶点
[*]数据项是构成数据元素的不可分割的最小单位
[*]数据对象是性质相同的数据元素的集合
[*]数据结构
[*]数据元素之间的关系就是结构
[*]数据结构就是指相互之间存在一种或多种特定关系的数据元素集合
[*]数据结构包括以下三个方面的内容
[*]数据元素之间的逻辑关系，也称为逻辑结构
[*]数据元素及其关系在计算机内存中的表示（又称为映像），称为数据的物理结构或数据的存储结构
[*]数据的运算和实现，即对数据元素可以施加的操作以及这些操作在相应的存储结构上的实现
[*]逻辑结构
是描述数据元素之间的逻辑关系，与数据的存储无关，独立于计算机，是从具体问题抽象出来的数学模型
[*]物理结构 （存储结构）
数据元素及其关系在计算机存储器中的结构（存储方式）
是数据结构在计算机中的表示
逻辑结构是数据结构的抽象，存储结构是数据结构的实现
四种基本逻辑结构：
[*]集合结构：结构中的数据元素之间除了同属于一个集合的关系外，无任何其它关系
[*]线性结构：结构中的数据元素之间存在着一对一的线性关系
[*]树形结构：结构中的数据元素之间存在着一对多的层次关系
[*]图状结构或网状结构：结构中的数据元素之间存在着多对多的任意关系
四种基本存储结构：
[*]顺序存储结构
用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示
C语言中用数组来实现顺序存储结构
[*]链式存储结构
用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示
C语言中用指针来实现链式存储结构
[*]索引存储结构
[*]在存储结点信息的同时，还建立附加的索引表
[*]索引表中每一项就是一个索引项
[*]索引项的一般形式是：（关键字，地址）
[*]关键字是能唯一标识一个结点的那些数据项
[*]若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引（Dense Index），若一组结点在索引表中只对应一个索引项，则该索引表称之为稀疏索引（Sparse Index）
比如手机通讯录列表
[*]散列存储结构
根据节点的关键字直接计算该节点的存储位置
数据类型和抽象数据类型
一些最基本数据结构可以用数据类型来实现，如数组、字符串等；而另一些常用的数据结构，如栈、队列、树、图等，不能直接用数据类型来表示
[*]数据类型的作用
[*]约束变量或常量的取值范围
[*]约束变量或常量的操作
数据类型（Data Type）
定义：数据类型是一组性质相同的值的集合以及定义于这个值集合上的一组操作的总称
数据类型=值的集合+值集合上的一组操作
抽象数据类型（Abstract Data Type）是指一个数学模型以及定义在此数学模型上的一组操作
[*]由用户定义，从问题抽象出数据模型（逻辑结构）
[*]还包括定义在数据模型上的一组抽象运算（相关操作）
[*]不考虑计算机内的具体存储结构与运算的具体实现算法
一个抽象数据类型的定义格式如下：
ADT 抽象数据类型名
数据对象 <数据对象的定义>
数据关系 <数据关系的定义>
基本操作 <基本操作的定义>
ADT 抽象数据类型名数据对象、数据关系的定义用伪代码描述
基本操作的定义格式为：
基本操作名(参数表)
//赋值参数只为操作提供输入值
//引用参数除可提供输入值外，还将返回操作结果
初始条件: (初始条件描述)
//描述操作执行之前数据结构和参数应满足的条件
//若不满足初始条件，则操作失败，并返回相应出错信息
//若初始条件为空，则省略
操作结果:(操作结果描述)
//说明操作正常完成之后，数据结构的变化状况和应返回的结果算法
算法的定义
[*]对特定问题求解方法和步骤的一种描述，它是指令的有限序列。其中每个指令表示一个或多个操作
[*]简单说算法就是解决问题的方法和步骤
可以使用自然语言、流程图、伪代码和程序代码来描述算法
算法与程序
[*]算法是解决问题的一种方法或一个过程，考虑如何将输入转换成输出
一个问题可以有多种算法
[*]程序是用某种程序设计语言对算法的具体实现
[*]程序=数据结构+ 算法
[*]数据结构通过算法实现操作
[*]算法根据数据结构设计程序
算法特性
[*]有穷性
一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。
[*]确定性
算法中的每一条指令必须有确切的含义，没有二义性
在任何条件下，只有唯一的一条执行路径，即对于相同的输入只能得到相同的输出。
[*]可行性
算法是可执行的，算法描述的操作可以通过已经实现的基本操作执行有限次来实现.
[*]输入
一个算法有零个或多个输入
[*]输出
一个算法有一个或多个输出
算法设计要求
[*]正确性(Correctness)
指算法满足问题要求，能够正确解决问题
算法转化为程序要注意：
[*]算法程序没有语法错误
[*]算法程序对于合法的输出数据能够产生满足要求的输出结果
[*]算法程序对于非法的输入数据能够得出满足规格说明的结果
[*]算法程序对于精心选择的，甚至***难的测试数据都有满足要求的输出结果
通常以第三层意义上的正确性作为衡量一个算法是否合格的标准
[*]可读性(Readability)
[*]算法设计的主要目的是为了便于阅读、理解和交流，其次才是为计算机执行
[*]可读性高有助于理解算法，晦涩难懂的算法往往隐含错误，不易被发现且难以调试和修改
[*]健壮性(Robustness)
[*]当输入数据不合法时，算法也能做出相关处理，而不是产生异常或莫名其妙的结果
[*]处理出错的方法，不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理
[*]高效性(Efficiency)
时间效率尽量高，存储需求尽量少
[*]时间效率是算法的执行时间
[*]存储量需求是算法在执行过程中需要的最大存储空间
算法分析
在满足算法设计要求的前提下考虑算法的效率
算法效率通过两个方面考虑：
[*]时间效率：算法所耗费的执行时间
[*]空间效率：算法在执行过程中耗费的存储空间
算法时间效率的度量
[*]算法时间效率可以用依据该算法编制的程序在计算机上执行所消耗的时间来度量
[*]两种度量方法
[*]事后统计
[*]将算法实现，测算其时间和空间开销
[*]缺点：编写程序实现算法将花费较多的时间和精力；所得实验结果依赖于计算机的软硬件等环境因素，掩盖算法本身的优劣
[*]事前分析
对算法所消耗资源的一种估算方法
算法运行时间=一个简单操作所需时间*简单操作次数
也就是算法中每条语句的执行时间之和
算法运行时间=每条语句的执行次数*该语句执行一次所需的时间
语句的执行次数也称为语句频度
算法运行时间=每条语句频度*该语句执行一次所需的时间
每条语句执行一次所需的时间，取决于不同机器的指令性能、速度以及编译的代码质量。是由机器本身软硬件环境决定的
所以，我们可假设执行每条语句所需的时间均为单位时间
此时对算法运行时间的讨论就可转化为讨论该算法中所有语句的执行次数，即频度之和
这样就可以独立于不同机器的软硬件环境来分析算法的时间性能
例如两个n*n矩阵相乘的算法：
for (i = 1; i <= n; i++)//n+1次，判断是否满足条件也是一次执行
for (j = 1; j <= n; j++) {//n(n+1)次
c = 0;//n*n次
//外层循环执行1次，内层循环就会执行n次
for (k = 0; k < n; k++) //n*n*(n+1)次
c = c + a * b;//n*n*n次
}双向链表
结点有两个指针域的链表，称为双向链表
在单链表的基础上，对于每一个结点设计一个前驱结点，前驱结点与前一个结点相互连接，构成一个链表
#include using namespace std;template class doubleLinkedList;//声明一下双向链表，以免定义友元时报错template class doubleLinkedListNode{ private: //双向结点前驱指针指向该结点的前驱结点 doubleLinkedListNode *prior; //储存结点数据 T data; //双向结点的后驱指针指向该结点的后继结点 doubleLinkedListNode *next; //将双向链表类定义为结点的友元类 friendclass doubleLinkedList; public: //结点的无参构造函数,将结点指针域初始化为NULL doubleLinkedListNode() { prior = NULL; next = NULL; } //结点的有参构造函数，初始化指针域和数据域 doubleLinkedListNode(T _data,doubleLinkedListNode *_prior = NULL,doubleLinkedListNode *_next = NULL) { prior = _prior;//初始化前驱指针 data = _data;//初始化数据域 next = _next;//初始化后继指针 } ~doubleLinkedListNode() { prior = NULL; next = NULL; }};template class doubleLinkedList{ private: doubleLinkedListNode *head;//双向链表的头指针 int length;//双向链表的长度 public: //双向链表的构造函数，链表产生新头结点 doubleLinkedList() { head = new doubleLinkedListNode();//链表产生新头结点 length = 0; } //双向链表的构造函数，链表产生新头结点 doubleLinkedList(doubleLinkedListNode *note) { head = note; length = 0; } //双向链表的析构函数，链表删除头节点 ~doubleLinkedList() { delete head; } //双链表插入结点----头插法 bool insertNodeByhead(T item); //双向链表插入结点----尾插法 bool insertNodeBytail(T item); //在第i个结点插入T类型item bool insertNode(T item,int n); //寻找给定数值的结点 bool findData(T item); //删除第i个结点的数据 bool deleteData(int n); //获取双向链表长度 int getLength(); //修改指定位置元素，被修改元素以引用返回 bool changeListElements(int n,T item,T &x); //打印双向链表 void printLinkedlist();};templateint doubleLinkedList::getLength(){ doubleLinkedListNode *pMove = head->next;//设置游标指针 int length=0; //遍历链表，计算结点数 while(pMove!=NULL) { pMove = pMove->next;//游标指针后移 length++; //计算length } return length;}templatebool doubleLinkedList::insertNode(T item,int n){ if(nprior = newNode; newNode->prior = head; head->next = newNode; return true; }}templatebool doubleLinkedList::insertNodeBytail(T item){ //创建一个新的结点 doubleLinkedListNode* newNode = new doubleLinkedListNode(item); if (newNode == NULL){ cout next;//没找到就一直循环 } //找到调整指针 lastNode->next = newNode; newNode->prior = lastNode; return true;}templatevoid doubleLinkedList::printLinkedlist(){ //从第二个结点开始打印，表头不含数据 doubleLinkedListNode* pMove = head->next; while(pMove) { coutnext; pMove->next->prior = pDelete->prior; delete pDelete;//释放空间 return true;}templatebool doubleLinkedList::changeListElements(int n,T item,T &x){ if (ngetLength()) { cout data; pMove->data = item; return true;}#include "DoubleLinkedList.h"void Menu(){ cout
页:
[1]