线性表的顺序存储结构和实现

石家庄经济学院

实 验 报 告

学 院: 数理学院

专 业: 数学与应用数学

班 级

学 号: XXXXXXXX

姓 名: XXXXXX

信息工程学院计算机实验中心制

实验题目：线性表的顺序存储结构和实现

一、实验内容

1.熟悉C 语言的上机环境，掌握C 语言的基本结构。

2.会定义线性表的顺序存储结构。

3.熟悉对顺序表的一些基本操作(建表、插入、删除等)和具体的函数定义。

二、实验目的

1、掌握顺序存储结构的特点 2. 掌握顺序存储结构的常见算法

3、掌握顺序存储结构的特点，了解、掌握并实现顺序表的常用的基本算法。

三、实验的内容及完成情况

1. 需求分析

(1)线性表的抽象数据类型ADT的描述及实现。

本实验实现使用Visual c++6.0实现线性表顺序存储结构的表示及操作。具体实现要求：

(2)完成对线性表顺序存储结构的表示和实现。

(3)实现对线性表的建立和初始化。

(4)实现对线性表插入和删除部分元素。

2．概要设计

抽象数据类型线性表的定义：

ADT {

数据对象：D={ai |ai∈ ElemSet,i=1,2,……,n,n≥0}

数据关系：R1={|ai-1,ai∈ D,i=2,……,n}

基本操作：

InitList_sq(&L)

操作结果：构造一个空的线性表L。

ListInsert_sq(&L,i,e)

初始条件：线性表L已存在,1≤i≤L.Length+1。

操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1。

ListDelete_sq(&L,i,&e)

初始条件：线性表L已存在且非空,1≤i≤L.Length。

操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。

input()

} ADT;

3．详细设计

（1）抽象数据类型线性表顺序存储结构的表示和实现

//线性表结构类型

#define LIST_INIT_SIZE 100//线性表存储空间的初始分量

#define LISTINCREMENT 10//线性表存储空间的分配增量

typedef struct

{

elemtype *elem;//存储空间基址

int length;//当前线性表的长度

int listsize;//当前分配的存储容量（以sizeof(elemtype)为单位）

}sqlist;

//建立线性表

Status InitList_sq(sqlist &L)

{//构造一个空的线性表

L.elem=(elemtype *)malloc(LIST_INIT_SIZE*sizeof(elemtype)); if(!L.elem) exit(OVERFLOW);//存储分配失败 L.length=0; //空表长度为0 L.listsize=LIST_INIT_SIZE;//初始存储容量 return OK;

}//InitList_sq

//在线性表指定位置插入指定元素

Status ListInsert_sq(sqlist &L,int i,int e)

