线性表

顺序表

#include <stdio.h>
#include <stdlib.h>
// 常量定义
#define MAXSIZE 100

// 函数结果状态代码
#define TURE 1
#define FALSE 0
#define OK 1
#define ERROR 0
// infeasible 不可执行的
#define INFEASIBLE -1
// overflow 溢出的
#define OVEREFLOW -2

// Status 函数类型，用来表示函数结果状态代码
typedef int Status;
// ElemType 顺序表的数据类型
typedef char ElemType;

// 顺序表的基本结构
typedef struct {
	// 顺序表的数据
	ElemType* elem;
	// 顺序表的长度
	int length;
}SqList;

// 函数声明
Status InitList_Sq(SqList& L);
void DestoryList(SqList& L);
void ClearList(SqList& L);
int GetLength(SqList& L);
int IsEmpty(SqList& L);
int GetElem(SqList& L, int i, ElemType& e);
int LocateElem(SqList& L, ElemType e);
Status ListInsert_Sq(SqList& L, int i, ElemType e);
Status ListDelete_Sq(SqList& L, int i);

// 主函数
int main() {
	SqList L;
	// 初始化顺序表
	InitList_Sq(L);
	// 插入数据
	int i = 1;
	for (i; i <= 10; i++) {
		ListInsert_Sq(L, i, i);
	}
	// 取出数据
	ElemType e = 0;
	GetElem(L, 1, e);
	printf("位置为1的数据为%d\n", e);
	// 计算长度
	int length = GetLength(L);
	printf("顺序表的长度为%d\n", length);
	// 查找数据
	int index = LocateElem(L, 2);
	printf("数据2的位置在%d\n", index);
	// 删除数据
	ListDelete_Sq(L, 2);
	// 求顺序表是否为空
	if (IsEmpty(L)) {
		printf("顺序表为空\n");
	}
	else {
		printf("顺序表不为空\n");
	}
	// 清空顺序表
	ClearList(L);
	if (IsEmpty(L)) {
		printf("顺序表已清空\n");
	}
	// 销毁顺序表
	DestoryList(L);
	printf("顺序表已销毁\n");
	return 0;
}

// 初始化顺序表
Status InitList_Sq(SqList& L) {
	// C++语法,为顺序表分配空间
	// L.elem = new ElemType[MAXSIZE];
	// C语法，为顺序表分配空间
	L.elem = (ElemType*)malloc(sizeof(ElemType) * MAXSIZE);
	// 空间分配失败(空间分配成功，elem为数组的初始地址。空间分配失败，则elem为空）
	// 对elem进行逻辑非运算，如果elem为空，那么!L.elem为真，执行if中的代码块
	if (!L.elem) exit(OVEREFLOW);
	// 空表长度为0
	L.length = 0;
	return OK;
}

// 销毁顺序表
void DestoryList(SqList& L) {
	if (L.elem) {
		// C++语法,释放空间
		// delete L.elem;
		// C语法,释放空间
		free(L.elem);
	}
}

// 清空顺序表(逻辑清空）
void ClearList(SqList& L) {
	L.length = 0;
}

// 求顺序表的长度
int GetLength(SqList& L) {
	return (L.length);
}

// 判断顺序表是否为空
int IsEmpty(SqList& L) {
	if (L.length == 0) {
		return 1;
	}
	else {
		return 0;
	}
}

// 顺序表的取值，随机存取，时间复杂度O(1)
// L为顺序表，i为要取的元素位置，e为取出的元素
int GetElem(SqList& L, int i, ElemType& e) {
	//判断值是否合理，不合理，返回ERROR
	if (i<1 || i > L.length) {
		return ERROR;
	}
	// 第i-1的单元存储着第i个元素
	e = L.elem[i - 1];
	return OK;
}

// 顺序表的查找（按值查找）,时间复杂度O(n)
int LocateElem(SqList& L, ElemType e) {
	int i = 0;
	// 在顺序表中查找值为e的数据元素，返回其序号
	for (i; i < L.length; i++) {
		if (L.elem[i] == e) {
			// 查找成功，返回序号
			return i + 1;
		}
	}
	// 查找失败，返回0
	return 0;
}

// 顺序表的插入
Status ListInsert_Sq(SqList& L, int i, ElemType e) {
	// 判断插入位置是否合法
	if (i < 1 || i > L.length + 1) {
		return ERROR;
	}
	// 判断顺序表是否已经溢出
	if (L.length == MAXSIZE) {
		return ERROR;
	}
	// 将插入位置以后的所有元素向后移动一个单元
	int j = 0;
	for (j = L.length - 1; j >= i - 1; j--) {
		L.elem[j + 1] = L.elem[j];
	}
	// 将元素插入到对应位置
	L.elem[i - 1] = e;
	// 将顺序表的长度加一
	L.length++;
	return OK;
}

