基础数据结构讲解 |
您所在的位置：网站首页 › 二叉树的基本术语包括 › 基础数据结构讲解 |
基础数据结构讲解
|
基础数据结构讲解-线性表、栈、队列、串、树、图
基本概念和术语1、算法的时间复杂度2、线性表2.1、线性表的存储（存储包括：顺序和链式）2.1.1、顺序存储结构2.1.2、链式存储结构
2.2、单链表2.3、静态链表2.4、循环链表2.5、双向链表
3、栈3.1、栈的顺序存储3.2、栈的链式存储3.3、队列的存储3.3.1、队列顺序存储的不足3.3.2、循环队列定义3.3.3、队列的链式存储结构
4、串4.1、串的存储4.2、朴素的模式匹配算法4.3、kmp模式匹配算法
5、树5.1、二叉树性质5.2、二叉树的存储5.3、遍历二叉树5.4、赫夫曼树及其应用
6、图6.1、图的存储6.1.1、邻接矩阵6.1.2、邻接表6.1.3、边集数组
6.2、图的遍历6.2.1、深度优先遍历6.2.2、广度优先遍历
6.3、最小生成树6.4、最短路径
基本概念和术语
数据：是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合 数据元素：是组成数据的，有一定意义的基本单位，在计算机中通常作为整体处理。也被称为记录 数据项：一个数据元素可以由若干个数据项组成，数据项是数据不可分割的最小单位 数据对象：是性质相同的数据元素的集合，是数据的子集 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合 逻辑结构：是指数据对象中数据元素之间的相互关系 集合结构：相互之间没有其他关系线性结构：一对一关系树形结构：一对多关系图形结构：多对多关系物理结构：是指数据的逻辑结构在计算机中的存储形式 顺序存储结构：是把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的 链式存储结构：是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的 数据类型：是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。 抽象：是指抽取出事物具有的普遍性的本质 抽象数据类型（Abstract Data Type ADT）:是指一个数字模型及定义在该模型上的一组操作 抽象数据类型体现了程序设计中问题分解、抽象和信息隐藏的特性 1、算法的时间复杂度算法的时间复杂度，也就是算法的时间量度，记作：T（n）= O（f(n)） T（n）增长最慢的算法为最优算法 O（n）来体现算法时间复杂度的记法，我们称之为大O记法 其中f（n）是一个表达式 最坏情况运行时间是一种保证，那就是运行时间将不会再坏了。在应用中，这是一种最重要的需求，通常，除非特别指定，我们提到的运行时间都是最坏情况的运行时间 算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作：S（n）= O（f（n）），其中，n为问题的规模，f（n）为语句关于n所占存储空间的函数 2、线性表定义：线性表（List）零个或多个数据元素的有限序列 Data 线性表的数据对象集合为{a1,a2,…,an}，每个元素的类型均为DataType，除第一个元素外，每一个元素有且只有一个直接前驱元素，除最后一个元素外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系 Operation InitList（*L）：初始化操作，建立一个空的线性表L ListEmpty（L）：若线性表为空，返回true，否则返回false ClearList（*L）：将线性表清空 GetElem（L，i，*e）：将线性表L中的第i个位置元素返回给e LocateElem（L，e）：在线性表L中查找与给定值e相等的元素，如果查找成功，返回该元素在表中序号表示成功，否则，返回0表示失败 ListInsert（*L，i，e）：在线性表L中的第i个位置插入新元素e ListDelete（*L，i，*e）：删除线性表L中第i个位置元素，并用e返回其值 ListLength（L）：返回线性表L的元素个数 2.1、线性表的存储（存储包括：顺序和链式） 2.1.1、顺序存储结构定义：指的是用一段地址连续的存储单元依次存储线性表的数据元素 初始化线性表#define MAXSIZE 20 /*存储空间初始化分配量*/ typedef int ElemType; /*ElemType类型根据实际情况而定，这里假设为int*/ typedef struct { ElemType data[MAXSIZE]; /*数组存储数据元素，最大值为MAXSIZE*/ int length; /*线性表当前长度*/ }SqList; 获得元素操作#define OK 1 #define ERROR 0 typedef int Status; Status GetElem(SqList L, int i, ElemType *e) { //判断如果线性表的长度为零，或者获取元素位置小于初始位置， //或大于线性表当前长度，则返回错误 if(L.length == 0 || i L.length) return ERROR; *e = L.data[i-1];//将要获取的数据放入*e中 return OK; } 插入操作Status ListInsert(SqList *L, int i, ElemType e) { int k; if(L->length == MAXSIZE) /*顺序线性表已满*/ return ERROR; if(i L->length+1) /*当i不在范围内时*/ return ERROR; if(i length) /*若插入数据位置不在表尾*/ { /*将要插入位置后数据元素向后移动一位*/ for(k = L->length-1; k >= i-1; k--) L->data[k+1] = L->data[k]; } L->data[i-1] = e; /*将新元素插入*/ L->length++; return OK; } 删除操作Status ListDelete(SqList *L, int i, ElemType *e) { int k; if(L->length == 0) /*线性表为空*/ return ERROR; if(i L->length) /*删除位置不正确*/ return ERROR; *e = L->data[i-1]; //将删除的元素保存下来 if(i length) /*如果删除不是最后位置*/ { for(k = i; k length; k++)/*将删除位置后继元素前移*/ L->data[k-1]=L->data[k]; } L->length--; return OK; }线性表顺序存储的优缺点： 优点： 1.无须为表示表中元素之间的逻辑关系而增加额外的存储空间 2.可以快速地存取表中任一位置的元素缺点： 1.插入和删除操作需要移动大量元素 2.当线性表长度变化较大时，难以确定存储空间的容量 3.会造成存储空间的“碎片” 2.1.2、链式存储结构线性表的链式存储结构又称为单链表 头指针与头结点异同：头指针是指向第一个元素的，如果存在头结点则指向头结点 线性表链式存储的初始化 typedef struct Node { ElemType data;//存放数据 struct Node *next;//存放下一结点的地址 }Node; typedef struct Node *LinkList; //定义LinkList 2.2、单链表定义：n个结点(a1的存储映像)链结成一个链表，即为线性表（a1,a2,…,an）的链式存储结构，因此此链表的每个结点中只包含一个指针域，所以叫单链表 单链表的查询Status GetElem(LinkList L, int i, ElemType *e) { int j; LinkList p; //声明一结点p p = L->next; //让p指向链表L的第一个结点 j = 1; //j为计数器 while(p && j next; //让p指向下一个结点 ++j; } if( !p || j > i) return ERROR; //第i个元素不存在 *e = p->data; //取第i个元素的数据 return OK; } 单链表的插入Status ListInsert(LinkList *L, int i, ElemType e) { int j; LinkList p, s; p = *L; j = 1; while(p && j next; ++j; } if( !p || j > i) return ERROR; //第i个元素不存在 //动态生成新的结点 s = (LinkList)malloc(sizeof(Node)); s->data = e; s->next = p->next; //将p的后继结点赋值给s的后继 p->next = s; //在将s的后继赋值给p的后继 return OK; } 单链表的删除Status ListDelete(LinkList *L, int i, ElemType *e) { int j; LinkList p,q; p = *L; j = 1; while (p->next && j next; ++j; } if( !(p->next) || j > i) return ERROR; //第i个元素不存在 q = p->next; p->next = q->next; //将q的后继赋值给p的后继 *e = q->data; //将q结点中的数据给e free(q); //释放内存 return OK; } 单链表的整表创建–头插法void CreateListHead(LinkList *L, int n) { LinkList p; int i; srand(time(0)); //初始化随机数种子 *L = (LinkList)malloc(sizeof(Node)); (*L)->next = NULL; //建立一个带头结点的单链表 for( i = 0; i data = rand()%100+1; //随机生成100以内的数字 p->next = (*L)->next; (*L)->next = p; //插入到表头 } } 单链表的整表创建–尾插法void CreateListTail(LinkList *L, int n) { LinkList p, r; int i; srand(time(0)); //初始化随机数种子 *L = (LinkList)malloc(sizeof(Node));//建立一个带头结点的单链表 r = *L; //r为指向尾部的结点 for( i = 0; i data = rand()%100+1; //随机生成100以内的数字 r->next = p; //将表尾终端结点指针指向新结点 r = p; //将当前新结点定义为表尾的终端结点 } r->next = NULL; //表示当前链表结束 } 单链表的整表删除Status ClearList(LinkList *L) { LinkList p, q; p = (*L)->next; //p指向第一个结点 while(p) //循环没有到表尾 { q = p->next; free(p); p = q; } (*L)->next = NULL; //头结点指针域为空 return OK; }总结：若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构。若需要频繁插入和删除时，宜采用单链表结构 2.3、静态链表定义：数组的元素都是由两个数据域组成，data和cur。每个数组都有两个小标一个数据域data（存放数据元素）和一个游标cur（存放后继元素的下标）。我们用这种数组描述的链表叫做静态链表 静态链表存储结构 #define MAXSIZE 1000 //初始化链表的最大长度1000 typedef struct { ElemType data; //数据域 int cur; //游标，为0时无指向 }Component,StaticLinkList[MAXSIZE];模拟分配新空间 int Malloc_SLL(StaticLinkList space) { int i = space[0].cur; //当前数组第一元素的cur存的值 if(space[0].cur) //判断为空则为空链表，不需要重新计算返回备用空闲下标 { space[0].cur = space[i].cur; //由于要拿上一个分量使用，所以存储下一个分量做备用 } return i; }模拟释放删除空间 void Free_SSL(StaticLinkList space, int k) { space[k].cur = space[0].cur; //把第一个元素cur值赋值给要删除的分量cur space[0].cur = k; //把要删除的分量下标赋值给第一个元素的cur }若静态链表L已存在，则返回L中数据元素个数 int ListLength(StaticLinkList L) { int j = 0; int i = L[MAXSIZE - 1].cur; while(i) { i = L[i].cur; j++; } return j; }静态链表的插入 Status ListInsert(StaticLinkList L, int i, ElemType e) { int j, k, m; k = MAX_SIZE-1; //获取最后一个元素的下标 if(i ListLength(L) + 1) return ERROR; j = Malloc_SLL(L); //获取当前空闲分量下标 if(j) { L[j].data = e; //将数据赋值给此分量的data for(m = 1; m top++; //栈顶 S->data[S->top] = e; //将新插入元素赋值给栈顶空间 return OK; } 出栈Status Pop(SqStack *S, SElemType *e) { if(S->top == -1) //栈空 return ERROR; *e = S->data[S->top]; S->top--; return OK; } 3.2、栈的链式存储栈的链式存储结构，简称为链栈 链栈的存储结构typedef struct StackNode { SElemType data; struct StackNode * next; }StackNode,*LinkStackPtr; typedef struct LinkStack { LinkStackPtr top; int count; }LinkStack; 进栈Status Push(LinkStack *S, SElemType e) { //动态生成一个结点 LinkStackPtr s = (LinkStackPtr)malloc(sizeof(StackNode)); s->data = e; //将新添加的值赋值给新生成的结点 s->next = s->top; //将当前栈顶指针赋值新生成结点next s->top = s; //将当前结点赋值给当前栈顶 s->count++; //链栈总数++ return OK; } 出栈Status Pop(LinkStack *S, SElemType *e) { LinkStackPtr p; if(StackEmpty(*S)) return ERROR; *e = S->top->data; p = S->top; //将栈顶结点赋值给p S->top = S->top->next; //使栈顶指针下移一位，指向后一结点 free(p); //释放结点p S->count--; return OK; }栈的应用—递归中 栈的应用—四则运算表达式求值 3.3、队列的存储定义：是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。队列是一种先进先出的线性表，简称FIFO ADT队列（Queue）Data 同线性表。元素具有相同的类型，相邻元素具有前驱和后继Operation InitQueue(*Q):初始化操作，建立一个空队列Q DestroyQueue(*Q):若队列Q存在，则销毁它 ClearQueue(*Q):将队列Q清空 QueueEmpty(Q):若队列Q为空，返回true，否则返回false GetHead(Q,*e):若队列Q存在且非空，用e返回队列Q的队头元素 EnQueue(*Q,e):若队列Q存在，插入新元素e到队列Q中并成功队尾元素 DeQueue(*Q,*e):删除队列Q中队头元素，并用e返回其值 QueueLength(Q):返回队列Q的元素个数 endADT 3.3.1、队列顺序存储的不足插入元素都是从队尾插入所以时间复杂度为O(1)，但是删除元素时都要在队头删除元素，为了保持队头始终从零开始，因此每当删除一个元素，都得依次往前运动，时间复杂度为O(n)，与线性表的顺序存储结构完全相同 3.3.2、循环队列定义我们把队列的这种头尾相接的顺序存储结构称为循环队列 循环队列的顺序存储结构typedef int QElemType; typedef struct { QElemType data[MAXSIZE]; int front; //头指针 int rear; //尾指针，若队列不空，指向队列尾元素的下一个位置 }SqQueue; 初始化一个空队列QStatus InitQueue(SqQueue *Q) { Q->front = 0; Q->rear = 0; return OK; } 循环队列长度int QueueLength(SqQueue Q) { return (Q.rear-Q.front+MAXSIZE)%MAXSIZE; } 入队列Status EnQueue(SqQueue *Q, QElemType e) { if((Q->rear+1)%MAXSIZE == Q->front) //队列满的判断 return ERROR; Q->data[Q->rear] = e; //将元素e赋值给队尾 Q->rear = (Q->rear+1)%MAXSIZE; //rear指针向后移一位置 return OK; } 出队列Status DeQueue(SqQueue *Q, QElemType *e) { if(Q->front == Q->rear) //队列空的判断 return ERROR; *e = Q->data[Q->front]; //将队头元素赋值给e Q->front = (Q->front + 1)%MAXSIZE; //front指针向后移一位置 } 3.3.3、队列的链式存储结构定义：队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们把他简称为链队列 链队列的结构typedef int QElemType; typedef struct QNode //结点结构 { QElemType data; struct QNode *next; }QNode, *QueuePtr; typedef struct //队列的链表结构 { QueuePtr front, rear; //队头、队尾指针 }LinkQueue; 入队Status EnQueue(LinkQueue *Q, QElemType e) { QueuePtr s = (QueuePtr)malloc(sizeof(QNode)); if(!s) //存储分配失败 exit(OVERFLOW); s->data = e; s->next = NULL; Q->rear->next = s; //把新结点赋值给原队尾结点 Q->rear = s; //将s设置为当前尾结点 return OK; } 出队Status DeQueue(LinkQueue *Q, QElemType *e) { QueuePtr p; if(Q->front == Q->rear) //如果为空队列 return ERROR; p = Q->front->next; //将要删除的队头结点暂存给P *e = p->data; //获取p中的数据给e Q->front->next = p->next;//将原队头结点后继p->next赋值给头结点后继 if(Q->rear == p) //若队头是队尾，则删除后将rear指向头结点 Q->rear = Q->front; free(p); return OK; }总结： 栈：是限定仅在表尾进行插入和删除操作的线性表队列：是允许在一端进行插入操作，而在另一端进行删除操作的线性表 4、串定义：串是由零个或多个字符组成的有限序列，又名叫字符串 4.1、串的存储 ADT串(string)Data 串中元素仅由一个字符串组成，相邻元素具有前驱和后继关系OperationStrAssign(T, *chars):生成一个其值等于字符串常量chars的串T StrCopy(T,S):串S存在，由串S复制得串T ClearString(S):串S存在，将串清空 StringEmpty(S):若串S为空，返回true，否则返回false StrLength(S):返回串S的元素个数，即串的长度 StrCompare(S,T):若S>T，返回值>0，若S=T，返回0，若Slchild = pre; //左孩子指针指向前驱 } if(!pre->rchild) //前驱没有右孩子 { pre->RTag = Thread; //后继线索 pre->rchild = p; //前驱右孩子指针指向后继（当前结点P） } pre = p; //保持pre指向p的前驱 InThreading(p->rchild); //递归右子树线索化 } } 5.4、赫夫曼树及其应用定义：赫夫曼编码是美国数学家赫夫曼发明的，他的编码用到了特殊二叉树，我们称之为赫夫曼树 我们同时将带权路径长度WPL最小的二叉树称为赫夫曼树，我们总是将最小的两个值组成一个二叉树，父级值为两个孩子之和，然后将这个二叉树顶点再放入集合对象，从新选择最小的两个值，组成二叉树，以此类推生成最优二叉树 应用：用于压缩文件、解决数据传输最优化问题 6、图定义：图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G（V，E），其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合 图的数据结构 ADT图（Graph）Data 顶点的有穷非空集合和边的集合OperationGreateGraph(*G, V, VR):按照顶点集V和边弧集VR的定义构造图G DestroyGraph(*G):图G存在则销毁 LocateVex(G,u):若图G中存在顶点u，则返回图中的位置 GetVex(G,v):返回图G中顶点v的值 PutVex(G,v,value):将图G中顶点v赋值value FirstAdjVex(G,*v):返回顶点v的一个邻接顶点，若顶点在G中无邻接顶点返回空 NextAdjVex(G,v,*w):返回顶点v相对于顶点w的下一个邻接顶点，若w是v的 最后一个邻接点则返回“空” InsertVex(*G,v):在图G中增添新顶点v DeleteVex(*G,v):删除图G中顶点v及其相关的弧 InsertArc(*G,v,w):在图G中增添弧，若G是无向图，还需要增添 对称弧 DeleteArc(*G,v,w):对图G中删除弧，若G是无向图，则还删除对称弧 DFSTraverse(G):对图G中进行深度优先遍历，在遍历过程对每个顶点调用 HFSTraverse(G):对图G中进行广度优先遍历，在遍历过程对每个顶点调用 endADT 6.1、图的存储 6.1.1、邻接矩阵图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息  邻接矩阵存储结构typedef char VertexType; //顶点类型应由用户定义
typedef int EdgeType; //边上的权值类型应由用户定义
#define MAXVEX 100 //最大顶点数，由用户定义
#define INFINITY 65535 //用65535来代表无限
typedef struct
{
VertexType vexs[MAXVEX]; //顶点表
EdgeType arc[MAXVEX][MAXVEX]; //邻接矩阵，可看作边表
int numVertexes, numEdges; //图中当前的顶点数和边数
}MGraph;
无向网-构造图void CreateMGraph(MGraph *G)
{
int i, j, k, w;
printf("输入顶点数和边数：\n");
scanf("%d, %d", &G->numVertexes, &G->numEdges); //输入顶点数和边数
for(i = 0; i numVertexes; i++) //读入顶点信息，建立顶点表
scanf(&G->vexs[i]);
for(i = 0; i numVertexes; i++)
for(j = 0; j numVertexes; j++)
G->arc[i][j] = INFINITY; //初始化邻接矩阵
for(k = 0; k numEdges; k++) //读入numEdges条边，建立邻接矩阵
{
printf("输入边（vi,vj）上的下标i，下标j和权w:\n");
scanf("%d, %d, %d", &i, &j, &w); //输入边(vi,vj)上的权w
G->arc[i][j] = w
G->arc[j][i] = G->arc[i][j]; //因为是无向图，矩阵对称
}
}
6.1.2、邻接表
定义：数组与链表相结合的存储方法称为邻接表 无向图邻接表结构如下： 边集数组是由两个一维数组构成。一个是存储顶点的信息；另一个是存储边的信息，这个边数组每个数据元素由一条边的起点下标、终点下标和权组成 6.2、图的遍历定义：从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫做图的遍历 6.2.1、深度优先遍历深度优先遍历，也有称为深度优先搜索，简称为DFS 邻接矩阵的深度优先递归算法typedef int Boolean; //Boolean是布尔类型，其值是TRUE或FALSE Boolean visited[MAX]; //访问标志的数组 void DFS(MGraph G, int i) { int j; visited[i] = TRUE; printf("%c ", G.vexs[i]); //打印顶点，也可以其他操作 for(j = 0; j adjvex]) DFS(GL, p->adjvex); //对为访问的邻接顶点递归调用 p = p->next; } } 邻接表的深度遍历操作void DFSTraverse(GraphAdjList GL) { int i; for(i = 0; i numVertexes; i++) visited[i] = FALSE; //初始所有顶点状态都是未访问状态 for(i = 0; i numVertexes; i++) if(!visited[i]) //对未访问过的顶点调用DFS，若是连通图，只会执行一次 DFS(GL, i); } 6.2.2、广度优先遍历广度优先遍历，又称为广度优先搜索，简称DFS 邻接矩阵的广度遍历算法void BFSTraverse(MGraph G) { int i, j; Queue Q; for(i = 0; i |
有向图邻接表如下： 
【本文地址】
今日新闻 |
推荐新闻 |