博客访问： 1368912
博文数量： 266
博客积分： 1305
博客等级： 军士长
技术积分： 4616
注册时间：
不懂的东西还有很多，随着不断的学习，不懂的东西更多，无法消灭更多不懂的东西，那就不断的充实自己吧。
欢迎关注微信公众号：菜鸟的机器学习
IT168企业级官微
微信号：IT168qiye
系统架构师大会
微信号：SACC2013
分类： C/C++
一、图的存储结构
1.1 邻接矩阵
& & 图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（邻接矩阵）存储图中的边或弧的信息。
& & 设图G有n个顶点，则邻接矩阵是一个n*n的方阵，定义为：
& & 看一个实例，下图左就是一个无向图。
& & 从上面可以看出，无向图的边数组是一个对称矩阵。所谓对称矩阵就是n阶矩阵的元满足aij&= aji。即从矩阵的左上角到右下角的主对角线为轴，右上角的元和左下角相对应的元全都是相等的。
& & 从这个矩阵中，很容易知道图中的信息。
& & （1）要判断任意两顶点是否有边无边就很容易了；
& & （2）要知道某个顶点的度，其实就是这个顶点vi在邻接矩阵中第i行或（第i列）的元素之和；
& & （3）求顶点vi的所有邻接点就是将矩阵中第i行元素扫描一遍，arc[i][j]为1就是邻接点；
& & 而有向图讲究入度和出度，顶点vi的入度为1，正好是第i列各数之和。顶点vi的出度为2，即第i行的各数之和。
& & 若图G是网图，有n个顶点，则邻接矩阵是一个n*n的方阵，定义为：
& & 这里的wij表示(vi,vj)上的权值。无穷大表示一个计算机允许的、大于所有边上权值的值，也就是一个不可能的极限值。下面左图就是一个有向网图，右图就是它的邻接矩阵。
& & 那么邻接矩阵是如何实现图的创建的呢？代码如下。
#include &stdio.h&
#include &stdlib.h&
#include &curses.h&
typedef char VertexT
&&&&&&&&//顶点类型应由用户定义
typedef int EdgeT
&&&&&&&&//边上的权值类型应由用户定义
#define MAXVEX 100
//最大顶点数，应由用户定义
#define INFINITY 65535
&&&&&&&&//用65535来代表无穷大
#define DEBUG
typedef struct
VertexType vexs[MAXVEX]; &&&&&&&&//顶点表
arc[MAXVEX][MAXVEX]; &&&&&&&&//邻接矩阵，可看作边
int numVertexes, numE
//图中当前的顶点数和边数
int locates(Graph *g, char ch)
int i = 0;
for(i = 0; i & g-&numV i++)
if(g-&vexs[i] == ch)
if(i &= g-&numVertexes)
return -1;
//建立一个无向网图的邻接矩阵表示
void CreateGraph(Graph *g)
int i, j, k,
printf("输入顶点数和边数:\n");
scanf("%d,%d", &(g-&numVertexes), &(g-&numEdges));
#ifdef DEBUG
printf("%d %d\n", g-&numVertexes, g-&numEdges);
for(i = 0; i & g-&numV i++)
g-&vexs[i] = getchar();
while(g-&vexs[i] == '\n')
g-&vexs[i] = getchar();
#ifdef DEBUG
for(i = 0; i & g-&numV i++)
printf("%c ", g-&vexs[i]);
printf("\n");
for(i = 0; i & g-&numE i++)
for(j = 0; j & g-&numE j++)
g-&arc[i][j] = INFINITY; //邻接矩阵初始化
for(k = 0; k & g-&numE k++)
printf("输入边(vi,vj)上的下标i，下标j和权值:\n");
p = getchar();
while(p == '\n')
p = getchar();
q = getchar();
while(q == '\n')
q = getchar();
scanf("%d", &w);
int m = -1;
int n = -1;
m = locates(g, p);
n = locates(g, q);
if(n == -1 || m == -1)
fprintf(stderr, "there is no this vertex.\n");
//getchar();
g-&arc[m][n] =
g-&arc[n][m] = g-&arc[m][n]; //因为是无向图，矩阵对称
void printGraph(Graph g)
for(i = 0; i & g.numV i++)
for(j = 0; j & g.numV j++)
printf("%d
", g.arc[i][j]);
printf("\n");
int main(int argc, char **argv)
//邻接矩阵创建图
CreateGraph(&g);
printGraph(g);
&& & 从代码中可以得到，n个顶点和e条边的无向网图的创建，时间复杂度为O(n + n2&+ e)，其中对邻接矩阵Grc的初始化耗费了O(n2)的时间。
1.2 邻接表
& & 邻接矩阵是不错的一种图存储结构，但是，对于边数相对顶点较少的图，这种结构存在对存储空间的极大浪费。因此，找到一种数组与链表相结合的存储方法称为邻接表。
& & 邻接表的处理方法是这样的：
& & （1）图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过，数组可以较容易的读取顶点的信息，更加方便。
& & （2）图中每个顶点vi的所有邻接点构成一个线性表，由于邻接点的个数不定，所以，用单链表存储，无向图称为顶点vi的边表，有向图则称为顶点vi作为弧尾的出边表。
& & 例如，下图就是一个无向图的邻接表的结构。
& & 从图中可以看出，顶点表的各个结点由data和firstedge两个域表示，data是数据域，存储顶点的信息，firstedge是指针域，指向边表的第一个结点，即此顶点的第一个邻接点。边表结点由adjvex和next两个域组成。adjvex是邻接点域，存储某顶点的邻接点在顶点表中的下标，next则存储指向边表中下一个结点的指针。
& & 对于带权值的网图，可以在边表结点定义中再增加一个weight的数据域，存储权值信息即可。如下图所示。
& & 对于邻接表结构，图的建立代码如下。
/* 邻接表表示的图结构 */
#include &stdio.h&
#include&stdlib.h&
#define DEBUG
#define MAXVEX 1000
//最大顶点数
typedef char VertexT
//顶点类型应由用户定义
typedef int EdgeT
//边上的权值类型应由用户定义
typedef struct EdgeNode
//边表结点
//邻接点域，存储该顶点对应的下标
//用于存储权值，对于非网图可以不需要
struct EdgeNode *
//链域，指向下一个邻接点
typedef struct VertexNode
//顶点表结构
//顶点域，存储顶点信息
EdgeNode *
//边表头指针
}VertexNode, AdjList[MAXVEX];
typedef struct
AdjList adjL
int numVertexes, numE //图中当前顶点数和边数
int Locate(GraphList *g, char ch)
for(i = 0; i & MAXVEX; i++)
if(ch == g-&adjList[i].data)
if(i &= MAXVEX)
fprintf(stderr,"there is no vertex.\n");
return -1;
//建立图的邻接表结构
void CreateGraph(GraphList *g)
EdgeNode *e;
EdgeNode *f;
printf("输入顶点数和边数:\n");
scanf("%d,%d", &g-&numVertexes, &g-&numEdges);
#ifdef DEBUG
printf("%d,%d\n", g-&numVertexes, g-&numEdges);
for(i = 0; i & g-&numV i++)
printf("请输入顶点%d:\n", i);
g-&adjList[i].data = getchar();
//输入顶点信息
g-&adjList[i].firstedge = NULL;
//将边表置为空表
while(g-&adjList[i].data == '\n')
g-&adjList[i].data = getchar();
//建立边表
for(k = 0; k & g-&numE k++)
printf("输入边(vi,vj)上的顶点序号:\n");
p = getchar();
while(p == '\n')
p = getchar();
q = getchar();
while(q == '\n')
q = getchar();
m = Locate(g, p);
n = Locate(g, q);
if(m == -1 || n == -1)
#ifdef DEBUG
printf("p = %c\n", p);
printf("q = %c\n", q);
printf("m = %d\n", m);
printf("n = %d\n", n);
//向内存申请空间，生成边表结点
e = (EdgeNode *)malloc(sizeof(EdgeNode));
if(e == NULL)
fprintf(stderr, "malloc() error.\n");
//邻接序号为j
e-&adjvex =
//将e指针指向当前顶点指向的结构
e-&next = g-&adjList[m].
//将当前顶点的指针指向e
g-&adjList[m].firstedge =
f = (EdgeNode *)malloc(sizeof(EdgeNode));
if(f == NULL)
fprintf(stderr, "malloc() error.\n");
f-&adjvex =
f-&next = g-&adjList[n].
g-&adjList[n].firstedge =
void printGraph(GraphList *g)
int i = 0;
#ifdef DEBUG
printf("printGraph() start.\n");
while(g-&adjList[i].firstedge != NULL && i & MAXVEX)
printf("顶点:%c
", g-&adjList[i].data);
EdgeNode *e = NULL;
e = g-&adjList[i].
while(e != NULL)
printf("%d
", e-&adjvex);
printf("\n");
int main(int argc, char **argv)
CreateGraph(&g);
printGraph(&g);
&& & 对于无向图，一条边对应都是两个顶点，所以，在循环中，一次就针对i和j分布进行插入。
& & 本算法的时间复杂度，对于n个顶点e条边来说，很容易得出是O(n+e)。
1.3 十字链表
& & 对于有向图来说，邻接表是有缺陷的。关心了出度问题，想了解入度就必须要遍历整个图才知道，反之，逆邻接表解决了入度却不了解出度情况。下面介绍的这种有向图的存储方法：十字链表，就是把邻接表和逆邻接表结合起来的。
& & 重新定义顶点表结点结构，如下所示。
& & 其中firstin表示入边表头指针，指向该顶点的入边表中第一个结点，firstout表示出边表头指针，指向该顶点的出边表中的第一个结点。
& & 重新定义边表结构，如下所示。
& & 其中，tailvex是指弧起点在顶点表的下表，headvex是指弧终点在顶点表的下标，headlink是指入边表指针域，指向终点相同的下一条边，taillink是指边表指针域，指向起点相同的下一条边。如果是网，还可以增加一个weight域来存储权值。
& & 比如下图，顶点依然是存入一个一维数组，实线箭头指针的图示完全与邻接表相同。就以顶点v0来说，firstout指向的是出边表中的第一个结点v3。所以，v0边表结点hearvex = 3，而tailvex其实就是当前顶点v0的下标0，由于v0只有一个出边顶点，所有headlink和taillink都是空的。
& & 重点需要解释虚线箭头的含义。它其实就是此图的逆邻接表的表示。对于v0来说，它有两个顶点v1和v2的入边。因此的firstin指向顶点v1的边表结点中headvex为0的结点，如上图圆圈1。接着由入边结点的headlink指向下一个入边顶点v2，如上图圆圈2。对于顶点v1，它有一个入边顶点v2，所以它的firstin指向顶点v2的边表结点中headvex为1的结点，如上图圆圈3。
& & 十字链表的好处就是因为把邻接表和逆邻接表整合在一起，这样既容易找到以v为尾的弧，也容易找到以v为头的弧，因而比较容易求得顶点的出度和入度。
& & 而且除了结构复杂一点外，其实创建图算法的时间复杂度是和邻接表相同的，因此，在有向图应用中，十字链表是非常好的数据结构模型。
& & 这里就介绍以上三种存储结构，除了第三种存储结构外，其他的两种存储结构比较简单。
二、图的遍历
& & 图的遍历和树的遍历类似，希望从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫图的遍历。
& & 对于图的遍历来说，如何避免因回路陷入死循环，就需要科学地设计遍历方案，通过有两种遍历次序方案：深度优先遍历和广度优先遍历。
2.1 深度优先遍历
& & 深度优先遍历，也有称为深度优先搜索，简称DFS。其实，就像是一棵树的前序遍历。
& & 它从图中某个结点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到。若图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中的所有顶点都被访问到为止。
& & 我们用邻接矩阵的方式，则代码如下所示。
#define MAXVEX
//最大顶点数
typedef int B &&&&&&&&//Boolean 是布尔类型，其值是TRUE 或FALSE
Boolean visited[MAXVEX];&&&&&&&&//访问标志数组
#define TRUE 1
#define FALSE 0
//邻接矩阵的深度优先递归算法
void DFS(Graph g, int i)
visited[i] = TRUE;
printf("%c ", g.vexs[i]);
&&&&&&&&&&&&&&&&//打印顶点，也可以其他操作
for(j = 0; j & g.numV j++)
if(g.arc[i][j] == 1 && !visited[j])
DFS(g, j);
//对为访问的邻接顶点递归调用
//邻接矩阵的深度遍历操作
void DFSTraverse(Graph g)
for(i = 0; i & g.numV i++)
visited[i] = FALSE;
//初始化所有顶点状态都是未访问过状态
for(i = 0; i & g.numV i++)
if(!visited[i])
//对未访问的顶点调用DFS，若是连通图，只会执行一次
& & 如果使用的是邻接表存储结构，其DFSTraverse函数的代码几乎是相同的，只是在递归函数中因为将数组换成了链表而有不同，代码如下。
//邻接表的深度递归算法
void DFS(GraphList g, int i)
EdgeNode *p;
visited[i] = TRUE;
printf("%c ", g-&adjList[i].data); //打印顶点，也可以其他操作
p = g-&adjList[i].
if(!visited[p-&adjvex])
DFS(g, p-&adjvex);
//对访问的邻接顶点递归调用
//邻接表的深度遍历操作
void DFSTraverse(GraphList g)
for(i = 0; i & g.numV i++)
visited[i] = FALSE;
for(i = 0; i & g.numV i++)
if(!visited[i])
DFS(g, i);
&& & 对比两个不同的存储结构的深度优先遍历算法，对于n个顶点e条边的图来说，邻接矩阵由于是二维数组，要查找某个顶点的邻接点需要访问矩阵中的所有元素，因为需要O(n2)的时间。而邻接表做存储结构时，找邻接点所需的时间取决于顶点和边的数量，所以是O(n+e)。显然对于点多边少的稀疏图来说，邻接表结构使得算法在时间效率上大大提高。
2.2 广度优先遍历
& & 广度优先遍历，又称为广度优先搜索，简称BFS。图的广度优先遍历就类似于树的层序遍历了。
& & 邻接矩阵做存储结构时，广度优先搜索的代码如下。
//邻接矩阵的广度遍历算法
void BFSTraverse(Graph g)
for(i = 0; i & g.numV i++)
visited[i] = FALSE;
InitQueue(&q);
for(i = 0; i & g.numV i++)//对每个顶点做循环
if(!visited[i])
//若是未访问过
visited[i] = TRUE;
printf("%c ", g.vexs[i]); //打印结点，也可以其他操作
EnQueue(&q, i);
//将此结点入队列
while(!QueueEmpty(q))
//将队中元素出队列，赋值给
DeQueue(&q, &m);
for(j = 0; j & g.numV j++)
//判断其他顶点若与当前顶点存在边且未访问过
if(g.arc[m][j] == 1 && !visited[j])
visited[j] = TRUE;
printf("%c ", g.vexs[j]);
EnQueue(&q, j);
&&&&对于邻接表的广度优先遍历，代码与邻接矩阵差异不大， 代码如下。
//邻接表的广度遍历算法
void BFSTraverse(GraphList g)
EdgeNode *p;
for(i = 0; i & g.numV i++)
visited[i] = FALSE;
InitQueue(&q);
for(i = 0; i & g.numV i++)
if(!visited[i])
visited[i] = TRUE;
printf("%c ", g.adjList[i].data); //打印顶点，也可以其他操作
EnQueue(&q, i);
while(!QueueEmpty(q))
DeQueue(&q, &m);
p = g.adjList[m].
找到当前顶点边表链表头指针
if(!visited[p-&adjvex])
visited[p-&adjvex] = TRUE;
printf("%c ", g.adjList[p-&adjvex].data);
EnQueue(&q, p-&adjvex);
& & &&对比图的深度优先遍历与广度优先遍历算法，会发现，它们在时间复杂度上是一样的，不同之处仅仅在于对顶点的访问顺序不同。可见两者在全图遍历上是没有优劣之分的，只是不同的情况选择不同的算法。
&&&&& & 参考：《大话数据结构》
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& & 梦醒潇湘love
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& & & & & & & & & & & & & &&& &15:30
阅读(80388) | 评论(3) | 转发(23) |
相关热门文章
给主人留下些什么吧！~~
邻接表结构实现的创建图&void&CreateGraph(GraphList&*g)，你是随意写的每个顶点加两个边数，和图片里的内容不一致，对吧？
：没必要这么拘泥于book，数组的不足在于浪费空间，链表的不足在于cache的命中不行，可以综合数组和链表的有点，用变长数组来矩阵做邻接
说的对&&应该学会变通&&&感谢 |
没必要这么拘泥于book，数组的不足在于浪费空间，链表的不足在于cache的命中不行，可以综合数组和链表的有点，用变长数组来矩阵做邻接
请登录后评论。&&&数据结构(第二版)
自营订单满39元（含）免运费
不足金额订单收取运费5元起
邀请好友参加吧
版 次：2页 数：340字 数：525000印刷时间：日开 本：纸 张：胶版纸印 次： 包 装：平装是否套装：否国际标准书号ISBN：9所属分类：&&
下载免费当当读书APP
品味海量优质电子书，尊享优雅的阅读体验，只差手机下载一个当当读书APP
本商品暂无详情。
当当价：为商品的销售价，具体的成交价可能因会员使用优惠券、积分等发生变化，最终以订单结算页价格为准。
划线价：划线价格可能是图书封底定价、商品吊牌价、品牌专柜价或由品牌供应商提供的正品零售价（如厂商指导价、建议零售价等）或该商品曾经展示过的销售价等，由于地区、时间的差异化和市场行情波动，商品吊牌价、品牌专柜价等可能会与您购物时展示的不一致，该价格仅供您参考。
折扣：折扣指在划线价（图书定价、商品吊牌价、品牌专柜价、厂商指导价等）某一价格基础上计算出的优惠比例或优惠金额。如有疑问，您可在购买前联系客服咨询。
异常问题：如您发现活动商品销售价或促销信息有异常，请立即联系我们补正，以便您能顺利购物。
当当购物客户端手机端1元秒
当当读书客户端万本电子书免费读&&& “数据结构”是计算机科学与技术专业、软件工程专业甚至于其它电气信息类专业的重要专业基础课程。它所讨论的知识内容和提倡的技术方法，无论对进一步学习计算机领域的其它课程，还是对从事大型信息工程的开发，都是重要而必备的基础。&&& 程序设计解决问题往往有多种方法，且不同方法之间的效率可能相差甚远。程序的时间和空间效率，不仅跟数据的组织方式有关，也跟处理流程的巧妙程度有关。本课程将介绍并探讨有关数据组织、算法设计、时间和空间效率的概念和通用分析方法，帮助学员学会数据的组织方法和一些典型算法的实现，能够针对问题的应用背景分析，选择合适的数据结构，从而培养高级程序设计技能。&&& 注意：本课程只涉及最基础的数据结构和与之关联的最基本的算法，更多更复杂的数据结构和经典的解决优化问题的算法，将在后续课程中介绍。&&& 本课程的特点是，对每一种重要的经典数据结构，我们都会从实际应用问题出发，导出其定义、实现（存储）方法以及操作实现，并以更丰富的综合应用案例和练习题帮助学员增强对理论的感性认识，从而明白这些数据结构为什么存在以及在什么情况下可以最好地解决什么样的问题。为了兼顾起点不同的学员，课程中特意设计了“小白专场”系列，手把手教授如何将解决问题的抽象算法用具体的代码实现，从而引导初学者更好地入门。&&& 坚持完成本课程学习、并按照要求完成所有练习的学员，应该具备了PAT（）甲级需要的所有基础知识，辅以充分的英语阅读能力和熟练的编程能力，应可以取得优良成绩。
&&& 这门课的一个重要目的是，帮助大家明白一些经典的数据结构为什么存在、以及在什么情况下可以最好地解决什么样的问题。要做到这一点，非自己动手解决问题不可。&&& 与程序设计课程类似，每一周的课后，我们都留有两类练习，一类是在线完成的选择、是非或填空题，以下称作“小测验”；一类是在的配套练习网站上的，以下称作“编程练习”。你可以自己注册帐户，随时进行练习，并不限于发布练习的时段。注意：你的PTA账号所用的电子邮箱必须与中国大学MOOC的账号进行绑定（同时在两个窗口登录PTA和中国大学MOOC，进入PTA用户名下的“详细资料”，点击“绑定”即可）。如果忘记帐号或密码，可以用你注册时登记的电子邮箱找回。&&& 课程过半时，我们还会安排一次期中考试，是在线完成的选择、是非或填空题，不包括编程题。期中考试在两周内用连续的60分钟完成均有效。&&& 最后，在期末后一周，我们会安排一次在线期末考试，需要在某一天内用连续的120分钟完成。&&& 本课程获得证书的资格，由以下因素决定：编程练习：必须在期末考试前在PTA的中获得200分及以上，才有资格获得证书，但是分数不会带入总评成绩；期中考试：得分占总评分数的40%；期末考试：得分占总评分数的60%； & &此外，若你的期末考试成绩高于期中考试或者无期中成绩，则期末占100%；若你的期末考试成绩低于期中考试，则期中考试占40%，期末考试占60%。&&& 满足条件1并且总评成绩达到60分及以上者，可以获得本课程的合格证书。&&& 在课程结束后，参加2017年秋季或冬季的PAT甲级考试，获得70分及以上者，可以获得优秀证书。 & &&& & 另加福利：最后获得合格证书的同学，总评分在[80,&100]区间内者，可以申领50元PAT代金券；在[60, 80)区间内者，可以申领20元PAT代金券。全国考点通用，一年有效。申领者用本课程注册邮箱发邮件到&领取。
&&& 学过一门编程语言，具有一定编程基础，即可理解主要内容，因为数据结构本质上是不依赖于编程语言的，且编程练习平台可以接受二十余种语言代码的提交。但由于算法描述多用类似C语言的伪码，且“小白系列”仅讲解C语言的算法实现，所以如果学过C语言会更容易接受。&&& 如果还对计算机处理离散结构的基本理论和方法有较为系统的理解（即预修“离散数学”），则对更扎实地掌握本课程内容有很大帮助，但并不是必须的。
第一讲 基本概念 [陈越]1.1 什么是数据结构1.2 什么是算法1.3 应用实例：最大子列和问题第二讲 线性结构 [何钦铭]2.1 线性表及其实现2.2 堆栈2.3 队列2.4 应用实例：多项式加法运算小白专场：一元多项式的乘法与加法运算- C语言实现&第三讲 树(上) [何钦铭]3.1 树与树的表示3.2 二叉树及存储结构3.3 二叉树的遍历小白专场：树的同构 - C语言实现&第四讲 树（中）[何钦铭]4.1 二叉搜索树4.2 平衡二叉树小白专场：是否同一棵二叉搜索树- C语言实现线性结构之习题选讲[陈越]：Reversing Linked List&第五讲 树（下）[何钦铭]5.1 堆5.2 哈夫曼树与哈夫曼编码5.3 集合及运算小白专场：堆中的路径 - C语言实现小白专场[陈越]：File Transfer - C语言实现第六讲 图（上）[陈越]6.1 什么是图6.2 图的遍历6.3 应用实例：拯救0076.4 应用实例：六度空间小白专场：如何建立图- C语言实现&第七讲 图（中）[陈越]树之习题选讲-Tree Traversals Again树之习题选讲-Complete Binary Search Tree树之习题选讲- Huffman Codes7.1 最短路径问题小白专场：哈利·波特的考试- C语言实现&第八讲 图（下）[陈越]8.1 最小生成树问题8.2 拓扑排序图之习题选讲-旅游规划&第九讲 排序（上）[陈越]9.1 简单排序（冒泡、插入）9.2 希尔排序9.3 堆排序9.4 归并排序&第十讲 排序（下）[陈越]10.1 快速排序10.2 表排序10.3 基数排序10.4 排序算法的比较&第十一讲 散列查找 [何钦铭]11.1 散列表11.2 散列函数的构造方法11.3 冲突处理方法11.4 散列表的性能分析11.5 应用实例：词频统计小白专场：电话聊天狂人- C语言实现第十二讲 综合习题选讲 [陈越]习题选讲-Insert or Merge习题选讲-Sort with Swap(0,*)习题选讲-Hashing - Hard Version&
推荐教辅和资料：&1．《数据结构》（第2版），陈越、何钦铭、徐镜春、魏宝刚、杨枨 编著，高等教育出版社，2016年6月2．《数据结构学习与实验指导》，陈越、何钦铭、徐镜春、魏宝刚、杨枨 编著，高等教育出版社，2013年5月3． 课程练习网站：PTA（Programming Teaching Assistant）：&本课程的编程练习将在这里布置。PAT（Programming Ability Test）官网： 提供全部考试真题。
0。我忘记了帐户信息怎么办呀？！答：如果是PTA上的，可以自己用邮箱找回。如果是PAT上的，请用你注册时登记的电子邮箱发求助信到 chenyue@。1。我不是计算机专业的，能学这门课吗？答：只要会写程序就能学。2。我数学不好，能学这门课吗？答：会算术就可以了…… 有个别例子涉及基础数学概念（比如什么是多项式），花一分钟上网搜索一下定义就可以搞定。3。我不会写程序，能学这门课吗？答：不能…… 还是先学会写程序再说吧~ 隔壁翁恺老师的C语言讲得很好懂，推荐~4。学这门课每周要花多少时间？答：平均4-8小时，开始可能轻松一点，后面的课业会越来越重 —— 这样你才能长进嘛~ 建议开课前先去PTA做一下：如果1小时内能做到满分，这门课你是可以轻松搞定的；如果需要2小时，那么你学这门课每周估计要花5小时以上；如果3小时还拿不到满分，那你这门课可能要花8小时以上（说不好是每周还是每天……）5。为什么我的程序在自己机器上跑得好好的，提交到PTA网站就各种错误？答：因为你自己用于测试自己程序的数据太弱了同学…… 另外一定注意严格按照题目要求输出结果，不要输出如“Please input ...”之类的多余信息。要用标准输入输出，不要从文件读写。不要急，想想ACM竞赛的世界冠军们也是这样哭着走过来的，心理就平衡了~6。PTA的测试数据能不能公布呀？答：不能。公布数据后一定会有人直接打印结果的…… 不过，如果在某组数据上卡了比较长的时间，可以到论坛上哭诉，老师会在一段时间后打开那组数据的提示信息。7。什么是PAT甲级，能吃？答：PAT是Programming Ability Test的缩写，是一个考试，分顶级、甲级、乙级三个级别。证书真的能吃 —— 就如托福考试在留学申请中的作用一样，百余家联盟企业划定了PAT分数线，对达到分数线的考生给予免除与编程能力测试相关的笔试，直接邀请进入面试的机会。数十家企业的HR排队打电话请你去面试，想想也是醉了……8。什么时候考PAT最合适？答：一般大三下半学期春季考试，凭成绩在企业春招中找份实习工作，暑假先去实践一下，对找工作非常有帮助。&&& 或者大四开学参加秋季考试，正对上企业大规模秋招的时间。&&& 万一秋季没考好、并且秋招时没找到理想的工作，还可以参加冬季考试、同时选择春季才把成绩推送给企业。&&& 万一冬季也没考好，还有最后一次春季考试，这样大四阶段还可以抓住最后春招的机会。9。我想拿优秀证书，要怎么申请？答：首先确认自己有获得合格证书的资格，并且申请合格证书。在此基础上，参加今年秋季或冬季的PAT甲级考试。获得70分及以上者，用你在MOOC上注册用的邮箱发邮件到 chenyue@，报上自己的身份证、准考证、证书编号，审核通过即可获得优秀证书。PTA常见问题及解答评分试题的解答提交后由评分系统评出即时得分，每一次提交会判决结果会及时通知；系统可能的反馈信息包括：结 & 果说 & 明等待评测
评测系统还没有评测到这个提交，请稍候正在评测
评测系统正在评测，稍候会有结果编译错误 您提交的代码无法完成编译，点击“编译错误”可以看到编译器输出的错误信息答案正确 恭喜！您通过了这道题部分正确 您的代码只通过了部分测试点，继续努力！格式错误 您的程序输出的格式不符合要求（比如空格和换行与要求不一致）答案错误 您的程序未能对评测系统的数据返回正确的结果运行超时您的程序未能在规定时间内运行结束内存超限 您的程序使用了超过限制的内存非零返回 您的程序结束时返回值非 0，如果使用 C 或 C++ 语言要保证 int main 函数最终 return 0段错误 您的程序发生段错误，可能是数组越界，堆栈溢出（比如，递归调用层数太多）等情况引起浮点错误您的程序运行时发生浮点错误，比如遇到了除以 0 的情况内部错误
评测系统发生内部错误，无法评测。工作人员会努力排查此种错误常见问题*我应该从哪里读输入，另外应该输出到哪里？如果没有特别说明，你的程序应该从标准输入（stdin，传统意义上的“键盘”）读入，并输出到标准输出（stdout，传统意义上的“屏幕”），不要使用文件做输入输出。由于系统是在你的程序运行结束后开始检查输出是否是正确的，对于有多组测试数据的输入，可以全部读入之后再输出，也可以处理一组测试数据就输出一组。*为什么我的程序交在这里得到编译错误，而我在自己的机器上已经编译通过了？本系统所使用的编译器和你在自己机器上使用的可能有区别，请留意几个常见的地方：本系统是 64 位 Linux 系统，使用的编译器版本和编译参数可以参见编译器帮助Java 代码需使用 Main 作为主类名Visual C++ 6.0 和 Turbo C++ 3.0 （及它们的更低版本）有较多违背 C++ 标准（ISO/IEC 14882）的地方，不要使用它们来判断 C++ 程序语法上是否有问题C++ 下 64 位整数的类型是 long long，不要使用 __int64*为什么我的程序得到了“返回非零”？返回零表示一个程序正常结束，如果没有返回零，则系统认为程序没有正常结束，这时即便输出了正确的内容也不予通过。C 或 C++ 代码请确认 int main 函数最终会返回 0，不要声明为 double main 或者 void main有异常的语言，请确认程序处理了可能抛出的异常*程序的时间和内存占用是如何计算的？程序的运行时间为程序在所有 CPU 核占用的时间之和，内存占用取程序运行开始到结束占用内存的最大值。*为什么同样的程序运行时间和所用内存会不同？程序运行时间会受到许多因素的影响，尤其是在现代多任务操作系统以及在使用动态库的情况下，多次使用同一输入运行同一程序所需时间和内存有一些不同是正常
现象。我们的题目给出的运行限制一般为标准程序的若干倍，也就是说，选用正确的算法和合适的语言，那么运行限制是富余的。*不同语言的时间限制和内存限制是相同的吗？是相同的，我们认为选择合适的编程语言也是一项必备技能，所以没有为不同语言设置不同的限制条件。*我提交的代码可以做什么，有什么限制吗？没有。这里没有系统调用白名单，也没有针对语言限制可使用的包或库。虽然我们比较宽容大度，但还是请不要做不符合道义的事情。如果你需要使用我们系统没有提供的某个语言的某个库，或者需要更改编译参数，可以联系我们。其他问题在考试或比赛中遇到其他问题请咨询现场工作人员。
由高教社联手网易推出，让每一个有提升愿望的用户能够学到中国知名高校的课程，并获得认证。
| 京ICP备号-2 |
(C) icourse163.org