数据结构图的构建算法

⑴ 数据结构有哪些基本算法

数据结构是一门研究非数值计算的程序设计问题中的操作对象，以及它们之间的关系和操作等相关问题的学科。

可以理解为：程序设计 = 数据结构 + 算法

数据结构算法具有五个基本特征：输入、输出、有穷性、确定性和可行性。

1、输入：一个算法具有零个或者多个输出。以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件。后面一句话翻译过来就是，如果一个算法本身给出了初始条件，那么可以没有输出。比如，打印一句话：NSLog(@"你最牛逼！");

2、输出：算法至少有一个输出。也就是说，算法一定要有输出。输出的形式可以是打印，也可以使返回一个值或者多个值等。也可以是显示某些提示。

3、有穷性：算法的执行步骤是有限的，算法的执行时间也是有限的。

4、确定性：算法的每个步骤都有确定的含义，不会出现二义性。

5、可行性：算法是可用的，也就是能够解决当前问题。

数据结果的基本算法有：

1、图搜索（广度优先、深度优先）深度优先特别重要

2、排序

3、动态规划

4、匹配算法和网络流算法

5、正则表达式和字符串匹配

6、三路划分-快速排序

7、合并排序（更具扩展性，复杂度类似快速排序）

8、DF/BF 搜索 （要知道使用场景）

9、Prim / Kruskal （最小生成树）

10、Dijkstra （最短路径算法）

11、选择算法

⑵ 一文带你认识30个重要的数据结构和算法

数组是最简单也是最常见的数据结构。它们的特点是可以通过索引（位置）轻松访问元素。

它们是做什么用的？

想象一下有一排剧院椅。每把椅子都分配了一个位置（从左到右），因此每个观众都会从他将要坐的椅子上分配一个号码。这是一个数组。将问题扩展到整个剧院（椅子的行和列），您将拥有一个二维数组（矩阵）。

特性

链表是线性数据结构，就像数组一样。链表和数组的主要区别在于链表的元素不存储在连续的内存位置。它由节点组成——实体存储当前元素的值和下一个元素的地址引用。这样，元素通过指针链接。

它们是做什么用的？

链表的一个相关应用是浏览器的上一页和下一页的实现。双链表是存储用户搜索显示的页面的完美数据结构。

特性

堆栈是一种抽象数据类型，它形式化了受限访问集合的概念。该限制遵循 LIFO（后进先出）规则。因此，添加到堆栈中的最后一个元素是您从中删除的第一个元素。

堆栈可以使用数组或链表来实现。

它们是做什么用的？

现实生活中最常见的例子是在食堂中将盘子叠放在一起。位于顶部的板首先被移除。放置在最底部的盘子是在堆栈中保留时间最长的盘子。

堆栈最有用的一种情况是您需要获取给定元素的相反顺序。只需将它们全部推入堆栈，然后弹出它们。

另一个有趣的应用是有效括号问题。给定一串括号，您可以使用堆栈检查它们是否匹配。

特性

队列是受限访问集合中的另一种数据类型，就像前面讨论的堆栈一样。主要区别在于队列是按照FIFO（先进先出）模型组织的：队列中第一个插入的元素是第一个被移除的元素。队列可以使用固定长度的数组、循环数组或链表来实现。

它们是做什么用的？

这种抽象数据类型 (ADT) 的最佳用途当然是模拟现实生活中的队列。例如，在呼叫中心应用程序中，队列用于保存等待从顾问那里获得帮助的客户——这些客户应该按照他们呼叫的顺序获得帮助。

一种特殊且非常重要的队列类型是优先级队列。元素根据与它们关联的“优先级”被引入队列：具有最高优先级的元素首先被引入队列。这个 ADT 在许多图算法（Dijkstra 算法、BFS、Prim 算法、霍夫曼编码 ）中是必不可少的。它是使用堆实现的。

另一种特殊类型的队列是deque 队列（双关语它的发音是“deck”）。可以从队列的两端插入/删除元素。

特性

Maps （dictionaries）是包含键集合和值集合的抽象数据类型。每个键都有一个与之关联的值。

哈希表是一种特殊类型的映射。它使用散列函数生成一个散列码，放入一个桶或槽数组：键被散列，结果散列指示值的存储位置。

最常见的散列函数（在众多散列函数中）是模常数函数。例如，如果常量是 6，则键 x 的值是x%6。

