《数据结构:C++实现》课后答案

  • 更新时间:
  • 7273人关注
  • 点击下载

给大家带来的是关于数据结构相关的课后习题答案下载,介绍了关于数据结构、C++方面的内容,由陈正浩 网友提供,本资源目前已被715人关注,高等院校数据结构类教材综合评分为:8.6分

数据结构是计算机专业教学计划中的一门核心课程,也是信息管理、通信电子、自动控制等与计算机技术关系密切的专业的一门基础课程。要从事和计算机科学与技术相关的工作,尤其是计算机应用领域的开发和研制工作,必须具备坚实的数据结构的基础。本书对C++语言作了简单介绍,叙述了抽象数据类型和面向对象的概念,介绍了线性表、栈、队列、数组、广义表、树和图等数据结构,并且介绍了查找和排序的方法。全书用C++语言描述并实现了所有数据结构的类和程序,并附有习题,便于教学。

本书是为高等院校开设“数据结构”课程编写的教材,可作为计算机专业本科生教材使用,也可供从事计算机软件开发和应用的工程技术人员阅读、参考。

目录

  • 1 绪论
  • 1.1 (算法十数据结构)=程序
  • 1.2 数据结构的基本概念
  • 1.2.1 两个简单的数据结构实例
  • 1.2.2 什么是数据结构
  • 1.3 C++语言基础
  • 1.3.1 程序结构
  • 1.3.2 数据声明和作用域
  • 1.3.3 输入/输出
  • 1.3.4 函数
  • 1.3.5 参数传递
  • 1.3.6 函数各重载
  • 1.3.7 动态内存分配
  • 1.3.8 结构与联合
  • 1.4 算法性能与复杂度
  • 1.4.1 算法的定义
  • 1.4.2 算法的性能标准
  • 1.4.3 算法的复杂度
  • 习题1
  • 2 抽象数据类型和C++类
  • 2.1 抽象数据类型
  • 2.1.1 从数据类型到抽象数据类型
  • 2.1.2 封装和信息隐藏
  • 2.1.3 抽象数据类型描述
  • 2.2 类与对象的基本概念
  • 2.2.1 类与对象
  • 2.2.2 消息与合作
  • 2.2.3 多态性
  • 2.3 面向对象的程序设计方法
  • 2.4 C++类与对象
  • 2.5 构造函数和析构函数
  • 2.6 工具函数
  • 2.7 继承
  • 2.8 this指针的使用
  • 2.9 虚函数、多态性以及动态联编
  • 2.9.1 虚函数和多态性
  • 2.9.2 动态联编
  • 2.10 模板类
  • 习题2
  • 3 线性表
  • 3.1 线性表的定义
  • 3.2 线性表的顺序表示
  • 3.2.1 顺序表的类定’义
  • 3.2.2 顺序表插入、删除算法的复杂度分析
  • 3.2.3 顺序表的应用
  • 3.3 线性表的链表表示
  • 3.3.1 单链表
  • 3.3.2 单循环链表
  • 3.3.3 双向循环链表
  • 3.3.4 静态链表
  • 3.4 多项式抽象数据类型
  • 3.4.1 多项式表示
  • 3.4.2 多项式相加
  • 习题3
  • 4 栈、队列和递归
  • 4.1 栈
  • 4.1.1 顺序栈
  • 4.1.2 链式栈
  • 4.1.3 表达式的计算
  • 4.2 队列
  • 4.2.1 循环队列
  • 4.2.2 链队列
  • 4.3 递归
  • 4.3.1 递归的概念
  • 4.3.2 递归过程与递归工作栈
  • 4.3.3 消除递归
  • 4.3.4 迷宫问题
  • 习题4
  • 5 串、数组和广义表
  • 5.1 字符串
  • 5.1.1 字符串的定义、存储结构和操作
  • 5.1.2 串的操作
  • 5.1.3 常用的C十十字符串函数
  • 5.1.4 串类及其实现
  • 5.1.5 模式匹配算法
  • 5.2 数组
  • 5.2.1 C十十中数组的定义
  • 5.2.2 数组的抽象数据类型表示
  • 5.2.3 数组的顺序存储结构
  • 5.3 稀疏矩阵
  • 5.3.1 三元组顺序表
  • 5.3.2 十字链表
  • 5.4 广义表
  • 5.4.1 广义表的定义
  • 5.4.2 广义表的存储结构
  • 5.4.3 n元多项式的表示
  • 5.4.4 广义表的递归算法
  • 习题5
  • 6 树和森林
  • 6.1 树的概念
  • 6.1.1 树的定义
  • 6.1.2 树的术语
  • 6.1.3 树的表示形式
  • 6.1.4 树的基本操作和抽象数据类型
  • 6.2 二叉树
  • 6.2.1 二叉树的定义
  • 6.2.2 二叉树的性质
  • 6.2.3 二叉树的基本操作和抽象数据类型
  • 6.3 二叉树的存储结构
  • 6.3.1 数组表示法
  • 6.3.2 链表表示法
  • 6.3.3 二叉树的二叉链表类声明
  • 6.4 遍历二叉树
  • 6.4.1 前序遍历
  • 6.4.2 中序遍历
  • 6.4.3 后序遍历
  • 6.4.4 层序遍历
  • 6.5 线索二叉树
  • 6.5.1 线索二又树的定义
  • 6.5.2 线索二叉树的类定义
  • 6.5.3 中序线索二叉树
  • 6.6 二叉树的应用
  • 6.6.1 堆
  • 6.6.2 哈夫曼树
  • 6.7 树和森林
  • 6.7.1 树的存储结构
  • 6.7.2 树、森林和二叉树的转换
  • 6.7.3 树的遍历
  • 6.7.4 森林的遍历
  • 6.8 等价类及其表示
  • 6.8.1 等价关系与等价类
  • 6.8.2 并查集
  • 习题6
  • 7 图
  • 7.1 图的基本概念
  • 7.1.1 图的定义
  • 7.1.2 图的术语
  • 7.1.3 图的基本操作和抽象数据类型
  • 7.2 图的存储结构
  • 7.2.1 邻接矩阵
  • 7.2.2 邻接表
  • 7.2.3 邻接多重表
  • 7.2.4 十字链表
  • 7.3 图的遍历与连通性
  • 7.3.1 深度优先遍历
  • 7.3.2 广度优先遍历
  • 7.3.3 连通分量
  • 7.4 最小生成树
  • 7.4.1 克鲁斯卡尔算法
  • 7.4.2 普里姆算法
  • 7.5 最短路径
  • 7.5.1 弧上权值为非负情形的单源点最短路径问题
  • 7.5.2 弧上权值为任意值的单源点最短路径问题
  • 7.5.3 所有顶点之间的最短路径
  • 7.6 活动网络
  • 7.6.1 用顶点表示活动的网络
  • 7.6.2 用边表示活动的网络(AOE网络)
  • 习题7
  • 8 查找
  • 8.1 基本概念
  • 8.2 顺序表
  • 8.2.1 顺序表的查找
  • 8.2.2 有序表的折半查找
  • 8.3 索引顺序表
  • 8.3.1 索引顺序表
  • 8.3.2 倒排表
  • 8.4 二叉排序树
  • 8.4.1 二叉排序树定义
  • 8.4.2 二叉排序树上的查找
  • 8.4.3 二叉排序树的插入
  • 8.4.4 二叉排序树的删除
  • 8.4.5 二叉排序树查找的性能分析
  • 8.5 平衡二叉树
  • 8.5.1 平衡二叉树的定义
  • 8.5.2 平衡旋转
  • 8.5.3 平衡二叉树的插入和删除
  • 8.6 B-树
  • 8.6.1 动态的m路查找树
  • 8.6.2 B-树
  • 8.6.3 B-树的插入
  • 8.6.4 B-树的删除
  • 8.6.5 B+树
  • 8.7 散列表查找
  • 8.7.1 散列表的基本概念
  • 8.7.2 散列函数
  • 8.7.3 处理溢出的闭散列方法
  • 8.7.4 处理溢出的开散列方法——链地址法
  • 8.7.5 散列表分析
  • 习题8
  • 9 排序
  • 9.1 基础知识
  • 9.1.1 基本概念
  • 9.1.2 排序表的抽象数据类型描述和类定义
  • 9.2 交换排序
  • 9.2.1 冒泡排序
  • 9.2.2 快速排序
  • 9.3 插入排序
  • 9.3.1 直接插入排序
  • 9.3.2 折半插入排序
  • 9.3.3 希尔排序
  • 9.4 选择排序
  • 9.4.1 直接选择排序
  • 9.4.2 锦标赛排序
  • 9.4.3 堆排序
  • 9.5 归并排序
  • 9.5.1 归并
  • 9.5.2 两路归并排序
  • 9.5.3 递归的归并排序
  • 9.6 基数排序
  • 9.6.1 多关键字排序
  • 9.6.2 链式基数排序
  • 9.7 各种排序方法的选择和使用
  • 习题9
  • 主要参考文献
