《数据结构与算法》实验指导书马晓波秦俊平刘利民编内蒙古工业大学信息工程学院计算机系2008年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语言版）. 北京：清华大学出版社，19972、教学参考书[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 inttypedef struct{ DATATYPE1 datas[MAXSIZE]; int last;}SEQUENLIST;typedef struct node{DA TA TYPE2 data;struct node *next;}LINKLIST;typedef struct dnode{DATA TYPE2 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{ DATA TYPE1 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];}SPMA TRIX;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 chartypedef 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");}}实验二二叉树的创建与访问算法的设计一、目的本实验的目的是通过理解二叉树的逻辑结构和存储结构，进一步提高使用理论知识指导解决实际问题的能力。