目录

前言

前提说明

线性表

顺序表 (随机存取)

顺序表的具体实现

链表 (顺序存取)

单链表的具体实现

循环链表的具体实现

双向链表的具体实现

栈

队列

//未完

前言

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

使用书籍: 数据结构 (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 

//函数结果状态代码
#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(">>>初始化线性表状态:%dnn", 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(" >>获取线性表长度:%dnn", GetLength(L));

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

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

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

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

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

	return OK;
}

运行结果:

---

链表 (顺序存取)

单链表/双链表/循环链表:

• 结点只有一个指针域的链表,称为单链表或线性链表, 指针域存放其直接后继的地址,尾结点的指针域存放NULL;
• 结点有两个指针域的链表,称为双链表, 其中一个指针域存放直接前驱地址,另一个存放直接后继地址;
• 首尾相连的链表称为循环链表 (尾结点指针域存放头节点地址);

头指针/头节点/首元结点:

• 头指针 : 是指向链表中第一个结点的指针
• 首元结点 : 是链表中存储第一个数据元素的结点
• 头节点 : 实在链表首元结点之前附设的一个结点 (起一系列辅助作用)

单链表的具体实现

• 单链表中基本操作的实现

#include 

//函数结果状态代码
#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;

typedef struct Lnode {
	ElemType data;	//数据域
	struct Lnode* next;	//指针域  (嵌套定义)
}Lnode, * linkList;	//通常习惯于用Lnode指向某一结点,用linkList指向整个链表(也就是指向头结点)

Status InitList_L(linkList& L) {
	L = new Lnode;	//与顺序表申请一块连续空间不同,链表只需申请出一个该结点类型空间即可
	L->next = NULL;	//头结点指向NILL,即将 L 置为空表
	return OK;
}

int IsEmpty(linkList L) {	//若L为空表,则返回1,否则返回0
	if(L->next)	//非空
		return 0;
	else
	return 1;
}

int GetLength(linkList L) {
	linkList p;
	p = L->next;
	int i = 0;
	while (p) {
		i++;
		p = p->next;
	}
	return i;
}

Status DestroyList_L(linkList &L) {
	Lnode* p;	//或 linkList p;
	while (L) {	//L指向NULL时 跳出循环
		p = L;
		L = L->next;
		delete p;
	}
	return OK;
}

Status ClearList(linkList& L) {
	Lnode* p, * q;
	p = L->next;
	while (p) {	//没到表尾
		q = p->next;
		delete p;
		p = q;
	}
	L->next = NULL;	//头结点指针域为空
	return OK;
}

void TraverList(linkList L) {
	Lnode* p;
	p = L->next;
	printf(".>>遍历链表内容: ");
	while (p) {
		printf(" %c ",(p->data));
		p = p->next;
	}
	puts("");
}

int main() {
	linkList L;		//头结点用 linkList 定义,表示指向该链表
	printf(">>>链表初始化状态:%dn", InitList_L(L));

	//手动输入数据
	Lnode* L1; InitList_L(L1);	//成员结点用 Lnode* 定义,表示指向某一成员结点
	L->next = L1; L1->data = 'a';
	
	Lnode* L2; InitList_L(L2);
	L1->next = L2; L2->data = 'b';
	
	Lnode* L3; InitList_L(L3);
	L2->next = L3; L3->data = 'c';

	Lnode* L4; InitList_L(L4);
	L3->next = L4; L4->data = 'd';

	Lnode* L5; InitList_L(L5);
	L4->next = L5; L5->data = 'e';
	L5->next = NULL;
	
    //功能测试
	printf(".>>链表是否为空:%dn",IsEmpty(L));
	printf(".>>链表长度:%dn", GetLength(L));
	TraverList(L);
	//printf(".>>链表销毁状态:%dn", DestroyList_L(L));
	printf(".>>清空线性表状态:%dn",ClearList(L));
	printf("..>链表长度:%dnn", GetLength(L));
	
	return 0;
}

运行结果:

• 单链表中重要操作的实现

#include 

//函数结果状态代码
#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;

typedef struct Lnode {
	ElemType data;	//数据域
	struct Lnode* next;	//指针域  (嵌套定义)
}Lnode, * linkList;	//通常习惯于用Lnode指向某一结点,用linkList指向整个链表(也就是指向头结点)

