数据结构大作业

南昌大学实验报告实验名称:线性表的顺序存储实现及链式存储实现学生姓名：学号：80023120 专业班级：电子商务121班实验类型：□验证□综合□设计□创新实验目的1.熟悉掌握线性表的两种存储实现方式。

2.熟悉掌握线性表的两种存储实现方式下的一些基本操作。

试验内容1.写出顺序表的class和一些关于顺序表的操作函数。

2.写出单链表的class和一些关于单链表的操作函数。

3.写出双向链表的class和一些关于双向链表的操作函数。

4.测试类中实现的操作函数。

实验步骤1、顺序表类是指采用顺序存储结构来表示线性表的类。

线性表采用顺序存储结构，其数组和线性表长可以作为类的数据成员。

创建一个类const int MAXSIZE=100; //数组的容量最大值为100class SqList{ private:ElemType elem[MAXSIZE]; //数组int length; //线性表长public:SqList( void); //构造函数~SqList(){ }; //析构函数void Creat() ; //初建一个简表函数void PrintOut(); //输出线性表函数void Insert( int i, ElemType e); //插入函数ElemType Delet(int i); //删除函数};//类定义结束{ cout<<"\n Input length="; cin>>length;cout<<"\n Input Data:\n" ;for(int k=0; k<length;k++) cin>>elem[k];}void SqList::PrintOut() //输出线性表函数{cout<<"\n length="<<length ;cout<<"\n PrintOut Data:\n" ;for(int k=0; k<length;k++) cout<<setw(6)<<elem[k];cout<<endl;}2、单链表：假设一个线性表有n个元素，则这n个元素所对应的n个节点就通过指针（是计算机内某个存储单元的地址）链接成一个链表由于这种链表中每个节点只有一个指针域，故称为单链表。

则关键字为49的地址为。

9）数据结构被形式地定义为（D, R），其中D是的有限集合，R是D上的有限集合。

10）一个算法的效率分为效率和效率。

3、应用题1）编写算法,将一个头指针为head不带头结点的单链表改造为一个单向循环链表，并分析算法的时间复杂度。

2）已知二叉树的先序遍历序列为ABCDEFGH，中序遍历序列为CBEDFAGH，画出二叉树。

然后写出该二叉树的后序遍历序列。

3）试用权集合{12,4,5,6,1,2}构造哈夫曼树，并计算哈夫曼树的带权路径长度。

4）已知图G如下所示，根据Prim算法，构造最小生成树。

（要求给出生成过程）5）设哈希表HT表长m为13，哈希函数为H(k)=k MOD m，给定的关键值序列为{19,14,23,10,68,20,84,27,55,11}。

试求出用线性探测法解决冲突时所构造的哈希表，并求出在等概率的情况下查找成功的平均查找长度ASL。

二、大作业要求大作业共需要完成22道题：第1大题必做，满分30分；第2大题必做，满分30分；第3大题选作2题，满分40分。

答卷提交要求：考试题提前公布，学生下载试题和答题卷后，在答题卷上答题。

完成后需网上提交答卷。

答卷于11月20日－－12月6日通过点击页面左侧导航栏内“我的考试”－“课程论文/大作业”提交。

1、选择题1) C 2) C 3) D 4) A 5) C6) C 7) B 8) D 9) A 10) A2、填空题1) l==l->next2)栈顶3)三元组顺序表十字链表。

4)LOC (A[0][0])+(n*i+j)*k5)R[2i+1]6) 先序遍历7)n-18)99) 数据元素关系10)时间效率空间效率3、应用题2）已知二叉树的先序遍历序列为ABCDEFGH，中序遍历序列为CBEDFAGH，画出二叉树。

然后写出该二叉树的后序遍历序列。

答：后序遍历序列CEFDBHGA3）试用权集合{12,4,5,6,1,2}构造哈夫曼树，并计算哈夫曼树的带权路径长度。

数据结构大作业一、大作业的性质和目的数据结构大作业是对软件设计的综合训练，包括问题分析、总体设计、用户界面设计、程序设计基本技能和技巧，以至一套软件工作规范的训练和科学作风的培养。

在数据结构实验中，完成的只是单一而“小”的算法，而本课程设计是对学生的整体编程能力的锻炼。

数据结构大作业的目的是训练学生对问题的抽象能力和算法的运用能力。

