C_数据结构

基本概念

数据,数据元素,数据项,数据对象

　　数据: 是客观事物的符号表示,是所有能输入到计算机中并被计算机程序处理的符号的总称.

　　数据元素:是数据的基本单位,在计算机中通常作为一个整体来处理.如学生管理系统中的一名学生.

　　数据项:是组成数据元素的,有独立含义的最小单位,如学生管理系统中学生的姓名,学号等基本信息.

　　数据对象:是性质相同的数据元素的集合,是数据的一个子集.

数据结构

　　数据结构是相互之间存在一种或多种特定关系的数据元素的集合.数据结构包括逻辑结构和存储结构两个层次.

逻辑结构:

　　从逻辑关系上描述数据,与数据的存储无关,独立于计算机.可以看作具体问题的数学模型.

　　逻辑结构的两大要素: 数据元素和逻辑关系,根据数据元素之间的关系不同,可以分为以下四种常见基本结构.

　　其中 集合结构,树结构和图(网)结构都属于非线性结构.

　　线性结构包括线性表,栈,队列,字符串和数组

　　非线性结构包括数,二叉树,有向图和无向图

存储结构

　　数据对象在计算机中的存储表示称为数据的存储结构,也称为物理结构,既要存储各数据元素的数据,又要存储它们之间的逻辑关系.数据元素再计算机中又两种基本的存储结构,分别是顺序存储结构和链式存储结构.

顺序存储结构:
　　顺序存储结构是借助元素再存储其中的相对位置;来表示数据元素之间的逻辑关系,通常借助程序设计语言的数组类型来描述.

链式存储结构:
　　链式存储结构无需占用一整块存储空间,但为了表示节点之间的关系,需要给每个节点附加指针字段,用于存放后继元素的存储地址.所以链式存储结构通常借助程序语言的指针类型来表示.

数据类型和抽象数据类型

数据类型

　　数据类型是一个值的集合和定义在这个值上的一系列操作的总称.

抽象数据类型

　　抽象数据类型(ADT),是指一个数学模型以及定义在该模型上的一组操作.

　　抽象数据类型的定义仅取决于它的一组逻辑特性.于其在计算机内如何表示和实现无关,即无论其内部结构如何变化,只要其数学特性不变,都不影响其外部使用.

　　**抽象**意思就是“不具体”,即描述数据类型的方法不依赖于具体实现方式,而在于其数学抽象特性.

ADT定义格式:
ADT抽象数据类型名{
	数据对象:<数据对象的定义>;
	数据关系:<数据关系的定义>;
	基本操作:<基本操作的定义>;
}ADT抽象数据类型名

　　数据对象和数据关系的定义采用数学符号和自然语言描述.

　　基本操作的定义格式为:

基本操作名(参数表)
	初始条件:<初始条件描述>
	操作结果:<操作结果描述>

　　基本操作有两种参数:赋值参数为操作提供输入值;引用参数(以&开头),除提供输入值外,还将返回操作结果.”初始条件”描述了操作执行之前的数据结构和参数应该满足的条件(若初始条件为控,则省略),”操作结果”说明了操作正常完成后,数据结构的变化和应返回的结果.

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

预定义常及类型:

//函数结果状态代码
#define TRUE  1
#define FALSE  0
#define OK  1
#define ERROR  0
#define OVERFLOW  -2
//Status 是用来作为函数返回值的类型,其值为函数结果状态代码
typedef int Status;

数据结构的表示(存储结构)用类型定义(typedef)描述;数据元素类型约定为ElemType,由用户自行定义;

基本操作的算法都用如下格式的函数来描述:

函数类型 函数名 (参数表){
	//算法说明
	算法语句
}/函数名
    

线性表

线性表的定义

　　由n(n≥0)个数据元素特性相同的元素构成的有限序列称为线性表.其中当n=0时称为空表.

对于非空线性表或线性结构,有以下特点:

• 存在唯一一个被称为“第一个”和唯一一个“最后一个”的元素.

• 除第一个元素之外,其他元素有且仅有一个前驱.

• 除最后一个元素之外,其他数据元素有且仅有一个后继.

线性表的抽象数据类型定义

线性表的顺序表示和实现

线性表的顺序存储表示

　　线性表的顺序表示指的是用一组连续的存储单元依次存储线性表的数据元素,也称为线性表的顺序存储结构或顺序映像.称这种存储结构的线性表为顺序表.

　　特点:逻辑上相邻的数据元素,其物理次序也是相邻的.

　　假设线性表每个元素占 l 个存储单元,所以第 i 个数据元素 a_i 的存储位置为:

　　　　　　　　　　　　LOC(a_i) = LOC(a₁)+ (i-1)*l

　　只要确定了存储线性表的起始位置,线性表中的任意元素都可以随机存取(使用数组下标),所以线性表的顺序存储结构是一种随机存取的数据结构.

//顺序表存储结构
#define MAXSIZE 100
typedef struct{
	ElemType * elem;
	int length;
}SqList;

• 元素类型定义中的ElemType数据类型是为了描述统一而定的,在实际应用中,可根据实际具体需求来定义,既可以是int, float,char等基本数据类型,也可以是构造数据类型,如struct结构体类型.

