【数据结构】数据结构C语言的实现（线性表）

71 阅读 0 评论 47 点赞

我是靠谱客的博主孝顺奇异果，最近开发中收集的这篇文章主要介绍【数据结构】数据结构C语言的实现（线性表），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

线性表

/*
* 线性表
*/
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INIT_SIZE 10 // 初始化线性表长度
#define INCREMENT_SIZE 5
typedef int Status;
typedef int Elemtype;
typedef struct
{
Elemtype *elem; // 线性表的首地址
int length;
// 线性表长度
int size;
// 线性表大小
} SqList;
// 初始化线性表
Status InitList(SqList *L)
{
// 开辟线性表
L->elem = (Elemtype *)malloc(INIT_SIZE * sizeof(Elemtype));
if (!L->elem)
return ERROR;
// 初始化线性表
L->length = 0;
L->size = INIT_SIZE;
return OK;
}
// 销毁线性表
Status DestroyList(SqList *L)
{
// 释放线性表空间，长度大小置零
free(L->elem);
L->length = 0;
L->size = 0;
return OK;
}
// 置空线性表
Status ClearList(SqList *L)
{
L->length = 0;
return OK;
}
// 判断线性表是否为空
Status isEmpty(const SqList L)
{
if (L.length == 0)
return TRUE;
else
return FALSE;
}
// 返回线性表长度
Status getLength(const SqList L)
{
return L.length;
}
// 返回第i个元素
Status GetElem(const SqList L, int i, Elemtype *e)
{
if (i < 1 || i > L.length)
return ERROR;
*e = L.elem[i - 1];
return OK;
}
// 比较两个元素
Status compare(Elemtype e1, Elemtype e2)
{
if (e1 == e2)
return 0;
else if (e1 < e2)
return -1;
else
return 1;
}
// 返回元素e的index
Status FindElem(const SqList L, Elemtype e, Status (*compare)(Elemtype, Elemtype))
{
int i;
for (i = 0; i < L.length; i++)
{
if (!(*compare)(L.elem[i], e))
return i + 1;
}
if (i >= L.length)
return ERROR;
return -1;
}
// 返回前一个元素（如果有的话）
Status PreElem(const SqList L, Elemtype cur_e, Elemtype *pre_e)
{
int i;
for (i = 0; i < L.length; i++)
{
if (cur_e == L.elem[i])
{
if (i != 0)
{
*pre_e = L.elem[i - 1];
return OK;
}
else{
return ERROR;
}
}
}
if (i >= L.length)
return ERROR;
return ERROR;
}
// 返回下一个元素（如果有的话）
Status NextElem(const SqList L, Elemtype cur_e, Elemtype *pre_e)
{
int i;
for (i = 0; i < L.length; i++)
{
if (cur_e == L.elem[i])
{
if (i < L.length - 1)
{
*pre_e = L.elem[i + 1];
return OK;
}
else
{
return ERROR;
}
}
}
if (i >= L.length)
return ERROR;
return ERROR;
}
// 在index = i处插入元素e
Status InsertElem(SqList *L, int i, Elemtype e)
{
Elemtype *_new;
if (i < 1 || i > L->length + 1)
return ERROR;
// 如果线性表的大小不足，则开辟空间
if (L->length >= L->size)
{
_new = (Elemtype *)realloc(L->elem, (L->size + INCREMENT_SIZE) * sizeof(Elemtype));
if (!_new)
return ERROR;
L->elem = _new;
L->size += INCREMENT_SIZE;
}
// 把从i到length的元素统一往后移一位
Elemtype *p = &L->elem[i - 1];
Elemtype *q = &L->elem[L->length - 1];
for (; q >= p; q--)
*(q + 1) = *q;
// 把元算e放到第i个
*p = e;
++L->length;
return OK;
}
// 删除第i个元素，被删除的元素通过指针*e返回
Status DeleteElem(SqList *L, int i, Elemtype *e)
{
if (i < 1 || i > L->length)
return ERROR;
// 删除第i个元素，并且把从第i+1个到第length个统一向前移一位
Elemtype *p = &L->elem[i - 1];
*e = *p;
for (; p < &L->elem[L->length]; p++)
*(p) = *(p + 1);
--L->length;
return OK;
}
// 访问元素
void visit(Elemtype e)
{
printf("%d ", e);
}
// 遍历线性表
Status TraverseList(const SqList L, void (*visit)(Elemtype))
{
int i;
for (i = 0; i < L.length; i++)
visit(L.elem[i]);
return OK;
}
/*
* 主函数测试
*/
int main()
{
SqList L;
if (InitList(&L))
{
Elemtype e;
printf("init_successn");
int i;
for (i = 0; i < 10; i++)
InsertElem(&L, i + 1, i);
printf("length is %dn", getLength(L));
if (GetElem(L, 1, &e))
printf("The first element is %dn", e);
else
printf("element is not existn");
if (isEmpty(L))
printf("list is emptyn");
else
printf("list is not emptyn");
printf("The 5th at %dn", FindElem(L, 5, *compare));
PreElem(L, 6, &e);
printf("The 6's previous element is %dn", e);
NextElem(L, 6, &e);
printf("The 6's next element is %dn", e);
DeleteElem(&L, 1, &e);
printf("delete first element is %dn", e);
printf("list:");
TraverseList(L, visit);
if (DestroyList(&L))
printf("ndestroy_successn");
}
}

init_success
length is 10
The first element is 0
list is not empty
The 5 at 6
The 6's previous element is 5
The 6's next element is 7
delete first element is 0
list:1 2 3 4 5 6 7 8 9
destroy_success