int GetLength(linkList L) {
	linkList p; p = L->next; int i = 0;
	while (p) { i++; p = p->next; }
	return i;
}
void TraverList(linkList L) {
	Lnode* p; p = L->next;
	printf("..>遍历链表内容: ");
	while (p) { printf(" %c ", (p->data)); p = p->next; }
	puts("");//换行
}

//以下为单链表的重要操作
void CreateList_H(linkList& L, int n) {	//头插法建表 n为表长  倒位序输入
	L = new Lnode; L->next = NULL;	//先建立一个带头结点的空单链表
	printf("请输入%d个元素:", n);
	for (int i = n; i >= 1; i--) {
		Lnode* p = new Lnode;	//生成新结点 p=(Lnode*)malloc(sizeof(Lnode));
		p->data = getchar();	//输入元素值//scanf(...);
		getchar();	//抵消输入时造成的额外 空格/回车/制表符等  若注释该行,则输入数据时需要连着输入
		p->next = L->next;
		L->next = p;
	}
}

void CreateList_R(linkList& L, int n) {	//尾插法建表 n为表长  正位序输入
	L = new Lnode; L->next = NULL;
	Lnode* r = L;	//尾指针r指向空表的头结点
	printf("请输入%d个元素:", n);
	for (int i = 0; i < n; i++) {
		Lnode* p = new Lnode; p->data = getchar(); getchar();	//生成新结点,输入元素值
		p->next = NULL;
		r->next = p;		//插到表尾
		r = p;		//r指向新的尾结点
	}
}

Status GetElem(linkList L, int i, ElemType& e) {	//获取线性表L中的第i个元素,通过e返回
	Lnode* p = L->next; int j = 1;		//初始化
	while (p && j < i) {		//向后扫描,直到p指向第i个元素或p为空
		p = p->next; j++;
	}
	if (!p || j > i) return ERROR;	//第i个元素不存在
	e = p->data;		//取第i个元素
	return OK;
}

Lnode* LocateElem_L(linkList L, ElemType e) {	//返回地址型查找
	Lnode* p = L->next;
	while (p && p->data != e) {
		p = p->next;
	}
	return p;
}

int LocateElem(linkList L, ElemType e) {	//返回位置序号型查找
	Lnode* p = L->next; int j = 1;
	while (p && p->data != e) {
		p = p->next; j++;
	}
	if (p) return j;
	else return 0;
}

Status InsertList(linkList& L, int i, ElemType e) {
	//在L中第i个元素前插入元素e
	Lnode* p = L; int j = 0;
	while (p && j < i - 1) {
		p = p->next; j++;	 //寻找第i-1个结点,p指向i-1结点
	}
	if (!p || j > i - 1) return ERROR;		//i大于表长+1或小于1,插入位置非法
	Lnode* s = new Lnode; s->data = e;		//生成新结点s,将结点s的数据域置为e
	s->next = p->next;
	p->next = s;
	return OK;
}

Status DeleteList(linkList& L, int i, ElemType& e) {
	//将线性表中第i个元素删除,并用e将所删除元素返回
	Lnode* p = L; int j = 0;
	while (p->next && j < i - 1) {
		p = p->next; j++;			//寻找第i个结点,并令p指向其前驱
	}
	if (!(p->next) || j > i - 1) return ERROR;	//删除位置不合理
	Lnode* q = p->next;			//临时保存被删除节点的地址以备释放
	p->next = p->next->next;	//改变 被删除结点 的 前驱结点的指针域,使其指向被删除结点的后继结点
	e = q->data;		//保存被删除结点的数据域
	delete q;			//释放被删除结点的空间
	return OK;
}


int main() {
	linkList L;		//头结点用 linkList 定义,表示指向该链表
	int index = 5;
	ElemType E = NULL;

	//功能测试
	CreateList_R(L, 5);
//	CreateList_H(L, 5);
	printf(".>>链表长度:%dn", GetLength(L));
	TraverList(L);

	GetElem(L, index, E);
	printf(".>>取值标号:%d		取值状态:%d		取值内容:%cn", index, GetElem(L, index, E), E);
	puts("----------------------------------------");
	E = 'a'; LocateElem(L, E);
	printf(".>>查找元素:%c		查得位置:%d (0-未查得)n", E, LocateElem(L, E));
	puts("----------------------------------------");
	E = 'A';
	int IL = InsertList(L, index, E);
	printf(".>>插入元素:%c		插入位置:%d		插入状态;%dn", E, index, IL);
	TraverList(L); puts("----------------------------------------");
	int DL = DeleteList(L, index, E);
	printf(".>>删除结点:%d		节点内容:%c		删除状态:%dn", index, E, DL);
	TraverList(L); puts("----------------------------------------");
	return 0;
}