展开阅读
精选笔记1:C++数据结构与算法之反转链表的方法详解

14小时59分钟前回答

本文实例讲述了C++数据结构与算法之反转链表的方法。分享给大家供大家参考,具体如下:

算法概述:要求实现将一条单向链表反转并考虑时间复杂度。

算法分析:

数组法(略):

将列表元素逐个保存进数组,之后再逆向重建列表
点评:实现逻辑最简单,需要额外的内存开销。

移动指针:

通过三个指针逐个从链表头开始逐一反转链表元素的指针
点评:不需要额外的内存开销,会改变原始链表。

递归:

以递归的方式首先找到链表尾部,再逐一反转指针
点评:不需要额外的内存开销,不会改变原始链表。

算法实现:

构建链表结构

/* 节点结构 */
struct NODE
{
 int data;
 struct NODE* next;
};
/* 添加元素-压栈 */
void push(NODE** head, int dat) {
 struct NODE* new_node = new NODE();
 new_node->data = dat;
 new_node->next = *head;
 *head = new_node;
}
/* 添加元素-添加 */
void add(NODE** head, int dat) {
 struct NODE* new_node = new NODE();
 new_node->data = dat;
 new_node->next = NULL;
 if (*head != NULL) {
  struct NODE* temp = *head;
  while (temp->next != NULL) {
   temp = temp->next;
  } 
  temp->next = new_node;
 }
 else {
  *head = new_node;
 }
}

移动指针

/* 反转列表 */
void reverse(NODE** head) {
 struct NODE* pre = NULL;
 struct NODE* cur = *head;
 struct NODE* nxt;
 while (cur != NULL) {
  // 反转指针
  nxt = cur->next;
  cur->next = pre;
  // 移动指针
  pre = cur;
  cur = nxt;
 }
 *head = pre;
}

递归

