#include <stdio.h>
#include <stdlib.h>
int OVERFLOW = 0;
typedef int ElemType;
typedef int Status;
typedef int Bool;
#define ERROR 0
#define OK 1
#define FALSE 0
#define TRUE 1
// ---------------线性表的动态分配顺序存储结构---------------
#define LIST_INIT_SIZE 10 //线性表存储空间的初始分配量
#define LISTINCREMENT 10 // 线性表存储空间的分配增量
typedef struct {
ElemType *elem; // 存储空间的基址
int length; // 当前长度
int listsize; // 当前分配的存储容量(以sizeof(ElemType)为单位)
} SqList;
/**
构建一个空的线性表L
*/
Status InitList(SqList *L);
/**
销毁一个以存在的线性表L
@param L 已经存在的线性表
@return 操作结果
*/
Status DestoryList(SqList *L);
/**
遍历线性表中的元素
@param L 已存在的线性表
*/
void OutputList(SqList *L);
/**
将L置为空表
@param L 以存在的线性表
@return 操作结果
*/
Status ClearList(SqList *L);
/**
判断顺序表是否为空
@param L 已存在的线性表
@return 若L为空表则返回TRUE，否则返回FALSE
*/
Status ListEmpty(SqList L);
/**
查看线性表中元素的个数
@param L 已存在的线性表
@return 返回L中数据元素的个数
*/
int ListLength(SqList *L);
/**
用e接收第i个数据元素的值
@param L 已存在的线性表
@param i 数据元素的位序
@param e 接收第i个数据元素
@return 用e接收顺序表L中第i个数据元素的值
*/
Status GetElem(SqList L, int i, ElemType *e);
/**
索引线性表中数据元素e的下标
@param L 已存在的线性表
@param e 数据元素
@return 数据元素e的下标
*/
int IndexOfElem(SqList L, ElemType e);
/**
查找线性表中值为e的直接前驱元素
@param L 已存在的线性表
@param e 数据元素
@param pre_e 用来存放e的直接前去元素的指针
@return 返回操作状态
*/
Status PriorElem(SqList L, ElemType e, ElemType *pre_e);
/**
查找线性表中值为e的直接后继元素
@param L 已存在的线性表
@param e 数据元素
@param next_e 用来存放e的直接后继元素的指针
@return 返回操作状态
*/
Status NextElem(SqList L, ElemType e, ElemType *next_e);
/**
在线性表L中第i个元素之前插入新的数据元素e
@param L 已存在的线性表
@param i 要插入的位序
@param e 所要插入的元素
@return 返回操作结果
*/
Status ListInsert(SqList *L, int i, ElemType e);
/**
从线性表L中删除第i个数据元素并用e接收所删除的元素
@param L 已存在的线性表
@param i 要删除元素所在的位置
@param e 接收删除的数据元素
@return 操作结果
*/
Status ListDelete(SqList *L, int i, ElemType *e);
int main(int argc, const char * argv[]) {
SqList *L = (SqList *)malloc(sizeof(SqList));
InitList(L);
(*L).length = 10;
for (int i=0; i<(*L).length; i++) {
(*L).elem[i] = i+1;
}
ElemType *e = (ElemType *)malloc(sizeof(ElemType));
// GetElem(*L, 5, e);
// 在线性表中获取e的直接前驱元素pre_e
// ElemType *pre_e = (ElemType *)malloc(sizeof(ElemType));
// PriorElem(*L, *e, pre_e);
// printf("pre_e = %d\n", *pre_e);
// 在线性表中获取e的直接后继元素pre_e
// ElemType *next_e = (ElemType *)malloc(sizeof(ElemType));
// NextElem(*L, *e, next_e);
// printf("next_e = %d\n", *next_e);
// 向线性表L中位序为5的位置插入一个元素
// ListInsert(L, 1, 0);
// 从线性表L中将位序为1的元素删除
ListDelete(L, 1, e);
// 清空线性表L
// ClearList(L);
// 输出线性表中的所有元素
// OutputList(L);
// 在线性表L中，从第一个位置开始，挨个取出每个位置上的数据放入e中
for (int i=1; i<=(*L).length; i++) {
ElemType *e = malloc(sizeof(ElemType));
GetElem(*L, i, e);
printf("elem[%d] = %d\n", i-1, *e);
}
// 销毁线性表L
DestoryList(L);
return 0;
}
Status InitList(SqList *L) {
(*L).elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
if ((*L).elem == NULL) {
printf("存储分配失败!\n");
exit(OVERFLOW); // 存储分配失败
}
(*L).length = 0; // 空表长度为0
(*L).listsize = LIST_INIT_SIZE; // 初始存储量
printf("线性表初始化成功!\n");
return OK;
}
Status DestoryList(SqList *L) {
if (!(*L).elem) {
printf("线性表不存在!\n");
return ERROR;
}
free((*L).elem);
free(L);
printf("线性表已清空!\n");
return OK;
}
void OutputList(SqList *L) {
for (int i = 0; i<(*L).length; i++) {
printf("elem[%d] = %d\n", i, (*L).elem[i]);
}
}
Status ClearList(SqList *L) {
if (L==NULL || L->elem == NULL) { // 判断顺序表是否存在 或 顺序表中是否为元素分配内存
printf("线性表不存在!\n");
return ERROR;
}
free(L->elem);
L->elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
L->length = 0;
printf("线性表已清空!\n");
return OK;
}
Bool ListEmpty(SqList L) {
return L.length==0;
}
int ListLength(SqList *L) {
return L->length;
}
// 位序 要从1开始
Status GetElem(SqList L, int i, ElemType *e) {
if (L.length == 0 || i < 1 || i > L.length) {
printf("线性表不存在！\n");
return ERROR;
}
*e = L.elem[i-1];
return OK;
}
int IndexOfElem(SqList L, ElemType e) {
if (L.elem == NULL) {
printf("线性表不存在!\n");
return -1;
}
int i = 0;
while (L.elem[i] != e) {
i = i+1;
if (i >= L.length) {
printf("该元素不存在!\n");
return -1;
}
}
return i;
}
Status PriorElem(SqList L, ElemType e, ElemType *pre_e) {
if (L.elem==NULL) {
printf("线性表不存在!\n");
return ERROR;
}
int index_e = IndexOfElem(L, e);
if (index_e == -1) {
printf("该元素不存在!\n");
return ERROR;
}
index_e = index_e - 1;
*pre_e = L.elem[index_e];
return OK;
}
Status NextElem(SqList L, ElemType e, ElemType *next_e) {
if (L.elem==NULL) {
printf("线性表不存在!\n");
return ERROR;
}
int index_e = IndexOfElem(L, e);
if (index_e == -1) {
printf("该元素不存在!\n");
return ERROR;
}
*next_e = L.elem[index_e+1];
return OK;
}
Status ListInsert(SqList *L, int i, ElemType e) {
ElemType *newbase;
if (i<1 || i>(*L).length+1) { // 判断所要插入的位序是否合法
printf("插入位置不存在!\n");
}
if ((*L).length == (*L).listsize) { // 判断当前存储空间是否已满，已满，则增加增量
newbase = (ElemType *)realloc((*L).elem, ((*L).listsize + LISTINCREMENT)*sizeof(ElemType));
if (newbase == NULL) {
exit(OVERFLOW);
return ERROR;
}
(*L).elem = newbase;
(*L).listsize = (*L).listsize + LISTINCREMENT;
printf("成功重新分配内存!\n");
}
// for (int j=(*L).length-1; j>=i-1; --j) {
// (*L).elem[j+1] = (*L).elem[j];
// }
// (*L).elem[i-1] = e;
ElemType *p, *q;
q = &(*L).elem[i-1];
for (p=&(*L).elem[(*L).length-1]; p>=q; --p) {
*(p+1) = *p;
}
*q = e;
(*L).length = (*L).length + 1;
return OK;
}
Status ListDelete(SqList *L, int i, ElemType *e) {
if (i<1 || i>(*L).length) { // 判断所要删除数据元素位置是否合理
printf("所要删除的位置不存在!\n");
return ERROR;
}
ElemType *p, *q;
*e = (*L).elem[i-1]; // 将别删除元素的值赋给e
p = &(*L).elem[i-1]; // p为被删除元素的位置
q = &(*L).elem[(*L).length-1]; // 表尾元素的位置
for (++p; p<=q; p++) {
*(p-1) = *p; // 将被删除元素之后的元素左移
}
// for (int j=i-1; j<(*L).length-1; j++) {
// (*L).elem[j]=(*L).elem[j+1];
// }
(*L).length -= 1;
return OK;
}
网友评论