概述

编程是为了利用计算机解决实际问题,而首先我们需要描述问题,然后建立抽象的数学模型并加以运算求解。其中既有数值计算部分,也有逻辑关系构造部分。

而数据结构就是根据数学逻辑性质构造的数据形式,它既有原子型,即不可再分型类型,也有结构型,即利用其他类型封装细节,进行信息屏蔽,有面向对象的程序设计思想。

数据都存放在内存中,与硬件关系密切,而所定义的数据结构只是表征了逻辑上的关系。实际的可以根据存储方式分为顺序存储,以及链式存储,即用链表实现。

这里将全部通过链表实现,以实现动态申请内存。

链表又可以用C语言的结构体指针进行构造,因此可以用C语言进行对数据结构的完整描述,以便加深对其理解,以及掌握实际的结构体的特点局限。

相比于顺序结构存储而言,链式存储能有效地对首尾端进行操作,而队列,栈等正是定义在首位两端的线性表操作。

对所有数据结构,将以C语言进行描述,并基于链表实现主要结构,线性结构、树型结构、图状结构等。

针对数据结构,需要对其进行相应的操作,如创建、销毁、查找、插入、删除等,这便是所谓的算法。可以根据空间复杂度、时间复杂度、频度等进行优化,而时间和空间常常起冲突,需要取舍。

通过宏定义状态返回判断操作是否成功,值传递进行运算,指针传递进行操作值返回。

#define OK 1
#define ERROR 0
typedef int Status;

学编程,未学数据结构,终是不成体系,写一些小的代码尚可,但如果遇到大的实验甚至是项目,调试便要许久。所以系统地学一遍数据结构一方面将储存一些代码储备,以便之后调用,同时也将进一步提高自己的编程能力。

但是学习数据结构和算法,往往会深陷其中,需要花费巨大的时间和精力,且无止境,对于非计算机专业的工科应用而言,更关注的应当是数据结构的实际应用。

因此数据结构应当搭配实际的软件编程应用进行学习,比如编译原理中用到的栈、线性表、树、串、散列表等,再比如操作系统中用到的栈、线性表、树、队列、散列表等。

应当根据原理构造相应的数据结构,同时通过实践数据结构的具体操作来验证相关原理。

线性表

线性表概述

线性表是一种常用的简单的数据结构,可以根据实际情况定义数据元素,而数据元素可以由若干个数据项组成,此时数据元素也被称为记录,含有大量记录的线性表又被称为文件。

这种数据结构灵活方便,长度可以动态改变,对线性表的数据元素不仅可以进行访问,还可以进行插入删除等操作。

线性顺序表可以通过申请一块连续内存来实现。

LinkList=(LNode*)malloc(LIST_INIT_SIZE*sizeof(LNode));
线性链表

线性链表的实现

链表不要求物理结构相邻,因此失去了顺序表随机存储的优点,同时它插入删除方式灵活,不再需要移动大量元素。

在C语言中,指针存储的是指向空间的地址,因此通过指针的索引方式,一个个结点也就是数据元素链接在了一起形成了链表。

对链表的操作有初始化、销毁、查找、插入、删除、修改、遍历等,用C语言实现代码可参考如下:

初始化:用两个结构体指针以此递推正向初始化。

Status InitLNList(LNLinkList L, int n){//初始化
	//建立带表头结点的单链线性表L,每个数据初始化为0
	LNLinkList p_new,p_old = L;
	for (int i = 0; i < n+1; i++){
		p_new = (LNLinkList)malloc(sizeof(LNLNode));
		p_new->data = 0;
		p_new->next = NULL;
		p_old->next = p_new;
		p_old = p_new;
	}
	return OK;

}

销毁:通过头指针以此访问指向数据元素,并释放相应空间,直至指针值为NULL。

Status DestroyLNList(LNLinkList L){//销毁
	LNLinkList p = L;
	while( p->next!= NULL){
		LNLinkList p_delete = p->next;
		p->next= p->next->next;
		free(p_delete);
	}
	return OK;

}

查找:通过头指针以此访问指向数据元素,进行判断,若找到返回相应索引值,否则返回0。

int LocateLNElem(LNLinkList L, ElemType e){//查找数据
	//查找第一个值为e的元素
	//若找到则返回对应的位序,否则返回0
	LNLinkList p = L; int j = 0;
	for (; p->next != NULL; p = p->next, ++j)
		if (p->data == e) return j;
	if (p->data == e)
		return j;
	else
		return 0;

}

插入:初始化一个计数器,用头指针依次访问数据元素,直到计数器等于传递索引值,然后执行插入操作。改变结构体指针指向即可。

Status LNListInsert(LNLinkList L, int i, ElemType e){//插入数据
	//在带头结点的单链线性表L中第I个位置之前插入元素e
	//需要生成一个新结点
	LNLinkList p = L->next; int j = 0;
	for (; p&&j < i - 2; p = p->next, ++j);
	if (!p || j>i - 1) return ERROR;//i不在表长之内,返回ERROR
	LNLinkList  s = (LNLinkList)malloc(sizeof(LNLNode));
	s->data = e; s->next = p->next;
	p->next = s;
	return OK;

}

删除:初始化一个计数器,用头指针依次访问数据元素,直到计数器等于传递索引值,然后执行删除操作。改变结构体指针指向即可。

