实验一 顺序表_建立一个线性表,首先依次输入数据元素

数据结构实验报告

1. 问题描述及分析

问题描述：完成顺序表软工具箱的创建，并验证课本例2-1、2-2。

分析：首先建立一个顺序表软工具箱，然后根据题目要求，能够在顺序表的任意位置插入、删除结点以及确定某一元素在链表中的位置。

1. 建立顺序表功能

建立一个顺序表，确定DataType与MaxSize。

1. 初始化

将顺序表初始化。

1. 插入功能

输入的形式与输入值的范围：输入一个表示插入位置且小于MaxSize的非负整数和一个表示元素值的形式为DataType的数。

输出的形式：如果输入的参数不合法或顺序表已满，则显示参数错误信息。

返回值：插入成功返回1，插入失败返回0。

测试数据：在建立顺序表且DataType为int、maxsize为10的基础上，做以下测试：

1. 输入3 8，运行成功。
2. 输入15 24，显示参数错误信息。
3. 输入5 n,显示参数错误信息。
4. 若顺序表已满，显示参数错误信息。

1. 删除功能

输入的形式与输入值的范围：输入一个表示删除位置且小于MaxSize的非负整数。

输出的形式：如果输入的参数不合法或顺序表为空，则显示参数错误信息。

返回值：删除成功返回1，删除失败返回0。

测试数据：在建立顺序表且DataType为int、MaxSize为10的基础上，做以下测试：

1. 输入12，显示参数错误信息。
2. 输入1，运行成功。
3. 若顺序表为空，显示参数错误信息。

1. 查找功能

输入的形式与输入值的范围：输入一个表示查找位置且小于MaxSize的非负整数。

输出的形式：如果输入的参数不合法，则显示参数错误信息。

返回值：查找成功返回1，查找失败返回0。

测试数据：在建立顺序表且DataType为int、MaxSize为10的基础上，做以下测试：

a)输入12，显示参数错误信息。

b)输入1，运行成功。

2.概要设计

（1）为了实现上述程序功能，先定义一个简化的包含抽象数据类型的头文件

typedef struct
 
{
 
DataType list[MaxSize];
 
int size;
 
}SeqList;
 
void ListInitiate(SeqList *L);//初始化顺序表
 
int ListInsert(SeqList *l,int i,DataType x);//插入元素
 
int ListDelete(SeqList *l,int i,DataType *x);//删除元素
 
int ListGet(SeqList,int i,DataType *x);//取元素
 
int ListLength(SeqList L);//返回当前元素个数

（2）程序包含的模块

主函数main()

初始化顺序表函数 ListInitiate(SeqList *L);

插入元素函数ListInsert(SeqList *l,int i,DataType x);

删除元素函数ListDelete(SeqList *l,int i,DataType *x);

提取元素函数ListGet(SeqList,int i,DataType *x);

当前元素个数函数ListLength(SeqList L);

（3）主函数的伪码

main(){
 
    定义一个顺序表myList;
 
    初始化myList;
 
    建立myList;
 
    删除某一元素;
 
    循环以下处理，直至结束：
 
{
 
取顺序表元素并输出;
 
}
 
}

3.详细设计

结合概要设计中定义的包含抽象类型的头文件,进行数据结构设计和算法设计。

1. 数据结构

typedef int DataType;
 
#define MaxSize 100
 
typedef struct
 
{
 
DataType list[MaxSize];
 
int size;
 
}SeqList;

1. 基本操作的伪码算法

初始化顺序表

void ListInitiate(SeqList *L)
 
{
 
>size=0;
}

返回当前元素个数

int ListLength(SeqList L)
 
{
 
return L.size;
 
}

插入元素

int ListInsert(SeqList *L,int i,DataType x)
 
