数据结构实验(1)线性表及其应用.doc

实验目的:
帮助学生掌握线性表的基本操作在顺序和链表这两种存储结构上的实现,尤以链表的操作和应用作为重点。
问题描述:
构造一个空的线性表L。
在线性表L的第i个元素之前插入新的元素e;
在线性表L中删除第i个元素,并用e返回其值。
实验要求:文法是一个四元
分别利用顺序和链表存储结构实现线性表的存储,并设计出在不同的存储结构中线性表的基本操作算法。
在实验过程中,对相同的操作在不同的存储结构下的时间复杂度和空间复杂度进行分析。
算法分析:
由于两种存储结构都用来创建线性结构的数据表,可采用相同的输出模式和整体结构类似的算法,如下:

实验内容和过程:
顺序存储结构线性表程序清单:
//顺序存储结构线性表的插入删除
#include <iostream>
#include <>
using namespace std;
# define LISTSIZE 100
# define CREMENTSIZE 10
typedef char ElemType; //定义数据元素类型为字符型
typedef struct {
ElemType *elem; //数据元素首地址
int len; //当前元素个数
int listsize; //当前存储最大容量
}SqList;
//构造一个空的线性表L
int InitList(SqList &L)
{
=(ElemType *)malloc(LISTSIZE*sizeof(ElemType));
if (!) exit(-2); //分配空间失败
=0;
=LISTSIZE;
}
//在顺序线性表L中第i个位置之前插入新的元素e
int ListInsert(SqList &L,int i,ElemType e)
{
if (i<1||i>+1) return -1; //i值不合法
if (>=)
{
ElemType *newelem=(ElemType *)realloc(,(+CREMENTSIZE)*sizeof(ElemType));
//存储空间已满,增加分配
if(!newelem) exit (-2); //分配失败
=newelem;
+=CREMENTSIZE;
}
ElemType *q=&([i-1]) ;
for (ElemType *p=&([-1]);p>=q;--p) *(p+1)=*p; //插入位置及其后的元素后移
*q=e; ++;
return 1;
}
//在顺序线性表L中删除第i个元素,并用e返回其值
int ListDelete(SqList &L,int i,ElemType&e)
{
if (i<1||i>) return -1; //i值不合法
ElemType *p=&([i-1]);
e=*p; ElemType*q=+