数据结构

数据结构

[TOC]

第一章绪论

1.数据结构的基本概念

1.基本概念和术语

1.数据

信息的载体,是描述客观事物属性的数,字符及所有能被计算机识别和处理的符号的集合

2.数据元素

数据的基本单位,由数据项组成,不可分割的最小单位

3.数据对象

具有相同性质的数据元素的集合,数据的一个子集

4.数据类型

一个值的集合和定义在集合上的一组操作的总称

原子类型值不可再分

结构类型值可以再分

抽象数据类型

5.抽象数据类型

1.定义: 一个数学模型和定义在模型上的一组操作

2.特点: 定义仅取决于它的一组逻辑特性,与在计算机内部如何表示和实现无关

3.表示: (数据对象,数据关系,基本操作集)

6.数据结构

1.结构: 数据元素之间的相互关系

2.定义: 相互之间存在一种或多种特定关系的数据元素的集合

3.内容: 逻辑结构,存储结构,数据的运算

逻辑结构: 一个算法的设计

存储结构: 一个算法的实现

2.数据结构三要素

1.数据的==逻辑结构==

1.定义: 数据元素之间的逻辑关系,与存储无关,独立于计算机

2.分类

线性结构

1、线性表一对一

非线性结构

1、集合同属一个集合

2、树一对多

3、图/网状多对多

2.数据的==存储结构==

1.定义: 数据结构在计算机中的表示(又称映像/物理结构)

2.包括: 数据元素的表示和关系的表示

3.分类

==顺序存储==

优点: 随机存取,元素占用最少存储空间

缺点: 只能使用相邻的一整块存储单元,产生较多的外部碎片
==链式存储==

优点: 不会出现碎片现象

缺点: 存储指针占用额外的存储空间; 只能顺序存取
==索引存储==

定义: 建立附加的索引表,每项称为索引项(关键字,地址)

优点: 检索速度快

缺点: 占用较多存储空间; 增加和删除数据要修改索引表,花费较多时间
==散列存储==

定义: 根据元素的关键字直接计算出该元素的存储地址(Hash存储)

优点: 检索,增加和删除结点都很快

缺点: 若散列函数不好,出现元素存储单元冲突,会增加时间和空间的开销

3.数据的运算

1.运算的定义: 针对逻辑结构,指出运算的功能

2.运算的实现: 针对存储结构,指出运算的具体操作步骤

题目总结

==易错：==

1.属于逻辑结构有序表

2.循环队列是用顺序表表示的队列,是数据结构,不是抽象数据结构

3.不同结点的存储空间可以不连续,但结点内的存储空间必须连续

4.两种不同的数据结构,逻辑结构和物理结构可以完全相同,但数据的运算不同

2.算法和算法评价

1.算法的基本概念

1.定义: 对特定问题求解步骤的描述,指令的有限序列

2.==特性==

1.有穷性

2.确定性

3.可行性

4.输入

5.输出

3.==好的算法==

1.正确性

2.可读性

3.健壮性

4.效率与低存储量需求

2.算法效率的度量

1.时间复杂度O(n)

定义: 衡量算法随着问题规模增大,算法执行时间增长的快慢

2.空间复杂度S(n)

1.定义: 衡量算法随着问题规模增大,算法所需空间增长的快慢

2.算法原地工作: 算法所需要的辅助空间为常数,即O(1)

题目总结

1、==易错==

1.将长度为m,n的两个升序链表,合并为m+n的降序链表(取较小元素,头插法)

2.时间复杂度计算

1.sum += ++i; O(n^1/2) 第k次: sum = 1+2+3+…+k ≥n

2、2.i=i*2 O(log₂n)

3.递归算法