Status LNListDelete(LNLinkList L, int i, ElemType* e){//删除数据
	LNLinkList p = L; int j = 0;
	for (; p->next != NULL&&j<i-1; p = p->next, ++j);
	LNLinkList p_delete = p->next;
	*e = p_delete->data;
	p->next = p->next->next;
	free(p_delete);
	return OK;

}

修改:初始化一个计数器,用头指针依次访问数据元素,直到计数器等于传递索引值,然后执行修改操作。

Status SetLNElem(LNLinkList L, int i, ElemType e){//修改数据
	//L为带头结点的单链表的头指针
	//当第i个元素存在时,其值赋为e并返回OK,否则返回ERROR
	LNLNode* p = L->next; int j = 1;
	for (; p->next != NULL&&j<i; p = p->next, ++j);
	p->data = e;
	return OK;

}

遍历:用头指针进行依次访问数据元素,同时对每个数据元素执行操作相同因此可以传递函数指针作为参数,具体的操作另定义。

Status LNListTraverse(LNLinkList L, Status(*visit)(ElemType)){//依次访问数据
	//访问数据可以是一系列相同类型函数,因此用函数指针实现
	LNLinkList p = L->next;
	for (; p->next != NULL; p = p->next)
	if ((*visit)(p->data) == ERROR) return ERROR;
	return OK;

}
循环链表

一般的链表最后的尾结点值为NULL,然而为了简化某些操作,有时让尾结点指向头结点,以此构成循环链表。

相比一般的链表只能从当前节点往后递推,循环链表可以通过循环的方式推的前部结点,操作更加灵活。从而可以简化某些操作,比如线性表的合并。

循环链表的操作和一般链表基本相同,不同之处在于循环条件改为判断尾指针是否指向头结点。

p->next==L->next;
双向链表

一般链表的数据元素的成员只有一个结构体指针,而双向链表有两个结构体指针,一个指向前一个结点,一个指向后一个结点。

比循环链表的灵活性更好,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。

线性表中的队列、栈等是对同一个结构所定义的不同操作,因此可统一定义结点结构体成员有双向指针,再对操作进行各自定义。

typedef int ElemType;
typedef struct LNLNode{
	ElemType data;
	struct LNLNode *prior;
	struct LNLNode *next;
}LNLNode,*LNLinkList;

栈的实现

栈是限定尽在表尾进行插入或删除操作的线性表,表尾端称之为栈顶,表头端称之为栈底,不含元素的空表称之为空栈。

也可以借助双向链表实现,首先定义栈结构体:

typedef struct Stack{
	LNLinkList head;
	LNLinkList tail;
	int length;
}Stack,*StackList;

若构造的栈长度不限,那么length就代表栈中元素的长度,如果构造的长度有限,那么length就代表栈的深度。

选取头尾指针进行初始化,操作仅有清空、插入、删除、判空等,用C语言描述如下:

初始化 :对头尾指针及对应结构体成员构造即可完成初始化,这里采取栈长度不定的实现方式。

Status InitStack(StackList S){//初始化一个空栈
	S->head = S->tail=(LNLinkList)malloc(sizeof(LNLNode));
	S->tail->next = NULL;
	S->tail->data = 0;
	S->length = 0;
	return OK;

}

清空:首先让尾指针等于头指针,栈顶与栈底重合,然后借助线性表的销毁,实现自栈底至栈顶元素的清除。

Status ClearStack(StackList S){//清空,栈底至栈顶
	S->tail = S->head;
	return DestroyLNList(S->head);

}

判空:判空操作十分有用,因为只有在栈不为空时print、pop等操作才有意义。

Status StackEmpty(StackList S){//判断是否栈空

	if (S->head == S->tail)
		return EMPTY;
	else
		return NEMPTY;
}

打印:打印栈中内容,便于代码调试类似线性表实现。

Status PrintStack(StackList S){//打印栈中内容,栈底至栈顶
	LNLinkList P = S->head;
	int i = 0;
	while (P->next != NULL){
		printf("index%d:%d\n", ++i, P->data);
		P = P->next;
	}
	return OK;

}

入栈:入栈操作类似于线性表的插入,只不过需根据tail尾指针进行操作,最后还需将tail指针后移。

Status Push(StackList S, ElemType e){//入栈
	S->tail->data = e;
	LNLinkList  p = (LNLinkList)malloc(sizeof(LNLNode));
	p->data = 0;
	p->next = NULL;
	S->tail->next= p;
	p->prior = S->tail;
	S->tail = S->tail->next;
	S->length += 1;
	return OK;

}

出栈:出栈操作类似于线性表的删除,元素值通过e进行返回。只不过需根据tail尾指针进行操作,最后还需将tail指针前移,所以栈需要靠双向链表实现。

Status Pop(StackList S, ElemType* e){//出栈
	if (StackEmpty(S) == EMPTY) return ERROR;
	*e = S->tail->data ;
	LNLinkList p_delete = S->tail;
	S->tail=S->tail->prior;
	S->tail->next = NULL;
	S->length -= 1;
	free(p_delete);
	return OK;

}

栈结构具有后进先出的固有特性,因此能够很方便地进行某些程序的作用域设计,如函数的嵌套递归调用以及编译原理中的表达式求值等。

队列

队列的实现

队列是模拟日常生活中的排队状况,先进先出,在尾端进行元素的添加,而在头端进行元素的删除,因此也可以借助双向链表进行实现。

typedef struct Queue{
	LNLinkList head;
	LNLinkList tail;
	int length;
}Queue,*QueueList;

其操作和栈的操作基本类似,不同之处在于一般定义的队列长度为定值,在队列满时无法进行尾端添加操作。