二、大作业安排每位同学独立完成，可自选题目或根据选择后面的一个参考题目来完成。

开学第一周统一提交到教学在线。

提交的内容包括：(1)设计报告文档。

该文档是评分的重要依据之一，请认真对待。

该文档包括如下内容：●需求分析： (陈述要解决的问题，要实现的功能),●详细设计：包括设计算法流程图、算法分析、使用的数据结构（要求详细论证）；●软件测试：包括测试数据和测试结果记录●总结：设计过程中遇到的问题及解决方法；尚未解决的问题及考虑应对的策略；收获和心得；(2)源代码。

要求注释清晰，编写规范，模块化。

(3)可运行的exe文件。

要求充分测试，在XP操作系统中能正常运行。

以上内容打包后提交到教学在线。

三、考核和成绩评定老师根据设计文档、源代码和可执行文件，进行判分。

对于出现以下情况的学生，要求统一进行答辩：●执行文件无法正常运行。

●源程序疑似抄袭。

如果有发现两个同学的代码相类似则需要共同出席答辩。

如果判定抄袭，则为不及格。

开发过程可以部分复用网上的开源代码，但必须体现自己的工作，如果没有自己工作的部分，同样判为抄袭。

五、题目（任选其中之一或自拟）1. 数字化校园（1）设计华南理工大学的校园平面图，至少包括10个以上的地点，每两个地点间可以有不同的路，且路长可能不同。

以图中顶点表示校内各地点，存放名称、代号、简介等信息；用边表示路径，存放路径长度等相关信息。

（2）提供图中任意地点相关信息的查询。

（3）提供图中任意地点的问路查询，即查询任意两个地点之间的一条最短路径。

（4）学校要新建一间超市，请为超市选址，实现总体最优。

数据结构一、选择题1．数据的存储结构是指（ ）。

A 存储在外存中的数据 B 数据所占的存储空间C 数据在计算机中的顺序存储方式D 数据的逻辑结构在计算机中的表示 2．下列关于栈的描述中错误的是（ ）。

A 栈是先进后出的线性表B 栈只能顺序存储C 栈具有记忆作用D 对栈的插入与删除操作中，不需要改变栈底指针 3．用链表表示线性表的优点是（ ）。

A 便于随机存取B 花费的存储空间较顺序存储少C 便于插入和删除操作D 数据元素的物理顺序与逻辑顺序相同 4．在下面关于线性表的叙述中，选出正确的一项（ ）。

A 线性表的每个元素都有一个直接前驱和直接后继；B 线性表中至少要有一个元素；C 线性表中的元素必须按递增或递减的顺序排列；D 除第一个元素和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。

5．设在栈中，由顶向下已存放元素c b a ，在第4个元素d 入栈前，栈中元素可以出栈，试问d 入栈后，不可能的出栈序列是 ( )。

A d c b a B c b d aC c a d bD c d b a6．在下列关于二叉树的叙述中，选出正确的一项（ ）。

A 在二叉树中，任何一个结点的度都是2；B 二叉树的度为2；C 在二叉树中至少有一个结点的度是2D 一棵二叉树的度可以小于27．下面的二叉树中，（ ）不是完全二叉树。

8．有一棵非空的二叉树（第0层为根结点），其第i 层上至多有多少个结点 ( )。

A 2iB 2i-1C 2i+1D i9．线性表的逻辑顺序与存储顺序总是一致的，这种说法 ( )。

A 正确B 不正确10．深度为k 的二叉树，所含叶子的个数最多为 ( )。

A 2KB KC 2k-1D 2k-111．深度为5的二叉树至多有（ ）个结点。

A 16B 32C 31D 1012．在下面关于线性表的叙述中，选出错误的一项（ ）。

A 采用顺序存储的线性表，必须占用一片连续的存储单元B 采用顺序存储的线性表，便于进行插入和删除操作C 采用链接存储的线性表，不必占用一片连续的存储单元D 采用链接存储的线性表，便于进行插入和删除操作13．已知一棵二叉树的前序遍历结果为ABCDEF ，中序遍历结果为CBAEDF ，则后序遍历的结果为（ ）。

数据结构作业（1）年级：2004级（2）班专业：计算机科学与技术专业学号：200431500066姓名：秦博纯病人看病模拟程序编写一个程序，反映病人到医院看病，排队看医生的情况。