运行结果: 

循环链表的具体实现

优点 : 从表中任一结点出发 均可找到表中其他结点.

注意 : 循环链表中没有使尾结点指向NULL , 故遍历循环链表的终止条件为当前指针是否等于头指针

#include 

typedef char ElemType;

typedef struct Lnode {
	ElemType data;	//数据域
	struct Lnode* next;	//指针域  (嵌套定义)
	struct Lnode* R;	//尾指针  (定义尾指针的目的时方便对循环链表的首尾进行操作)
}Lnode, * linkList;	//通常习惯于用Lnode指向某一结点,用linkList指向整个链表(也就是指向头结点)


void CreateList_R(linkList& L, int n) {	//尾插法建表 n为表长  正位序输入
	L = new Lnode;
	L->next = L;	//使空表L首尾相连 (自己指向自己)
	Lnode* r = L;	//定义尾指针r指向空表的头结点

	printf("请输入%d个元素:", n);
	for (int i = 0; i < n; i++) {
		Lnode* p = new Lnode; p->data = getchar(); char disTab = getchar();	//生成新结点,输入元素值
		p->next = L;		//尾结点指向头结点 构成循环链表
		r->next = p;		//插到表尾
		r = p;				//r指向新的尾结点
		L->R = r;			//尾指针指向尾结点
	}
}

int main() {
	linkList L;		//头结点用 linkList 定义,表示指向该链表

	//功能测试
	CreateList_R(L, 3);
	printf("头结点地址:%p  n",L);
	printf("第一结点地址:%p  该结点数据:%c n", L->next, L->next->data);
	printf("第二结点地址:%p  该结点数据:%c n", L->next->next, L->next->next->data);
	printf("第三结点地址:%p  该结点数据:%c n", L->next->next->next, L->next->next->next->data);
	printf("尾指针指向结点地址:%p  该结点数据:%c n", L->R, L->R->data);
	printf("第三结点->next地址:%p	(注意是否与头结点地址相同)n", L->next->next->next->next);
	return 0;
}

运行结果:

---

表长为0时的运行结果:

可见空表的next地址还是指向自己

	CreateList_R(L, 0);    //表长参数设为0

---

两个 循环链表 合并的具体实现 (对尾指针进行操作)

#include 

typedef char ElemType;

typedef struct Lnode {
	ElemType data;	//数据域
	struct Lnode* next;	//指针域  (嵌套定义)
}Lnode, * linkList;	


Lnode* CreateList_R(linkList& L, int n) {	//尾插法建表 n为表长  正位序输入
	L = new Lnode;
	L->next = L;	//使空表L首尾相连 (自己指向自己)
	Lnode* r = L;	//定义尾指针r指向空表的头结点

	printf("请输入%d个元素:", n);
	for (int i = 0; i < n; i++) {
		Lnode* p = new Lnode; p->data = getchar(); char disTab = getchar();	//生成新结点,输入元素值
		p->next = L;		//尾结点指向头结点 构成循环链表
		r->next = p;		//插到表尾
		r = p;				//r指向新的尾结点
	}
	return r;	//返回尾指针r  (目的是方便后续对循环链表的首尾进行操作)
}

linkList Connect(Lnode* RA, Lnode* RB) {//传入参数为两个循环链表的尾指针
	Lnode* p = RA->next;				//保存LA表的头结点
	RA->next = RB->next->next;	//把LB首元结点 连接在 LA尾结点
	delete RB->next;			//释放LB的头结点
	RB->next = p;				//修改指针 : LB的尾结点 指向 LA的头结点
	return RB->next;			//返回值是表头,所以这里再"next"一下
}

void TraverList(linkList L) {
	Lnode* p; p = L->next;
	printf("..>遍历链表内容: ");
	while (p!=L) { printf(" %c ", (p->data)); p = p->next; }
	puts("");//换行
}

