数据结构笔记（c++版，期末复习）

 

目录

一、绪论

1.数据结构基本概念

2.算法定义与特征

二、线性表

1.线性表的定义

2.顺序表的存储结构

3.链式存储结构

三、栈和队列

1、栈的基本概念

2.队列的基本概念

3.循环队列 

四、字符串和多维数组

1.字符串的基本概念

2.串的简单模式匹配

3.多维数组

3.1数组的定义

3.2数组的特点

3.4数组的存储结构与寻址——一维数组

3.5数组的存储结构与寻址——二维数组

4.矩阵的压缩存储

4.1.概念

4.2对称矩阵

4.3三角矩阵

4.4对角矩阵

 4.5稀疏矩阵

5.广义表

5.1概念

5.2题目                                   

五、树和二叉树

1.树的逻辑结构

1.1树的基本概念

1.2树的基本术语

1.3树的遍历操作

2.树的存储结构

2.1 双亲表示法

2.2孩子表示法

 2.3孩子兄弟表示法

小结

3.二叉树的逻辑结构

3.1二叉树基本概念

3.2二叉树的性质

3.3二叉树的存储结构

3.4二叉树的遍历

4. 树、森林与二叉树的转换

5.最优二叉树——哈夫曼树

六、图

1.图的定义

2.图的存储结构

2.1邻接矩阵法o(n^2)

2.2邻接表法o(n+e)

2.2.1邻接表存储的基本思想：

2.2.1邻接表构建

3.图的遍历

1.深度优先遍历(dfs)

2.广度优先遍历（bfs)

4.最小生成树

1.prim算法

2.Kruskal算法:

5.最短路径

6.aov网与拓扑排序

1.概念

2.拓扑排序算法

7.关键路径

七、查找

 1.基本概念

2.查找算法的性能

3.顺序表查找

4.折半查找

5.二叉排序树

6.平衡二叉树

7.散列表查找技术

八、排序

1.选择排序

2.冒泡排序

3.插入排序

4.快速排序

5.归并排序

---

 

一、绪论

1.数据结构基本概念

（1）数据：对客观事物的符号表示。（是计算机中可以操作的对象，是能被计算机识别，并 输入给计算机处理的符号集合。数据不仅仅包括整型、实型等数值类型，还包括字符 及声音、图像、视频等非数值类型。）

（2）数据元素：组成数据的基本单位。（人类中，人就是是数据元素。）

（3）数据项：数据项是数据不可分割的最小单位。一个数据元素可以由若干个数据项组成，数据项是数据的最小单位。 但真正讨论问题时，数据元素才是数据结构中建立数据模型的着眼点。

（比如人这样的数据元素，可以有眼、耳、鼻、嘴、手、脚这些数据项，也可以有姓 名、年龄、性别、出生地址、联系电话等数据项）

（4）数据对象：具有相同性质的数据元素的集合，是数据的子集。（比如，还是刚才的 例子，人都有姓名、生日、性别等相同的数据项）

（5）数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。

数据结构由逻辑结构和存储结构（物理结构）和基本操作组成。

逻辑结构：是指数据对象中数据元素之间的相互关系。包括四种结构：集合结构、线性结构、树形结构、图形结构。

存储结构（物理结构）：是指数据的逻辑结构在计算机中的存储形式。有两种：顺序存储和链式存储。

 

2.算法定义与特征

 

 1.概念：算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列。

2.五个基本特性：输入、输出、有穷性、确定性和可行性。

3.什么是好算法：好的算法，应该具有正确性、可读性、健壮性、高效率和低存储量的特征。

4.算法分析：目的是分析算法效率以求改进，两个主要方面是时间性能和空间性能。

常用时间复杂度所耗费的时间从小到大依次是： 

我们所求的时间复杂度一般在没有特殊说明的情况下，都是指最坏时间复杂度。

二、线性表

1.线性表的定义

（1）线性表：零个或多个具有相同数据类型的数据元素的有限序列。

第一个元素无前驱，最后一个元素无后继。

2.顺序表的存储结构

  (1)顺序表：顺序存储的线性表，其基本思想是用一段连续的存储单元依次存储线性表的数据元素。

（2）特点：随机存储，逻辑上相邻的元素其存储的物理位置也是相邻的

（3）设顺序表的每个元素占用 c 个存储单元，则第 i 个元素的存储地址为：

　　　LOC ( a i ) = LOC ( a 1 ) ＋ ( i － 1 ) × c

（4）顺序存储的实现：一维数组存储顺序表中的数据。

