数据结构试验指导书

1、数据结构实验指导书数据结构是软件工程等专业的一门核心基础课程，也是很多高校考研专业课之一。 它主要介绍线性结构、树结构、图结构三种逻辑结构元素的存储实现，在此基础上介绍一些 典型算法及时、空效率分析。这门课程的主要任务是培养学生的算法设计能力及良好的程序 设计习惯。通过学习，要求学生能够掌握典型算法的设计思想及程序实现，能够根据实际问 题选取合适的存储方案，设计出简洁、高效、实用的算法，为后续课程的学习及软件开发打 下良好的基础。学习这门课程，习题和实验是两个关键环节。学生理解算法，上机实验是最 佳的途径之一。因此，实验环节的好坏是学生能否学好数据结构的关键。为了更好地配 合学生实验，特编写实

2、验指导书。一、实验目的更好的理解算法的思想、培养算法设计、分析及程序调试能力。二、实验要求1、每次实验前学生必须根据试验内容认真准备实验程序及调试时所需的输入数据及 预期输出数据。2 、独立完成或在指导教师的帮助下，完成实验项目，得出正确的实验结果。3 、遵守实验室规章制度、不缺席、按时上、下机。4 、实验学时内必须做数据结构的有关内容， 不允许上网聊天或玩游戏， 如发现上述现 象，取消本次上机资格，平时成绩扣 10 分。5 、实验项目有一次未完成，扣 5 分，两次以上未完成者，平时成绩以零分记，不允许 参加期末考试。三、实验环境 VC+6.0或其它C+集成环境四、说明1 、本实验的所有算法中

3、元素类型可以根据实际需要选择。2 、实验题目中带者为较高要求，学生可自选；其余部分为基本内容，必须完成，否 则实验不合格。3 、数据结构是很多高校的硕士研究生入学考试的专业课之一， 希望有志于考研的学生 能够在学习过程中注意各种算法的理解，以便为考研做一定的准备。4、所有实验项目布置在在线评测系统平台（Online Judge System）上，校内访问IP :59.73.73.133 ，每位学生需实名注册账号， 并将完成的实验项目在平台上提交， 平台能够实 现自动评测。五、参考书目数据结构（C+语言描述）王红梅等清华大学出版社DATA STRUCTURE WITH C+ William Fo

4、rd,William Topp清华大学出版社（影印版）目录实验一线性表的操作 3实验二栈、队列的操作 4实验三二叉树的操作 5实验四图的操作 12实验五查 找 14实验六排 序 15实验七综合实验 16实验八停车场管理 18实验九窗口管理 19实验类型：设计性实验要求：必修实验学时： 4 学时一、实验目的 ：基于线性表顺序表类和链表类，实现线性表的相关算法。实验一 线性表的操作二、实验要求 ：1、掌握线性表顺序表类和链表类的特点。掌握线性表的常见算法。2、在评测系统平台提交相应的实验项目，并提交电子版实验报告，报告内容包括：目 的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设

5、计技巧、心得体 会。三、实验内容：1设计一个静态数组存储结构的顺序表类，要求编程实现如下任务： 建立一个线性表，首先依次输人数据元素 1, 2, 3，10,然后删除数据元素 6,最后依次显示当前 线性表中的数据元素。要求采用顺序表实现，假设该顺序表的数据元素个数在最坏 情况下不会超过 50 个。2设计一个带头结点的单链表类,要求：(1) 生成一个整数线性表, 实现将其分解成两个链表, 其中一个全部为奇数, 另一个 全部为偶数(尽量利用已知的存储空间) 。(2) 设计一个测试主函数,实际运行验证所设计单链表类的正确性。 3设计一个不带头结点的单链表类,要求：(1) 不带头结点单链表类的成员函数包

6、括取数据元素个数、插入元素、 删除所有值为 k 的元素、取数据元素。( 提示： 要考虑在第一个数据元素结点前插入和删除第一个数据元素结点时与在其 他位置插入和删除其他位置结点时的不同情况。 )(2) 设计一个测试主函数,实际运行验证所设计循环单链表类的正确性。 4设计一个仅设置尾指针的无头结点的循环单链表类,实现约瑟夫环问题； 问题描述：设编号为 1,2, , n(n>0) 个人按顺时针方向围坐 -圈,每人持有一个正整数密码。开始时任意给出一个报数上限值m从第一个人开始顺时针方向自1起顺序报数。报到m时停止报数，报 m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人起重新自