{ //在线性表L中第i个位置前插入新的元素e

//i的合法值1

if(iL.length+1) return ERROR;//i值不合法

if(L.length>=L.listsize)//当存储空间已满，增加分配

{ newbase=(int*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(int)); if(!newbase) exit(OVERFLOW);//存储分配失败 L.elem=newbase; //新基址 L.listsize+=LISTINCREMENT; //增加存储容量 } q=&(L.elem[i-1]); //q为插入位置 for(p=&(L.elem[L.length-1]);p>=q;--p) *(p+1)=*p; //插入位置及之后的元素后移 *q=e; //插入e ++L.length;//表长增加1 return OK;

}//ListInsert_sq

//在线性表指定位置删除元素

Status ListDelete_sq(sqlist &L,int i,int &e)

{ //在顺序表L中删除第i个元素,并用e返回其值

//i的合法值为1

if(iL.length) return ERROR;//i值不合法 p=&(L.elem[i-1]);//p为被删除元素的位置 e=*p; //被删除元素复制给e q=L.elem+L.length-1;//表尾元素的位置 for(++p;p

}//ListDelete_sq

（2）主函数的伪码算法

void main()//主函数

{

printf("\t\t》》》》》》》>>数据结构实验一

printf("\t\t*********线性表的顺序存储结构和实现***********\n");

do

{

menu();

printf("\t\t★请按提示输入指令:");

scanf("%d",&a); switch(a) {//调用各函数 case 1: input(); break; case 2: if(ListInsert_sq(L,i,e)==1) output(); else printf("☆插入位置不合法,请重新输入~\n"); break; case 3: if(ListDelete_sq(L,i,e)==1) { output(); printf("\t\t☆所删除元素为：%d\n",e); } else printf("☆删除位置不合法，请重新输入~\n"); break; case 0: printf("\t\t☆谢谢您的使用,再见 (*^__^*)! \n"); return; default : printf("\t\t☆输入有误,请重新输入 (*^__^*) \n"); }

}while(a!=0);

}

4. 调试分析

(1) 调试过程中出现的问题

1.未定义某些变量以及Status和elemtype的类型。

2.某些变量的作用范围广，应定义为全局变量。

3.定义与引用名称较长的变量时由于部分字母大小写不一致出现低级错误。

4.程序执行界面有点乱，应在程序中设计好界面，增加程序执行界面的美感。

(2) 经验和体会

得到的经验：

1. 编写程序前应先了解算法，再把算法合理的编写成可操作的程序。

2. 一定要在程序中添加合理的说明语句，增加程序的可读性，也为检查程序正确与否提供方便。

3. 要多用输出语句输出程序执行时的提示性语句，增加程序的可操作性。

4. 合理的利用返回值检查程序的错误是快捷的方法，值得提倡。

5. 执行删除操作时，所删除元素后的元素全部前移，尝试将前移的元素个数+1即把后面的空值赋

值给最后一个元素，节省了存储空间彻底完成了删除操作！

得到的体会：

1. 多思考、多尝试能更好的完成程序的编写。

2. 算法是程序编写的灵魂，选择好算法有助于编写程序。

3. 编写程序时细心才能少出错！

(3) 算法的时空分析和改进

1.线性表的插入平均时间复杂度：T(n)=O(n/2) ;

2.线性表的删除平均时间复杂度：T(n)=O（(n-1)/2） ;

删除操作将后面元素前移，未彻底删除最后的元素，浪费了一定的存储空间。

改进：可将线性表的顺序存储结构调整为链式存储结构。将前移的元素个数+1即把后面的空值赋值给最后一个元素，节省存储空间。

5．用户使用说明

打开可执行程序，即Visual c++6.0环境下，参照用户选择界面提示即可使用本程序

6．测试结果

程序具体执行如下：

运行程序，进入操作界面：

初始化线性表元素：

实现插入操作：

实现删除操作：

演示操作完毕，退出程序！

插入和删除均可以多次操作，按提示语句执行即可！

7．附录

源程序如下：

#include//头文件

#include

#include

#define LIST_INIT_SIZE 100//线性表存储空间的初始分量

#define LISTINCREMENT 10//线性表存储空间的分配增量

#define OVERFLOW -2//宏定义

#define OK 1//宏定义

#define ERROR 0//宏定义

typedef int elemtype;//类型定义

typedef int Status;

typedef struct

{

elemtype *elem;//存储空间基址

int length;//当前线性表的长度

int listsize;//当前分配的存储容量（以sizeof(elemtype)为单位）

}sqlist;

int *p,*q;//定义全局变量

int n,i,e,a;//定义全局变量

sqlist L;//定义结构体L

//自定义函数的声明

Status InitList_sq(sqlist &L);//建表

Status ListInsert_sq(sqlist &L,int i,int e);//插入元素函数

Status ListDelete_sq(sqlist &L,int i,int &e);//删除元素函数

void menu();//菜单函数

void input();//初始化线性表的函数

void output();//显示线性表元素的函数

void main()//主函数

printf("\t\t》》》》》》》>>数据结构实验一

printf("\t\t*********线性表的顺序存储结构和实现***********\n");

do {

menu();

printf("\t\t★请按提示输入指令:");

scanf("%d",&a); switch(a) {//调用各函数 case 1: input(); break; case 2: if(ListInsert_sq(L,i,e)==1) output(); else printf("☆插入位置不合法,请重新输入~\n"); break; case 3: if(ListDelete_sq(L,i,e)==1) { output(); printf("\t\t☆所删除元素为：%d\n",e); } else printf("☆删除位置不合法，请重新输入~\n"); break; case 0: printf("\t\t☆谢谢您的使用,再见 (*^__^*)! \n"); return; default : printf("\t\t☆输入有误,请重新输入 (*^__^*) \n");

}

}while(a!=0);

}

Status InitList_sq(sqlist &L)

{//构造一个空的线性表

L.elem=(elemtype *)malloc(LIST_INIT_SIZE*sizeof(elemtype)); if(!L.elem) exit(OVERFLOW);//存储分配失败 L.length=0; //空表长度为0 L.listsize=LIST_INIT_SIZE;//初始存储容量

return OK;

}//InitList_sq

Status ListInsert_sq(sqlist &L,int i,int e)

{ //在线性表L中第i个位置前插入新的元素e

//i的合法值1

int *newbase; printf("\t\t☆请输入要插入的位置："); scanf("%d",&i); printf("\t\t☆请输入要插入的元素："); scanf("%d",&e); if(iL.length+1) return ERROR;//i值不合法 if(L.length>=L.listsize)//当存储空间已满，增加分配 {

if(!newbase) exit(OVERFLOW);//存储分配失败 L.elem=newbase; //新基址 L.listsize+=LISTINCREMENT; //增加存储容量 } q=&(L.elem[i-1]); //q为插入位置 for(p=&(L.elem[L.length-1]);p>=q;--p) //插入位置及之后的元素后移 *(p+1)=*p; *q=e;//插入e ++L.length;//表长增加1

return OK;

}//ListInsert_sq

Status ListDelete_sq(sqlist &L,int i,int &e)

{ //在顺序表L中删除第i个元素,并用e返回其值

//i的合法值为1

printf("\t\t☆请输入要删除的位置："); scanf("%d",&i); if(iL.length) return ERROR;//i值不合法 p=&(L.elem[i-1]);//p为被删除元素的位置 e=*p; //被删除元素复制给e q=L.elem+L.length-1;//表尾元素的位置 for(++p;p

return OK;

}//ListDelete_sq

void menu()

{//菜单函数

printf("\t\t============= 请按提示输入指令================\n");

printf("\t\t------------★1输入线性表初始值---------------\n"); printf("\t\t------------★2向线性表插入元素---------------\n");

printf("\t\t------------★3删除线性表元素-----------------\n");

printf("\t\t------------★0退出系统-----------------------\n");

}//menu

void input()

{//初始化线性表元素

if(InitList_sq(L)!=1) { printf("☆分配存储空间失败!!!"); return; } printf("\t\t☆请输入线性表元素的个数："); scanf("%d",&n);

printf("\t\t☆请输入线性表的%d个元素：",n); for(i=0;i

output();//调用输出函数，查看线性表元素

}//input

void output()

{

printf("\t\t☆操作后线性表内元素为：\n\t\t");

for(i=0;i

printf("\n");

}//output

四、实验总结

1.学会了线性表顺序存储结构的各项操作。

2.熟练了线性表顺序存储结构实现的算法和程序编写。

3.懂得了return OK存在的意义并合理的利用返回值。

4.学会了用返回值检查程序的错误之处，避免了盲目的查找错误。

5.合理输出运行程序的提示性语句，可以增强程序的可读性和可操作性。

6.在定义和使用同一变量或者函数等名称时尽量使用复制粘贴，可以避免字母大小写不一致等原因出现的低级错误。

7. 执行删除操作时，所删除元素后的元素全部前移，将前移的元素个数+1即把后面的空值赋值给原来的最后一个元素，可以节省存储空间！

8.编写程序时应考虑算法的时间和空间复杂度，选择最优的算法编写程序。

9.程序编写的规范化和视觉美感同程序本身一样重要！

五、成绩