插入操作：o(n)      删除操作：o(n)    按值查找、按位查找

（5）缺点：插入或删除运算不方便，其效率较低，存储分配只能预先进行静态分配，因此当表长变化较大时，难以确定合适的存储规模。

3.链式存储结构

   3.1  链式存储分配的特点：

  根据线性表的长度动态的申请存储空间，以解决顺序存储中存在的存储空间难以确定的问题 

3.2  链式存储结构的实现

  单链表

  双向链表

          循环链表等  

3.3   单链表

（1）结点由数据域和指针域两部分组成。

L1,L2是头指针，也是链表的名字，我们设立头节点只是为了运算更加方便。

 （2）头指针和头节点的异同

 （3）单链表的实现和操作

单链表的构造：头插法和尾插法

支持操作：按值查找、按位查找、删除操作，插入操作：o(n) 

遍历

template 
void LinkList::PrintList()
{
      Node*p=first->next;//工作指针p初始化
      while(p!=nullptr)
      {
          coutdata;
}

插入操作

template 
void LinkList::Insert(int i,T x)
{
   Node*p=first->next,*s=nullptr;
   int count=1;
   while(p!=nullptr&&countnext;
      count++:
   }
  if(p==nullptr)throw"插入位置错误";
 else 
  {
    s=new Node;
    s->data=x;
    s->next=p->next;
    p->next=s;
  }
}

删除操作

T LinkList::Delete(int i)//删除第i个结点
{ 
   T x;
   Node*p=first->next,q=nullptr;
   int count=1;
  while(p!=nullptr&&countnext;
     count++;
   }
  if(p==nullptr||p->next==nullptr)throw"删除位置错误"
 else 
  {
    q=p->next;
    x=q->data;
    p->next=q->next;
    delete q;
    return x;
  }
}

3.4双向链表

结点由三部分构成：前驱指针域，数据域，后继指针域。

优点：更方便数据的插入和删除

3.5循环链表

特点：首尾相接的链表。

优点：可以从任一节点出发，访问链表中的所有节点。

判断循环链表中尾结点：

                   q->next==first。

3.6循环双链表

优点：删除最后一个结点或在最后一个结点之后插入结点十分快。o(1)

3.7顺序表与单链表比较

 若线性表的操作主要是进行查找，很少做插入和删除时，宜采用顺序表做存储结构。

 

对于频繁进行插入和删除的线性表， 宜采用链表做存储结构。

当线性表的长度变化不大， 易于事先确定其大小时，为了节约存储空间，宜采用顺序表作为存储结构。

三、栈和队列

1、栈的基本概念

（1）栈：只允许在一端进行插入和删除操作的线性表

（2）空栈：不含任何数据元素的栈

（3）栈顶：允许插入和删除的一端。

插入：入栈、进栈、压栈

删除：出栈、弹栈

（4）栈底：另一端。

（5）特性：先进后出

（6）n个不同元素进栈，出栈元素不同排列的个数为

逐一进行模拟即可。 

链栈对比顺序栈的优点是便于多个栈共享存储空间和提高效率，且不存在栈满上溢的情况。

（7）用处：栈能适用于递归算法、表达式求值、括号匹配。

（8）两栈共享空间判满：top1+1==top2为栈满

2.队列的基本概念

(1)队列：只允许在表的一端插入，另一端删除的线性表。

允许插入的一端叫队尾， 允许删除的一端叫队头。

（2）特性：先进先出

(3)队列的顺序存储

初始状态：q.front==q.rear==0

判空操作：q.front==q.rear==0

进队操作：队不满时，先送值到队尾元素，在将rear++;

出队操作：队不空时，先取队头元素值，再将front++;

无法判满，因为会假溢出

3.循环队列 

（1）初始：q.front=q.rear=0;

（2）队首指针进1：q.front=(q.front+1)%maxsize

   (3)队尾指针进1：q.rear=(q.rear+1)%maxsize

（4）队列长度：(q.rear+maxsize-q,front)%maxsize

  (5)队空条件：q,front=q,rear=0;

（6）队满条件：(q.rear+1)%maxsize==q.front

需要牺牲一个空间，只能存储maxsize-1个元素

（7）时间复杂度：链队列和循环队列都是o(1)

空间复杂度：循环队列会产生空间浪费，链队列不会.

四、字符串和多维数组

1.字符串的基本概念

(1)字符串（简称串）：是由零个或多个字符组成的有限序列。

串的长度：串中字符的个数

子串：字符串中任意个连续的字符组成的子 序列。

主串：包含子串的串

字符在串中的位置：该字符在串中的序号

子串在主串中的位置以子串的第一个字符在主串中的位置来表示，当两个串的长度相等且每个对应位置的字符都相等时，称这两个串是相等的。

空格串：由一个或多个空格组成的串。

（2）特性：从数据结构来看，串是一种特殊的线性表，特殊性体现在数据元素可以是一个字符。

2.串的简单模式匹配

  (1)模式匹配：子串的定位操作，它求的是子串在主串中的位置。

（2）匹配算法：bf算法，kmp算法

kmp算法一般要求求next数组，在选择题里

T="abcabc"

	a	b	c	a	b	c
序号	0	1	2	3	4	5
next	-1	0	0	0	1	2

next[i]的值表示前0~i个字符串中最大公共前后缀的前缀的最后一个元素的下标，并且规定next[0]=-1

3.多维数组

（1）（多维）数组：线性表中的数据元素可以是线性表，但所有元素的类型相同。

（2）广义表：线性表中的数据元素可以是线性表，且元素的类型可以不相同。

3.1数组的定义

数组是由一组类型相同的数据元素构成的有序集合，每个元素受n(n≥1)个线性关系的约束，并称该数组为 n 维数组。

3.2数组的特点

（1）元素本身可以具有某种结构，属于同一数据类型； （2）数组是一个具有固定格式和数量的数据集合。

（3）二维数组是数据元素为线性表的线性表。

3.4数组的存储结构与寻址——一维数组

Loc(ai)＝Loc(al)＋(i－l)×c

3.5数组的存储结构与寻址——二维数组

（1）按行优先：先行后列，先存储行号较小的元素，行号相同者先存储列号较小的元素。

（2）按列优先：先列后行，先存储列号较小的元素，列号相同者先存储行号较小的元素。

4.矩阵的压缩存储

4.1.概念

(1)压缩存储：为多个值相同的元素只分配一个存储空间，对零元素不分配存储空间，目的是为了节省存储空间。特殊矩阵才能进行压缩存储。

（2）特殊矩阵：具有许多相同矩阵元素或零元素，并且这些相同矩阵元素或零元素的分布具有一定的规律性的矩阵。

常见的特殊矩阵有对称矩阵、三角矩阵、对角矩阵等。

4.2对称矩阵

将内存映射到一维数组 

元素个数=1+2+...+n=n(n+1)/2

在从0开始的一维数组中的下标=n(n+1)/r

下三角中的元素aij(i≥j), 在一维数组中的下标k与i、j的关系为： 

aij是第几个数  =1+2+...+（i-1）+j=i(i-1)/2 +j；

由于一维数组下标从0开始

所以k＝i×(i-1)/2＋j-1

上三角中的元素aij（i＜j），因为aij＝aji，则访问和它对应的元素aji即可，即：

k＝j×(j-1)/2＋i -1

注意题目要求的是下标还是第几个值，行优先还是列优先

4.3三角矩阵

下三角矩阵的压缩存储和对称矩阵类似，不同之处在于除了存储下三角中的元素个数，还要存储对角线上方的常数，因为是同一个常数，所以只存储一个即可。 

（a)  k=n(n+1)/2   i>j  

  (b)  k=n+(n-1)+...+(n-i+2)+(j-i+1)-1=(i-1)(2n-i+2)/2 +(j-i)。

