数据结构实验1.1： 顺序表的操作及其应用

---

一、实验目的

1．掌握使用C++/VC环境上机调试程序的基本方法；
2．掌握线性表顺序存储的概念，加深对顺序存储数据结构的理解；
3．掌握顺序表的基本运算及简单应用问题，逐步培养解决实际问题的编程能力。

二、注意事项

1．在磁盘上创建一个目录，专门用于存储数据结构实验的程序。
2．建议实验者不要过分依赖本书提供的算法或参考程序，实验者对每一个实验题目可独立进行算法分析与设计，独立设计完整的上机程序。只有经过严格的训练，才能显著提高算法分析与设计能力、程序设计能力，更有助于《数据结构》课程知识体系的理解和掌握。

三、实验内容

（一）问题描述

设有线性表（34，12，45，64，28，36，45），采用顺序存储结构。编程实现有关顺序表的下列基本操作：
（1）初始化一个空的顺序表；
（2）在顺序表的第i个位置上插入一个新元素；
（3）在顺序表中查找指定值的元素位置；
（4）删除顺序表中的第i个元素；
（5）删除顺序表中指定值的元素；
（6）输出顺序表中的所有元素值。

（二）基本要求

（1）采用动态分配方式设计顺序表的存储结构；
（2）用反复执行插入操作的方式建立线性表；
（3）每完成一个步骤，必须及时输出顺序表中的所有元素，便于观察操作结果；
（4）完善参考程序，并在参考程序中的下划线处填上适当的语句或文字；
（5）设计测试用例，上机调试、测试完善后的参考程序，保存和打印测试结果，对测试结果进行分析，包括算法效率分析；

四，操作步骤

（一）使用visual studio集成环境编写程序

1.双击启动程序。

2.选择“新建项目”。

3.选择“空项目”——输入“项目名称”——单击确认按钮。

4.添加项目文件，右击“源文件”——选择“添加”——单击“新建项”。

5.这里选择C++——输入文件名称（不要输入中文，建议输入英文或拼音）——单击“添加”按钮。

6.在C++文件中编写代码，可以先自己编写，在与示例代码进行对比。（实例代码在五，示例代码）。

7.右击编写的文件——单击编译。

8.查看编译结果，成功则如下图所示，失败的话会给出出错位置，进行修改就可以重新编译。

五，示例代码

#define OVERFLOW -1
#define OK 1
#define ERROR 0
#define MAXSIZE 6   		//空间初始分配量，为了检验空间扩展，初值取小一点
#define INCREMENT 10	//空间分配增量
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>typedef int Status;
typedef int ElemType;
typedef struct {ElemType *elem;     		//存储空间基址int length;		  		//当前顺序表中实际元素的个数int listsize;	 			//当前分配的存储容量
} SqList;Status InitList(SqList &L)		// 初始化顺序表
{L.elem=(ElemType *)malloc(MAXSIZE*sizeof(ElemType));if( !L.elem )  exit(OVERFLOW); // 1. 判断内存分配是否成功L.length=0;L.listsize = MAXSIZE; // 2. 初始化当前分配的存储容量return OK;
}Status  InsertList (SqList &L, int i, ElemType e) {//将新元素e插入到顺序表L的第i个位置上if ( i < 1 || i > L.length + 1 )  return  ERROR; // 3. 判断插入位置是否合法ElemType  *p;int  j;if( L.length >= L.listsize ) {		//若顺序表已满，则需扩充空间p=(ElemType *)realloc(L.elem, (L.listsize+INCREMENT)*sizeof(ElemType));if (!p) exit (OVERFLOW);L.elem=p;L.listsize += INCREMENT;}for(j = L.length-1; j>=i-1; --j) L.elem[j+1]=L.elem[j];L.elem[i-1] = e; // 5. 插入新元素L.length++;return OK;
}// InsertList void PrintList(SqList L)				// 输出顺序表元素
{int  i;for(i=0; i < L.length; i++) // 6. 遍历顺序表printf("%d  ", L.elem[i]);printf("\n");
}int SearchList(SqList L, ElemType e)
// 在顺序表L中查找值为e的第一个元素，查找成功返回元素的位置，失败返回-1
{int i;for(i=0; i<L.length; i++)if( L.elem[i] == e )   		// 7. 找到相同的元素，返回位置return i;return -1;
}int Del_List1(SqList &L, ElemType e)
// 在顺序表L中删除值为e的第一个元素，删除成功返回元素位置，失败则返回-1
{int i, j;for(i=0; i<L.length; i++)if(L.elem[i]==e)              		// 找到相同的元素break;if(i<L.length){for(j=i; j<L.length -1; j++)			// 删除L.elem[j] = L.elem[j+1]; // 8. 元素前移L.length--;return i;}return -1;
}Status  Del_List2(SqList &L, int i, ElemType &e)
// 在顺序表L中删除第i个元素，被删元素用参数e带回
{if ( i < 1 || i > L.length ) return  ERROR; // 9. 判断删除位置是否合法int  j;e=L.elem[i-1];for(j=i; j<L.length; j++) L.elem[j-1] = L.elem[j]; // 10. 元素前移--L.length;return OK;
}void main()
{SqList  LL;ElemType x;int r,i;printf("(1)初始化顺序表……\n");if( !InitList(LL) )  return;printf("  初始化成功！\n");printf("(2)顺序表的插入操作……\n");while(1)      {printf("  输入插入元素的值(0:结束)=>");scanf("%d", &x);if( x == 0 )  break;printf("    输入插入位置：");scanf("%d", &r);InsertList(LL, r, x); // 12. 调用插入函数printf("  线性表输出：");PrintList(LL); // 13. 输出顺序表}printf("(3)顺序表上的查找操作……\n");while(1)      //在顺序表中查找指定值的元素，输出该元素所在位置{printf("  输入查找元素的值(0:结束)=>");scanf("%d", &x);if(x==0)break;r= SearchList(LL, x); // 14. 调用查找函数if(r<0)printf("    没找到！\n");elseprintf("  有符合条件的元素，位置为：%d\n", r+1);}printf("(4)顺序表中指定元素值的删除操作……\n");while(1)        //在顺序表中删除指定值的元素{printf("  输入删除元素的值(0:结束)=>");scanf("%d", &x);if(x==0)break;r= Del_List1(LL, x); // 15. 调用删除函数if(r<0)printf("  没找到\n");else {printf("  删除成功！被删元素的位置是：%d\n  线性表输出：", r+1);PrintList(LL);}}printf("(5)顺序表中指定元素位置的删除操作……\n");while(1) {printf("  输入删除元素的位置(0:结束)=>");scanf("%d", &r);if(r==0)break;if( r < 1 || r > LL.length )printf("  位置越界!\n");else {ElemType deleted;Del_List2(LL, r, deleted);printf("  线性表输出：");PrintList(LL);}}
}

六，运行效果

1.单击调试按钮，运行程序。

2.成功运行效果图。

3.按照需求，调试程序。