数据结构实验指导书及答案(徐州工程学院)

《数据结构实验》实验指导书及答案信电工程学院计算机科学和技术教研室编2011.12数据结构实验所有代码整理作者郑涛声明：在这里我整理了数据结构实验的所有代码，希望能对大家的数据结构实验的考试有所帮助，大家可以有选择地浏览，特别针对一些重点知识需要加强记忆（ps:重点知识最好让孙天凯给出），希望大家能够在数据结构实验的考试中取得令人满意的成绩，如果有做的不好的地方请大家谅解并欢迎予以指正。

实验一熟悉编程环境实验预备知识：1．熟悉本课程的语言编译环境（TC或VC），能够用C语言编写完整的程序，并能够发现和改正错误。

2．能够灵活的编写C程序，并能够熟练输入C程序。

一、实验目的1．熟悉C语言编译环境，掌握C程序的编写、编译、运行和调试过程。

2．能够熟练的将C程序存储到指定位置。

二、实验环境⒈硬件：每个学生需配备计算机一台。

⒉软件：Windows操作系统+Turbo C；三、实验要求1．将实验中每个功能用一个函数实现。

2．每个输入前要有输入提示（如：请输入2个整数当中用空格分割：），每个输出数据都要求有内容说明（如：280和100的和是：380。

）。

3．函数名称和变量名称等用英文或英文简写（每个单词第一个字母大写）形式说明。

四、实验内容1．在自己的U盘中建立“姓名+学号”文件夹，并在该文件夹中创建“实验1”文件夹（以后每次实验分别创建对应的文件夹），本次实验的所有程序和数据都要求存储到本文件夹中（以后实验都按照本次要求）。

2．编写一个输入某个学生10门课程成绩的函数（10门课程成绩放到结构体数组中，结构体包括：课程编号，课程名称，课程成绩）。

3．编写一个求10门成绩中最高成绩的函数，输出最高成绩和对应的课程名称，如果有多个最高成绩，则每个最高成绩均输出。

4．编写一个求10门成绩平均成绩的函数。

5．编写函数求出比平均成绩高的所有课程及成绩。

#include<stdio.h>#include<conio.h>struct subject{int subject_id;char subject_name[20];double subject_grades;};struct subject sub[10];void input(){int i;printf("please input:\n");for(i=0;i<10;i++){scanf("%d %s %lf",&sub[i].subject_id,&sub[i].subject_name,&sub[i].subject_g rades);}printf("you just input:\n");for(i=0;i<3;i++){printf("%d %s %lf\n",sub[i].subject_id,sub[i].subject_name,sub[i].subject_g rades);}}void subject_max(){int i,flag;double max=sub[0].subject_grades;for(i=0;i<10;i++){if(sub[i].subject_grades>max)max=sub[i].subject_grades;flag=i;}printf("The high score of subjectis %s %lf\n",sub[flag].subject_name,max);}void subject_average(){int i;double average,sum=sub[0].subject_grades;for(i=1;i<10;i++){sum+=sub[i].subject_grades;}average=sum/10;printf("subject's average is %lf\n",average);}void subjct_gtaverage(){int i,flag;double average,sum=sub[0].subject_grades;for(i=1;i<10;i++){sum+=sub[i].subject_grades;}average=sum/10;for(i=0;i<10;i++){if(sub[i].subject_grades>average){flag=i;printf("subject greater than average is %s %lf\n",sub[flag].subject_name,sub[flag].subject_grades);}}}int main(){input();subject_max();subject_average();subjct_gtaverage();return 0;}实验二顺序表的基本操作实验预备知识：1．熟练运用数组进行程序设计，掌握数组名和指针作为函数参数。

第1章数据库系统概论三、简答题1. 答：数据库DB是长期存储在计算机内、有组织的、统一管理的相关数据的集合。

DB能为各种用户共享，具有较小冗余度、数据间联系紧密而又有较高的数据独立性等特点。

2. 答：数据库管理系统DBMS是位于用户与操作系统（OS）之间的一层数据管理软件，它为用户或应用程序提供访问DB的方法，包括DB的建立、查询、更新及各种数据控制。

DBMS 总是基于某种数据模型，可以分为层次型、网状型、关系型和面向对象型等。

3. 答：①数据定义语言及其翻译处理程序；②数据操纵语言及其编译（或解释）程序；③数据库运行控制程序；④实用程序。

4. 答：文件系统中的文件是面向应用的，一个文件基本上对应于一个应用程序，文件之间不存在联系，数据冗余大，数据共享性差，数据独立性差；数据库系统中的文件不再面向特定的某个或多个应用，而是面向整个应用系统，文件之间是相互联系的，减少了数据冗余，实现了数据共享，数据独立性高。

5. 答：①实现数据的集中化控制；②数据的冗余度小，易扩充；③采用一定的数据模型实现数据结构化；④避免了数据的不一致性；⑤实现数据共享；⑥提供数据库保护；⑦数据独立性；⑧数据由DBMS统一管理和控制。

6. 答：数据独立性是指数据库中的数据独立于应用程序，即数据的逻辑结构、存储结构与存取方式的改变不影响应用程序。

数据独立性一般分为数据的逻辑独立性和数据的物理独立性。

数据逻辑独立性是指数据库总体逻辑结构的改变（如修改数据定义、增加新的数据类型、改变数据间的联系等）不需要修改应用程序。

数据物理独立性是指数据的物理结构（存储结构、存取方式等）的改变，如存储设备的更换、物理存储格式和存取方式的改变等不影响数据库的逻辑结构，因而不会引起应用程序的改变。

7. 答：数据库系统中数据不是面向单个应用组织的，而是直接面向数据本身及数据间的内在联系来组织的，因此可以方便地供多用户多应用共享，这样，数据的冗余度就大幅度降低了。

数据结构实验报告答案数据结构实验报告答案引言：数据结构是计算机科学中的重要概念，它涉及组织和管理数据的方法和技术。

在本次实验中，我们将研究和实践几种常见的数据结构，包括数组、链表、栈和队列。

通过这些实验，我们将深入理解数据结构的原理和应用。

一、数组数组是一种线性数据结构，它由一系列相同类型的元素组成。

数组的特点是可以通过索引来访问和修改元素，具有随机访问的能力。

在本次实验中，我们将实现一个简单的数组类，并进行一些基本操作，如插入、删除和查找。

首先，我们定义一个数组类，包含以下成员变量和方法：- size：数组的大小- elements：存储元素的数组- insert(index, element)：在指定位置插入元素- remove(index)：删除指定位置的元素- get(index)：获取指定位置的元素- search(element)：查找元素在数组中的位置通过实现上述方法，我们可以对数组进行各种操作。

例如，我们可以在数组的末尾插入一个元素，然后在指定位置删除一个元素。

我们还可以通过元素的值来查找其在数组中的位置。

二、链表链表是另一种常见的线性数据结构，它由一系列节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。

链表的特点是插入和删除操作的效率较高，但随机访问的效率较低。

在本次实验中，我们将实现一个简单的单向链表，并进行一些基本操作。

首先，我们定义一个节点类，包含以下成员变量和方法：- data：节点的数据元素- next：指向下一个节点的指针然后，我们定义一个链表类，包含以下成员变量和方法：- head：链表的头节点- insert(element)：在链表的末尾插入一个节点- remove(element)：删除链表中指定的节点- search(element)：查找链表中指定元素的节点通过实现上述方法，我们可以对链表进行各种操作。

例如，我们可以在链表的末尾插入一个节点，然后删除链表中指定的节点。

数据结构习题解答信息工程学院徐燕萍第1章绪论一、基本内容数据、数据元素、数据对象、数据结构、存储结构和数据类型等概念术语的确定含义；抽象数据类型的定义、表示和实现方法；描述算法的类C语言；算法设计的基本要求以及从时间和空间角度分析算法的方法。

二、学习要点1．熟悉各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系。

分清哪些是逻辑结构的性质，哪些是存储结构的性质。

2．了解抽象数据类型的定义、表示和实现方法。

3．熟悉类C语言的书写规范，特别要注意值调用和引用调用的区别，输入、输出的方式以及错误处理方式。

4．理解算法五个要素的确切含义：①动态有穷性（能执行结束）；②确定性（对于相同的输入执行相同的路径）；③有输入；④有输出；⑤可行性（用以描述算法的操作都是足够基本的）。

5．掌握计算语句频度和估算算法时间复杂度的方法。

三、基础知识题1.1简述下列术语：数据、数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。

答：数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

数据对象是性质相同的数据元素的集合，是数据的一个子集。

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

存储结构是数据结构在计算机中的表示（又称映像）。

数据类型是一个值的集合和定义在这个值集上的一组操作的总称。

抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。

1.2试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。

答：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素。

数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。

程序设计语言中的数据类型是一个值的集合和定义在这个值集上的一组操作的总称。

而抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。

数据结构（第4版）习题及实验参考答案数据结构复习资料完整版（c语言版）数据结构基础及深入及考试习题及实验参考答案见附录结论1、数据的逻辑结构是指数据元素之间的逻辑关系。

即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。

2、数据的物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。

它依赖于计算机。

存储结构可分为4大类：顺序、链式、索引、散列3、抽象数据类型：由用户定义，用以表示应用问题的数据模型。

它由基本的数据类型构成，并包括一组相关的服务（或称操作）。

它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）。

4、算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。

5、在数据结构中，从逻辑上可以把数据结构分成（C）A、动态结构和表态结构B、紧凑结构和非紧凑结构C、线性结构和非线性结构D、内部结构和外部结构6、算法的时间复杂度取决于（A）A、问题的规模B、待处理数据的初态C、问题的规模和待处理数据的初态线性表1、线性表的存储结构包括顺序存储结构和链式存储结构两种。

2、表长为n的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均次数为（E），删除一个元素需要移动的元素的个数为（A）。

A、(n-1)/2B、nC、n+1D、n-1E、n/2F、(n+1)/2G、(n-2)/23、“线性表的逻辑顺序与存储顺序总是一致的。

”这个结论是（B）A、正确的B、错误的C、不一定，与具体的结构有关4、线性表采用链式存储结构时，要求内存中可用存储单元的地址（D）A、必须是连续的B、部分地址必须是连续的C一定是不连续的D连续或不连续都可以5、带头结点的单链表为空的判定条件是（B）A、head==NULLB、head->ne某t==NULLC、head->ne某t=headD、head!=NULL6、不带头结点的单链表head为空的判定条件是（A）A、head==NULLB、head->ne某t==NULLC、head->ne某t=headD、head!=NULL7、非空的循环单链表head的尾结点P满足（C）A、p->ne某t==NULLB、p==NULLC、p->ne某t==headD、p==head8、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（B）A、O(1)B、O(n)C、O(n2)D、O(nlog2n)数据结构(第4版）习题及实验参考答案9、在一个单链表中，若删除p所指结点的后继结点，则执行（A）A、p->ne某t=p->ne某t->ne某t;B、p=p->ne某t;p->ne某t=p->ne某t->ne某t;C、p->ne某t=p->ne某t;D、p=p->ne某t->ne某t;10、在一个单链表中，若在p所指结点之后插入所指结点，则执行（B）A、->ne某t=p;p->ne某t=;B、->ne某t=p->ne某t;p->ne某t=;C、->ne某t=p->ne某t;p=;D、p->ne某t=;->ne某t=p;11、在一个单链表中，已知q是p的前趋结点，若在q和p之间插入结点，则执行（C）A、->ne某t=p->ne某t;p->ne某t=;B、p->ne某t=->ne某t;->ne某t=p;C、q->ne某t=;->ne某t=p;D、p->ne某t=;->ne某t=q;12、在线性结构中，第一个结点没有前趋结点，其余每个结点有且只有1个前趋结点。

.实验九图的最小生成树算法的实现实验预备知识：1．理解图最小生成树的意义和相应算法。

2．掌握带权图的存储结构。

一、实验目的1．使学生熟悉最小生成树的算法实现。

2．掌握带权图的存储结构和处理方法。

二、实验环境⒈硬件：每个学生需配备计算机一台。

操作系统：DOS或 Windows；⒉软件： DOS或 Windows操作系统 +Turbo C；三、实验要求1．能够独立完成带权图的存储和最小生成树的生成四、实验内容1．在自己的 U盘的“姓名 +学号”文件夹中创建“实验 9”文件夹，本次实验的所有程序和数据都要求存储到本文件夹中。

2．现在某电信公司要对如下图的几个城市之间进行光纤连接布线，请用合适的存储结构将下图存储到计算机中方便进行处理。

3．现在公司想以最小的代价将所有城市连通，方便所有城市间通信，请用普里姆算法和克鲁斯卡尔算法实现本图的最小生成树#include <stdio.h>#include <stdlib.h>#define INF 50typedef struct ArcNode{int adjvex;// 该弧所指向的顶点位置struct ArcNode *nextarc;// 下一个临接点int weight;// 弧的权重}ArcNode;// 表结点typedef struct VNode{char data;// 顶点信息ArcNode *firstarc;// 指向下一个结点}VNode,AdjList[6];typedef struct{AdjList LH;// 创建头结点数组int vexnum;// 图的点的个数int arcnum;// 图的边的个数}Graph;typedef struct{char nextvex;int lowcost;int know;}Auxiliary_array;// 辅助数组结构体void main (void){void buildtu (Graph*);void printgraph(Graph*);void prim( Graph *G, char u);char u;Graph UDG;Graph *G = &UDG;buildtu(G);printgraph(G);// 打印图printf(" 请输入起始顶点：\n");while(getchar()!='\n');u = getchar();prim(G ,u);}void buildtu (Graph *G) {// 建图int search(Graph *G,char a);int i,n1,n2,w;char a,b;ArcNode *p, *q;printf(" 请输入顶点个数和边的条数：\n");scanf("%d %d",&G->vexnum,&G->arcnum);printf(" 请输入顶点信息\n");for (i = 0; i < G->vexnum; ++i){while (getchar()!='\n');scanf("%c",&G->LH[i].data);G->LH[i].firstarc = NULL;}printf(" 请输入有关系的结点和该边的权重:\n");for(i=0;i<G->arcnum;++i){while (getchar()!='\n');scanf("%c %c %d",&a,&b,&w);n1=search(G,a);n2=search(G,b);p=G->LH[n1].firstarc;if(p == NULL){p=G->LH[n1].firstarc=(ArcNode *) malloc (sizeof(ArcNode));}else{while( p->nextarc !=NULL ){p=p->nextarc;}p=p->nextarc=(ArcNode *) malloc (sizeof(ArcNode));}q=G->LH[n2].firstarc;if(q == NULL){q=G->LH[n2].firstarc=(ArcNode *) malloc (sizeof(ArcNode));}else{while( q->nextarc !=NULL ){q=q->nextarc;}q=q->nextarc=(ArcNode *) malloc (sizeof(ArcNode));}p->adjvex=n2;p->weight=w;p->nextarc=NULL;q->adjvex=n1;q->weight=w;q->nextarc=NULL;}}int search (Graph *G,char a){ // 确定顶点a 在头结点数组中的位置int i;for(i=0;i<G->vexnum;++i){if(G->LH[i].data==a){return i;}}}void printgraph(Graph *G){// 打印图int i;ArcNode *p;for (i=0 ; i < G->vexnum; ++i){p=G->LH[i].firstarc;printf("data:%c \t",G->LH[i].data);while(p!=NULL){printf("firstarc->adjvex=%d",p->adjvex);p=p->nextarc;}printf("\n");}}void prim( Graph *G, char u){// 用 prim 算法实现最小生成树int search (Graph *G,char a);int minimize(Graph *G, Auxiliary_array[]);void printtable(Auxiliary_array[]);Auxiliary_array A[6]; // 创建辅助数组int i,j,seat;int location;ArcNode *p ;for (i = 0; i < G->vexnum; ++i) {A[i].nextvex = '0';A[i].know = 0;A[i].lowcost = INF;}location = search(G ,u);// 确定 u 元素在头结点数组中的位置for (p=G->LH[location].firstarc ; p != NULL; p=p->nextarc ){i = p->adjvex;A[i].nextvex = G->LH[location].data;A[i].lowcost = p->weight;A[i].know= 0;}A[location].know = 1;A[location].lowcost = 0;A[location].nextvex = '0';for(j=0;j<G->vexnum-1;++j){seat = minimize( G,A );printf("select min: %d\n", seat);A[seat].know = 1;p=G->LH[seat].firstarc;for (p; p != NULL; p=p->nextarc){i=p->adjvex;if(A[i].know == 0 && p->weight < A[i].lowcost){A[i].nextvex = G->LH[seat].data;A[i].lowcost = p->weight;}}}printtable(A); //打印辅助数组中的信息for (j = 0; j < G->vexnum; ++j)if (j != location)printf("%c<---->%c\n",A[j].nextvex,G->LH[j].data);}int minimize(Graph *G, Auxiliary_array A[]){// 取出辅助数组中权值最小的顶点所在的位置int i,place,num;num = INF;for (i = 0; i < G->vexnum; ++i){if(A[i].know == 0 && num >= A[i].lowcost){num= A[i].lowcost;place = i;}}return place;}void printtable(Auxiliary_array A[]) {//打印辅助数组int i;for (i = 0; i < 6; i++) {printf("modifier:%c lowcost:%d known:%d\n",A[i].nextvex,A[i].lowcost, A[i].know);}}实验总结：通过该实验，我深刻明白到了自己对循环的能力不足，书写代码的逻辑性也不够强，相信在以后的学习中能加强这方面的学习，争取在以后的学习中解决这两个方面的问题。

《数据结构和算法》实验指导书郁松软件学院第一部分：《数据结构》实验步骤和实验报告规范一、《数据结构》实验步骤随着计算机性能的提高，它所面临的软件开发的复杂度也日趋增加，因此软件开发需要系统的方法。

一种常用的软件开发方法，是将软件开发过程分为分析、设计、实现和维护四个阶段。

虽然数据结构课程中的实习题的复杂度远不如实际中真正的软件系统，但为了培养一个软件工作者所应具备的科学工作的方法和作风，我们制订了如下所述完成实习的5个步骤：1、问题分析和任务定义通常，实验题目的陈述比较简洁，或者说有模棱两可的含义。

因此，在进行设计之前，首先应该充分地分析和理解问题，明确问题要求做什么，限制条件是什么。

注意：本步骤强调的是做什么，而不是怎么做。

对问题的描述应避开算法和所涉及的数据类型，而是对所需完成的任务作出明确的回答。

例如：输入数据的类型、值的范围以及输入的形式；输出数据的类型、值的范围及输出的形式；若是会话式的输入，则结束标志是什么，是否接受非法的输入，对非法输入的回答方式是什么等等。

这一步还应该为调试程序准备好测试数据，包括合法的输入数据和非法形式输入的数据。

2、数据类型和系统设计在设计这一步骤中需分逻辑设计和详细设计两步实现。

逻辑设计指的是，对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。

详细设计则为定义相应的存储结构并写出各过程和函数的伪码算法。

在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。

作为逻辑设计的结果，应写出每个抽象数据类型的定义（包括数据结构的描述和每个基本操作的规格说明），各个主要模块的算法，并画出模块之间的调用关系图。

详细设汁的结果是对数据结构和基本操作的规格说明作出进一步的求精，写出数据存储结构的类型定义，按照算法书写规范用类C语言写出过程或函数形式的算法框架。

引言概述正文内容
1.实验环境配置
1.1硬件要求
计算机硬件配置要求
操作系统要求
附加硬件设备要求（如虚拟机等）
1.2软件要求
编程语言要求（如C/C++、Java等）开发环境配置（如IDE、编译器等）1.3实验库和工具
实验需要使用的库文件和工具
如何获取和配置实验库和工具
2.实验内容介绍
2.1实验目标和背景
数据结构实验的作用和意义
实验背景和相关应用领域介绍
2.2实验概述
实验内容的大致流程和步骤
实验中可能遇到的问题和挑战
2.3实验要求
对学生实验流程和实验结果的要求
实验过程中需要注意的事项和技巧
3.实验步骤
3.1实验准备
配置实验环境
获取实验所需数据和文件
3.2实验具体步骤
根据实验要求将数据结构知识应用到具体问题中根据实验要求实现相应的算法和数据结构
3.3实验示例代码
提供示例代码以供学生参考和学习
解析示例代码中的关键步骤和实现细节
4.实验答案
4.1实验题目
实验题目及相关说明
确定实验的具体要求和目标
4.2实验答案解析
对实验答案的具体实现进行解析
对实验中可能遇到的问题和错误进行分析和解决4.3实验答案示例
提供实验答案的示例代码
解析实验答案中的关键实现步骤和说明
5.实验总结
5.1实验成果评估
对学生实验成果进行评估
分析实验结果的优点和不足
5.2实验心得
学生对本次实验的收获和感想
学生对未来实验的建议和展望
总结。

数据结构实验指导书数据结构实验指导书目录数据结构实验指导书 (1)目录 (1)实验指导书概述 (2)实验题目 (3)实验一单链表的插入、删除 (3)[实验目的] (3)[实验内容] (3)[测试数据] (3)[实现提示] (3)实验二栈及其应用 (5)[实验目的] (5)[实验内容] (5)[测试数据] (5)实验三二叉树的递归算法 (5)[实验目的] (5)[实验内容] (6)[测试数据] (6)实验四查找及排序算法的应用 (7)[实验目的] (7)[实验内容] (7)[测试数据] (7)实验指导书概述“数据结构”是计算机专业一门重要的专业技术基础课程，是一门关键性核心课程。

本课程系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了多种常用的查找和排序技术，并对其进行了性能分析和比较，内容非常丰富。

本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。

由于以下原因，使得掌握这门课程具有较大难度：∙内容多，时间短，给学习带来困难；∙贯穿全书的动态链表存储结构和递归技术是学习中的重点和难点；∙隐含在各部分的技术和方法丰富，也是学习的重点和难点；∙先修课程中所介绍的专业性知识不多，加大了学习难度。

由于数据结构课程的技术性与实践性，《数据结构课程实验》的设置十分必要。

为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所用到的一些技术。

数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法，如算法设计的构思方法，动态链表，算法的编码，递归技术，与特定问题相关的技术等，要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算法的设计。

在掌握基本算法的基础上，掌握分析、解决实际问题的能力。

通过实验实践内容的训练，突出构造性思维训练的特征, 提高学生组织数据及编写大型程序的能力。

数据结构( Java 版) 习题解答与实验指导目录第1 章绪论11.1 数据结构的基本概念11.2 算法2第2 章线性表32.1 线性表抽象数据类型32.2 线性表的顺序存储和实现42.2.1 线性表的顺序存储结构42.2.2 顺序表52.2.3 排序顺序表72.3 线性表的链式存储和实现92.3.1 单链表9【习题2-8】单链表结点类问题讨论。

9【习2.1 ]使用单链表求解Josephu环问题。

12【习2.2】集合并运算，单链表深拷贝的应用。

142.3.2 双链表16【习2.3] 循环双链表的迭代方法。

19【习2.4] 循环双链表合并连接。

19第3 章串213.1 串抽象数据类型213.2 串的存储和实现223.2.1 串的存储结构223.2.2 常量字符串类22【习3.1 ] C/C++语言，str in g.h 中的strcpy()和strcat()函数存在下标越界错误。

22【思考题3-1】逆转String串，分析算法效率。

24【实验题3-1】MyString 类，比较串大小，忽略字母大小写。

25【例3.2思考题3-2] Mylnteger整数类，返回value的radix进制原码字符串。

26【实验题3-9] 浮点数类。

273.2.3 变量字符串类30【实验题3-11]删除变量串中的所有空格。

4-样卷303.3 串的模式匹配313.3.1 Brute-Force模式匹配算法313.3.2 模式匹配应用32【思考题3-4，实验题3-13 ] MyString 类，replaceAII(pattern,s)改错。

323.3.3 KMP模式匹配算法33第4 章栈和队列364.1 栈364.2 队列384.3 递归41【习4.1 】打印数字塔。

41第5 章数组和广义表435.1 数组435.2 特殊矩阵的压缩存储445.2.1 三角矩阵、对称矩阵和对角矩阵的压缩存储445.2.2 稀疏矩阵的压缩存储465.3 广义表48第6 章树和二叉树496.2 二叉树496.3 线索二叉树566.4 Huffman 树616.5 树的表示和实现62第7 章图637.1 图及其抽象数据类型637.2 图的表示和实现647.3 图的遍历657.4最小生成树677.5最短路径69 第8章查找728.1查找的基本概念728.2二分法查找738.4散列748.5二叉排序树7676【实验8-1】判断一棵二叉树是否为二叉排序树，改错。

《数据结构实验指导书》答案实验一：1、请编写函数int fun(int *a, int *b),函数的功能是判断两个指针a和b所指存储单元的值的符号是否相同；若相同函数返回1，否则返回0。

这两个存储单元中的值都不为0。

在主函数中输入2个整数、调用函数fun、输出结果。

#include <stdio.h>int fun(int *a, int *b){if (*a*(*b)>0) return(1);else return(0);}main(){int x,y;scanf("%d%d",&x,&y);if (fun(&x,&y)) printf("yes\n");else printf("no");}2、计算1+2+3+……+100，要求用指针进行设计。

即设计函数int fun(int *n)实现求1+2+3+……+*n，在主函数中输入、调用、输出结果。

#include <stdio.h>int fun(int *n){int i,sum=0;for (i=1;i<=*n;i++)sum+=i;return(sum);}main(){int x,sum;scanf("%d",&x);printf("the sum is %d\n",fun(&x));}3、函数的功能是求数组a中最大数的位置（位序号）。

在主函数中输入10个整数、调用函数fun、输出结果。

#define N 10#include <stdio.h>void input(int *a,int n){int i;for (i=0;i<n;i++)scanf("%d",a+i); /*scanf("%d",&a[i]);*/ }int fun(int *a,int n){int i,*max;max=a;for (i=1;i<n;i++)if (a[i]>*max) max=a+i;return(max-a);}main(){int a[N],maxi;input(a,N);maxi=fun(a,N);printf("\n the max position is %d\n",maxi);4、请编写函数fun(int *a,int n, int *odd, int *even),函数的功能是分别求出数组a中所有奇数之和和所有偶数之和。

实验一：以单链表表示集合，设计算法建立先后输入的两个集合的差。

说明：已知两个集合A和B，集合A-B中包含所有属于集合A而不属于集合B 的元素。

步骤：1.首先建立A和B的单链表2.然后对集合B中的每个元素x，在A中查找，若存在和x相同的元素，则从该链表中删除。

3.打印A-B，进行验证。

实验二：建立一个二叉树，并进行先序和中序遍历。

（递归和非递归算法）步骤1.补充元素0建立一个满二叉树，存储到一维数组2.利用递归算法建立二叉树，注意零的元素处置3．进行递归、非递归的中序和先序遍历。

打印结果。

实验三：先从键盘输入26个字母生成无序数组，对数组排序后，再从键盘输入一个字符进行折半查找。

实验四：为一个图（maxnode＝20）建立一个邻接表、编写深度遍历和广度遍历算法并给出遍历结果。

