《数据结构实验》指导书(实验1)2010

实验一 顺序表的基本操作

一、 实验目的

1．掌握使用VC++6.0调试程序的基本方法； 2．掌握线性表的顺序存储结构的类型定义；

3．掌握顺序表的基本操作的实现,如：插入、删除、遍历、查找、排序、修改、合并等； 4．掌握顺序表的应用。

二、 实验环境

1．台式计算机每人一台； 2．软件：Visual C++6.0

三、 注意事项

在U盘上创建一个以“学号姓名”命名的文件夹（如：20090001张三），专门用于存储数据结构实验的程序及实验报告、处理的输入数据。

四、 实验内容

示例程序：简易学生信息管理系统（SqList.cpp）

本简易学生信息管理系统要求以顺序表作为学生信息的载体，并实现学生信息的查询、添加、删除、统计、排序、修改、保存等基本功能。本示例程序已经实现了简易学生信息管理中的查询、添加和保存等功能，要求学生对该系统进行完善，继续添加相关函数以提高其实用性。

1. 文件结构设计

a) 原始数据：保存在文件input1.txt中。 b) 输出数据：保存在文件output1.txt中。

2. 数据结构设计

//顺序表存储结构定义

#define MaxSize 50 //线性表的最大容量，假设为50 typedef struct Stu{ long int num;//学号 char name[20];//姓名 char sex;//性别 int age;//年龄

int score;//分数

}Elemtype;//定义数据元素为学生信息 typedef struct SqList { Elemtype *data;

int length; // 线性表长度 }SqList; // 顺序表数据类型为SqList 3. 程序结构

a) 函数说明

int Menu();//系统主菜单 int QMenu();//查询菜单

void PrintElem(Elemtype a);//打印输出数据元素a的各数据项 void Init_SqList(SqList &L);//构造一个空的顺序表L void SaveList(SqList L,FILE *out);//保存顺序表L的数据 void Creat_SqList(SqList &L,FILE *in); //建表

void Traver_SqList(SqList L); //查询(遍历顺序表L) SqList Insert_SqList (SqList &L); //添加 b) 函数实现

//基本操作的实现

int Menu()//系统主菜单 { int n; printf(\ printf(\学生信息管理系统******************\\n\\n\ printf(\导入数据\\n\ printf(\查询（全部信息、男生信息、女生信息）\\n\ printf(\添加学生信息\\n\ printf(\删除学生信息\\n\ printf(\统计人数（男生、女生、不及格、优秀等）\\n\ printf(\排序（升序、降序）\\n\ printf(\修改（修改姓名、性别、年龄、分数等属性值）\\n\ printf(\存盘\\n\ printf(\退出\\n\\n\ printf(\欢迎访问**********************\\n\ printf(\ scanf(\ return(n); }

int QMenu()//查询菜单 { int n; printf(\欢迎进入查询系统************\\t\\n\ printf(\全部信息\ printf(\男生信息\

2

《数据结构实验》指导书