在病人排队过程中，主要重复两件事：1.病人到达诊室，将病历本交给护士，排到等待队列中候诊。

2.护士从等待队列中取出下一们病人的病历，该病人进入人诊室就诊。

要求模拟病人等待这一过程，程序采用菜单方式，其选项及功能说明如下：a.排队——输入排队病人的病历号，加入病人排队队列中;b.就诊——病人排队队列中最前面的病人就诊，并将其从队列中删除;c.查看排队——从队首到队尾列出所有的排队病人的病历号;d.不再排队，余下依次就诊——从队首到队尾列出所有的排队病人的病历号，并退出运行;e.下班——退出运行。

解：本项目的组成结构如图1所示，本程序的模块结构图如图2所示，图中方框表示函数，方框中指出函数名，箭头方向表示函数间的调用关系，虚线方框表示文件的组成，即指出该虚线方框中的函数存放在哪个文件中。

文件包含如下函数:. SeeDoctor():模拟病人看病的过程。

病人排队看医生，所以要用到一个队列，这里设计了一个不带头结点的单链表作为队列。

源程序如下：图1 项目组成#include<stdio.h>#include<malloc.h>typedef struct qnode{int data;struct qnode *next;}QNode;typedef struct{QNode *front,*rear;}QuType; 图2 项目的程序结构图void SeeDoctor(){int sel,flag=1,find,no;QuType *qu;QNode *p;qu=(QuType *)malloc(sizeof(QuType)); /*创建空队*/qu->front=qu->rear=NULL;while(flag==1) /*循环执行*/{printf("1:排队2：就诊3：查看排队4：不再排队，余下依次就诊5：下班请选择");scanf("%d",&sel);switch(sel){case 1:printf(">>输入病历号：");do{scanf("%d",&no);find=0;p=qu->front;while(p!=NULL&&!find){if(p->data==no)find=1;elsep=p->next;}if(find)printf(">>输入的病历号重复，重新输入：");}while(find==1);p=(QNode *)malloc(sizeof(QNode)); /*创建结点*/p->data=no;p->next=NULL;if(qu->rear==NULL) /*第一个病人排队*/ {qu->front=qu->rear=p;}else{qu->rear->next=p; /*将*p结点入队*/qu->rear=p;}break;case 2: /*队空*/ if(qu->front==NULL)printf(">>没有排队的病人!\n");else /*队不空*/{p=qu->front;printf(">>病人%d就诊\n",p->data);if(qu->rear==p) /*只有一个病人排队*/{qu->front=qu->rear=NULL;}elsequ->front=p->next;free(p);}break;case 3: /*队空*/ if(qu->front==NULL)printf(">>没有排列的病人!\n");else /*队不空*/{p=qu->front;printf(">>排队病人: ");while(p!=NULL){printf("%d ",p->data);p=p->next;}printf("\n");}break;case 4: /*队空*/ if(qu->front==NULL)printf(">>没有排队的病人!\n");else /*队不空*/{p=qu->front;printf(">>病人按以下顺序就诊: ");while(p!=NULL){printf("%d ",p->data);p=p->next;}printf("\n");}flag=0; /*退出*/break;case 5: /*队不空*/ if(qu->front!=NULL)printf(">>请排队的病人明天就医!\n");flag=0; /*退出*/break;}}}void main(){SeeDoctor();}程序运行结果如下：。

数据结构大作业在计算机科学领域中，数据结构是非常重要的一个概念。

它是指组织和存储数据的方式，以及对数据进行操作的方法。

数据结构的选择与实现直接影响着算法的复杂度和程序的性能。

因此，在学习数据结构的过程中，一般都会有相应的大作业，以帮助学生更好地理解和应用所学的知识。

本篇文章将重点介绍数据结构大作业的一般要求和一种可能的实现方案，供读者参考。

一、数据结构大作业要求数据结构大作业一般旨在让学生将所学的数据结构知识应用于实际问题的解决。

作业要求通常包括以下几个方面：1. 题目选择：作业题目需要涵盖数据结构的各个方面，例如链表、栈、队列、树、图等等。

题目应具备一定的难度，能够考察学生对数据结构的理解和运用能力。