1.T(n)=2T(n/2)+n (n>1) (n=1时: T(n)=1) O(nlog₂n）
2.设n=2^k,先根据递归条件,找到T(2^k)的通式,再转化为n,即得到时间复杂度

3.同一个算法,实现的语言的级别越高级,执行效率越低

第二章线性表

1.线性表的定义和基本操作

1.线性表的定义

1.定义: 相同数据类型的有限序列

2.注意: 线性表是逻辑结构,顺序表和链表指存储结构

2.线性表的基本操作

1.注意: & 表示C++中的引用,若传入指针型变量且在函数体内要进行改变,要用到指针变量的引用(C中用指针的指针也可以)

2.主要操作

2.线性表的顺序表示

1.顺序表的定义

1.顺序表需要三个部分

==存储空间的起始位置==
==顺序表最大存储空间==
==顺序表当前的长度==

2.==静态分配==

#define MaxSize 50 			//定义线性表的最大长度
typedef struct {
	ElemType data[MaxSize]; //顺序表的元素
	int length;				//顺序表的当前元素
}SqList;					//顺序表的类型定义

3.==动态分配==

#define InitSize 10 		//顺序表的初始长度
typedef struct{
    ElemType *data;			//指示动态分配数组的指针
    int MaxSize;			//顺序表的最大容量
    int length;				//顺序表的当前长度
}SqList;					//顺序表的类型定义（动态分配方式）

4.动态分配语句

C语言: ==L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);==

C++: ==L.data=new ElemType[InitSize];==

5.注意: 动态分配不是链式存储,同样属于顺序存储结构,物理结构没有变化:随机存取方式,只是分配的空间大小可以在运行时决定

6.特点: 随机访问,存储密度高,插入和删除需要移动大量元素

2.顺序表上基本操作的实现

1.==插入操作 O(n)==

bool ListInsert(SqList &L, int i, ElemType e){
	if (i < 1 || i > L.length + 1) 				//判断i的范围是否有效
		return false;
	if (L.length >= MaxSize) 					//当前存储空间已满，不能插入
		return false;
	for (int j = L.length; j >= i; j -- )		//将第i个元素及之后的元素后移
		L.data[j] = L.data[j - 1];
	L.data[i - 1] = e;							//在位置i处放入e
	L.length ++ ;								//线性表长度加1
	return true;
}

2.==删除操作 O(n)==

bool ListDelete(SqList &L, int i, ElemType &e){
	if (i < 1 || i > L.length)					//判断i的范围是否有效
		return false;
	e = L.data[i - 1];							//将被删除的元素赋值给e
	for (int j = i; j < L.length; j ++ )		//将第i个位置后的元素前移
		L.data[j - 1] = L.data[j];
	L.length -- ;								//线性表长度减1
	return true;
}

3.==按值查找(顺序查找) O(n)==

int LocateElem(SqList L, ElemType e) {
	int i;
	for (int i = 0; i < L.length; i ++ )
		if (L.data[i] == e) 
			return i + 1;				//下标伟i的元素值等于e，返回其位序i + 1；
	return 0;							//退出循环，说明查找失败
}

4、==初始化顺序表==

void InitList(Sqlist &L) {
	for (int i = 0; i < MaxSize; i ++ )
		L.data[i] = 0;					//所有数据元素设置为默认初始值
	L.length = 0;						//顺序表初始长度为0
}

题目总结

==1、易错==

1.线性表必须是有限序列

2.在顺序表的第i个位置插入一个数,i的合法取值: 1≤i≤n+1 在第n+1个位置插入相当于在表尾追加

==2、算法==

1.将顺序表的所有元素逆序

