《数据结构与算法》实验指导书
内蒙古工业大学信息工程学院计算机系
20##年9月1日
《数据结构与算法》实验教学大纲
一、基本信息
二、实验安排
三、实验目的、内容与要求
实验一 线性表的创建与访问算法设计(4学时)
（一）实验目的
数据结构于算法实验是计算机类本科学生计算机软件知识重要的实验环节，它将使学生从实践上学会用高级语言程序设计、实现复杂的数据结构，为大型软件设计奠定基础。本实验以某种线性表的创建与访问算法设计作为实验内容，举一反三，全面、深刻掌握线性结构的实现方法，培养解决问题的能力。
（二）实验内容
1、编写生成线性表的函数，线性表的元素从键盘输入；
2、编写在线性表中插入元素的函数；
3、编写在线性表中删除元素的函数；
4、编写输出线性表的函数；
5、编写主函数，调用以上各函数，以便能观察出原线性表以及作了插入或删除后线性表的屏幕输出。
方案一采用顺序存储结构实现线性表。
方案二采用单链表结构实现线性表。
（三）实验要求
1、掌握线性结构的机器内表示；
2、掌握线性结构之上的算法设计与实现；
3、列表对比分析两种数据结构的相应操作的时间复杂度、空间复杂度，阐明产生差异的原因。实验二 二叉树的创建与访问算法设计(4学时)
（一）实验目的
本实验以二叉树的创建与访问算法设计作为实验内容，掌握树型结构的实现方法，培养解决负责问题的能力。
（二）实验内容
1、编写生成二叉树的函数， 二叉树的元素从键盘输入；
2、编写在二叉树中插入元素的函数；
3、编写在二叉树中删除元素的函数；
4、编写遍历并输出二叉树的函数。
方案一采用递归算法实现二叉树遍历算法。
方案二采用非递归算法实现二叉树遍历算法。
（三）实验要求
1、掌握树型结构的机器内表示；
2、掌握树型结构之上的算法设计与实现；
3、列表对比分析两种数据结构的相应操作的时间复杂度、空间复杂度，阐明产生差异的原因。实验三 图的创建与访问算法设计(4学时)
（一）实验目的
本实验以图的创建与访问算法设计作为实验内容，掌握图型结构的实现方法，培养解决负责问题的能力。
（二）实验内容
1、编写生成图的函数， 图的元素从文件输入；
2、编写在图中插入元素的函数；
3、编写在图中删除元素的函数；
4、编写遍历并输出图的函数。
方案一采用BFS深度优先搜索算法实现图的遍历。
方案二采用DFS广度优先搜索算法实现图的遍历。
（三）实验要求
1、掌握图结构的机器内表示；
2、掌握图型结构之上的算法设计与实现；
3、列表对比分析两种数据结构的相应操作的时间复杂度、空间复杂度，阐明产生差异的原因。
四、考核方式
1、学生课前要认真阅读实验教材，理解实验内容与相关理论知识的关系，并完成预习报告；
2、实验课上教师讲解实验难点及需要注意的问题，并对实验数据签字；
3、学生课后要完成实验报告，并将签字的实验数据与实验报告交给带课教师；
4、教师根据学生实验情况，及时对实验内容和方法进行必要的调整和改进。
根据实验预习报告、实验课考勤、课上实验能力与实验效果、实验报告的完成情况确定最终的实验成绩，实验成绩占课程总成绩的10%。
五、建议教材与教学参考书
1、建议教材
[1]严蔚敏、吴伟民主编. 数据结构（C语言版）. 北京：清华大学出版社，1997
2、教学参考书
[1] 严蔚敏、吴伟民主编. 数据结构题集（C语言版）. 北京：清华大学出版社，1997
[2] 李春葆编. 数据结构习题与解析. 北京：清华大学出版社，2002
[3] 刘振鹏主编. 数据结构. 北京：中国铁道出版社，2003
[4] 许卓群编．数据结构．北京：中央电大出版社， 2001
[5] Anany Levitin著．潘彦译．算法设计与分析．北京：清华大学出版社， 2004
六、其它说明
实验报告格式参照信息学院实验报告规范要求。
实验一 线性表的创建与访问算法的设计
一、目的
本实验的目的是进一步理解线性表的逻辑结构和存储结构，进一步提高使用理论知识指导解决实际问题的能力。
二、题目
线性表的创建与访问算法的设计
三、实验类型
设计性。本实验设计了链表，并涉及到了对链表的一些基本操作：建立、删除、插入、查找等基本操作。
四、要求及提示
说明：以下4个题中，任意选作一题。
1、【问题描述】
某百货公司仓库中有一批电视机，构成了一个单链表并存与计算机中，链表的结点指出同样价格的若干台。
【基本要求】
实现以下基本操作：
（1） 从键盘输入电视机的信息，建立电视机链表。
（2） 从键盘输入电视机的信息，实现电视机查询操作。
（3） 从键盘输入电视机的信息，实现电视机入库操作。
（4） 从键盘输入电视机的信息，实现电视机出库操作。
2、【问题描述】
有一班学生上体育课排队，构成了一个单链表，链表的结点存储了学生的学号、姓名。
【基本要求】
实现以下基本操作：
（1） 从键盘输入学生的信息，建立学生链表。
（2） 从键盘输入学生的信息，实现学生查询操作。
（3） 从键盘输入学生的学号值，将学号为x的学生与其右边的学生进行交换。（注：不允许将链表中数据域的值进行交换）
3、【问题描述】
利用单链表存储一元多项式。
【基本要求】
实现以下基本操作：
（1） 从键盘输入一元多项式的信息，建立一元多项式。
（2） 实现两个一元多项式相加，并输出和多项式。
4、【问题描述】
利用单链表存储集合（集合中不存在重复元素）。
【基本要求】
实现以下基本操作：
（1） 从键盘输入集合值，建立集合。
（2） 求集合的并、交和差，并输出结果。
五、实验报告
1、写出每个算法的思想。
2、画出算法流程图。
3、调试程序出现的问题及解决的方法。
4、打印实验报告及程序清单。
5、报告给出测试的结果并写出设计体会。
六、范例参考
1、问题描述
这是单链表的一个综合练习，包括以下各项内容的函数，可共享被调用，可以通过菜单选择方式运行单链表的各种操作。
1) 建立单链表（1）：将用户输入的数据按头插入法建立一个不带头结点的单链表。输入结点数据时以输入一串字符的方式实现，$字符为结束输入字符
2) 建立单链表（2）：将用户输入的数据按头插入法建立一个带头结点的单链表。输入数据方式同上。
3) 建立单链表（3）：将用户输入的数据按尾插入法建立一个不带头结点的单链表。输入数据方式同上。
4) 建立单链表（4）：将用户输入的数据按尾插入法建立一个带头结点的单链表。输入数据方式同上。
5) 逆置单链表：按头插入法建立一个不带头结点的单链表，用最少的辅助空间实现单链表元素的逆置。
6) 有序链表插入元素：建立一个带头结点的单链表，表中元素从小到大有序排列。输入一个元素并将其插入到单链表中正确的位置上。
7) 有序链表删除重复元素：建立一个带头结点的单链表，表中元素递增有序。删除表中值相同的多余元素（即重复元素只保留一个）
8) 无序链表删除重复元素建立一个带头结点的单链表，元素按输入的次序排列。删除表中值相同的多余元素（即重复元素只保留一个）。
9) 两链表合并：建立两个带头结点的单链表a1和a2，元素均递增有序。将两个单链表归并成新的单链表c,c 中元素也递增有序，相同值的元素均保留在c中。
10) 两链表并集：按用户输入的数据建立两个集合a1和a2，同一集合中无重复元素，以带头结点的单链表形式存放。对两集合进行并集运算，结果放在a1 表中。
附：头文件 DATASTRU.H 定义了程序使用的数据结构，在使用时将之拷贝到相应 C 程序的目录下。
#define DATATYPE1 int
#define DATATYPE2 char
#define KEYTYPE int
#define MAXSIZE 100
#define MAXLEN 40
#define VEXTYPE int
#define ADJTYPE int
typedef struct
{ DATATYPE1 datas[MAXSIZE];
int last;
}SEQUENLIST;
typedef struct node
{
DATATYPE2 data;
struct node *next;
}LINKLIST;
typedef struct dnode
{DATATYPE2 data;
struct dnode *prior, *next;
} DLINKLIST;
typedef struct
{ DATATYPE1 data[MAXSIZE];
int top;
}SEQSTACK;
typedef struct snode
{ DATATYPE2 data;
struct snode *next;
}LINKSTACK;
typedef struct
{ DATATYPE1 data[MAXSIZE];
int front, rear;
}SEQQUEUE;
typedef struct qnode
{ DATATYPE1 data;
struct qnode *next;
}LINKQLIST;
typedef struct
{ LINKQLIST *front, *rear;
}LINKQUEUE;
typedef struct
{ char ch[MAXSIZE];
int len;
}SEQSTRING;
typedef struct
{ char *ch;
int len;
} HSTRING;
typedef struct
{ int i, j;
DATATYPE1 v;
}NODE;
typedef struct
{ int m, n, t;
NODE data[MAXLEN];
}SPMATRIX;
typedef struct
{ DATATYPE2 bt[MAXSIZE];
int btnum;
}BTSEQ;
typedef struct node1
{ DATATYPE2 data;
struct node1 *lchild, *rchild;
}BTCHINALR;
typedef struct node2
{ DATATYPE2 data;
struct node2 *lchild, *rchild, *parent;
}BTCHINALRP;
typedef struct
{ DATATYPE2 data;
int parent;
}PTNODE;
typedef struct
{ PTNODE nodes[MAXSIZE];
int nodenum;
}PTTREE;
typedef struct cnode
{ int child;
struct cnode *next;
}CHILDLINK;
typedef struct
{ DATATYPE2 data;
CHILDLINK *headptr;
}CTNODE;
typedef struct
{CTNODE nodes[MAXSIZE];
int nodenum, rootset;
}CTTREE;
typedef struct csnode
{ DATATYPE2 data;
struct csnode *firstchild, *nextsibling;
}CSNODE;
typedef struct
{ VEXTYPE vexs[MAXLEN];
ADJTYPE arcs[MAXLEN][MAXLEN];
int vexnum, arcnum;
int kind;
}MGRAPH;
typedef struct node3
{ int adjvex;
struct node3 *next;
}EDGENODE;
typedef struct
{ VEXTYPE vertex;
EDGENODE *link;
int id;
} VEXNODE;
typedef struct
{ VEXNODE adjlist[MAXLEN];
int vexnum, arcnum;
int kind;
}ADJGRAPH;
typedef struct
{ KEYTYPE key;
}SSELEMENT;
typedef struct
{ SSELEMENT r[MAXSIZE];
int len;
}SSTABLE;
typedef struct node4
{KEYTYPE key;
struct node4 *lchild, *rchild;
} BSTNODE;
typedef struct node5
{
KEYTYPE key;
struct node5 *next;
}CHAINHASH;
typedef struct
{
KEYTYPE key;
}HASHTABLE;
typedef struct
{ KEYTYPE key;
}RECNODE;
2、程序清单
#include "datastru.h"
#include <stdio.h>
#include <malloc.h>
#define DATATYPE2 char
typedef struct node
{DATATYPE2 data;
struct node *next;
}LINKLIST;
int locate(LINKLIST *a,char x)
/*检查元素x是否在a表中*/
{LINKLIST *la;
la = a->next;
while(la !=NULL)
if(la->data == x) return 1;
else la = la->next;
return 0;
}
insert(LINKLIST *a,char x)
/*将x元素加入a表中*/
{LINKLIST *p;
p = (LINKLIST *) malloc(sizeof(LINKLIST));
p->data = x;
p->next = a->next;
a->next = p;
}
void unionn(LINKLIST *a1, LINKLIST *b1){
/*两有序表交集*/
LINKLIST *lb;
lb = b1->next;
while(lb != NULL)
{ if (!locate(a1,lb->data)) /*如果b1表中的一个元素不在a1表中*/
insert(a1,lb->data); /*则将b1表中的该元素加入a1表中*/
lb = lb->next;}
}
void unite(LINKLIST *a, LINKLIST *b, LINKLIST *c){
/*a, b为两有序链表，合并到c表，并保持有序*/
LINKLIST *la, *lb, *lc, *p;
la = a->next; lb = b->next; lc = c;
while(la != NULL && lb != NULL)
{ if (la->data <= lb->data)
{ p = (LINKLIST *) malloc(sizeof(LINKLIST));
p->data = la->data; p->next = NULL;
lc->next = p; lc = lc->next; la = la->next;
}
else
{ p = (LINKLIST *) malloc(sizeof(LINKLIST));
p->data = lb->data; p->next = NULL;
lc->next = p; lc = lc->next; lb = lb->next;
}
}
while(la != NULL)
{ p = (LINKLIST *) malloc(sizeof(LINKLIST));
p->data = la->data; p->next = NULL;
lc->next = p; lc = lc->next; la = la->next;
}
while(lb != NULL)
{ p = (LINKLIST *) malloc(sizeof(LINKLIST));
p->data = lb->data; p->next = NULL;
lc->next = p; lc = lc->next; lb = lb->next;
}
}
void delete1(LINKLIST *a){
/*无序链表中删除重复元素，重复元素保留一个*/
LINKLIST *la, *p, *q;
la = a->next;
while(la != NULL)
{ q = la; p = la->next;
while(p != NULL)
{if (p->data == la->data)
{ p = p->next; q->next = p;}
else { q = p; p = p->next;}
}
la = la->next;
}
}
void delete(LINKLIST *a){
/*有序链表中删除重复元素，重复元素保留一个*/
LINKLIST *la;
la = a->next;
while(la != NULL && la->next != NULL)
if (la->data == la->next->data)
la->next = la->next->next;
else la = la->next;
}
inser_order(DATATYPE2 x, LINKLIST *head){
/*有序表中插入元素x,并保持表有序*/
LINKLIST *pr, *pn, *pp;
pr = head; pn = head->next;
while(pn != NULL && pn->data < x)
{pr = pn;
pn = pn->next;}
pp = (LINKLIST *)malloc(sizeof(LINKLIST));
pp->data = x;
pp->next = pr->next;
pr->next = pp;
}
LINKLIST *invertlink(LINKLIST *head){
/*单链表元素逆置*/
LINKLIST *p, *q, *r;
q = NULL; p = head;
while(p != NULL)
{r = q; q = p ;
p = p->next;
q->next = r;}
return q;
}
int count_nohead(LINKLIST *head){
/*不带头结点的单链表：输出单链表元素值并计数*/
int i = 0;
LINKLIST *p;
p = head;
printf("输出单链表元素值 : ");
while(p != NULL)
{printf(" %c",p->data);
i++;
p = p->next;}
printf("\n");
return i;
}
int count_head(LINKLIST *head){
/*带头结点的单链表：输出单链表元素值并计数*/
int i = 0;
LINKLIST *p;
p = head->next;
printf("输出单链表元素值 : ");
while(p != NULL)
{printf(" %c",p->data);
i++;
p = p->next;}
printf("\n");
return i;
}
LINKLIST *creatlink_nohead_head(LINKLIST *head) {
/*用头插入法建立不带头结点的单链表*/
LINKLIST *t;
char ch;
printf("单链表元素值为单个字符, 连续输入，$为结束字符 : ");
while((ch = getchar())!= '$')
{ t = (LINKLIST *) malloc(sizeof(LINKLIST));
t->data = ch;
t->next = head;
head = t;}
return(head);
}
LINKLIST *creatlink_head_head(LINKLIST *head) {
/*用头插入法建立带头结点的单链表*/
LINKLIST *t;
char ch;
t = (LINKLIST *)malloc(sizeof(LINKLIST));
head = t;
t->next = NULL;
printf("单链表元素值为单个字符, 连续输入，$为结束字符 : ");
while((ch = getchar())!= '$')
{t = (LINKLIST *) malloc(sizeof(LINKLIST));
t->data = ch;
t->next = head->next;
head->next = t;}
return(head);
}
LINKLIST *creatlink_nohead_rail(LINKLIST *head){
/*用尾插入法建立不带头结点的单链表*/
LINKLIST *last, *t;
char ch;
last = head;
printf("单链表元素值为单个字符, 连续输入，$为结束字符 : ");
while ((ch = getchar()) != '$')
{t = (LINKLIST *)malloc(sizeof(LINKLIST));
t->data = ch;
t->next = NULL;
if (head == NULL) {head = t; last = t;}
else { last->next = t; last = t;}
}
return (head);
}
LINKLIST *creatlink_head_rail(LINKLIST *head){
/*用尾插入法建立带头结点的单链表*/
LINKLIST *last, *t;
char ch;
t = (LINKLIST *)malloc(sizeof(LINKLIST));
head = t; last = t;
t->next = NULL;
printf("单链表元素值为单个字符, 连续输入，$为结束字符 : ");
while ((ch = getchar()) != '$')
{t = (LINKLIST *)malloc(sizeof(LINKLIST));
t->data = ch;
t->next = NULL;
last->next = t;
last = t;}
return (head);
}
LINKLIST *creatlink_order_head(LINKLIST *head)
/*建立带头结点的有序单链表*/
{ LINKLIST *t, *p, *q;
char ch;
t = (LINKLIST *)malloc(sizeof(LINKLIST));
head = t; t->next = NULL;
printf("单链表元素值为单个字符, 连续输入，$为结束字符 : ");
while ((ch = getchar()) != '$')
{t = (LINKLIST *)malloc(sizeof(LINKLIST));
t->data = ch;
q = head; p = head->next;
while( p != NULL && p->data <= ch) {
q = p; p = p->next;}
q->next = t; t->next = p;
}
return(head);
}
main()
{ LINKLIST *head, *a1, *a2, *c;
int num = 0,loop,j;
char ch;
loop = 1;
while (loop) {
printf("\n\n");
printf(" 1 -- 建立单链表（头插入，不带头结点）\n");
printf(" 2 -- 建立单链表（头插入，带头结点）\n");
printf(" 3 -- 建立单链表（尾插入，不带头结点）\n");
printf(" 4 -- 建立单链表（尾插入，带头结点）\n");
printf(" 5 -- 逆置单链表\n");
printf(" 6 -- 有序链表插入\n");
printf(" 7 -- 有序链表删除重复元素\n");
printf(" 8 -- 无序链表删除重复元素\n");
printf(" 9 -- 两链表合并并排序\n");
printf(" 10 -- 两链表并集\n\n");
printf(" 请选择项号 ： ");
scanf("%d",&j);
fflush(stdin);
printf("\n\n");
if(j >= 1 && j <= 10)
switch(j) {
case 1: printf("\n 建立单链表\n\n");
head = NULL;
head = creatlink_nohead_head(head);
fflush(stdin);
num = count_nohead(head);
printf("单链表元素个数 = %d\n", num);
break;
case 2: printf("\n 建立单链表\n\n");
head = NULL;
head = creatlink_head_head(head);
fflush(stdin);
num = count_head(head);
printf("单链表元素个数 = %d\n", num);
break;
case 3: printf("\n 建立单链表\n\n");
head = NULL;
head = creatlink_nohead_rail(head);
fflush(stdin);
num = count_nohead(head);
printf("单链表元素个数 = %d\n", num);
break;
case 4: printf("\n 建立单链表\n\n");
head = NULL;
head = creatlink_head_rail(head);
fflush(stdin);
num = count_head(head);
printf("单链表元素个数 = %d\n", num);
break;
case 5: printf("\n 建立单链表\n\n");
head = NULL;
head = creatlink_nohead_head(head);
fflush(stdin);
num = count_nohead(head);
printf("单链表元素个数 = %d\n", num);
printf("\n 逆置单链表\n\n");
head = invertlink(head);
num = count_nohead(head);
break;
case 6: printf("\n 建立单链表\n\n");
head = NULL;
head = creatlink_order_head(head);
fflush(stdin);
num = count_head(head);
printf("单链表元素个数 = %d\n", num);
printf("\n输入插入元素值 : ");
ch = getchar();
inser_order(ch, head);
printf("\n 元素插入后\n\n");
num = count_head(head);
printf("插入后单链表元素个数 = %d\n", num);
break;
case 7: printf("\n 建立单链表\n\n");
head = NULL;
head = creatlink_order_head(head);
fflush(stdin);
num = count_head(head);
printf("\n 删除重复元素后\n\n");
delete(head);
num = count_head(head);
break;
case 8: printf("\n 建立单链表\n\n");
head = NULL;
head = creatlink_head_rail(head);
fflush(stdin);
num = count_head(head);
printf("\n 删除重复元素后\n\n");
delete1(head);
num = count_head(head);
break;
case 9: printf("\n 建立单链表a1\n\n");
a1 = NULL;
a1 = creatlink_order_head(a1);
fflush(stdin);
num = count_head(a1);
printf("单链表a1元素个数 = %d\n", num);
printf("\n 建立单链表a2\n\n");
a2 = NULL;
a2 = creatlink_order_head(a2);
fflush(stdin);
num = count_head(a2);
printf("单链表a2元素个数 = %d\n", num);
c = NULL;
c = (LINKLIST *)malloc(sizeof(LINKLIST));
c->next = NULL;
unite(a1, a2, c);
num = count_head(c);
printf("合并到单链表c中，元素个数 = %d\n", num);
break;
case 10:printf("\n 建立单链表a1 \n\n");
a1 = NULL;
a1 = creatlink_head_rail(a1);
fflush(stdin);
num = count_head(a1);
printf("\n 建立单链表a2 \n\n");
a2 = NULL;
a2 = creatlink_head_rail(a2);
fflush(stdin);
num = count_head(a2);
printf("\n\n 两链表交集运算,结果保留在a1中\n\n");
unionn(a1,a2);
num = count_head(a1);
}
printf("结束此练习吗? (0 -- 结束 1 -- 继续) : ");
scanf("%d",&loop);
printf("\n");
}
}
实验二 二叉树的创建与访问算法的设计
一、目的
本实验的目的是通过理解二叉树的逻辑结构和存储结构，进一步提高使用理论知识指导解决实际问题的能力。
二、题目
二叉树的创建与访问算法的设计
三、实验类型
设计性。本实验设计了二叉树的创建与访问算法。
四、要求及提示
说明：以下4个题中，任意选作一题。
1、【问题描述】
从键盘输入二叉树的元素，建立二叉树，实现二叉树的遍历算法。
【基本要求】
实现以下基本操作：
（1） 从键盘输入二叉树的元素，建立二叉树。
（2） 实现二叉树的先序遍历算法。
2、【问题描述】
从键盘输入二叉树的元素，建立二叉树，实现二叉树的遍历算法。
【基本要求】
实现以下基本操作：
（1） 从键盘输入二叉树的元素，建立二叉树。
（2） 实现二叉树的中序遍历算法。
3、【问题描述】
从键盘输入二叉树的元素，建立二叉树，实现二叉树的遍历算法。
【基本要求】
实现以下基本操作：
（1） 从键盘输入二叉树的元素，建立二叉树。
（2） 实现二叉树的后序遍历算法。
4、【问题描述】
采用某种遍历方法查找二叉树中的结点值为x（x为从键盘输入的一个值）的结点，如果找到则返回其双亲结点值；否则返回值0
【基本要求】
实现以下基本操作：
（1） 从键盘输入二叉树的元素，建立二叉树。
（2） 实现查找算法，并输出双亲结点值。
五、实验报告
1、写出每个算法的思想。
2、画出算法流程图。
3、调试程序出现的问题及解决的方法。
4、打印实验报告及程序清单。
5、报告给出测试的结果并写出设计体会。
六、范例参考
1、 问题描述（两种方法建立二叉树）
1) 二叉树的建立：设有一棵二叉树如图（a），将二叉树模拟为完全二叉树从根开始对结点进行编号，编号从1 开始，结果如图(b)所示。在运行过程中要求输入结点对应的编号和值时，请按图（c）中的数据输入，最后以编号 I=0；结点值x=’$’结束。
2) 二叉树中序遍历:对建立的二叉树进行中序遍历,并输出遍历结果.中序遍历算法可以用递归算法实现,也可以用非递归算法实现.
2、程序清单
#include <stdio.h>
#include "datastru.h"
#include <malloc.h>
typedef struct node1
{char data;
struct node1 *lchild,*rchild;
}BTCHINALR;
BTCHINALR * createbt( )
{ BTCHINALR *q;
struct node1 *s[30];
int j,i,x;
printf("建立二叉树，输入结点对应的编号和值,编号和值之间用逗号隔开\n\n");
printf("i,x = ");
scanf("%d,%c",&i,&x);
while(i != 0 && x != '$')
{q = (BTCHINALR*)malloc(sizeof(BTCHINALR)); /*建立一个新结点q*/
q->data = x; q->lchild = NULL; q->rchild = NULL;
s[i] = q; /*q新结点地址存入s指针数组中*/
if(i != 1) /*i = 1，对应的结点是根结点*/
{j = i / 2; /*求双亲结点的编号j*/
if(i % 2 == 0) s[j]->lchild = q; /*q结点编号为偶数则挂在双亲结点j的左边*/
else s[j]->rchild = q;} /*q结点编号为奇数则挂在双亲结点j的右边*/
printf("i,x = ");
scanf("%d,%c",&i,&x);}
return s[1]; /*返回根结点地址*/
}
void inorder(BTCHINALR *bt)
/*中序遍历二叉树(递归算法)*/
{if(bt != NULL)
{ inorder(bt->lchild);
printf("%c ",bt->data);
inorder(bt->rchild); }
}
void inorder_notrecursive(BTCHINALR *bt)
/*中序遍历二叉树(非递归算法)*/
{BTCHINALR *q, *s[20];
int top = 0;
int bool = 1;
q = bt;
do {while(q != NULL)
{ top ++; s[top] = q; q = q->lchild; }
if(top == 0) bool = 0;
else { q = s[top];
top --;
printf("%c ",q->data);
q = q->rchild; }
}while(bool);
}
main( )
{ BTCHINALR *bt;
char ch;
int i;
bt = createbt(); i = 1;
while(i) {
printf("\n中序遍历二叉树(递归按y键，非递归按n键): ");
fflush(stdin);
scanf("%c",&ch);
if(ch == 'y') inorder(bt); else inorder_notrecursive(bt);
printf("\n");
printf("\n继续操作吗?(继续按1键，结束按0键): ");
fflush(stdin);
scanf("%d",&i);
}
}
方法二：按先序遍历序列建立二叉树的二叉链表，已知先序序列为：
A B C φ φ D E φ G φ φ F φ φ φ
#define datatype char
typedef struct node
{datatype data;
struct node *lchild,*rchild;
}JD;
JD *crt_bt_pre(JD *bt)
{ char ch;
printf("ch=");
scanf("%c",&ch);
if(ch==' ') bt=NULL;
else
{ bt=(JD *)malloc(sizeof(JD));
bt->data=ch;
bt->lchild=crt_bt_pre(bt->lchild);
bt->rchild=crt_bt_pre(bt->rchild);
}
return(bt);
}
实验三 图的创建与访问算法的设计
一、目的
本实验的目的是通过理解图的逻辑结构和存储结构，进一步提高使用理论知识指导解决实际问题的能力。
二、题目
图的创建与访问算法的设计
三、实验类型
设计性。本实验设计了图的创建与访问算法。
四、要求及提示
说明：以下4个题中，任意选作一题。
1、【问题描述】
设有六个比赛项目，规定每个选手至多可参加三个项目，有五人报名参加比赛（如下表所示）设计比赛日程表，使得在尽可能短的时间内完成比赛。
【基本要求】
实现以下基本操作：
（1） 建立图。
（2） 输出比赛日程表。
（3） 对所建的图进行深度优先遍历，输出深度优先遍历序列。
（4）
2、【问题描述】
设有六个比赛项目，规定每个选手至多可参加四个项目，有五人报名参加比赛（如下表所示）设计比赛日程表，使得在尽可能短的时间内完成比赛。
【基本要求】
实现以下基本操作：
（1） 建立图。
（2） 输出比赛日程表。
（3） 对所建的图进行深度优先遍历，输出广度优先遍历序列。
（4）
3、【问题描述】
大学的每个专业都要制定教学计划，课程在开设时间的安排必须满足先修关系。某专业的课程先修关系如下表所示，按此表编制出教学计划。
【基本要求】
实现以下基本操作：
按上表课程的先修关系建立图，并编制出教学计划。
4、【问题描述】
从文件输入图的元素，建立一个无向连通图，并访问图上全部结点。
【基本要求】
实现以下基本操作：
（1） 从文件输入图的元素，建立无向连通图。
（2） 以图的某种遍历方法（深度优先遍历或广度优先遍历）访问图中的全部结点。
五、实验报告
1、写出每个算法的思想。
2、画出算法流程图。
3、调试程序出现的问题及解决的方法。
4、打印实验报告及程序清单。
5、报告给出测试的结果并写出设计体会。
六、范例参考
1、问题描述
1) 建立连通图邻接链表结构：建立过程依赖于图中顶点和边的编号。顶点和边的编号可以预先规定，编法不同，则数据输入的过程和输出的结果也会不同，但广度优先遍历算法的结果都是正确的。
2) 实现广度优先遍历：在以邻接连表为存储结构的无向图上，实现无向图广度优先遍历算法。
3) 实现深度优先遍历：在以邻接连表为存储结构的无向图上，实现无向图深度优先遍历算法。
连通图如图所示：
顶点值设定为：
v1=100,v2=200,v3=300,v4=400,v5=500,v6=600,v7=700,v8=800
2、程序清单
广度优先遍历程序清单：
#include "datastru.h"
#include <stdio.h>
#include <malloc.h>
#define VEXTYPE int
3define MAXLEN 40
typedef struct node3 /*表结点结构*/
{int adjvex; /*存放与表头结点相邻接的顶点在数组中的序号*/
struct node3 *next; /*指向与表头结点相邻接的下一个顶点的表结点*/
}EDGENODE;
typedef struct
{VEXTYPE vertex; /*存放图中顶点的信息*/
EDGENODE *link; /*指针指向对应的单链表中的表结点*/
}VEXNODE;
typedef struct
{VEXNODE adjlist[MAXLEN]; /*邻接链表表头向量*/
int vexnum,arcnum; /*顶点数和边数*/
int kind; /*图的类型*/
}ADJGRAPH;
typedef struct qnode
{int data;
struct qnode *next;
}LINKQLIST;
typedef struct
{ LINKQLIST front;
LINKQLIST rear;
}LINKQUEUE;
ADJGRAPH creat_adjgraph(){
EDGENODE *p;
int i, s, d;
ADJGRAPH adjg;
adjg.kind = 2;
printf("\n\n输入顶点数和边数(用逗号隔开) : ");
scanf("%d,%d", &s, &d);fflush(stdin);
adjg.vexnum = s; /*存放顶点数在adjg.vexnum中 */
adjg.arcnum = d; /*存放边点数在adjg.arcnum中*/
printf("\n\n");
for(i = 0; i < adjg.vexnum; i++)
{printf("输入顶点 %d 的值 : ", i + 1);
scanf("%d", &adjg.adjlist[i].vertex); /*输入顶点的值*/
fflush(stdin);
adjg.adjlist[i].link = NULL;}
printf("\n\n");
for(i = 0; i < adjg.arcnum; i++)
{printf("输入第 %d 条边的起始顶点和终止顶点(用逗号隔开): ", i + 1);
scanf("%d,%d", &s, &d); /*输入边的起始顶点和终止顶点*/
fflush(stdin);
while(s < 1 || s > adjg.vexnum || d < 1 || d > adjg.vexnum)
{ printf("输入错，重新输入: ");
scanf("%d,%d", &s, &d); }
s --;
d --;
p = malloc(sizeof(EDGENODE)); /*建立一个和边相关的结点*/
p->adjvex = d;
p->next = adjg.adjlist[s].link; /*挂到对应的单链表上*/
adjg.adjlist[s].link = p;
p = malloc(sizeof(EDGENODE)); /*建立另一个和边相关的结点*/
p->adjvex = s;
p->next = adjg.adjlist[d].link; /*挂到对应的单链表上*/
adjg.adjlist[d].link = p;}
return adjg;
}
void initlinkqueue(LINKQUEUE *q)
{/*初始化广度遍历中用到的链队列*/
q->front = malloc(sizeof(LINKQLIST));
(q->front)->next = NULL;
q->rear = q->front;
}
int emptylinkqueue(LINKQUEUE *q)
{/*判队列是否为空？*/
int v;
if(q->front == q->rear)
v = 1;
else
v = 0;
return v;
}
void enlinkqueue(LINKQUEUE *q, DATATYPE1 x)
{/*元素x入队列*/
(q->rear)->next = malloc(sizeof(LINKQLIST));
q->rear = (q->rear)->next;
(q->rear)->data = x;
(q->rear)->next = NULL;
}
DATATYPE1 dellinkqueue(LINKQUEUE *q)
{/*删除队头元素*/
LINKQLIST *p;
DATATYPE1 v;
if(emptylinkqueue(q)) {printf("队列空.\n"); v = 0;}
else
{p = (q->front)->next;
(q->front)->next = p->next;
if(p->next == NULL) q->rear = q->front;
v = p->data;
free(p);}
return v;
}
void bfs(ADJGRAPH adjg, int vi)
{/*连通图的广度遍历算法：从vi顶点出发*/
int visited[MAXLEN];
int i, v;
EDGENODE *p;
LINKQUEUE que, *q;
q = &que;
initlinkqueue(q);
for(i = 0; i < adjg.vexnum; i++)
visited[i] = 0; /*visited数组初始化，均置0*/
visited[vi-1] = 1; /*从编号为vi的顶点出发，visited数组对应置1*/
printf(" %d", adjg.adjlist[vi-1].vertex); /*输出vi顶点*/
enlinkqueue(q,vi); /*vi顶点入队列*/
while(!emptylinkqueue(q)) /*队列不空，继续进行遍历*/
{v = dellinkqueue(q); /*取队头元素放入v变量中*/
v --;
p = adjg.adjlist[v].link;
while(p != NULL) /*对应单链表不空，进行广度遍历*/
{if(visited[p->adjvex] == 0)
{visited[p->adjvex] = 1;
printf(" %d", adjg.adjlist[p->adjvex].vertex);
enlinkqueue(q, (p->adjvex)+1);} /*遍历到的结点编号入队列*/
p = p->next;}
}
}
main()
{
ADJGRAPH ag;
int j;
printf("\n连通图的广度遍历\n");
ag = creat_adjgraph(); /*建立连通图的邻接链表结构*/
printf("\n\n输入广度遍历起始顶点(1 -- %d) : ",ag.vexnum);
scanf("%d",&j);
printf("\n\n广度遍历结果序列 : ");
bfs(ag,j); /*连通图的广度遍历算法*/
printf("\n\n");
}
深度优先遍历程序清单：
#include <stdio.h>
#include "datastru.h"
#include <malloc.h>
int visited[MAXLEN];
ADJGRAPH creat_adjgraph()
{
EDGENODE *p;
int i, s, d;
ADJGRAPH adjg;
adjg.kind = 2;
printf("\n\n输入顶点数和边数(用逗号隔开) : ");
scanf("%d,%d", &s, &d);fflush(stdin);
adjg.vexnum = s; /*存放顶点数在adjg.vexnum中 */
adjg.arcnum = d; /*存放边点数在adjg.arcnum中*/
printf("\n\n");
for(i = 0; i < adjg.vexnum; i++) /*输入顶点的值*/
{printf("输入顶点 %d 的值 : ", i + 1);
scanf("%d", &adjg.adjlist[i].vertex);
fflush(stdin);
adjg.adjlist[i].link = NULL;}
printf("\n");
for(i = 0; i < adjg.arcnum; i++)
{printf("输入第 %d 条边的起始顶点和终止顶点(用逗号隔开): ", i+1);
scanf("%d,%d", &s, &d); /*输入边的起始顶点和终止顶点*/
fflush(stdin);
while(s < 1 || s > adjg.vexnum || d < 1 || d > adjg.vexnum)
{ printf("输入错，重新输入: ");
scanf("%d,%d", &s, &d); }
s --;
d --;
p = malloc(sizeof(EDGENODE)); /*建立一个和边相关的结点*/
p->adjvex = d;
p->next = adjg.adjlist[s].link; /*挂到对应的单链表上*/
adjg.adjlist[s].link = p;
p = malloc(sizeof(EDGENODE)); /*建立另一个和边相关的结点*/
p->adjvex = s;
p->next = adjg.adjlist[d].link; /*挂到对应的单链表上*/
adjg.adjlist[d].link = p;}
return adjg;
}
void dfs(ADJGRAPH adjg, int v){
/*连通图的深度遍历算法：从v顶点出发*/
EDGENODE *p;
visited[v - 1] = 1; /*从编号为v的顶点出发，visited数组对应置1*/
v --;
printf(" %d", adjg.adjlist[v].vertex); /*输出v顶点*/
p = adjg.adjlist[v].link; /*取单链表的第一个结点*/
while(p != NULL) /*对应单链表不空，进行遍历*/
{ if(visited[p->adjvex] == 0) /*如果有未被访问过的结点*/
dfs(adjg, (p->adjvex)+1); /*递归调用深度遍历算法*/
p = p->next;} /*取单链表的下一个结点*/
}
main()
{
ADJGRAPH ag;
int i;
printf("\n连通图的深度遍历\n");
ag = creat_adjgraph(); /*建立连通图的邻接链表结构*/
for(i = 0; i < ag.vexnum; i++) /*visited数组初始化，均置0*/
visited[i] = 0;
printf("\n\n输入深度遍历起始顶点(1 -- %d) : ",ag.vexnum);
scanf("%d",&i);
printf("\n\n深度遍结果序列 : ");
dfs(ag,i); /*连通图的深度遍历算法*/
printf("\n\n");
}