2015-08-06 15:39:31 Cowena 阅读数 1612

第一章    绪论


《数据结构》主要研究内容:

1、数据的各种逻辑结构物理结构,以及他们之间的相应关系

2、并对每种结构定义相适应的各种运算

3、设计出相应的算法

4、分析算法的效率

常见的数据结构有:数组、栈、队列、表、串、树、图、和文件等。



1.3    基本术语


数据(Data):  所有能被计算机处理的符号的集合。

数据元素(Data Element):  是数据这个集合中的一个个体。

设给定数据集合为:

D = {d1,d2,...., dn}   则di属于D,并称为di为数据元素。

 数据项(Data Item):  数据元素常常由若干个数据项组成,是数据的不可分割的最小单位。

数据对象(Data Object):  具有相同性质的数据元素的集合。


数据结构(Data Structure):是相互之间存在一种或多种特定关系的数据元素的集合。

形式定义为:数据结构是一个二元组  Data_Structure = (D,S)

     其中:D是数据元素的有限集,S是D上关系的有限集。


逻辑结构(Logical Structure):指数据元素之间的结构关系。

(任何一个算法的设计取决于选定的数据(逻辑)结构)


物理结构(Physical Structure): 指数据结构在机内的表示(存储结构)。

(算法的实现依赖于采用的存储结构)


1.4    算法描述和算法分析


1、算法的概念:算法是一个有限的指令集,遵循指令流可以完成特定的功能。


2、算法的基本特性

有穷性:操作步骤有穷,每个步骤的运行时间有穷;

确定性:下一步必须是明确的;

可行性:每一步是可执行的;

输入:零个或多个输入;

输出:一个或多个输出。


3、算法设计的要求:正确性、可读性、健壮性、高效率和低存储量需求。


4、算法与程序的区别:

算法是解决问题的一种方法或一个过程,考虑如何将输入转换成输出,一个问题可以有多种算法。
程序是用某种程序设计语言对算法的具体实现。

主要区别:有穷性、正确性和描述方法

程序可以是无穷的,例如OS,算法是有穷的;

程序可以是错误的,算法必须是正确的;

程序是用程序设计语言描述,在机器上可以执行;算法还可以用框图、自然语言等方式描述。


5、算法的度量方法:事后统计方法(不科学、不准确)、事前分析估算方法。

6、函数的渐进增长:给定两个函数 f(n) 和 g(n), 如果存在一个整数N,使得对所有的 n > N, f(n) 总是比 g(n), 那么,我们说 f(n) 的增长渐进快于 g(n)。

