前言

本文章用于记录个人学习过程与心得,欢迎讨论!

使用书籍: 数据结构 (C语言版第2版) (严蔚敏李冬梅吴伟民)

前提说明

教材中使用的描述语言为"类C语言",是一种介于C和C++之间的伪代码,方便转化为实际C/C++代码
文件后缀名为 .cpp , 目的是使用C++中的 &引用类型?/?new?/?delete 等来简化代码实现 , 但主要代码风格还是以C语言为主
以下补充一些书籍中出现的宏定义和自定义类型

//函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1	//不可行
#define OVERFLOW -2		//溢出

//Status 是函数类型,其值是函数结果状态代码
typedef int Status;

以下主要记录具体代码实现,不再详细记录教材已有的具体理论内容

线性表

????????顺序表的具体实现

#include <stdio.h>
#include <stdlib.h>

//函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1	//不可行
#define OVERFLOW -2		//溢出

//Status 是函数类型,其值是函数结果状态代码
typedef int Status;

typedef char ElemType;		//自定义数据类型,根据实际需求设置即可
#define MAXSIZE 100

typedef struct {
	ElemType* elem;
	int length;
}SqList;

Status InitList_Sq(SqList& L) {		//构造一个空的顺序表L
	L.elem = new ElemType[MAXSIZE];	//为顺序表分配空间
	if (!L.elem) exit(OVERFLOW);	//存储分配失败
	L.length = 0;					//空表长度为0
	//printf("SqList Initialization Successful!\n");
	return OK;
}

void DestroyList(SqList& L) {
	if (L.elem) delete L.elem;		//释放存储空间
}

void ClearList(SqList& L) {
	L.length = 0;					//将线性表长度置为0
}

int GetLength(SqList& L) {			//获取线性表长度
	return (L.length);
}

int IsEmpty(SqList& L) {			//判断线性表是否为空
	if (L.length == 0) return TRUE;
	else return FALSE;
}

int GetElem(SqList L, int i, ElemType& e) {//获取第i个元素传递给e
	if (i<1 || i>L.length) return ERROR;
	e = L.elem[i - 1];
	return OK;
}

int LocateElem(SqList L, ElemType e) {    //查找元素e是否存在于L
	for (int i = 0; i < L.length; i++) {
		if (L.elem[i] == e) return (i + 1);
	}
	return 0;        //存在则返回其序号,不存在则返回0
}
//以下为查找元素方法 LocateElem(); 的另一种写法
//int LocateElem(SqList L, ElemType e) {
//	//在线性表L中查找值为e的数据元素,返回其序号(是第几个元素)
//	int i = 0;
//	while (i < L.length && L.elem[i] != e)i++;
//	if (i < L.length) return i + 1;//查找成功,返回序号
//	return 0;//查找失败,返回0
//}

void TraverList(SqList L) {		// 插入\删除方法中调用了该方法,故该方法需定义在插入\删除方法之前
	printf("   线性表中元素为:	");
	for (int i = 0; i < L.length; i++)
		printf("%c	", L.elem[i]);
	printf("\n");
}

Status InsertList(SqList& L, int i, ElemType e) {
	if (i<1 || i>L.length) return ERROR;	//i值不合法
	if (L.length == MAXSIZE) return ERROR;	//当前存储空间已满
	for (int j = L.length - 1; j >= i - 1; j--)
		L.elem[j + 1] = L.elem[j];		//将插入位置及之后的元素后移一个单位
	L.elem[i - 1] = e;					//将新元素e放入第i个位置
	L.length++;							//表长增加 1
	TraverList(L);
	return OK;
}

Status DeleteList(SqList& L, int i, ElemType& E) {
	if ((i < 1) || (i > L.length)) return ERROR;	//i值不合法
	E = L.elem[i - 1];
	for (int j = i; j < L.length; j++)
		L.elem[j - 1] = L.elem[j];
	L.length--;
	TraverList(L);
	return OK;
}

int main() {
	SqList L;
	ElemType E = NULL;
	int index = 1;

	//初始化线性表并输出初始化状态
	printf(">>>初始化线性表状态:%d\n\n", InitList_Sq(L));

	//手动赋初值
	L.elem[0] = 'a';
	L.length++;
	L.elem[1] = 'b';
	L.length++;
	L.elem[2] = 'c';
	L.length++;
	L.elem[3] = 'd';
	L.length++;
	L.elem[4] = 'e';
	L.length++;
	TraverList(L);
	printf("\n");

	//测试 输出测试结果:

	//测试 GetLength();
	printf(" >>获取线性表长度:%d\n\n", GetLength(L));

	//测试 IsEmpty();
	printf(" >>判断线性表是否为空:%d\n\n", IsEmpty(L));

	//测试 GetElem();
	int GE = GetElem(L, index, E);
	printf(" >>获取元素标号:%d		获取状态:%d		元素内容:%c\n\n", index, GE, E);

	//测试 LocateElem();
	E = 'e';
	int LE = LocateElem(L, E);
	printf(" >>查找元素:%c		元素位置:%d\n\n", E, LE);

	//测试 InsertList();
	E = 'A';
	int IL = InsertList(L, index, E);
	printf(" >>插入元素:%c		插入位置:%d		插入状态:%d\n", E, index, IL);
	GE = GetElem(L, index, E);
	printf("  >获取元素标号:%d		获取状态:%d		元素内容:%c\n", index, GE, E);
	printf("  >获取线性表长度:%d\n\n", GetLength(L));

	//测试 DeleteList();
	int DI = DeleteList(L, index, E);
	printf(" >>删除元素标号:%d		删除状态:%d		删除元素值:%c\n", index, DI, E);
	printf("  >获取线性表长度:%d\n", GetLength(L));
	GE = GetElem(L, index, E);
	printf("  >获取元素标号:%d		获取状态:%d		元素内容:%c\n\n", index, GE, E);

	return OK;
}

运行结果: