线性表——顺序结构和基本操作的实现
程序员文章站
2024-03-20 14:42:46
...
具体实现代码如下:
#include<stdio.h>
#include<stdlib.h>
#define LISTINITSIZE 256 //顺序表初始分配的空间大小
#define LISTINCREMENT 128 //空间分配的增量大小
#define OK 1
#define ERROR 0
typedef int ElemType, Status; //定义元素和函数返回值类型
typedef struct
{
ElemType* pData; //指向顺序表首地址
int length; //顺序表中元素个数
int size; //顺序表大小
}SeqList;
Status InitList(SeqList& L) //顺序表初始化
{
L.pData = (ElemType*)malloc(LISTINITSIZE * sizeof(ElemType));
if (L.pData == NULL) exit(0);
L.size = LISTINITSIZE;
L.length = 0;
return OK;
}
Status DestroryList(SeqList& L) //顺序表销毁
{
if (L.pData != NULL)
{
free(L.pData);
L.pData = NULL;
}
L.length = 0;
L.size = 0;
return OK;
}
Status ClearList(SeqList& L) //顺序表清空
{
L.length = 0;
return OK;
}
Status GetElem(SeqList L, int i, ElemType& e) //查找顺序表中第i个元素
{
if (i < 1 || i> L.length)
return ERROR;
e = L.pData[i - 1];
return OK;
}
Status LocateElem(SeqList L, ElemType e) //顺序表元素查找
{
for (int i = 0; i < L.length; i++)
{
if (L.pData[i] == e)
return i + 1;
}
return ERROR;
}
Status ListEmpty(SeqList L) //顺序表判空
{
if (L.length == 0) return OK;
return ERROR;
}
Status PriorElem(SeqList L, ElemType cur_e, ElemType &pre_e) //顺序表元素前驱
{
if (L.pData == NULL) return ERROR;
if (L.length == 0) return ERROR;
if (L.pData[0] == cur_e) return ERROR;
for (int i = 1; i < L.length; i++)
{
if (L.pData[i] == cur_e)
{
pre_e = L.pData[i - 1];
return OK;
}
}
return ERROR;
}
Status NextElem(SeqList L, ElemType cur_e, ElemType& next_e) //顺序表元素后继
{
if (L.pData == NULL) return ERROR;
if (L.length <= 1) return ERROR;
for (int i = 0; i < L.length - 1; i++)
{
if (L.pData[i] == cur_e)
{
next_e = L.pData[i + 1];
return OK;
}
}
return ERROR;
}
Status ListTraverse(SeqList L) //顺序表遍历
{
if (L.pData == NULL) return ERROR;
if (L.length == 0) return ERROR;
for (int i = 0; i < L.length; i++)
{
printf("%d ", L.pData[i]);
}
printf("\n");
return OK;
}
Status SetElem(SeqList &L, int i, ElemType &e) //顺序表元素替换
{
if (L.pData == NULL) return ERROR;
if (i < 1 || i > L.length) return ERROR;
int temp = e;
e = L.pData[i - 1];
L.pData[i - 1] = temp;
return OK;
}
Status InsertElem(SeqList &L, int i, ElemType e) //顺序表元素插入
{
if (L.pData == NULL) return ERROR;
if (L.length == 0 && i == 1)
{
L.pData[i - 1] = e;
L.length = L.length + 1;
return OK;
}
if (i < 1 || i > L.length) return ERROR;
if (L.length == L.size)
{
ElemType* newbase = (ElemType*)realloc(L.pData, (L.size + LISTINCREMENT) * sizeof(ElemType));
if (newbase == NULL) exit(0);
L.pData = newbase;
L.size = L.size + LISTINCREMENT;
}
for (int j = L.length; j > i - 1; j--)
{
L.pData[j] = L.pData[j - 1];
}
L.pData[i - 1] = e;
L.length = L.length + 1;
return OK;
}
Status DeleteElem(SeqList& L, int i, ElemType& e) //顺序表元素删除
{
if (L.pData == NULL) return ERROR;
if (i < 1 || i > L.length) return ERROR;
e = L.pData[i - 1];
for (int j = i - 1; j < L.length - 1; j++)
{
L.pData[j] = L.pData[j + 1];
}
L.length = L.length - 1;
return OK;
}
int main()
{
SeqList L;
InitList(L);
InsertElem(L, 1, 1);
for (int i = 1; i < 10; i++)
{
InsertElem(L, i, i + 1);
}
printf("顺序表长度:%d\n", L.length);
ElemType e;
PriorElem(L, 3, e);
printf("元素3的前驱:%d\n", e);
NextElem(L, 3, e);
printf("元素3的后继:%d\n", e);
ListTraverse(L);
e = 0;
SetElem(L, 3, e);
ListTraverse(L);
DeleteElem(L, 4, e);
ListTraverse(L);
return OK;
}
运行结果