7、算法时间复杂度
在进行算法分析时,语句总的执行次数 T(n) 是关于问题规模 n 的函数, 进而分析 T(n) 随 n 的变化情况并确定 T(n) 的数量级。
算法的时间复杂度,也就是算法的时间度量,记作: T(n) = O(f(n))。它表示随问题规模 n 的增大, 算法执行时间的增长率和 f(n) 的增长率相同,称作算法的渐进时间复杂度,简称为时间复杂度。其中 f(n) 是问题规模 n的某个函数。(f(n) 是运行时间随 n 增大时的增长率
这样用大写O() 来体现算法时间复杂度的记法,我们称之为大O记法。

8、算法空间复杂度:指空间需求。

9、推导大O阶
>  用常数1取代运行时间中的所有加法常数。
>  在修改后的运行次数函数中,只保留最高阶项。
>   如果最高阶项存在且不是1,则去除与这个项相乘的常数。
得到的结果就是大O阶。

常见的时间复杂度所耗时间的大小排列:

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

2014-07-31 11:05:39 awyd234 阅读数 2736

由于本科不是计算机专业的,之前也没学过类似的课程,在看这本书时花了很长时间,也做了一些准备,网上听人介绍,建议先学离散数学,就自学了一点离散数学啥的(国内的和国外的那本《离散数学及其应用》都看过一点),也看过一点国外的那本《数据结构》,但由于自己没太大毅力,加之本专业课程较多和不习惯国外教材的思维模式啥的,一直都是各种教材浅尝辄止,大都只看了一点基础就没继续了。同时也是因为迷信离散数学是数据结构的先修课。

之前写程序一直没有数据结构的概念,经常就是一个数组写到底。大一时C语言大作业做了一个好友信息管理,就是纯控制台,所有数据用全局变量数组存储,当时还觉得挺得意的,因为花了很大功夫,代码很冗长,现在其实想想用数据结构的知识会简洁很多。第一次了解到数据结构,还是因为看到二级C里面考数据结构才了解到的,当然,裸考,也没具体看了。后来,学数据结构是因为常听说“程序设计=算法+数据结构”,加之想跨专业工作考研啥的,就开始下决心自学数据结构。

刚开始自学时很不习惯这种不给出完全代码的风格,加之C语言结构体指针学的很浅,自己也没想太多怎么实现,就放弃了这本书。在查资料后,了解到有本程杰的《大话数据结构》不错,就借 来看看。不得不说,那本书写的幽默易懂,适合初学者用来建立学习兴趣,印象最深的就是作者在开头举的那个故事里“没学过数据结构吧!”。于是通过这本书大概了解了数据结构的表,队列,栈,树,图啥的是啥意思,相对地,这本书比较浅显,也就不适合用于深度学习。大二暑假时曾学过一遍,看到KMP算法时被卡住了就一直搁着了。最近是今年3月份重新开始啃严奶奶版的。

一直看的很随意,一直到今年3月份才开始决定写点东西实践下,主要是因为考研论坛xuzhezhaozhao(http://blog.csdn.net/xzz_hust)介绍的学习方法,加之其将代码放到了GitHub上让我有了参照,便开始边依葫芦画瓢边看书自己码了起来,在此表示感谢。最开始用的CodeBlocks,后来决定从大流,用VS,用的2013的,大部分代码放在了GitHub:https://github.com/awyd234/DS_yan,部分代码有参考。

啰嗦了这么多,谈谈这本书的感受吧。严版的这本网上评价不太好,有很多错误,大家更看好国外教材。可能我看的第4版吧,错误相对而言还算较少,也或许是我能力不够找不出来吧。总的来说,这本相对而言用于打基础还是不错的,相比于Data Structureand Alogrithm Analysis in C的更重于理论分析,两本书这点可以用于互补的。本书概念较多,看上去有点头大,可能于国内编教材风格有关吧。本书的代码风格我模仿过,感觉比我以前的初学者似的代码风格好一些,就暂时先用着,至于Weiss的风格还是不太习惯将函数类型单独成行以及用/* */注释。书中代码不太完整,也有一定好处,可以强迫自己理解算法思想了再自己加以实现,在此过程中,我也学会了用IDE对程序进行Debug。另外本书配套的有教学平台,可以演示算法的执行过程,其中为了避免ElemType到底是用char还是用int的问题,光盘中的代码用#define和#ifndef来处理,这点感觉不错。另外由于本书给的部分代码较复杂,如KMP,可以多查查资料,不要一个劲地死磕一本书。

第一次写这类读书总结,较啰嗦,见谅。

2019-01-04 12:02:33 qq_41059755 阅读数 555

看之前请注意!博主小菜鸡一个,所以有许多瑕疵,请做好心理准备!

编程语言:C
编译环境:Dev-C++

编程实现书P121 ADT BinaryTree 基本操作20个,用二叉链表结构实现

基本概念:
二叉树是一种应用广泛的树型结构,它的特点是每个结点至多只有两棵子树
并且二叉树的子树有左右之分,其次序不能任意颠倒

1.Status InitBiTree(BiTree *T) 构造空二叉树
2.Status DestroyBiTree(BiTree *T) 销毁二叉树,前提T存在
3.Status CreateBiTree(BiTree *T) 用先序遍历创建二叉树
4.Status ClearBiTree(BiTree *T) 清空二叉树,前提T存在
5.Status BiTreeEmpty(BiTree T) 探空,前提T存在,很抱歉只有这个我不会
6.int BiTreeDepth(BiTree T) 返回二叉树的深度,前提T存在,这个我写的不太好,有缺点
7.BiTree Root(BiTree T) 返回二叉树的根,前提T存在
8.ElemType Value(BiTree T,BiTree e) 若e是T中某个结点,返回e的值,前提T存在
9.Status Assign(BiTree T,BiTree *e,ElemType value) 若e是T中某个结点,结点e赋值为value,前提T存在
10.BiTree Parent(BiTree T,BiTree e) 若e是T中某个非根结点,则返回它的双亲,否则返回NULL,前提T存在
11.BiTree LeftChild(BiTree T,BiTree e) 若e是T中某个结点,返回e的左孩子。若e无左孩子,则返回NULL,前提T存在
12.BiTree RightChild(BiTree T,BiTree e) 若e是T中某个结点,返回e的右孩子。若e无右孩子,则返回NULL,前提T存在
13.BiTree LeftSibling(BiTree T,BiTree e) e是T中某个结点,返回e的左兄弟。若e是其双亲的左孩子或无左兄弟,则返回NULL,前提T存在
14.BiTree RightSibling(BiTree T,BiTree e) e是T中某个结点,返回e的右兄弟。若e是其双亲的右孩子或无右兄弟,则返回NULL,前提T存在
15.Status InsertChild(BiTree T,BiTree p,int LR,BiTree c)
初始条件:T存在,p指向T中某个结点,LR为0或1,非空二叉树c与T不相交且右子树为空。
操作结果:根据LR为0或1,插入c为T中p所指结点的左或右子树。p所指结点的原有左或右子树则成为c的右子树。
16.Status DeleteChild(BiTree T,BiTree p,int LR)
初始条件:T存在,p指向T中某个结点,LR为0或1
操作结果:根据LR为0或1,删除T中p所指结点的左或右子树
17.Status PreOrderTraverse(BiTree T) 先序遍历二叉树,前提T存在
18.Status InOrderTraverse(BiTree T) 中序遍历二叉树,前提T存在
19.Status PostOrderTraverse(BiTree T) 后序遍历二叉树,前提T存在
20.Status LevelOrderTraverse(BiTree T) 层序遍历二叉树,前提T存在

源代码:

#include<stdio.h> 
#include<stdlib.h>
#include<malloc.h>
//函数结果状态代码
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -1

typedef char ElemType;
typedef int Status;
//二叉树的二叉链表存储表示
typedef struct BiTNode{
	ElemType data;
	struct BiTNode *lchild,*rchild;//左右孩子指针 
}BiTNode,*BiTree; 
//数据元素类型为BiTree的队列,用于层序遍历 
typedef struct QNode{
	BiTree Qdata;
	struct QNode *next;
}QNode,*QueuePtr;
typedef struct{
	QueuePtr front;
	QueuePtr rear;
}LinkQueue;
//构造一个空队列Q
Status InitQueue(LinkQueue *Q)
{
	(*Q).front=(QueuePtr)malloc(sizeof(QNode));
	if(!(*Q).front) exit(OVERFLOW);
	(*Q).front->next=NULL;
	(*Q).rear=(*Q).front;
	return OK;
}
//探空,前提Q存在
Status QueueEmpty(LinkQueue Q)
{
	if(Q.front==Q.rear)
	    return TRUE;
	else
	    return FALSE;
}
//插入元素e作为新的队尾元素,前提Q存在
Status EnQueue(LinkQueue *Q,BiTree e)
{
	QueuePtr p=(QueuePtr)malloc(sizeof(QNode));//开辟新结点
	if(!p) exit(OVERFLOW);
	p->Qdata=e;
	p->next=NULL;
	(*Q).rear->next=p;
	(*Q).rear=p;
	return OK;
}
//若队列不空,删除队头元素,用e返回其值,前提Q存在
Status DeQueue(LinkQueue *Q,BiTree *e)
{
	if((*Q).front==(*Q).rear)
	    return ERROR;
	QueuePtr p=(*Q).front->next;
	*e=p->Qdata;
	(*Q).front->next=p->next;
	if((*Q).rear==p)
	    (*Q).rear=(*Q).front;
	free(p);
	return OK;
}
//1.构造空二叉树
Status InitBiTree(BiTree *T)
{
	(*T)=(BiTree)malloc(sizeof(BiTNode));
	if(!(*T)) exit(OVERFLOW);
	(*T)->lchild=NULL;
	(*T)->rchild=NULL;
	return OK;
}
//2.销毁二叉树,前提T存在
Status DestroyBiTree(BiTree *T) 
{
	if(!(*T))
	    return OK;
	DestroyBiTree(&((*T)->lchild));
	DestroyBiTree(&((*T)->rchild));
	free(*T);
	return OK;
}
//3.用先序遍历创建二叉树
Status CreateBiTree(BiTree *T)
{
	char ch=getchar();//读入一个字符
	if(ch=='.') //个人认为用.表示空树比较好(这样输入多个空树的时候方便检验有没有输入错误,但是如果用空格的话,嗯......实在是无法检验) 
	    *T=NULL;
	else
	{
		*T=(BiTree)malloc(sizeof(BiTNode));
		if(!(*T)) exit(OVERFLOW);
		(*T)->data=ch;
		CreateBiTree(&((*T)->lchild));
		CreateBiTree(&((*T)->rchild));
	}
	return OK;
}
//4.清空二叉树,前提T存在(二叉链表的根结点和单链表的头结点是不同的,所以二叉树的清空不太一样)
Status ClearBiTree(BiTree *T)//清空之后,根结点是改变了的 
{
	if(!(*T))
	    return ERROR;
	DestroyBiTree(&((*T)->lchild));
	DestroyBiTree(&((*T)->rchild));//这里的确是销毁,你没看错 
	free(*T);
	(*T)=(BiTree)malloc(sizeof(BiTNode));//重新分配空间 
	if(!(*T)) exit(OVERFLOW);
	(*T)->lchild=NULL;
	(*T)->rchild=NULL;
	return OK; 
}
//5.探空,前提T存在
//哎呀,这个真不会写
//空树的特点是只有一个根结点,数据域没有赋数据,左右指针指向空 
//所以怎么判断根结点的数据域有没有赋数据啊 
//6.返回二叉树的深度,前提T存在
int BiTreeDepth(BiTree T)
{
	if(!T) 
	    return 0;
	else
	    return max(BiTreeDepth(T->lchild),BiTreeDepth(T->rchild))+1;//这有个缺点,空树会返回深度1	
}
//辅助函数
int max(int a,int b) 
{
	return (a>=b)?a:b;
}
//7.返回二叉树的根,前提T存在
BiTree Root(BiTree T)
{
	return T;
}
//8.若e是T中某个结点,返回e的值,前提T存在
ElemType Value(BiTree T,BiTree e)
{
	if(Search(T,e)==TRUE)
	    return e->data;
    else
        return '.';
}
//辅助函数
Status Search(BiTree T,BiTree e)
{
	if(!T)
	    return FALSE;
	if(T==e||Search(T->lchild,e)==TRUE||Search(T->rchild,e)==TRUE)
	    return TRUE;
	else
	    return FALSE;    
} 
//9.若e是T中某个结点,结点e赋值为value,前提T存在
Status Assign(BiTree T,BiTree *e,ElemType value)
{
	if(Search(T,*e)==TRUE)
	{
	    (*e)->data=value;
		return OK;	
	}
	return ERROR;
}
//10.若e是T中某个非根结点,则返回它的双亲,否则返回NULL,前提T存在
BiTree Parent(BiTree T,BiTree e)
{
	if(T==e)
	    return NULL;
	    
	if(T->lchild==e||T->rchild==e)
		return T;
	else if(Search(T->lchild,e)==TRUE)
	    return Parent(T->lchild,e);
	else if(Search(T->rchild,e)==TRUE)
	    return Parent(T->rchild,e);
	else
	    return NULL;
}
//11.若e是T中某个结点,返回e的左孩子。若e无左孩子,则返回NULL,前提T存在
BiTree LeftChild(BiTree T,BiTree e)
{
	if(Search(T,e)==TRUE)
	    return e->lchild;
	else
	    return NULL;
}
//12.若e是T中某个结点,返回e的右孩子。若e无右孩子,则返回NULL,前提T存在
BiTree RightChild(BiTree T,BiTree e)
{
	if(Search(T,e)==TRUE)
	    return e->rchild;
	else
	    return NULL;
}
//13.e是T中某个结点,返回e的左兄弟。若e是其双亲的左孩子或无左兄弟,则返回NULL,前提T存在
BiTree LeftSibling(BiTree T,BiTree e)
{
	if(Search(T,e)==TRUE&&Parent(T,e)->lchild!=e)
	    return Parent(T,e)->lchild;
	else
	    return NULL;
}
//14.e是T中某个结点,返回e的右兄弟。若e是其双亲的右孩子或无右兄弟,则返回NULL,前提T存在 
BiTree RightSibling(BiTree T,BiTree e)
{
	if(Search(T,e)==TRUE&&Parent(T,e)->rchild!=e)
	    return Parent(T,e)->rchild;
	else
	    return NULL;
}
//15.初始条件:T存在,p指向T中某个结点,LR为0或1,非空二叉树c与T不相交且右子树为空。
//   操作结果:根据LR为0或1,插入c为T中p所指结点的左或右子树。p所指结点的原有左或右子树则成为c的右子树。
Status InsertChild(BiTree T,BiTree p,int LR,BiTree c)
{
	if(!T||Search(T,p)==FALSE)
	    return ERROR;
	BiTree q;
	if(LR==0)
	{
		q=p->lchild;
		p->lchild=c;
		c->rchild=q;
	}
	else if(LR==1)
	{
		q=p->rchild;
		p->rchild=c;
		c->rchild=q;
	}
	else
	    return ERROR;
	return OK;
}
//16.初始条件:T存在,p指向T中某个结点,LR为0或1
//   操作结果:根据LR为0或1,删除T中p所指结点的左或右子树
Status DeleteChild(BiTree T,BiTree p,int LR)
{
	if(T&&Search(T,p)==FALSE)
	    return ERROR;
	if(LR==0)
	{ 
		DestroyBiTree(&p->lchild);
		p->lchild=NULL;
	} 
	else if(LR==1)
	{ 
		DestroyBiTree(&p->rchild);
		p->rchild=NULL;
	} 
	else
	    return ERROR;
	return OK;
}
//17.先序遍历二叉树,前提T存在
Status PreOrderTraverse(BiTree T)
{
	if(!T)
	    return ERROR;
	printf("%c ",T->data);
	PreOrderTraverse(T->lchild);  
	PreOrderTraverse(T->rchild);
	return OK;
}
//18.中序遍历二叉树,前提T存在
Status InOrderTraverse(BiTree T)
{
	if(!T)
	    return ERROR;
	InOrderTraverse(T->lchild);
	printf("%c ",T->data);
	InOrderTraverse(T->rchild);
	return OK;
}
//19.后序遍历二叉树,前提T存在
Status PostOrderTraverse(BiTree T)
{
	if(!T)
	    return ERROR;
	PostOrderTraverse(T->lchild);  
	PostOrderTraverse(T->rchild);
	printf("%c ",T->data);
	return OK;
}
//20.层序遍历二叉树,前提T存在
Status LevelOrderTraverse(BiTree T)
{
	if(!T)
	    return ERROR;
	LinkQueue Q;
	InitQueue(&Q);
	BiTree p;
	EnQueue(&Q,T);
	while(QueueEmpty(Q)==FALSE)
	{
		DeQueue(&Q,&p);
		printf("%c ",p->data);
		if(p->lchild)
		    EnQueue(&Q,p->lchild);
		if(p->rchild)
		    EnQueue(&Q,p->rchild);
	}
	return OK;
}
int main()
{
	BiTree T,c;
	char ch;
	printf("测试第一个基本操作\n");
	if(InitBiTree(&T)==OK&&InitBiTree(&c)==OK)
	    printf("二叉树初始化成功!\n");
	printf("\n\n测试第三个基本操作\n");
	printf("首先构造二叉树T\n");
	CreateBiTree(&T);
	ch=getchar();//吸收换行符 
	printf("先序遍历:");
	PreOrderTraverse(T);
	printf("\n中序遍历:");
	InOrderTraverse(T);
	printf("\n后序遍历:");
	PostOrderTraverse(T);
	printf("\n层序遍历:");
	LevelOrderTraverse(T);
	printf("\n\n\n构造二叉树c\n");
	CreateBiTree(&c);
	printf("层序遍历:");
	LevelOrderTraverse(c);
	printf("\n\n\n测试第六个基本操作\n");
	printf("T的深度为:%d\n",BiTreeDepth(T));
	printf("\n\n测试第七、第八个操作\n");
	printf("根为:%c\n",Value(T,Root(T)));
	printf("\n\n测试第十至第十四个基本操作\n");
	BiTree m=T->lchild->lchild,n=T->rchild;//这里我是在知道二叉树结构的情况下进行赋值的 
	printf("m为:%c,n为:%c\n",Value(T,m),Value(T,n));
	printf("m的双亲为:%c,n的双亲为:%c\n",Value(T,Parent(T,m)),Value(T,Parent(T,n)));
	printf("m的左孩子为:%c,n的左孩子为:%c\n",Value(T,LeftChild(T,m)),Value(T,LeftChild(T,n)));
	printf("m的右孩子为:%c,n的右孩子为:%c\n",Value(T,RightChild(T,m)),Value(T,RightChild(T,n)));
	printf("m的左兄弟为:%c,n的左兄弟为:%c\n",Value(T,LeftSibling(T,m)),Value(T,LeftSibling(T,n)));
	printf("m的右兄弟为:%c,n的右兄弟为:%c\n",Value(T,RightSibling(T,m)),Value(T,RightSibling(T,n)));
	printf("\n\n测试第九个基本操作\n");
	printf("将n的值改为G\n");
	Assign(T,&n,'G');
	printf("层序遍历:");
	LevelOrderTraverse(T);
	printf("\n\n测试第十五个基本操作\n");
	InsertChild(T,n,0,c);
	printf("层序遍历T:");
	LevelOrderTraverse(T);
	printf("\n\n\n测试第十六个基本操作\n");
	DeleteChild(T,n,0);
	printf("层序遍历T:");
	LevelOrderTraverse(T);
	printf("\n\n测试第二个基本操作\n");
	if(DestroyBiTree(&T)==OK)
	    printf("销毁二叉树T成功!\n");
	return 0; 
}

运行结果:

以上代码不是很完美,毕竟我还只是个初学者,如果谁有更好的建议,欢迎底下评论!

2019-10-09 10:37:45 qq_42815188 阅读数 506

趁着这学期学习 严蔚敏《数据结构》,记录一下自己的学习过程^ - ^。

网上关于数据结构的文章也不少,但是大多数博文对新手来说不太友好,所以,打算自己写个系列博客,也算是学习笔记吧!如果能帮助到和我(qdu)一样使用这本书的同学,那你要好好反思一下了,这都能帮到你?难道和我一样菜?!

再补充一句:syh老师太强了!希望老师能看到,数据结构给个59+1分!

注意:

  1. 提供严蔚敏《数据结构》C/C++语言参考代码,实现了课本上的基本算法,并进行了相应的知识扩充。
  2. 数据结构的思想精髓还是要上课好好听讲、好好看书学习 ^ - ^
  3. 算法题刷多了,项目代码风格有点难看,多多包涵。水平不足,还望指出。

【第1章 绪论】

  • 好好听课。略。

【第2章 线性表】

静态顺序表

  • 第2章 静态顺序表 基本算法实现:点击这里
  • 第2章 静态顺序表 删除值等于x的所有元素:点击这里
  • 第2章 静态顺序表 划分(快排基础):点击这里
  • 第2章 静态顺序表 将所有奇数移动到偶数的前面:点击这里

动态顺序表

带头结点的单链表

  • 第2章 带头结点的单链表 基本算法实现:点击这里
  • 第2章 带头结点的单链表 归并单链表:点击这里

静态链表

带头结点的双链表

  • 第2章 带头结点的双链表 基本算法实现:点击这里

带头结点的循环单链表

  • 第2章 带头结点的循环单链表 基本算法实现:点击这里

带头结点的循环双链表

  • 第2章 带头结点的循环双链表 基本算法实现:点击这里

线性表的应用

  • 第2章 一元多项式的加减(顺序表):点击这里
  • 第2章 一元多项式的加减(带头结点的单链表):点击这里
  • 第2章 约瑟夫环问题 (不带头结点的循环单链表):点击这里

【第3章 栈和队列】

栈的应用

队列

  • 第3章 链队 基本算法实现:点击这里
  • 第3章 循环队列(顺序队列) 基本算法实现:点击这里

【第4章 串】

  • 第4章 串的定长顺序存储表示 基本算法实现:点击这里
  • 第4章 串的堆分配存储表示 基本算法实现:点击这里
  • 第4章 块链串 基本算法实现:点击这里
  • 第4章 串的模式匹配(BF、KMP):点击这里

【第5章 数组和广义表】

  • 第5章 数组的存储结构以及特殊矩阵的压缩存储:点击这里
  • 第5章 稀疏矩阵(三元组顺序表):点击这里
  • 第5章 稀疏矩阵(十字链表):点击这里
  • 第5章 广义表的定义及其存储结构:点击这里

【第6章 树和二叉树】

  • 第6章 二叉树的性质及顺序存储结构:点击这里
  • 第6章 二叉树的链式存储结构及其遍历(递归+非递归):点击这里
  • 第6章 二叉树其他的一些算法(重点是理解递归):点击这里
  • 第6章 线索二叉树(中序线索化):点击这里
  • 补充:给定先序序列和中序序列,重建二叉树:点击这里
  • 补充:给定后序序列和中序序列,重建二叉树:点击这里
  • 第6章 树的存储结构(双亲表示法、孩子表示法、孩子兄弟表示法):点击这里
  • 第6章 二叉树、树、森林的转换及树、森林的遍历:点击这里
  • 第6章 哈夫曼树及哈夫曼编码(手工分析):点击这里
  • 第6章 哈夫曼树及哈夫曼编码(算法实现):点击这里

【第7章 图】

  • 第7章 图的邻接矩阵存储及其遍历:点击这里
  • 第7章 图的邻接表存储及其遍历:点击这里
  • 第7章 最小生成树 普里姆(Prim)算法:点击这里
  • 第7章 最小生成树 克鲁斯卡尔(Kruskal)算法:点击这里
  • 第7章 AOV网及拓扑排序:点击这里
  • 第7章 AOE网与关键路径:点击这里
  • 第7章 单源最短路径 迪杰斯特拉(Dijkstra)算法:点击这里
  • 第7章 全源最短路径 弗罗伊德(Floyd)算法:点击这里

【第8章 动态存储管理】

  • 略。

【第9章 查找】

【第10章 排序】

更新日志
2019.10.11 初步建立专栏
2019.10.20 结束第二章的学习,周末复习整理
2019.11.2 结束第三章和第四章的理论知识学习
2019.12.17 完成第五章和第六章
2019.12.21 初步理清第七章
2019.12.25 梳理第九章QAQ
2020.1.14 专栏完结

2018-04-20 19:38:51 heisehuanyin 阅读数 190

提要

算法3.7表达:银行业务模拟,获取客户平均等待时间

算法重点思路理解

算法模拟银行业务运用的主要思路:事件驱动。

由于该算法运用了事件驱动的设计思路,故算法中占据中心地位的是事件队列,整个算法的核心驱动力源自于对于事件队列的处理。其他的四个队列只是用于顾客堆栈,存储客户符号。

算法的假设

算法源自于对于银行事务的理解:

  1. 开门第一时间,第一位顾客到达,即刻办理业务;
  2. 客户办理业务所需时间是随机的,生成客户符号之后,便已经确定下来;
  3. 接下来的客户到达与本客户到达事件之间的间隔是随机的,算法中提前确定下来;
  4. 一位客户业务办理完成,离开银行,另一位客户开始办理业务;
  5. 耗时=客户离开时间-客户到达时间

算法的运行过程分析

第一步,首先在事件队列中存储一个到达事件,这个事件代表第一位顾客进入银行办理业务。

由于算法核心是事件驱动,因此这只是为后续处理过程添加了一个驱动事件,并不意味着第一位顾客相关事件的处理全部完成了,即使客户的到达事件也并没有处理。

第二步,抽取事件队列的事件符号,开始处理该事件,利用处理到达事件的子过程处理事件。

首先抽取事件队列到达事件,生成一个客户符号,将客户符号存入其中一个客户队列,如果这个队列中只有一个客户,那么即刻生成一个离开事件存入事件队列。

  • 整个算法中产生离开事件的位置有两个:一个是到达事件处理程序的结尾,另一个是离开事件处理程序的结尾。如果队列中只有一个客户,那么他的离开事件产生于到达事件处理程序,如果队列中不只有一个客户,那么这些客户的离开事件产生于离开事件处理程序的结尾。

其次,获取一个随机间隔,计算下一位客户的到达时间,如果到达时间在营业时间范围内,那么在事件队列中生成一个新的到达事件。

第三步,循环处理事件队列中的事件。

循环抽取事件队列中的事件进行处理,遇到事件调用相应的事件处理程序进行处理。
调用离开事件处理程序的时候,在事件队列中移除该事件并在客户队列中移除该事件所关联的客户,如果该队列不为空,生成下一个元素的离开事件存储到事件队列中。
处理离开事件的过程中计算客户所消耗的时间。

  • 由于事件队列中的所有事件是严格按照时间的先后顺序进行排序的,客户业务消耗的时间也是随机的,因此,事件队列的客户的排序必定是无序的。在事件队列中堆栈的事件是随机的。当遭遇到达事件时候,调用到达事件处理程序,遭遇离开事件,调用离开事件处理程序。由于初期只有到达事件存储在事件队列中,如果不在到达事件处理程序中抛出离开事件,很有可能算法永远不会调用离开事件处理程序。

摒弃该算法的思考

按照一般人的思考模式,肯定不是事件驱动而是时间驱动。
时间驱动的算法也可以设计出来,但是比较复杂。
首先是顾客到达时间和离开时间的确定。每一位客户到达时间是确定的,利用前一位客户的到达时间和间隔时间确定。那么需要维持一个时间队列,在时间队列中的元素是事件,按照发生的时间点排序。
其次,算法的运行过程每到达一位客户,调用一次时间计算程序,计算每个客户队列中队首客户的离开事件,存储到时间队列中。
再次,算法运行过程中,首先计算每一位客户的到达时间,并与时间队列中的下一个时间点进行比较,如果下一个时间点更靠前,先处理下一个事件,然后将客户符号压入客户队列。
如此多做了不少事情,不断的程序调用,进栈出栈会占用很大开销:频繁调用时间计算程序。

没有更多推荐了,返回首页