2. 实现方式：学生需要根据题目要求选择合适的数据结构和算法，并进行实现。

一般要求使用编程语言来完成实现，并给出相应的代码。

3. 功能要求：作业题目通常会要求实现某些特定的功能或解决某些问题。

学生需要确保所实现的程序能够满足这些功能需求，并能正确运行。

4. 性能评估：作业可能会要求对所实现的程序进行性能评估，比如时间复杂度、空间复杂度等。

学生需要能够分析和解释程序的性能，并对可能的改进方法进行讨论。

5. 报告撰写：作业一般要求学生完成一份报告，对所实现的程序进行详细的说明和分析。

报告需要包括程序设计思路、实现细节、运行结果以及遇到的问题和解决方法等。

二、数据结构大作业实现方案示例以下是一个可能的数据结构大作业实现方案示例，以一个简化的社交网络系统为题目：1. 题目描述：设计一个基于图的社交网络系统，能够实现用户的注册、好友关系的建立和查询、用户之间的消息传递等功能。

2. 数据结构选择：可以使用图的数据结构来存储用户和好友关系的信息，使用链表来存储用户的消息队列。

3. 算法实现：根据题目要求，需要实现用户注册、好友关系的建立和查询、消息传递等功能的算法。

可以使用深度优先搜索或广度优先搜索算法来查找用户的好友关系，使用链表来实现用户消息的发送和接收。

《数据结构》大作业
数据结构是计算机科学中构建可靠计算机系统所必需的基础知识。

它主要是用来处理
非常大的量级的数据，并为用户快速访问，高效的解决计算机问题。

由于中央处理机的特
点是高速而有效，起到了极大的性能提升。

数据结构有很多不同的结构，其中最重要的是线性结构和非线性结构。

线性结构又可
以分为数组、单向链表、双向链表和循环链表；非线性结构可以分为二叉树、二叉搜索树、B树、堆、红黑树和图。

在实际计算机程序中，数据结构一般被用来搜索和排序存储的数据，这些操作有助于
提高计算机的运行效率。

如果用户想要查找某一个数据，可以在合适的存储结构中找到它；如果用户希望把一系列数据按照某种顺序排列起来，也可以使用数据结构进行排序。

同时数据结构还可以用于实现数据结构间的转换，使得用户可以较为方便的获得数据。

它的运用，更加方便了计算机的工作，更加提高了计算机的性能。

总之，数据结构是计算机科学中重要的组成部分，它为计算机的工作提供了重要的基础，更加方便了用户的操作，也帮助用户更好地完成计算机系统中的各种工作和解决方案。

数据结构大作业平衡二叉树是一种特殊的二叉树结构，在插入或删除节点时，通过旋转操作来保持树的平衡性，从而提高查找、插入或删除操作的效率。

平衡二叉树的一种常见实现方式是AVL树。

AVL树是由俄罗斯数学家Adelson-Velsky和Landis于1962年提出的，它是一种自平衡的二叉树。

在AVL树中，每个节点的左右子树的高度之差（也称为平衡因子）不超过1、当插入或删除节点后导致一些节点的平衡因子超过1时，就需要通过旋转操作进行平衡调整。

具体来说，插入节点时，需要首先将节点插入到AVL树的合适位置。

然后，自底向上地检查每个节点的平衡因子。

如果发现一些节点的平衡因子超过1，则需要进行相应的旋转操作，使树重新恢复平衡。

旋转操作有四种基本情况，分别是LL、RR、LR和RL旋转。

LL旋转发生在一些节点的左子树的左子树上，RR旋转发生在一些节点的右子树的右子树上，LR旋转发生在一些节点的左子树的右子树上，RL旋转发生在一些节点的右子树的左子树上。

通过这些旋转操作，可以使树重新平衡。

删除节点时，需要先找到待删除的节点，并根据其子树的情况进行删除操作。

然后，从被删除节点的父节点向上检查每个节点的平衡因子，如果发现不平衡的节点，也需要进行相应的旋转操作。

AVL树的平衡调整是通过旋转操作来实现的，旋转操作的时间复杂度为O(1)，因此平衡调整的时间复杂度为O(logn)，其中n为树的节点数。

平衡二叉树的优点是能够保持树的平衡性，提高查找、插入、删除等操作的效率。