4.4对角矩阵

（1）对角矩阵：所有非零元素都集中在以主对角线为中心的带状区域中，除了主对角线和它的上下方若干条对角线的元素外，所有其他元素都为零。

（2）

 共有n+n-1+n-1=3n-2个元素

aij序号=前i-1行元素个数+第i行元素个数

=2+3（i-2）+j-i+2

=2i+j-2

下标=2i+j-3

 4.5稀疏矩阵

（1）概念：矩阵中非零元素的个数r远远小于矩阵元素个数s。零元素的分布无规律

将非零元素及其行和列构成一个三元组（行标、列标、值）

（2）稀疏矩阵的存储方法：三元组顺序表、十字链表

 

5.广义表

5.1概念

广义表（列表）：  n ( >=0 )个表元素组成的有限序列，记作：

LS = (a0, a1, a2, …, an-1)

  LS是表名，ai是表元素，它可以是表 (称为子表)，可以是数据元素(称为原子)。

  n为表的长度。n = 0 的广义表为空表。

长度：广义表LS中的直接元素的个数；

深度：广义表LS中括号的最大嵌套层数。

表头：广义表LS非空时，称第一个元素为LS的表头；

表尾：广义表LS中除表头外其余元素组成的广义表

5.2题目                                   

A ＝( )                空表 ，长度0，深度1

