数据结构与算法学习笔记

线性表

顺序表

静态分配

//顺序表的实现--静态分配
#define MAX_SIZE 10
#define ElemType int
typedef struct
{
	ElemType Data[MAX_SIZE];
	int Length;
} SQList;

//基本操作--初始化一个顺序表
void InitList(SQList &L)
{
	for (int i = 0; i < MAX_SIZE; i++)
		L.Data[i] = 0;
	L.Length = 0;
}

int main()
{
	SQList L;
	InitList(L);
}

动态分配

//顺序表的实现--动态分配
#define InitSize 10
#define ElemType int
typedef struct
{
	ElemType* data;
	int MaxSize;
	int Length;
} SeqList;

void InitList(SeqList &L)
{
	L.data = (int*)malloc(InitSize * sizeof(int));
	L.Length = 0;
	L.MaxSize = InitSize;
}

//增加动态数组的长度
void IncreaseSize(SeqList &L,int len)
{
	int* p = L.data;
	L.data = (int*)malloc((L.MaxSize + len) * sizeof(int));
	for (int i = 0; i < L.Length; i++)
	{
		L.data[i] = p[i];
	}
	L.MaxSize = L.MaxSize + len;
	free(p);
}

插入

//静态分配的插入
void ListInsert(SQList &L,int i,int e)
{
	for (int j=L.Length;j>=i;j--)
		L.Data[j] = L.Data[j - 1];
	L.Data[i - 1] = e;
	L.Length++;
}

//静态分配的插入改进
bool ListInsert(SQList& L, int i, int e)
{
	if (i<1 || i>L.Length + 1)return false;
	if (L.Length >= MAX_SIZE)return false;
	for(int j=L.Length;j>=i;j--)
		L.Data[j] = L.Data[j - 1];
	L.Data[i - 1] = e;
	L.Length++;
	return true;
}

时间复杂度为O(n)

删除

//静态分配的删除
bool ListDelete(SQList &L,int i,int &e)
{
	if (i<1 || i>L.Length)return false;
	e = L.Data[i - 1];
	for (int j = i; j < L.Length; j++)
		L.Data[j - 1] = L.Data[j];
	L.Length--;
	return true;
}

时间复杂度为O(n)

查找

//按位查找
ElemType GetElem(SQList L,int i)
{
	return L.Data[i - 1];
}

//按值查找
int LocateElem(SeqList L,int e)
{
	for (int i = 0; i < L.Length; i++)
		if (L.Data[i] == e)return i + 1;
	return 0;
}

单链表

定义

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

初始化

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

按位插入

//按位插入
bool ListInsert(LinkList &L,int i, ElemType e)
{
	if (i < 1)return false;
	LNode* p = L;
	int j = 0;
	while (p!=NULL&&j<i-1)
	{
		p = p->next;
		j++;
	}
	if (p == NULL)
		return false;
	LNode* s = (LNode*)malloc(sizeof(LNode));
	s->Data = e;
	s->next = p->next;
	p->next = s;
	return true;
}

后插操作

//后插操作
bool InserNextNode(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 = s;
	return true;
}

前插操作

//前插操作
bool InsertPriorNode(LNode *p,ElemType e)
{
	if (p == NULL)return false;
	LNode* s = (LNode*)malloc(sizeof(LNode));
	if (s == NULL)return false;
	s->next = p->next;
	p->next = s;
	s->Data = p->Data;
	p->Data = e;
	return true;
}

删除

按位删除

//按位删除
bool ListDelete(LinkList &L,int i,ElemType &e)
{
	if (i < 1)return false;
	LNode* p = L;
	int j = 0;
	while (p!=NULL&&j<i-1)
	{
		p = p->next;
		j++;
	}
	if (p == NULL)return false;
	if (p->next == NULL)return false;
	LNode* q = p->next;
	e = q->Data;
	p->next = q->next;
	free(q);
	return true;
}

指定节点删除

//指定节点删除
bool DeleteNode(LNode *p)
{
	if (p == NULL)return false;
	LNode* q = p->next;
	p->Data = p->next->Data;
	p->next = q->next;
	free(q);
	return true;
}

查找

按位查找

//按位查找
LNode * GetElem(LinkList L,int i)
{
	if (i < 0)return NULL;
	LNode* p=L;
	int j = 0;
	while (p!=NULL&&j<i)
	{
		p = p->next;
		j++;
	}
	return p;
}

按值查找

//按值查找
LNode* LocateElem(LinkList L,ElemType e)
{
	LNode* p = L->next;
	while (p != NULL && p->Data != e)
		p = p->next;
	return p;
}

双链表

初始化

typedef struct DNode
{
	ElemType data;
	struct DNode* prior, * next;
}DNode,*DLinklist;

bool InitDLinkList(DLinklist &L)
{
	L = (DNode*)malloc((sizeof(DNode)));
	if (L == NULL)
		return false;
	L->prior = NULL;
	L->next = NULL;
	return true;
}

插入

bool InsertNextDNode(DNode *p,DNode *s)
{
	if (p == NULL || s == NULL)
		return false;
	s->next = p->next;
	if (p->next != NULL)
		p->next->prior = s;
	s->prior = p;
	p->next = s;
	return true;
}

删除

删除节点

bool DeleteNextDNode(DNode *p)
{
	if (p == NULL)
		return false;
	DNode* q = p->next;
	if (q == NULL)return false;
	p->next = q->next;
	if (q->next != NULL)
		q->next->prior = p;
	free(q);
	return true;
}