// 顺序表的删除
Status ListDelete_Sq(SqList& L, int i) {
	// 判断删除位置是否合法
	if (i < 1 || i > L.length) {
		return ERROR;
	}
	// 将删除位置后的数据向前移动一个单元
	int j = 0;
	for (j = i; j <= L.length - 1; j++) {
		L.elem[i - 1] = L.elem[i];
	}
	// 将顺序表的长度减一
	L.length--;
	return OK;
}

单链表

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;

// 函数结果状态代码
#define TURE 1
#define FALSE 0
#define OK 1
#define ERROR 0
// infeasible 不可执行的
#define INFEASIBLE -1
// overflow 溢出的
#define OVEREFLOW -2

// Status 函数类型，用来表示函数结果状态代码
typedef int Status;
// ElemType 顺序表的数据类型
typedef int ElemType;


// 创建单链表的结构
typedef struct node {
	// 单链表的数据域
	ElemType data;
	// 单链表的指针域
	struct node* next;
// LinkList是指向结构体Lnode的指针数据类型
}Lnode, * LinkList;

// 初始化空链表
Status initList_L(LinkList& L) {
	// C++语言，给L开辟指向Lnode的数据类型
	// L = new Lnode; 
	// C语言语法, 创建一个LinkList类型的变量
	L = (LinkList)malloc(sizeof(Lnode));
	// 将头节点的指针域置为空
	L->next = NULL;
	// 返回操作结果
	return OK;
}

// 判断链表是否为空
int ListEmpty(LinkList L) {
	// 判断头结点的指针是否为空
	// 为空，则表示为空链表，返回0
	// 不为空，则返回1
	if (L->next == NULL) {
		return 0;
	}
	else {
		return 1;
	}
}

// 销毁单链表
Status destroyList_L(LinkList& L) {
	// 创建一个指向链表结点的变量
	Lnode* p;
	while (L) {
		// 将当前结点赋值给变量p
		p = L;
		// 让L指向当前结点的下一个结点
		L = L->next;
		// 释放当前结点
		free(p);
	}
	// 返回操作结果
	return OK;
}

// 清空链表
Status ClearList(LinkList& L) {
	// 创建指向结点的两个指针变量
	Lnode* p, *q;
	// 让p指向头节点的下一个结点
	p = L->next;
	// 判断p是否为空，不为空循环执行
	while (p) {
		// 让q指向p的下一个结点
		q = p->next;
		// 释放当前结点
		delete p;
		// 让p指向q指向的结点
		p = q;
	}
	// 最后将头节点的指针域置为空
	L->next = NULL;
	// 返回操作结果
	return OK;
}

// 求单链表的表长
int ListLength_L(LinkList L) {
	// 让p指向首元结点
	Lnode* p = L->next;
	// 创建计数器
	int i = 0;
	// 判断当前结点是否为空
	while (p) {
		// 计数器加一
		i++;
		// 让p指向p的下一个结点
		p = p->next;
	}
	// 返回表长
	return i;
}

// 按照位置获取单链表中某个元素的内容 （时间效率：O(n)）
Status GetElem_L(LinkList L, int i, ElemType& e) {
	// 让p指向首元结点
	Lnode * p = L->next;
	// 初始化j
	int j = 1;
	// 循环遍历
	while (p && j < i) {
		// 让p指向p的下一个结点
		p = p->next;
		// 计数器加一
		j++;
	}
	// 如果p为空，说明遍历完了都没有j=i的时候，则位置i的元素不存在
	// j>i，说明i的位置不合理，都比第一个位置还要小
	if (!p || j > i) {
		// 元素不存在
		return ERROR;
	}
	// 获取第i个位置的元素
	e = p->data;
	// 返回处理结果
	return OK;
}

// 按照值查找某个元素的位置 （时间效率：O(n)）
int LocateElem_L(LinkList& L, ElemType e) {
	// 让p指向首元结点
	Lnode* p = L->next;
	// 创建计数器
	int j = 1;
	// 如果p存在，并且p的数据域中的值不等于e时，循环遍历
	while (p && p->data != e) {
		// 指针向后移动一位
		p = p->next;
		// 计数器加一
		j++;
	}
	// 如果p不为空，说明已经找到了元素，返回计数器的值（元素位置）
	if (p) return j;
	// 为空，则返回0
	else return 0;
}

// 在链表L中第i个元素之前插入数据元素e （时间效率：O(1)）
Status ListInsert_L(LinkList& L, int i, ElemType e) {
	// 让p指向头节点
	Lnode * p = L;
	// 创建计数器
	int j = 0;
	// 如果p不为空，且计数器j小于i-1时，循环遍历,直到找到第i - 1个位置的结点
	while (p && j < i - 1) {
		// 让p指向p的下一个结点
		p = p->next;
		// 计数器加一
		j++;
	}
	// 如果p为空，说明遍历到链表的末尾都未满足j = i - 1,则位置i超过了链表长度
	// 如果j从一开始就大于了i - 1,说明位置i小于1
	if (!p || j > i - 1) {
		return ERROR;
	}
	// 创建一个指向结点的指针变量
	Lnode * s = new Lnode;
	// 将e赋值给s的数据域
	s->data = e;
	// 让s的指针域指向p的下一个结点
	s->next = p->next;
	// 让p的指针域指向新节点s
	p->next = s;
	// 返回成功的结果
	return OK;
}