int main() {
	linkList La;
	linkList Lb;
	linkList Lc;

	//功能测试 (建表函数会返回链表尾指针,故接下来在建表的同时接收其尾指针)
	printf("La > "); 
    Lnode * Ra = CreateList_R(La, 3);
	printf("Lb > "); 
    Lnode * Rb = CreateList_R(Lb, 3);
	
	printf("合并前La内容"); TraverList(La);
	printf("合并前Lb内容"); TraverList(Lb);

	Lc = Connect(Ra,Rb);

	printf("合并后Lc内容"); TraverList(Lc);

	return 0;
}

运行结果:

---

双向链表的具体实现

说明 : 与之前不同的操作主要是插入与删除结点,其他类似操作不再一一实现

注意 : 双向链表的头结点前驱置空 , 尾结点后继置空

双向循环链表 : 将双向链表和循环链表结合一下即可实现,不在赘述.

#include 

#define OK 1
#define ERROR 0
typedef int Status;
typedef char ElemType;

typedef struct Lnode {
	ElemType data;	//数据域
	struct Lnode* next, * prior;	//指针域 包括"前驱指针"和"后继指针" (嵌套定义)
}Lnode, * linkList;

Status InitList_L(linkList& L) {
	L = new Lnode;
	L->next = NULL; L->prior = NULL;	//头结点的 前驱/后继 都指向NILL,即将 L 置为空表
	return OK;
}

void InsertList(linkList& L, int i, ElemType e) {	//暂时只考虑功能的实现,不考虑代码健壮性
	//在L中第i个元素前插入元素e
	Lnode* p = L; int j = 0;
	while (p && j < i - 1) {
		p = p->next; j++;	 //寻找第i-1个结点,p指向i-1结点
	}
	Lnode* s = new Lnode; s->data = e;
	s->next = p->next;
	p->next->prior = s;
	p->next = s;
	s->prior = p;
}

void DeleteList(linkList& L, int i, ElemType &e) {	//暂时只考虑功能的实现,不考虑代码健壮性
	Lnode* p = L; int j = 0;
	while (p && j < i - 1) {
		p = p->next; j++;	 //寻找第i-1个结点,p指向i-1结点
	}
	Lnode* s = p->next;	//记录被删除结点地址
	e = s->data;	//传出被删除结点中的数据
	s->next->prior = p;
	p->next = s->next;
	delete s;
}

void TraverList(linkList L) {
	Lnode* p;
	p = L->next;
	printf(".>>遍历链表内容: ");
	while (p) {
		printf(" %c ", (p->data));
		p = p->next;
	}
	puts("");
}

int main() {
	linkList L;
	printf(">>>链表初始化状态:%dn", InitList_L(L));

	//手动输入数据
	Lnode* L1; InitList_L(L1);
	L1->data = 'a';
	L->next = L1; L->prior = L;

	Lnode* L2; InitList_L(L2);
	L2->data = 'b';
	L1->next = L2; L2->prior = L1;

	Lnode* L3; InitList_L(L3);
	L3->data = 'c';
	L2->next = L3; L3->prior = L2;

	Lnode* L4; InitList_L(L4);
	L4->data = 'd';
	L3->next = L4; L4->prior = L3;

	Lnode* L5; InitList_L(L5);
	L5->data = 'e';
	L4->next = L5; L5->prior = L4;
	L5->next = NULL;

	//功能测试
	TraverList(L);
	puts("---------------------------");
	printf("..>L1的后继是: %c n", L1->next->data);
//	printf("..>L2的前驱是: %c ,L2的后继是: %c n", L2->prior->data, L2->next->data);
//	printf("..>L3的前驱是: %c ,L3的后继是: %c n", L3->prior->data, L3->next->data);
//	printf("..>L4的前驱是: %c ,L4的后继是: %c n", L4->prior->data, L4->next->data);
	printf("..>L5的前驱是: %c n", L5->prior->data);
	puts("---------------------------");
	InsertList(L, 2, 'A');
	TraverList(L);
	puts("---------------------------");
	char E = NULL;	//接收传出的被删除结点数据
	DeleteList(L,1,E);
	TraverList(L);
	puts("---------------------------");
	return 0;
}

运行结果:

---

栈

只能对表尾进行增删操作  后进先出

可用顺序栈或链栈存储 , 顺序栈较为常用

---

队列

只能对表尾进行增加操作 , 对表头进行删除操作  先进先出

可用顺序队或链队存储 , 顺序队较为常用

//未完