文享日志

数据结构概述

发表于2018年09月07日12:25:28

0条评论 68次阅读

一、概念

数据结构是对相关的数据项进行组织的特殊架构


二、类型

常用数据结构有:

线性数据结构、图、树、集合与字典


三、数据结构

1、线性数据结构

两种最重要的基本数据结构是数组和链表。

数组是n个相同的数据类型的元素构成的序列,它们连续存储在计算机的存储器中,只要指定数组下标就可以访问到这些元素

链表是0个或多个称为节点的元素构成的序列,每隔节点包含两类信息:一类是数据;另一类是一个或多个指向其他节点的地址(指针)。


链表通常有两种单链表和双链表。单链表除了为节点,每个节点都包含一个指向下一元素的指针。双链表除了首位两个节点,每一个节点都同时包含指向前趋的指针和指向后继的指针。


数组与链表都属于线性列表(简称列表)。列表是按照一定的线性顺序排列的数据项集合。基本操作包括对元素的查找、插入和删除


栈和队列是两种特殊类型的列表。栈是一种插入删除都在端部进行的列表,这一段称为栈顶。满足"后进后出"。队列是一种删除和插入分别在列表两头进行的数据机构,进行删除操作的一头称之为队头,删除操作称为出队,进行插入操作的一头称为队尾,插入操作称为入队。队列满足"先进先出"


2、图

通俗的讲,图可以看做平面上的"顶点"或者"节点"构成的集合,某些顶点被称为"边"或者"弧"的线段连接。如果边是有方向的,则图为有向图,否则为无向图。


任意两点都有边相连,则称为完全图。如果相对完全图,所缺边较少,则称稠密图,所缺边较多,则称稀疏图


2.1表示法

图通常用邻接矩阵或邻接表来表示。


邻接矩阵

n个顶点的邻接矩阵是一个n*n的布尔矩阵,图中每个顶点有一行和一列来表示。若第i到第j个节点有边,则矩阵中第i行第j列为1,否则为0.


邻接链表

图中的每一个顶点用一个邻接链表表示,该链表包含了和这个顶点邻接的所有节点。


如果图是稀疏图,使用邻接链表。若果图是稠密图,使用邻接矩阵。


2.2加权图

加权图即在图的基础上,为边加权值。


2.3路径与环

路径时图G中始于u止于v的邻接序列(就是图的邻接链表中的任意一条序列)。

如果路径中所有顶点不同,则为简单路径。

路径长度是该路径顶点长度-1(即边的个数)。

连通图是图中任意两点都是连通的。

非连通图如果包含几个自我连通的部分,该部分称为连通分量


回路是一种起点和终点都是同一顶点的路径,长度大于0,同一条边不会包含两次。


3、树

树是一种连通无回路图

森林是无回路并且不一定连通的图,森林的每一个连通分量是一棵树


3.1有根树

随机选择自由树的一个顶点作为根,该树为有根树


3.2有序树

有序树是一个有根树,且树中每一顶点的所有子女都是有序的。


二叉查找树是在二叉树的基础上,分配给每隔父母顶点的数字都比它左子树的数字大,比右子树中的数字小。


4、集合与字典

集合是互不相同项的无序组合。


从集合中查找一个给定元素、增加新元素和删除一个元素。能实现这三种操作的数据结构称为字典。







👍 0  👎 0
共有0条评论

发表新评论

提交

广告展示

腾讯云推广 阿里云推广