线性表的创建，删除插入等操作

Question

如题所述

Answer 1

线性表的操作类似于数组，都是连续存储，所以相关的操作也是类似。

插入：在第t个位置插入元素，需要将从第t个位置到第n个位置向后移动。

删除：删除第t个元素，从t+1位置元素往前移动

插入和删除都需要将元素移动，顺序存储结构线性表所需要的平均时间复杂度为O(n)。

下面是根据数据结构实现的代码；

#include

#include

#define TRUE 1;

#define FALSE 0;

#define OK 1;

#define ERROR 0;

#define OVERFLOW -2;

typedef int Status;

typedef int ElemType;

typedef struct {

ElemType *elem;//线性表的基地址

int Length;//长度

int Listsize;//当前分配的存储容量

}SqList;

Status InitList(SqList &L)//初始化线性表

{

L.elem = (ElemType*)malloc(100 * sizeof(ElemType));//分配内存

if (!L.elem) exit(-2);

L.Length = 0;

L.Listsize = 100;

return OK;

}

Status ListInsert(SqList &L,int i,ElemType e)//在顺序表第i个位置之前插入新的元素e

{

if (i 1 || i>L.Length + 1) return ERROR;//i值不合法

if (L.Length >= L.Listsize)//存储空间已满

{

ElemType *newbase = (ElemType*)realloc(L.elem, (L.Listsize + 10) * sizeof(ElemType));

if (!newbase)

{

exit(-2);

}

L.elem = newbase;

L.Listsize += 10;

}

ElemType *q = &(L.elem[i - 1]); //将L表中第i个元素的地址信息传递给指针q

for (ElemType *p = &(L.elem[L.Length - 1]); p >= q; --p)//p为末尾元素的地址

{

*(p + 1) = *p;

}

*q = e;

++L.Length;

return OK;

}

Status OutputList(SqList L)//输出线性表中的元素

{

int i = 0;

for (i ; i < L.Length ; i++)

{

printf("%d ", L.elem[i]);

}

return OK;

}

Status ListLength(SqList L)//返回线性表的表长

{

return L.Length;

}

Status GetElem(SqList L, int i, ElemType &e)//用e返回第i个元素的值

{

if (iL.Length) return ERROR;

e = L.elem[i-1];

return OK;

}

Status ClearList(SqList &L)//清除线性表的数据

{

L.Length = 0;

return OK;

}

Status DeleteList(SqList &L,int i,ElemType &e)//删除第i个元素，并用e返回其值

{

if (iL.Length) return ERROR;

e = L.elem[i - 1];//通过下标找到第i个元素的值

ElemType *p = &(L.elem[i - 1]);

ElemType *q = L.elem + L.Length - 1;

for (p; p