欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

线性表——顺序结构和基本操作的实现

程序员文章站 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;
}

运行结果
线性表——顺序结构和基本操作的实现