初始化:在初始化时,习惯定义结构体指针的同时就申请内存,因此tail、head指向的元素即为当前需要操作的内容,而next指向null。

Status InitLQueue(QueueList Q, int n){//初始化
	Q->tail = Q->head=(LNLinkList)malloc(sizeof(LNLNode));
	Q->head->next = NULL;
	Q->length = n;
	return OK;
}

打印:打印队列内容,调试代码用。

Status PrintQueue(QueueList Q){//打印,测试用,头至尾
	LNLinkList p = Q->head;
	while (p != Q->tail){
		printf("%d\n", p->data);
		p = p->next;
	}
	return OK;
}

判空:根据头指针及尾指针确定队列个数,以及队列的实际状况是空还是满。

int QueueLength(QueueList Q){//队列长度
	LNLinkList p = Q->head; int j = 0;
	while (p != Q->tail){
		p = p->next; j++;
	}
	return j;
}

Status QueueEmpty(QueueList Q){//判断是否为空
	if (QueueLength(Q) == 0)
		return EMPTY;
	else 
		return NEMPTY;
}

添加:当队列不满时,在队尾添加新元素,同时多申请一块内存做指向。

Status EnQueue(QueueList Q, ElemType e){//添加队尾新元素
	int len = QueueLength(Q);
	if (len >= Q->length)//队列已满
		return ERROR;
	else{
		Q->tail->next = (LNLinkList)malloc(sizeof(LNLNode));
		Q->tail->next->next = NULL;
		Q->tail->data = e;
		Q->tail = Q->tail->next;
	}
	return OK;
}

移除:当队列不空时,从队首移除元素,同时释放相应的内存。

Status DeQueue(QueueList Q, ElemType* e){//移除队首元素
	if (QueueLength(Q) ==0)//队列已空
		return ERROR;
	LNLinkList p_delete = Q->head;
	Q->head = Q->head->next;
	free(p_delete);
	return OK;
}

清除:需要清除整个队列时可以借助于线性表的销毁操作,同时令尾指针等于头指针。

Status ClearQueue(QueueList Q){//清除所有队列内容
	Q->tail = Q->head;
	return DestroyLNList(Q->head);
}

上述实现是采取动态实现,即需要操作时再申请内存,如果事先规定存储的数据量那么可以在初始化的时候就分配好内存,push及pop操作不再申请或是释放内存。

此时可以将尾指针的next指向头指针,构成循环队列的形式,只需要改变head及tail的指向结构即可。

队列这种先入先出的结构,具有很强的秩序性,在实际的程序设计中也得到广泛的应用,如操作系统的消息队列、任务队列等,常用作模拟离散事件的驱动程序。

树的概述

线性表是线性关系 ,即只有一个后继节点和前驱节点,而树结构则是一种非线性数据结构。

树结构能够形象地表示实际生活中的分支关系,在编译原理的语法表示中也得到了广泛的应用。流行的机器学习算法决策树等更是一种智能的树结构。

树是n个节点的有限集,其某个分支子集称为子树,因此它的定义是一种递归的定义,自然也可以用递归的方式实现。

节点的子树的根称为该节点的孩子,相应地,该节点称为孩子的双亲。树中节点的最大层次称为深度或高度。末节点称为叶子或终端节点。

二叉树

二叉树的实现

二叉树是一种树型结构,它的特点是每个节点至多只有两棵子树,并且其子树有左右之分,其次序不能任意颠倒。

长满叶子的树,即一棵深度为k且有\(2^{k}-1\)个节点的二叉树称为满二叉树,其特点是每一层上的节点数都是最大节点数。

二叉树节点可以用二叉链表的结构实现:

//二叉链表存储表示                                                                                                                                                                                                        
typedef struct BiTNode{
	ElemType data;
	int height;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree,**BiTreeP;

初始化:接下来以深度为参数构造一棵满二叉树:

Status InitBiTree(BiTree T,int n){//构造一棵空二叉树,n为高度
	if (n >1){
		//递归创建,先序实现
		T->data = n; T->height = n; PrintTree(T->data);
		T->lchild = (BiTree)malloc(sizeof(BiTNode));
		T->lchild->lchild = NULL; T->lchild->rchild = NULL;
		InitBiTree(T->lchild, n - 1);
		T->rchild = (BiTree)malloc(sizeof(BiTNode));
		T->rchild->lchild = NULL; T->rchild->rchild = NULL;
		InitBiTree(T->rchild, n - 1);
	}
	else if (n == 1){//叶节点
		T->data = n; T->height = 1; PrintTree(T->data);
	}
	return OK;
}

遍历:在实现树结构的过程中用了递归的方法,而根据访问根节点的时间,又可以分为先序、中序、后序。

Status PreOrderTraverse(BiTree T, Status (*visit)(ElemType)){//先序遍历
	if (T){
		visit(T->data);                                                     
		PreOrderTraverse(T->lchild, visit);
		PreOrderTraverse(T->rchild, visit); 
	}
	return OK;
}

Status InOrderTraverse(BiTree T, Status(*visit)(ElemType)){//中序遍历
	if (T){
		InOrderTraverse(T->lchild, visit);
		visit(T->data);
		InOrderTraverse(T->rchild, visit);
	}
	return OK;
}

Status PostOrderTraverse(BiTree T, Status(*visit)(ElemType)){//后序遍历
	if (T){
		PostOrderTraverse(T->lchild, visit);
		PostOrderTraverse(T->rchild, visit);
		visit(T->data);
	}
	return OK;
}
二叉排序树

二叉排序树BST的实现

二叉排序树是一种动态查找表,即是在查找过程中动态生成的,它相比于一般的二叉树有如下的特点:

左子树若不为空,则左子树上所有节点的值均小于其根节点的值;若其右子树不为空,则左子树上所有节点的值均小于其根节点的值;左右子树分别也为二叉排序树。

可以用一般的二叉树的二叉链表进行存储二叉排序树的结构,但是其查找、插入、删除的操作却与线性表有着相当的不同。

查找:二叉排序树是查找数据时动态生成的树结构,因此先构造树的查找操作:

Status SearchBST(BiTree T, KeyType key, BiTree f, BiTreeP p){//查找,p作为查找值返回,便于插入
	if (!T){//查找不成功
		*p = f;
		return FALSE;
	}
	else if (T->data == key){
		*p = T;//查找成功
		return TRUE;
	}
	else if (T->data > key)
		return SearchBST(T->lchild, key, T, p);//在左子树中继续查找
	else
		return SearchBST(T->rchild, key, T, p);//在右子树中继续查找

}

通过递归的方式进行查找,先定义递归的结束位置,即查找到叶节点仍未成功,然后根据实际的值与根节点值比较,在子树中查找,最后无论查找成功与否,返回查找到的位置p。

插入:查找返回的地址p是为了后续插入、删除的操作,接下来构造插入函数:

Status InsertBST(BiTreeP T_p, ElemType e){//插入
	BiTreeP p = (BiTreeP)malloc(sizeof(BiTree));
	if (!SearchBST(*T_p, e, NULL, p)){
		BiTree s = (BiTree)malloc(sizeof(BiTNode));
		s->data = e; s->lchild = s->rchild = NULL;
		if (!(*p)) *T_p = s;
		else if ((*p)->data > e)
			(*p)->lchild = s;
		else
			(*p)->rchild = s;
		return TRUE;
	}
	else
		return FALSE;
}

申请一块内存s作为新的节点,由于二叉链表结构没有定义双亲成员,所以只能用二级指针实现对象的引用,从而获得返回地址的信息。

删除:二叉排序树的删除操作与插入类似,同样需要利用返回的查找地址,不同之处在于删除源节点之后需要转接左右子树。

Status Delete(BiTreeP p){//删除某一节点,并重接其子树
	if (!(*p)->rchild){
		BiTree p_delete = *p;
		*p = (*p)->lchild;
		if (p_delete)
			free(p_delete);
	}
	else if (!(*p)->lchild){
		BiTree p_delete = *p;
		*p = (*p)->rchild;
		if (p_delete)
			free(p_delete);
	}
	else{
		BiTree q = *p,s=(*p)->lchild;
		while (s->rchild){
			q = s; s = s->rchild;
		}
		(*p)->data = s->data;
		if (q != (*p))
			q->rchild = s->lchild;
		else
			q->lchild = s->lchild;
		if (s)
			free(s);
	}
	return TRUE;
}

需要考虑左右子树是否为空,否则会出现free一块空内存造成程序出错。

结合遍历执行删除操作就能很容易地删除整棵二叉排序树:

Status DeleteBST(BiTreeP T_p, KeyType key){//删除的递归过程
	if (!(*T_p))return FALSE;
	else{
		if ((*T_p)->data == key)
			return Delete(T_p);
		else if ((*T_p)->data > key)
			return DeleteBST(&((*T_p)->lchild), key);
		else
			return DeleteBST(&((*T_p)->rchild), key);
	}
	return TRUE;
}
平衡二叉树

平衡二叉树AVL的实现

二叉排序树插入的始终是叶子节点,因此尽管叶子上数值相同,但插入顺序不同也会造成二叉树最后形态的不同。

更有一种极端情况,按序插入,那么二叉树就退化成了但链表,树的灵活性将大大丧失。

为了防止这种现象的发生,人们提出了平衡二叉树AVL的概念,即不论如何插入、删除,始终保持一棵较为规范的二叉树的形状。

至于具体的“规范”定义如下:

左右子树都是平衡二叉树,且左右子树的深度之差的绝对值不超过1。

为了定量描述深度之差,定义二叉树上节点的平衡因子BF为左子树减去右子树深度,只可能为-1、0、1,分别代表右高、相平、左高三种情况。

同时根据失去平衡后进行调整的规律归纳为四种情况:LL、LR、RR、RL,分别对应右单旋、双向旋转(先左后右)、左单旋、双向旋转(先右后左)。

而旋转操作实际上就是节点调换与其孩子的辈分关系,其中对应关系为右旋为左孩子,左旋为右孩子。

首先通过改变指针指向实现一系列旋转操作:

Status R_Rotate(BBSTreeP p){//右旋操作
	BBSTree lc = (*p)->lchild;
	(*p)->lchild = lc->rchild;
	lc->rchild = (*p);
	(*p) = lc;
	return TRUE;
}

Status L_Rotate(BBSTreeP p){//左旋操作
	BBSTree rc = (*p)->rchild;
	(*p)->rchild = rc->lchild;
	rc->lchild = (*p);
	(*p) = rc; 
	return TRUE;
}

接着我们需要识别当前的状况究竟是归纳中的哪种情况,利用当前节点的BF以及孩子的BF实现并根据情况作出相应的旋转:

Status LeftBalance(BBSTreeP T_p){//左平衡处理
	BBSTree lc = (*T_p)->lchild;
	if (!lc) return FALSE;
	switch (lc->bf){//检查左子树平衡度,并作相应平衡处理
	case LH:
		(*T_p)->bf = lc->bf = EH;
		R_Rotate(T_p); break;//单向右旋
	case RH:
		BBSTree rd = lc->rchild;
		switch (rd->bf){
		case LH:
			(*T_p)->bf = RH; lc->bf = EH; break;
		case EH:
			(*T_p)->bf = lc->bf = EH; break;
		case RH:
			(*T_p)->bf = EH; lc->bf = LH; break;
		}
		rd->bf = EH;
		L_Rotate(&((*T_p)->lchild));
		R_Rotate(T_p);
	}
	return TRUE;
}

Status RightBalance(BBSTreeP T_p){//右平衡处理
	BBSTree rc = (*T_p)->rchild;
	if (!rc) return FALSE;
	switch (rc->bf){//检查右子树平衡度,并作相应平衡处理
	case RH:
		(*T_p)->bf = rc->bf = EH;
		L_Rotate(T_p); break;//单向左旋
	case LH:
		BBSTree ld = rc->lchild;
		switch (ld->bf){
		case LH:
			(*T_p)->bf = EH; rc->bf = RH; break;
		case EH:
			(*T_p)->bf = rc->bf = EH; break;
		case RH:
			(*T_p)->bf = LH; rc->bf = EH; break;
		}
		ld->bf = EH;
		R_Rotate(&((*T_p)->rchild));
		L_Rotate(T_p);
	}
	return TRUE;
}

最后需要构造一个插入函数,得找到插入的位置,并且新定义一个布尔型变量taller,代表树长高,若原先就左高,左子树又插入后得以长高,那么必然不满足平衡二叉树的定义,需要进行旋转的操作。

Status InsertAVL(BBSTreeP T_p, ElemType e, Boolean taller){//平衡二叉树插入节点
	if (!(*T_p)){//插入新节点,树长高
		*T_p = (BBSTree)malloc(sizeof(BBSTNode));
		(*T_p)->data = e;
		(*T_p)->lchild = (*T_p)->rchild = NULL;
		(*T_p)->bf = EH; *taller = TRUE;
	}
	else{//递归查找
		if ((*T_p)->data == e){//不再插入
			taller = FALSE;
			return FALSE;
		}
		else if ((*T_p)->data > e){//左子树中搜索
			if (!InsertAVL(&((*T_p)->lchild), e, taller))//未插入
				return FALSE;
			if (taller)//树长高
				switch ((*T_p)->bf){//检查节点原有平衡度
					case LH:LeftBalance(T_p); *taller = FALSE; break;
					case EH:(*T_p)->bf=LH; *taller = TRUE; break;//对于父节点而言
					case RH:(*T_p)->bf=EH; *taller = FALSE; break;
			}
		}
		else{//右子树中搜索
			if (!InsertAVL(&((*T_p)->rchild), e, taller))//未插入
				return FALSE;
			if (taller)//树长高
				switch ((*T_p)->bf){//检查节点原有平衡度
					case LH:
						(*T_p)->bf = EH; *taller = FALSE; break;
					case EH:
						(*T_p)->bf =RH; *taller = TRUE; break;//对于父节点而言
					case RH:
						RightBalance(T_p); *taller = FALSE; break;
			}
		}
	}
	return TRUE;
}     
B树

B-树的实现

B树是一棵平衡的多路查找树,其每个结点对应文件的索引,在文件系统中用处很大。

一棵m阶的B-树的定义如下:

每个节点最多有m棵子树;若根节点不为叶子节点,则至少有两棵子树;除根节点之外的所有非终端节点至少有[m/2]棵子树;所有非终端节点中包含下列数据信息:\((n,A_{0},K_{1},A_{1},K_{2},A_{2},…,K_{n},A_{n})\),其中K为关键字,A为指向子树节点的指针;叶子节点为空。

理解B树的定义关键在于理解K和A的关系,以一棵4阶B树为例,它的子树最多有4棵,而实际上是先插入,再判断是否满足定义,不满足执行相应操作。

因此其节点指向子树的指针应当有5个,虽然多数时间只用到前4个,而子树的指针对应于节点的K值,5个指针A,4个K值(作为间隔)即可,而为了指针和K的相对应,K也定义为5个长度,但是0号单元不做使用。

于是B树的数据结构可定义如下:

typedef struct BTNode{
	int keynum;//关键字个数,即节点大小
	struct BTNode* parent;//指向双亲结点
	KeyType key[M + 1];//关键字向量,0号单元未用
	struct BTNode* ptr[M + 1];//子树指针向量
	Record* recptr[M + 1];//记录指针向量,0号单元未用
}BTNode,*BTree,**BTreeP;

查找:首先类似与二叉排序树的方式找到关键字对应的位置:

Result SearchBTree(BTree T, KeyType K){//查找
	BTree p = T, q = NULL;
	bool found = FALSE; int i = 0;//初始化,p指向待查节点,q指向p的双亲
	while (p&&!found){
		i = Search(p, K);//p->key[i]<=K<p->key[i+1]
		if (i > 0 && p->key[i] == K) 
			found = TRUE;//查找成功	,结束循环
		else{
			q = p; p = p->ptr[i];//查找子树,进行循环,包含0号单元
		}
	}

	Result r = { NULL, 0, 0 };
	if (found){//找到结果,返回对应节点位置
		r = { p, i, 1 };
		return r;
	}
	else{//未找到结果,返回双亲位置
		r = { q, i, 0 };
		return r;
	}

}

节点中K与A值的存储也是按序进行的,因此还需要定义一个函数在节点中查找,返回K的位置。

int Search(BTree p, KeyType K){
	int i = 1;//0号单元未用
	if (p->key[1]>K)
		return 0;
	if (p->key[p->keynum] < K)
		return p->keynum;
	for (; i < p->keynum; i++){
		if (p->key[i] <= K < p->key[i + 1])
			break;
	}
	return i;
}

插入:B树的插入操作类似二叉排序树,但是若插入不满足B树的定义,则根据双亲节点的K值有相应的操作。

Status InsertBTree(BTreeP T_p, KeyType K, BTree q, int i){//插入操作,在查找之后
	KeyType x = K; bool finished = FALSE;
	BTree ap = NULL;
	while (q&&!finished){
		Insert(q, i, x, ap);//x和ap分别插入到q->key[i+1]和q->ptr[i+1]
		if (q->keynum <M){
			printf("成功插入数据%d\n",x);
			finished = TRUE;//插入完成
		}
		else{//需要分裂节点*q
			int s = (int)(M / 2)+1; Split(q, s, ap); x = q->key[s];//中间值移入新节点*ap
			q = q->parent;
			if (q)//双亲节点存在
				i = Search(q, x);//通过循环,在双亲结点中插入x
		}//else
	}//while
	if (!finished){//T是空树或者根节点已分裂为节点*q和*ap
		NewRoot(T_p, q, x, ap);//生成新的根节点
		printf("成功生成新节点并插入数据%d\n",x);
	}
	return OK;
}

同样,节点中K与A值的存储也是按序进行的,因此还需要定义一个函数在节点有序插入。

Status Insert(BTree q, int i, KeyType x, BTree ap){
	//移位
	KeyType k_t; BTree p_t; int j = q->keynum;
	for (; j >i+1; j--){
		q->key[j] = q->key[j-1 ];
		q->ptr[j] = q->ptr[j-1 ];
	}
	//添加
	q->keynum += 1;
	q->key[i+1] = x;
	q->ptr[i+1] = ap;
	return OK;
}

若是插入后的B树不满足定义则需进行分裂的操作,子树分裂,值插入根节点中:

Status Split(BTree q, int s, BTree ap){//分裂
	q->keynum = s - 1;
	ap = (BTree)malloc(sizeof(BTNode));
	ap->keynum = M - s;
	ap->parent = q->parent;
	for (int i = s + 1; i <= M; i++)
		ap->key[i - s ] = q->key[i];
	for (int i = s; i <= M; i++)
		ap->ptr[s - i + 1] = q->ptr[i];
	for (int i = s + 1; i <= M; i++)
		ap->recptr[i - s] = q->recptr[i];
	printf("成功分裂节点\n");
	return OK;
}

若是根节点不存在,或者根节点也不满足B树定义,那么须生成新的根节点:

Status NewRoot(BTreeP T_p,BTree q,KeyType x, BTree ap){//生成新的根节点
	BTree n_p = (BTree)malloc(sizeof(BTNode));
	n_p->parent = NULL;
	if (q&&ap)
		q->parent = ap->parent = n_p;
	n_p->ptr[0] = q; n_p->ptr[1] = ap;
	n_p->key[1] = x; n_p->keynum = 1;
	*T_p = n_p;
	return OK;
}

删除操作是插入的逆向过程,如果不满足B树的定义,那么插入时的分裂对应于删除时的合并,这里不再赘述。

B+树的定义

B+树是应文件系统所需而出现的一种B-树的变形,其与B-树的差异在于:

有n棵子树的节点中含有n个关键字;叶子节点包含全部关键字信息,本身依照关键字大小顺序连接;所有非终端节点可以看成是索引部分,节点中仅含其子树中的最大(或最小)关键字。

图的概述

线性表是只有一个前驱和一个后驱节点的数据结构,而树是由一个前驱和多个后驱节点的数据结构。相对应的图是可以有多个前驱和后驱节点的数据结构。

更一般的,图结构中,节点间关系可以是任意的,图结构可以很好的描述消息传递的网络,在现实中应用广泛,而图论是专门研究图的理论。

图由顶点和边组成,规范的描述如下:

G=(V,E),其中V是顶点的有穷非空集合,E是V中顶点偶对的有穷集合,若边为线段,则图为无向图,若边为向量,则图为有向图。边上可标有某种含义的数值,称为权,带权的图称为网。

存储结构

存储结构

图没有顺序存储结构,因为无法以数据元素(顶点)在存储区中的物理位置来表示元素之间的关系,但可以借助二维矩阵(边)描述,而图的链式结构有多种,应根据实际需要进行选择。

邻接矩阵

邻接矩阵,表示顶点之间相邻关系的矩阵,即以二进制存储图的边,使用与已知一个图的点和边。

优点是便于判断边的存在以及计算顶点的度,缺点是不便于动态改变图的顶点数目以及不便于表示有向图。

//邻接矩阵存储表示
typedef struct {
	VerTexType vexs[MVNum];//顶点表
	ArcType arcs[MVNum][MVNum];//邻接矩阵
	int vexnum, arcnum;//图当前的顶点数和边数
}AMGraph;

邻接表

邻接表,类似于链式散列表,表头结点顺序存储以实现随机访问,数据域存储结点信息,链域指向第一个邻接点;边表表示顶点间关系,邻接点域指示位置,数据域存储权值,链域指向下一个邻接点。

有向图可以多建立逆邻接表以储存方向。优缺点基本上与邻接矩阵互补。

//邻接表存储表示
typedef struct ArcNode{//边结点
	int adjvex;
	struct ArcNode* nextarc;
	InforType info;
}ArcNode;
typedef struct VNode{//顶点信息
	VerTexType data;
	ArcNode* firstarc;
}VNode,AdjList[MVNum];
typedef struct{//邻接表
	AdjList vertices;
	int vexnum, arcnum;
}ALGraph;

十字链表

十字链表,弧结点中尾域和头域指示位置,尾链和头链指示弧尾和头相同的下一条弧,数据域存储信息。指示同一弧头或弧尾的在同一链表上,因此可以看作是有向图的邻接表和逆连接表的结合。顶点结点中存储有链表的表头。

//十字链表存储表示
#define MAX_VERTEX_NUM 20
typedef struct ArcBox{
	int tailvext, headvex;
	struct ArcBox *hlink, *tlink;
	InforType * info;
}ArcBox;
typedef struct VexNode{
	VerTexType data;
	ArcBox *firstin, *firstout;
}VexNode;
typedef struct{
	VexNode xlist[MAX_VERTEX_NUM];
	int vexnum, arcnum;
}OLGraph;

邻接多重表

邻接多重表,邻接表中的边有两个节点,给图的删除等操作带来不方便,而邻接多重表每条边用一个结点表示,标志域标志是否被搜索,位置域指示依附顶点位置,链域指示下一条依附于该顶点的边。

//邻接多重表存储表示
typedef enum{ unvisited, visited } VisitIf;
typedef struct EBox{
	VisitIf mark;
	int ivex, jvex;
	struct EBOX *ilink, *jlink;
	InforType * Info;
}Ebox;
typedef struct VexBox{
	VerTexType data;
	EBox *firstedge;
}VexBox;
typedef struct{
	VexBox adjmulist[MAX_VERTEX_NUM];
	int vexnum, edgenum;
}AMLGraph;
遍历方式

遍历方式

图的遍历算法也是从顶点出发对所有顶点仅访问一次,是求解图的连通性问题、拓扑排序和关键路径等算法的基础。

根据搜索路径的方向,可分为深度优先搜索和广度优先搜索,适用于有向图和无向图。图中存在回路,为了实现仅访问一次,需要设辅助数组,记下已访问的结点。

深度优先搜索

深度优先搜索DFS:从某顶点出发,访问该顶点,之后访问第一个未被访问的邻接点,再以该顶点作为新顶点,重复至访问过得顶点没有未被访问的邻接点为止,返回前一个访问过且仍有未被访问邻接点的顶点,继续重复步骤至所有顶点都被访问。

对连通图,深度优先搜索可以用递归实现,对于非连通图,则需要循环调用连通算法。

Status DFS_AM(AMGraph G, int v, bool *visited){//深度优先遍历,从第v个顶点开始
	visited[v] = true;
	printf("访问了顶点%d\n", v+1);
	for (int w = 0; w < G.vexnum; w++){
		if ((G.arcs[v][w] != 0) && (!visited[w]))
			DFS_AM(G, w,visited);//递归调用
	}

	return OK;
}

广度优先搜索

广度优先搜索BFS:从某顶点出发,访问该顶点,之后依次访问未被访问的邻接点,该邻接点作为新顶点,并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问。重复至访问过得顶点没有被访问的邻接点为止。

这里可以引入队列保存已被访问过的顶点来实现,当然个人感觉栈也可以实现。

哈希表

之前所介绍的数据结构在查找的时候都要经过一系列关键字的比较,效率取决于查找过程中的比较次数。

而试想一种最理想的情况,直接根据关键字查找数据,即数据存放的地址和关键字对应,构成映射的关系f(key)=address。

这个建立的函数f便称为哈希函数,依照这种方法构造的表称为哈希表。

构造哈希函数

直接定址法:

取关键字或关键字的某线性函数值为哈希地址,即:H(key)=key或H(key)=a*key+b

直接定址法所得地址集合和关键字集合大小相同,因此对于不同的关键字不会发生冲突。

数字分析法:

假设关键字是以r为基的数,并且所有的关键字实现可知,则取关键字的若干数位组成哈希地址。

平方取中法:

取关键字平方后的中间几位为哈希地址。

除留余数法:

取关键字被某个不大于哈希表表长m的数除后所得余数为哈希地址,即H(key)=key MOD p,p不大于m。

实际工作中需要可根据不同的情况采取不同的哈希函数,如关键字的长度、哈希表的大小、关键字的分布情况、记录的查找频率等。

处理哈希表的冲突

key相当于自变量,addreess相当于因变量,完美的哈希表应当是一对一映射,但多数情况下,往往有多个key对应一个address,称为哈希表的冲突。

一方面在选取哈希函数的时候就要考虑到可能的冲突,并通过选择合适的哈希函数来进行减少冲突,另一方面对待冲突的处理也有多种方法。

开放定址法:

\(H_{i}=(H(key)+d_{i})\) MOD m,i=1,2,…,k

即在引起冲突时依次找当前空余的位置填入数据,但这种方法会引起后继哈希地址的冲突,这种现象称为“二次聚集”。

再哈希法:

在引起冲突时,换一个哈希函数计算地址,直到哈希表不再冲突为止。

哈希函数可以用函数指针的方式进行调用,这种方法虽然不易产生“聚集”,但是计算时间大大增加。

链地址法:

将所有关键字哈希地址相同的记录存储在同意线性链表中,每个分量的初始状态都是空指针。

这种方法实际上就是数组和链表的结合,既有链表的灵活性,也有顺序存储寻址的便捷性。

建立公共的溢出区:

很朴素的思想,将冲突的记录通通放进这个区域。

哈希表的实现

选择除留余数法构造哈希函数,同时选取链地址法处理冲突,存储1-99到构造的哈希表中并打印出来。

定义哈希表结构体和链表:

typedef struct LNLNode{
	ElemType e;
	int length;
	LNLNode* next;
}LNLNode,*LNLinkList,**LNLinkListP;
typedef struct Hash{
	LNLNode L;
}HashTable,*HashTableP;

用结构体数组顺序存储哈希表,初试元素为空:

HashTable H[10] = { NULL };

构造哈希函数:

int Hash(ElemType e){
	return e % 10;
}

构造对哈希表的相关操作,插入,查找,删除:

Status InsertHash(HashTable H[10], ElemType e){//插入
	int i= Hash(e);
	return InsertLNL(&H[i].L, e);
}
Status SearchHash(HashTableP H, ElemType e, LNLinkListP p ){//查找
	int i = Hash(e);
	return SearchLNL(&H[i].L, p, e);
}
Status DeleteHash(HashTableP H, ElemType e){//删除
	int i = Hash(e);
	return DeleteLNL(&H[i].L,e);
}

可以看到哈希表的操作实际上就是选择性对链表的操作,为此接下来构造链表的相关操作:

//链表的相关操作
Status InsertLNL(LNLinkList L, ElemType e){//插入,传入参数为位置
	LNLinkListP p = (LNLinkListP)malloc(sizeof(LNLinkList));
	if (SearchLNL(L, p, e) == UNSUCCESS){
		if (L->length == 0){
			L->e = e;
			L->length += 1;
			return SUCCESS;
		}
		(*p)->next = (LNLinkList)malloc(sizeof(LNLNode));	
		(*p)->next->e = e; (*p)->next->next = NULL;
		L->length += 1;
		return SUCCESS;
	}
	else{
		return UNSUCCESS;
	}
}

Status SearchLNL(LNLinkList L,LNLinkListP p, ElemType e){//查找
	LNLinkList p_find =L;
	while (p_find){
		if (p_find->e == e)
			return SUCCESS;
		*p = p_find;
		p_find = p_find->next;
	}
	
	return UNSUCCESS;
}

Status DeleteLNL(LNLinkList L, ElemType e){//删除
	LNLinkListP p = (LNLinkListP)malloc(sizeof(LNLinkList));
	if (SearchLNL(L,p,e) == UNSUCCESS){
		return UNSUCCESS;
	}
	else{
		if (L->length == 0){
			return UNSUCCESS;
		}
		else{
			LNLinkList p_delete =(*p)->next->next;
			*(*p)->next = *p_delete;
			L->length -= 1;
			if (p_delete)
				free(p_delete);
			return SUCCESS;
		}
		
	}
	
}

最后打印输出,测试结果如下:

for (int i = 0; i < 100; i++)
		InsertHash(H, i);
	DeleteHash(H, 88);
	printf("100以内按取10的模哈希:\n");
	for (int i = 0; i < 10; i++){
		PrintLNL(&(H[i].L));
		printf("\n");
	}
100以内按取10的模哈希:
10      20      30      40      50      60      70      80      90
1       11      21      31      41      51      61      71      81      91
2       12      22      32      42      52      62      72      82      92
3       13      23      33      43      53      63      73      83      93
4       14      24      34      44      54      64      74      84      94
5       15      25      35      45      55      65      75      85      95
6       16      26      36      46      56      66      76      86      96
7       17      27      37      47      57      67      77      87      97
8       18      28      38      48      58      68      78      98
9       19      29      39      49      59      69      79      89      99

总结与展望

数据结构的学习还算有章可循,但是对数据结构的具体操作,也就是算法则需要耐心调试。

我在复现相关操作的过程中,发现在正确编译之前,实际代码已经在我脑海中跑了一遍,也就是我清楚的知道哪一块内存该存什么数据。

不足之处在于对于图数据结构尚未进行学习,因为主要学习数据结构是为了方便后续OS的学习,而据了解OS用不到图的结构,因此以后有机会学习了再进行补充吧。

接下来将利用所学的数据结构实践相关的计算机理论,比如编译原理,再比如操作系统中相关算法。

倪老师曾言,对我们专业而言代码会调通就行,至于逻辑算法的进一步优化还是应当交给CS科班的来负责比较合适。

我们应当更关注的是上层数字算法的实现和应用,比如信号分析、控制理论的嵌入式应用。

——黑帅

2020.6.30

编译器词法分析状态集合构造时需要图的遍历,因此补充图的基础概念,存储结构以及遍历方式。

——黑帅

2020.7.2

By gzj7108

人生只有一条路,就是勇往直前。

在 “数据结构” 有 1 条评论
  1. I like the valuable info you provide in your articles. I’ll bookmark your blog and check again here regularly. I am quite certain I’ll learn plenty of new stuff right here! Good luck for the next! Kaitlynn Regen Lebna

发表评论

邮箱地址不会被公开。 必填项已用*标注