/* 反转列表-复制原表返回反转表 */
NODE* reverse(NODE* head) {
 if (head == NULL || head->next == NULL) {
  return head;
 }
 NODE* new_head = reverse(head->next);
 // 反转指针
 head->next->next = head;
 head->next = NULL;
 return new_head;
}

打印链表

/* 打印队列 */
void print(NODE* head) {
 NODE* temp = head;
 while (temp != NULL) {
  std::cout << temp->data << std::endl;
  temp = temp->next;
 }
}

完整代码如下:

#include <iostream>
/* 节点结构 */
struct NODE
{
  int data;
  struct NODE* next;
};
/* 添加元素-压栈 */
void push(NODE** head, int dat) {
  struct NODE* new_node = new NODE();
  new_node->data = dat;
  new_node->next = *head;
  *head = new_node;
}
/* 添加元素-添加 */
void add(NODE** head, int dat) {
  struct NODE* new_node = new NODE();
  new_node->data = dat;
  new_node->next = NULL;
  if (*head != NULL) {
    struct NODE* temp = *head;
    while (temp->next != NULL) {
      temp = temp->next;
    }  
    temp->next = new_node;
  }
  else {
    *head = new_node;
  }
}
/* 反转列表 */
void reverse(NODE** head) {
  struct NODE* pre = NULL;
  struct NODE* cur = *head;
  struct NODE* nxt;
  while (cur != NULL) {
    // 反转指针
    nxt = cur->next;
    cur->next = pre;
    // 移动指针
    pre = cur;
    cur = nxt;
  }
  *head = pre;
}
/* 反转列表-复制原表返回反转表 */
NODE* reverse(NODE* head) {
  if (head == NULL || head->next == NULL) {
    return head;
  }
  NODE* new_head = reverse(head->next);
  // 反转指针
  head->next->next = head;
  head->next = NULL;
  return new_head;
}
/* 打印队列 */
void print(NODE* head) {
  NODE* temp = head;
  while (temp != NULL) {
    std::cout << temp->data << std::endl;
    temp = temp->next;
  }
}
int main() {
  struct NODE* n = NULL;
  add(&n, 1);
  add(&n, 2);
  add(&n, 3);
  n = reverse(n);
  print(n);
  return 0;
}

希望本文所述对大家C++程序设计有所帮助。

展开阅读
精选笔记2:C++数据结构之实现邻接表

2小时5分钟前回答

本文实例为大家分享了C++数据结构之实现邻接表的具体代码,供大家参考,具体内容如下

一、图的邻接表实现

1.实现了以顶点顺序表、边链表为存储结构的邻接表;

2.实现了图的创建(有向/无向/图/网)、边的增删操作、深度优先递归/非递归遍历、广度优先遍历的算法;

3.采用顶点对象列表、边(弧)对象列表的方式,对图的创建进行初始化;引用 "ObjArrayList.h"头文件,头文件可参看之前博文“数据结构之顺序列表(支持对象元素)”代码;

4.深度优先遍历分别采用递归/非递归算法;非递归中用到的栈,引用"LinkStack.h"头文件,头文件可参看之前博文“数据结构之栈”代码;

5.广度优先遍历采用队列方式实现;用到的队列,引用 "LinkQueue.h"头文件,头文件可参看之前博文“数据结构之队列”代码;

6.测试代码中以有向网的所有带权边作为边的初始化数据,选择图类型(DG, UDG, DN, UDN)可创建成不同类型的图。

7.优劣分析:

7.1.(优势)邻接表存储结构,相比邻接矩阵,消除了无邻接关系顶点的边存储空间;

7.2.(优势)邻接表比邻接矩阵更容易访问某顶点的邻接顶点;

7.3.(优势)邻接表比邻接矩阵更易于统计边总数,无需逐行逐列遍历;

7.4.(劣势)在确定两顶点间是否有边的搜索过程中,邻接表不如邻接矩阵可直接寻址快,反而需要顶点到边链的遍历;

7.5.(劣势)邻接矩阵在删除顶点时,只需清除对应行列数据即可;而邻接表在清除顶点指向的边链后,还需遍历整个边表,清除所有邻接于此顶点的边结点;

7.6.(不足)邻接表在统计有向图出度时容易,只需遍历依附此顶点的边链;却在统计其入度时,需要遍历整个边表,比较麻烦;可采用十字链表(邻接表与逆邻接表的结合)解决这个问题;

7.7.(不足)邻接表在无向图的存储中,属于行列对称矩阵形式,因此会有一半重复的边数据,故可采用邻接多重表,只存储一半边,来优化存储。

二、测试代码中的图结构

深度优先遍历序列(从 v1 顶点开始):

1.无向图/网:v1-v2-v3-v5-v4-v6-v7

2.有向图/网:v1-v2-v5-v3-v4-v6-v7

广度优先遍历序列(从 v2 顶点开始):

1.无向图/网:v2-v1-v3-v5-v4-v6-v7

2.有向图/网:v2-v5 后序无法遍历

注:有向图的遍历 是遵循出度方向遍历的,若无出度方向,则遍历终止。

三、代码

//文件名:"GraphAdjList.h"
#pragma once
#ifndef GRAPHADJLISL_H_
#define GRAPHADJLISL_H_
 
#include <string>
#include "ObjArrayList.h"
using namespace std;
 
/*
. 图(邻接表实现) Graph Adjacency List
. 相关术语:
. 顶点 Vertex ; 边 Arc ;权 Weight ;
. 有向图 Digraph ;无向图 Undigraph ;
. 有向网 Directed Network ;无向网 Undirected Network ;
. 存储结构:
. 1.顶点表只能采用顺序结构。(因为若采用链式结构,顶点结点定义与边表结点定义就相互引用,无法定义)
. 2.边表采用链表结构。
*/
 
class GraphAdjList
{
 /*
 . 边表(链表)结点
 */
 struct ArcNode
 {
 int adjVex; //邻接顶点所在表中下标
 int weight; //边权重
 ArcNode * next; //下一条边
 };
 /*
 . 顶点表(顺序表)结点
 */
 struct VNode
 {
 string name; //顶点名
 ArcNode * first; //指向的第一个依附该顶点的顶点边结点
 };
public:
 /*
 . 图 种类
 */
 enum GraphType
 {
 DG, //有向图,默认 0
 UDG, //无向图,默认 1
 DN, //有向网,默认 2
 UDN //无向网,默认 3
 };
 /*
 . 边(弧)数据,注:供外部初始化边数据使用
 */
 struct ArcData
 {
 string Tail; //弧尾
 string Head; //弧头
 int Weight; //权重
 };
 
private:
 static const int _MAX_VERTEX_NUM = 10; //支持最大顶点数
 
 VNode vexs[_MAX_VERTEX_NUM]; //顶点表
 int vexs_visited[_MAX_VERTEX_NUM]; //顶点访问标记数组:0|未访问 1|已访问
 int vexNum; //顶点数
 int arcNum; //边数
 int type; //图种类
 
 void _CreateVexSet(ObjArrayList<string> * vexs); //创建顶点集合
 void _CreateDG(ObjArrayList<ArcData> * arcsList); //创建有向图
 void _CreateUDG(ObjArrayList<ArcData> * arcsList); //创建无向图
 void _CreateDN(ObjArrayList<ArcData> * arcsList); //创建有向网
 void _CreateUDN(ObjArrayList<ArcData> * arcsList); //创建无向网
 
 int _Locate(string vertex);   //定位顶点元素位置
 void _InsertArc(int tail, int head, int weight); //插入边(元操作,不分有向/无向)
 void _DeleteArc(int tail, int head);  //删除边(元操作,不分有向/无向)
 void _DFS_R(int index);   //深度优先遍历 递归
 void _DFS(int index);   //深度优先遍历 非递归
 
public:
 GraphAdjList(int type); //构造函数:初始化图种类
 ~GraphAdjList();  //析构函数
 void Init(ObjArrayList<string> * vexs, ObjArrayList<ArcData> * arcsList); //初始化顶点、边数据为 图|网
 void InsertArc(ArcData * arcData); //插入边(含有向/无向操作)
 void DeleteArc(ArcData * arcData); //删除边(含有向/无向操作)
 void Display();  //显示 图|网
 void Display_DFS_R(string *vertex); //从指定顶点开始,深度优先 递归 遍历
 void Display_DFS(string *vertex); //从指定顶点开始,深度优先 非递归 遍历
 void Display_BFS(string *vertex); //从指定顶点开始,广度优先遍历
 
};
//文件名:"GraphAdjList.cpp"
#include "stdafx.h"
#include <string>
#include "ObjArrayList.h"
#include "LinkQueue.h"
#include "LinkStack.h"
#include "GraphAdjList.h"
using namespace std;
 
GraphAdjList::GraphAdjList(int type)
{
 /*
 . 构造函数:初始化图类型
 */
 this->type = type;
 this->vexNum = 0;
 this->arcNum = 0;
}
 
GraphAdjList::~GraphAdjList()
{
 /*
 . 析构函数:销毁图
 */
}
 
void GraphAdjList::Init(ObjArrayList<string> * vexs, ObjArrayList<ArcData> * arcsList)
{
 /*
 . 初始化顶点、边数据,并构建 图|网
 . 入参:
 . vexs: 顶点 列表
 . arcsList: 边数据 列表
 */
 //1.创建顶点集
 _CreateVexSet(vexs);
 //2.根据图类型,创建指定的图
 switch (this->type)
 {
 case DG:
 _CreateDG(arcsList); break;
 case UDG:
 _CreateUDG(arcsList); break;
 case DN:
 _CreateDN(arcsList); break;
 case UDN:
 _CreateUDN(arcsList); break;
 default:
 break;
 }
}
 
void GraphAdjList::_CreateVexSet(ObjArrayList<string> * vexs)
{
 /*
 . 创建顶点集合
 */
 string vertex = "";
 //顶点最大数校验
 if (vexs->Length() > this->_MAX_VERTEX_NUM)
 {
 return;
 }
 //遍历顶点表,无重复插入顶点,并计数顶点数
 for (int i = 0; i < vexs->Length(); i++)
 {
 vertex = *vexs->Get(i);
 if (_Locate(vertex) == -1)
 {
 this->vexs[this->vexNum].name = vertex;
 this->vexs[this->vexNum].first = NULL;
 this->vexNum++;
 }
 }
}
 
void GraphAdjList::_CreateDG(ObjArrayList<ArcData> * arcsList)
{
 /*
 . 创建有向图
 . 邻接矩阵为 非对称边
 */
 //初始化临时 边对象
 ArcData * arcData = NULL;
 //初始化 Tail Head 顶点下标索引
 int tail = 0, head = 0;
 //遍历边数据列表
 for (int i = 0; i < arcsList->Length(); i++)
 {
 //按序获取边(弧)
 arcData = arcsList->Get(i);
 //定位(或设置)边的两端顶点位置
 tail = _Locate(arcData->Tail);
 head = _Locate(arcData->Head);
 //插入边
 _InsertArc(tail, head, 0);
 }
}
 