7、 1 起顺序报数 . 如此下去,直到所有人全部出列为止。要求设计一个程序模拟此过 程,并给出出列人的编号序列。测试数据： n=7,7 个人的密码依次为 3,1,7,2,4,8,4 初始报数上限值 m=20*5设计一个带头结点的循环双向链表类,要求：(1) 带头结点循环双向链表类：获取元素个数、插入、删除、取数据元素等。(2) 设计一个测试主函数,实际运行验证所设计循环双向链表类的正确性。 *6设计一个单链表实现一元多项式求和问题。要求：( 1 )设计存储结构表示一元多项式；(2) 设计算法实现一元多项式相加。实验类型：验证性实验要求：必修实验学时： 2 学时一、 实验目的：基于栈类和队列类，实

8、现栈和队列的常见算法，并结合线性表类实现有关串的操作。实验二 栈、队列的操作二、实验要求：1、掌握栈、队列、串的特点。掌握特殊线性表的常见算法。 2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、 程序清单、调试情况、设计技巧、心得体会。三、实验内容：1. 堆栈类测试和应用问题。要求：(1)设计一个主函数实现对顺序堆栈类和链式堆栈类代码进行测试。测试方法为： 依次把数据元素 1,2,3,4,5 入栈，然后出栈堆栈中的数据元素并在屏幕上显示。(2)定义数据元素的数据类型为如下形式的结构体：struct DataType char taskname10;/ 任务名int

9、 taskno; / 任务号;设计一个包含 5个数据元素的测试数据， 并设计一个主函数实现依次把 5 个数据元 素入栈，然后出栈堆栈中的数据元素并在屏幕上显示。2. 队列类测试和应用问题。要求： 设计一个主函数对循环队列类和链式队列类代码进行测试. 测试方法为：依次把数据元素 1,2,3,4,5 入队，然后出队中的数据元素并在屏幕上显示。3设计串采用顺序存储结构，编写函数实现两个串的比较Compare(S, T) 。要求比较结果有大于、等于和小于三种情况。*4. 设计算法利用栈类实现把十进制整数转换为二至九进制之间的任一进制输出。*5. 设计串采用静态数组存储结构，编写函数实现串的替换 Rep

10、lace(S, start, T, V) ， 即要求在主串S中，从位置start开始查找是否存在子串T,若主串S中存在子串T,则用子串V替换子串T,且函数返回1;若主串S中不存在子串T,则函数返回0。并要求设计主函数进行测试。一个测试例子为：S=" I am a student”，T=“student ”， V=“ teacher ”。*6.输入一个C+表达式，实现表达式求值算法。注意问题1 重点理解栈、队列和串的算法思想，能够根据实际情况选择合适的存储结构。2 栈、队列的算法是后续实验的基础(树、图、查找、排序等) 。实验类型：设计性实验要求：必修实验学时： 2 学时一、 实验目的

11、：基于教材给定的二叉树类，实现二叉树的有关操作。实验三 二叉树的操作二、实验要求： 1、掌握二叉树、哈夫曼树和树的特点。掌握它们的常见算法。 2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、 程序清单、调试情况、设计技巧、心得体会。三、实验内容：1 设计实现二叉树类，要求： （1）编写一个程序，首先建立不带头结点的二叉链式存储结构的二叉树，然后分 别输出按照前序遍历二叉树、 中序遍历二叉树和后序遍历二叉树访问各结点的序 列信息，最后再测试查找函数和撤销函数的正确性。（2）实现二叉树层次遍历的非递归算法。（3）编写一主函数来验证算法实现。2. 假设二叉树采用链式存储

12、结构进行存储， 编写一个算法， 输出一个二叉树的所有叶 子结点，并统计叶子结点个数。*3. 设计实现二叉线索链表类，要求： （1）编写一个程序，首先建立中序线索链表的二叉树，然后实现中序线索链表的 遍历算法。（2）编写一主函数来验证算法实现。*4. 编写求二叉树高度的函数。*5. 编写创建哈夫曼树和生成哈夫曼编码的算法。*6假设二叉树采用链式存储结构进行存储，试设计一个算法，输出从每个叶子结点 到根结点的路径。*7 假设二叉树采用链式存储结构进行存储，试设计一个算法，求二叉树的宽度（即 具有结点数最多的层次上结点总数）四、程序样例1.二叉树二叉链表结点声明template <class