理想情况下，散列函数会将每个键分配给一个唯一的桶，但他们的大多数设计都采用了不完善的函数，这可能会导致具有相同生成值的键之间发生冲突。这种碰撞总是以某种方式适应的。

它们是做什么用的？

Maps 最着名的应用是语言词典。语言中的每个词都为其指定了定义。它是使用有序映射实现的（其键按字母顺序排列）。

通讯录也是一张Map。每个名字都有一个分配给它的电话号码。

另一个有用的应用是值的标准化。假设我们要为一天中的每一分钟（24 小时 = 1440 分钟）分配一个从 0 到 1439 的索引。哈希函数将为h(x) = x.小时*60+x.分钟。

特性

术语：

因为maps 是使用自平衡红黑树实现的（文章后面会解释），所以所有操作都在 O(log n) 内完成；所有哈希表操作都是常量。

图是表示一对两个集合的非线性数据结构：G={V, E}，其中 V 是顶点（节点）的集合，而 E 是边（箭头）的集合。节点是由边互连的值 - 描述两个节点之间的依赖关系（有时与成本/距离相关联）的线。

图有两种主要类型：有向图和无向图。在无向图中，边(x, y)在两个方向上都可用：(x, y)和(y, x)。在有向图中，边(x, y)称为箭头，方向由其名称中顶点的顺序给出：箭头(x, y)与箭头(y, x) 不同。

它们是做什么用的？

特性

图论是一个广阔的领域，但我们将重点介绍一些最知名的概念：

一棵树是一个无向图，在连通性方面最小（如果我们消除一条边，图将不再连接）和在无环方面最大（如果我们添加一条边，图将不再是无环的）。所以任何无环连通无向图都是一棵树，但为了简单起见，我们将有根树称为树。

根是一个固定节点，它确定树中边的方向，所以这就是一切“开始”的地方。叶子是树的终端节点——这就是一切“结束”的地方。

一个顶点的孩子是它下面的事件顶点。一个顶点可以有多个子节点。一个顶点的父节点是它上面的事件顶点——它是唯一的。

它们是做什么用的？

我们在任何需要描绘层次结构的时候都使用树。我们自己的家谱树就是一个完美的例子。你最古老的祖先是树的根。最年轻的一代代表叶子的集合。

树也可以代表你工作的公司中的上下级关系。这样您就可以找出谁是您的上级以及您应该管理谁。

特性

二叉树是一种特殊类型的树：每个顶点最多可以有两个子节点。在严格二叉树中，除了叶子之外，每个节点都有两个孩子。具有 n 层的完整二叉树具有所有2ⁿ-1 个可能的节点。

二叉搜索树是一棵二叉树，其中节点的值属于一个完全有序的集合——任何任意选择的节点的值都大于左子树中的所有值，而小于右子树中的所有值。

它们是做什么用的？

BT 的一项重要应用是逻辑表达式的表示和评估。每个表达式都可以分解为变量/常量和运算符。这种表达式书写方法称为逆波兰表示法 (RPN)。这样，它们就可以形成一个二叉树，其中内部节点是运算符，叶子是变量/常量——它被称为抽象语法树（AST）。

BST 经常使用，因为它们可以快速搜索键属性。AVL 树、红黑树、有序集和映射是使用 BST 实现的。

特性

BST 有三种类型的 DFS 遍历：

所有这些类型的树都是自平衡二叉搜索树。不同之处在于它们以对数时间平衡高度的方式。

AVL 树在每次插入/删除后都是自平衡的，因为节点的左子树和右子树的高度之间的模块差异最大为 1。 AVL 以其发明者的名字命名：Adelson-Velsky 和 Landis。

在红黑树中，每个节点存储一个额外的代表颜色的位，用于确保每次插入/删除操作后的平衡。

在 Splay 树中，最近访问的节点可以快速再次访问，因此任何操作的摊销时间复杂度仍然是 O(log n)。

它们是做什么用的？

AVL 似乎是数据库理论中最好的数据结构。

RBT（红黑树） 用于组织可比较的数据片段，例如文本片段或数字。在 Java 8 版本中，HashMap 是使用 RBT 实现的。计算几何和函数式编程中的数据结构也是用 RBT 构建的。

在 Windows NT 中（在虚拟内存、网络和文件系统代码中），Splay 树用于缓存、内存分配器、垃圾收集器、数据压缩、绳索（替换用于长文本字符串的字符串）。

特性

最小堆是一棵二叉树，其中每个节点的值都大于或等于其父节点的值：val[par[x]]

