如何建立一个顺序存储的线性表，实现线性表的插入、删除操作？

如题所述

顺序存储结构线性表基本操作 C语言实现

#include <stdio.h>
//以下为函数运行结果状态代码
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define LIST_INIT_SIZE 100  //线性表存储空间的初始分配量
#define LISTINCREMENT 10  //线性表存储空间分配增量
typedef int Status; //函数类型，其值为为函数结果状态代码
typedef int ElemType; //假设数据元素为整型
typedef struct
{
     ElemType *elem; //存储空间基址
    int length; //当前长度
    int listsize; //当前分配的存储容量
}SqList;
//实现线性表的顺序存储结构的类型定义
//函数声明开始
Status InitList_Sq(SqList &L);
void DestroyList_Sq(SqList &L);
void ClearList_Sq(SqList &L);
void ListEmpty_Sq(SqList L);
Status GetElem_Sq(SqList L,i,&e);
int LocateElem_Sq(SqList L,e,compare());
Status PriorElem_Sq(SqList L,cur_e,&pre_e);
Status NextElem_Sq(SqList L,cur_e,&next_e);
Status ListInsert_Sq(SqList &L,i,e);
Status ListDelete_Sq(SqList &L,i,&e);
ListTravel_Sq(SqList L,visit());
//函数声明结束
int main(void)
{
    return 0;
}
//函数定义开始
///////////////////////////////////////
//函数名：InitList_Sq()
//参数：SqList *L
//初始条件：无
//功能：构造一个空线性表
//返回值：存储分配失败：OVERFLOW
//         å­˜å‚¨åˆ†é…æˆåŠŸï¼šOK
///////////////////////////////////////
Status InitList_Sq(SqList *L)
{
     L.elem=(ElemType*)malloc((LIST_INIT_SIZE *sizeof(ElemType)); //分配空间
    if(!L.elem)
         exit(OVERFLOW); //若存储分配失败，返回OVERFLOW
     L.length=0; //空表，长度为0
     L.listsize=LIST_INIT_SIZE; //初始存储容量
    return OK;
}
///////////////////////////////////////
//函数名：DestroyList_Sq()
//参数：SqList *L
//初始条件：线性表L已存在
//功能：销毁线性表
//返回值：无
///////////////////////////////////////
void DestroyList_Sq(SqList *L)
{
    if (L->elem)
         free(L->elem); //释放线性表占据的所有存储空间
}
///////////////////////////////////////
//函数名：ClearList_Sq()
//参数：SqList *L
//初始条件：线性表L已存在
//功能：清空线性表
//返回值：无
///////////////////////////////////////
void ClearList_Sq(SqList *L)
{
     L->length=0; //将线性表的长度置为0
}
///////////////////////////////////////
//函数名：ListEmpty_Sq()
//参数：SqList L
//初始条件：线性表L已存在
//功能：判断线性表是否为空
//返回值：空：TRUE
//         éžç©ºï¼šFALSE
///////////////////////////////////////
Status ListEmpty_Sq(SqList L)
{
    if (L.length==0)
        return TRUE;
     else
        return FALSE;
}
///////////////////////////////////////
//函数名：ListLength_Sq()
//参数：SqList L
//初始条件：线性表L已存在
//功能：返回线性表长度
//返回值：线性表长度(L.length)
///////////////////////////////////////
Status ListLength_Sq(SqList L)
{
    return (L.length);
}
///////////////////////////////////////
//函数名：GetElem_Sq()
//参数：SqList L,int i,ElemType *e
//初始条件：线性表L已存在，1<=i<=ListLength(L)
//功能：用e返回线性表中第i个元素的值
//返回值：(i<1)||(i>ListLength(L))：ERROR
//         1<=i<=ListLength(L)：OK
///////////////////////////////////////
Status GetElem_Sq(SqList L,int i,ElemType *e)
{
    if (i<1||i>L.length)
        return ERROR; //判断i值是否合理，若不合理，返回ERROR
     *e=L.elem[i-1]; //数组中第i-1的单元存储着线性表中第i个数据元素的内容
    return OK;
}
///////////////////////////////////////
//函数名：LocateElem_Sq()
//参数：L,e,compare(ElemType1,ElemType2)
//初始条件：线性表L已存在，compare()为数据元素判定函数
//功能：返回顺序表L中第1个与e满足关系 compare( ) çš„数据元素的位序
//返回值：若在L中存在于e满足关系compare()的元素：其位序
//         è‹¥åœ¨L中不存在于e满足关系compare()的元素：0
///////////////////////////////////////
int LocateElem_Sq(SqList L,e,compare(ElemType1,ElemType2))
{
　　int i = 1; // i çš„初值为第1元素的位序
　　int p = L.elem; // p çš„初值为第1元素的存储位置
　　while (i <= L.length && !(*compare)(*p++,e))
　　　++i; // ä¾æ¬¡è¿›è¡Œåˆ¤å®š
　　if (i <= L.length)
      return i; // æ‰¾åˆ°æ»¡è¶³åˆ¤å®šæ¡ä»¶çš„数据元素为第 i ä¸ªå…ƒç´ 
　　else
      return 0; // è¯¥çº¿æ€§è¡¨ä¸­ä¸å­˜åœ¨æ»¡è¶³åˆ¤å®šçš„数据元素
}
Status PriorElem_Sq(SqList L,cur_e,&pre_e);
//见Status NextElem_Sq(SqList L,cur_e,&next_e);
Status NextElem_Sq(SqList L,cur_e,&next_e);
//我的思路是先用LocateElem_Sq()搜索cur_e的位序，
//再看是否大于等于length，
//若是，则返回OVERFLOW；否则返回后继
//这样也许有点麻烦？所以希望大家能够补充方案
//by wangweinoo1
///////////////////////////////////////
//函数名：ListInsert_Sq()
//参数：SqList *L,int i,ElemType e
//初始条件：线性表L已存在，1<=i<=ListLength(L)+1
//功能：在线性表中第i个数据元素之前插入数据元素e
//返回值：失败：ERROR
//         æˆåŠŸï¼šOK
///////////////////////////////////////
Status ListInsert_Sq(SqList *L,int i,ElemType e)
{
     ElemType *j;
    if (L->length==LIST_MAX_LENGTH)
        return ERROR; //检查是否有剩余空间
    if (i<1||i>L->length+1)
        return ERROR; //检查i值是否合理
    //将线性表第i个元素之后的所有元素向后移动
    for (j=L->length-1;j>=i-1;i++)
         L->elem[j+1]=L->elem[j];
     L->elem[i-1]=e; //将新元素的内容放入线性表的第i个位置，
     L->length++;
    return OK;
}
///////////////////////////////////////
//函数名：ListDelete_Sq()
//参数：SqList *L,int i,Elemtype *e
//初始条件：线性表L已存在，1<=i<=ListLength(L)
//功能：将线性表L中第i个数据元素删除
//返回值：失败：ERROR
//         æˆåŠŸï¼šOK
///////////////////////////////////////
int ListDelete_Sq(SqList *L,int i,Elemtype *e)
{
    if (IsEmpty(L))
        return ERROR; //检测线性表是否为空
    if (i<1||i>L->length)
        return ERROR; //检查i值是否合理
     *e=L->elem[i-1]; //将欲删除的数据元素内容保留在e所指示的存储单元中
    //将线性表第i+1个元素之后的所有元素向前移动
    for     (j=i;j<=L->length-1;j++) L->elem[j-1]=L->elem[j];
     L->length--;
    return OK;
}
//函数定义结束

温馨提示：内容为网友见解，仅供参考

当前网址：https://11.t2y.org/zz/fms24p28pf7fpmqp2s7.html