13、T>struct BiNodeT data;BiNode<T> *lchild, *rchild;二叉链表类声明template <class T>class BiTreepublic:BiTree ( ) root=NULL;/无参构造函数，初始化一棵空的二叉树BiTree( BiNode<T> *root ); /有参构造函数，初始化一棵二叉树，其前序序列由键盘输入BiTree ( ) ;/析构函数，释放二叉链表中各结点的存储空间void PreOrder ( BiNode<T> *root );/ 前序遍历二叉树void InOrde

14、r ( BiNode<T> *root ); / 中序遍历二叉树 void PostOrder ( BiNode<T> *root );/ 后序遍历二叉树void LeverOrder ( BiNode<T> *root ); / 层序遍历二叉树private:BiNode<T> *root;/指向根结点的头指针void Creat ( BiNode<T> *root );/有参构造函数调用void Release( BiNode<T> *root ); /析构函数调用;二叉树的层序遍历算法 LeverOrdertempl

15、ate <class T>void BiTree:LeverOrder ( BiNode<T> *root )front=rear=0; /采用顺序队列，并假定不会发生上溢if ( root=NULL ) return;Q+rear=root;while ( front!=rear )q=Q+front;cout<<q -> data;if ( q-> lchild!= NULL) Q+rear=q -> lchild;if ( q-> rchild!= NULL) Q+rear=q -> rchild; 二叉树的构造函数算法

16、BiTree template <class T>BiTree :BiTree ( BiNode<T> *root )creat( root ) ；template <class T>void BiTree :Creat ( BiNode<T> *root )cin>>ch;if ( ch='# ') root=NULL;/建立一棵空树else root=new BiNode<T>/生成一个结点root-> data=ch;Creat( root-> lchild ); /递归建立左子树 Cre

17、at( root-> rchild ) ; /递归建立右子树二叉树的后序遍历递归算法 PostOrdertemplate <class T>void BiTree:PostOrder ( BiNode<T> *root )if ( root= NULL ) return;/递归调用的结束条件else PostOrder( root-> lchild ) ;/后序递归遍历 root 的左子树PostOrder( root-> rchild ) ;/ 后序递归遍历 root 的右子树cout<<root -> data;/访问根结点的数据

18、域二叉树的后序遍历非递归算法 PostOrdertemplate <class T>void BiTree:PostOrder ( BiNode<T> *root )top= -1;/采用顺序栈，并假定栈不会发生上溢while ( root!= NULL | | top!= - 1)while ( root!= NULL)top+;stop.ptr=root; stop.flag=1; root=root -> lchild;while ( top!= -1 && stop.flag=2 )root=stop - .ptr; cout<<

19、;root -> data;if ( top!= -1) stop.flag=2; root=stop.ptr -> rchild; 二叉树前序遍历递归算法 PreOrder template <class T> void BiTree:PreOrder ( BiNode<T> *root ) if ( root = NULL ) return;/递归调用的结束条件else cout<<root -> data; / 访问根结点的数据域PreOrder( root-> lchild ) ; / 前序递归遍历 root 的左子树 Pre

20、Order( root-> rchild ) ; / 前序递归遍历 root 的右子树 二叉树的前序遍历非递归算法 PreOrdertemplate <class T> void BiTree:PreOrder ( BiNode<T> *root ) top= - 1;/ 采用顺序栈，并假定不会发生上溢while ( root!= NULL | | top!= -1)while ( root!= NULL) cout<<root -> data; s+top=root; root=root -> lchild; if ( top!= -1)

21、 root=stop - ; root=root -> rchild; 二叉树的析构函数算法 BiTree template <class T> BiTree :BiTree ( BiNode<T> *root ) Release( root) ;void BiTree :Release ( BiNode<T> *root ) if ( root!=NULL ) Release( root-> lchild ); / 释放左子树 Release( root-> rchild ); / 释放右子树 delete root; 二叉树的中序遍历递

22、归算法 InOrder template <class T> void BiTree:InOrder ( BiNode<T> *root ) if ( root= NULL ) return;/递归调用的结束条件else InOrder ( root-> lchild ) ; /中序递归遍历 root 的左子树 cout<<root -> data;/ 访问根结点的数据域InOrder ( root-> rchild ) ; /中序递归遍历 root 的右子树 2 线索链表线索链表结点声明enum flag Child, Thread; /

