数据结构课程实验

数据结构实验实验内容和目的：掌握几种基本的数据结构：集合、线性结构、树形结构等在求解实际问题中的应用，以及培养书写规范文档的技巧。

学习基本的查找和排序技术。

让我们在实际上机中具有编制相当规模的程序的能力。

养成一种良好的程序设计风格。

实验教材：数据结构题集（C语言版）清华大学出版社2007年实验项目：实验一、栈和循环队列㈠、实验内容：①栈掌握栈的特点(先进后出FILO)及基本操作,如入栈、出栈等，栈的顺序存储结构和链式存储结构，以便在实际问题背景下灵活应用。

本程序采用的是链栈结构，具有初始化一个栈、PUSH、POP、显示所有栈里的元素四个功能。

②循环队列掌握队列的特点(先进先出FIFO)及基本操作,如入队、出队等，学会循环队列的实现，以便在实际问题背景下灵活运用。

本程序具有初始化一个队列、入队、出队、显示队列的所有元素、队列长度五个功能。

㈡、实验代码①栈程序代码：#include <stdio.h>#include <malloc.h>#define Stack_Size 6#define ERROR 0#define OK 1typedef int SElemType;typedef struct SNode{SElemType data;struct SNode *next;}SNode,*LinkStack;int CreatTwo(LinkStack &head,int n){int i;SNode *p;head=(LinkStack)malloc(sizeof(SNode));head->next=NULL;printf("请输入数据(数字):\n");for(i=n;i>0;--i){p=(SNode *)malloc(sizeof(SNode));scanf("%d",&p->data);p->next=head->next;head->next=p;}return 1;}int menu_select(){int sn;for(;;){scanf("%d",&sn);if(sn<1||sn>6)printf("\n\t输入错误，请重新输入\n");elsebreak;}return sn;}int Push(LinkStack &top,SElemType e){SNode *q;q=(LinkStack)malloc(sizeof(SNode));if(!q){printf("溢出!\n");return(ERROR);}q->data=e;q->next=top->next;top->next=q;return(OK);}int Pop(LinkStack &top,SElemType &e){SNode *q;if(!top->next){printf("error!\n");return(ERROR);}e=top->next->data;q=top->next;top->next=q->next;free(q);return(OK);}void main(){ int e;LinkStack top;printf("1.初始化一个栈;\n2.PUSH;\n3.POP;\n4.显示所有栈里的元素;\n5.结束;\n");while(1){switch(menu_select()){case 1:if(CreatTwo(top,Stack_Size))printf("Success!\n");break; case 2:printf("Push:\n");scanf("%d",&e);if(Push(top,e))printf("Success!\n");break;case 3:if(Pop(top,e))printf("Success!\n");printf("%d\n",e);break;case 4:LinkStack p;printf("所有栈里的元素:\n");p=top;while(p->next){p=p->next;printf("%7d",p->data);}printf("\n");break;case 5:return;}}}运行结果：②循环队列程序代码：#include<stdlib.h>#include<stdio.h>#define OVERFLOW -1#define OK 1#define ERROR 0#define MAXSIZE 100typedef struct{int *elem;//队列存储空间int front;int rear;}SqQueue;//判断选择是否正确int menu_select(){int sn;for(;;){scanf("%d",&sn);if(sn<1||sn>6)printf("\n\t输入错误，请重新输入\n");elsebreak;}return sn;}//参数(传出)SqQueue &Q,循环队列(空)int InitQueue(SqQueue &Q){Q.elem=(int *)malloc(MAXSIZE*sizeof(int));if(!Q.elem)exit(OVERFLOW);Q.front=Q.rear=-1;for(int i=0;i<MAXSIZE;i++)Q.elem[i]=-1;return OK;}//返回Q的元素个数int QueueLength(SqQueue Q){return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;}//显示队列的元素void Display(SqQueue Q){for(int i=0;i<=QueueLength(Q);i++)if(Q.elem[i]!=-1)printf("%d ",Q.elem[i]);printf("\n");}//入队int EnQueue(SqQueue &Q,int e){Q.rear=(Q.rear+1)%MAXSIZE;if(Q.rear==Q.front)return ERROR;Q.elem[Q.rear]=e;return OK;}//出队int DeQueue(SqQueue &Q,int &e){if(Q.front==Q.rear)return ERROR;e=Q.elem[Q.front+1];Q.elem[Q.front+1]=-1;Q.front=(Q.front+1)%MAXSIZE;return OK;}void main(){SqQueue Q;InitQueue(Q);int elem,e;printf("请输入队列元素(以0结束):\n");scanf("%d",&elem);while(elem!=0){EnQueue(Q,elem);scanf("%d",&elem);}printf("队列为：\n");Display(Q);printf("1.初始化一个队列;\n2.入队;\n3.出队;\n4.显示队列的所有元素;\n5.队列长度:\n6.结束;\n");while(1){switch(menu_select()){case 1:printf("请输入队列元素(以0结束):\n");scanf("%d",&elem);while(elem!=0){EnQueue(Q,elem);scanf("%d",&elem);}printf("队列为：\n");Display(Q);fflush(stdin);break;case 2:scanf("%d",&elem);EnQueue(Q,elem);printf("队列为：\n");Display(Q);fflush(stdin);break;case 3:DeQueue(Q,elem);printf("队列为：\n");Display(Q);break;case 4:printf("\n队列的所有元素:\n");Display(Q);break;case 5:printf("%d\n",QueueLength(Q));break;case 6:return;}}}运行结果：实验二、数组㈠、实验内容：数组一般不做插入或删除操作，也就是说，一旦建立了数组，则结构中的数据元素个数和元素之间的关系就不再发生变动。

