线性表逆置(顺序表)实验报告

实验一：线性表逆置(顺序表)实验报告

(一) 问题的描述： 实现顺序表的逆置算法

(二) 数据结构的设计： 顺序表是线性表的顺序存储形式，因此设计如下数据类型表示线性表： typedef struct

{

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

int length; /* 当前长度 */

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

}SqList;

(三) 函数功能、参数说明及概要设计：

1. 函数 Status InitList(SqList *L) 功能说明：实现顺序表 L 的初始化 算法设计：为顺序表分配一块大小为 LIST_INIT_SIZE 的储存空间

2. 函数 int ListLength(SqList L) 功能说明：返回顺序表 L 长度 算法设计：返回顺序表中的

length 变量

3. 函数 Status ListInsert(SqList *L,int i,ElemType e)

功能说明：将元素 e插入到顺序表L中的第i个节点

算法设计：判断顺序表是否已满，已满则加空间，未满则继续，将元素 e插入到第i个

元素之前，并将后面的元素依次往后移

4. 函数 Status ListTraverse(SqList L,void(*vi)(ElemType*))

功能说明：依次对 L 的每个数据元素调用函数 vi()

算法设计：依次对 L 的每个数据元素调用函数 vi()

5. 函数 void Exchange(SqList *L)

功能说明：实现顺序表 L 的逆置

算法设计：用 for 循环将顺序表 L 中的第 i 个元素依次与第( i+length )个元素交换

6. 函数 void print(ElemType *c)

功能说明：打印元素 c

算法设计：打印元素 c

2.

(四) 具体程序的实现

/* 程序名 */

#include

#include

#include /* malloc() 等 */

#include /* INT_MAX 等 */

#include /* EOF(=AZ 或 F6),NULL */

#include /* atoi() */

#include /* eof() */

#include /* floor(),ceil(),abs() */

#include /* exit() */

/* 函数结果状态代码 */

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define INFEASIBLE -1

/* #define OVERFLOW -2 因为在 math.h中已定义 OVERFLOW 的值为3,故去掉此行 */

typedef int Status; /* Status 是函数的类型 ,其值是函数结果状态代码，如 OK 等 */ typedef

int Boolean; /* Boolean 是布尔类型 ,其值是 TRUE 或 FALSE */

typedef int ElemType;

/* 线性表的动态分配顺序存储结构 */

#define LIST_INIT_SIZE 10

#define LISTINCREMENT 2

typedef struct

{

ElemType *elem;

int length;

int listsize; //

}SqList;

/* 顺序表示的线性表的基本操作 */

Status InitList(SqList *L) /* 算法 2.3 */

{ /* 操作结果：构造一个空的顺序线性表 */

(*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;

} // 线性表存储空间的初始分配量

// 线性表存储空间的分配增量

// 存储空间基址

// 当前长度

当前分配的存储容量 (以 sizeof(ElemType) 为单位 )

Status DestroyList(SqList *L)

{ /* 初始条件：顺序线性表 L 已存在。操作结果：销毁顺序线性表 L */

free((*L).elem);

(*L).elem=NULL;

(*L).length=0;

(*L).listsize=0;

return OK;

}

int ListLength(SqList L)

{ // 初始条件：顺序线性表 L 已存在。操作结果： 返回 L 中数据元素个数

return L.length;

}

Status ListInsert(SqList *L,int i,ElemType e) // 算法 2.4

{ //初始条件：顺序线性表 L已存在，1 < i < ListLength(L)+1

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

ElemType *newbase,*q,*p;

if(i<1||i>(*L).length+1) // i 值不合法

return ERROR;

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

{

newbase=(ElemType *)realloc((*L).elem,((*L).listsize+LISTINCREMENT)*sizeof(ElemType));

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;

}

Status ListTraverse(SqList L,void(*vi)(ElemType*))

{ /* 初始条件：顺序线性表 L 已存在

操作结果：依次对 L的每个数据元素调用函数 vi()。一旦vi()失败，则操作失败

vi()的形参加& ,表明可通过调用 vi()改变元素的值 */

ElemType *p;

int i;

p=L.elem;

for(i=1;i<=L.length;i++)

vi(p++);

printf("\n");

return OK;

}

/* 逆置链表的程序 */

void change(SqList *L) /* 逆置算法 */

{

ElemType e;

int L_len;

int i;

L_len=ListLength(*L); /* 求线性表的长度 */ for(i=0;i<=L_len/2;i++)

{

e=*((*L).elem+i); *((*L).elem+i)=*((*L).elem+L_len-i-1); *((*L).elem+L_len-i-1)=e;

}

}

void print(ElemType *c)

{

printf("%d ",*c);

}

main()

{

SqList L;

Status i;

ElemType e;

int j;

i=InitList(&L);

if(i==1)

{/* 创建空表 L 成功 */ printf(" 请输入 5 个数字： "); for(j=1;j<=5;j++)

{

scan f("%d", &e); i=List In sert (&L,j,e);

}

}

printf("逆置前的表：L= "); /*输出表L的内容*/

ListTraverse(L,pri nt);

cha nge(&L);

printf(”逆置后的表：L= "); /*输出新表L的内容*/ ListTraverse(L,pri nt);

}

(五) 主界面设计和调试情况

（六） 算法的分析和评价及本次实验心得

顺序表的操作算法看似简单，实则困难。 eV

3

3 3 2

2 4

B 1

1 S

rL-纬

餒表表犍

》的的意 擔任