整表删除

void DestoryList(DLinklist &L)
{
	while (L->next != NULL)
		DeleteNextDNode(L);
	free(L);
	L = NULL;
}

遍历

前项遍历

while(P!=NULL)
    p=p->next;

后项遍历

while(P!=NULL)
    p=p->prior;

循环链表

循环单链表

创建

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

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

//循环单链表判空
bool Empty(LinkList L)
{
	if (L->next == L)
		return true;
	return false;
}

//判断P是否为表尾节点
bool isTail(LinkList L, LNode* p)
{
	if (p->next == L)
		return true;
	return false;
}

循环双链表

创建

typedef struct DNode
{
	ElemType data;
	struct DNode *prior, *next;
}DNode,*DLinklist;

bool InitDLinkList(DLinklist L)
{
	L = (DNode*)malloc(sizeof(DNode));
	if (L == NULL)
		return false;
	L->prior = L;
	L->next = L;
	return true;
}

插入

bool InsertNextDNode(DNode *p,DNode *s)
{
	if (p == NULL || s == NULL)
		return false;
	s->next = p->next;
	p->next->prior = s;
	s->prior = p;
	p->next = s;
	return true;
}

静态链表


struct Node
{
	ElemType data;
	int next;
}SLinkList[MaxSize];

栈

栈是只允许在一段进行插入或删除操作的线性表

顺序存储结构

创建

typedef struct my_struct
{
	ElemType data[MaxSize];
	int top;
}SqStack;

void InitStack(SqStack &S)
{
	S.top = -1;
}

入栈

bool Push(SqStack &S,ElemType x)
{
	if (S.top == MaxSize - 1)
		return false;
	S.top = S.top + 1;
	S.data[S.top] = x;
	return true;
}

出栈

bool Pop(SqStack &S,ElemType &x)
{
	if (S.top == -1)
		return false;
	x = S.data[S.top];
	S.top = S.top - 1;
	return true;
}

获取栈顶元素

bool GetTop(SqStack& S, ElemType& x)
{
	if (S.top == -1)
		return false;
	x = S.data[S.top];
	return true;
}

共享栈

链式存储结构

略

判断输出序列的合法性


如果一个节点已经弹出,那么它之后弹出的比它先压入栈的节点一定按照顺序出栈

栈在括号匹配中的应用

从左向右扫描一个有括号的字符串,遇到左括号就压入栈,遇到右括号就弹出栈,如果最后栈不为空或中途栈空却依然遇到右括号,则该字符串的括号有问题

栈在表达式求值中的应用

我们常用的表达式,比如1+1,叫做中缀表达式

所以也存在前缀表达式(波兰表达式)和后缀表达式(逆波兰表达式)

后缀表达式

ab+ , ab+c-, ab+cd*-

后缀表达式的计算

中缀转后缀

以上两种的结果是一样的,计算机算法的结果是前者

后缀表达式的计算(机算)

中缀表达式转后缀表达式(机算)

栈要足够长,否则可能溢出

中缀表达式的计算(用栈实现)

中缀转后缀


注:教材中没有”左/右操作数”和”左/右优先原则”这是说

前缀表达式

+ab , -+abc , -+ab*cd

前缀表达式的计算

栈在递归中的应用

• 函数调用栈

队列

队列是只允许在一段进行插入,在另一端删除的线性表

所以队列是先进先出的

First In First Out(FIFO)

顺序存储结构

初始化

typedef struct 
{
	ElemType data[MaxSize];
	int front,rear;
}SqQueue;

void InitQueue(SqQueue &Q)
{
	Q.rear = Q.front = 0;
}

入队

bool EnQueue(SqQueue &Q,ElemType x)
{
	if ((Q.rear+1)%MaxSize==Q.front)
		return false;
	Q.data[Q.rear] = x;
	Q.rear = (Q.rear + 1)%MaxSize;
	return true;
}

出队

bool DeQueue(SqQueue &Q,ElemType &x)
{
	if (Q.rear == Q.front)
		return false;
	x = Q.data[Q.front];
	Q.front = (Q.front + 1) % MaxSize;
	return true;
}

查看队头

bool GetHead(SqQueue& Q, ElemType& x)
{
	if (Q.rear == Q.front)
		return false;
	x = Q.data[Q.front];
	return true;
}

其他判断队满的办法

链式存储结构(带头结点)

创建

typedef struct LinkNode
{
	ElemType data;
	struct LinkNode* next;
}LinkNode;
typedef struct 
{
	LinkNode* front, * rear;
}LinkQueue;

void InitQueue(LinkQueue &Q)
{
	Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
	Q.front->next = NULL;
}

入队

void EnQueue(LinkQueue &Q,ElemType x)
{
	LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));
	s->data = x;
	s->next = NULL;
	Q.rear->next = s;
	Q.rear = s;
}

出队

bool DeQueue(LinkQueue &Q,ElemType &x)
{
	if (Q.front == Q.rear)
		return false;
	LinkNode* p = Q.front->next;
	x = p->data;
	Q.front->next = p->next;
	if (Q.rear == p)
		Q.rear = Q.front;
	free(p);
	return true;
}

双端队列

双端队列是允许从两端插入和删除的线性表

判断输出序列合法性

如果一个序列在栈中合法,那么在双端序列中一定合法