B ＝(e)               只有一个单元素，长度1，深度1

C ＝(a, (b，c，d))    有一个单元素和一个子表，长度2，深度2

D ＝(A, B, C)      有三个子表，长度3，深度3

E ＝(a, E)       递归表，长度2 ，深度无限

        F ＝(( ))      只有一个空表，长度1，深度2

五、树和二叉树

1.树的逻辑结构

1.1树的基本概念

（1）树：n（n≥0）个结点的有限集合。

当n=0时，称为空树。

树中的每个元素只可能有一个直接前驱，但可以有多个直接后继

（2）任意一棵非空树满足以下条件：

 有且仅有一个特定的称为根的结点；

 当n＞1时，除根结点之外的其余结点被分成m（m>0）个互不相交的有限集合T1,T2,… ,Tm，其中每个集合又是一棵树，并称为这个根结点的子树。

（3）树的定义是采用递归方法

1.2树的基本术语

结点的度：结点所拥有的子树的个数。

树的度：树中各结点度的最大值。

叶子结点：度为0的结点，也称为终端结点。

分支结点：度不为0的结点，也称为非终端结点。

孩子、双亲：树中某结点子树的根结点称为这个结点的孩子结点，这个结点称为它孩子结点的双亲结点；

兄弟：具有同一个双亲的孩子结点互称为兄弟。

祖先、子孙：在树中，如果有一条路径从结点x到结点y，那么x就称为y的祖先，而y称为x的子孙。

路径：如果树的结点序列n1, n2, …, nk有如下关系：结点ni是ni+1的双亲（1lchild); PostOrder(root->rchild); cout>ch; if (ch=='# ') root= nullptr; else { root=new BiNode; root->data=ch; root->lchild=creat(); root->rchild= creat(); } return root }

求树结点的数目

template
int BiTree::count(BiNode* root){
	int number=0;
	if (root== nullptr)
		number=0;
	else
		number=count(root->lchild)+count(root->rchild)+1;
	return number;
}

求叶子结点数目

template 
void BiTree:: countleaf(BiTreeNode * root){
	if (root) {
		if (root->lchild== nullptr && root->rchild== nullptr)
			leafcount=leafcount+1;
		else
		{
			countleaf(root->lchild);
			countleaf(root->rchild);
		}
	}
	return;
}

1.已知一颗二叉树的先序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历的结果是（）。

首先构建二叉树

前序遍历首先遍历根节点，所以A为根节点，对应中序遍历，分为CB（左子树） EDF（右子树）。前序遍历根左右，所以V、B是根，C是B的·左子树，对于EDF，在前序中，D是根，则E是D的左孩子，F是有孩子。所以后序遍历 CBEFDA

题目

1.某二叉树结点的中序序列为ABCDEFG，后序序列为BDCAFGE，则其根节点左子树的结点数目为（4）。

后序遍历最后访问的是根节点，前序最先访问根节点，我们在遇到这种问题时，首先考虑前序和后续找到根节点。

 

注意！由前序和后序遍历，后序和中序遍历序列，可以唯一确定一颗二叉树，但由前序和后序却不能唯一确定一颗二叉树，因为他们俩的根节点不一定相同。

4. 树、森林与二叉树的转换

1.树转化为二叉树

（1）在兄弟结点之间加一条线

（2）对每个结点，只保留他与第一个孩子的连线，抹去与其他孩子的连线。

（3）以树根为轴心，顺时针旋转45度，

 

 

由树转化为二叉树，其根节点的右子树总是空的

2.森林转化为二叉树

(1)把森林中的每颗二叉树转换成相应的二叉树

（2）每颗树的根也可以视为兄弟节点，在每颗树的树根之间加一条连线

（3）以第一颗树的树根为根节点，顺时针选择45度

 转化为二叉树，是没有右儿子的，但是变成森林以后，第二三课树都成为了第一棵树的右儿子。D

3.二叉树转化为森林或树

⑴ 加线——若某结点x是其双亲y的左孩子，则把结点x的右孩子、右孩子的右孩子、……，都与结点y用线连起来；

⑵ 去线——删去原二叉树中所有的双亲结点与右孩子结点的连线；

⑶ 层次调整——整理由⑴、⑵两步所得到的树或森林，使之层次分明。

4.森林的遍历

