实验一顺序表的基本操作实验报告

 实验名称 实验日期 1、实验目的： 2019.9.23 顺序表的基本操作 实验成绩 1．掌握线性表的顺序存储结构的表示和实现方法。 2．掌握顺序表基本操作的算法实现。 3．了解顺序表的应用。 2、实验内容： char）， 并在此基础上设计一个主程序完成如下功能： （1）初始化顺序表 L； （2）依次采用尾插法插入 a、b、c、d、e 元素； （3）输出顺序表 L； （4）输出顺序表 L 的长度； （5）判断顺序表 L 是否为空； （6）输出顺序表 L 的第 3 个元素； （7）输出元素 a 的位置 （8）在第 4 个元素位置上插入 f 元素 （9）输出顺序表 L； （10）删除 L 的第 3 个元素； （11）输出顺序表 L； （12）释放顺序表 L。 3、核心算法或代码片段： 核心算法： 1．顺序表插入操作的基本步骤：要在顺序表中第 i 个数据元素之前插入一 个数据元素 x，首先要判断插入位置 i 是否合法，假设线性表的长为 n，则 i 的 合法值范围： 1≤i≤n+1，若是合法位置，就再判断顺序表否满，如果满，则增 加空间或结束操作，如果不满，则将第 i 个数据元素及其之后的所有数据元素都 后移一个位置，此时第 i 个位置已经腾空，再将待插入的数据元素 x 插入到该位 置上，最后将线性表的长增加 1。 2．顺序表删除操作的基本步骤：要删除顺序表中第 i 个数据元素，首先仍然 要判断 i 的合法性， i 的合法范围是 1≤i≤n，若是合法位置，则将第 i 个数据 编写一个程序，实现顺序表的各种基本运算（假设顺序表的元素类型为 元素之后的所有数据都前移一个位置，最将线性表长减 1。

3．顺序表查找操作的基本步骤：要在顺序表中查找一个给定值的数据元素 则可以采用顺序查找的方法，从表中第 1 个数据元素开始依次将值与给定值进行 比较，若相等则返回该数据元素在顺序表中的位置，否则返回 0 值。 线性表的动态分配顺序存储结构—C语言实现 #define MaxSize 50//存储空间的分配量 Typedef char ElemType； Typedef struct{

ElemType data[MaxSize];

int length; //表长度（表中有多少个元素） }SqList;

动态创建一个空顺序表的算法： void InitList(SqList *&L) //初始化线性表 {

L=(SqList *)malloc(sizeof(SqList)); //分配存放线性表的空间 L->length=0; //置空线性表长度为0 }

线性表的插入：

status Sqlist_insert(Sqlist &L,int i,Elemtype x) /*在顺序表L中第i个元素前插入新元素x*/

{ if (i<1||i>L.length+1) return ERROR; /*插入位置不正确则出错*/ if (L.length>=MAXLEN)return OVERFLOW;

/*顺序表L中已放满元素，再做插入操作则溢出*/ for(j=L.length-1;j>=i-1;j--)

L.elem[j+1]=L.elem[j]; /*将第i个元素及后续元素位置向后移一位*/ L.elem[i-1]=x; /*在第i个元素位置处插入新元素x*/ L.length++; /*顺序表L的长度加1*/ return OK; }

线性表的删除：

status Sqlist_delete(Sqlist &L,int i,Elemtype &e) /*在顺序表L中删除第i个元素*

{ if (i<1||i>L.length) return ERROR; /*删除位置不正确则出错*/ for(j=i;j<=L.length-1;j++)

L.elem[j-1]=L.elem[j]; /*将第i+1个元素及后继元素位置向前移一位*/

L.length--;/*顺序表L的长度减1*/ return OK； }

线性表元素的查找：

int LocateElem(SqList *L, ElemType e) //按元素值查找 { int i=0;

while (ilength && L->data[i]!=e) i++; //查找元素e

if (i>=L->length) //未找到时返回0 return 0; else

return i+1; //找到后返回其逻辑序号 }

输出线性表：

void DispList(SqList *L) //输出线性表 { int i;