{
 
int j;
 
if(L->size>=maxsize)
 
{
 
printf("FULL\n");
 
return 0;
 
}
 
else if(i<0||i>L->size)
 
{
 
printf("i ERROR\n");
 
return 0;
 
}
 
else
 
{
 
for(j=L->size;j>i;j--)
 
{
 
L->list[j]=L->list[j-1];
 
L->list[i]=x;
 
L->size++;
 
return 1;
 
}
 
}

删除元素

int ListDelete(SeqList *L,int i,DataType *x){
 
    int j;
 
    if(L->size<=0){
 
    printf("EMPTY\n");
 
return 0;
 
}
 
    else if(i<0||i>L->size-1){
 
    printf("i ERROR\n");
 
return 0;
 
}
 
    else{
 
    *x=L->list[i];
 
    for(j=i+1;j<=L->size-1;j++)
 
L->list[j-1]=L->list[j];
 
    L->size--;
 
    return 1;
 
}
 
}

取元素

int ListGet(SeqList L,int i,DataType *x){
 
    if(i<0||i>L.size-1){
 
printf("i ERROR\n");
 
return 0;   
 
}
 
    else{
 
*x=L.list[i];
 
    return 1;
 
}
 
 
 
}

实验内容：

[例2-1]编程实现如下任务: 建立一个线性表，首先依次输入数据元素1，2，3，...,10。然后删除数据元素5,最后依次显示当前线性表中的数据元素。假设该线性表的数据元条个数在最坏情况下不会超过100个。要求使用顺序表。

实验代码：

#include<stdio.h>
 
#include<stdlib.h>
 
#define MaxSize 100   //定义maxsize为100
 
typedef int DataType;//定义DataType为int型í#include "SeqList.h"//包含SeqList.h头文件
 
void main(void)
 
{
 
    SeqList myList;
 
    int i,x;
 
    ListInitiate(&myList);//初始化函数调用
 
    for(i=0;i<10;i++)     //插入10个数据元素
 
         ListInsert(&myList,i,i+1);//插入函数调用（依次插入1，2，3...）
 
    ListDelete(&myList,4,&x);//删除函数调用
 
    //显示循序表当前数据元素
 
    for(i=0;i<ListLength(&myList);i++)//当前元素个数函数调用去
 
    {
 
         ListGet(&myList,i,&x);//取元素函数调用
 
         printf("%d   ",x);//显示数据元素
 
    }
 
    system("pause");
 
}

[例2-2]编程实现如下任务: 建立一个如表2-1所示的学生情况表，要求先依次输入数据元素，然后依次显示当前表中的数据元素。假设该表数据元素个数在最坏情况下不会超过100个。要求使用顺序表。

实验代码：

#include<stdio.h>
 
#include<stdlib.h>
 
#include "SeqList1.h"
 
void main(void)
 
{
 
    SeqList myList;
 
    int i;
 
    Student x[3] = {{2000001, "张三" , "男" , 20},
 
                    {2000002, "李四" ,"男" , 20},
 
                    {2000003, "王五" , "女" , 20}};
 
    Student s;
 
    ListInitiate(&myList) ;
 
    ListInsert(&myList , 0 , x[0]);
 
    ListInsert(&myList , 1 , x[1]);
 
    ListInsert(&myList , 2 , x[2]);
 
    for(i=0 ; i<ListLength(myList);i++)
 
    {
 
         ListGet(myList , i , &s);
 
         printf("%d %s %s %d \n",s.number,s.name,s.sex,s.age);
 
    }
 
    system("pause");
 
}

1. 调试与分析

 

该结果与预期结果一致

1. 使用说明

程序执行过程如下：

1. 输出1 2 3 4 6 7 8 9 10
2. 输出2000001  张三  男  20

2000002  李四  男  21

2000003  王五  女  22

1. 总结

经过调试与测试，实验结果与测试预期一致。顺序表是计算机内存以数组形式保存的线性表，是指用一组地址连续的存储单元依次存储数据元素的线性结构。线性表采用的顺序存储方式存储就称之为顺序表。通过本次实验，掌握了定义线性表的顺序存储类型，加深了对顺序存储结构的理解，进一步巩固和理解了顺序表的基本操作，如建立、查找、插入和删除等。同时，也体会到顺序存储结构的缺点：在插入或删除操作时，需要移动大量的元素，且长度相对固定，当表中数据元素个数较多且变化较大时，操作复杂。