23、枚举类型，枚举常量 Child=0 ，Thread=1 template <class T>struct ThrNodeT data;ThrNode<T> *lchild, *rchild; flag ltag, rtag;线索链表类声明template <class T> class InThrBiTreepublic:InThrBiTree ( ThrNode<T> * root );/构造函数，建立中序线索链表 InThrBiTree ( ) ;/析构函数，释放线索链表中各结点的存储空间ThrNode *Next ( ThrNode<

24、T> *p ) ; / 查找结点 p 的后继 void InOrder ( ThrNode<T> *root ) ; / 中序遍历线索链表 private:ThrNode<T> *root;/ 指向线索链表的头指针void Creat ( ThrNode<T> *root ) ; /构造函数调用void ThrBiTree ( ThrNode<T> *root );/构造函数调用;中序线索链表构造函数算法 InThrBiTree template <class T>InThrBiTree:InThrBiTree ( ThrNod

25、e<T> *root )Creat( root) ;pre=NULL;ThrBiTree ( root) ;template <class T>void InThrBiTree :Creat ( ThrNode<T> *root )cin>>ch;if ( ch='# ') root=NULL;/ 建立一棵空树else root=new ThrNode<T>/生成一个结点，左右标志均置0root-> data=ch; root -> ltag=0; root -> rtag=0;Creat( root

26、 -> lchild ) ;/递归建立左子树Creat( root -> rchild );/递归建立右子树 template <class T> void InThrBiTree :ThrBiTree ( ThrNode<T> *root )if ( root= NULL ) return;ThrBiTree ( root -> lchild ) ;if (!root-> Ichild ) /对root的左指针进行处理root->ltag=1;root-lchild=pre;设置pre的前驱线索if ( !root->rchild

27、) root->rtag=1;/对 root 的右指针进行处理if ( pre->rtag=1) pre-> rchild=root; /设置 pre 的后继线索 pre=root;ThrBiTree ( root->rchild) ; 中序线索链表查找后继的算法 Next template <class T>ThrNode<T> *InThrBiTree:Next (ThrNode<T> *p ) if ( p-> rtag= =1 ) q=p->rchild;/右标志为 1，可直接得到后继结点else q=p->

28、rchild;/工作指针初始化，while (q->ltag=0)/查找最左下结点q=q->lchild;return q; 中序线索链表查找后继的算法 Next template <class T> void InThrBiTree:InOrder ( ThrNode<T> *root ) if ( root=NULL ) return; / 如果线索链表为空，则空操作返回 p=root;while ( p-> ltag=0 )/查找中序遍历序列的第一个结点p 并访问p=p-> lchild;cout<<p -> data;w

29、hile ( p-> rchild!=NULL ) / 当结点 p 存在后继，依次访问其后继结点 p=Next ( p) ; cout<<p -> data; 中序线索链表构造函数算法 InThrBiTree template <class T>InThrBiTree:InThrBiTree ( ThrNode<T> *root )Creat( root) ;pre=NULL;ThrBiTree ( root) ; template <class T> void InThrBiTree :Creat ( ThrNode<T>

30、; *root )cin>>ch;if ( ch='# ') root=NULL;/ 建立一棵空树else root=new ThrNode<T>/生成一个结点，左右标志均置0root-> data=ch; root -> ltag=0; root -> rtag=0;Creat( root -> lchild ) ;/递归建立左子树Creat( root -> rchild );/递归建立右子树 template <class T> void InThrBiTree :ThrBiTree ( ThrNode&l

31、t;T> *root )if ( root= NULL ) return;ThrBiTree ( root -> lchild ) ;if (!root-> Ichild ) /对root的左指针进行处理root->ltag=1;root-lchild=pre;设置pre的前驱线索if ( !root->rchild ) root->rtag=1; /对 root 的右指针进行处理if ( pre->rtag=1) pre-> rchild=root; /设置 pre 的后继线索 pre=root;ThrBiTree ( root->rch

32、ild) ;3 .哈夫曼树void HuffmanTree ( element huffTree , int w , int n ) for (i=0; i<2*n - 1; i+ ) huffTree i.parent= - 1;huffTree i.lchild= - 1;huffTree i.rchild= -1; for (i=0; i<n; i+ )huffTree i.weight=wi;for (k=n; k<2*n -1; k+) Select(h uffTree, i1, i2 ); huffTreei1.parent=k;/初始化/构造 n 棵只含有根结点

33、的二叉树/n- 1 次合并/在 huffTree 中找权值最小的两个结点 i1 和 i2/将 i1 和 i2 合并，则 i1 和 i2 的双亲是 khuffTreei2.parent=k;huffTreek.weight= huffTreei1.weight+huffTreei2.weight;huffTreek.lchild=i1;huffTreek.rchild=i2;注意问题1 注意理解有关树的各种递归算法的执行步骤。2注意字符类型数据在输入时的处理。3重点理解如何利用栈结构实现非递归算法。实验四 图的操作二、实验要求：1、掌握图的特点，利用图的邻接矩阵和邻接表的存储结构实现图的常见算法

