数据结构实验报告
数据结构与算法实验一（顺序表的操作）
一、实验目的
1．掌握线性表的顺序存储结构的表示和实现方法。
2．掌握顺序表基本操作的算法实现。
3．了解顺序表的应用。
二、实验内容
1．建立顺序表。
2．在顺序表上实现插入、删除和查找操作（验证性内容）。
3．删除有序顺序表中的重复元素（设计性内容）。
4．完成一个简单学生成绩管理系统的设计（应用性设计内容）。
三、实验的软硬件环境要求
硬件环境要求：
PC机（单机）
使用的软件名称、版本号以及模块：
Windows环境下的VC++等。
四、知识准备
前期要求熟练掌握了C语言的编程规则、方法和顺序表的基本操作算法。
五、验证性实验
1．实验要求
编程实现如下功能：
（1）根据输入顺序表的长度n和各个数据元素值建立一个顺序表，并输出顺序表中各元素值，观察输入的内容与输出的内容是否一致。
（2）在顺序表的第i个元素之前插入一个值为x的元素，并输出插入后的顺序表中各元素值。
（3）删除顺序表中第i个元素，并输出删除后的顺序表中各元素值。
（4）在顺序表中查找第i个元素，如果查找成功，则显示“查找成功”和该元素在顺序表中的位置，否则显示“查找失败”。
2. 实验相关原理：
线性表的顺序存储结构称为顺序表，顺序表的存储结构描述为：
#define MAXLEN 30 /*线性表的最大长度*/
typedef struct
{ Elemtype elem[MAXLEN]; /*顺序表中存放元素的数组，其中elemtype为抽象数据类型，在程序具体实现时可以用任意类型代替*/
int length; /*顺序表的长度，即元素个数*/
}Sqlist; /*顺序表的类型*/
【核心算法提示】
1．顺序表插入操作的基本步骤：要在顺序表中的第i个数据元素之前插入一个数据元素x,首先要判断插入位置i是否合法，假设线性表的表长为n，则i的合法值范围：1≤i≤n+1，若是合法位置，就再判断顺序表是否满，如果满，则增加空间或结束操作，如果不满，则将第i个数据元素及其之后的所有数据元素都后移一个位置，此时第i个位置已经腾空，再将待插入的数据元素x插入到该位置上，最后将线性表的表长增加1。
2．顺序表删除操作的基本步骤：要删除顺序表中的第i个数据元素，首先仍然要判断i的合法性，i 的合法范围是1≤i≤n，若是合法位置，则将第i个数据元素之后的所有数据元素都前移一个位置，最后将线性表的表长减1。
3．顺序表查找操作的基本步骤：要在顺序表中查找一个给定值的数据元素，则可以采用顺序查找的方法，从顺序表中第1个数据元素开始依次将数据元素值与给定值进行比较，若相等则返回该数据元素在顺序表中的位置，否则返回0值。
【核心算法描述】
status Sqlist_insert(Sqlist &L,int i,Elemtype x)
/*在顺序表L中第i个元素前插入新元素x*/
{ if (i<1||i>L.length+1) return ERROR; /*插入位置不正确则出错*/
if (L.length>=MAXLEN) return OVERFLOW;
/*顺序表L中已放满元素，再做插入操作则溢出*/
for(j=L.length-1;j>=i-1;j--)
L.elem[j+1]=L.elem[j];/*将第i个元素及后续元素位置向后移一位*/
L.elem[i-1]=x; /*在第i个元素位置处插入新元素x*/
L.length++; /*顺序表L的长度加1*/
return OK;
}
status Sqlist_delete(Sqlist &L,int i,Elemtype &e)
/*在顺序表L中删除第i个元素*/
{ if (i<1||i>L.length) return ERROR; /*删除位置不正确则出错*/
for(j=i;j<=L.length-1;j++)
L.elem[j-1]=L.elem[j]; /*将第i+1个元素及后继元素位置向前移一位*/
L.length--; /*顺序表L的长度减1*/
return OK；
}
int Sqlist_search(Sqlist L,Elemtype x)
/* 在顺序表中查找值为x的元素，如果找到，则函数返回该元素在顺序表中的位置，否则返回0*/
{ for (i=0;i<L.length&&L.elem[i]!=x;i++);
/*从第一个元素开始依次将每个元素值与给定值x比较*/
if (i<L.length)
return i;
else
return o;
}
3．学生实验代码
#include "stdio.h"
#define MaxSize 50
typedef struct node
{
int elem [MaxSize];
int length;
}Sqlist;
Sqlist creat(Sqlist L,int n)
{
int i=0;
for(i=0;i<n;i++)
{
int x;
printf("请输入值：");
scanf("%d",&x);
L.elem [i]=x;
}
L.length =n;
return L;
}
void print(Sqlist L)
{
for(int i=0;i<L.length;i++)
printf("%4d",L.elem [i]);
printf("\n");
}
Sqlist Sqlist_insert(Sqlist L,int i,int x)
{
if(i<1||i>L.length )
printf("error");
if(L.length >=MaxSize)
printf("overflow");
for(int j=L.length-1;j>=i-1;j--)
L.elem [j+1]=L.elem [j];
L.elem [i-1]=x;
L.length++;
return L;
}
Sqlist Sqlist_delete(Sqlist &L,int i,int e)
{
if(i<1||i>L.length )
printf("error");
// if(L.length >=MaxSize)
// printf("overflow");
for(int j=i;j<=L.length-1;j++)
L.elem [j-1]=L.elem [j];
L.length--;
return L;
}
int Sqlist_search(Sqlist L,int x)
{
int i;
for(i=0;i<L.length&&L.elem [i]!=x;++i);
if(i<L.length )
return i;
else
return -1;
}
int main()
{
Sqlist head;
int n,k,i,x;
printf("请输入n的值：");
scanf("%d",&n);
head=creat(head,n);
print(head);
printf("请输入插入i位置的值：");
scanf("%d",&i);
printf("请输入要插入x的值：");
scanf("%d",&x);
head=Sqlist_insert(head,i,x);
print(head);
printf("请输入要删除的i位置的值：");
scanf("%d",&i);
head=Sqlist_delete(head,i,x);
print(head);
printf("请输入要查找的值：");
scanf("%d",&x);
k=Sqlist_search(head,x);
if(k==-1)
printf("NOT found\n");
else printf("要查找的%d在%d位置上",x,k+1);
return 0;
}
4．运行结果
六、设计性实验(以下两个设计题目学生可根据自己的掌握程度或兴趣自行选择完成)
1．编程实现删除有序顺序表中的所有重复元素，即使有序顺序表中相同的元素只保留一个。
⑴ 实验要求
① 根据输入的n个非递减的有序数据建立一个有序顺序表，并输出有序顺序表中各元素值。
② 删除有序顺序表中所有的重复元素，并显示删除后的有序顺序表中各元素值。
⑵ 核心算法提示
要在有序顺序表中删除重复的元素，首先就要抓住有序顺序表的特性：重复的元素总是在相邻的位置上，如：12，15，15，15，35，56，56，78。则删除重复元素后所得的有序表为：12，15，35，56，78。下面给出大致的操作步骤：从第1个元素开始，依次将它与后面相邻的元素进行比较，如果相等则将前面那个相等的元素从顺序表中删除；如果不相等，则继续往下比较，如此重复，直到最后一个元素为止。
⑶ 核心算法描述
Sqlist delSqlist(Sqlist L)
{int i=0,j;
while(i<L.length-1)
if (L.elem[i]==L.elem[i+1]) /*如果第i个及第i+1个相邻元素值相等*/
{ for (j=i+1;j<L.length;j++) /*将第i+1个元素及其之后的所有元素前移一个位地置，以达到删除第i个元素的目的*/
L.elem[j-1]=L.elem[j];
L.length--; /*有序顺序表的表长减1*/
}
else
i++;
return L;
}
2．编程实现一个简单学生成绩表的操作。
实验要求
此系统的功能包括：
① 查询：按特定的条件查找学生
② 修改：按学号对某个学生的某门课程成绩进行修改
③ 插入：增加新学生的信息
④ 删除：按学号删除已退学的学生的信息。
学生成绩表的数据如下：
学号 姓名 性别 大学英语 高等数学
2008001 Alan F 93 88
2008002 Danie M 75 69
2008003 Helen M 56 77
2008004 Bill F 87 90
2008006 Peter M 79 86
2008006 Amy F 68 75
要求采用顺序存储结构来实现对上述成绩表的相关操作。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_STR_LEN 20
#define MAX_STUDENT_NUM 10
typedef struct student{
int id;
char name[7];
char sex[5];
int English;
int Math;
}STUDENT;
int Insert(STUDENT student[],int num);
void PrintLine(STUDENT student[],int num);
int Search(STUDENT student[],int student_id);
int Delete(STUDENT student[],int student_id);
int main(void){
STUDENT a[MAX_STUDENT_NUM];
int res,num,student_id;
int command;
while(1){
printf("%s","1.插入学生信息\n2.删除学生信息\n3.查询学生信息\n4.显示学生信息\n5.exit\n");
scanf("%d",&command);
printf("\n");
fflush(stdin);
switch(command){
case 1:
printf("输出学生人数：");
scanf("%d",&num);
fflush(stdin);
if(num>MAX_STUDENT_NUM){
printf("Exceeds the maximum\n");
continue;
}
res=Insert(a,num);
if(res==2){
printf("success!\n");
}else{
printf("false!\n");
}
break;
case 2:
printf("输入学生学号：");
scanf("%d",&student_id);
fflush(stdin);
res=Search(a,student_id);
if(res==-1){
printf("the student is not exist\n");
}else{
Delete(a,res);
num=num-1;
}
break;
case 3:
printf("输入查询的学号：");
scanf("%d",&student_id);
fflush(stdin);
res=Search(a,student_id);
if(res==-1){
printf("the student is not exist\n");
}else{
printf("学号 姓名 性别 大学英语 大学数学\n");
printf("%d%9s%9s%17d%17d\n",
a[res-1].id ,a[res-1].name ,a[res-1].sex,a[res-1].English,a[res-1].Math);
}
break;
case 4:
PrintLine(a,num);
break;
case 5:
return 0;
default :
printf("input error!\n");
break;
}
}
return 0;
}
int Insert(STUDENT student[],int num){
int i;
int res;
for(i=0;i<=num-1;i++){
printf("input the student id:");
res=scanf("%d",&student[i].id);
fflush(stdin);
if(res==0){
printf("error!input again：");
res=scanf("%d",&student[i].id);
}
printf("input the student name：");
scanf("%s",&student[i].name);
printf("input the student sex:");
scanf("%s",&student[i].sex);
printf("input the student English：");
scanf("%d",&student[i].English);
printf("input the student Math：");
scanf("%d",&student[i].Math);
printf("已录入！\n");
fflush(stdin);
if(res==0){
printf("error!input again\n");
res=scanf("%d",&student[i].id);
}
}
return 2;
}
void PrintLine(STUDENT student[],int num){
int i;
if(num==0){
printf("the student array is null\n");
}else{
printf("学号 姓名 性别 大学英语 大学数学\n");
for(i=0;i<num;i++)
{
printf("%d%9s%9s%17d%17d",
student[i].id ,student[i].name ,student[i].sex,student[i].English,student[i].Math);
printf("\n");
}
}
}
int Search(STUDENT student[],int student_id){
int i;
for(i=0;i<=MAX_STUDENT_NUM;i++){
if(student[i].id==student_id){
return i+1;
}
}
return -1;
}
int Delete(STUDENT student[],int student_id){
int j;
for(j=student_id;j<=MAX_STUDENT_NUM;j++){
student[j-1].id=student[j].id;
strcpy(student[j-1].name,student[j].name);
strcpy(student[j-1].sex,student[j].sex);
student[j-1].English=student[j].English;
student[j-1].Math=student[j].Math;
}
printf("success!\n");
return 1;
}
一站式虚拟内容创作平台，激发创意，赋能创作，进入R空间，遇见同道，让优质作品闪耀发光。
更多推荐
11
0- 0
已为社区贡献1条内容
所有评论(0)