[高等教育]数据结构实验指导书.doc

数据结构实验指导书主编 姜力山东理工大学工程技术学院电子信息系 目录概述-3课程大纲-4实验大纲-9实验一线性表顺序存储结构的描述及基本操作-12实验二线性表链式存储结构的描述及基本操作-13实验三栈存储结构的描述及应用算法设计-19实验四队列存储结构的描述及应用算法设计-21实验五二叉树的存储结构的两种描述方法-24实验六二叉树的基本操作实现-26实验七图存储结构的描述及基本操作实现-28实验八查找算法、排序基本算法- 35概述数据结构在计算机科学与技术专业中是一门必修的综合性专业基础课，对数据结构的研究不仅涉及计算机硬件的研究范围，而且和计算机的软件研究有着密切的关系，无论是编译原理还是操作系统，都涉及到数据元素在存储器中的分配问题；在研究信息检索时也必须考虑如何组织数据，以便查找和存取元素更为方便。因此，可以认为数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。学习本课程的目的是使学生了解计算机处理对象的特性，能将实际问题中所设计的处理对象在计算机中表示出来并对它们进行处理。学习本课程的任务是通过算法训练来提高学生的思维能力，通过程序设计的技能训练来提高学生的综合应用能力和专业素质。为今后学习程序设计特别是系统程序和大型应用程序的设计打下重要基础。要求学生通过实验学会分析研究计算机加工的数据对象的特性，通过算法设计及调试能够运用所学知识选择适当的数据结构、存储结构和编写相应的算法，初步掌握算法的时间与空间性能分析技巧，得到复杂程序设计的训练。数据结构课程教学大纲 课程名称：数据结构（Data Structures） 课程编号：172321总学时数：72学时（其中含实验教学 16学时） 学 分：4.5学分课程类别：必修先修课程：离散数学、C语言教 材：数据结构 (C语言版)（清华大学出版社、编者：严蔚敏）参考书目：宁正元编著，数据结构，水利水电出版社，2000年6月 课程内容简介： 数据结构是计算机程序设计的重要理论技术基础，是计算机学科的核心课程。第一章综述数据、数据结构和抽象数据类型等基本概念；第二至第七章从抽象数据类型的角度，分别讨论线性表、栈、队列、串、数组、广义表、树和二叉树以及图等基本类型数据结构及其应用；第八章综合介绍操作系统和编译程序中涉及的动态存储管理的基本技术；第九章至第十一章讨论查找和排序，介绍了各种实现方法，并从时间上进行定性或定量饿分析和比较；第十二章介绍常用的文件结构。一、课程性质、目的和要求 数据结构是计算机科学与技术专业必修的综合性专业基础课，学习本课程的目的是使学生了解计算机处理对象的特性，能将实际问题中所设计的处理对象在计算机中表示出来并对它们进行处理。课程的任务是通过算法训练来提高学生的思维能力，通过程序设计的技能训练来提高学生的综合应用能力和专业素质。为今后学习程序设计特别是系统程序和大型应用程序的设计打下重要基础。要求学生学会分析研究计算机加工的数据对象的特性，能够通过运用所学知识在实际应用中选择适当的数据结构、存储结构和相应的算法，初步掌握算法的时间与空间性能分析技巧，得到复杂程序设计的训练。二、教学内容、要点和课时安排 数据结构授课课时分配表课 程 内 容（按章节）课内学时课 程 内 容（按章节）课内学时第一章 绪论2第七章 图8第二章 线性表 8第八章 动态存储管理2第三章 栈和队列 8第九章 查找 4第四章 串4第十章 内部排序4第五章 数组和广义表4第十一章 外部排序 2第六章 树8第十二章 文件2合计56本课程的教学内容共分12章。第一章：绪论 主要内容是：数据结构的一些基本概念：数据、数据元素、数据结构、存储结构、数据类型、抽象数据类型、算法等。算法的时间复杂性和空间复杂性的评价。重点：基本概念与术语难点：抽象数据类型第二章：线性表 主要内容是：线性表的定义和线性表的顺序、链式存储结构。线性表的插入、删除等运算的算法。重点：线性表的操作算法难点：线性表算法设计第三章：栈与队列主要内容是：栈的定义、顺序、链式存储、进出栈运算及双栈操作。栈在非递归和递归算法中的应用。队列的定义、顺序、链式存储、入队和出队运算。重点：栈和队列的操作算法难点：栈的应用和队列的应用第四章：串主要内容是：字符串的定义、顺序存储和运算、串的模式匹配算法。重点：字符串的运算算法难点：串的模式匹配算法第五章：数组和广义表主要内容是：数组及其运算、数组的顺序存储、稀疏矩阵的三元组线性表表示、顺序存储、十字链存储及相关运算。广义表的定义、存储结构及运算。重点：特殊矩阵与稀疏矩阵难点：稀疏矩阵第六章：树主要内容是：树的概念和树的各种表示、二叉树的定义、性质、存储结构和生成算法。二叉树的遍历运算和线索的应用。二叉排序树的定义、查找、插入、删除和生成算法。哈夫曼树的定义和生成过程、哈夫曼编码。一般树的存储结构、树和森林之间的相互转换及树与森林遍历。重点：二叉树的运算、哈夫曼树及编码难点：哈夫曼树及编码第七章：图主要内容是：图的定义和基本术语、图的存储结构。主要指邻接矩阵和邻接表。图的深度和广度优先搜索遍历、产生图的最小生成树的普利姆算法和克鲁斯卡尔算法。求图中从一顶点到其余各项顶点最短路径的狄克斯特拉算法和每对顶点之间最短路径的佛洛伊德算法。拓扑排序的概念及算法、关键路径的概念及算法。重点：图的存储和算法难点：最小生成树、狄克斯特拉算法第八章：动态存储管理主要内容是：动态存储概念、可利用空间表及分配方法、边界标识法和伙伴系统。重点：动态存储概念、可利用空间表及分配方法难点：可利用空间表及分配方法第九章：查找主要内容是：查找的有关概念、顺序查找和二分查找、索引查找和分块查找，散列的概念，构造散列函数，处理冲突的方法，散列表的插入和查找算法。平衡二叉树的定义及调整算法，B_树的定义及查找、插入和删除关键字的过程。重点：各种查找算法难点：平衡二叉树的定义及调整算法、散列表第十章：内部排序主要内容是：排序的有关概念、直接插入排序和希尔排序、直接选择排序和堆排序、冒泡排序和快速排序。归并排序和基数排序。重点：各种排序算法难点：希尔排序、直接选择排序和堆排序第十一章：外部排序主要内容是：外存信息的存取、外部排序的方法。重点：外部排序的方法难点：外部排序的方法第十章：文件主要内容是：文件的概念，外存储器的组织，外存储器信息交换的基本单位页面的含义。顺序文件和索引文件的组织、按扩充散列和可扩充散列文件的组织、多重链接表文件和倒排文件的组织。重点：文件的概念难点：顺序文件和索引文件的组织三、教学方法 根据该课程理论性强、抽象、难度大的特点，以教师课堂讲授为主，教学方法采用多媒体技术手段，并结合学生的实际情况进行大量课外作业练习与上机实践练习。四、成绩考核方式考试采取笔试，满分100分。五、制定本大纲的有关说明1、本教学大纲是计算机科学与技术本科专业和信息管理与信息系统本科专业数据结构课程的基本内容。这些内容是通过讲课、实验和实训等教学环节进行教学的。2、本课程是一门介于数学、计算机硬件和计算机软件三者之间的综合基础课程。既有抽象的理论分析又有很强的实践性，涉及知识面较广。为了使学生便于理解讲课内容，在教学过程中要穿插安排一定数量的实践环节。使学生在学完本课程后，能够运用所学的知识，分析和解决实际的问题，为具有开发非数值计算程序设计、研发其它系统程序和设计大型应用程序打下坚实的理论基础和实践基础。3、因课程涉及的图形较多并且算法比较复杂，需采用多媒体教室教学。4、作业通过布置课后习题的形式进行，每周上交一次作业。通过课后练习、上机调试程序加以完善。以便使学生掌握通过对实际问题的抽象，舍去数据元素的具体内容，得到其逻辑结构，再通过抽象舍弃实现细节，得到运算的定义，从而完成设计任务的方法，达到能够独立设计出一般、复杂程序的目的。5、本课程必须在专业技术基础课：C语言、离散数学等课程的基础上开设。是操作系统、数据库系统等后续课程的基础，也是设计和实现其它系统程序和大型应用程序的重要基础。6、主讲教师根据本大纲，制定具体的授课计划。大纲执笔者：姜力大纲审定者：分管教学负责人签字： 数据结构(172321)实验(上机)教学大纲学科部(系): 工程技术学院电子信息系 执笔人: 姜力 审核人:王军一、 课程基本情况总学时72，教学计划实验学时16，实际开出实验学时16。本课程为计算机科学与技术本科专业基础课。二、实验教学目的和要求 1、掌握各实验项目的基本原理、方法和实验内容和步骤。2、熟练掌握线性表、树和图型结构。3、能独立编写算法和调试程序。4、了解三种数据结构的具体应用。三、学时分配及实验项目表学时分配及实验项目表（本课程实验共安排16学时，其中16学时为必选实验）。编码实 验 项 目名 称学时数/学分每组人数实验类型必选/可选首开时间17232101线性表的逻辑结构定义和顺序存储结构的描述方法220验证必选17232102线性表的链式存储结构的描述操作算法220验证必选17232103栈的基本操作220验证必选17232104队列的基本操作220验证必选17226505二叉树的存储220验证必选17232106二叉树的基本操作220验证必选17232107图的存储及基本运算220验证必选17232108查找、排序220综合必选四、实验课的考核1、学生在实验前应认真阅读实验指导书，设计算法要求并编写出程序代码。2、教师要重点讲述有关算法思想、调试环境和编程方法，使学生逐步掌握算法的设计思路、进一步理解课程内容、掌握程序调试的方法。3、要求学生独立完成实验项目，并按要求写出实验报告。4、实验成绩按优秀、良好、中等、及格和不及格5级评分标准，由实验指导教师评定给出。五、实验指导（参考）书和实验报告实验课程要有实验指导书或参考书及实验报告。实验指导（参考）书：数据结构上机实验指导书 自编参考讲义。实验报告的要求：1、 每个实验写一份实验报告2、 每个实验报告内容要求完备，必须有实验目的、实验内容，还可以根据实验的需求加上必要的讨论以及解决某些问题的想法和上机结果。实验报告要书写认真，反映出实验的过程和内容。六、实验项目信息：实 验 项 目 信 息实验项目称：数据结构实验 实验项目代码：172321课程名称数据结构课程代码172321实验类别专业基础实验依据教学大纲实验学时16实验类型验证实验专业计算机科学与技术每组人数20实验者本科实验内容概述：1、线性表的逻辑结构定义和各种存储结构的描述方法。要求熟练掌握线性表在顺序存储结构实现基本算法，并从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。2、栈的基本操作要求熟悉并掌握栈在两种存储结构上的基本运算操作，初始、终条件的描述。3、队列的基本操作要求熟悉并掌握队列在两种存储结构上的基本运算操作，初始、终条件（空、满）的描述。4、二叉树的存储结构要求熟练掌握树、二叉树的性质及各种存储结构。5、二叉树的基本运算熟悉二叉树的遍历算法和线索化算法。6、图的存储要求熟练掌握图的性质及邻接矩阵、邻接表存储结构。7、图的基本运算熟悉图的基本运算，遍历及最小生成树等算法。8、数据结构综合训练要求熟练掌握线性结构、树型结构和图形结构，会三种结构的基本算法及综合运用，会分析时间复杂度。本实验课程主要是在微机室内验证数据结构及算法的编程规则，以此来进一步掌握课堂上学习内容。本实验所需主要设备设 备 名 称规 格数量/组备注专用计算机586以上20共用20一次性耗材2020非一次性耗材2020 填表人： 姜力 审核人：注：本表是实验教学大纲的内容之一，实验室应有单独的项目卡片 2008-09-01实验一线性表顺序存储结构的描述及基本操作1、实验目的： 熟悉线性表的逻辑结构定义。掌握线性表的顺序存储结构实现、初始化、插入、删除等基本操作。2、实验要求：（1）掌握顺序表的类型定义、能够建立一个顺序表、设计顺序表的基本操作实现算法、输出一个顺序表。（2）设计算法，用C语言实现，调试并输出结果。 实验参考程序顺序表typedef structint elem20;int len;Sqlist; int Insert_sq(Sqlist *l,int i,int x)int j;if(il-len+1)return 0; if(l-len=19)return -1; for(j=l-len;j=i;-j) l-elemj+1=l-elemj; l-elemi=x; +l-len;return 1;int Delete_Sq(Sqlist *l,int i)int j;if(il-len) return 0; if(l-len=0) return -1; for(j=i;jlen;j+) l-elemj=l-elemj+1; -l-len; return 1 ; main() Sqlist s,*l; int i,x,j,n; l=&s; printf(nn=); scanf(%d,&n); for (i=1;ielemi); l-len=n; for (i=1;ilen ;i+) printf(%3d,l-elemi); printf(ncharu:ni=?); scanf(%3d,&i); printf(x=?); scanf(%d,&x); Insert_sq(l,i, x); for (i=1;ilen;i+) printf(%3d,l-elemi); printf(nlen=n%d,l-len); printf(nshanchu:ni=?); scanf(%d,&i); Delete_Sq(l,i); for (i=1;ilen;i+) printf(%3d,l-elemi); printf(nlen=n%3d,l-len); 实验二线性表链式存储结构的描述及基本操作方法1、实验目的： 熟悉线性表的逻辑结构定义。掌握线性表的链式存储结构实现、初始化操作、建立一个链表、插入、删除操作等。2、实验要求：（1）掌握链表的类型定义、能够建立一个链表(循环链表)、设计链表的基本操作实现算法、输出一个链表表。（2）设计算法，用C语言实现，调试并输出结果。 参考程序链表#include #include #include typedef int dataType; typedef struct node dataType data; struct node *next; *LinkList; void main() LinkList head,p; int num,n; head=malloc(sizeof(struct node); head-data=-1; head-next=head; printf(nn-000head=%d,000data=%d-n,head,head-data); printf(nn Input integer(ending with -1):n); scanf(%d,&num); while(num!=-1) p=(LinkList)malloc(sizeof(struct node);p-data=num; p-next=head-next; head-next=p; scanf(%d,&num); p=head-next; printf(-111head=%d:111data=%d-n,p,p-data); while(p!=head) printf(data:); printf(%dn,p-data); p=p-next; printf(ngoodbay!(0); scanf(%d,&n); if(n=0) return; 循环链表#include #include #include typedef int dataType; typedef struct node dataType data; struct node *next; *LinkList; void main() LinkList head,p,u,pre; int num,m,k=0; head=malloc(sizeof(struct node); head-data=-1; head-next=head; printf(nn-000head=%d,000data=%d-n,head,head-data); printf(nn Input integer(ending with -1):n); scanf(%d,&num); while(num!=-1) p=(LinkList)malloc(sizeof(struct node); p-data=num; p-next=head-next; head-next=p; scanf(%d,&num); p=head-next; printf(-111head=%d:111data=%d-n,p,p-data); while(p!=head) printf(data:); printf(%dn,p-data); p=p-next; p=head; printf(nn Count Number m=?); scanf(%d,&m); printf(nnnn%40snn,select); while(p-next!=p) pre=p; p=p-next; if(p=head) pre=p; p=p-next; +k; if(k=m) printf(%5d,p-data); pre-next=p-next; u=p; free(u); p=pre; k=0; printf(nn%40s,select out!n); printf(nn%40s,Good Bye!(0); scanf(%d,&m); if (m=0) return;约瑟夫回环#include #include #include typedef int dataType; typedef struct node dataType data; struct node *next; *LinkList; void init_linklist(LinkList head) ; void release_linklist(LinkList head) ; void clear_linklist(LinkList head) ; void creatlist(LinkList head) ; void out(LinkList head) ; void select(LinkList head) ; void exitJosephus(); void init_linklist(LinkList head) /*init_linklist*/ head=(LinkList) malloc(sizeof(struct node); head-data=-1; head-next=head; void clear_linklist(LinkList head) /*clear_linklist*/ LinkList p,q; p=head-next; head-next=head; while(p!=head) q=p; p=p-next; free(q); void creatlist(LinkList head) /*creatlist*/ int num; LinkList p; /*clear_linklist(head);*/ printf(nn Input integer(ending with -1):n); scanf(%d,&num); while(num!=-1) p=(LinkList)malloc(sizeof(struct node);p-data=num; p-next=head-next; head-next=p; scanf(%d,&num); void out(LinkList head) /*out*/ int i,n; LinkList p; i=1; n=1; p=head-next; printf(nn); while(p!=head) if(n=6) n=1; printf(n); printf(%5d:%-5d|,i,p-data); i+; n+; p=p-next; void select(LinkList head) /*select*/ int m,k=0; LinkList p,pre,u; p=head; printf(nn Count Number m=?); scanf(%d,&m); printf(nnnn%40snn,select); while(p-next!=p) pre=p; p=p-next; if(p=head) pre=p; p=p-next; +k; if(k=m) printf(%d,p-data); pre-next=p-next; u=p; free(u); p=pre; k=0; printf(nn%40s,select out!); void exitJosephus() printf(Good Bye!n); void main() int choice; LinkList head; /*init_linklist(head);*/ head=malloc(sizeof(struct node); head-data=-1; head-next=head; do printf(%s%15s%15s%15s%15s,nnnnnn,1:Create,2:Out,3:Select,4:ExitJosephus); printf(nn%33c,); scanf(%d,&choice); switch(choice) case 1: creatlist(head); out(head); break; case 2: out(head); break; case 3:select(head); break; case 4:exitJosephus(); break; default:printf(n Wrong select !Try again!) ; while(choice!=4) ;/*release_linklist(head);*/实验三栈存储结构的两种描述方法及应用算法设计1、实验目的：熟悉栈的逻辑结构定义。掌握栈的顺序存储结构实现、初始化栈、入栈、出栈、取栈顶元素等操作。掌握链式存储结构实现、初始化栈、入栈、出栈、取栈顶元素等操作。2、实验要求：（1）掌握栈的类型定义、能够建立一个栈（顺序栈、链栈）、设计栈的基本操作实现算法、设计一个栈的综合应用算法。（2）设计算法，用C语言实现，调试并输出结果。参考程序 值转换算法(栈操作)#define Maxsize 20typedef int DataType ;typedef struct DataType dataMaxsize;int top;SeqStack;void InitStack(SeqStack *S)S-top=0; int StackEmpty(SeqStack *S)if(S-top=0)return 1;elsereturn 0;void Push(SeqStack *S,DataType x)if(S-top=Maxsize-1) printf(Stack overflow); else S-data(S-top)+=x; DataType Pop(SeqStack *S) if(StackEmpty(S) printf(Stackunderflow); else return S-data-(S-top); void conversion(int n,int d); void main() int n,d; char ch; printf(start- y,exit- n :); scanf(n%c,&ch); while(ch=y) printf(input n:); scanf(%d,&n); printf(input d:); scanf(%d,&d); conversion(n,d); printf(contiue- y,exit-n); scanf(n%c,&ch); void conversion(int n,int d) DataType k; SeqStack L,*S; S=&L; InitStack(S); while(n) Push(S,n%d); n=n/d; printf(out:n); while(!StackEmpty(S) k=Pop(S); switch(k) case 10:printf(%c,a); break; case 11:printf(%c,b); break; case 12:printf(%c,c); break; case 13:printf(%c,d); break; case 14:printf(%c,e); break; case 15:printf(%c,f); break; default:printf(%d,k); printf(n); 实验四队列存储结构的描述及应用算法设计1、实验目的： 熟悉队列的逻辑结构定义,掌握队列的顺序存储结构实现、初始化队列、入队、出队、求队列长度等操作。掌握队列的链式存储结构实现、初始化队列、入队、出队、求队列长度等操作。2、实验要求：（1）掌握队列的类型定义、能够建立一个队列（顺序、链栈）、设计队列的基本操作实现算法、设计一个队列的综合应用算法。（2）设计算法，用C语言实现，调试并输出结果。参考程序队列操作#include #include #define OVERFLOW -1#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0typedef int Status;typedef char QElemType;typedef struct QnodeQElemType data;struct Qnode *next;Qnode,*QueuePtr;typedef structQueuePtr front;QueuePtr rear;int len;LQueue,*LinkQueue;Status InitQueue(LinkQueue Q) Q-front=(Qnode *)malloc(sizeof(Qnode); if (!Q-front) printf(OVERFLOW); Q-rear=Q-front; Q-front-next=NULL; Q-len=0; return OK;Status ClearQueue(LinkQueue Q) QueuePtr p,q; p=Q-front-next; Q-rear=Q-front; Q-front-next=NULL; Q-len=0; while(p) q=p; p=p-next; free(q); Status QueueEmpty(LinkQueue Q) if (Q-front=Q-rear) return TRUE; else return FALSE;int QueueLength(LinkQueue Q) return Q-len;Status GetHead(LinkQueue Q,char *e) if (Q-front=Q-rear) return ERROR; *e=Q-front-next-data; printf(h:%c,*e); return OK;Status EnQueue(LinkQueue Q,char e) QueuePtr p; p=(QueuePtr)malloc(sizeof(Qnode); if (!p) exit(OVERFLOW); p-data=e; p-next=NULL; Q-rear-next=p; Q-rear=p; +Q-len; return 1;Status DeQueue(LinkQueue Q,QElemType *e) QueuePtr p; if (Q-front=Q-rear) return ERROR; p=Q-front-next; *e=p-data; Q-front-next=p-next; Q-len-; if (Q-rear=p) Q-rear=Q-front; free(p); return OK;main() char *t,*f;LQueue A;QueuePtr p;LinkQueue Q;int s,i,j; char x,y; t=&x; f=&y;Q=&A;s=InitQueue(Q);printf(InitQueue ok!%dn,s);printf(input x:n);for(i=1;ilen);p=Q-front-next;for(i=1;ilen;+i) printf(%c ,p-data); p=p-next; while(!QueueEmpty(Q) DeQueue(Q,t); printf(n%c ,*t); printf(nThe Length of Queue is %d.n,Q-len); 实验五二叉树的存储结构的两种描述方法1、实验目的： 熟悉二叉树的逻辑结构定义。掌握二叉树的顺序、链式存储结构实现、建立二叉树的存储、遍历二叉树等基本操作。2、实验要求：（1）掌握二叉树的类型定义、能够建立一个二叉树（顺序、链栈）存储、设计二叉树的基本操作算法。（2）设计算法，用C语言实现，调试并输出结果。参考程序二叉树实验#define Null 0typedef struct node int data; struct node *lchild,*rchild; bitree,*bt; #define maxsize 64; typedef struct bt data64; int top; seqstack; seqstack *s; bitree *creat() bitree *t; int x; scanf(%d,&x); if(x=0) t=Null; else t=(bitree*)malloc(sizeof(bitree); t-data=x; t-lchild=creat(); t-rchild=creat(); return t; void inorder(t) bitree *t; if(t!=Null) inorder(t-lchild); printf(%4d,t-data); inorder(t-rchild); void exchange(t) bitree *t; seqstack a;bitree *p;seqstack *s;s=&a;