34、。2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、 程序清单、调试情况、设计技巧、心得体会。三、实验内容：1. 设计无向图的邻接矩阵图类，实现如下操作：（1）实现邻接矩阵的构造，深度优先、广度优先遍历；（2）实现最小生成树算法；（3）实现最短路径算法；（4）设计主函数，输入数据，测试各算法。2. 设计有向图的邻接表类，实现深度优先非递归遍历、广度优先遍历和拓扑排序， 并设计主函数输入数据进行测试。*3.设计邻接表类，设计一个算法，输出图 G中从顶点u到顶点v的长度为I的所有 简单路径。四、程序样例： 请在下列邻接表和邻接矩阵的基础上自习添加其它任务1. 图的邻接表

35、类struct ArcNode/定义边表结点int adjvex; / 邻接点域ArcNode *next;tempIate <cIass T>struct VertexNode/定义顶点表结点T vertex;ArcNode *firstedge;const int MaxSize=10;/图的最大顶点数tempIate <cIass T>cIass ALGraphpubIic:ALGraph （T a , int n, int e ）;构造函数，初始化一个有 n个顶点e条边的图ALGraph;/析构函数，释放邻接表中各边表结点的存储空间T GetVex ( int

36、i) ; / 取图中第 i 个顶点数据信息void PutVex ( int i, T value ) ;/将图中第 i 个顶点的数据域置为 valuevoid InsertVex ( int i, T value ); /在图中插入一个顶点，其编号为 i ，值为 valuevoid DeleteV ex( int i);/删除图中第 i 个顶点void InsertArc ( int i, int j );/在图中插入一条边，其依附的两个顶点的编号为i 和 jvoid DeleteArc ( int i, int j ) ;/在图中删除一条边，其依附的两个顶点的编号为i 和 jvoid DF

37、STraverse ( int v) ;/深度优先遍历图void BFSTraverse ( int v) ;/广度优先遍历图private:VertexNode adjlistMaxSize;/存放顶点表的数组int vertexNum, arcNum;/图的顶点数和边数;2. 图的邻接矩阵类const int MaxSize=10;/图中最多顶点个数template <class T>class MGraphpublic:MGraph ( T a , int n, int e ); /构造函数，初始化具有 n 个顶点 e 条边的图 MGraph ( ) / 析构函数T GetV

38、ex ( int i);/取图中第 i 个顶点数据信息void PutVex ( int i, T value ) ;/将图中第 i 个顶点的数据域置为 valuevoid InsertVex ( int i, T value ); /在图中插入一个顶点，其编号为 i ，值为 valuevoid DeleteV ex( int i);/删除图中第 i 个顶点void InsertArc ( int i, int j );/在图中插入一条边，其依附的两个顶点的编号为i 和 jvoid DeleteArc ( int i, int j ) ;/ 在图中删除一条边，其依附的两个顶点的编号为i 和 j

39、void DFSTraverse ( int v) ;/深度优先遍历图void BFSTraverse ( int v) ;/ 广度优先遍历图private:T vertexMaxSize;/ 存放图中顶点的数组int arcMaxSizeMaxSize; /存放图中边的数组int vertexNum, arcNum;/ 图的顶点数和边数;注意问题1注意理解各算法实现时所采用的存储结构。2 注意区别正、逆邻接矩阵。实验类型：设计性实验要求：必修实验学时： 2 学时一、 实验目的：参照各种查找算法程序样例，实现查找的常见算法。实验五 查 找二、实验要求：1、掌握各种查找算法的特点，测试并验证查找

40、的常见算法。2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、 程序清单、调试情况、设计技巧、心得体会。三、实验内容：1. 建立有序表，采用折半查找实现某一已知的关键字的查找。2利用折半查找算法在一个有序表中插入一个元素，并保持表的有序性。3建立顺序表，统计表中重复元素个数。5. 根据给定的二叉排序树类的定义 , 验证二叉排序树的各个成员函数。4. 哈希表类设计。要求：(1) 哈希函数采用除留余数法，哈希冲突解决方法分别采用链地址法和线性探测法；(2) 各自设计一个测试程序进行侧试。注意问题1注意理解折半查找的适用条件(链表能否实现折半查找？)。2. 注意理解静态查