实验一答案：#include<stdio.h>typedef struct linknode{int data;struct linknode *next;} node;node *creatlist(){node *head,*r,*s;int x;head=(node*)malloc(sizeof(node));r=head;printf("input int and end with \n");scanf("%d",&x);while(x!=0){s=(node*)malloc(sizeof(node));s->data=x;r->next=s;s->next=NULL;r=s;scanf("%d",&x);}r->next=NULL;s=head;head=head->next;free(s);return(head);}void subs(){node *p,*p1,*p2,*q,*heada,*headb;heada=creatlist();headb=creatlist();p=heada;p1=p;while(p!=NULL){q=headb;while(q->data!=p->data && q!=NULL) q=q->next; if(q!=NULL){if(p==heada){heada=heada->next;p1=heada;}else if(p->next==NULL) p1->next=NULL;else p1->next=p->next;p2=p->next;p->next=NULL;free(p);p=p2;}else{p1=p;p=p->next;}}p=heada;if(p==NULL)printf("kong\n");elseprintf(" A - B \n");while(p!=NULL){printf("%d\n",p->data);p=p->next;}}main(){subs();}实验二答案：//程序目的建立二叉树，同时对他进行先序排列。

北京林业大学实验任务书备注：实验共分4次，其中实验1――实验3为设计性实验，实验4为综合性实验，具体安排下面一一列出。

北京林业大学09学年—10学年第 2学期数据结构实验任务书专业名称：实验学时： 4课程名称：数据结构任课教师：李冬梅实验题目：线性表的基本操作实验环境： Visual C++实验目的：1、掌握线性表的定义；2、掌握线性表的基本操作，如建立、查找、插入和删除等。

实验内容：定义一个包含学生信息（学号，姓名，成绩）的的顺序表和链表，使其具有如下功能：(1) 根据指定学生个数，逐个输入学生信息；(2) 逐个显示学生表中所有学生的相关信息；(3) 根据姓名进行查找，返回此学生的学号和成绩；(4) 根据指定的位置可返回相应的学生信息（学号，姓名，成绩）；(5) 给定一个学生信息，插入到表中指定的位置；(6) 删除指定位置的学生记录；(7) 统计表中学生个数。