void GraphAdjList::_CreateUDG(ObjArrayList<ArcData> * arcsList)
{
 /*
 . 创建无向图
 . 邻接矩阵为 对称边
 */
 //初始化临时 边对象
 ArcData * arcData = NULL;
 //初始化 Tail Head 顶点下标索引
 int tail = 0, head = 0;
 //遍历边数据列表
 for (int i = 0; i < arcsList->Length(); i++)
 {
 //按序获取边(弧)
 arcData = arcsList->Get(i);
 //定位(或设置)边的两端顶点位置
 tail = _Locate(arcData->Tail);
 head = _Locate(arcData->Head);
 //插入对称边
 _InsertArc(tail, head, 0);
 _InsertArc(head, tail, 0);
 }
}
 
void GraphAdjList::_CreateDN(ObjArrayList<ArcData> * arcsList)
{
 /*
 . 创建有向网
 . 邻接矩阵为 非对称矩阵
 */
 //初始化临时 边对象
 ArcData * arcData = NULL;
 //初始化 Tail Head 顶点下标索引
 int tail = 0, head = 0;
 //遍历边数据列表
 for (int i = 0; i < arcsList->Length(); i++)
 {
 //按序获取边(弧)
 arcData = arcsList->Get(i);
 //定位(或设置)边的两端顶点位置
 tail = _Locate(arcData->Tail);
 head = _Locate(arcData->Head);
 //插入边
 _InsertArc(tail, head, arcData->Weight);
 }
}
 
void GraphAdjList::_CreateUDN(ObjArrayList<ArcData> * arcsList)
{
 /*
 . 创建无向网
 . 邻接矩阵为 对称矩阵
 */
 //初始化临时 边对象
 ArcData * arcData = NULL;
 //初始化 Tail Head 顶点下标索引
 int tail = 0, head = 0;
 //遍历边数据列表
 for (int i = 0; i < arcsList->Length(); i++)
 {
 //按序获取边(弧)
 arcData = arcsList->Get(i);
 //定位(或设置)边的两端顶点位置
 tail = _Locate(arcData->Tail);
 head = _Locate(arcData->Head);
 //插入对称边
 _InsertArc(tail, head, arcData->Weight);
 _InsertArc(head, tail, arcData->Weight);
 }
}
 
int GraphAdjList::_Locate(string vertex)
{
 /*
 . 定位顶点元素位置
 . 后期可改成【字典树】,顶点数超过100个后定位顶点位置可更快
 */
 //遍历定位顶点位置
 for (int i = 0; i < this->_MAX_VERTEX_NUM; i++)
 {
 if (vertex == this->vexs[i].name)
 {
 return i;
 }
 }
 //cout << endl << "顶点[" << vertex << "]不存在。" << endl;
 return -1;
}
 
void GraphAdjList::_InsertArc(int tail, int head, int weight)
{
 /*
 . 插入边(元操作,不分有向/无向)
 */
 //边结点指针:初始化为 弧尾 指向的第一个边
 ArcNode * p = this->vexs[tail].first;
 //初始化 前一边结点的指针
 ArcNode * q = NULL;
 //重复边布尔值
 bool exist = false;
 //1.边的重复性校验
 while (p != NULL)
 {
 //若已存在该边,则标记为 存在 true
 if (p->adjVex == head)
 {
 exist = true;
 break;
 }
 //若不是该边,继续下一个边校验
 q = p;
 p = p->next;
 }
 //2.1.如果边存在,则跳过,不做插入
 if (exist)
 return;
 //2.2.边不存在时,创建边
 ArcNode * newArc = new ArcNode();
 newArc->adjVex = head;
 newArc->weight = weight;
 newArc->next = NULL;
 //3.1.插入第一条边
 if (q == NULL)
 {
 this->vexs[tail].first = newArc;
 }
 //3.2.插入后序边
 else
 {
 q->next = newArc;
 }
 //4.边 计数
 this->arcNum++;
}
 
void GraphAdjList::InsertArc(ArcData * arcData)
{
 /*
 . 插入边(含有向/无向操作)
 */
 //初始化 Tail Head 顶点下标索引
 int tail = 0, head = 0;
 tail = _Locate(arcData->Tail);
 head = _Locate(arcData->Head);
 //根据图类型,插入边
 switch (this->type)
 {
 case DG:
 _InsertArc(tail, head, 0);
 break;
 case UDG:
 _InsertArc(tail, head, 0);
 _InsertArc(head, tail, 0);
 break;
 case DN:
 _InsertArc(tail, head, arcData->Weight);
 break;
 case UDN:
 _InsertArc(tail, head, arcData->Weight);
 _InsertArc(head, tail, arcData->Weight);
 break;
 default:
 break;
 }
}
 