森林有两种遍历方法：

⑴前序（根）遍历：前序遍历森林中的每一棵树。（一颗一颗来）

⑵后序（根）遍历：后序遍历森林中的每一棵树。  

5.最优二叉树——哈夫曼树

1、叶子结点的权值：对叶子结点赋予的一个有意义的数值量。

2、二叉树的带权路径长度：设二叉树具有n个带权值的叶子结点，从根结点到各个叶子结点的路径长度与相应叶子结点权值的乘积之和。 记为：

lk是从根结点到第k个叶子的路径长度

wk第k个叶子的权值

3.哈夫曼树：带权路径长度最小的二叉树。

给定n个权值分别为w1,w2，···，w,的结点，构造哈夫曼树的算法描述如下!

(1) 将这n 个结点分别作为n棵仅含一个结点的二叉树，构成森林F

(2)构造一个新结点，从F中选取两棵根结点权值最小的树作为新结点的左、右子树，(小的在左，大的在右），且将新结点的权值置为左、右子树上根结点的权值之和。

(3)从F中删除刚才选出的两棵树，同时将新得到的树加入F中。

(4) 重复步骤 (2) 和(3)，直至F中只剩下一棵树为止。

 

4.哈夫曼树的特点：

1. 权值越大的叶子结点越靠近根结点，而权值越小的叶子结点越远离根结点。

2. 只有度为0（叶子结点）和度为2（分支结点）的结点，不存在度为1的结点.

 

 1 。对n(n≥2)个权值均不相同的字符构成哈夫曼树，关于该哈弗曼树的叙述中，错误的是（ ）.

      A：该树一定是一棵完全二叉树

      B：树中一定没有度为1的结点

      C：树中两个权值最小的结点一定是兄弟结点

      D：树中任一非叶结点的权值一定不小于下一层任一结点的权值

答：选A，不一定是一颗完全二叉树

 选D

哈夫曼树不存在度数为1的点

选C，10是110的前缀子串，不符合

 

六、图

1.图的定义

（1) 有向图：若E是有向边(弧) 的有限集合时，则图G为有向图。弧是顶点的有序对记为，其中v,w是顶点，v称为弧尾，w称为弧头，称为从顶点v到顶点w的弧。

(2)无向图：若E是无向边 (边) 的有限集合时，则图G为无向图。边是顶点的无序对记为(v,w)或(w,v)，因为两者相等，其中v,w是顶点，顶点v,w互为邻接点。边(v,w)依附于顶点v,w，或者边(v,w)和顶点v,w相关联。

（3）简单图：一个图G若满足: 不存在重复边; 不存在顶点到自身的边，则称图G为简单图。

(4)多重图：若图G中某两个结点之间的边数多于一条，又允许顶点通过一条边和自己关联，则图G为多重图。

（5）完全图 (简单完全图)：对于无向图，任意两个顶点之间都存在边5)对于有向图，任意两个顶点之间都存在方向相反的两条弧。

含有n个顶点的无向完全图有n×(n-1)/2条边。

含有n个顶点的有向完全图有n×(n-1)条边。

(6) 子图：若图G=（V，E），G'=（V'，E'），如果: V'是V 的子集且E' 是 E 的子集，则称图G'是G的子图。

(7)连通、连通图
在无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的。

若图G中任意两个顶点都是连通的，则称图G是连通图

连通分量：非连通图的极大连通子图称为连通分量。

强连通图：在有向图中，对图中任意一对顶点vi和vj (i≠j)，若从顶点vi到顶点vj和从顶点vj到顶点vi均有路径，则称该有向图是强连通图。

强连通分量：非强连通图的极大强连通子图。

生成树：n个顶点的连通图G的生成树是包含G中全部顶点的一个极小连通子图。

（点不变，边是n-1条，还连通）

（8）稀疏图：称边数很少的图为稀疏图；

       稠密图：称边数很多的图为稠密图。

（9）顶点的度：在无向图中，顶点v的度是指依附于该顶点的边数，通常记为TD (v)。

 

         顶点的入度：在有向图中，顶点v的入度是指以该顶点为弧头的弧的数目，记为ID (v)；

         顶点的出度：在有向图中，顶点v的出度是指以该顶点为弧尾的弧的数目，记为OD (v)。

 

（10）权：是指对边赋予的有意义的数值量。

          网：边上带权的图，也称网图。

 