实验提示：学生信息的定义：typedef struct {char no[8]; //8位学号char name[20]; //姓名int price; //成绩}Student;顺序表的定义typedef struct {Student *elem; //指向数据元素的基地址int length; //线性表的当前长度}SqList；链表的定义：typedef struct LNode{Student data; //数据域struct LNode *next; //指针域}LNode,*LinkList;实验要求：(1) 程序要添加适当的注释，程序的书写要采用缩进格式。

(2) 程序要具在一定的健壮性，即当输入数据非法时，程序也能适当地做出反应，如插入删除时指定的位置不对等等。

(3) 程序要做到界面友好，在程序运行时用户可以根据相应的提示信息进行操作。

(4) 根据实验报告模板详细书写实验报告,在实验报告中给出链表根据姓名进行查找的算法和插入算法的流程图。

徐州工程学院管理学院实验报告实验课程名称：数据结构与算法实验地点：经济管理实验中心年月至年月专业信息管理与信息系统班级学生姓名学号指导老师实验报告实验项目：线性表及其应用实验学时： 2实验日期：实验要求：熟悉并掌握单链表的存储及基本算法的使用实验内容：单链表就地逆置代码如下：#include<stdio.h>#include<stdlib.h>typedef struct LNode{int data;struct LNode *next;}LNode, *LinkList;LNode *p106,*head106;LNode *s106,*l106,*d106;int n;int m=sizeof(LNode);void ListCreate(){int i106;head106=(LinkList)malloc(m);p106=head106;for(i106=1;i106<5;i106++){p106->data=i106;p106->next=(LinkList)malloc(m);p106=p106->next;}p106->data=5;p106->next=NULL;}void ListOutput(){p106=head106;while(p106->next!=NULL){printf("%d",p106->data);p106=p106->next;}printf("%d\n",p106->data);}void ListChange(){LNode *q106,*l106;p106=head106;l106=p106->next;while(l106!=NULL){q106=l106->next;l106->next=p106;p106=l106;l106=q106;}head106->next=NULL;head106=p106;}void ListFinal(){p106=head106;while(p106->next!=NULL){printf("%d",p106->data);p106=p106->next;}printf("%d\n",p106->data);}int main(){ListCreate();ListOutput();ListChange();ListFinal();getch();}运行结果如下：实验项目：栈的应用实验学时： 2实验日期：实验要求：熟悉并掌握利用栈的特性进行相关运算实验内容：：双向栈的应用代码如下：#include <stdio.h>#include <stdlib.h>#include <malloc.h>#define OK 1#define ERROR 0#define OVERFLOW -1typedef int Elemtype;typedef struct{ int *base[2]; int *top[2];}*BDStacktype;Init_BDStack(BDStacktype tws,int m)｛(*tws).base[0]=(Elemtype*)malloc(m*sizeof(Elemtype)); (*tws).base[1]=(*tws).base[0]+((m-1)*sizeof(Elemtype)); (*tws).top[0]=(*tws).base[0];(*tws).top[1]=(*tws).base[1];return OK;}push(BDStacktype tws,int i106,Elemtype x) {if((*tws).top[0]>(*tws).top[1]) return OVERFLOW;if(i106==0) *(*tws).top[0]++=x;else if(i106==1){ if((*tws).top[1]==(*tws).base[1]) return OVERFLOW;*x=*++(*tws).top[1];}else return ERROR;return OK; }printBDStack(BDStacktype tws)｛Elemtype *p;p=(*tws).base[0];printf("Now the 0 Stack is:");Elemtype *p;p=(*tws).base[0];printf("Now the 0 Stack is:");while(p!=(*tws).top[0])printf("%d",*p++);printf("\n");p=(*tws).base[1];printf("Now the 1 Stack is:");while(p!=(*tws).top[1])printf("%d",*p--);printf("\n");}void main(){int m=0; int t=0,n;Elemtype *e; int i106;BDStacktype s;printf("Input the size of BDStack :");scanf("%d",m);Init_BDStack(s,m);printf("Input the total num of push:");scanf("%d",&t);for(i106=1;i106<t+1;i106++){printf("Input the %dth stack No.and data of push:",i);scanf("%d,%d",&n,e);push(s,n,*e); }printBDStack(s);printf("Input the stack No. which you will pop:");scanf("%d",&n);pop(s,n,e);printf("Pop the %dth stack,the num is:%d\n",n,*e);printBDStack(s);printf("\n");getch();}(2)结果实验项目：数组的应用实验学时：4实验日期：实验要求：熟悉并掌握矩阵压缩存储的算法实验内容：矩阵压缩存储代码如下：#include<stdlib.h>typedef int ElemType;#define MAXSIZE 100typedef struct{int i,j;ElemType e;}Triple;typedef struct{Triple data[MAXSIZE+1];int mu106,nu,tu;}TSMatrix;int CreateSMatrix(TSMatrix *M){int i,m,n;ElemType e;int k;printf("hang,lie,feiling geshu:\n");scanf("%d,%d,%d",&(*M).mu106,&(*M).nu,&(*M).tu);(*M).data[0].i=0;for(i = 1; i <= (*M).tu; i++){do{printf("%dgefeilingyuansuozaide hang(1-%d), lie(1-%d),yuansuzhi:\n", i,(*M).mu106,(*M).nu);scanf("%d,%d,%d",&m,&n,&e);k=0;if(m < 1 || m > (*M).mu106|| n < 1 || n > (*M).nu)k=1;if(m <(*M).data[i-1].i || m ==(*M).data[i-1].i && n <= (*M).data[i-1].j) k=1;}while(k);(*M).data[i].i = m;(*M).data[i].j = n;(*M).data[i].e = e;}(*M).data[i].i = m;(*M).data[i].j = n;(*M).data[i].e = e;}return 1;}void PrintSMatrix(TSMatrix M){int x,y,z;int k;for(x=1;x<=M.mu106;x++){for(y=1;y<=M.nu;y++){k=0;for(z=1;z<=M.tu;z++){if((M.data[z].i==x) && (M.data[z].j==y)){ printf("%4d",M.data[z].e);k=1;}}if(k==0){printf("%4d",k);}}printf("\n");}}int main(){TSMatrix A;CreateSMatrix(&A);PrintSMatrix(A);getch();}（2）结果：实验项目：树的应用实验学时：2实验日期：实验要求：熟悉并掌握建立树及利用二叉树遍历算法进行其他操作实验内容：二叉树的叶子结点计算代码如下：#include "stdio.h"#include "conio.h"typedef struct Node{char data;struct Node *lchild,*rchild;}BiTNode;crt_bt_pre106(){BiTNode *T;char ch;printf("ch==");scanf("%c",&ch);if(ch==' ')T=NULL;else{T=(BiTNode*) malloc (sizeof(BiTNode));T->data=ch;T->lchild=crt_bt_pre106(T->lchild);T->rchild=crt_bt_pre106(T->rchild);}return T;}void preorder106 (BiTNode *T){if(T!=NULL){printf("%c",T->data);preorder106(T->lchild);preorder106(T->rchild);}}int leafCount106(BiTNode *T){if(!T) return 0;else if (!T->lchild && !T->rchild) return 1;else return leafCount106(T->lchild) + leafCount106(T->rchild); }void main(){BiTNode *root;printf("creat erchashu:");root=crt_bt_pre106();printf("\n");printf("preorder:");printf("\n");preorder106(root);printf("\n");printf("count is %d\n",leafCount106(root));getch();}(2)结果：实验项目：图的应用实验学时：2实验日期：实验要求：熟悉并掌握图的构造算法的使用实验内容：有向图的邻接表存储代码如下：#include "stdio.h"typedef struct e_node{ int adjvex;struct e_node *next ;}E_NODE;E_NODE *q106;E_NODE *p106;typedef struct v_node{ int vertex;E_NODE *link;}V_NODE;V_NODE head[20];void creat_adj_list(V_NODE head[], int t, int n) {int i106;int e106;int w106;int v106;w106=1,v106=1;for(i106=1;i106<=n;i106++){ head[i106].link=NULL;head[i106].vertex=i106;}printf("the sidenumber is: e=");scanf("%d",&e106);for(i106=1;i106<=e106;i106++){printf("v=");scanf("%d",&v106);printf("w=");scanf("%d",&w106);if((v106<=n)&&(w106<=n)){if(t==1){p106=(E_NODE *)malloc(sizeof(E_NODE));p106->adjvex=w106;p106->next=head[v106].link;head[v106].link=p106;}if(t==0){ p106=(E_NODE *)malloc(sizeof(E_NODE));p106->adjvex=v106;p106->next=head[w106].link;head[w106].link=p106;}}}printf("the content : \n");for(i106=1;i106<=n;i106++){q106=head[i106].link;printf("the number %d vertex =>",i106); while(q106!=NULL){printf("%d",q106->adjvex);q106=q106->link;}printf("\n");}}void main(){int t;int n;printf("t=");scanf("%d",&t);printf("the number of vertex :");scanf("%d",&n);creat_adj_list(head,t,n);getch();}结果:实验项目：查找和排序算法应用实验学时： 4实验日期：实验要求：熟悉并掌握查找和排序算法的使用实验内容：对某字符串进行排序，并在此基础上利用查找算法进行查找代码如下：#include "stdio.h"typedef struct {char key;}create;create st[26];void build(){printf("please input the letters:");gets(st);}void change(){int t106;int i106;int j106;for(j106=0;j106<25;j106++){for(i106=0;i106<25-j106;i106++){if(st[i106].key>st[i106+1].key){t106=st[i106].key;st[i106].key=st[i106+1].key;st[i106+1].key=t106;}}}printf("the right order is:");for(i106=0;i106<26;i106++){printf("%c",st[i106]);}}int binsrch(create st[],char k){int low,high,mid, found;low=0; high=25; found=0;while((low<=high) &&(found==0)){mid=(low+high)/2;if(k>st[mid].key) low=mid+1;else if(k==st[mid].key) found=1; else high=mid-1;}if(found==1) return(mid);else return(-1);}int main(){int n;char k;build();change();printf("\nthe letter needed found is:"); scanf("%c",&k);n=binsrch(st,k);printf("the location is: %d",n+1);getch();}（2）结果：。

《数据结构》实验指导第一章实验0 C/C++程序设计一、实验基础知识二、实验案例1 学生成绩统计系统[问题描述]一个班同学的学号为1-n，输入n位同学的学号、姓名、语文、数学、英语等3门课程成绩，统计每位同学的总分后按成绩从高到低的次序输出。

[基本要求]实现成绩表的录入、总分统计、总分排序和输出。

[测试数据]对于10个同学的学号、姓名、语文、数学、英语等3门课程成绩设计实例数据[实现提示]1）用结构体设计同学记录，学号、各课程成绩和总分数据域用整型，姓名域采用字符数组；学生成绩表用数组模拟，数组大小根据实际学生数动态申请；学生成绩统计系统通过主菜单形式提供成绩表初始化、学生成绩录入、学生总分统计和排名、成绩表输出等功能。

[提高部分]1）实现成绩表的文件录入和文件保存2）实现成绩键盘录入的有效数据限制2复数计算器[问题描述]设计一个能进行复数运算的演示程序。

[基本要求]实现复数的基本运算：1）由输入的实部和虚部生成一个复数；2）求两个复数的和；3）求两个复数的差；4）求两个复数的乘积；5）求复数的实部；6）求复数的虚部[测试数据]0+0=03.1,0;4.22,8.9;输出7.32+i8.99,8;-9,8;输出i169,-8;-9,-8;输出-i16-9,8;-9,-8;输出-189,-7;-9,8;输出i9,-9;-9,8;输出-i[实现提示]将复数的实部和虚部组成结构体数据类型，利用实数的操作实现复数的操作。

[提高部分]1）实现复数的除法运算；2）求共轭复数3有理数计算器[问题描述]设计一个能进行有理数运算的演示程序。

[基本要求]实现有理数的基本运算：1）由输入的分子和分母生成一个有理数；2）求两个有理数的和；3）求两个有理数的差；4）求两个有理数的乘积；5）求有理数的分子；6）求有理数的分母[实现提示]将有理数的分子和分母组成结构体数据类型，利用整数的操作实现有理数的操作。

[提高部分]1）实现有理数的除法运算；第二章线性表一、实验基础知识二、实验案例4顺序表基本操作演示系统[问题描述]设计一个能进行顺序表基本运算的演示程序。

第5章数据库设计一、单项选择题1.C2.B3.D4.D5.C6.A7.D8.D9.A 10.B11.C 12.D 13.D 14.B 15.A 16.A 17.B18.A二、填空题1. 需求分析概念结构设计逻辑结构设计物理结构设计数据库实施运行与维护2. 属性冲突命名冲突结构冲突3. 数据项4. 实体属性实体间的联系5. 数据流的起点或终点数据存储数据处理数据流三、简答题1. 答：这里只概要列出数据库设计过程的六个阶段：（1）需求分析;（2）概念结构设计;（3）逻辑结构设计;（4）数据库物理设计;（5）数据库实施;（6）数据库运行和维护。

这是一个完整的实际数据库及其应用系统的设计过程。

不仅包括设计数据库本身,还包括数据库的实施、运行和维护。

设计一个完善的数据库应用系统往往是上述六个阶段的不断反复。

2. 答：各阶段的设计要点如下：（1）需求分析：准确了解与分析用户需求(包括数据与处理)。

（2）概念结构设计：通过对用户需求进行综合、归纳与抽象,形成一个独立于具体DBMS的概念模型。

（3）逻辑结构设计：将概念结构转换为某个DBMS所支持的数据模型,并对其进行优化。

（4）数据库物理设计：为逻辑数据模型选取一个最适合应用环境的物理结构(包括存储结构和存取方法)。

（5）数据库实施：设计人员运用DBMS提供的数据语言、工具及宿主语言,根据逻辑设计和物理设计的结果建立数据库,编制与调试应用程序,组织数据入库,并进行试运行。

（6）数据库运行和维护：在数据库系统运行过程中对其进行评价、调整与修改。

3. 答：数据库结构设计的不同阶段形成数据库的各级模式,即：（1）在概念设计阶段形成独立于机器特点,独立于各个DBMS产品的概念模式,在本篇中就是E-R图；（2）在逻辑设计阶段将E-R图转换成具体的数据库产品支持的数据模型,如关系模型,形成数据库逻辑模式,然后在基本表的基础上再建立必要的视图(View),形成数据的外模式；（3）在物理设计阶段,根据DBMS特点和处理的需要,进行物理存储安排,建立索引,形成数据库内模式。