队列的应用

• 树的层次遍历

• 图的广度优先遍历

• 队列在操作系统中的应用:

  FCFS(first come first service)的策略轮流服务进程

特殊矩阵的压缩存储

普通矩阵的存储

最直观的方式是用二位数组

矩阵的行/列号大多是从1开始

对称矩阵的存储

ai,j = aj,i

我们可以只存储主对角线和上或下某个三角区

按行优先原则将各个元素存入一维数组中

数组的长度为(1+n)*n/2

将矩阵下标映射为数组下标:

是否-1要具体看题

三角矩阵的压缩存储

同上,在最后一个位置存储常量c

三对角矩阵的压缩存储

已知数组下标k,如何得到i,j:

稀疏矩阵的压缩存储

顺序存储-三元组<行,列,值>

链式存储-十字链表法

串

串就是存储字符的线性表

顺序存储

//静态数组实现
typedef struct 
{
	char ch[MAXLEN];
	int length;
}SString;

求子串

bool SubString (SString &Sub,SString S, int pos, int len)
{
	if (pos + len - 1 > S.length)
		return false;
	for (int i = pos; i < pos + len; i++)
		Sub.ch[i - pos+1] = S.ch[i];
	Sub.length = len;
	return true;
}

比较两个串的大小

int StrCompare(SString S,SString T)
{
	for(int i =1;i<=S.length&&i<=T.length;i++)
	{
		if (S.ch[i] != T.ch[i])
			return S.ch[i] - T.ch[i];
	}
	return S.length - T.length;
}

定位

int Index(SString S,SString T)
{
	int i = 1, n = StrLength(S), m = StrLength(T);
	SString sub;
	while (i<= n-m+1)
	{
		SubString(sub, S, i, m);
		if (StrCompare(sub, T) != 0)++i;
		else return i;
	}
	return 0;
}

链式存储

typedef struct StringNode
{
	char ch[4];
	struct StringNode* next;
}StringNode,*String;

ch作为数组旨在提高存储密度

朴素模式匹配算法

匹配一定长度的模式串,将主串中所有长度和模式串的子串和模式串比较,直到找到一个完全匹配的子串或所有的子串都不匹配

int Index(SString S,SString T)
{
	int i = 1, j = 1;
	while (i<=S.length&&j<=T.length)
	{
		if(S.ch[i]==T.ch[j])
		{
			++i; ++j;
		}
		else
		{
			i = i - j + 2;
			j = 1;
		}
	}
	if (j > T.length)
		return i - T.length;
	else
		return 0;
}

最坏时间复杂度:O(nm)

KMP算法

算法分析

在这种情况下,查找到模式串第六个字符才发现不匹配,那么主串的前几个子串都不匹配,可以直接从下图的位置继续匹配

对于这个例子,当出现这种情况,可以使i不变,j=3继续匹配

那么如果第五个元素匹配失败,可以使i不变,j=2继续匹配

也就是说,对于某个特定的模式串,某位位数不是1的字符如果匹配失败,可以使i不变,j赋给某个值继续匹配来节省计算

这个思想只和子串的内容有关系,和主串没有关系,也就是说,主串指针i不需要回溯

代码实现

int Index_KMP(SString S,SString T,int next[])
{
	int i = 1, j = 1;
	while (i<=S.length&&j<=T.length)
	{
		if (j == 0 || S.ch[i] == T.ch[j])
		{
			++i;
			++j;
		}
		else
			j = next[j];
	}
	if (j > T.length)
		return i - T.length;
	else
		return 0;
}

求next数组

4.2_3_求next数组_哔哩哔哩_bilibili

next数组的优化

在下面的例子中,j=3时匹配失败,应该使j=1

但我们可以发现,模式串的第一个和第三个字符都是a,所以i=3,j=1进行的匹配一定失败

因此,最好的方式是将next[3]=0,同理也应该使next[5]=1

这样得到的数组叫nextval数组

求nextval数组

nextval[1] = 0;
for (int j=2;j<=T.length;j++)
{
	if (T.ch[next[j]] == T.ch[j])
		nextval[j] = nextval[next[j]];
	else
		nextval[j] = next[j];
}

树

树的定义和基本术语

树的性质

树的结点数为总度数+1

度为m的树第i层至多有m^i-1个结点

高度为h的m叉树至多有(m^h-1)/m-1和结点

高度为h的m叉树至少有h个结点

高度为h,度为m的数至少有h+m-1个结点

二叉树

基本概念

几个特殊的二叉树

二叉树的性质

完全二叉树的性质

二叉树的存储结构

顺序存储

struct TreeNode
{
	ElemType value;
	bool isEmpty;
};

下面是完全二叉树的顺序存储

将普通二叉树的编号和完全二叉树对应,就可以顺序存储普通二叉树

对于普通二叉树的顺序存储,判断二叉树的结点是否有左/右子时,需要使用变量isEmpty判断

这种方法存储的二叉树可能有大量的内存浪费

链式存储