例:用顺序表存储稀疏多项式

#define MAXSIZE 100			//顺序表最大长度
typedef struct{				//多项式非零项定义
	float coef;					//系数
	int expn;					//指数
}Polunomial;
typedef struct{
	Polynomial *elem;		//存储空间的基地址
	int length;				//顺序表当前长度;
}SqList;					//将此顺序表存储结构定义为SqList类型

在上述定义后,可以通过以下变量定义语句将L定义为SqList类型的变量.

SqList L;

并通过L.elem[i-1]来访问表中第 i 个数据元素.

顺序表基本操作的实现

• 初始化

  构造一个空的顺序表

算法思路:

1. 为顺序表动态分配一个空间,使elem指向这段空间的基地址.
2. 将表的当前长度设为0.

算法实现:

//顺序表 存储结构 定义
#define MAXSIZE 100
typedef struct{
	ElemType * elem;
	int length;
}SqList;
//通过变量定义顺序表 L
SqList L;
//初始化顺序表 L 算法实现
Status InintList (SqList &L){
	L.elem = new ElemType[MAXSIZE];		//为顺序表分配一个大小为MIXSIZE的数组空间
	if(!L.elem) exit (OVERFLOW);		//存储分配失败则退出
	L.Length = 0;						//将表长度设为 0
	return OK;
}

• 取值

  获取顺序表中的第 i 个元素的值.可以直接通过数组下标定位到,elem[i-/‘;;991]数组单元中存储的第 i 个元素.

算法思路:

1. 判断序号 i 是否合理(1 ≤ i ≤ L.length),若为否,返回ERROR.
2. i 合理,将第 i 个元素赋值给参数,并返回.

算法实现:

Status GetElem(SqList L,int i,ElemType &e)
{
if (i<1 || i>L.lenght)
	return ERROR;
e=L.elem[i-1];
return OK;
}

• 查找

  根据指定元素e,查找顺序表中第 1 个与e相等的元素,若查找成功,则返回该元素再表中的位置序号,若查找失败,则返回 0.

算法思路:

1. 从第 1 个元素起依次比较,若找到与e相等的元素L.elem[i],则返回序号i+1.
2. 若查找失败则返回0;

算法实现:

int LocatElem {SqList L,ElemType e}{
	for( i = 0; i< L.length;i++)
		if(L.elem[i] == e) return i+1;
	return 0;
}

• 插入

  在表的第 i 个为位置插入一个新的数据元素 e ,使长度为 n 的线性表变为 n+1 的线性表.

算法思路:

1. 判断插入位置是否合法(1 ≤ i ≤ n+1 ), 若不合法则返回ERROR.
2. 判断顺序表的存储空间是否已满,若满则返回ERROR.
3. 将第 n 个至 i 个位置之间的元素依次向后移动一个位置
4. 在第 i 个位置插入 e .
5. 表长 L.length + 1.

算法实现:

Status ListInsert (SqList &L,ElemType e){
if((i<1)||(i>L.length+1))		
	return ERROR;			//检测 i 是否合法
if(L.length == MAXSIZE)
	return ERROR;		    //当前存储空间已满
for(j=L.length-1;j>=i-1;j--)
	L.elem[j+1]=L.emem[j];	//插入位置及其以后元素后移
L.elem[i-1]=e;				//将 e 插入第 i 个位置
++L.length;					//表长加1
return OK;
}

时间复杂度为O(n).

• 删除

  将表中第 i 个元素删除,将长度为 n 的表变为长度为 n-1 的表

算法思路:

1. 判断删除位置 i 是否合法(1 ≤ i ≤ n ),若不合法返回 ERROR.
2. 将第 i+1 个至 n个元素依次向前移动一个位置.
3. 表长 (L.length–).

算法实现:

Status ListDelete (Sqlist &L,int i){
	if((i<1)||(i>length))
		return ERROR;			//i值不合法
	for(j=i;j<L.length;j++){    //被删除元素之后元素前移
		L.elem[j-1]=L.elem[j];
	}
	--L.length;					//表长减 1
	return OK;
}

时间复杂度为O(n).

顺序表链式表示和实现

单链表的定义和表示

线性表链式存储结构:

　　用一组任意的存储单元存储线性表的数据元素(这组存储单元不需要连续),所以每个结点(node)由两部分组成,包含两个域: 存储数据元素信息的数据域和存储后继存储位置(后继结点)的指针域.n 个结点( 1 ≤ i ≤ n )链结成的一个链表即称为线性表.又因为此链表的每个结点中只包含一个指针域,故又称为线性链表或单链表.

　　根据链表结点所包含的指针个数,指针指向和指针的连接方式,可将链表分为:

　　实现线性表的链式存储结构:单链表,循环链表,双向链表;

　　实现树和图的非线性存储结构:二叉链表,十字链表,邻链表,邻接多重链表.

单链表中结点的定义可由C语言中的“结构指针来描述”

typedef struct LNode{
	ElemType data;		//数据域
	struct LNode *next; //指针域
}LNode,*LinkList;