总结起来，平衡二叉树是一种特殊的二叉树，通过旋转操作来保持树的平衡性，从而提高查找、插入或删除操作的效率。

AVL树是一种常见的平衡二叉树实现方式，通过LL、RR、LR和RL旋转来使树重新平衡。

平衡二叉树的优点是能够保持树的平衡性，提高操作的效率。

浙江工商大学计算机与信息工程学院数据结构实验大作业报告专业：班级：学号：姓名：指导教师：年月一、大作业报告内容包括以下几个部分⒈问题描述：(题目)⒉设计：⑴数据结构设计和核心算法设计描述；⑵主控及功能模块层次结构；⑶主要功能模块的输入、处理(算法框架描述)和输出；⑷功能模块之间的调用与被调用关系等。

⒊测试：测试范例，测试结果，测试结果的分析与讨论，测试过程中遇到的主要问题及所采用的解决措施。

⒋使用说明和作业小结：⑴使用说明主要描述如何使用你的程序以及使用时的主要事项；⑵在小结中说明程序的改进思想、经验和体会；⒌整理一份程序清单及运行示例的结果。

将以上各项文字材料及程序清单等装订成册，形成一个完整的报告。

题目从以下题目中任选一个，每人1个题目。

（一）试设计一个航空客运定票系统。

基本要求如下：1、每条航线所涉及的信息有：终点站名、航班号、飞机号、飞机周日（星期几）、乘员定额、余票量、订定票的客户名单（包括姓名、订票量、舱位等级1，2或3）以及等候替补的客户名单（包括姓名、所需数量）。

2、系统能实现的操作和功能如下：1）查询航线：根据客户提出的终点站名输出如下信息：航班号、飞机号、星期几飞行，最近一天航班的日期和余票额；2）承办订票业务：根据客户提出的要求（航班号、订票数额）查询该航班票额情况，若有余票，则为客户办理订票手续，输出座位号；若已满员或余票少余订票额，则需重新询问客户要求。

若需要，可登记排队候补；3）承办退票业务：根据客户提出的情况（日期、航班号），为客户办理退票手续，然后查询该航班是否有人排队候补，首先询问排在第一的客户，若所退票额能满足他的要求，则为他办理订票手续，否则依次询问其它排队候补的客户。

3、实现提示：两个客户名单可分别由线性表和队列实现。

为查找方便，已订票客户的线性表应按客户姓名有序，并且，为了插入和删除方便，应以链表作为存储结构。

由于预约人数无法预计，队列也应以链表作为存储结构。

课程设计（数据结构）一、题目的目的和要求1.设计目的巩固和加深对数据结构的理解，通过上机实验、调试程序，加深对课本知识的理解，最终使学生能够熟练应用数据结构的知识写程序。

（1）通过本课程的学习，能熟练掌握几种基本数据结构的基本操作。

（2）能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的正确求解过程并编写代码实现。

2.设计题目要求设计内容：本系统应完成以下几方面的功能：学生信息的建立：create()；学生信息的插入：insert()；学生信息的查询：search()；学生信息的修改：change()；学生信息的删除：delete()；学生信息的输出：print()。

设计要求：（1）每条记录至少包含：姓名（name ）、（xuehao）,(kemu),(chengji)属性。

（2）作为一个完整的系统，应具有友好的界面和较强的容错能力（3）程序能正常运行，并写出课程设计报告二、设计进度及完成情况三、主要参考文献及资料[1] 叶核亚编著. 数据结构（Java版）（第3版）. 北京：电子工业出版社，2011[2] 施平安等译. JAVA程序设计教程（第5版）. 北京：清华大学出版社，2007[3] Java相关资料四、成绩评定设计成绩：（教师填写）指导老师：（签字）目录第一章系统概述 (1)第二章系统分析 (1)第三章系统设计 (1)第四章系统实现 (10)第五章系统运行与测试 (11)第六章总结与心得 .............................................. 错误！未定义书签。

参考文献 ................................................................ 错误！未定义书签。

第一章系统概述在这次的课程设计中我们选择的题目是：学生信息系统,能够添加、删除、查询联系人等。

由于自己的知识有限，程序可能不是太完美，但是我会认真对待，尽自己最大女里去完成此次任务！！！第二章系统分析学生信息系统主要用于帮助用户保存学生信息，方便用户查询联系人的相关信息。