数据结构实验指导书(2009).doc

数据结构与算法实验指导书马晓波 秦俊平 刘利民 编内蒙古工业大学信息工程学院计算机系2009年3月1日数据结构与算法实验教学大纲 一、基本信息课程编码020213040课程学时64课程类别学科基础课实验总学时12开出学期第四学期开出单位信息学院计算机系适用专业 计算机科学与技术、软件工程二、实验安排序号实 验 项 目实验学时每组人数实验类型开出要求1线性表的创建与访问算法设计41设计已开出二叉树的创建与访问算法设计41设计已开出图的创建与访问算法设计41设计已开出三、实验目的、内容与要求实验一 线性表的创建与访问算法设计(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语言版）. 北京：清华大学出版社，19972 李春葆编. 数据结构习题与解析. 北京：清华大学出版社，2002 3 刘振鹏主编. 数据结构. 北京：中国铁道出版社，2003 4 许卓群编数据结构北京：中央电大出版社， 20015 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 datasMAXSIZE; int last;SEQUENLIST;typedef struct nodeDATATYPE2 data;struct node *next;LINKLIST;typedef struct dnodeDATATYPE2 data;struct dnode *prior, *next; DLINKLIST;typedef struct DATATYPE1 dataMAXSIZE; int top;SEQSTACK;typedef struct snode DATATYPE2 data; struct snode *next; LINKSTACK; typedef struct DATATYPE1 dataMAXSIZE; int front, rear; SEQQUEUE;typedef struct qnode DATATYPE1 data; struct qnode *next; LINKQLIST;typedef struct LINKQLIST *front, *rear;LINKQUEUE;typedef struct char chMAXSIZE; 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 dataMAXLEN;SPMATRIX;typedef struct DATATYPE2 btMAXSIZE; 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 nodesMAXSIZE; int nodenum;PTTREE;typedef struct cnode int child;struct cnode *next;CHILDLINK;typedef struct DATATYPE2 data; CHILDLINK *headptr;CTNODE;typedef structCTNODE nodesMAXSIZE; int nodenum, rootset;CTTREE;typedef struct csnode DATATYPE2 data; struct csnode *firstchild, *nextsibling;CSNODE;typedef struct VEXTYPE vexsMAXLEN; ADJTYPE arcsMAXLENMAXLEN; 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 adjlistMAXLEN; int vexnum, arcnum; int kind; ADJGRAPH;typedef struct KEYTYPE key;SSELEMENT;typedef struct SSELEMENT rMAXSIZE; int len;SSTABLE;typedef struct node4KEYTYPE 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 #include #define DATATYPE2 chartypedef struct nodeDATATYPE2 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 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 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 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(nn);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 - 两链表并集nn);printf( 请选择项号 ： );scanf(%d,&j);fflush(stdin);printf(nn);if(j = 1 & j next = NULL;unite(a1, a2, c);num = count_head(c);printf(合并到单链表c中，元素个数 = %dn, num);break;case 10:printf(n 建立单链表a1 nn);a1 = NULL;a1 = creatlink_head_rail(a1);fflush(stdin);num = count_head(a1);printf(n 建立单链表a2 nn);a2 = NULL;a2 = creatlink_head_rail(a2);fflush(stdin);num = count_head(a2);printf(nn 两链表交集运算,结果保留在a1中nn);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 #include datastru.h#include typedef struct node1char data;struct node1 *lchild,*rchild;BTCHINALR;BTCHINALR * createbt( )BTCHINALR *q;struct node1 *s30;int j,i,x;printf(建立二叉树，输入结点对应的编号和值,编号和值之间用逗号隔开nn);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; si = q; /*q新结点地址存入s指针数组中*/ if(i != 1) /*i = 1，对应的结点是根结点*/ j = i / 2; /*求双亲结点的编号j*/ if(i % 2 = 0) sj-lchild = q; /*q结点编号为偶数则挂在双亲结点j的左边*/ else sj-rchild = q; /*q结点编号为奇数则挂在双亲结点j的右边*/ printf(i,x = ); scanf(%d,%c,&i,&x);return s1; /*返回根结点地址*/void inorder(BTCHINALR *bt)/*中序遍历二叉树(递归算法)*/if(bt != NULL)inorder(bt-lchild);printf(%c ,bt-data);inorder(bt-rchild);void inorder_notrecursive(BTCHINALR *bt)/*中序遍历二叉树(非递归算法)*/BTCHINALR *q, *s20; int top = 0; int bool = 1; q = bt; do while(q != NULL) top +; stop = q; q = q-lchild; if(top = 0) bool = 0; else q = stop; 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 chartypedef struct nodedatatype 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);实验三 图的创建与访问算法的设计一、目的本实验的目的是通过理解图的逻辑结构和存储结构，进一步提高使用理论知识指导解决实际问