printf(\女生信息\ printf(\退出\\t\ printf(\ scanf(\ return(n); }

void PrintElem(Elemtype a)

{//打印输出数据元素a的各数据项，即输出单个学生信息 printf(\ a.num,a.name,a.sex,a.age,a.score); }

void Init_SqList(SqList &L) {//构造一个空的顺序表L L.data=(Elemtype *)malloc(MaxSize*sizeof(Elemtype)); if(!L.data) exit(1); L.length=0; }

void Creat_SqList(SqList &L,FILE *in)

{//建表，从文件指针in所指文件读取数据,以尾插法建立顺序表L int i; fscanf(in,\读取数据元素个数，即表长n //printf(\表长n=%d\\n\ for(i=0;i

L.data[i].name,&L.data[i].sex,&L.data[i].age,&L.data[i].score);

}

void Traver_SqList(SqList L)

{//遍历顺序表L（输出L中的数据序列）

//查询（1.全部信息 2.男生信息 3.女生信息 4.退出 ） int i,choice=QMenu(); switch(choice) { printf(\学号 姓名 性别 年龄 分数）\\n\ case 1://全部信息 for(i=0;i

L.data[i].name,L.data[i].sex,L.data[i].age,L.data[i].score);*/

printf(\

3

case 2://男生信息 for(i=0;i

SqList Insert_SqList (SqList &L)

{// 在顺序表L的第 i 个位置上插入（添加）一个新元素 Elemtype x; int i; printf(\请输入插入的位置(1..%d)i=\ scanf(\

if ((i<1) || ( i>L.length+1)) //检查插入位置的正确性 { printf (\插入位置i不合理！\ } //不合理，中止程序运行 if (L.length >= MaxSize) // 顺序表是否已满 { printf (\“顺序表已满，不能再插入！”\ exit(1); } // 表满,不能插入 printf(\请输入添加的元素（学号 姓名 性别 年龄 成绩）\\n x=\ scanf(\

for (int m=L.length-1; m>=i-1; --m) L.data [m+1]=L.data[m];// 数据后移

//L.data [m+1] = L.data[m]; // 数据后移 L.data[i-1]=x;//新元素插入 // L.data [i-1] = x; //新元素插入 L.length++; //表长+1 return L; //插入成功，返回 }

void SaveList(SqList L,FILE *out)

{//将顺序表L的数据存入文件output1.txt int i; fprintf(out,\保存表长 for(i=0;i

4

《数据结构实验》指导书

fprintf(out,\

L.data[i].num,L.data[i].name,L.data[i].sex,L.data[i].age,L.data[i].score);

}

c) 主函数 void main()

{//通过文件input1.txt输入数据，结果输出到文件output1.txt //打开输入输出文件 FILE *in,*out;

if((in=fopen(\ { printf(\ exit(0); }

if((out=fopen(\ { printf(\ exit(0); } int choice; SqList L;

Init_SqList(L);//系统文件初始化,构造空表L while(1) { choice=Menu(); switch(choice) {

case 1: Creat_SqList(L,in); //导入数据,根据文件input.txt读入的数据建立顺序表L

break;

case 2: Traver_SqList(L);//查询，输出顺序表

break;

case 3: Insert_SqList(L);// 在顺序表L中插入一个新元素

break;

5

case 4: case 5: case 6: case 7:

break;//删除元素 break;//统计 break;//排序 break;//修改

case 0: SaveList(L,out);fclose(in);fclose(out);exit(-1);break;

//保存数据，并退出系统

} }

} getchar();

五、 实验要求

1．认真阅读和掌握本实验的示例程序。

2．上机运行示例程序，打印出程序的运行结果，并作必要的说明。 3．对示例程序，按照对线性表的操作需要，在程序中至少添加2个顺序表的相关操作。如：

1) 查找并显示分数在区间[a，b）的学生信息； 2) 查找并显示最高分或最低分学生信息； 3) 统计不及格或及格人数及所占比例；

4) 将信息表按学号、姓名或分数升序或降序排列； 5) 按学号顺序进行数据元素的插入； 6) 删除指定学号或姓名的学生信息； 7) 修改某个学生的信息； 8) 其它。

4．重新改写主函数（要求必需调用自己添加的操作），打印出文件清单（自己添加的函数、修改后的主函数和运行结果）。 5．对修改后的程序，分析每一个算法（函数）的时间复杂度。 6．根据上述要求撰写实验报告，并简要给出算法设计小结和心得。

6

《数据结构实验》指导书

//************************************************************************//

附：顺序表基本操作的实现程序实例

本程序实例提供的顺序表存储结构定义及基本操作的实现仅供参考。 //-----------------SqList2.CPP-------------------- //本程序定义了顺序表存储结构的另外一种形式 //并演示了几个基本操作的实现

//（初始化、清空、求长度、判空、判满、遍历、查找、插入、删除、有序输出）

#include #include #include #include

typedef int ElemType; // 定义ElemType为int类型 //线性表顺序存储类型定义 struct SqList {ElemType *list;// int size;// 线性表长度

int MaxSize;//线性表的最大容量 };

//顺序表基本操作说明

void InitList(SqList &L,int ms); //初始化顺序表 void ClearList(SqList &L); //清空线性表 int ListSize(SqList &L); //求线性表长度 bool ListEmpty(SqList &L); //检查线性表是否为空 bool ListFull(SqList &L);

//检查线性表是否为满 void TraverList(SqList &L);

//遍历线性表

int FindList(SqList &L,ElemType item);

//从线性表中查找元素

bool InsertList(SqList &L,const ElemType item,int mark);//向线性表插入元素 bool DeleteList(SqList &L,ElemType &item,int mark); //从线性表中删除元素

void OrderOutputList(SqList &L,int mark); //对线性表进行有序输出

//顺序表基本操作的实现

//初始化顺序表

void InitList(SqList &L,int ms)

7

{L.list=new ElemType[ms]; if(!L.list) {cout<<\ exit(1);

}

L.size=0; L.MaxSize=ms; }

//清空线性表

void ClearList(SqList &L) {L.size=0; }

//求线性表长度 int ListSize(SqList &L) {return L.size; }

//检查线性表是否为空 bool ListEmpty(SqList &L) {return L.size==0; }

//检查线性表是否为满 bool ListFull(SqList &L) {return L.size==L.MaxSize; }

//遍历线性表

void TraverList(SqList &L)

{for(int i=0;i

//从线性表中查找元素

int FindList(SqList &L,ElemType item) {for(int i=0;i

8

《数据结构实验》指导书

if(L.list[i]==item) return i; return -1; }

//向线性表的表头、表尾或合适位置插入元素 bool InsertList(SqList &L,const ElemType item,int mark) {if(ListFull(L)) return false; if(mark>0) //向表头插入元素 { for(int i=L.size-1;i>=0;i--) L.list[i+1]=L.list[i];

L.list[0]=item;

}

else //向表尾插入元素 if(mark<0) L.list[L.size]=item; else{ //有序插入元素 for(int i=0;i=i;j--)

L.list[j+1]=L.list[j];

L.list[i]=item;

} L.size++; return true; }

//从线性表中删除表头、表尾或等于给定值的元素 bool DeleteList(SqList &L,ElemType &item,int mark) {if(ListEmpty(L)) return false; if(mark>0) //删除表头元素 {item=L.list[0]; for(int i=1;i

L.list[i-1]=L.list[i]; }

else //删除表尾元素 if(mark<0) item=L.list[L.size-1]; else{ //删除值为item的元素 for(int i=0;i

if(L.list[i]==item) break;

if(i>=L.size) return false;

9

for(int j=i;j

L.list[j]=L.list[j+1];

} L.size--;//表长减1 return true; }

//对线性表进行有序输出

void OrderOutputList(SqList &L,int mark) {int *b=new int[L.size]; int i,k;

for(i=0;i

for(int j=i;j

}

if(k!=i-1) {int x=b[i-1];b[i-1]=b[k];b[k]=x;}

}

for(i=0;i

}

const int ML=10; //线性表的最大长度

void main() {SqList a; InitList(a,ML); int i; ElemType x;

//依次向线性表a表尾插入5个整数元素 cout<<\从键盘输入5个整数：\ for(i=0;i<5;i++) {cin>>x; InsertList(a,x,-1); }

//依次向线性表表头插入2个整数元素

10

《数据结构实验》指导书

cout<<\从键盘输入两个整数：\ cin>>x;InsertList(a,x,1); cin>>x;InsertList(a,x,1); //按不同次序遍历输出线性表a TraverList(a); OrderOutputList(a,1); OrderOutputList(a,0);

//把线性表a中的元素依次有序插入到一个新线性表b中 SqList b; InitList(b,ML); for(i=0;i

//从线性表a 中依次删除表头、表尾和等于给定值的元素 if(DeleteList(a,x,1)) cout<<\ else cout<<\ //输出线性表a TraverList(a);

if(DeleteList(a,x,-1)) cout<<\ else cout<<\ //输出线性表a TraverList(a);

cout<<\从键盘上输入一个待删除的整数：\ cin>>x;

if(DeleteList(a,x,0)) cout<<\ else cout<<\ //输出线性表a TraverList(a); }

//*************************************************************************//

11

《数据结构实验》指导书

cout<<\从键盘输入两个整数：\ cin>>x;InsertList(a,x,1); cin>>x;InsertList(a,x,1); //按不同次序遍历输出线性表a TraverList(a); OrderOutputList(a,1); OrderOutputList(a,0);

//把线性表a中的元素依次有序插入到一个新线性表b中 SqList b; InitList(b,ML); for(i=0;i

//从线性表a 中依次删除表头、表尾和等于给定值的元素 if(DeleteList(a,x,1)) cout<<\ else cout<<\ //输出线性表a TraverList(a);

if(DeleteList(a,x,-1)) cout<<\ else cout<<\ //输出线性表a TraverList(a);

cout<<\从键盘上输入一个待删除的整数：\ cin>>x;

if(DeleteList(a,x,0)) cout<<\ else cout<<\ //输出线性表a TraverList(a); }

//*************************************************************************//

11

本文来源：https://www.bwwdw.com/article/zp1a.html