算法思想：扫描顺序表L的前班部分元素，对于元素L.date[ i ] (0 <= L.length / 2），将其与后半部分的对应元素L.data[L.length - i - 1]进行交换

void Reverse(SqList &L){
    ElemType temp;									//辅助变量
    for (int i = 0; i < L.length / 2; i ++ ){
        temp = L.data[i];							//交换L.data[i]与L.data[L.length - i - 1];
        L.data[i] = L.data[L.length - i - 1];
        L.data[L.length - i - 1] = temp;
    }
}

2.顺序表(非有序)删除所有值为x的数据元素

用k记录顺序表L中不等于x的元素个数（既需要保存的元素个数），扫描时将不等于x的元素移动到下标k的位置，并更新k值。扫描结束后修改L的长度

void del_x_l(SqList &L, Elemtype x){
	int k = 0, i;							//记录值不等于x的元素个数
	for (int i = 0; i < L.length; i ++ )
		if (L.data[i] != x){
			L.data[k] = L.data[i];
			k ++ ;							//不等于x的元素增1
			}
		L.length = k;						//顺序表L的长度等于k
}

3.有序顺序表删除给定值s与t之间的所有元素

bool Del_S_t2(SqList &L, ElemType s, ElemType t){
	//删除有序顺序表L中值在给定值s到t之间的所有元素
	int i, j;
	if (s >= t || L.length == 0)
		return false;
	fOr (i = 0; i < L.length && L.data[i] < s; i ++ );	//寻找值大于等于s的第一个元素
	if (i >= L.length)	
		return false;									//所有元素值均小于s，返回
	for (j = i; j < L.length && L.data[j] <= t; j ++ )	//寻找值大于t的第一个元素
	for (;j < L.length; i ++ , j ++ )
		L.data[i] = L.data[j];							//前移，填补被删元素位置
	L.length = i;
	return true;
}

4.有序表删除所有其值重复的元素

bool  Delete_Same(SeqList &L){
	if (L.length == 0)
		return false;
	int i, j;											//i存储第一个不相同的元素，j为工作指针
	for (int i = 0, j = 1; j < L.length; j ++ )
		if (L.data[i] != L.data[j])						//查找下一个与上个元素值不同的元素
			L.data[++ i] = L.data[j];					//找到后，将元素前移
	L.length = i + 1;
	return true;
}

5.将两个有序表合并为一个有序表,由函数返回结果

bool Merge(SeqList A, SeqList B, SeqList &c){
	//将有序顺序表A与B合并为一个新的有序顺序表C
	if (A.length + B.length > C.maxSize)				//大于顺序表的最大长度
		return fasle;
	int i = 0, j = 0, k = 0;
	while(i < A.length && J < B.length){				//循环，两两比较，小者存入结构表
		if (A.data[i] < B.data[i])
			C.data[k ++ ] = A.data[i ++ ];
		else 
			C.data[k ++ ] = B.data[j ++ ];
	}
	while(i < A.length)									//还剩下一个没有比较完的顺序表
		C.data[k ++ ] = A.data[i ++ ];
	while(j < B.length)
		C.data[k ++ ] = B.data[j ++ ];
	C.length = k;
	return true;
}

3.线性表的链式表示

1.单链表的定义

1.结点类型的描述

2.特点: 浪费空间,非随机存取

3.头指针和头结点区别

1.不管带不带头结点,头指针始终指向链表的第一个结点

2.头结点是带头结点的链表中的第一个结点,通常不存储信息

4.引入头结点的优点

1.在链表第一个位置上的操作和其他位置上的一致

2.无论链表是否为空,头指针都指向头结点的非空指针,空表和非空表处理一致

单链表定义

typedef struct LNode{			//定义单链表结点类型
	ElemType data;				//数据域
	struct LNode *next;			//指针域
}LNode, *LinkList;

2.单链表上基本操作的实现

1.头插法建立链表

LinkList List_HeadInsert(LinkList &L){			//逆向建立单链表
	LNode *s; int x;
	L = (LinkList)malloc(sizeof(LNode));		//创建头结点
	L.next = NULL;								//初始化为空链表
	scanf("%d", &x);							//输入结点的值
	while(x != 9999){							//输入9999表示结束
		s = (LNode *)malloc(sizeof(LNode));		//创建新结点
		s->data = x;
		s->next = L->next;
		L->next = s;							//将新的结点插入表中，L为头指针
		scanf("%d", &x);
	}
	return L;
}

2.尾插法建立链表

3.按序号查找结点值

4.按值查找表结点

5.插入结点操作

前插操作: 先找到前一个结点,时间复杂度为O(n)

扩展: 将前插操作转化为后插操作,然后交换两个结点的数据,时间复杂度为O(1)

6.删除结点操作

先找到前驱节点,再删除结点,O(n

扩展: 先和后继结点交换数据,再删除后继结点,O(1)

7.求表长操作

计算数据结点的个数

3.双链表

1.双链表中结点类型的描述

2.插入操作

3.删除操作

4.循环链表

1.==循环单链表==

1.判空条件: 头结点的指针是否指向头指针

2.对单链表在表头和表尾操作时: 不设头指针仅设尾指针,效率更高

2.==循环双链表==

判空条件: 头结点的prior域和next域都指向头指针

5.静态链表

1.定义: 用数组描述链式存储结构,也有数据域和指针域.指针是结点的相对地址(数组下标),又称游标

2.形式

3.结束标志: next==-1

4.注意

1.和顺序表一样,也要预先分配一块连续的内存空间

2.插入和删除只需要修改指针,不需要移动元素

3.在不支持指针的高级语言(Basic)中很巧妙

6.顺序表和链表的==比较==

1.存取方式

顺序表可顺序存取,可随机存取. 链表只能从表头顺序存取

2.逻辑结构与物理结构

3.查找,插入和删除

1.按值查找

无序时,都为O(n)

有序时,顺序表可以折半查找,O(log₂n)

2.按序号查找

顺序表为O(1),链表为O(n)

4.空间分配

5.怎样选取存储结构

1.基于存储的考虑

难以估计长度和存储规模时用链表,但链表的存储密度较低

2.基于运算的考虑

经常做按序号访问数据元素用顺序表

3.基于环境的考虑

顺序表容易实现,链表基于指针

较稳定选顺序表,动态性较强选链表

题目总结

1、==易错==

1.链式存储结构比顺序存储结构更方便地表示各种逻辑结构

2.顺序存储不只能用于存储线性结构,还能存储图和树的结构(满二叉树)

3.静态链表需要分配较大的连续空间,插入和删除不需要移动元素

4.若用单链表表示队列,应选用带尾指针的循环链表

5.给定一维数组,建立一个有序单链表的最低时间为O(nlog₂n)

先对数组进行排序,再构造单链表

6.链表常用操作为在最后一个元素之后插入,删除第一个元素,最节省时间的是

1.不带头结点且有尾指针的单循环链表

2.即使是双链表,只要不带尾指针,都要找到尾结点,时间为O(n)

第一章绪论

1.数据结构的基本概念

1.基本概念和术语

2.数据结构三要素

题目总结

2.算法和算法评价

1.算法的基本概念

2.算法效率的度量

题目总结

第二章线性表

1.线性表的定义和基本操作

1.线性表的定义

2.线性表的基本操作

2.线性表的顺序表示

1.顺序表的定义

2.顺序表上基本操作的实现

1.==插入操作 O(n)==

2.==删除操作 O(n)==

3.==按值查找(顺序查找) O(n)==

4、==初始化顺序表==

题目总结

3.线性表的链式表示

1.单链表的定义

2.单链表上基本操作的实现

3.双链表

4.循环链表

5.静态链表

6.顺序表和链表的==比较==

题目总结

注意点

1.插入结点时: 先对插入结点的后继结点操作,再对原结点进行操作

第三章栈和队列

第四章树和二叉树

第五章图

第六章查找

第七章排序

数据结构

第一章 绪论

1.数据结构的基本概念

1.基本概念和术语

2.数据结构三要素

题目总结

2.算法和算法评价

1.算法的基本概念

2.算法效率的度量

题目总结

第二章 线性表

1.线性表的定义和基本操作

1.线性表的定义

2.线性表的基本操作

2.线性表的顺序表示

1.顺序表的定义

2.顺序表上基本操作的实现

1.==插入操作 O(n)==

2.==删除操作 O(n)==

3.==按值查找(顺序查找) O(n)==

4、==初始化顺序表==

题目总结

3.线性表的链式表示

1.单链表的定义

2.单链表上基本操作的实现

3.双链表

4.循环链表

5.静态链表

6.顺序表和链表的==比较==

题目总结

注意点

1.插入结点时: 先对插入结点的后继结点操作,再对原结点进行操作

第三章 栈和队列

第四章 树和二叉树

第五章 图

第六章 查找

第七章 排序

第一章绪论

第二章线性表

第三章栈和队列

第四章树和二叉树

第五章图

第六章查找

第七章排序