[简述]数据结构-概念(c语言实现)
简述数据结构-概念(c语言实现)
1. 什么是数据结构?
数据结构:数据以及之间的联系,带结构的数据元素的集合。
包括三方面:
a) 数据的逻辑结构
b) 数据的存储结构
c) 数据的运算
1.1 数据的逻辑结构
从逻辑关系上描述数据,与存储无关。从具体问题抽象出来的数学模型。
如C声明的结构体。
struct{
ElemType data[MAXSIZE];
int len;
}sqlist;
1.2 数据的存储结构
即逻辑结构在计算机中的存储方式。即可以看成是在内存或磁盘中的存储方式。
如, 数组和链表是两种不同的存储结构。
1.3 数据的运算
在数据逻辑结构之上,对应的一组运算。常用的有:检索,插入,更新,排序等。
2 逻辑结构类型
集合:数据元素之间除了同属于一个集合外,无其他关系。
线性结构:结构中的结点存在一对一的关系。
树形结构:结构中的结点存在一对多的关系。
图形结构:结构中的结点存在多对多的关系。
3 存储结构类型
顺序存储结构:逻辑上相邻的点在物理上也相邻,如数组
a) 优点:节省空间,随机存取
b) 缺点:不便于插入,删除和修改
链式存储结构:不要求逻辑上相邻的结点,物理上也相邻,如链表
a) 优点:便于修改,插入和删除
b) 缺点:点用额外的空间,不能随机存取
索引存储结构:存储信息同时,还建立附加索引表。
a) 优点:大大提高查找速度,可随机访问,对数据修改效率高
b) 缺点:增加了索引表,存储空间大
哈希(散列)存储结构: 根据结点的关键字通过哈希函数计算出一个值,做为该结点的存储地址。
a) 优点:查找速度快,
b) 缺点:一般只适合要求对数据能够进行快速查找和插入的场合。
4 数据类型
简单类型和结构类型。
5 抽象数据类型(abstract data type ,ADT)
用户进行软件系统设计时人问题的数学模型抽象出来的逻辑数据结构和逻辑数据结构上的运算,而不考虑计算机的存储实现和运算的具体实现算法。
基本格式:
ADT 抽象数据类型名
{
数据对象:数据对象的定义
数据关系:数据关系的定义
基本运算:基本运算的定义
}ADT抽象数据类型名
基本运算名(参数表):运算功能描述
如:
ADT Complex
{
数据对象:
D = {e1,e2|e1,e2均为实数}
数据关系:
R = {<e1,e2>| e1是复数实数部分, e2是复数的虚数部份}
基本操和:
AssignComplex(&Z,v1,v2):构造复数
DestroyComplex(&Z):销毁复数
GetReal(z,&real):取得复数的实部
GetImag(z,zImag):取得复数的虚部
Add(z1,z2,&sum):用sum返回两个复数的和
}ADT Complex