数据结构实验指导书C语言—连接表的操作.doc

数据结构实验参考资料目 录一、课程编号2二、课程类型2三、本课程的地位、作用与任务2四、课程基本要求2五、实验安排21、数据结构实验机器与环境2（一）计算机的硬件配置2（二）计算机的软件配置22、VisualC+6.0开发C语言程序2（一）进入C+工作环境2（二）编译、运行C程序33、上机实验6实验1：线性表操作6实验2：单链表操作11实验3：二叉树操作17实验4：图的运算23数据结构（C语言版）实验一、课程编号（本科）二、课程类型课程类型：必修课。适用专业：计算机大类各专业实验学时：16学时三、本课程的地位、作用与任务数据结构在计算机科学中是一门综合性的专业基础课。数据结构的研究不仅涉及到计算机硬件的研究范围，而且和计算机软件的研究有密切的关系，可以认为数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。在计算机科学中，数据结构不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其它系统程序和大型应用程序的重要基础，它的主要任务是讨论各种数据结构的逻辑结构，存储结构及有关操作的算法。目的是使学生学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应的算法，并初步了解对算法的时间分析和空间分析技术。另一方面，通过对本课程算法设计和上机实践的训练，还应培养学生的数据抽象能力和程序设计的能力，从而为提高学生的实际分析问题和解决问题的编程能力打下基础。四、课程基本要求1、 学生应根据每个上机实验的任务和教师所提的要求，上机前准备好上机内容。2、 上机输入程序并调试出结果。3、 上机结束后应按时提交实验报告，对于上机未完成部分，应该下机后利用课余时间完成。实验报告包括以下内容：(1) 实验题目(2) 实验目的(3) 实验要求(4) 实验内容(5) 实验总结五、实验安排1、数据结构实验机器与环境（一）计算机的硬件配置PC系列微机，包括286、386、486、奔腾及各种兼容机，要求内存为64M以上，一个硬盘驱动器和一个软盘驱动器，80列字符监视器，配备鼠标器。（二）计算机的软件配置DOS6.22或Windows 98、Windows 2000、Windows xp、Windows 7；VC+6.0或Turbo C。2、VisualC+ 6.0开发C语言程序（一）进入C+工作环境双击Windows桌面上的Visual C+ 6.0图标或单击Windows桌面上“开始”按钮，在“程序”中选择“Visual C+ 6.0”运行即可。（二）编译、运行C程序创建一个新的工程文件（Project file）启动Visual C+ 6.0 编译系统后，出现“Microsoft Developer Studio”窗口，该窗口菜单条有9个菜单项（如图1所示）：（1）单击“File”菜单，在其下拉菜单中选择“New”，屏幕上出现一个“New”对话框，在该对话框中选择“Projects”标签，出现“Project”对话框。（2）选择工程类型为“Win32 Console Application”，这时，在右边的Platforms选框中就会出现Win 32。（3）输入工程名字。在“Project name”选框中输入所指定的工程文件名字，例如： 1st。（4）输入路径名。在“Location”选框中，输入你将要把所建立的工程文件放人何处的路径名。例如，要将工程文件放在E 盘下已建立好的子目录E:sw1001子目录中，所以该选取路径为：E:sw10011st。选择“OK”按钮，该工程文件已建立。图1 创建新的工程文件建立源文件再次选择“File”菜单中的“New”选项，在四个标签中选择“File”标签，在其对话框选项中，选择“C+ Source File”，并在右边的Add project的选择框内打勾，激活其下面的选项，然后在File框内输入源文件名（如1st），单击“OK”按钮，出现编辑屏幕，即可编写程序（如图2和图3所示）。图2 建立源文件图3 编辑源文件编译连接和运行源程序程序编好后要进行编译连接和运行，步骤如下：（1）选择“Build”菜单，单击下拉菜单中的“Compile 1st.cpp”，这时系统开始对当前的源程序进行编译，在编译过程中,将所发现的错误显示在屏幕下方的“Build”窗口中。根据错误提示，修改程序后再重新编译，如还有错误，再继续修改、编译，直到没有错误为止。（2）编译无误后进行连接，这时选择“Build”菜单中的“Build 1st.exe”选项。同样，对出现的错误要进行更改，直到编译连接无错为止。这时，在“Build”窗口中会显示如下信息：1st.obj- 0 error(s), 0 warning(s)，说明编译连接成功，并生成以源文件名为名字的可执行文件（1st.exe）。（3）运行程序，选择“Build”菜单中的“! Execute 1st.exe”选项。这时，会出现一个“MS-DOS”窗口，输出结果显示在该窗口中（如图4和图5所示）。（4）运行结束后，可以回到“File”菜单，点击“Close Workspace”选项，关闭当前文件窗口。若要编辑新的源程序，可以再次打开“File”菜单，重新建立工程文件，步骤如上所述；也可以点击“File”菜单中的“Open Workspace”选项，打开一个已经存在的源文件。图4 编辑运行源程序图5 编译连接及结果3、上机实验实验1：线性表操作1实验目的1、 会定义线性表的顺序存储类型。2、 熟悉C或C+程序的基本结构，掌握程序中的用户头文件、实现文件和主文件之间的相互关系及各自的作用。3、 熟悉对线性表的一些基本操作和具体的函数定义。4、 熟悉Turbo C或VC+操作环境的使用以及多文件程序的输入、编辑、调试和运行的全过程。2实验要求1、 认真阅读和掌握本实验内容所给的全部程序。2、 保存和打印出程序运行结果，并结合程序进行分析。3、 按照你对线性表操作的需要，重新改写主文件并运行，打印出文件清单和运行的结果。3实验内容该程序的功能是对元素类型为整型的顺序存储的线性表进行一些操作。该程序包含三个文件，一个为头文件，用来存储定义的线性表结构类型以及对线性表进行的各种操作的函数声明；第二个为线性表操作的实现文件，用来存储每一种线性表操作的具体函数定义；第三种为主文件，用来定义线性表和调用线性表的一些操作，实现对给定线性表的具体运算。整个程序如下：/头文件linearlist1.h/定义ElemType为int类型/头文件linearlist1.h/定义ElemType为int类型typedef int ElemType;/线性表顺序存储类型struct LinearList ElemType* list; /存线性表元素int size; /存线性表长度int MaxSize; /存list数组长度; /初始化线性表 void InitList(LinearList& L, int ms); /清空线性表 void ClearList(LinearList& L); /求线性表长度 int ListSize(LinearList& L); /检查线性表是否为空 bool ListEmpty(LinearList& L); /检查线性表是否为满 bool ListFull(LinearList& L); /遍历线性表 void TraverList(LinearList& L); /从线性表中查找元素 bool FindList(LinearList& L, ElemType& item); /更新线性表中的给定元素 bool UpdateList(LinearList& L, const ElemType& item); /向线性表插入元素 bool InsertList(LinearList& L, const ElemType& item, int mark); /从线性表中删除元素 bool DeleteList(LinearList& L, ElemType& item, int mark);/对线性表进行有序输出 void OrderOutputList(LinearList& L, int mark);/实现文件linearlist1.cpp #include #include #include #includelinearlist1.h/初始化线性表void InitList(LinearList& L, int ms) L.list=new ElemTypems;if(!L.list) printf(Memory allocation failure!);exit(1); L.size=0;L.MaxSize=ms;/清空线性表void ClearList(LinearList& L) L.size=0;/求线性表长度int ListSize(LinearList& L) return L.size;/检查线性表是否为空bool ListEmpty(LinearList& L) return L.size=0; /检查线性表是否为满bool ListFull(LinearList& L) return L.size=L.MaxSize; /遍历线性表void TraverList(LinearList& L) for(int i=0; iL.size; i+) printf( %d,L.listi);printf(n); /从线性表中查找元素bool FindList(LinearList& L, ElemType& item) for(int i=0; iL.size; i+)if(L.listi=item) item=L.listi;return true;return false; /更新线性表中的给定元素bool UpdateList(LinearList& L, const ElemType& item) for(int i=0; i0) for(int i=L.size-1; i=0; i-)L.listi+1=L.listi;L.list0=item; else if(mark0) L.listL.size=item;else for(int i=0; iL.size; i+) if(item=i; j-) L.listj+1=L.listj; L.listi=item;L.size+;return true; /从线性表中删除表头、表尾或等于给定值的元素bool DeleteList(LinearList& L, ElemType& item, int mark)if(ListEmpty(L) return false;if(mark0) item=L.list0;for(int i=1; iL.size; i+)L.listi-1=L.listi; else if(mark0) item=L.listL.size-1;else for(int i=0; i=L.size) return false; else item=L.listi; for(int j=i+1; jL.size; j+) L.listj-1=L.listj;L.size-;return true; /对线性表按升序或降序输出void OrderOutputList(LinearList& L, int mark)int* b=new intL.size;int i,k;for(i=0; iL.size; i+)bi=i;for(i=1; iL.size; i+) k=i-1;for(int j=i; jL.size; j+) if(mark=1 & L.listbjL.listbk) k=j; /升序 if(mark!=1 & L.listbkL.listbj) k=j; /降序if(k!=i-1) int x=bi-1; bi-1=bk; bk=x;for(i=0; iL.size; i+)printf( %d,L.listbi);printf(n);/主文件listmain1.cpp#include /要用到格式控制符#include #includelinearlist1.hconst int ML=10; void main()LinearList a;InitList(a,ML);int i;ElemType x; /依次向线性表a表尾插入5个整数元素printf(从键盘输入5个整数:n);for(i=0; i5; i+)scanf(%d,&x);InsertList(a,x,-1); /依次向线性表a表头插入2个整数元素printf(从键盘输入2个整数:);scanf(%d,&x);InsertList(a,x,1);scanf(%d,&x);InsertList(a,x,1); /按不同次序遍历输出线性表aTraverList(a);OrderOutputList(a,1);OrderOutputList(a,0); /把线性表a中的所有元素依次有序插入到一个新线性表b中 LinearList b;InitList(b,ML);for(i=0; ia.size; i+)InsertList(b, a.listi, 0); /输出线性表bTraverList(b); /从线性表a中分别删除表头、表尾、给定值元素if(DeleteList(a,x,1) printf(Delete success!);else printf(Delete fail!n);if(DeleteList(a,x,-1) printf(Delete success!n);else printf(Delete fail!n);printf(从键盘上输入一个待删除的整数:n);scanf(%d,&x);if(DeleteList(a,x,0) printf(Delete success!n);else printf(Delete fail!n); /输出线性表aTraverList(a);（选作）试着参照算法写出C语言程序，实现下列题目要求！（1）试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表逆置为。解：/ 顺序表的逆置Status ListOppose_Sq(SqList &L)int i;ElemType x;for(i=0;iL.length/2;i+)x=L.elemi;L.elemi=L.elemL.length-1-i;L.elemL.length-1-i=x;return OK;（2） 假设以两个元素依值递增有序排列的线性表A和B分别表示两个集合（即同一表中的元素值各不相同），现要求另辟空间构成一个线性表C，其元素为A和B中元素的交集，且表C中的元素有依值递增有序排列。试对顺序表编写求C的算法。解：/ 将A、B求交后的结果放在C表中Status ListCross_Sq(SqList &A,SqList &B,SqList &C)int i=0,j=0,k=0;while(iA.le