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]); // p为插入位置的前一个位置 q = &(L->elem[L->length-1]); // q为表尾元素的位置 for (; q >= p; --q) *(q+1) = *q; // 插入位置之后的元素右移 *p = e; // 插入元素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; }