typedef struct BiTNode
{
	ElemType data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

typedef struct BiTNode
{
	ElemType data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

BiTree root = NULL;

//插入根结点
	root = (BiTree)malloc(sizeof(BiTNode));
	root->data = 1;
	root->lchild = NULL;
	root->rchild = NULL;
//插入新结点
	BiTNode* p = (BiTNode*)malloc(sizeof(BiTNode));
	p->data = 2;
	p->lchild = NULL;
	p->rchild = NULL;
	root->lchild = p;

还有三叉链表式的定义,便于查找父结点

typedef struct BiTNode
{
	ElemType data;
	struct BiTNode *lchild,*rchild;
	struct BiTNode* parent;
}BiTNode,*BiTree;

二叉树的先/中/后序遍历

//先序遍历
void PreOrder(BiTree T)
{
	if (T!=NULL)
	{
		visit(T);
		PreOrder(T->lchild);
		PreOrder(T->rchild);
	}
}

//中序遍历
void InOrder(BiTree T)
{
	if (T != NULL)
	{
		InOrder(T->lchild);
		visit(T);
		InOrder(T->rchild);
	}
}

//后序遍历
void PostOrder(BiTree T)
{
	if (T != NULL)
	{
		PostOrder(T->lchild);
		PostOrder(T->rchild);
		visit(T);
	}
}

应用:求树的深度

int treeDepth(BiTree T)
{
	if (T==NULL)
		return 0;
	int l = treeDepth(T->lchild);
	int r = treeDepth(T->rchild);
	return l > r ? l + 1 : r + 1;
}

二叉树的层序遍历

一层一层的遍历

用一个辅助队列,根节点入队,若队列非空,队头出队,访问队头,队头节点的左右子依次入队,直至队列为空

void LevelOrder(BiTree T)
{
	LinkQueue Q;
	InitQueue(Q);
	BiTree p;
	EnQueue(Q, T);
	while (!isEmpty(Q))
	{
		DeQueue(Q, p);
		visit(p);
		if (p->lchild != NULL)
			EnQueue(Q, p->lchild);
		if (p->rchild != NULL)
			EnQueue(Q, p->rchild);
	}
}

由遍历序列构造二叉树

只给定一个遍历序列,不能确定唯一的二叉树

必须至少给出以下三种组合中的一种才能确定唯一的二叉树

e.g.


线索二叉树

二插链表存储的二叉树的叶结点的左右指针为空,我们可以让这些指针指向结点的前驱和后继,从而使二叉树获得一些性质

typedef struct ThreadNode
{
	ElemType data;
	struct ThreadNode* lchild, * rchild;
	int ltag, rtag;
}ThreadNode,*ThreadTree;

二叉树的线索化

//以下为中序线索化
ThreadNode* pre = NULL;

void InThread(ThreadTree T);
void visit(ThreadNode* q);

void CreateInThread(ThreadTree T)
{
	pre = NULL;
	if(T!=NULL)
	{
		InThread(T);
		if (pre->rchild == NULL)
			pre->rtag = 1;
	}
}
void InThread(ThreadTree T)
{
	if(T!= NULL)
	{
		InThread(T->lchild);
		visit(T);
		InThread(T->rchild);
	}
}

void visit(ThreadNode* q)
{
	if (q->lchild == NULL)
	{
		q->lchild = pre;
		q->ltag = 1;
	}
	if (pre!=NULL&&pre->rchild==NULL)
	{
		pre->rchild = q;
		pre->rtag = 1;
	}
	pre = q;
}

先序线索化会出现循环遍历的问题,可以改为

void PreThread(ThreadTree T)
{
	if(T!=NULL)
	{
		visit(T);
		if (T->ltag == 0)
			PreThread(T->lchild);
		PreThread(T->rchild);
	}
}

找前驱和后继

以下是找中序后继

ThreadNode *Firstnode(ThreadNode *p)
{
	while (p->ltag == 0)p = p->lchild;
	return p;
}

ThreadNode *Nextnode(ThreadNode *p)
{
	if (p->rtag == 0)return Firstnode(p->rchild);
	return p->rchild;
}

由此可以实现中序遍历的另一种方法

void Inorder(ThreadNode *T)
{
	for (ThreadNode* p = Firstnode(T); p != NULL; p = Nextnode(p))
		visit(p);
}

以下是找中序前驱

ThreadNode* Lastnode(ThreadNode* p)
{
	while (p->rtag == 0)p = p->rchild;
	return p;
}

ThreadNode *Prenode(ThreadNode *p)
{
	if (p->ltag == 0)return Lastnode(p->lchild);
	return p->lchild;
}

同理也有了逆向中序遍历二叉树的方法

先序找前驱和后序找后继需要二叉树为三叉链表存储,也就是需要父节点地址

树的存储结构

双亲表示法(顺序存储)

typedef struct 
{
	ElemType data;
	int parent;
}PTNode;
typedef struct 
{
	PTNode nodes[MaxSize];
	int n;
}PTree;

孩子表示法(顺序+链式存储)

struct CTNode
{
	int child;
	struct CTNode* next;
};

typedef struct 
{
	ElemType data;
	struct CTNode* FirstChild;
}CTBox;

typedef struct
{
	CTBox nodes[MaxSize];
	int n, r;
}CTree;

孩子兄弟表示法(链式存储)/树转化为二叉树

typedef struct CSNode
{
	ElemType data;
	struct CSNode* firstchild, * nextsibling;
}CSNode,*CSTree;

森林和二叉树的转换

将各个树的根视作一个树的同一层,这样就可以用类似树转化为二叉树的方法转化为二叉树

树的遍历

树是递归定义的数据结构,所以可以用递归算法实现遍历

先根遍历

void PreOrder(TreeNode *R)
{
	if (R!=NULL)
	{
		visit(R);
		while (R还有下一个子树)
			PreOrder(T);
	}
}

遍历顺序和与之对应的二叉树的先序遍历相同

后根遍历

void PreOrder(TreeNode *R)
{
	if (R!=NULL)
	{
		while (R还有下一个子树)
			PreOrder(T);
        visit(R);
	}
}

遍历顺序和与之对应的二叉树的中序遍历相同

层次遍历(树的广度优先遍历)

和二叉树的层次遍历类似

森林的遍历

哈夫曼树

带权路径长度

哈夫曼树,也称最优二叉树,是在含有n个带权结点的二叉树中,WPL最小的二叉树

构造哈夫曼树

哈夫曼编码

固定长度编码:每个字符用相等长度的二进制数字表示,ASC2就是固定长度编码

当有了编码的定义,可以用树来分辨得到的编码

但每个英文字母的使用频率不一样,所以可以用较少的编码表示使用较多的字母,用较多的编码表示使用较少的字母

并查集

并查集是一种集合数据结构,只实现”并”和”查”两种操作

如果我们想查一个元素所属集合,或者合并两个集合,该如何做?

我们可以用树来表示这种数据结构,问题就会简单很多

int UFSets[MaxSize];

void Initial(int s[])
{
	for (int i = 0; i < MaxSize; i++)
		s[i] = -1;
}

每个结点存储父节点的下标,这样查某个元素的集合,就可以变成查这个元素的根结点,合并集合,直接更改结点的父节点即可

int Find(int S[],int x)
{
	while (S[x] >= 0)
		x = S[x];
	return x;
}

void Union(int S[],int Root1,int Root2)
{
	if (Root1 == Root2)
		return;
	S[Root2] = Root1;
}

Union操作优化

当树很高的时候,显然Find操作的耗时将会增加,所以在合并树的时候,我们要避免增加树的高度,也就是让小树合并到大树上

根据上图,根结点由于没有父结点,所以父节点的值为-1,我们可以利用这个空位,改成用绝对值存储树的结点数量,这样就可以方便的得知树的大小(教程中说的是存储结点的数量,但也许存储树的深度会好些?不过问题在于如何得知树的深度)

void Union(int S[],int Root1,int Root2)
{
	if (Root1 == Root2)
		return;
	if(S[Root2]>S[Root1])
	{
		S[Root1] += S[Root2];
		S[Root2] = Root1;
	}
	else
	{
		S[Root2] += S[Root1];
		S[Root1] = Root2;
	}
}

Find操作优化(压缩路径)

当树很高的时候,查找路径会很长

我们不需要保持树的结构,因为我们只是用树的性质表示并查集,而并查集中的元素是相互没有关系的

比如下面的树,很高,所以我们可以进行一些调整

我们可以将某些节点(准确的说是查找路径上的节点)的父节点直接设为根节点

int Find(int S[], int x)
{
	int root = x;
	while (S[root] >= 0)
		root = S[root];
	while (x!=root)
	{
		int t = S[x];
		S[x] = root;
		x = t;
	}
	return root;
}

图

基本概念

几种特殊形态的图

图的存储结构

邻接矩阵

typedef struct
{
	char Vex[MaxSize];
	int Edge[MaxSize][MaxSize];
	int vexnum, arcnum;
}MGraph;

邻接表

//边/弧
typedef struct ArcNode
{
	int adjvex;
	struct ArcNode* next;
}ArcNode;

//顶点
typedef struct VNode
{
	VertexType data;
	ArcNode* first;
}VNode,AdjList[MaxSize];

//图
typedef struct
{
	AdjList vertices;
	int vexnum, arcnum;
}ALGraph;

十字链表

邻接多重表

广度优先遍历BFS

void BFS(Graph G,int v)
{
	visit(v);
	visited[v] = true;
	EnQueue(Q, v);
	while (!isEmpty(Q))
	{
		DeQueue(Q, v);
		for (Vex w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
			if (!visited[w])
			{
				visit(w);
				visited[w] = true;
				EnQueue(Q, w);
			}
	}
}

BFS遍历序列不唯一

如果一个图不是连通图,或者起点与某些结点间没有路径,BFS无法全部遍历,用以下函数解决

bool BFSTraverse(Graph G)
{
	for (int i = 0; i < G.vexnum; ++i)
		visited[i] = false;
	InitQueue(Q);
	for (int i =0;i<G.vexnum;++i)
		if (!visited[i])
		{
			BFS(G, i);
		}
}

广度优先生成树

我们用这种方法访问一个图时,会通过n-1条边

去掉没有通过的边,我们就得到了一个生成树

BFS遍历序列不唯一,所以广度优先生成树不唯一

广度优先生成森林同理

深度优先遍历DFS

void DFSTravverse(Graph G)
{
	for (v = 0, v < G.vexnum; ++v)
		visited[v] = false;
	for (v = 0;v<G.vexnum;++v)
		if (!visited[v])
		{
			DFS(G, v);
		}
}

void DFS(Graph G,int v)
{
	visit(v);
	vivited[v] = true;
	for (w=FirstNeighbor(G,v);w>=0;NextNeighbor(G,v,w))
		if(!visited[w])
		{
			DFS(G, w);
		}
}

同样,DFS遍历序列不同,深度优先生成树不同

最小生成树

一个图生成的树的集合中,权值总和最小的树称为这个图的最小生成树

同一个图的最小生成树可能不唯一

Prim算法

适用于边稠密图

Kruskal算法

适用于边稀疏图

最短路径问题

BFS

BFS有一定的局限性,不能适用于带权图

Dijkstra算法

第一轮:遍历所有的数组信息,找到还没确定最短路径,且dist最小的顶点Vi,另final[i] = true

检查所有邻接自Vi的顶点,若其final的值为false,则更新dist和path信息

第二轮同理,循环往复直至final中所有的值都为true

如果带权图中有负权值的边,则Dijkstra算法可能会失效

Floyd算法

佛洛依德算法用到了动态规划思想

#初始:两顶点间不允许有中转点,记录两顶点间的路径长度

#0:若允许在V0中转,求A^0和path^0

#1:若允许在V1中转,求A^1和path^1

#2:若允许在V2中转,求A^2和path^2

最后用递归的方式找到完整路径

Floyd算法不能解决有负权回路的图

有向无环图循环表达式

算术表达式可以用树来表示

上图中的表达式有一些重复的部分,((c+d)*e),所以可以删除一个子树

于是这个树就变成了一个图,继续合并,成为以下有向无环图

最终的有向无环图中不会出现重复的操作数

最终得到的有向无环图可能不唯一

拓扑排序

AOV网

拓扑排序

简单的说,拓扑排序就是找到做事的先后顺序

逆拓扑排序

拓扑排序和逆拓扑排序的序列可能不唯一

拓扑排序和逆拓扑排序的图不能有环

关键路径

AOE网

求关键路径

若关键活动耗时增加,再整个工程的工期将增长

缩短关键活动的时间,就能缩短整个工程的工期

当缩短到一定程度时,关键活动可能变成非关键活动

可能有多条关键路径,只提高一条关键路径上的关键活动的速度并不能缩短整个工程的工期,只有加快那些包括在所有关键路径上的活动才能缩短工期的目的

查找

顺序查找

也叫线性查找,通常用于线性表

typedef struct
{
	ElemType* elem;
	int TableLen;
}SSTable;

int Search_Seq(SSTable ST,ElemType key)
{
	int i;
	for (i = 0; i < ST.TableLen && ST.elem[i] != key; i++);
	return i == ST.TableLen ? -1 : i;
}

“哨兵”方法

顺序查找的优化

对有序表

如果一个数字列表是有序的,比如从小到大,如果我们要查找21,但已经查到29了也没有查到,说明之后也不会查找,可以直接判断查找失败

这中方法有效避免了查找失败情况下不必要的查找

被查概率不相等

如果我们已知列表中元素被查的概率,那么我们也可以将被查概率高的元素放在列表前面

显然,如果你用被查概率排序元素,就无法同时使用有序表

折半查找

又称”二分查找”,仅适用于有序表

对于查找一个有序表中的元素,我们可以先查找表中最中间的元素,或者说将中间的被查元素与查找目标做比较,如果被查元素较大,就将有序表以中间的元素为中心切半,查找较小边的最中间的元素,往复此步,被查元素较小同理

 int Binary_Search(SSTable L,ElemType key)
{
	 int low = 0, high = L.TableLen - 1, mid;
	 while (low<=high)
	 {
		 mid = (low + high) / 2;
		 if (L.elem[mid] == key)
			 return mid;
		 else if (L.elem[mid] > key)
			 high = mid - 1;
		 else
			 low = mid + 1;
	 }
	 return -1;
}

查找效率分析


查找判定树的构造


分块查找

将一个序列分成若干个区间,区间间是有序的,区间内是无序的

查找时,先比对查找目标在哪个块中,在相应块中顺序查找

二叉排序树BST

BST的查找

typedef struct BSTNode
{
 int key;
 struct BSTNode* lchild, * rchild;
}BSTNode, * BSTree;

BSTNode *BST_Search(BSTree T,int key)
{
	while (T != NULL && key != T->key)
	{
		if (key < T->key)T = T->lchild;
		else T = T->rchild;
	}
	return T;
}

由于BST的递归特性,我们也可以递归实现算法

BSTNode *BSTSearch(BSTree T,int key)
{
	if (T == NULL)
		return NULL;
	if (key == T->key)
		return T;
	else if (key < T->key)
		return BSTSearch(T->lchild, key);
	else
		return BSTSearch(T->rchild, key);
}

BST的插入

int BST_Insert(BSTree &T,int k)
{
	if (T == NULL)
	{
		T = (BSTree)malloc(sizeof(BSTNode));
		T->key = k;
		T->lchild = T->rchild = NULL;
		return 1;
	}
	else if (k == T->key)
		return 0;
	else if (k < T->key)
		return BST_Insert(T->lchild, k);
	else
		return BST_Insert(T->rchild, k);
}

BST构造

void Creat_BST(BSTree &T,int str[],int n)
{
	T = NULL;
	int i = 0;
	while (i<n)
	{
		BST_Insert(T, str[i]);
		i++;
	}
}

BST的删除

首先要查找这个结点,如果目标结点是叶子节点,那么可以直接删除,如果是其他情况

当我们对BST进行查找的时候,显然ASL的大小取决与BST的深度,为了减少ASL,我们要减少BST的深度

平衡二叉树

平衡二叉树的插入

在插入结点后，从插入点往回找到第一个不平衡结点，调整该节点为根的子树，每次调整的对象都是最小不平衡子树

调整最小不平衡树

调整最小不平衡树分为4种情况

调整LL和RR

调整LR和RL

平衡二叉树的删除

红黑树

在平衡二叉树的中,每插入/删除一个结点,很可能很破坏AVL的特性,需要平凡调整树的形态

在红黑树中,插入/删除很多时候不会破坏红黑特性,即使需要调整,一般都可以在常数级时间内完成

定义

红黑树是一种二叉排序树,并且

1. 每个结点要么是红的,要么是黑的
2. 根结点是黑色的;叶结点(外部结点,NULL结点,失败结点)是黑色的
3. 不存在两个相邻的红结点(也就是说红结点的父结点和孩子结点均是黑色)
4. 对每个结点,从该结点到任意叶结点的简单路径上,所含黑结点的数目相同

struct RBNode
{
	int key;
	RBNode* parent;
	RBNode* lChild;
	RBNode* rChild;
	int color;// 0/1-black/red 
};

结点的黑高bh:从某结点出发(不含该结点)到达任意空叶结点的路径上黑结点总数

如果根结点的黑高为h，内部结点数至少为2^h-1个

性质

1. 从根结点到叶结点的最长路径不大于最短路径的2倍
2. 有n个内部结点的红河树高度h<=2log2(n+1)

查找

与BST、AVL相同，从根出发，左小右大，若查找到一个空叶结点，则查找失败

插入

插入的每个新结点,如果破坏红黑树的特性,一定是破坏不红红（定义中的第三条）的特性

删除

考研不考，所以没教

B树

我们讨论过许多二叉的排序树，现在我们尝试将排序树的定义发散到m叉树

如果每个结点的关键字大少，导致树变高，要查找很多层，效率低

可以规定m叉查找树中，除了根结点外，任何结点至少有[m/2]个分叉,即至少有[m/2]-1个关键字

树不平衡，也会使查找树过高

规定m叉查找树中，对于任何一个结点，其所有子树的高度都要相同

满足以上两个条件的m叉查找树，称为B树

定义

B树，或称多路平衡查找树，B树中所有结点的孩子个数的最大值称为B树的阶，通常用m表示，一棵m阶B树或为空树，或满足以下特性

1. 树中每个结点至多有m棵子树，即至多有m-1个关键字
2. 若根结点不是终端结点，则至少有两课子树
3. 除了根结点外，任何非叶结点至少有[m/2]棵子树,即至少有[m/2]-1个关键字
4. 所有叶结点出现在同一层次上，并且不带信息
5. 所有非叶结点的结构如下

特性

插入

我们现在讨论5阶B树

新元素一定是插入到最底层”终端结点”,用”查找”确定插入位置

删除

7.4_2_B树的插入删除_哔哩哔哩_bilibili

如果删除的关键字在终端节点,则直接删除关键字要注意关键字个数是否低于下限[m/2]-1

如果要删除的关键字不是终端节点,则用直接前驱或直接后继来代替被删除的关键字

相当于删除了直接前驱或直接后继,最终会删除到终端结点

直接前驱:当前关键字左侧指针所指子树中”最右下”的元素

直接后继:当前关键字右侧指针所指子树中”最左下”的元素

所以所有的删除非终端结点的情况都可以转换为删除中断结点的情况

如果删除终端结点后关键字个数低于下限:


B+树

定义

一棵m阶B+树需要满足如下条件:

1. 每个分支结点最多有m棵子树

2. 如果一个结点不是叶结点,则该节点至少有两棵子树,其他每个分支结点至少有[m/2]棵子树

3. 结点的子树个数与关键字个数相等

4. 所有的叶子结点包含全部的关键字及指向相应记录的指针,叶子结点中将关键字按大小顺序排列,并且相邻叶子结点按大小顺序相互链接起

5. 所有分支结点中仅包含它的各个子结点中关键字的最大值及指向其子结点的指针

查找

可以用类似分块查找的方式,也可以用叶结点链表顺序查找

散列查找

简介

散列表Hash Table,又称哈希表,是一种数据结构,其数据元素的关键字与其存储地址直接相关

通过散列函数(哈希函数)建立关键字与存储地址的联系

如果不同的关键字通过散列函数映射到同一个值,则称它们是”同义词”

通过散列函数确定的位置已经存放了其他元素,则称这种情况为”冲突”

用拉链法(链接法,链地址法)处理冲突:把所有同义词放在一个链表中

通过计算ASL可以发现,用拉链法处理,如果链越长,则ASL越大,所以我们需要一个更合理的哈希函数来减少同义词

散列查找是用空间换时间的算法,理论上来说,散列表越长,冲突的可能性越低,时间复杂度越小

装填因子:表中记录数/散列表长度

常见的散列函数

除留余数法

H(key) = key&p

散列表长度为m,取一个不大于m但最接近或等于m的质数p

取质数是为了减少冲突

直接定址法

H(key) = key 或 H(key) = a*key + b

a和b是常数,这种方法计算简单,不会产生冲突,适合关键字分布基本连续的情况,若关键字分布不连续,空位较多,会造成存储空间的浪费

数字分析法

选取数码分布较为均匀的若干位作为散列地址

平方取中法

取关键字的平方值的中间值作为散列地址

中间值具体取多少位视情况而定,这种方法得到的散列地址与关键字的每位都有关系,因此散列地址分布比较均匀

冲突处理-开放定址法

我们也可以选用其他的冲突处理方法尝试减少时间复杂度

开放定址法,是指可存放新表项的空闲地址既向它的同义词开放,又向它的非同一次表项开放

线性探测法

di = 0,1,2,3,4,…,m-1

用线性探测法查找时,如果向后查找到空结点,就可以判断查找失败

在删除时,如果我们直接删除查找到的元素,以后可能出现表中有目标元素但查找到空结点的情况

可以在删除元素的结点上作bool标记,表明该结点删除过元素

这中方法的查找效率极低

平方探测法

di = 0^2,1^2,-1^2,2^2,-2^2….k^2,-k^2

如果用平方探测法,哈希表长度m必须是一个可以表示成4j+3的素数,才能探测到所有位置

再散列法

除了原始的散列函数之外,多准备几个散列函数,当散列函数冲突时,用下一个散列函数计算一个新地址,直到不冲突为止

排序

排序是将表中的元素按关键字重新排列,使元素有序的过程

算法的稳定性:排序时可能会出现元素关键字相同的情况,如果一个算法排序总是使两个关键字相同的元素的顺序不变,就称这个算法是稳定的,否则是不稳定的

插入排序

当一个待排序的记录按其关键字大小插入到前面已排号序的子序列中,直到全部记录插入完成

void InsertSort(int A[],int n)
{
	int i, j, temp;
	for(i=1;i<n;i++)
	{
		if(A[i]<A[i-1])
		{
			temp = A[i];
			for (j = i - 1; j >= 0 && A[j] > temp; --j)
				A[j + 1] = A[j];
			A[j + 1] = temp;
		}
	}
}

最好时间复杂度O(n),最坏时间复杂度O(n^2)

折半插入排序

我们可以先用折半查找找到应该插入的位置,再移动元素,以此来优化算法

void InsertSort(int* a, int n)
{
	int i, j, temp;
	for (i = 1; i < n; i++)
	{
		if (a[i] > a[i - 1])continue;
		temp = a[i];

		int low = 0, high = i - 1, mid;
		while (low <= high)
		{
			mid = (low + high) / 2;
			if (a[mid] > temp)
				high = mid - 1;
			else
				low = mid + 1;
		}
		for(j = i;j>low;j--)
		{
			a[j] = a[j-1];
		}
		a[low] = temp;
	}
}

希尔排序

如果我们要排序一个表,那么最好的情况就是这个表本来就是有序的,或者比较好的情况是这个表是基本有序的

希尔排序:将待排序表分割成若干形如L[i,i+d,i+2d,…,i+kd]的,也就是表中相距距离为d的元素组成的特殊子表,对各个子表分别进行插入排序,缩小增量d,重复上述过程,直到d=1为止

void ShellSort(int A[],int n)
{
	int d, i, j;
	for (d = n/2;d>=1;d/=2)
		for (i=d+1;i<n;++i)
		{
			if (A[i]<A[i-d])
			{
				A[0] = A[i];
				for (j = i - d; j > 0 && A[0] < A[j]; j -= d)
					A[j + d] = A[j];
				A[j + d] = A[0];
			}
		}
}

希尔排序是不稳定的

冒泡排序

void swap(int &a ,int &b)
{
	int temp = a;
	a = b;
	b = temp;
}

void BubbleSort(int A[],int n)
{
	for (int i = 0;i<n-1 ;i++)
	{
		bool flag = false;
		for (int j = n-1;j>i;j--)
		{
			if(A[j-1]>A[j])
			{
				swap(A[j - 1], A[j]);
				flag = true;
			}
		}

		if (!flag)
			return;
	}
}

冒泡排序是稳定的

快速排序

在待排序的表L中任意一个元素作为枢轴(通常取首元素),通过一趟排序将待排序表划分为独立的两部分,L1,L2,使L1中的所有元素都小于枢轴,L2的所有元素都大于枢轴,这个过程叫划分,重复在分出子表划分,直至排序完成

每次划分,都能将枢轴摆放到最终位置

int Partition(int A[],int low,int high)
{
	int pivot = A[low];
	while(low<high)
	{
		while (low < high && A[high] >= pivot)
			high--;
        A[low] = A[high];
		while (low < high && A[low] <= pivot)
			low++;
		A[high] = A[low];
	}
	A[low] = pivot;
	return low;
}

void QuickSort(int A[],int low,int high)
{
	if(low<high)
	{  
		int pivotpos = Partition(A, low, high);
		QuickSort(A, low, pivotpos - 1);
		QuickSort(A, pivotpos + 1, high);
	}
}

归并排序

归并排序通常使用二路归并

int* B = (int*)malloc(10*sizeof(int));
void Merge(int A[], int low, int mid, int high)
{
	int i, j, k;
	for (k = low;k<high;k++)
		B[k] = A[k];
	for (i = low,j = mid +1,k = low;i<=mid&&j<=high;k++)
	{
		if (B[i] <= B[j])
			A[k] = B[i++];
		else
			A[k] = B[j++];
	}
	while (i <= mid)A[k++] = B[i++];
	while (j <= high)A[k++] = B[j++];
}
void MergeSort(int A[],int low,int high)
{
	if (low >= high)return;
	int mid = (high + low) / 2;
	MergeSort(A, low, mid);
	MergeSort(A, mid+1, high);	
	Merge(A, low, mid, high);
}

简单选择排序

遍历序列n-1次,每次将最小的元素放入子序列

时间复杂度O(n^2)