void GraphAdjList::_DeleteArc(int tail, int head)
{
 /*
 . 删除边(元操作,不分有向/无向)
 */
 //边结点指针:初始化为 弧尾 指向的第一个边
 ArcNode * p = this->vexs[tail].first;
 //初始化 前一边结点的指针
 ArcNode * q = NULL;
 //1.遍历查找边
 while (p != NULL)
 {
 //若存在该边,则结束循环
 if (p->adjVex == head)
 {
 break;
 }
 //若不是该边,继续下一个边
 q = p;
 p = p->next;
 }
 //2.1.边不存在
 if (p == NULL)
 {
 cout << endl << "边[" << this->vexs[head].name << "->" << this->vexs[head].name << "]不存在。" << endl;
 return;
 }
 //2.2.边存在,删除边
 //2.2.1.若为第一条边
 if (q == NULL)
 {
 this->vexs[tail].first = p->next;
 }
 //2.2.2.非第一条边
 else
 {
 q->next = p->next;
 }
 //3.释放 p
 delete p;
}
 
void GraphAdjList::DeleteArc(ArcData * arcData)
{
 /*
 . 删除边(含有向/无向操作)
 */
 //初始化 Tail Head 顶点下标索引
 int tail = 0, head = 0;
 tail = _Locate(arcData->Tail);
 head = _Locate(arcData->Head);
 //根据图类型,删除边
 switch (this->type)
 {
 case DG:
 _DeleteArc(tail, head);
 break;
 case UDG:
 _DeleteArc(tail, head);
 _DeleteArc(head, tail);
 break;
 case DN:
 _DeleteArc(tail, head);
 break;
 case UDN:
 _DeleteArc(tail, head);
 _DeleteArc(head, tail);
 break;
 default:
 break;
 }
}
 
void GraphAdjList::Display()
{
 /*
 . 显示 图|网
 */
 //初始化边表结点指针
 ArcNode * p = NULL;
 cout << endl << "邻接表:" << endl;
 //遍历顶点表
 for (int i = 0; i < this->_MAX_VERTEX_NUM; i++)
 {
 //空顶点(在删除顶点的操作后会出现此类情况)
 if (this->vexs[i].name == "")
 {
 continue;
 }
 //输出顶点
 cout << "[" << i << "]" << this->vexs[i].name << " ";
 //遍历输出边顶点
 p = this->vexs[i].first;
 while (p != NULL)
 {
 cout << "[" << p->adjVex << "," << p->weight << "] ";
 p = p->next;
 }
 cout << endl;
 }
}
 
void GraphAdjList::_DFS_R(int index)
{
 /*
 . 深度优先遍历 递归
 */
 //1.访问顶点,并标记已访问
 cout << this->vexs[index].name << " ";
 this->vexs_visited[index] = 1;
 //2.遍历访问其相邻顶点
 ArcNode * p = this->vexs[index].first;
 int adjVex = 0;
 while (p != NULL)
 {
 adjVex = p->adjVex;
 //当顶点未被访问过时,可访问
 if (this->vexs_visited[adjVex] != 1)
 {
 _DFS_R(adjVex);
 }
 p = p->next;
 }
}
 
void GraphAdjList::Display_DFS_R(string *vertex)
{
 /*
 . 从指定顶点开始,深度优先 递归 遍历
 */
 //1.判断顶点是否存在
 int index = _Locate(*vertex);
 if (index == -1)
 return;
 //2.初始化顶点访问数组
 for (int i = 0; i < this->_MAX_VERTEX_NUM; i++)
 {
 this->vexs_visited[i] = 0;
 }
 //3.深度优先遍历 递归
 cout << "深度优先遍历(递归):(从顶点" << *vertex << "开始)" << endl;
 _DFS_R(index);
}
 
void GraphAdjList::_DFS(int index)
{
 /*
 . 深度优先遍历 非递归
 */
 //1.访问第一个结点,并标记为 已访问
 cout << this->vexs[index].name << " ";
 vexs_visited[index] = 1;
 //初始化 边结点 栈
 LinkStack<ArcNode> * s = new LinkStack<ArcNode>();
 //初始化边结点 指针
 ArcNode * p = this->vexs[index].first;
 //2.寻找下一个(未访问的)邻接结点
 while (!s->Empty() || p != NULL)
 {
 //2.1.未访问过,则访问 (纵向遍历)
 if (vexs_visited[p->adjVex] != 1)
 {
 //访问结点,标记为访问,并将其入栈
 cout << this->vexs[p->adjVex].name << " ";
 vexs_visited[p->adjVex] = 1;
 s->Push(p);
 //指针 p 移向 此结点的第一个邻接结点
 p = this->vexs[p->adjVex].first;
 }
 //2.2.已访问过,移向下一个边结点 (横向遍历)
 else
 p = p->next;
 //3.若无邻接点,则返回上一结点层,并出栈边结点
 if (p == NULL)
 {
 p = s->Pop();
 }
 }
 //释放 栈
 delete s;
}
 
void GraphAdjList::Display_DFS(string *vertex)
{
 /*
 . 从指定顶点开始,深度优先 非递归 遍历
 */
 //1.判断顶点是否存在
 int index = _Locate(*vertex);
 if (index == -1)
 return;
 //2.初始化顶点访问数组
 for (int i = 0; i < this->_MAX_VERTEX_NUM; i++)
 {
 this->vexs_visited[i] = 0;
 }
 //3.深度优先遍历 递归
 cout << "深度优先遍历(非递归):(从顶点" << *vertex << "开始)" << endl;
 _DFS(index);
}
 
