数据结构前三章(*回忆)

2024-02-01 20:07:40

数据结构的基本概念
算法的基本概念
算法的时间复杂度
算法的空间复杂度
线性表(逻辑结构)的定义和基本操作
顺序表(存储结构：顺序存储)的定义和基本操作
单链表(存储结构：链式存储)的定义和基本操作
双链表的定义和基本操作
循环链表的定义和基本操作
静态链表的定义和基本操作
链表和顺序表的比较
栈的定义(逻辑结构：线性表)和基本操作
顺序栈(存储结构：顺序存储)的定义和基本操作
链栈(存储结构：链式存储)的定义和基本操作
队列的定义(逻辑结构：线性表)和基本操作
队列的顺序实现
队列的链式实现
双端队列（栈是只在一端进出的队列）
栈的应用
- 括号匹配
- 中缀表达式转后缀表达式
- 中缀表达式求值、后缀表达式求值

数据结构的基本概念

程序 = 算法 + 数据结构
数据结构 = 数据的逻辑结构、数据的物理结构(存储结构)、数据的运算

算法的基本概念

算法是数据运算的顺序和执行方式

算法的时间复杂度与空间复杂度

时间复杂度：算法的运行次数与数据规模n的关系
空间复杂度：算法所占用的内存单元与数据规模n的关系
用O表示法

线性表

定义：相同类型元素的有限序列
操作:

//初始化
InitList(List &L);
//销毁列表
DestroyList(List &L);
//插入
ListInsert(List &L,ElemType x);
//删除i位元素
ListDelete(List &L,int i,ElemType &x);
//返回x地址
LocateElem(List L,ElemType x);
//返回i位元素x
GetElem(List L,ELemType &x);
//判空
IsEmpty(List L);
//判满
IsFull(List L);
//返回线性表长
ListLong(List L);

线性表的顺序存储

顺序表
顺序表的特点：
优点：随机读取，存储密度大
缺点：扩容不方便，插入、删除数据不方便
逻辑结构：线性表
存储结构：顺序存储
代码定义

静态分配

#define MaxSize 10
typedef struct{
	ElemType data[MaxSize];
	int length;
}SqList;

void InitList(SqList &L){
	for(int i = 0; i < MaxSize;i++)L.data[i] = 0;
	L.length = 0;
}

bool IsEmpty(SqList &L){
	if(L.length == 0)return true;
	return false;
}

bool InsertList(SqList &L,int i,ElemType e){
	if(i < 0|| i > length||L.length == MaxSize)return false;
	if(i == length)L.data[i] = e;
	else{
		for(int j = length - 1;j >= i - 1;j--){
			L.data[j+1] == L.data[j];
		}
		L.data[i - 1] = e;
	}
	L.length ++;
	return true;
}

动态分配

#define InitSize 10
typedef struct{
	ElemType *data;
	int maxSize;
	int length;
}SqList;

bool InitList(SqList &L){
	L.data = (int *)malloc(InitSIze*sizeof(int));
	if(L.data == NULL)return false;
	L.length = 0;
	L.maxSize = InitSize;
	return true;
}

bool IncreaseSize(SqList &L,int len){
	int *p = L.data;
	L.data = (int *)malloc((L.MaxSize + len)*sizeof(int));
	if(L.data == NULL)return false;
	for(int i = 0;i < L.length;i++)L.data[i] == p[i];
	L.maxSize += len;
	return true;
}

线性表的链式存储

单链表
定义:每个节点存储数据及指向下一个节点指针的线性表
链表的特点：
优点：扩容方便，不要求大片连续的空间
缺点：不可随机存取，存储密度小，要耗费一定空间存储指针

实现：

无头节点

typedef struct LNode{
	ElemType data;
	struct LNode *next;
}LNode, *LinkList;

void InitList(LinkList &L){
	L = NULL;
}

bool IsEmpty(LinkList L){
	if(L == NULL)return true;
	return false;
}

有头节点

typedef struct LNode{
	ElemType data;
	struct LNode *next;
}LNode*LinkList;

bool InitList(LinkList &L){
	L = (LNode *)malloc(sizeof(LNode));
	L -> next = NULL;
}

bool IsEmpty(LinkList L){
	if( L -> next == NULL)return true;
	return false;
}

bool ListInsert(LinkList L,int i,ElemType x){
	if(i < 1)return false;
	for(int j = 0;j < i - 1 && L != NULL; j++){
		L = L -> next;
	}
	if(L == NULL)return false;
	LNode *s = (LNode *)malloc(sizeof(LNode));
	if(s == NULL)return flase;
	s -> data = x;
	s - > next = L -> next;
	L -> next = s;
	return true;
}

bool InsertNextNode(LNode *p,ElemType e){
	if(p == NULL)return false;
	LNode *s == (LNode *)malloc(sizeof(LNode));
	if(s == NULL)return false;
	s -> data = e;
	s -> next = p -> next;
	p -> next = p;
	return true;
}

bool ListInsert(LinkList L,int i,ElemType x){
	if(i < 1)return false;
	for(int j = 0;j < i - 1 && L != NULL; j++){
		L = L -> next;
	}
	return InsertNextNode(L,x);
}

bool InsertPriorNode(LNode *p,ElemType e){
	if(p == NULL)return false;
	LNode *s = (LNode *)malloc(sizeof(LNode));
	s -> next = p -> next;
	s ->value = p -> value;
	p -> next = s;
	p -> value = e;
	return true;
}

码农公寓