C语言线性表顺序存储结构实现 - 在第i个位置之前插入元素

#include <stdio.h> #include <stdlib.h>

#define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 #define LIST_INIT_SIZE 100 #define LISTINCREAMENT 10

typedef int ElemType; typedef int Status;

typedef struct { ElemType *elem; //线性表占用的数组空间 int length; //线性表的长度 int listsize; //当前分配的存储容量(以sizeof(ElemType)为单位) }SqList;

//线性表初始化 Status InitList_Sq(SqList *L){
//构造一个空的线性表 L->elem=(ElemType )malloc(LIST_INIT_SIZEsizeof(ElemType)); if (!L->elem) exit(OVERFLOW); //存储分配失败 L->length=0; //空表长度为0 L->listsize= LIST_INIT_SIZE; //初始存储容量 return OK; }

//求线性表长度 Status ListLength(SqList *L){ return L->length; }

//插入元素，C语言数组从第0个元素开始，此处下标从1开始

Status ListInsert(SqList *L, int i, ElemType e) {

// 在顺序表L的第 i 个元素之前插入新的元素e,
// i 的合法范围为  1≤i≤L->length+1

ElemType  *p,*q,*newbase;
if (i<1 || i>L->length+1)  return ERROR;  // 插入位置不合法
if (L->length+1 >= L-> listsize)
{
    newbase=(ElemType*)realloc(L->elem++,(LIST_INIT_SIZE+LISTINCREAMENT)*sizeof(ElemType));
    if(!newbase)
        return  OVERFLOW;// 当前存储空间已满
    L-> elem=newbase;
    L-> listsize+=LISTINCREAMENT;
}
// i的范围合法，则在顺序表L的第 i 个元素之前插入新的元素e,
p = &(L->elem[i-1]);
for (q = &(L->elem[L->length-1]); q >= p; --q)
    *(q+1) = *q;
*p = e;
++L->length;

return OK;

}

//删除元素 Status ListDelete(SqList *L, int i, ElemType *e){
ElemType *p,*q; // 在顺序线性表L中删除第i个元素，并用e返回其值。 // i的合法值为1≤i≤ListLength(L)

// 删除位置不合法
if ((i < 1) || (i > L->length)) return ERROR;

// 若删除位置合法，则删除该位置元素 p = &(L->elem[i-1]);

// p为被删除元素的位置
*e = *p;

// 被删除元素的值赋给e
q = &L->elem[L->length-1];

// 表尾元素的位置
for (++p; p <= q; ++p)
    *(p-1) = *p;

// 被删除元素之后的元素左移
--L->length;

return  OK;

}

//获取某个位置的元素值 Status GetItem(SqList *L,int i,ElemType *e){ if ((i < 1) || (i > L->length)) return ERROR; *e = L->elem[i-1]; return OK; }

Status DestroyList(SqList *L){ free(L->elem); free(L); return OK; }

//主函数 int main(){ SqList *L; ElemType x,e; int i,n,choice,position,flag; L=(SqList *)malloc(sizeof(SqList)); InitList_Sq(L);

// 插入5个结点，值为1 2 3 4 5 
for(i=1;i<=5;i++){                                
    ListInsert(L, i,i);
} 
    
printf("请输入你要插入结点的位置:");
scanf("%d",&position);
printf("请输入你要插入的数据:");
scanf("%d",&x);
flag = ListInsert(L, position,x);

if(flag)
    printf("插入成功，插入的元素值为%d\n",x);
else
    printf("元素插入失败，请重试!\n");

printf("顺序表的元素为：");
for(i=1;i<= ListLength(L);i++)
    printf("%d\t",L->elem[i-1]);

DestroyList(L);
return 0;

}