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

软件学院课程实验指导书课程名称 数据结构 任课教师 王珊珊 开课学期 2015年秋季学期 辽宁工程技术大学软件学院软件工程系目 录实验一 顺序表的基本操作的实现1实验二 单链表的基本操作的实现8实验三 栈的应用15实验四 队列的应用18实验五 矩阵22实验六 二叉树的实现24实验七 图的实现及应用27实验八 排序36实验九 综合应用40数据结构实验指导书实验一 顺序表的基本操作的实现一、实验属性 实验性质： 验证性 实验学时： 2学时实验要求： 必做二、实验目的1掌握线性表顺序存储结构的特点。2掌握线性表顺序存储结构的基本操作(创建、插入、删除)的实现。3. 通过顺序表有序表的合并的实现，掌握顺序表操作特点。三、实验环境及知识准备 1.实验环境： C与C+程序设计学习与实验系统 2.知识准备：(1) 线性表的顺序存储结构； (2) 顺序表初始化、插入、删除算法。(3)两个有序表合并算法。四、实验内容 1. 完成线性表的顺序存储及基本操作的实现（顺序表初始化、插入、删除功能）；2. 实现两个有序表的合并功能。五、实验要求及步骤1. 定义顺序表的存储结构SqList。2. 完成顺序表的初始化，插入，删除等基本操作函数。 InitList_Sq(SqList &L); InsertList_Sq(SqList &L,int i，Elemtype e )； DeleteList_Sq(SqList &L，int i， Elemtype &e )；3. 实现两个有序表合并函数。 MergeList(SqList La, SqList Lb, SqList &Lc,) 4. 在主函数中调用以上算法，完成如下功能： 建立一个空表L，输入一组元素序列； 输入插入位置及元素值，完成L表插入操作，并输出插入后顺序表； 输入删除元素位序，完成L表删除操作，输出删除元素值及删除后顺序表； 建立顺序表La，Lb，并输入元素。调用合并算法，将La，Lb合并成Lc，输出合并后Lc。六、实验指导 1. 顺序表的存储结构定义如下： typedef int ElemType；/元素类型 typedef struct ElemType *elem; int length; /表的实际长度 int listsize; /顺序表容量 SqList;/顺序表的类型名2. 给出部分程序模块如下，可在此基础上实现其余功能：/*-预定义部分-*/#include stdio.h#include malloc.h#define OK 1#define OVERFLOW -1#define ERROR 0#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef int ElemType;typedef int Status;/*-顺序表的存储结构定义-*/typedef structElemType *elem;int length;int listsize;sqlist;/*-初始化顺序表L-*/Status InitList_sq(sqlist *L)L-elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType);if(!L-elem) exit(OVERFLOW);L-length=0;L-listsize=LIST_INIT_SIZE;return OK;/*-顺序表L插入-*/Status ListInsert_Sq(sqlist *L,int i,ElemType e)ElemType *newbase,*p,*q;if(iL-length+1) return ERROR;if(L-length=L-listsize)newbase=(ElemType*)realloc(L-elem,(L-listsize+LISTINCREMENT)*sizeof(ElemType);if(!newbase) exit(OVERFLOW);L-elem=newbase;L-listsize=L-listsize+LISTINCREMENT;q=&(L-elemi-1);for(p=&(L-elemL-length-1);p=q;-p) *(p+1)=*p;*q=e;+L-length;return OK;/*-顺序表L删除-*/Status ListDelete_Sq(sqlist *L,int i,ElemType *e)ElemType *p,*q;if(iL-length) return ERROR;p=&(L-elemi-1);*e=*p;q=L-elem+L-length-1;/*printf(%d,%d,%d,%d,p,L-elem,L-length,q);*/for(+p;plength;return OK;/*-main函数-*/main()sqlist La;int i;int n=5;ElemType e;/*-INIT-*/if(InitList_sq(&La) printf(Inite is ok!n); printf(Length: %dn,La.length); printf(Listsize: %dnn,La.listsize); elseprintf(error!);/*-顺序表La输入初始值-*/printf(Please input the values of sq:n);for(i=1;i=n;i+) scanf(%d,&e) ; if(ListInsert_Sq(&La,i,e)!=OK) break; for(i=1;i=La.length;i+) printf(e%d=%dn,i-1,La.elemi-1);printf(Length: %dnn,La.length);/*-INSERT-*/printf(Please input the place of insert:n);scanf(%d,&i);printf(Please input the elemvalue:n);scanf(%d,&e);if(ListInsert_Sq(&La,i,e)=OK) for(i=1;i=La.length;i+) printf(e%d=%dn,i-1,La.elemi-1); printf(Length: %dnn,La.length); /*-DELETE-*/printf(Please input the place of delete:n);scanf(%d,&i);if(ListDelete_Sq(&La,i,&e)=OK) printf(The deleted elem is: %dn,e); for(i=1;i=La.length;i+) printf(e%d=%dn,i-1,La.elemi-1); printf(Length: %dn,La.length); getch();3. 需完成内容框架：#include stdio.h#include malloc.h#define OK 1#define OVERFLOW -1#define ERROR 0#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef int ElemType;typedef int Status;typedef structElemType *elem;int length;int listsize;sqlist;Status InitList_sq(sqlist *L);Status ListInsert_Sq(sqlist *L,int i,ElemType e);Status ListDelete_Sq(sqlist *L,int i,ElemType *e);Void Merglist_sq(sqlist La,sqlist Lb,sqlist *Lc)/合并操作,La,Lb是sqlist类型变量，Lc是sqlist类型指针 ElemTye *pa，*pb，*pc，*pa_last,*pb_last;main()sqlist La,Lb,Lc;int i;int n=5;ElemType e;/*-MergList-*/ InitList_sq(&La);/初始化La，Lb InitList_sq(&Lb); for(i=1;i=8;i+)/la,lb初值； scanf(%d,&e) ; if(ListInsert_Sq(&La,i,e)!=OK) break; for(i=1;i=11;i+) scanf(%d,&e) ; if(ListInsert_Sq(&Lb,i,e)!=OK) break; /La，Lb输出 for(i=1;i=La.length;i+) printf(La%d=%dn,i-1,La.elemi-1); for(i=1;i=Lb.length;i+) printf(Lb%d=%dn,i-1,Lb.elemi-1); Merglist_sq(La,Lb,&Lc); /合并Lc，并输出 for(i=1;inext=NULL;for(i=n;i0;-i) p=(LinkList)malloc(sizeof(LNode); scanf(%d,&(p-data); p-next=(*L)-next; (*L)-next=p; /*-单链表元素输出-*/void Print(LinkList L)LinkList p;p=L-next;while(p)printf(%d,p-data);p=p-next;/*-主函数-*/main()LinkList L;/*-Creat-*/Creatlist_L(&L,5);printf(The values of Linklist:n);Print(L);getch();(3) 需完成内容框架如下：#include stdio.h#include malloc.h#define OK 1#define OVERFLOW -1#define ERROR 0typedef int ElemType;typedef int Status;typedef struct LNode ElemType data; struct LNode *next;LNode,*LinkList;void Creatlist_L(LinkList *L,int n)int i;LinkList p;*L=(LinkList)malloc(sizeof(LNode);(*L)-next=NULL;for(i=n;i0;-i) p=(LinkList)malloc(sizeof(LNode); scanf(%d,&(p-data); p-next=(*L)-next; (*L)-next=p; status ListInsert_L(LinkList *L,int i,ElemType e)status ListDelete_L(LinkList *L,int i,ElemType *e)status MergeList_L(LinkList *La,LinkList *Lb,LinkList *Lc)void Print(LinkList L)LinkList p;p=L-next;while(p)printf(%d ,p-data);p=p-next;main()LinkList L;LinkList la,lb,lc;int i;ElemType e;/*-Creat-*/Creatlist_L(&L,5);printf(The values of Linklist:n);Print(L);/-INSERT-i,eInsertList_L();printf(The values of Linklist:n);Print(L);/-DELETE-iDeleteList_L();printf(The values of Linklist:n);Print(L);/-MergeList-Createlist_L(&la,3);printf( The la:);Print(la);Createlist_L(&lb,5);printf( The lb:);Print(lb);MergeList_L(&la,&lb,&lc);printf( The lc:);Print(lc)getch();七、注意事项1.为了算法实现简单，最好采用带头结点的单向链表。(思考：不带头结点单链表基本操作如何实现。) 2.注意Lnode,Lnode *，LinkList等参数传递。3单向链表的操作是数据结构的基础，一定要注意对这部分的常见算法的理解。 4. 提高内容： Joseph环（提高内容可课后完成，不计入成绩。如完成根据完成情况加510分计入总成绩。）(1)设计任务编号是1，2，,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。(2)设计要求设计一个程序，以人机交互的方式执行，用户指定约瑟夫环游戏的总人数n和初始的报数上限m，然后输入每个人所持有的密码key。模拟约瑟夫环，从头开始报数，直到所有人出列。系统按照出列顺序给出编号及该人所持有的密码。（3）实现提示利用带头结点的循环链表作为模拟约瑟夫环的存储结构。先创建一个有头结点的单循环链表，依次输入n个人的密码。然后从第一个结点出发，连续略过m-1个结点，将第m个结点删除，并将第m个人的密码作为新的m值，接着从下一个结点出发，重复以上过程，直到链表为空为止。八、实验报告内容及要求1.实验的程序源码2.运行程序，给出运行结果截图3.分析实验结果，得出结论约瑟夫环：选择不带头结点的循环链表作为存储结构，从第一个结点开始计数，找到第m个结点，将该结点从链表中删除，并输出。从下一个结点开始继续从1计数，到m删除结点并输出直到只剩一个结点结束程序。-(2分)其存储结构定义为：typedef struct CircNodeint data;struct CircNode *next;CircNode,*CircList;-(2分)(2) void Jesephus(CircList &J,int n，int m) /不带头结点的循环链表J,模拟约瑟夫环游戏执行过程。 Circlist p=J,pre=Null; int i,j; for（i=1;in;i+） /执行n-1趟报数。 for（j=1;jnext;printf(“出列的人编号是：%d”,p-data);pre-next=p-next; /删除报数为m结点，进入下一趟报数delete p;p=pre-next; Printf（“最终胜出者是：”，p-data）; 实验三 栈的应用一、实验属性 实验性质： 设计性 实验学时： 2学时 实验要求： 必做二、实验目的 1掌握栈的结构及操作特点。2.实现栈的顺序存储结构及基本操作的实现。3利用栈的操作实现括号匹配的检验。三、实验环境及知识准备 1.实验环境： C与C+程序设计学习与实验系统 2.知识准备：(1) 栈的顺序存储结构； (2)栈的初始化、入栈、出栈，取栈顶，判断栈是否为空等算法的实现。(3)括号匹配算法的设计。四、实验内容 1 定义栈的存储结构，完成入栈、出栈、取栈顶、判断栈是否为空等基本操作的实现。2 利用栈完成括号匹配算法。五、实验要求及步骤1 定义栈的存储结构，完成入栈、出栈、取栈顶、判断栈是否为空等基本操作的实现。2 实现括号匹配算法的实现。3 主函数完成括号匹配算法的调用，实现对给定的括号序列进行匹配，给出匹配结果。六、实验指导1.顺序栈示例typedefstruct ElemType *base；ElemType * top；int stacksize； SqStack；2括号匹配算法思想（1）出现的凡是“左括号”，则进栈；（2）出现的是“右括号”，首先检查栈是否空？ 若栈空，则表明该“右括号”多余 否则和栈顶元素比较？ 若相匹配，则栈顶“左括号出栈” 否则表明不匹配（3）表达式检验结束时， 若栈空，则表明表达式中匹配正确 否则表明“左括号”有余3完成程序框架 #include stdio.h#include malloc.h#define OK 1#define OVERFLOW -1#define ERROR 0#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef char ElemType;typedef int Status;typedefstruct ElemType *base；ElemType * top；int stacksize； SqStack;Status InitStack_Sq(SqStack *s);Status EmpyStack(SqStack s);Status Push(SqStack* s,ElemType e);Status Pop(SqStack *s,ElemType *e);void brackets(char *ch);main()char ch50;/scanft(“%s”,&ch); gets(ch);brackets(&ch);七、注意事项 1重点理解栈的算法思想，能够根据实际情况选择合适的存储结构。 2栈和队列的算法是后续实验的基础（广义表、树、图、查找、排序等）。 八、实验报告内容及要求1.实验的程序源码2.运行程序，给出运行结果截图3.分析实验结果，得出结论Status Brackets_Test(char *str) /判别表达式中三种括号是否匹配 InitStack(s); for(p=str; *p; p+) if(*p=(|*p=|*p=) push(s,*p); else if(*p=)|*p=|*p=) if(StackEmpty(s) return ERROR; pop(s,c); if(*p=)&c!=() return ERROR; if(*p=&c!=) return ERROR; if(*p=&c!=) return ERROR; /必须与当前栈顶括号匹配 if(!StackEmpty(s) return ERROR; return OK; 实验四 队列的应用一、实验属性 实验性质： 设计性 实验学时： 2学时 实验要求： 必做二、实验目的 1掌握栈队列特点及顺序存储结构(循环队列)下基本操作的实现。2掌握队列的应用，能根据问题特点选择队列结构。三、实验环境及知识准备 1.实验环境： C与C+程序设计学习与实验系统 2.知识准备：(1) 循环队列的存储结构； (2)队列的的初始化、入队、出队、取队头等基本操作实现算法。(3)杨辉三角理论及方法。四、实验内容 1 定义循环队列的存储结构，完成入队、出队、取队头等基本操作的实现。2 利用循环队列实现杨辉三角的输出。五、实验要求及步骤1 定义循环队列的存储结构2 完成入队、出队、取队头等基本操作的实现。3 利用队列的基本操作实现n行杨辉三角的输出。4 主函数调用杨辉三角输出函数，实现n行杨辉三角输出。六、实验指导1./-循环队列队列的顺序存储结构 - #define MAXSIZE 100typedef struct QElemType *base; /初始化的动态分配存储空间 int front; /头指针，队列不空指向队列头元素 int rear; /尾指针，队列不空指向队列尾元素下一位置 SqQueue;2.杨辉三角: 11 1 121133114641这是一个初等数学中讨论的问题。系数表中的第 k行有 k个数，除了第一个和最后一个数为1之外，其余的数则为上一行中位其左、右的两数之和。如果要求计算并输出杨辉三角前n行的值，则队列的最大空间应为 n+2。假设队列中已存有第 k 行的计算结果，并为了计算方便，在两行之间添加一个0作为行界值，则在计算第 k+1 行之前，头指针正指向第 k 行的0，而尾元素为第 k+1 行的0。由此从左到右依次输出第 k 行的值，并将计算所得的第 k+1 行的值插入队列的基本操作为： void YangHui(int n) printf(1n); EnQueue(&q,0); /*开始*/ EnQueue(&q,1); /*第1行*/ EnQueue(&q,1); for(j=2;j=n;j+) EnQueue(&q,0); do DeQueue(&q,&s); GetHead(&q,&t); if(t) printf(%dt,t); /*非0输出，否则换行*/ else printf(n); EnQueue(&q,s+t); while(t!=0); /*遇到结束符前循环*/ DeQueue(&q,&s);七、注意事项 1重点理解队列的算法思想，能够根据实际情况选择合适的存储结构。 2栈和队列的算法是后续实验的基础（广义表、树、图、查找、排序等）。3.提高内容： 模拟操作系统中进程的调度实现模拟操作系统中进程的调度。操作系统中仅设置一个进程队列，记录所有待执行的作业。调度算法每次从队列中取出一个进程执行1个时间片（time slice），若进程执行完毕则退出内存。否则，将剩余时间片数减1后，重新插入作业队列末尾等待再次调度。新的进程到达时，插入队列尾。要求：进程不少于5个，最终要给出每个进程执行的起止时间、进程的执行顺序和整个服务所需的总的时间；队列的存储方式可采用循环队列、链队列。循环队列示例:#define MAXSIZE 100typedef struct QElemType *base; /初始化的动态分配存储空间 int front; /头指针，队列不空指向队列头元素 int rear; /尾指针，队列不空指向队列尾元素下一位置 SqQueue;提示：每个进程在输入时，需描述下面的特征： 进程名（可用字符串或用整数简单表示） 到达时间（可用整数表示，以时间片为单位） 所需执行时间（整数，以时间片为单位）测试用的数据：时间片可选为1进程名 ABCDE到达时间01234服务时间43424八、实验报告内容及要求1.实验的程序源码2.运行程序，给出运行结果截图3.分析实验结果，得出结论实验五 矩阵一、实验属性 实验性质： 验证性 实验学时： 2学时 实验要求： 选作二、实验目的 1掌握稀疏矩阵压缩存储方法(三元组顺序表存储)。 2完成压缩存储下矩阵计算(矩阵转置)。三、实验环境及知识准备 1.实验环境： C与C+程序设计学习与实验系统 2.知识准备： 矩阵的压缩存储方法及算法实现。四、实验内容 1.实现矩阵压缩存储。(静态数组压缩存储或直接输入矩阵非0元均可)2.实现矩阵转置算法。3.实现矩阵快速转置。五、实验要求及步骤1.实现矩阵压缩存储。(静态数组压缩存储或直接输入矩阵非0元均可)2.实现矩阵转置算法TransposeSMatrix(TSMatrix M,TSMatrix &T)。3.实现矩阵快速转置FastTransposeSMatrix(TSMatrix M,TSMatrix &T)。4.主函数中创建矩阵M，将M调用转置算法转置成矩阵N，调用快速转置算法转化成矩阵T。六、实验指导三元组顺序表存储:#define MAXSIZE 12500 /设非零个数最大值 typedef struct int i, j; /该非零元的行下标和列下标 ElemType e; / 该非零元的值 Triple; / 三元组类型typedef struct Triple dataMAXSIZE + 1; /存放非零元(行序为主) int mu, nu, tu; /存放行数、列数、非零元素的总个数 TSMatrix; / 稀疏矩阵类型七、注意事项1.提高内容：矩阵乘法使用行逻辑链接的三元组顺序表压缩存储稀疏矩阵，并实现两个矩阵相乘。#define MAXSIZE 12500 /设非零个数最大值 typedef struct int i, j; /该非零元的行下标和列下标 ElemType e; / 该非零元的值 Triple; / 三元组类型typedef struct Triple dataMAXSIZE + 1; /存放非零元(行序为主) int rposMAXC+1; int mu, nu, tu; /存放行数、列数、非零元素的总个数 TSMatrix; / 稀疏矩阵类型八、实验报告内容及要求1.实验的程序源码2.运行程序，给出运行结果截图3.分析实验结果，得出结论实验六 二叉树的实现一、实验属性 实验性质： 设计性 实验学时： 2学时 实验要求： 必做二、实验目的 1掌握二叉树的存储实现。 2掌握二叉树的遍历思想。 3掌握二叉树的常见算法的程序实现。三、实验环境及知识准备 1.实验环境： C与C+程序设计学习与实验系统 2.知识准备：二叉树的存储、建立、遍历及其应用。四、实验内容 1输入字符序列，建立二叉链表存储结构。 2实现先序遍历二叉树、后序遍历二叉树的递归算法。 3实现栈及其基本操作，利用栈实现中序遍历二叉树的非递归算法。五、实验要求及步骤1定义二叉树的二叉链表存储结构。实现二叉树的创建函数CreateBiTree（BiTree *T）。2实现二叉树的先序PreOrderTraverse(BiTree T)，后序PostOrderTraverse(BiTree T)递归算法。3实现栈的定义及操作。4实现二叉树的中序遍历非递归算法InOrderTraverse（BiTree T）。 5主函数中按照二叉树先序遍历输入二叉树，创建一颗二叉树。 调用先序，中序，后序遍历算法，分别输出遍历序列。六、实验指导1.类型定义 /二叉链表存储 typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchild; BiTNode,*BiTree; 2部分程序模块如下，可在此基础上实现其余操作：#include #include #define OK 1#define ERROR 0#define OVERFLOW -2typedef char TElemType;typedef int Status;typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchild; BiTNode,*BiTree;Status CreateBinTree(BiTree *T)char ch;scanf(%c,&ch);if (ch= ) *T=NULL;else if(!(*T=(BiTNode*)malloc(sizeof(BiTNode) exit(OVERFLOW); (*T)-data=ch; CreateBinTree(&(*T)-lchild); CreateBinTree(&(*T)-rchild); return OK;Status PreOrderTraverse(BiTree T) if(T) printf(%c ,T-data); PreOrderTraverse(T-lchild); PreOrderTraverse(T-rchild); else return OK;void main() BiTree T; printf(Please input tree elements in PreOrderTraverse :n); if(CreateBinTree(&T) printf(The tree is ok!n); PreOrderTraverse(T); getch();七、注意事项 1注意理解递归算法的执行步骤。2注意字符类型数据在输入时的处理。3重点理解如何利用栈结构实现非递归算法，思考二叉树先序遍历及后序遍历非递归算法实现。 4二叉树层次遍历的实现 提示：利用队列实现二叉树的层次遍历算法。(1)初始化队列，根指针入队；(2) 对头出队，访问，出队元素左右孩子入队。至队列为空。八、实验报告内容及要求1.实验的程序源码2.运行程序，给出运行结果截图3.分析实验结果，得出结论实验七 图的实现及应用一、实验属性 实验性质： 设计性 实验学时： 4学时 实验要求： 必做二、实验目的 1掌握图的邻接矩阵和邻接表存储思想及其算法的实现。 2. 掌握图的深度、广度优先遍历算法思想及其程序实现。 3掌握图的常见应用算法的思想及其程序实现。三、实验环境及知识准备 1.实验环境： C与C+程序设计学习与实验系统 2.知识准备：图的存储结构、遍历算法、及其应用。四、实验内容 1 定义图的存储结构,实现图的创建。2 完成图的深度优先搜索算法。3 定义队列的存储结构，完成入队、出队、等基本操作的实现。4.利用队列完成图的广度优先搜索算法。*5邻接矩阵存储下，完成网的最小生成树求解过程。五、实验要求及步骤 1.键盘输入数据，建立一个有向图的邻接表。 2采用邻接表存储实现无向图的深度优先遍历递归算法。 3采用邻接表存储实现无向图的广度优先遍历算法。4在主函数中设计一个简单的菜单，分别调试上述算