⑶ 数据结构经典算法有哪些

二叉树遍历：
status initqueue(Queue &Q)
{//初始化一个空队列
Q.base=(QElemtype *)malloc(MAXSIZE*sizeof(QElemtype));
if(!Q.base)
exit(OVERFLOW);
Q.front=Q.rear=0;
return OK;
}

status inqueue(Queue &Q,BiTree e)
{//将元素e入队
if((Q.rear+1)%MAXSIZE==Q.front)
return ERROR;
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1)%MAXSIZE;
return OK;
}

status outqueue(Queue &Q,BiTree &e)
{//删除队头元素，并用e返回其值
if(Q.front==Q.rear)
return ERROR;
e=Q.base[Q.front];
Q.front=(Q.front+1)%MAXSIZE;
return OK;
}

status emptyqueue(Queue Q)
{//若队列空，返回TRUE，否则返回FALSE
if(Q.front==Q.rear)
return TRUE;
return FALSE;
}

//以下是二叉树的算法
void creattree(BiTree &t)
{//先序顺序建立二叉树t
char ch;
ch=getchar();
if(ch==' ')
{
t=NULL;
return;
}
t=(BiTree)malloc(sizeof(BiNode));
if(!t) exit(OVERFLOW);
t->data=ch;
creattree(t->lchild);
creattree(t->rchild);
}
void print(TElemtype e)
{
printf("%c",e);
}
void pretraverse(BiTree t, void (*visit)(TElemtype e))
{//先序遍历二叉树t
if(t)
{
(*visit)(t->data);
pretraverse(t->lchild,visit);
pretraverse(t->rchild,visit);
}
}

void intraverse(BiTree t, void (*visit)(TElemtype e))
{//中序遍历二叉树t
if(t)
{
intraverse(t->lchild,visit);
(*visit)(t->data);
intraverse(t->rchild,visit);
}
}

void posttraverse(BiTree t, void (*visit)(TElemtype e))
{//后序遍历二叉树t
if(t)
{
posttraverse(t->lchild,visit);
posttraverse(t->rchild,visit);
(*visit)(t->data);
}
}

void leveltraverse(BiTree t, void (*visit)(TElemtype e))
{//层次遍历二叉树t
BiNode *p;
Queue Q;
//if(!t) return;
initqueue(Q);
p=t;
inqueue(Q,p);
while(!emptyqueue(Q))
{
outqueue(Q,p);
if(p)
{

(*visit)(p->data);
inqueue(Q,p->lchild);
inqueue(Q,p->rchild);
}
}

}

void destroytree(BiTree &t)
{
if(t==NULL) return;
else if(t->lchild==NULL&&t->rchild==NULL)
{
free(t);
return;
}
else{
destroytree(t->lchild);
destroytree(t->rchild);
free(t);
return;
}
}

⑷ 数据结构必须掌握的算法有哪些

主要是树的遍历，查找，替换和删除。图的遍历。（bfs，dfs）查找里面的二叉树查找
，平均数查找，harsh查找八大排序注意图和树的算法因存储结构不同而不同。其他的如表了什么的，应该不是很难。是必须会的

⑸ 计算机考研：数据结构常用算法解析(7)