void GraphAdjList::Display_BFS(string *vertex)
{
 /*
 . 从指定顶点开始,广度优先遍历
 */
 //1.判断顶点是否存在
 int index = _Locate(*vertex);
 if (index == -1)
 return;
 //2.初始化顶点访问数组
 for (int i = 0; i < this->_MAX_VERTEX_NUM; i++)
 {
 this->vexs_visited[i] = 0;
 }
 //3.广度优先遍历
 cout << "广度优先遍历:(从顶点" << *vertex << "开始)" << endl;
 //3.1.初始化队列
 LinkQueue<int> * vexQ = new LinkQueue<int>();
 //3.2.访问开始顶点,并标记访问、入队
 cout << this->vexs[index].name << " ";
 this->vexs_visited[index] = 1;
 vexQ->EnQueue(new int(index));
 //3.3.出队,并遍历邻接顶点(下一层次),访问后入队
 ArcNode * p = NULL;
 int adjVex = 0;
 while (vexQ->GetHead() != NULL)
 {
 index = *vexQ->DeQueue();
 p = this->vexs[index].first;
 //遍历邻接顶点
 while (p != NULL)
 {
 adjVex = p->adjVex;
 //未访问过的邻接顶点
 if (this->vexs_visited[adjVex] != 1)
 {
 //访问顶点,并标记访问、入队
 cout << this->vexs[adjVex].name << " ";
 this->vexs_visited[adjVex] = 1;
 vexQ->EnQueue(new int(adjVex));
 }
 p = p->next;
 }
 }
 
 //4.释放队列
 int * e;
 while (vexQ->GetHead() != NULL)
 {
 e = vexQ->DeQueue();
 delete e;
 }
 delete vexQ;
}
//文件名:"GraphAdjList_Test.cpp"
#include "stdafx.h"
#include <iostream>
#include "GraphAdjList.h"
#include "ObjArrayList.h"
using namespace std;
 
int main()
{
 //初始化顶点数据
 string * v1 = new string("v1");
 string * v2 = new string("v2");
 string * v3 = new string("v3");
 string * v4 = new string("v4");
 string * v5 = new string("v5");
 string * v6 = new string("v6");
 string * v7 = new string("v7");
 ObjArrayList<string> * vexs = new ObjArrayList<string>();
 vexs->Add(v1);
 vexs->Add(v2);
 vexs->Add(v3);
 vexs->Add(v4);
 vexs->Add(v5);
 vexs->Add(v6);
 vexs->Add(v7);
 
 //初始化边(弧)数据
 GraphAdjList::ArcData * arc1 = new GraphAdjList::ArcData{ "v1", "v2", 2 };
 GraphAdjList::ArcData * arc2 = new GraphAdjList::ArcData{ "v1", "v3", 3 };
 GraphAdjList::ArcData * arc3 = new GraphAdjList::ArcData{ "v1", "v4", 4 };
 GraphAdjList::ArcData * arc4 = new GraphAdjList::ArcData{ "v3", "v1", 5 };
 GraphAdjList::ArcData * arc5 = new GraphAdjList::ArcData{ "v3", "v2", 6 };
 GraphAdjList::ArcData * arc6 = new GraphAdjList::ArcData{ "v3", "v5", 7 };
 GraphAdjList::ArcData * arc7 = new GraphAdjList::ArcData{ "v2", "v5", 8 };
 GraphAdjList::ArcData * arc8 = new GraphAdjList::ArcData{ "v4", "v6", 9 };
 GraphAdjList::ArcData * arc9 = new GraphAdjList::ArcData{ "v4", "v7", 9 };
 GraphAdjList::ArcData * arc10 = new GraphAdjList::ArcData{ "v6", "v7", 9 };
 ObjArrayList<GraphAdjList::ArcData> * arcsList = new ObjArrayList<GraphAdjList::ArcData>();
 arcsList->Add(arc1);
 arcsList->Add(arc2);
 arcsList->Add(arc3);
 arcsList->Add(arc4);
 arcsList->Add(arc5);
 arcsList->Add(arc6);
 arcsList->Add(arc7);
 arcsList->Add(arc8);
 arcsList->Add(arc9);
 arcsList->Add(arc10);
 
 //测试1:无向图
 cout << endl << "无向图初始化:" << endl;
 GraphAdjList * udg = new GraphAdjList(GraphAdjList::UDG);
 udg->Init(vexs, arcsList);
 udg->Display();
 //1.1.深度优先遍历
 cout << endl << "无向图深度优先遍历序列:(递归)" << endl;
 udg->Display_DFS_R(v1);
 cout << endl << "无向图深度优先遍历序列:(非递归)" << endl;
 udg->Display_DFS(v1);
 //1.2.广度优先遍历
 cout << endl << "无向图广度优先遍历序列:" << endl;
 udg->Display_BFS(v2);
 //1.3.插入新边
 cout << endl << "无向图新边:" << endl;
 udg->InsertArc(new GraphAdjList::ArcData{ "v7", "v1", 8 });
 udg->Display();
 //1.4.删除边
 cout << endl << "无向图删除边arc9:" << endl;
 udg->DeleteArc(arc9);
 udg->Display();
 
 //测试2:有向图
 cout << endl << "有向图:" << endl;
 GraphAdjList * dg = new GraphAdjList(GraphAdjList::DG);
 dg->Init(vexs, arcsList);
 dg->Display();
 //2.1.深度优先遍历
 cout << endl << "有向图深度优先遍历序列:(递归)" << endl;
 dg->Display_DFS_R(v1);
 cout << endl << "有向图深度优先遍历序列:(非递归)" << endl;
 dg->Display_DFS(v1);
 //2.2.广度优先遍历
 cout << endl << "有向图广度优先遍历序列:" << endl;
 dg->Display_BFS(v2);
 
 //测试:无向网
 cout << endl << "无向网:" << endl;
 GraphAdjList * udn = new GraphAdjList(GraphAdjList::UDN);
 udn->Init(vexs, arcsList);
 udn->Display();
 
 //测试:有向网
 cout << endl << "有向网:" << endl;
 GraphAdjList * dn = new GraphAdjList(GraphAdjList::DN);
 dn->Init(vexs, arcsList);
 dn->Display();
 
 return 0;
}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持码农之家。