（11）回路（环）：第一个顶点和最后一个顶点相同的路径。

           简单路径：序列中顶点不重复出现的路径。

           简单回路（简单环）：除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路。

 1.一个n个顶点的连通无向图，其边的个数至少为(n-1)条

 2.要连通具有n个顶点的有向图，至少需要（  n  ）条边

 3.无向图中，所有顶点的度数之和等于边数的两倍。

 

若无向图G=(V,E)中含7个顶点，则保证图G在任何情况下都是连通的，则需要的边数最少是

( )

      A ：6   B：15  C：16   D：21

分析：要想保证在任何情况下都连通，其中6个顶点组成完全图。包含6个顶点的完全图中包含6*5/2=15个条边。第7个顶点和其他6个顶点之间有一条边，就能保证图是联通的。因此，至少需要16条边

2.图的存储结构

2.1邻接矩阵法o(n^2)

2.1.1基本思想：

（1）用一个一维数组存储图中顶点的信息

（2）用一个二维数组（称为邻接矩阵）存储图中各顶点之间的邻接关系。

 

假设图G＝(V，E)有n个顶点，则邻接矩阵是一个n×n的方阵，定义为：

 

2.1.2无向图的邻接矩阵的特点？

（1）主对角线为 0 且一定是对称矩阵。

（2）顶点i的度数=邻接矩阵的第i行（或第i列）非零元素的个数。

（3）求顶点 i 的所有邻接点，将数组中第 i 行元素扫描一遍，若arc[i][j]为1，则顶点 j 为顶点 i 的邻接点。

2.1.3有向图邻接矩阵

（1）有向图的邻接矩阵不一定对称。

（2）顶点 i 的出度=邻接矩阵的第 i 行元素之和。

（3）顶点 i 的入度=邻接矩阵的第 i 列元素之和。

2.1.4

 

创建无向图邻接矩阵代码

1.确定图的顶点个数和边的个数； 2.输入顶点信息存储在一维数组vertex中； 3.初始化邻接矩阵； 4.依次输入每条边存储在邻接矩阵arc中；

     4.1 输入边依附的两个顶点的序号i, j；

     4.2 将邻接矩阵的第i行第j列的元素值置为1；

     4.3 将邻接矩阵的第j行第i列的元素值置为1；

template 
MGraph::MGraph(T a[ ], int n, int e) {
    vertexNum=n; arcNum=e;
    for (i=0; ij;     //边依附的两个顶点的序号
        arc[i][j]=1;  arc[j][i]=1;  //置有边标志    
    }
}

2.2邻接表法o(n+e)

2.2.1邻接表存储的基本思想：

对于图的每个顶点vi，将所有邻接于vi的顶点链成一个单链表，称为顶点vi的边表（对于有向图则称为出边表）

所有边表的头指针和存储顶点信息的一维数组构成了顶点表。

2.2.1邻接表构建

vertex：数据域，存放顶点信息。

firstedge：指针域，指向边表中第一个结点。

adjvex：邻接点域，边的终点在顶点表中的下标。

next：指针域，指向边表中的下一个结点。

有向图构建步骤

 

1. 确定图的顶点个数和边的个数；

 

2. 输入顶点信息，初始化该顶点的边表；

3. 依次输入边的信息并存储在边表中；

     3.1  输入边所依附的两个顶点的序号i和j；

     3.2  生成邻接点序号为j的边表结点s；

     3.3 将结点s插入到第i个边表的头部；

template 
ALGraph::ALGraph(T a[ ], int n, int e)
{   
    vertexNum=n; arcNum=e; 
    for (int i=0; ii>>j; //输入i-j这条边   
         s=new ArcNode;
         s->adjvex=j;  	        
         s->next=adjlist[i].firstedge; //头插法
         adjlist[i].firstedge=s;
     }
}

3.图的遍历

1.深度优先遍历(dfs)

深度优先遍历（Depth_First_Search），也有称为深度优先搜索，简称为DFS。

类似前序遍历

数据结构：stack
优势：空间:o(h)
劣势：不具最短路

每一个dfs对应一个树

重要：顺序（暴搜）

知识点：

{

回溯：往回走的过程，记得恢复现场
递归：同上

剪枝：提前判断，不合适直接跳过

}

基本思想：

⑴ 访问顶点v；

⑵ 从v的未被访问的邻接点中选取一个顶点w，从w出发进行深度优先遍历；

⑶ 重复上述两步，直至图中所有和v有路径相通的顶点都被访问到。

邻接矩阵dfs

int visited[MaxSize];
template 
void MGraph::DFSTraverse(int v){
     coutve[j]+lenvl[j]-len