41、找、动态查找概念。3比较各种查找算法的各自特点，能够根据实际情况选择合适的查找方法。实验类型：设计性实验要求：必修实验学时： 2 学时一、 实验目的：利用各种排序算法，实现不同数据量时的排序算法所花时间的比较。实验六 排 序二、实验要求：1、设计 List 类，实现各种排序算法，并测试不同数据量时算法所花时间的比较。2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、 程序清单、调试情况、设计技巧、心得体会。三、实验内容：设计 List 类，实现以下任务1、构造函数随机生成一组关键字序列2 、实现简单选择排序、直接插入排序和冒泡排序。3 、实现希尔排序算法。4 、实现

42、快速排序算法（取第一个记录或中间记录作为基准记录） 。5 、实现堆排序算法。*6 、快速排序的非递归算法。*7 、实现折半插入排序。*8 、采用链式存储实现简单选择排序、直接插入排序和冒泡排序。*9 、双向起泡排序。在起泡排序中，若待排序序列为正序，只需一趟扫描，而待排序序 列为反序时，需进行 n-1 趟扫描。对于初始序列（ 94，10，12，18， 42，44，67）只需 扫描 2趟，而对于初始序列（ 12，18，42，44，67，94，10）就需扫描 6 趟。造成这种 不对称的原因：每趟扫描仅能使最小数据下沉一个位置，如果改变扫描方向， ，情况正 好相反，即每趟从后往前扫描，都能使当前无序

43、区中最大数据上浮一个位置。为了改变 上述两种情况下的不对称性，可以在排序过程中交替改变扫描方向，称之为双向起泡排 序。10、main 中定义类对象，设计一个菜单，实现测试各个排序所花时间。注意问题：注意理解各种算法的思想、 了解算法的适用情况及时间复杂度， 能够根据实际情况选择 合适的排序方法。随机函数 rand （），初始化随机发生器函数 srand（time（0）.实验七 综合实验实验类型：综合性实验要求：必修实验学时： 2 学时一、实验目的：通过该实验是学生能够综合数据结构所学的知识， 自行分析、 设计， 学会对一个实际问 题分析、综合、设计的能力。二、实验要求 1、掌握数据结构所学的内

44、容，分析给定实验内容并设计出程序，然后运行，同时分析 几种不同方法的效率。2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、 程序清单、调试情况、设计技巧、心得体会。三、实验内容：选作项目 1设计一个简单个人电话号码查询系统1. 问题描述： 人们在日常中经常要查找某个人或某个单位的电话号码， 本实验将实现一个简单的个人 电话号码查询系统，根据用户输入信息（例如姓名等）进行快速查询。2、基本要求 （1）在外存上，用文件保存电话号码信息；（ 2）在内存中，设计数据结构存储电话信息；（3）提供查询功能；根据姓名实现快速查询；（4）提供其他功能，例如插入、删除、修改等；3、

45、设计思想由于要管理的电话号码信息很多， 而且要在程序运行后仍然保存电话号码信息， 所以电 话号码信息采用文件的形式存放在外存上。 在系统运行时， 要将电话号码信息从文件调入内 存来进行查询等操作， 为了接收文件中内容， 要有一个数据结构与之对应， 可以设计如下结 构类型的数组来接收数据：const int max = 10struct TeleNumberString name;String phoneNumber;String mobileNumber;String email; Telemax;为了实现对电话号码的快速查询， 可以将上述结构数组排序， 以便应用折半查找， 但 数组中实现插入

46、和删除操作的代价较高。 如果记录频繁进行插入或删除操作， 可以考虑采用 二叉排序数组织电话号码信息， 则查询和维护都能获得较高的时间性能； 另外也可以考虑直 接使用哈希表表结构存储电话号码信息，请同学根据实际情况自己选择。4、详细分析采用几种不同方法实现的效率。选作项目 2利用单向链表，设计一个学生管理系统，能够实现学生信息管理及文件读写。 主要功能有学生信息录入，数据输出，基本信息查询（按学号、姓名） ，成绩查询，数据统 计，文件读写等。实验八 停车场管理实验类型：综合性 实验要求：必修 实验学时： 2 学时 【实验内容与要求】设停车场内只有一个可停放 n 辆汽车的狭长通道， 且只有一个大门可供汽车进出。 汽车 在停车场内按车辆到达时间的先后顺序， 依次由北向南排列 （大门在最南端， 最先到达的第 一辆车停放在车场的最北端） ，若车场内已停满 n 辆汽车，则后来的汽车只能在门外的便道 上等候，一旦有车开走，则排在便道上的第一辆车即可