数据结构实验教学

数据结构实验指导说明：课内上机要求完成实验一到实验四的内容，并完成实验报告，实验报告在十七周星期三之前交，其他实验请大家课外抽时间完成。给出的示例程序供大家参考，大家实验的时候要自己动手编写程序，切不可完全照抄，每个实验具体的实验题目大家可以做示例的题目，也可以自己定一题目，只需用到该实验的知识点即可，编程语言大家可以选用自己熟悉的语言。一．实验要求：书写类C语言的算法，并将算法转变为程序实现。正确理解各种数据结构的逻辑特性和存储表示和基本操作的算法实现。针对问题的不同选择合适的数据结构，提高算法设计的能力和动手实验的技能。。二．主要仪器设备：（所开实验的主要仪器设备）硬件要求：在多媒体教室讲解及演示。为保证教学顺利进行，要求实验室提供PⅢ及以上的微机。三、实验项目内容简介为了达到实验目的，本课程安排了四个实习单元，训练的重点在于基本的数据结构，而不是强调面面俱到。各实习单元与教科书的各章只具有粗略的对应关系，一个实习题常常涉及到几部分教学内容。1、线性表基本操作（1)熟悉线性表的基本运算在两种存储结构（顺序结构和链式结构）上的实现（2)以线性表的各种操作（建立、插入、删除等）的实现为重点（3)通过本次实习帮助学生加深对高级语言C语言的使用（特别是函数参数、指针类型、链表的使用）。2、栈、队列以及递归算法的设计（1)掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们（2)训练的要点是“栈”的观点及其典型用法；问题求解的状态表示及其递归算法；由递归程序到非递归程序的转化方法3、树、图及其应用（1)树和图是两种非线性数据结构，广义表的实质是树结构，而稀疏矩阵的十字链表存储结构也是图的一种存储结构，故本单元是本课的实习重点。（2)要求学生熟悉各种存储结构的特性，以及如何应用树和图结构求解具体问题。（3)训练的要点是：递归算法的设计方法；表达式的求值技术；哈夫曼方法及其编译码技术；完整的应用系统的用户界面设计和操作定义方法；矩阵乘法的特殊操作顺序；路径遍历（树、图的遍历）技术。4、查找和排序本次实习旨在集中对几个专门的问题做较为深入的探讨和理解重点在掌握各种内部排序算法、查找算法的思想和实现。学生在实习中体会查找和内部排序算法思想，理解开发高效算法的可能性和寻找、构造高效算法的方法。四、主要参考书1、《数据结构题集》（C语言版）实习题部分，清华大学出版社,1999.112、《数据结构习题与解析》（C语言篇），李春葆编著，清华大学出版社，2000.13、宁正元《数据结构习题解析与上机实验指导》水利水电出版社（2003年）实验一线性表的操作一、实验目的1．熟悉C语言的上机环境，掌握C语言的基本结构。2．会定义线性表的顺序存储结构。（链式存储结构）3．熟悉对顺序表（单链表）的一些基本操作。二、实验要求1．认真阅读和掌握本实验内容所给的全部程序。2．保存和打印出程序运行结果，并结合程序进行分析。注意事项在做第一次“数据结构”课程实验之前，要在硬盘上建立好自己的工作目录，专门来存储你所做的实验程序及相关信息，以后每次做实验都采用这个目录。三、实验内容1、示例（以顺序表为示例，同学们也可以编程实现单链表的创建、查找、插入、删除等功能）以输入整形数据为主，输入后按“？”结束输入。程序所能表达到的功能为：实现顺序表的创建、查找、插入、删除等功能。程序运行后，输入数据并执行。#includestdio.h#includeconio.h#defineMaxSize50typedefcharelemtype;typedefstructnode{elemtypedata[MaxSize];intlen;}lnode,*List;voidinit(ListL){L-len=0;}intlength(ListL){returnL-len;}elemtypegetnode(ListL,intpos){if(pos1||posL-len)printf(error);elsereturnL-data[pos-1];}intlocate(ListL,elemtypex){inti=0;while(iL-len&&L-data[i]!=x)i++;if(i==L-len)return-1;elsereturn(i+1);}voidinsert(ListL,intpos,elemtypex){intj;if(pos1||posL-len+1)printf(inserterror\n);else{L-len++;for(j=L-len;j=pos;j--)L-data[j]=L-data[j-1];L-data[pos-1]=x;};}voiddelnode(ListL,intpos){intj;if(pos1||posL-len)printf(delerror\n);else{for(j=pos;jL-len;j++)L-data[j-1]=L-data[j];L-len--;}}voidprint(ListL){inti;for(i=1;iL-len;i++)printf(%c-,L-data[i-1]);printf(%c,L-data[L-len-1]);}main(){inti=1,n;lnodeL;charch,x;init(&L);printf(\n\n\n*******************************顺序表演示程序***********\n);printf(请输入你想建立的顺序表的元素，以？结束:);ch=getchar();while(ch!='?'){insert(&L,i,ch);i++;ch=getchar();};printf(你建立的顺序表为:);print(&L);printf(\n顺序表的长度为:%d,L.len);printf(\n输入你想查找的元素：);fflush(stdin);scanf(%c,&x);printf(你查找的元素为%c序位为%d,x,locate(&L,x));printf(\n输入你想查找的元素序位:);scanf(%d,&n);printf(\n你查找的元素为：%c,getnode(&L,n));printf(\n输入你想插入的元素以及序位:用逗号隔开);fflush(stdin);scanf(%c,%d,&x,&n);insert(&L,n,x);printf(\n插入后顺序表为：);print(&L);fflush(stdin);printf(\n请输入你想删除的元素序位：);scanf(%d,&n);delnode(&L,n);printf(\n删除后的顺序表为：);print(&L);getch();}四、测试结果运行程序，屏幕显示：“请输入你想建立的顺序表的元素，以？结束:”输入：54381你建立的顺序表为:5—4—3—8—1顺序表的长度为:5输入你想查找的元素：4你查找的元素为4序位为2输入你想查找的元素序位:4你查找的元素为：8输入你想插入的元素以及序位:用逗号隔开：6，3插入后顺序表为：5—4—6—3—8—1请输入你想删除的元素序位：5删除后的顺序表为：5—4—6—3—1实验二二叉树的操作一．实验目的理解并熟悉掌握创建二叉树和实现二叉树的三种遍历二．实验内容创建二叉树和实现二叉树的三种遍历根据提示输入字符型数据创建二叉树，输入值为所有字符型数据输出为遍历后的每个结点的值的顺序创建二叉树并能实现二叉树的先序、中序、后序遍历如果输入数据为：abc输出结果为：abcbacbca程序流程：main()clrscr()createtree()preorder()inorder()postorder源程序#includestdlib.h/*引入头文件*/structtnode/*定义二叉树存储结构*/{chardata;structtnode*lchild;structtnode*rchild;};structtnodetree;/*定义二叉树指针*/voidcreatetree(structtnode*t)/*创建函数*/{structtnode*p=t;/*把二叉树指针给p*/charcheck;if(p-lchild==NULL||p-rchild==NULL)/*判断左右子树是否为空*/{printf(pleaseenterthedata:);/*输入根结点数据*/scanf(%c,&(p-data));getchar();}if(p-lchild==NULL){printf(%cleftchildisnull.Add?y/n\n,p-data);/*左子树空，询问是否创建*/scanf(%c,&check);getchar();if(check=='y'){structtnode*q=(structtnode*)malloc(sizeof(structtnode));/*开辟空间*/q-lchild=NULL;q-rchild=NULL;p-lchild=q;createtree(q);}}if(p-rchild==NULL){printf(%crightchildisNULL.Add?y/n\n,p-data);/*右子树空，询问是否创建*/scanf(%c,&check);getchar();if(check=='y'){structtnode*q=(structtnode*)malloc(sizeof(structtnode));/*开辟空间*/q-lchild=NULL;q-rchild=NULL;p-rchild=q;/*连到二叉树上*/createtree(q);}}}voidpreorder(structtnode*t)/*先序遍历函数*/{if(t){printf(%c,t-data);/*输出根结点数据*/preorder(t-lchild);preorder(t-rchild);}}voidinorder(structtnode*t)/*中序遍历函数*/{if(t){inorder(t-lchild);printf(%c,t-data);inorder(t-rchild);}}voidpostorder(structtnode*t)/*后序遍历函数*/{if(t){postorder(t-lchild);postorder(t-rchild);printf(%c,t-data);}}voidmain(){clrscr();/*清屏函数*/tree.lchild=NULL;/*左子树*/tree.rchild=NULL;/*右子树*/createtree(&tree);/*创建二叉树*/preorder(&tree);/*先序遍历*/printf(\n);inorder(&tree);/*中序遍历*/printf(\n);postorder(&tree);/*后序遍历*/}三．使用说明程序运行：先输入根结点数据，例如：a输入y或n判断是否创建左子树。输入y然后输入左子树数据输入y或n判断是否创建右子树。输入y然后输入右子树数据按回车可查看遍历结果并退出程序。四．测试结果运行程序，屏幕提示：pleaseenterthedata:a/*首先输入根结点，为a*/aleftchildisnull.add?y/n/*询问是否输入a结点的左结点*/y/*输入*/pleaseenterthedata:b/*输入结点a的左结点，为b*/bleftchildisnull.add?y/n/*询问是否输入b结点的左结点*/n/*不输入*/brightchildisnull.add?y/n/*询问是否输入b结点的右结点*/n/*不输入*/arightchildisnull.add?y/n/*询问是否输入a结点的右结点*/y/*输入*/pleaseenterthedata:c/*输入结点a的右结点，为