实验1(1) 线性表-顺序表及其应用-16

实验一 线性表

班级: 姓名: 学号：

一、实验目的

1．掌握线性表的顺序存储结构的含义；

2．掌握动态内存分配方式和顺序表的类型定义；

3．掌握顺序表的基本操作的实现算法； 4．通过上机实践加强利用数据结构解决实际问题的能力。

二、实验要求

1．实验前做好充分准备，包括复习第一章、第二章所学内容，事先预习好本次实验内容；

2．实验时记录实验结果，按要求完成各题； 3．实验结束后，给出实验总结与分析并及时给出本次实验的实验报告。

三、实验题目与要求

1．实验题目一：顺序表的类型定义及其相关操作算法的实现

要求：编程实现顺序表的类型定义及顺序表的初始化操作、插入操作、删除操作、取元素操作、输出操作等，并对其进行验证。

2．实验题目二：顺序表的应用实例

结合课上讲过的顺序表的逆向删除操作的例子以及顺序表的逆置问题，编程实现。

四、实验内容

本指导书所给出的示例程序均为DEV C++环境下完成的，若使用其它C开发环境，则部分语句要进行少许修改。

1．实验题目一：顺序表的类型定义及其相关操作算法的实现

#include \

#include \ //预定义常量及类型

#define OK 1 #define ERROR 0

#define OVERFLOW -2 #define TRUE 1 #define FALSE 0 typedef int Status;

//顺序表类型及其基本操作函数的定义

#define ListSpaceIncr 20 typedef int LElemType; typedef struct SqList { LElemType *base;

int length; int listSize;

}SqList; //SqList类型为顺序表类型 Status initList(SqList &L, int initSize) //初始化操作函数定义 {

L.base=(LElemType*)malloc(InitSize*sizeof(LElemType));//申请初始指定大小的存储空间

if(!L.base) return(OVERFLOW); L.length=0;

L.listSize=InitSize; return OK; }

Status listInsert(SqList &L, int i, LElemType e){ //顺序表的插入操作

LElemType *newBase; int j;

if(i<1||i>L.length+1) return ERROR;

if( L.length==L.listSize ){ //补齐代码，若存储空间已满，则追加存储空间 newBase=(LElemType*)realloc(L.base,

(L.listSize+ListSpaceIncr)*sizeof(LElemType) );

if(!newBase) return OVERFLOW;

L.base=newBase;

L.listSize+=ListSpaceIncr; }

for(j= L.length-1 ; j>= i-1 ; j--) L.base[j+1]=L.base[j]; L.base[i-1]=e; L.length++;

return OK; }

Status listDelete(SqList &L, int i, LElemType &e){ //顺序表的删除操作 int j;

if(i<1||i>L.length) return ERROR; e=L.base[i-1];

for(j= i ; j< L.length ; j++) L.base[j-1]=L.base[j]; L.length--; return OK; }

}

L.length= j; }

任务：补齐上述算法中的代码，然后编写主函数实现上述算法。（提示：首先创建一个长度为n的顺序表，向顺序表中输入n个元素，然后调用deleteElem算法删除掉给定区间的元素，最后再输出顺序表L，看是否删除成功！）

#include \#include \

typedef int Status;

//顺序表类型及其基本操作函数的定义 #define ListSpaceIncr 20 typedef int LElemType; typedef struct {

LElemType *base; int length; int listsize; } SqList;

void deleteElem(SqList &L, LElemType x, LElemType y){

//删除顺序表L中所有值在区间[x, y]内的元素 int i=0, j=0; while(i

if( !(L.base[i]>=x&&L.base[i]<=y)){ L. base [j]=L. base [i]; j++ ; }

i++; 2．实验题目二：顺序表的应用实例

} （1）设顺序表L中的数据元素为数值类型，下述

L.length= j; 算法用来实现删除顺序表L中所有值在[x, y]之间的元

} 素。

void deleteElem(SqList &L, LElemType x, //任务：补齐上述算法中的代码，然后编写主函LElemType y){ 数实现上述算法。（提示：首先创建一个长度为n的顺

//删除顺序表L中所有值在区间[x, y]内的元素 序表，向顺序表中输入n个元素，然后调用deleteElem int i=0, j=0; 算法删除掉给定区间的元素，最后再输出顺序表L， while(i=x&&L.base[i]<=y ) ){ int main() L. base [j]=L. base [i]; { j++ ; int n,x,y; } SqList La; i++;

void listOutput(SqList L) //顺序表输出操作 { int i;

for(i=0;i

printf(\ printf(\}

int main() { SqList La; int i,e;

initList(La,100);

for (i=0;i<5;i++) listInsert(La,i+1,2*i); listOutput(La);

listInsert(La,1,999); listOutput(La); listInsert(La,4,888); listOutput(La); listInsert(La,La.length+1,111); listOutput(La);

listDelete(La,3,e); listOutput(La); listDelete(La,1,e); listOutput(La); system(\ return 0; }

程序运行结果：

int a,i = 0; int cnt = 0;

printf(\请输入元素的个数及x，y\\n\ scanf(\ printf(\请输入元素\\n\

La.base = (int *)malloc(sizeof(int) * cnt); La.length = 0;

while(i < cnt){ scanf(\ La.base[i++] = a; La.length++; } deleteElem(La,x,y);

for(i=0;i

printf(\ printf(\

system(\ return 0; }

程序运行结果：

（2）设顺序表L中有n个元素，且其元素为整数类型，设计一个算法，将顺序表L中的这n个元素就地逆置。如果原来的顺序表L如下所示（n=8时）。 length=8 0 1 2 3 4 5 6 7 base 8 10 95 23 41 6 7 9 listSize=8 L

则执行完逆置算法后，顺序表L如下图所示。

length=8 0 1 2 3 4 5 6 7 base 9 7 6 41 23 95 10 8 listSize=8

L

要求：给出实现逆置功能的算法，然后在主函

数中调用该算法实现逆置，最后输出逆置后的顺序表L。

完整程序：

#include #include \typedef int LElemType; typedef struct {

LElemType *base; int length; int listsize; } SqList;

void ReverseList(SqList *L) {

int i, temp;

int n = L->length;

for(i = 0; i < n/2; i ++) {

temp = L->base[i];

L->base[i] = L->base[n-1-i]; L->base[n-1-i] = temp; } }

int main() {

int n,x,y; SqList La;

int a,i = 0; int cnt = 0;

printf(\请输入元素的个数\\n\ scanf(\

printf(\请输入元素\\n\

La.base = (int *)malloc(sizeof(int) * cnt);

La.length = 0;

while(i < cnt){ scanf(\ La.base[i++] = a; La.length++; }

printf(\原顺序表为：\ for(i=0;i

printf(\ printf(\

ReverseList(&La);

printf(\逆置后的顺序表为：\ for(i=0;i

printf(\ printf(\}

程序运行结果：

五、实验总结

成绩：