数据结构实验指导书（计算机科学与技术专业）淮南师范学院计算机与信息工程系2015.9前言数据结构是软件开发的基础，数据结构课程是软件工程、计算机科学与技术、网络工程、信息安全、物联网工程等专业的必修技术基础课程。

该课程是在学生学习高级语言程序设计课程基础上，使学生掌握各种常用数据结构的逻辑表示、存储表示、处理方法及应用算法设计，学会常用数据分类和数据查找的技术，对所设计的算法会做定量或定性的分析比较，培养学生的算法设计与分析的能力。

通过该课程的学习，使学生学会分析数据对象特性，选择合适的数据结构、存贮结构及相应的基本处理算法；初步掌握算法的时间空间复杂度分析技巧。

既为学生学习后继课程打好基础，也为将来软件开发提供理论指导。

数据结构具有很强的实践性，只有通过编程上机实验，才能真正领会数据结构的真正内涵，并灵活运用数据结构的基本知识提高自己的软件开发能力。

《数据结构》实验项目一览表课程名称：数据结构学时：16 适应专业：计算机科学与技术实验1：顺序表及其应用1．实验目的：（1）熟练掌握VC或Dev C++集成环境和程序开发步骤；（2）熟练掌握顺序表的插入、删除、查找定位等基本算法；（3）能利用顺序表解决简单的问题。

2．实验原理：线性表是最基本最常用的一种线性结构。

其特点是除了第一个元素和最后一个元素以外，其他数据元素都只有一个前驱和一个后继。

一个线性表中的数据元素应具有相同的描述性质，即属于同一个数据对象。

在实际应用中，必须将线性表中的数据存放在计算机中。

常用的存储方式有两种：顺序存储和链式存储，线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各个元素，使得数据元素逻辑上的相邻关系与物理上的相邻关系一致。

顺序存储的线性表又称顺序表，可以随机地存取表中的任意一个元素；也无需为表示结点之间的逻辑关系而额外增加存储空间。

但是，顺序表在进行插入和删除操作时需要移动大量的元素，影响运行的效率；同时表的最大容量事先无法估计，如果对表长估计的过长，可能会浪费空间，相反则可能会发生溢出的现象。

得 的 一些心 得体会 。
【 键词 】 数据 结构 ； 关 ： 实验 教 。 解 数 据 结 构 和 程 序 设 计 之 间 并要 求写 出实 验报 告 。 理 主要分 为 告知题 目阶段 、 法 实 算
现 阶段和 结果 汇 总阶 段等 三个 阶段 来进 行 。 ｆ１ １ 告知 题 目阶段 《 据结 构 》 是计 算 机 专 业 课 程 体 系 的 主 干 专 业 数 由于一 次 实 验课 的时 间 可能 就是 两 个小 时 ．所 以 课 ． 是一 门把 技术 、 它 理论 和 实践 融 合 于一体 的 十分 重 要 的核 心课 程 建议 一般 在 上 实 验 课 的前 几 天 就 可 以 把 题 目抛 给 学 这样 可 以让 学生 在课 余 时 问去 查一 些相 关 的资 料 ， 那 么 是不 是 只 要学 会 程 序 设 计 ， 习《 据 结 构 》 生 ． 学 数
最后一个数交换。 ②有 ５个学生 ， 每个学生的数据包括
参考 文献 ：
１严 吴伟 《 ｃ 》Ｍ】北京 清 学号、 姓名 、 门课 的成 绩 、 均 分 。 三 平 要求 用结 构体 实 现 【】 蔚 敏 ， 民 ．数 据 结 构 （ 语 言版 ）【 ． ： 华 大学 出 版 社 ．９ ７ １９． 从 键盘 依次 输入 ５个 学 生的学 号 、姓 名 、三 门课 的成
绩． 自动计算 三 门课 的平 均分 数 ， 并将 ５个 学生 的数 据 ２０ ０５ ７ 输出。 对 于 每一 次 实验 课 老 师 都 要 进 行 了精 心 地 策 划 ．
【］ 春 葆 ． 据 结 构 教 程 上 机 实 验 指 导 ． 京 ： 华 大 学 出版 社 ， ２李 数 北 清
ｆ１ ２算法 实现 阶段 在实 验课 堂 上 教 师可 以根 据题 目难 易程序 ．归 纳

{
}
/*
*前置条件：顺序表存在
*输入：要删除元素位置i
*功能：删除顺序表中位置为i的元素
*输出：无
*后置条件：顺序表删除元素
*/
template <class T>
T SeqList<T>::Delete(int i)
{
}
/*
*前置条件：顺序表存在
*输入：无
*功能：输出顺序表长度
*输出：顺序表长度
*后置条件：顺序表不变
{
}
/*
*前置条件：顺序表存在
*输入：查询元素值x
*功能：按值查找值的元素并输出位置
*输出：查询元素的位置
*后置条件：顺序表不变
*/
template <class T>
int SeqList<T>::Locate(T x)
{
}
/*
*前置条件：顺序表存在
*输入：无
*功能：顺序表遍历
*输出：输出所有元素
cout<<endl;
cout<<"顺序表a的长度为:";
cout<<a.Length()<<endl; //返回单链表长度
cout<<endl;
cout<<"按位查询第二个元素:"<<endl;
cout<<"第二个元素为:";
cout <<a.Get(2)<<endl; //查找顺序表中第二个元素
}
cout<<endl;
cout<<"顺序表a中的元素有:"<<endl;