// 删除第i个位置的结点 （时间效率：O(1)）
Status ListDelete(LinkList& L, int i, ElemType& e) {
	// 创建指向头结点的指针变量p
	Lnode* p = L;
	// 创建指向结点的指针变量q
	Lnode* q = new Lnode;
	// 创建计数器
	int j = 0;
	// 如果p的下一个结点不为空并且计数器的值小于i-1，说明当前未找到第i-1个结点，循环遍历
	while (p->next && j < i - 1) {
		// 让p指向p的下一个结点
		p = p->next;
		// 计数器加一
		j++;
	}
	// 如果p的下一个结点为空，说明已经遍历到单链表的末尾了，则位置i-1大于链表长度
	// 如果j>i-1，说明i小于1，位置非法了
	if (!(p->next) || j > i - 1) {
		return ERROR;
	}
	// 让q指向p的下一个结点
	q = p->next;
	// 让p的指针域指向q的下一个结点，这样就删除了结点q
	p->next = q->next;
	// 将结点q中数据域的值赋值给e
	e = q->data;
	// 释放结点q
	delete q;
	// 返回成功的函数结果
	return OK;
}

// 建立链表:头插法
void CreateList_H(LinkList& L, int n) {
	// 判断当前链表是否初始化
	if (L->next != NULL) {
		L = new Lnode;
		L->next = NULL;
	}
	// 循环n次，直到所有数据都插入进去
	for (int i = n; i > 0; i--) {
		// 创建一个指向结点的指针变量p
		Lnode * p = new Lnode;
		// 通过键盘输入数据
		printf("请输入第%d个数据：" , n - i + 1);
		cin >> p->data;
		// 让p的指针域指向头节点的下一个结点
		p->next = L->next;
		// 让头节点的指针域指向结点p
		L->next = p;
	}
}

// 建立链表：尾插法
void CreateList_R(LinkList& L, int n) {
	// 判断当前链表是否初始化
	if (L->next != NULL) {
		L = new Lnode;
		L->next = NULL;
	}
	// 创建尾指针指向头节点
	Lnode* r = L;
	// 循环n次，直到所有数据都插入进去
	for (int i = 0; i < n; i++) {
		// 创建一个指向结点的指针变量p
		Lnode* p = new Lnode;
		// 将新节点的指针域置为空
		p->next = NULL;
		// 通过键盘输入数据
		printf("请输入第%d个数据：", i + 1);
		cin >> p->data;
		// 通过尾指针将新节点连接到链表后面
		r->next = p;
		// 让尾指针指向最新的一个结点
		r = p;
	}
}

// 遍历链表
void PrintfList(LinkList L) {
	Lnode* p = L->next;
	while (p) {
		cout << p->data <<" ";
		p = p->next;
	}
}

int main() {
	LinkList L;
	// 初始化链表
	int i = initList_L(L);
	if (i == 1) {
		printf("链表已初始化完成！\n");
	}
	// 判断链表是否为空
	i = ListEmpty(L);
	if (i == 0) {
		printf("链表为空链表！\n");
	}
	else {
		printf("链表不为空链表！\n");
	}
	// 建立链表：头插法
	CreateList_H(L, 3);
	// 建立链表：尾插法
	// CreateList_R(L, 3);
	// 遍历链表
	PrintfList(L);
	printf("\n");
	// 获取表长
	int length = ListLength_L(L);
	printf("表长为：%d\n", length);
	// 获取指定位置的元素
	ElemType e;
	GetElem_L(L, 1, e);
	printf("位置为1的元素为：%d\n", e);
	// 按值查找元素位置
	int locate = LocateElem_L(L, 1);
	printf("元素为1的位置为：%d\n", locate);
	printf("在第二个位置插入元素4:\n");
	ListInsert_L(L, 2, 4);
	// 遍历链表
	PrintfList(L);
	printf("\n");
	// 删除第2个位置的结点
	ListDelete(L, 2, e);
	printf("删除位置的元素为：%d\n", e);
	// 清空链表
	ClearList(L);
	// 判断链表是否清空
	i = ListEmpty(L);
	if (i == 0) {
		printf("链表已清空！\n");
	}
	else {
		printf("链表未清空！\n");
	}
	// 销毁链表
	destroyList_L(L);
	if (!L) {
		printf("链表已销毁！");
	}
	return 0;
}