展开阅读

数据结构相关资源

  • C++数据结构与算法(第4版)

    C++数据结构与算法(第4版)

    这本《C++数据结构与算法(第4版)》全面系统地介绍了数据结构,并以C++语言实现相关的算法。 主要强调了数据结构和算法之间的联系,使用面向对象的方法介绍数据结构,其内容包括算法的复

    大小:192.9 MBc++

    立即下载
  • 数据结构 算法与应用 C++语言描述 课后答案

    数据结构 算法与应用 C++语言描述

    《数据结构、算法与应用:C++语言描述》在简要回顾了基本的C++ 程序设计概念的基础上,全面系统地介绍了队列、堆栈、树、图等基本数据结构,以及贪婪算法、分而治之算法、分枝定界算法等多种算法设计方法,为数据结构与算法的继续学习和研究奠定了一个坚实的基础。更为可贵的是,《数据结构、算法与应用:C++语言描述》不仅仅介绍了理论知识,还提供了50多个应用实例及600多道练习题。 目录 译者序 前言 第一部分 预备知识 第1章 C++程序设计

    大小:259 KB数据结构

    立即下载
  • 数据结构、算法与应用:C++语言描述

    数据结构、算法与应用:C++语言描述

    数据结构、算法与应用:C++语言描述(原书第2版) 共分三个部分。第一部分从第1章到第4章,旨在复习C++程序设计的概念以及程序性能的分析和测量方法。第二部分从第5章到第16章,研究数据结构

    大小:109.2 MB数据结构

    立即下载
  • 数据结构:C++版 课后答案

    数据结构:C++版

    《数据结构(C++版)》是2007年武汉大学出版社出版的图书,作者是王艳华、戴小鹏。 《数据结构(C++版)》对常用数据进行了系统的介绍,包括线性表、栈、队列、串、数组、树、图等,详细讨论了查找和排序的各种实现方法和算法,阐明了各种数据结构的内在逻辑关系及其在计算机中的存储表示,给出了每种数据结构的运算及算法描述,并进行了初步的算法分析。全书采用C++语言进行数据结构和算法的描述。 本书对常用数据进行了系统的介绍,包括线性表

    大小:69.2 KB数据结构

    立即下载
  • 数据结构:用面向对象方法与C++语言描述(第2版) 课后答案

    数据结构:用面向对象方法与C++语言描述(第2版)

    数据结构是计算机专业的核心课程,是从事计算机软件开发和应用人员必备的专业基础。随着计算机的日益普及,数据结构课程也在不断地发展。 本书按照清华大学计算机系本科数据结构大纲的要求,从面向对象的概念、对象类设计的风格和数据结构的层次开始,从线性结构到非线性结构,从简单到复,深入地讨论了各种数据结构内在的逻辑关系及其在计算机中的实现方式和使用。此外,对常用的迭代、递归、回溯等算法设计技巧,搜索和排序算法等都

    大小:657 KB数据结构

    立即下载
  • 图解数据结构:使用C++

    图解数据结构:使用C++

    大小:196 MB数据结构

    立即下载

学习笔记

1小时25分钟前回答

C++ 数据结构之水洼的数量算法

C++ 数据结构之水洼的数量算法 题目: 有一个大小为N*M的园子, 雨后起了积水. 八连通的积水被认为是连接在一起的. 请求出园子里总共有多少水洼. 使用深度优先搜索(DFS), 在某一处水洼, 从8个方向查找, 直到找到所有连通的积水. 再次指定下一个水洼, 直到没有水洼为止. 则所有的深度优先搜索的次数, 就是水洼数. 时间复杂度O(8*M*N)=O(M*N). 代码: /* * main.cpp * * Created on: 2014.7.12 *本栏目更多精彩内容:http://www.bianceng.cn/Programming/sjjg/ * Author: spike */ #include stdio.h #include stdlib.h #include string.h #include math.h class Program { static const int MAX_N=20, MAX_M=20; int N = 10, M = 12; char field[MAX_N][MAX_M+1] = { "W........WW.", ".WWW.....WWW", "....WW...WW……

11小时38分钟前回答

C++数据结构与算法之反转链表的方法详解

本文实例讲述了C++数据结构与算法之反转链表的方法。分享给大家供大家参考,具体如下: 算法概述: 要求实现将一条单向链表反转并考虑时间复杂度。 算法分析: 数组法(略): 将列表元素逐个保存进数组,之后再逆向重建列表 点评:实现逻辑最简单,需要额外的内存开销。 移动指针: 通过三个指针逐个从链表头开始逐一反转链表元素的指针 点评:不需要额外的内存开销,会改变原始链表。 递归: 以递归的方式首先找到链表尾部,再逐一反转指针 点评:不需要额外的内存开销,不会改变原始链表。 算法实现: 构建链表结构 /* 节点结构 */struct NODE{ int data; struct NODE* next;};/* 添加元素-压栈 */void……