大学数据结构上机实验题二
实验报告
一、实验目的
1、掌握堆栈的顺序存储结构
2、掌握顺序栈的基本运算和堆栈的应用
3、掌握队列的链式存储结构和基本运算
二、实验环境
PC微机，Windows， Visual C++
三、实验内容
1、堆栈的建立及基本运算
（1）问题描述
堆栈采用顺序存储，基本的操作包括初始化栈、入栈、出栈、显示栈中元素、判断栈满等。
（2）基本要求
每个运算要求用一个函数实现。
（3）算法描述
利用堆栈，实现数制转换运算（例如将十进制数转换为八进制）。首先定义一个数制转换函数，在该函数中创建一个堆栈，然后读入用户指定的待转换的值N，并将其入栈。求N 模8的余数，将余数入栈，所得的商继续做模8的运算，直到余数为0。将余数出栈，得到转换的八进制数。
（4）算法实现——示例程序
定义头文件
#define MAXSIZE 100
typedef int Elemtype;
typedef struct
{
Elemtype stack[MAXSIZE];
int top;
}Sstack;
主文件
#include
#include
#include
#include "hehe.h"
void initiate(Sstack *L)//初始化一个栈
{//initiate a stack
L->top=0;
return;
}
int stackIsEmpty(Sstack *L)//判断栈是否为空，若为空返回1，否则返回0
{//determine an empty stack
if(L->top==0)
return 1;
else
return 0;
}
int push(Sstack *L, Elemtype x)//入栈运算：若栈已满提示并返回值0，否则将元素入栈并返回值1
{//push element x into stack
if(L->top>=MAXSIZE-1)
{
printf("栈已满,不能完成入栈运算！\n");
return 0;
}
L->top++;
L->stack[L->top]=x;
return 1;
}
Elemtype pop(Sstack *L)//出栈运算：若栈为空提示并返回0，否则出栈一个元素并返回该元素的值
{//pop an element
Elemtype a;
if(L->top<=0)
{
printf("栈为空,不能完成出栈运算！\n");
return 0;
}
a=L->stack[L->top];
L->top--;
return a;
}
Elemtype getTop(Sstack *L)//读取并返回栈顶元素的值
{//get the top element
Elemtype a;
if(L->top<=0)
{
printf("栈已空，不能完成取栈运算！\n");
return 0;
}
a=L->stack[L->top];
return 1;
}
void conversion()//数制转换
{
Sstack *L;
int e;
L=(Sstack *) malloc (sizeof(Sstack));//为L申请栈空间
initiate(L);//初始化栈L
int N;
printf("Please input a number to be converted\n");
scanf("%d",&N);
while(N)//当N不等于0
{
push(L, N%8);
N=N/8;
}
printf("The number converted into octal form is\n");//输出转换后的八进制数while(!stackIsEmpty(L)){
e=pop(L);
printf("%d",e);
}
printf("\n");
}
void main()//主函数
{
conversion();
}
2、链式队列的建立和基本运算
（1）问题描述
队列采用链式存储，基本的操作包括初始化队列、入队、出队、判断队满等。（2）基本要求
队列的每个运算用一个函数实现。
（3）算法描述
参见教材62页的参考算法。
（4）算法实现
头文件
typedef int ElemType;
typedef struct Node {
ElemType data;
struct Node *next;
}Lnode; //节点类型
typedef struct Qu
{
Lnode *front;
Lnode *rear;
} Queue;//队列类型
主文件
#include
#include
#include
#include
#include "hehe.h"
Queue * Initiate_queue()//初始化队列
{
Queue *que;//队列的指针
Lnode *qhead;//队列的节点
que=(Queue *)malloc(sizeof(Queue));//队列的指针分配空间
qhead=(Lnode *)malloc(sizeof(Lnode));//队列的头节点
qhead->data=-1;
qhead->next=NULL;
que->front=qhead;//将头节点插入队列
que->rear=qhead;
return que;//返回队列的指针
}
int Queue_empty (Queue *queue)//判断队列是否为空，为空返回1，否则返回0 {
if (queue->front->next==NULL)
return 1;
else
return 0;
}
void En_queue(Queue *queue, int node_seq)//入队
{
Lnode *newnode;
newnode=(Lnode *)malloc(sizeof(Lnode));
newnode->data=node_seq;
newnode->next=NULL;//元素入队
queue->rear->next=newnode;
queue->rear=newnode;
}
int De_queue(Queue *queue)//出队一个节点，返回其值{
Lnode *de_node;
int seq;
if(Queue_empty(queue)==1)//判断队列是否为空
{
printf("The queue is empty! Cannot dequeue");
return -1;
}
else//出队一个元素
{
de_node=queue->front->next;
queue->front->next=de_node->next;
if (queue->front->next==NULL)
queue->rear=queue->front;
seq=de_node->data;
//cout<<"node "< free(de_node); return seq; } } void displayQueue(Queue *queue)//显示从队头到队尾的元素{ Lnode *current; current=queue->front->next; printf("The queue is\n"); while(current!=NULL) { printf("%d\t",current->data); current=current->next; } printf("\n"); } void main()//主函数 { Queue *Q; int i; Q=Initiate_queue(); int qa; printf("Please input 5 elements\n"); for(i=0;i<5;i++) { scanf("%d",&qa); En_queue(Q,qa); } displayQueue(Q); De_queue(Q); printf("One element dequeue, and the queue is\n"); displayQueue(Q); } 数据结构上机实验报告 学院：电子工程学院 专业：信息对抗技术 姓名： 学号： 教师：饶鲜日期： 目录 实验一线性表................................................. - 4 - 一、实验目的................................................ - 4 - 二、实验代码................................................ - 4 - 三、实验结果............................................... - 14 - 四、个人思路............................................... - 15 -实验二栈和队列.............................................. - 15 - 一、实验目的............................................... - 15 - 二、实验代码............................................... - 16 - 三、实验结果............................................... - 24 - 四、个人思路............................................... - 25 -实验三数组.................................................. - 26 - 一、实验目的............................................... - 26 - 二、实验代码............................................... - 26 - 三、实验结果............................................... - 28 - 四、个人思路............................................... - 28 -实验四树.................................................... - 29 - 一、实验目的............................................... - 29 - 二、实验代码............................................... - 29 - 《数据结构课程实验》大纲 一、《数据结构课程实验》的地位与作用 “数据结构”是计算机专业一门重要的专业技术基础课程，是计算机专业的一门核心的关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了常用的多种查找和排序技术，并做了性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因，使得掌握这门课程具有较大的难度： （1）内容丰富，学习量大，给学习带来困难； （2）贯穿全书的动态链表存储结构和递归技术是学习中的重点也是难点； （3）所用到的技术多，而在此之前的各门课程中所介绍的专业性知识又不多，因而加大了学习难度； （4）隐含在各部分的技术和方法丰富，也是学习的重点和难点。 根据《数据结构课程》课程本身的技术特性，设置《数据结构课程实验》实践环节十分重要。通过实验实践内容的训练，突出构造性思维训练的特征, 目的是提高学生组织数据及编写大型程序的能力。实验学时为18。 二、《数据结构课程实验》的目的和要求 不少学生在解答习题尤其是算法设计题时，觉得无从下手，做起来特别费劲。实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。 为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所用到的一些技术。数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法，如算法设计的构思方法，动态链表，算法的编码，递归技术，与特定问题相关的技术等，要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算法的设计。在掌握基本算法的基础上，掌握分析、解决实际问题的能力。 三、《数据结构课程实验》内容 课程实验共18学时，要求完成以下六个题目： 实习一约瑟夫环问题（2学时） 数据结构实验指导书 一、实验目的 《数据结构》是计算机学科一门重要的专业基础课程，也是计算机学科的一门核心课程。本课程较为系统地论述了软件设计中常用的数据结构以及相应的存储结构与实现算法，并做了相应的性能分析和比较，课程内容丰富，理论系统。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因，使得掌握这门课程具有较大的难度： 1）理论艰深，方法灵活，给学习带来困难； 2）内容丰富，涉及的知识较多，学习有一定的难度； 3）侧重于知识的实际应用，要求学生有较好的思维以及较强的分析和解决问题的能力，因而加大了学习的难度； 根据《数据结构》课程本身的特性，通过实验实践内容的训练，突出构造性思维训练的特征，目的是提高学生分析问题，组织数据及设计大型软件的能力。 课程上机实验的目的，不仅仅是验证教材和讲课的内容，检查自己所编的程序是否正确，课程安排的上机实验的目的可以概括为如下几个方面： （1）加深对课堂讲授内容的理解 实验是对学生的一种全面综合训练。是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常，实验题中的问题比平时的习题复杂得多，也更接近实际。实验着眼于原理与应用的结合点，使学生学会如何把书上学到的知识用于解决实际问题，培养软件工作所需要的动手能力；另一方面，能使书上的知识变" 活" ，起到深化理解和灵活掌握教学内容的目的。 不少学生在解答习题尤其是算法设计时，觉得无从下手。实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出 现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。 (2) 培养学生软件设计的综合能力 平时的练习较偏重于如何编写功能单一的" 小" 算法，而实验题是软件设计的综合训练，包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧，多人合作，以至一整套软件工作规范的训练和科学作风的培养。 通过实验使学生不仅能够深化理解教学内容，进一步提高灵活运用数据结构、算法和程序设计技术的能力，而且可以在需求分析、总体结构设计、算法设计、程序设计、上机操作及程序调试等基本技能方面受到综合训练。实验着眼于原理与应用的结合点，使学生学会如何把书本上和课堂上学到的知识用于解决实际问题，从而培养计算机软件工作所需要的动手能力。 (3) 熟悉程序开发环境，学习上机调试程序一个程序从编辑，编译，连接到运行，都要在一定的外部操作环境下才能进行。所谓" 环境" 就是所用的计算机系统硬件，软件条件，只有学会使用这些环境，才能进行 程序开发工作。通过上机实验，熟练地掌握程序的开发环境，为以后真正编写计算机程序解决实际问题打下基础。同时，在今后遇到其它开发环境时就会触类旁通，很快掌握新系统的使用。 完成程序的编写，决不意味着万事大吉。你认为万无一失的程序，实际上机运行时可能不断出现麻烦。如编译程序检测出一大堆语法错误。有时程序本身不存在语法错误，也能够顺利运行，但是运行结果显然是错误的。开发环境所提供的编译系统无法发现这种程序逻辑错误，只能靠自己的上机经验分析判断错误所在。程序的调试是一个技巧性很强的工作，尽快掌握程序调试方法是非常重要的。分析问题，选择算法，编好程序，只能说完成一半工作，另一半工作就是调试程序，运行程序并得到正确结果。 二、实验要求 常用的软件开发方法，是将软件开发过程划分为分析、设计、实现和维护四个阶段。虽然数据结构课程中的实验题目的远不如从实际问题中的复杂程度度高，但为了培养一个软件工作者所应具备的科学工作的方法和作风，也应遵循以下五个步骤来完成实验题目： 1) 问题分析和任务定义 在进行设计之前，首先应该充分地分析和理解问题，明确问题要求做什么?限制条件是什么。本步骤强调的是做什么?而不是怎么做。对问题的描述应避开算法和所涉及的数据类型，而是对所需完成的任务作出明确的回答。例如：输入数据的类型、值的范围以及输入的 华农数据结构上机实验答案 数据结构上机答案 1.1顺序线性表的基本操作 #include { newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*size of(ElemType)); L.elem=newbase; L.listsize+=LISTINCREMENT; } q=&(L.elem[i-1]); for(p=&(L.elem[L.length-1]);p>=q;--p) *(p+1)=*p; *q=e; ++L.length; return OK; } int ListDelete_Sq(SqList &L,int i,int &e) { ElemType *q,*p; if(i<1||i>L.length) return ERROR; p=&(L.elem[i-1]); e=*p; q=L.elem+L.length-1; for(++p;p<=q;p++) *(p-1)=*p; L.length--; return OK; } int main() { SqList T; int a,i; ElemType e,x; if(InitList_Sq(T)) { printf("A Sequence List Has Created.\n"); } while(1) { printf("1:Insert element\n2:Delete element\n3:Load all elements\n0:Exit\nPlease choose:\n"); scanf("%d",&a); switch(a) 数据结构实验报告全集 实验一线性表基本操作和简单程序 1．实验目的 （1）掌握使用Visual C++ 6.0上机调试程序的基本方法； （2）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2．实验要求 （1）认真阅读和掌握和本实验相关的教材内容。 （2）认真阅读和掌握本章相关内容的程序。 （3）上机运行程序。 （4）保存和打印出程序的运行结果，并结合程序进行分析。 （5）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include iostream.h>//头文件 #include nodetype *create()//建立单链表，由用户输入各结点data域之值，//以0表示输入结束 { elemtype d;//定义数据元素d nodetype *h=NULL,*s,*t;//定义结点指针 int i=1; cout<<"建立一个单链表"< 数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include 上机实验要求及规范 《数据结构》课程具有比较强的理论性，同时也具有较强的可应用性和实践性，因此上机实验是一个重要的教学环节。一般情况下学生能够重视实验环节，对于编写程序上机练习具有一定的积极性，但是容易忽略实验的总结，忽略实验报告的撰写。对于一名大学生必须严格训练分析总结能力、书面表达能力。需要逐步培养书写科学实验报告以及科技论文的能力。拿到一个题目，一般不要急于编程，而是应该按照面向过程的程序设计思路（关于面向对象的训练将在其它后继课程中进行），首先理解问题，明确给定的条件和要求解决的问题，然后按照自顶向下，逐步求精，分而治之的策略，逐一地解决子问题。具体步骤如下： 1.问题分析与系统结构设计 充分地分析和理解问题本身，弄清要求做什么（而不是怎么做），限制条件是什么。按照以数据结构为中心的原则划分模块，搞清数据的逻辑结构（是线性表还是树、图？），确定数据的存储结构（是顺序结构还是链表结构？），然后设计有关操作的函数。在每个函数模块中，要综合考虑系统功能，使系统结构清晰、合理、简单和易于调试。最后写出每个模块的算法头和规格说明，列出模块之间的调用关系（可以用图表示），便完成了系统结构设计。 2.详细设计和编码 详细设计是对函数（模块）的进一步求精，用伪高级语言（如类C语言）或自然语言写出算法框架，这时不必确定很多结构和变量。 编码，即程序设计，是对详细设计结果的进一步求精，即用某种高级语言（如C/C++语言）表达出来。尽量多设一些注释语句，清晰易懂。尽量临时增加一些输出语句，便于差错矫正，在程序成功后再删去它们。 3.上机准备 熟悉高级语言用法，如C语言。熟悉机器（即操作系统），基本的常用命令。静态检查主要有两条路径，一是用一组测试数据手工执行程序（或分模块进行）；二是通过阅读或给别人讲解自己的程序而深入全面地理解程序逻辑，在这个过程中再加入一些注释和断言。如果程序中逻辑概念清楚，后者将比前者有效。 4.上机调试程序 调试最好分块进行，自底向上，即先调试底层函数，必要时可以另写一个调用驱动程序，表面上的麻烦工作可以大大降低调试时所面临的复杂性，提高工作效率。 5.整理实验报告 在上机实验开始之前要充分准备实验数据，在上机实践过程中要及时记录实验数据，在上机实践完成之后必须及时总结分析，写出实验报告。 数据结构实验报告 一．顺序表 要求：实现顺序表的初始化、在指定位置插入和删除元素。 算法思路：线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。顺序表的初始化操作就是为顺序表分配一个预定义大小的空间，并将线性表的当前长度设为“0”。线性表的插入操作是在线性表的第i-1个数据元素和第i个元素之间插入新的数据元素，使得长度为n的线性表变成长度为n+1的线性表，而删除恰好相反长度变为n-1的线性表，而且删除点后面的元素要往前移动一个位。 程序代码： #include for(i=0;i 数据结构上机实验题目 实验一线性表的顺序存储结构 实验学时 2学时 背景知识:顺序表的插入、删除及应用。 目的要求： 1．掌握顺序存储结构的特点。 2．掌握顺序存储结构的常见算法。 实验容 1．输入一组整型元素序列，建立顺序表。 2．实现该顺序表的遍历。 3．在该顺序表中进行顺序查找某一元素,查找成功返回1,否则返回0。4．判断该顺序表中元素是否对称,对称返回1,否则返回0。 5．实现把该表中所有奇数排在偶数之前,即表的前面为奇数,后面为偶数。 6．输入整型元素序列利用有序表插入算法建立一个有序表。 7．利用算法6建立两个非递减有序表并把它们合并成一个非递减有序表。 8. 利用该顺序结构实现循环队列的入队、出队操作。 8．编写一个主函数,调试上述算法。 #include #define OVERFLOW 0 #define MAXSIZE 100 typedef int ElemType; typedef struct list {ElemType elem[MAXSIZE]; int length; }Sqlist; void Creatlist(Sqlist &L) {int i; printf("请输入顺序表的长度："); //输入一组整型元素序列，建立一个顺序表。 scanf("%d",&L.length); for(i=0;i 班级：：学号： 实验一线性表的基本操作 一、实验目的 1、掌握线性表的定义； 2、掌握线性表的基本操作，如建立、查找、插入和删除等。 二、实验容 定义一个包含学生信息（学号，，成绩）的顺序表和链表（二选一），使其具有如下功能： (1) 根据指定学生个数，逐个输入学生信息； (2) 逐个显示学生表中所有学生的相关信息； (3) 根据进行查找，返回此学生的学号和成绩； (4) 根据指定的位置可返回相应的学生信息（学号，，成绩）； (5) 给定一个学生信息，插入到表中指定的位置； (6) 删除指定位置的学生记录； (7) 统计表中学生个数。 三、实验环境 Visual C++ 四、程序分析与实验结果 #include typedef int Status; // 定义函数返回值类型 typedef struct { char num[10]; // 学号 char name[20]; // double grade; // 成绩 }student; typedef student ElemType; typedef struct LNode { ElemType data; // 数据域 struct LNode *next; //指针域 }LNode,*LinkList; Status InitList(LinkList &L) // 构造空链表L { L=(struct LNode*)malloc(sizeof(struct LNode)); L->next=NULL; return OK; 2009级数据结构实验报告 实验名称：约瑟夫问题 学生姓名：李凯 班级：21班 班内序号：06 学号：09210609 日期：2010年11月5日 1．实验要求 1）功能描述：有n个人围城一个圆圈，给任意一个正整数m，从第一个人开始依次报数，数到m时则第m个人出列，重复进行，直到所有人均出列为止。请输出n个人的出列顺序。 2）输入描述：从源文件中读取。 输出描述：依次从显示屏上输出出列顺序。 2. 程序分析 1）存储结构的选择 单循环链表 2）链表的ADT定义 ADT List{ 数据对象：D={a i|a i∈ElemSet,i=1,2,3,…n,n≧0} 数据关系：R={< a i-1, a i>| a i-1 ,a i∈D,i=1,2,3,4….,n} 基本操作： ListInit(&L)；//构造一个空的单链表表L ListEmpty(L); //判断单链表L是否是空表，若是，则返回1，否则返回0. ListLength(L); //求单链表L的长度 GetElem（L，i）；//返回链表L中第i个数据元素的值； ListSort(LinkList [内容要求] 1、存储结构：顺序表、单链表或其他存储结构，需要画示意图，可参考书上P59 页图2-9 2.2 关键算法分析 结点类： template 《数据结构》课程上机实验指导书 实验一 【实验名称】顺序表的基本算法 【实验目的】 创建一个顺序表，掌握线性表顺序存储的特点。设计和验证顺序表的查找、插入、删除算法。 【实验要求】 （1）从键盘读入一组整数，按输入顺序形成顺序表。并将创建好的顺序表元素依次打印在屏幕上。 设计一个带选择菜单的主函数，菜单中具备任意选择删除、插入、查找数据元素（2）的功能。 当选择删除功能时，从键盘读入欲删除的元素位置或元素值，按指定方式删除；3（）当选择插入功能时，从键盘读入新元素值和被插入位置，在指定位置插入；当选择查找功能时，从键盘读入欲查找的元素值，返回其位置序号。 （4）每种操作结束后，都能在屏幕上打印出此时顺序表元素的遍历结果。 【实验步骤】、实验前先写好算法。1 上机编写程序。2、编译。3、调试。4、 综合实例！，2-62-8！带菜单的主函数参考书上2.5，，，书上参考算法例程：2-12-42-5注意：顺序表的结构体！typedef struct { datatype items[listsize]; int length; }SpList; 实验二 【实验名称】单链表的基本算法 【实验目的】 创建一个单链表，掌握线性表链式存储的特点。设计和验证链表的查找、插入、删除、求表长的算法。【实验要求】 （1）从键盘读入一组整数，按输入顺序形成单链表。并将创建好的单链表元素依次打印在屏幕上。（注意：选择头插法或者尾插法！） 设计一个带选择功能菜单的主函数，菜单中至少具备任意选择删除、插入、查找（2）数据元素，和求单链表表长等几项功能。 当选择删除功能时，从键盘读入欲删除的元素位置，按指定位置删除；当选择插）（3入功能时，从键盘读入新元素值和被插入位置，在指定位置插入；当选择查找功能时，从键盘读入欲查找的元素值，返回其位置序号；当选择求表长功能时，返回该单链表表长的数值。 （4）每种操作结束后，都能在屏幕上打印出此时单链表元素的遍历结果。 【实验步骤】、实验前先写好算法。1 、上机编写程序。2 编译。3、调试。4、 综合实例！！带菜单的主函数参考书上，2-132-15，2-172.5，，书上参考算法例程：2-102-12 另外，注意，指针的初始化！指针的操作必须谨慎！链表的结构体如下：typedef struct Node { Datatype ch; struct Node *next; }LNode, *Pnode, *Linklist; 实验三 《数据结构实验指导书》答案 实验一： 1、请编写函数int fun(int *a, int *b),函数的功能是判断两个指针a和b所指存储单元的值 的符号是否相同；若相同函数返回1，否则返回0。这两个存储单元中的值都不为0。在主函数中输入2个整数、调用函数fun、输出结果。 #include 数fun、输出结果。 #define N 10 #include 2013-03-08 上机实验题 1.构建两个顺序表示的非空线性表LA和LB (数据元素为整型，其值自行确定)； 2.从线性表LA中删除第i 个元素； 3.将元素e插入到线性表LB中的第i个元素之后； 4.假设LA中不含重复的元素 (LB同)，将线性表LA和LB合并，并输出结果，要求结 果中不含重复的元素。 //构建两个顺序表（定义、初始化） //在一个顺序表中删除指定位置的元素 //在一个顺序表中指定位置插入一个新元素 //将两个线性表LA和LB进行合并 //遍历LB, 如果其中的数据元素不在LA中，则将其插入LA，否则不予处理 //打印线性表LA #define List_Init_Size 100 #define LISTINCREMENT 10 typedef int Status; typedef struct { int * elem; int length; // 当前长度 int ListSize; // 当前分配的存储容量 }SqList; Status Initialize_table (SqList &L) {// 初始化线性表 int i, m, data; L.elem=(int *)malloc(List_Init_Size *sizeof(int)); if (!L.elem) { // 为线性表分配空间 printf("Overflow"); return FAILURE; } L.ListSize=List_Init_Size; L.length=0; printf ("Please input the size of linear table (<=%d): "+ List_Init_Size); scanf_s("%d",&m); for (i=0;i 数据结构基础及深入及考试 复习资料 习题及实验参考答案见附录 结论 1、数据的逻辑结构是指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。 2、数据的物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。存储结构可分为4大类：顺序、链式、索引、散列 3、抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作）。它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）。 4、算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。 5、在数据结构中，从逻辑上可以把数据结构分成（ C ） A、动态结构和表态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 6、算法的时间复杂度取决于（ A ） A、问题的规模 B、待处理数据的初态 C、问题的规模和待处理数据的初态 线性表 1、线性表的存储结构包括顺序存储结构和链式存储结构两种。 2、表长为n的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均次数为（ E ），删除一个元素需要移动的元素的个数为（ A ）。 A、(n-1)/2 B、n C、n+1 D、n-1 E、n/2 F、(n+1)/2 G、(n-2)/2 3、“线性表的逻辑顺序与存储顺序总是一致的。”这个结论是（ B ） A、正确的 B、错误的 C、不一定，与具体的结构有关 4、线性表采用链式存储结构时，要求内存中可用存储单元的地址（ D ） A、必须是连续的 B、部分地址必须是连续的C一定是不连续的D连续或不连续都可以 5、带头结点的单链表为空的判定条件是（ B ） A、head==NULL B、head->next==NULL C、head->next=head D、head!=NULL 6、不带头结点的单链表head为空的判定条件是（ A ） A、head==NULL B、head->next==NULL C、head->next=head D、head!=NULL 7、非空的循环单链表head的尾结点P满足（ C ） A、p->next==NULL B、p==NULL C、p->next==head D、p==head 8、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（ B ） A、O(1) B、O(n) C、O(n2) D、O(nlog2n) 9、在一个单链表中，若删除p所指结点的后继结点，则执行（ A ） 实验报告 （2015 / 2016学年第二学期） 课程名称数据结构A 实验名称内排序算法的实现以及性能比较 实验时间2016 年 5 月26 日 指导单位计算机科学与技术系 指导教师骆健 学生姓名耿宙班级学号B14111615 学院(系) 管理学院专业信息管理与信息系统 —— 实习题名:内排序算法的实现及性能比较 班级 B141116 姓名耿宙学号 B14111615 日期2016.05.26 一、问题描述 验证教材的各种内排序算法，分析各种排序算法的时间复杂度；改进教材中的快速排序算法，使得当子集合小于10个元素师改用直接插入排序；使用随即数发生器产生大数据集合，运行上述各排序算法，使用系统时钟测量各算法所需的实际时间，并进行比较。系统时钟包含在头文件“time.h”中。 二、概要设计 文件Sort.cpp中包括了简单选择排序SelectSort()，直接插入排序InsertSort()，冒泡排序BubbleSort()，两路合并排序Merge()，快速排序QuickSort()以及改进的快速排序GQuickSort()六个内排序算法函数。主主函数main的代码如下图所示： 三、详细设计 1.类和类的层次设计 在此次程序的设计中没有进行类的定义。程序的主要设计是使用各种内排序算法对随机 生成的数列进行排列，并进行性能的比较，除此之外还对快速排序进行了改进。下图为主函 数main的流程图： —— main() 2.核心算法 1)简单选择排序： 简单选择排序的基本思想是：第1趟，在待排序记录r[1]~r[n]中选出最小的记录，将它与r[1]交换；第2趟，在待排序记录r[2]~r[n]中选出最小的记录，将它与r[2]交换；以此类推，第i趟在待排序记录r[i]~r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到 2011~2012第一学期数据结构实验报告 班级：信管一班 学号：201051018 姓名：史孟晨 实验报告题目及要求 一、实验题目 设某班级有M（6）名学生，本学期共开设N（3）门课程，要求实现并修改如下程序（算法）。 1. 输入学生的学号、姓名和 N 门课程的成绩（输入提示和输出显示使用汉字系统）， 输出实验结果。（15分） 2. 计算每个学生本学期 N 门课程的总分，输出总分和N门课程成绩排在前 3 名学 生的学号、姓名和成绩。 3. 按学生总分和 N 门课程成绩关键字升序排列名次，总分相同者同名次。 二、实验要求 1．修改算法。将奇偶排序算法升序改为降序。（15分） 2．用选择排序、冒泡排序、插入排序分别替换奇偶排序算法,并将升序算法修改为降序算法；。（45分）） 3．编译、链接以上算法，按要求写出实验报告（25）。 4. 修改后算法的所有语句必须加下划线，没做修改语句保持按原样不动。 5．用A4纸打印输出实验报告。 三、实验报告说明 实验数据可自定义，每种排序算法数据要求均不重复。 (1) 实验题目：《N门课程学生成绩名次排序算法实现》； (2) 实验目的：掌握各种排序算法的基本思想、实验方法和验证算法的准确性； (3) 实验要求：对算法进行上机编译、链接、运行； (4) 实验环境（Windows XP-sp3,Visual c++)； (5) 实验算法（给出四种排序算法修改后的全部清单）； (6) 实验结果（四种排序算法模拟运行后的实验结果）； (7) 实验体会（文字说明本实验成功或不足之处）。 三、实验源程序（算法） Score.c #include "stdio.h" #include "string.h" #define M 6 #define N 3 struct student { char name[10]; int number; int score[N+1]; /*score[N]为总分,score[0]-score[2]为学科成绩*/ }stu[M]; void changesort(struct student a[],int n,int j) {int flag=1,i; struct student temp; while(flag) { flag=0; for(i=1;i数据结构上机实验报告
数据结构实验报告格式
数据结构课程实验指导书
华农数据结构上机实验答案
数据结构实验报告全集
数据结构实验报告
计10--数据结构专题实验rev2
数据结构上机实验报告
经典数据结构上机题_答案解析
数据结构实验一 实验报告
数据结构实验报告模板
数据结构上机实验指导
数据结构上机实验答案
数据结构 上机实验题及题解
数据结构(第4版)习题及实验参考答案数据结构复习资料完整版(c语言版)
南邮数据结构上机实验四内排序算法的实现以及性能比较
数据结构实验报告及心得体会