if (ListEmpty(L)) return; for (i=0;ilength;i++) printf(\"%c \->data[i]); printf(\"\\n\"); }

输出线性表第i个元素的值：

bool GetElem(SqList *L,int i,ElemType &e)//求线性表中某个数据元素值 {

if (i<1 || i>L->length)

return false; //参数错误时返回false e=L->data[i-1]; //取元素值

return true; //成功找到元素时返回true }

代码：

#include #include #define MaxSize 50 typedef char ElemType; typedef struct {

ElemType data[MaxSize];

int length;

} SqList;

void InitList(SqList *&L); void DestroyList(SqList *L); bool ListEmpty(SqList *L); int ListLength(SqList *L); void DispList(SqList *L);

bool GetElem(SqList *L,int i,ElemType &e); int LocateElem(SqList *L, ElemType e); bool ListInsert(SqList *&L,int i,ElemType e); bool ListDelete(SqList *&L,int i,ElemType &e); void InitList(SqList *&L) //初始化线性表 { }

void DestroyList(SqList *L) { }

bool ListEmpty(SqList *L) //判线性表是否为空表 { }

int ListLength(SqList *L) //求线性表的长度 {

return(L->length); return(L->length==0); free(L);

//销毁线性表

L=(SqList *)malloc(sizeof(SqList)); //分配存放线性表的空间 L->length=0;

//置空线性表长度为0

}

void DispList(SqList *L) //输出线性表 { }

bool GetElem(SqList *L,int i,ElemType &e) //求线性表中某个数据元素值 { }

int LocateElem(SqList *L, ElemType e) //按元素值查找 { }

bool ListInsert(SqList *&L,int i,ElemType e) //插入数据元素 { int j;

if (i<1 || i>L->length+1)

return false;

//参数错误时返回false

//将顺序表逻辑序号转化为物理序号 //将data[i]及后面元素后移一个位置

i--; int i=0;

while (ilength && L->data[i]!=e)

i++;

//查找元素e //未找到时返回0

if (i>=L->length)

return 0; return i+1;

//找到后返回其逻辑序号

else

if (i<1 || i>L->length)

return false;

//参数错误时返回false

//取元素值

//成功找到元素时返回true

e=L->data[i-1]; return true; int i;

if (ListEmpty(L)) return; for (i=0;ilength;i++)

printf(\"%c \->data[i]); printf(\"\\n\");

for (j=L->length;j>i;j--)

L->data[j]=L->data[j-1];

}

L->data[i]=e; L->length++; return true;

//插入元素e //顺序表长度增1 //成功插入返回true

bool ListDelete(SqList *&L,int i,ElemType &e) //删除数据元素 { }

void main() {

SqList *L; ElemType e;

printf(\"顺序表的基本运算如下:\\n\"); printf(\" (1)初始化顺序表L\\n\"); InitList(L);

printf(\" (2)依次采用尾插法插入a,b,c,d,e元素\\n\"); ListInsert(L,1,'a'); ListInsert(L,2,'b'); ListInsert(L,3,'c'); ListInsert(L,4,'d'); ListInsert(L,5,'e');

printf(\" (3)输出顺序表L:\"); DispList(L);

printf(\" (4)顺序表L长度=%d\\n\

printf(\" (5)顺序表L为%s\\n\空\":\"非空\")); GetElem(L,3,e);

printf(\" (6)顺序表L的第3个元素=%c\\n\ int j;

if (i<1 || i>L->length)

return false;

//将顺序表逻辑序号转化为物理序号

i--;

//参数错误时返回false

e=L->data[i];

for (j=i;jlength-1;j++) //将data[i]之后的元素前移一个位置

L->data[j]=L->data[j+1];

//顺序表长度减1 //成功删除返回true

L->length--; return true;

} printf(\" (7)元素a的位置=%d\\n\ printf(\" (8)在第4个元素位置上插入f元素\\n\"); ListInsert(L,4,'f'); printf(\" (9)输出顺序表L:\"); DispList(L); printf(\" (10)删除L的第3个元素\\n\"); ListDelete(L,3,e); printf(\" (11)输出顺序表L:\"); DispList(L); printf(\" (12)释放顺序表L\\n\"); DestroyList(L); 4、实验结果分析及总结体会： 实验结果： 心得体会： 通过本次实验，实现了数据结构在程序设计上的作用，了解了数据结构语言，加深了对c语言的认识掌并掌握了线性表的顺序存储结构的表示和实现方法，掌握顺序表基本操作的算法实现，同时了解了顺序表的应用。