实验十一 顺序表操作实现
实验报告
系别:
专业:
组长:
组员:
信息技术学院 网络14-1班 张航 赵曙光 薛志杰
第2讲 线性表及其顺序存储
实验十一 顺序表操作实现
实验目的及要求
1. 熟练掌握线性表的基本操作在顺序存储上的实现;
2. 以线性表的各种操作(建立、插入、删除、遍历等)的实现为重点;
3. 掌握线性表的顺序存储结构的定义和基本操作的实现;
4. 通过本实验加深对C语言的使用(特别是函数调用的参数传递、指针类型的应用)。 实验内容
已知程序文件seqlist.cpp已给出学生身高信息顺序表的类型定义和基本运算函数定义。
(1)顺序表类型定义
typedef struct {
int xh; /*学号*/
float sg; /*身高*/
int sex; /*性别,0为男生,1为女生*/
} datatype;
typedef struct{
datatype data[MAX]; /*存放顺序表元素的数组*/
int last; /*表示data中实际存放元素个数*/
}Seqlist;
(2)基本运算函数原型
void initList(Seqlist *lp);/*置一个空表*/
void createList(Seqlist *lp);/*建一个学生顺序表*/
void sort_xh(Seqlist *lp);/*按学号排序*/
void Error(char *s);/*自定义错误处理函数*/
void pntList(Seqlist *lp);/*输出学生表*/
void save(Seqlist *lp,char strname[]);/*保存学生顺序表到指定文件*/
第 1页
第2讲 线性表及其顺序存储
任务一
创建程序文件seqlist.cpp,其代码如下所示,理解顺序表类型Seqlist和基本运算函数后回答下列问题。
/*seqlist.cpp程序文件代码*/
#include <stdio.h>
#include <stdlib.h>
#define MAX 50
typedef struct {
int xh; /*学号*/
float sg; /*身高*/
int sex; /*性别,0为男生,1为女生*/
} datatype;
typedef struct{
datatype data[MAX]; /*存放顺序表元素的数组*/
int last; /*表示data中实际存放元素个数*/
}Seqlist;
void initList(Seqlist *lp);/*置一个空表*/
void createList(Seqlist *lp);/*建一个学生顺序表*/
void sort_xh(Seqlist *lp);/*按学号排序*/
void Error(char *s);/*自定义错误处理函数*/
void pntList(Seqlist *lp);/*输出学生表*/
void save(Seqlist *lp,char strname[]);/*保存学生顺序表到指定文件*/
/*置一个空表*/
void initList(Seqlist *lp)
{ lp->last=0; }
/*建一个学生顺序表*/
void createList(Seqlist *lp)
{ FILE *fp;
int xh ,sex;
float sg;
if((fp=fopen("records.txt","r"))==NULL)
{ Error("can not open file !");
}
while(!feof(fp))
{ fscanf(fp,"%d%f%d",&xh,&sg,&sex);
lp->data[lp->last].xh=xh;
lp->data[lp->last].sg=sg;
lp->data[lp->last].sex=sex;
lp->last++;
}
fclose(fp);
第 2页
第2讲 线性表及其顺序存储
}
/*按学号排升序*/
void sort_xh(Seqlist *lp)
{ int i,j,k;
datatype st;
for(i=0;i<lp->last-1;i++)
{k=i;
for(j=i+1;j<lp->last;j++)
if(lp->data[j].xh<lp->data[k].xh )
k=j;
if(k!=i)
{st=lp->data[k];
lp->data[k]=lp->data[i];
lp->data[i]=st;}
}
}
/*自定义错误处理函数*/
void Error(char *s)
{ printf("\n %s", s);
exit(1); /*返回OS,该函数定义在stdlib.h中*/
}
/*输出学生顺序表*/
void pntList(Seqlist *lp)
{ int i;
for(i=0;i<lp->last ;i++)
printf("%2d: %.2f %d\n",lp->data [i].xh,lp->data [i].sg,lp->data[i].sex); }
/*保存学生顺序表到指定文件*/
void save(Seqlist *lp,char strname[])
{ FILE *fp;
int i;
if((fp=fopen(strname,"w"))==NULL)
{ Error("can not open file !");
}
for(i=0;i<lp->last ;i++)
{ fprintf(fp,"%2d %5.2f %2d\n",lp->data[i].xh,lp->data[i].sg,lp->data[i].sex); }
fclose(fp);
}
第 3页
第2讲 线性表及其顺序存储
请回答下列问题:
(1)由顺序表类型定义可知,该顺序表类型名为 Seqlist ,其中存放的元素为学
生信息,学生信息定义的类型名为 datatype ,包含 xh 、 sg 、 sex 、 三个成员(写出成员变量名),学生信息存储于 data 数组,顺序表的表长变量为 MAX 。
(2)seqlist.cpp程序编译连接通过后能执行吗?为什么?其代码的整体结构有哪几个组成部分?
不能;因为没有主函数,程序无法运行。
代码的整体结构有哪几个组成部分:
typedef struct datatype;
typedef struct Seqlist;
void initList(Seqlist *lp);/*置一个空表*/
oid sort_xh(Seqlist *lp);/*按学号排序*/
void createList(Seqlist *lp);/*建一个学生顺序表*/
void Error(char *s);/*自定义错误处理函数*/
void pntList(Seqlist *lp);/*输出学生表*/
void save(Seqlist *lp,char strname[]);/*保存学生顺序表到指定文件*/
(3)回答下列问题
a)initList函数的形参变量lp存放什么值?顺序表置为空表的实质是做什么操作?
学生信息:学号,身高,性别。
顺序表的初始化即构造一个空表,这对表是一个加工型的运算,因此,将L设为指针
参数,首先动态分配存储空间,然后,将表中last指针置为0,表示表中没有数据元素
b)在建立顺序表的createList函数中,顺序表的数据元素来自何处?根据已提供的数据
建完的顺序表表长是多少?
顺序表的数据元素来自文件,顺序表表长是:last。
c)sort_xh排序函数采用了什么排序方法?请列举5个学号值写出每趟(5个需排4趟)
第 4页
第2讲 线性表及其顺序存储
排序后的结果
冒泡排序。
第一次排序 1,3,6,4,5
第二次排序1,3,6,4,5
第三次排序1,3,4,6,5
第四次排序1,3,4,5,6
d)列举一个调用自定义错误处理函数Error的调用语句,并给出屏幕输出结果
e)save函数中的形参数组strname中存放什么?
存放的是学生的学生的信息:学号,身高,性别。
任务二
1.题目要求
创建一个新的程序文件sy11.cpp,请调用seqlist.cpp提供的功能函数(以#include “seqlist.cpp” 方式导入函数库)及自定义的函数完成以下操作:
? 创建一个包含学生学号、身高、性别的学生身高信息表并输出到屏幕,学生信息从
records.txt文件读取;
? 对已建立的学生身高信息表按学号从小到大排序,并把结果写入到数据文件中
(result.txt);
? 从键盘输入一位学生的相关信息插入到已排序的学生身高信息表中后仍然保持学
号的有序性;
? 对插入后的学生身高信息表进行倒置,结果输出在屏幕;
? 从键盘输入一个身高值,统计与该身高相同的学生个数并输出在屏幕; 在程序文件sy1.cpp需再定义以下三个功能函数:
(1)void insertX(Seqlist *lp, datatype x)
功能:在学号从小到大排序的学生表中插入值为x的学生仍保持学号的有序性
(2)void reverse(Seqlist *lp)
第 5页
第2讲 线性表及其顺序存储
功能:对lp指向的顺序表进行倒置操作
(3)int count(Seqlist *lp,float y)
功能:统计学生表中身高值为y的学生数并返回
2.请根据题目功能要求及程序中的注释填空完整sy1.cpp代码
/*sy11.cpp程序文件代码*/
#include "seqlist.cpp" //导入自定义类型及函数所在的文件seqlist.cpp,该文件与sy11.cpp存于同一目录中
void insertX(Seqlist *lp, datatype x);
void reverse(Seqlist *lp);
int count(Seqlist *lp,float y);
void main()
{
Seqlist stu; //定义stu为学生顺序表变量
datatype x; //x为存储一个学生信息的变量
int c;
char strname[20]; //strname为存储文件名的数组
/*创建一个包含学生学号、身高、性别的学生身高信息表stu并输出到屏幕,学生信息从records.txt文件读取*/
//调用函数initList初始化顺序表stu
// 调用函数createList创建学生表stu printf("\nsource list:\n");
//调用函数pntList打印学生表stu
getchar(); //在执行程序能起到暂定的作用,按任意键继续
/*对已建立的学生身高信息表按学号从小到大排序,并把结果写入到数据文件中(result.txt)*/
//调用函数sort_xh 对学生表stu按学号从小到大排序
printf("\nInput new file name to save: ");
//键盘输入文件名字符串存于strname字符数组中 //调用函数save把排序后的顺序表stu存于文件中,文件名在strname数组中
/*从键盘输入一位学生的相关信息插入到已排序的学生身高信息表中后仍然保持学号的有序性;*/
printf("\nInput a student information: \n");
scanf("%d%f%d",&x.xh,&x.sg,&x.sex);
第 6页
第2讲 线性表及其顺序存储
//插入
printf("\nlist after insert:\n");
pntList(&stu);
getchar();
/*对插入后的学生身高信息表进行倒置,结果输出在屏幕;*/
//倒置顺序表
printf("\nlist after reverse:\n");
pntList(&stu);
getchar();
/*从键盘输入一个身高值,统计与该身高相同的学生个数并输出在屏幕*/ printf("\nInput a student height: \n");
scanf("%f",&x.sg);
//统计相同身高的学生数存于c中
printf("\nThe same height :%d\n",c);
getchar();
}
/*在学号从小到大排序的学生表中插入值为x的学生仍保持学号的有序性*/ void insertX(Seqlist *lp,datatype x)
{
int i,j;
if(lp->last>=MAX)
Error("list is full");
//在学号升序的顺序表中找插入位置后,插入x并使表长增1
else
For(i=0;i<lp->last;i++)
If(lp->last>x)
Break;
for(j=lp->last-1;j>=i;j--) /*从后往前元素后移*/
lp-> strname [j+1]=lp-> strname [j];
lp-> strname [i]=x; lp->last++; /*插入并表长增1*/
第 7页
第2讲 线性表及其顺序存储
}
/*对lp指向的顺序表进行倒置操作*/
void reverse(Seqlist *lp)
{ int i,j;
datatype temp;
//通过前后数据元素交换的方式实现倒置
.
}
/*统计学生表中身高值为y的学生数并返回*/
int count(Seqlist *lp,float y)
{ int i,c=0;
//遍历顺序表统计身高为y的学生数到c变量并返回值
}
实验总结分析(本程序的重点与难点,调试中出现的问题及解决方法等)
第 8页
第二篇:实验一 顺序表操作
实验一 线性表的应用—顺序表操作
[ 实验日期 ] 2014 年 3 月 1 日
学号: 11022029 专业年级: 海工一班 姓名:刘争
一、目的和要求
1.熟悉并掌握线性表的逻辑结构定义、特点。
2.熟悉并掌握顺序表描述方法。
3.熟悉并掌握顺序表的基本操作,包括顺序表的建立与打印,插入与删除数据元素,查找数据元素等。
二、实验内容
(详细说明顺序表操作的各个函数头的说明)
三、实验环境
1.硬件:PC机。
2.软件:DOS 、Windows9.x 、Window2000或以上版本,TurboC 2.0 及以上版本或VC6.0。
四、源程序
#include<iostream>
using namespace std;
template <class T>
class sq_LList
{ private:
int mm;
int nn;
T* v;
public:
}; sq_LList(){mm=0;nn=0;return;} sq_LList(int); void prt_sq_LList(); int flag_sq_LList(); void ins_sq_LList(int,T); void del_sq_LList(int);
template<class T>
sq_LList<T>::sq_LList(int m) {
}
template<class T>
void sq_LList<T>::prt_sq_LList() {
mm=m; v=new T[mm]; nn=0; return; int i; cout<<"nn="<<nn<<endl;
} for(i=0;i<nn;i++)cout<<v[i]<<endl; return;
template <class T>
int sq_LList<T>::flag_sq_LList()
{ if(nn==mn) return(-1);
if(nn==0) return(0);
return(1);
}
template<class T>
void sq_LList<T>::ins_sq_LList(int i,T b) {
int k; if(nn==mm) {cout<<"overflow"<<endl; return;} if(i>nn)i=nn+1; if(i<1) i=1; for(k=nn;k>=i;k--) v[k]=v[k-1]; v[i-1]=b; nn=nn+1;
} return;
template<class T>
void sq_LList<T>::del_sq_LList(int i)
{int k;
if(nn==0)
{cout<<"underflow!"<<endl;return;}
if((i<1)||(i>nn))
{cout<<"Not this element in the list!"<<endl; return;
}
for(k=i;k<nn;k++)
v[k-1]=v[k];
nn=nn-1;
return;
}
int main()
{
sq_LList<double>s1(100); cout<<"第一次输出顺序表对象s1:"<<endl; s1.prt_sq_LList(); s1.ins_sq_LList(0,1.5);
s1.ins_sq_LList(1,2.5); s1.ins_sq_LList(4,3.5);
} cout<<"第二次输出顺序对象s1:"<<endl; s1.prt_sq_LList(); s1.del_sq_LList(0); s1.del_sq_LList(2); cout<<"第三次输出顺序对象s1:"<<endl; s1.prt_sq_LList(); return 0;