第七章：
对于无向图，e的范围是：
数据结构中所讨论的图都是简单图，任意两结点间不会有双重的边。
对于有向图，e的范围是：
图的各种存储结构
邻接矩阵很方便访问任意两点的边，但是不方便计算其邻接点。在深度和广度遍历中广泛的需要求某点的邻接点。所以邻接矩阵只在Floyed和Prim和Dijstra中采用。
邻接表能很方便的求某顶点的邻接点，索引对于与遍历有关的算法大多都采用邻接表。如深度、广度、拓扑排序、关键路径。但他也有不足的地方，就是不方便求入度或是那些薯早握点可以到他的操作。所以有人引进逆邻接表。最后人们把这两种表结合到一起就是十字链表和邻接多重表。一个是存储有向图，另一个是存储无向图。
在十字链睁历表和邻接多重表很方便求邻接点的操作和对应的逆操作。所以实际应用中，凡是能用邻接表实现的一定能用十字链表和邻接多重表实现。并且它们的存储效率更高。
1.邻接矩阵(有向图和无向图和网)又称为数组表示法
typedef struct
{ vextype vexs[maxn]; ∥顶点存储空间∥
adjtype A[maxn][maxn]; ∥邻接矩阵∥
int vexnum,arcnum; //图的顶点数和边数
GraphKind Kind; //图的类型
} mgraph;
2.邻接表(有向图和无向图和网)
typedef struct node ∥边
{ int adj; int w; ∥邻接点、权∥
struct node *next; ∥指向下一弧或边∥
}linknode;
typedef struct ∥顶点类型∥
{ vtype data; ∥顶点值域∥
linknode *farc; ∥指向与本顶点关联的第一条弧或边∥
}Vnode;
typedef struct
{
Vnode G[maxn]; ∥顶点表∥
int vexnum,arcnum;
GraphKind kind;
}ALGraph;
adjvexnextarcinfo
边结点
datafirstarc
顶点结点
3.十字链表(有向图和有向网)
headvextaivexhlinktlinkinfo
边结点
datafirstinfirstout
顶点结点
4.邻接多重表(无向图)
markivexjvexilinkjlinkinfo
边结点
datafirstedge
顶点结点
有向无环图(DAG)：是描述含有公共子式的表达式的有效工具。二叉树也能表示表达式，但是利用有向无环图可以实现对相同子式的共享，从而节省存储空间。
顶点的度：
无向图：某顶点V的度记为D(V)，代表与V相关联的边的条数
有向图：顶点V的度D(V)=ID(V)+OD(V)
强连通分量:在有向图中，若图中任意两顶点间都存在路径，则称其是强连通图。图中极大 强连通子图称之为强连通分量
“极大”在这里指的是：往一个连通分量中再加入顶点和边，就构不成原图中的一个 连通子图，即连通分量是一个最大集的连通子图。有向图的连通就是指该有向图是强连通的。

考研有疑问、不知道如何总结考研考点内容、不清楚数庆考研报名当地政策，点击底部咨询官网，免费领取复习资料：https://www.87dh.com/xl/

⑹ 数据结构中图的建立及算法实现

#include<stdio.h>
#include<stdlib.h>
#define MaxSize 20
struct ArcNode
{
int adjvex;
struct ArcNode *nextarc;
};
struct Vnode
{
int data;
struct ArcNode *firstarc;
};
struct Vnode AdjList[MaxSize];
int m,n,v,cord;
void main()
{
void creatgraph(struct Vnode A[MaxSize]);
void dfs(struct Vnode A[MaxSize]);
do
{
printf("\n 主菜单");
printf("\n 1 建立无向图的邻接表");
printf("\n 2 按深度遍历图");
printf("\n 3 结束程序运行");
printf("\n-----------------------------------");
printf("\n 请输入您的选择 1, 2, 3 -->");
scanf("%d",&cord);
switch(cord)
{
case 1:
creatgraph(AdjList);
break;
case 2:
dfs(AdjList);
break;
case 3:
exit(0);
}
}while(cord<=3);
}//main end
void creatgraph(struct Vnode A[MaxSize])
{
int i,j,k;
struct ArcNode *p;
printf("input arces and vexes:");
scanf("%d %d",&m,&n);
for(k=0;k<n;k++)
{
printf("\ninput arc:");
scanf("%d%d",&i,&j);
p=(struct ArcNode*)malloc(sizeof(struct ArcNode));
p->adjvex=j;
p->nextarc=A[i-1].firstarc;
A[i-1].firstarc=p;
p=(struct ArcNode*)malloc(sizeof(struct ArcNode));
p->adjvex=i;
p->nextarc=A[j-1].firstarc;
A[j-1].firstarc=p;
}
printf("\n");
for(k=0;k<n;k++)
{
printf("%d",A[k].data);
p=A[k].firstarc;
while(p)
{
printf("%d",p->adjvex);
p=p->nextarc;
}
printf("\n");
}
}///creatgraph end
void dfs(struct Vnode A[MaxSize])
{
struct ArcNode *p,*ar[MaxSize];
int x,i,y,top=-1;
int visited[MaxSize];
for(i=0;i<n;i++)
visited[i]=0;
printf("\ninput x:");
scanf("%d",&x);
printf("%d",x);
visited[x-1]=1;
p=A[x-1].firstarc;
while((p)||(top>=0))
{
if(!p)
{
p=ar[top];
top--;
}
y=p->adjvex;
if(visited[y-1]==0)
{
visited[y-1]=1;
printf("->%d",y);
p=p->nextarc;
if(p)
{
top++;
ar[top]=p;
}
p=A[y-1].firstarc;
}
else p=p->nextarc;
}
}