数据结构 基本概念和述语

本文主要是介绍数据结构 基本概念和述语，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

基本概念和述语

数据（data）

是对客观事物的符号表示，是计算机中可以操作的对象，能被计算机程序处理的总称。

数据元素(data element)

是数据的基本单位，在计算机程序中通常做为一个整体进行考虑和处理，也被称为记录。
是组成数据的，有一定意义的基本单位，

数据项(data item)

一个数据元素可以由若干个数据项组成。数据项是数据不可分割的最小单位。

数据对象(data object)

是性质相同的数据元素的集合，是数据的一个子集。

数据结构(data structure)

是相互之间存在一种或多种特定关系的数据元素的集合。
通常有下列4类基本结构：

1. 集合：结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系。
2. 线性结构：结构中的数据元素之间存在一个对一个的关系。
3. 树形结构：结构中的数据元素之间存在一个对多个的关系。
4. 图状结构或网状结构：结构中的数据元素之间存在多个对多个的关系。
   

逻辑结构与物理结构

逻辑结构

逻辑结构是指数据对象中数据元素之间的相互关系。

物理结构

物理结构：是指数据的逻辑结构在计算机中的存储形式。
顺序存储结构：是把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。
链式存储结构：是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。

抽象数据类型（Abstract Data Type, ADT）:

数据类型：

是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。
抽象数据类型：是指一个数学模型以及定义在该模型上的一组操作.

ADT 抽象数据类型名 {数据对象:<数据对象的定义>数据关系:<数据关系的定义>基本操作:<基本操作的定义>
}ADT 抽象数据类型名
其中,数据对象和数据关系的定义用伪码描述,基本操作的定义格式为
基本操作名(参数表)初始条件:<初始条件描述>操作结果:<操作结果描述>

抽象数据类型三元组的定义:

ADT Triplet {数据对象：D={e1,e2,e3|e1,e2,e3属于ElemSet}数据关系：R1=｛<e1,e2>,<e2,e3>｝基本操作：IinitTriplet(&T, v1,v2,v3)操作结果：构造了三元组T，元素e1,e2和e3分别被赋以参数，v1,v2,v3的值。DestroyTriplet(&T)操作结果：三元组T被销毁Get(T, i, &e)初始条件：三元组T已存在，1<= i <=3操作结果：用e返回T的第i个元素的值。Put(&T, i, e)初始条件：三元组T已存在，1<= i <=3操作结果：改变T的第i个元素的值为e。IsAscending(T)初始条件：三元组T已存在。操作结果：如果T的3个元素按升序排列，则返回1，否则返回0.IsDescending(T)初始条件：三元组T已存在。操作结果：如果T的3个元素按降序排列，则返回1，否则返回0.Max(T, &e)初始条件：三元组T已存在。操作结果：用e返回T的3个元素中的最大值。Min(T, &e)初始条件：三元组T已存在。操作结果：用e返回T的3个元素中的最小值。
}ADT Triplet

抽象数据类型的表示与实现

1.预定义常量和类型：
//函数结果状态代码
#define TRUE 		1
#define FALSE 		0
#define OK			1
#define ERROR		0
#define INFEASIBLE	-1
#define OVERFLOW	-2//Status是函数的类型，其值是函数结果状态代码
typedef int Status;2.数据结构的表示（存储结构）用类型定义(typedef)描述。数据元素类型约定为ElemType，由用户在使用该数据类型时自行定义。3.基本操作的算法都用以下形式的函数描述：函数类型 函数名 (函数参数表) {// 算法说明语名序列} //函数名

抽象数据类型Triplet的表示和实现：

// 采用动态分配的顺序存储结构
typedef ElemType *Triplet; // 由InitTriplet分配3个元素存储空间
Status InitTriplet(Triplet &T, ElemType v1, ElemType v2, ElemType v3);
Status DestroyTriplet(Triplet &T);
Status Get(Triplet T, int i, ElemType &e);
Status Put(Triplet &T, int i, ElemType e);
Status IsAscending(Triplet T);
Status IsDescending(Triplet T);
Status Max(Triplet T, ElemType &e);
Status Min(Triplet T, ElemType &e);//基本操作的实现
Status InitTriplet(Triplet &T, ElemType v1, ElemType v2, ElemType v3) {// 构造三元组T，依次置T的3个元素置为v1,v2,v3T = (ElemType *)malloc(3 * sizeof(ElemType));if (!T)exit(OVERLOW);T[0] = v1; T[1] = v2; T[2] = v3;return OK;
} // InitTripletStatus DestroyTriplet(Triplet &T) {//销毁三元组T。free(T); T=NULL;retrun OK;
} //DestroyTripletStatus Get(Triplet T, int i, ElemType &e) {//1<=i<=3,用e返回T的第i元素if (i<1 || i>3) return ERROR;e = T[i-1];return OK;
} //GetStatus Put(Triplet &T, int i, ElemType e) {// 1<=i<=3, 置T的第i元素的值为eif (i<1 || i>3) return ERROR;T[i-1] = e;return OK;
} // PutStatus IsAscending(Triplet T) {//如果T的3个元素是按升序排列，则返回1，否则返回0；return (T[0] <= T[1]) && (T[1] <= T[2]);
} //IsAscendingStatus IsDescending(Triplet T) {//如果T的3个元素是按降序排列，则返回1，否则返回0；return (T[0] >= T[1]) && (T[1] >= T[2]);
} //IsDescendingStatus Max(Triplet T, ElemType &e) {//用e返回指向T的最大元素的值。e = (T[0] >= T[1])? ((T[0]>=T[2])?T[0]:T[2]) : ((T[1] >= T[2]) ? T[1] : T[2]);return OK;
}; //MaxStatus Min(Triplet T, ElemType &e) {//用e返回指向T的最大元素的值。e = (T[0] <= T[1])? ((T[0]<=T[2])?T[0]:T[2]) : ((T[1] <= T[2]) ? T[1] : T[2]);return OK;
}; //Min

算法和算法分析

算法：

算法(algorithm)是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作；

算法的5个重要特性：

1.有穷性：指算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成。
2.确定性：算法的每一步骤都具有确定的含义，不会出现二义性。
3.可行性：算法的每一步都必须是可行的，也就是说，每一步都能够通过执行有限次数完成。
4.输入：算法具有零个或多个输入
5.输出：算法至少有一个或多个输出

算法设计的要求：

1.正确性：是指算法至少应该具有输入，输出和加工处理无歧义性，能正确反映问题的需求，能够得到问题的正确答案。
2.可读性：算法设计的另一目的是为了便于阅读，理解。
3.健壮性：当输入数据不合法时，算法也能做出相关处理，而不是产生异常或莫名其妙的结果。
4.效率与低存储量需求：设计算法应该尽量满足时间效率高和存储量低的需求。

算法的效率的度量方法

算法时间复杂度 T(n) = O(f(n))

推导大O阶方法

1.用常数1取代运行时间中的所有加法常数。
2.在修改后的运行次数函数中，只保留最高阶项
3.如果最高阶项存在且不是1，则去除与这个项相乘的常数，得到的结果就是大O阶
常数阶 O(1)
线性阶 分析算法的复杂度，关键就是要分析循环结构的运行情况 O(n)
对数阶 O(logn)
平方阶 O(n^2)

算法空间复杂度
算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作：S(n) = O(f(n)),其中,n为问题的模，f(n)为语句关于n所占存储空间的函数。

这篇关于数据结构 基本概念和述语的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---