数据结构学习笔记＜1＞线性表 - 数据结构 - 笔记 | cosine = 余弦の博客 = WA 的一声就哭了

# 一、线性表的抽象数据类型描述

类型名：线性表（List）
数据对象集：线性表示 n (>=0) 个元素构成的有序序列 (a1,a2,……,an)
操作集：线性表 L∈List, 整数 i 表示位置，元素 X∈ElementType

# 二、顺序表

# 1. 定义

	struct LNode {
	ElementType Data[MAXSIZE];// 存了一个数组，其最多能存 MAXSIZE 个元素
	int Last;// 最后一个元素的下标！
	};
	typedef struct LNode *List;

访问下标为 i 的元素：L.Data [i] 或 PtrL->Data [i]
线性表的长度: L.Last+1 或 PtrL->Last+1;

# 2. 操作

其基本操作有

1.List MakeEmpty ();// 初始化一个空线性表
2.ElementType FindKth (int K, List Ptrl);// 返回下标为 K 的相应元素
3.int Find (ElementType X, List Ptrl);// 在线性表 L 中查找 X 的第一次出现位置
4.void Insert (ElementType X, int i, List Ptrl);// 在位序 i 前插入一个新元素 X
5.void Delete (int i, List Ptrl);// 删除指定位序 i 的元素
6.int Length (List Ptrl);// 返回线性表的长度 n**

下面我们来一一过一遍

# (1) 创建空表

	List MakeEmpty() {
	List PtrL;
	PtrL = (List)malloc(sizeof(struct LNode));
	PtrL -> Last = -1;
	return PtrL;
	}

# (2) 查找下标为 K 的元素

返回下标 K 的相应元素。

	ElementType FindKth(int K, List Ptrl) {
	return Ptrl->Data[K];
	}

# (3) 查找元素 X

返回下标，未找到返回 - 1。

	int Find(ElementType X, List Ptrl) {
	int i = 0;
	while(i <= PtrL->Last && PtrL->Data[i] != X)
	i++;
	if(i > PtrL->Last) return -1;// 如果没找到返回 - 1
	else return i;// 找到后返回的是存储位置即下标
	}

# (4) 插入

在第 i (1 ≤ i ≤ n+1) 个位置上插入一个值为 X 的新元素

	void Insert(ElementType X, int i, List Ptrl) {
	int j;
	if(Ptrl->Last == MAXSIZE-1) {// 表空间已满，则不能插入
	printf("表满");
	return;
	}
	if(i < 1 \|\| i > Ptrl->Last+2) {// 检查输入是否合法
	printf("位置不合法");
	return;
	}
	for(j = Ptrl->Last; j >= i-1; j--) // 注意这里顺序不能从前往后
	Ptrl->Data[j+1] = Ptrl->Data[j];
	Ptrl->Data[i-1] = X;
	Ptrl->Last++;//last 仍指向最后元素！
	return;
	}

# (5) 删除

删除第 i 个元素（下标为 i-1）

	void Delete(int i, List Ptrl) {
	int j;
	if(i < 1 \|\| i > Ptrl->Last+1) {// 检查输入是否合法
	printf("不存在第%d个元素",i);
	return;
	}
	for (j = i; j <= Ptrl->Last; j++) // 删除操作就必须从前往后了
	Ptrl->Data[j-1] = Ptrl->Data[j];
	Ptrl->Last--;
	return;
	}

# (6) 返回线性表的长度 n

删除第 i 个元素（下标为 i-1）

	int Length(List Ptrl){
	return Ptrl->Last + 1;
	}

# 3. 完整代码演示

	// 顺序表
	#include <iostream>
	using namespace std;
	typedef int ElementType;
	const int MAXSIZE = 1000;
	// 1. 定义部分
	struct LNode {
	ElementType Data[MAXSIZE]; // 存了一个数组，其最多能存 MAXSIZE 个元素
	int Last; // 最后一个元素的下标！
	};
	typedef LNode *List;
	// 2. 操作函数
	//(1) 建立空线性表
	List MakeEmpty() {
	List Ptrl; // 建立
	Ptrl = new struct LNode; // 为其分配第一个结点的空间
	Ptrl->Last = -1; // 还未存数据，下边设为 - 1
	return Ptrl; // 返回该指针
	}
	//(2) 查找下标为 K 的元素返回下标 K 的相应元素
	ElementType FindKth(int K, List Ptrl) {
	return Ptrl->Data[K];
	}
	//(3) 查找元素 X 返回下标未找到返回 - 1
	int Find(ElementType X, List Ptrl) {
	int i = 0;
	while (i <= Ptrl->Last && Ptrl->Data[i] != X) {
	i++;
	}
	if (i > Ptrl->Last)
	return -1;
	else
	return i;
	}
	//(4) 插入元素 X 在第 i (1 ≤ i ≤ n+1) 个位置上插入一个值为 X 的新元素
	void Insert(ElementType X, int i, List Ptrl) {
	if (Ptrl->Last == MAXSIZE - 1) { // 表空间已满，则不能插入
	printf("表满");
	return;
	}
	if (i < 1 \|\| i > Ptrl->Last + 2) { // 检查输入是否合法
	printf("位置不合法");
	return;
	}
	int j;
	for (j = Ptrl->Last; j >= i - 1; j--) // 注意这里顺序不能从前往后
	Ptrl->Data[j + 1] = Ptrl->Data[j];
	Ptrl->Data[i - 1] = X;
	Ptrl->Last++; //last 仍指向最后元素！
	return;
	}
	//(5) 删除删除第 i 个元素（下标为 i-1）
	void Delete(int i, List Ptrl) {
	int j;
	if (i < 1 \|\| i > Ptrl->Last + 1) { // 检查输入是否合法
	printf("不存在第%d个元素", i);
	return;
	}
	for (j = i; j <= Ptrl->Last; j++) // 删除操作就必须从前往后了
	Ptrl->Data[j - 1] = Ptrl->Data[j];
	Ptrl->Last--;
	return;
	}
	//(6) 返回线性表的长度 n
	int Length(List Ptrl){
	return Ptrl->Last + 1;
	}
	int main() {
	List P;
	P = MakeEmpty();
	for(int i = 0; i < 10; i++){
	Insert(i,i+1,P);
	}
	cout << "该顺序表长度为：" << Length(P) << endl;
	cout << "第5个元素为：" << FindKth(4,P) << endl;
	cout << "--删除第4个元素--" << endl;
	Delete(4,P);
	cout << "删除后第5个元素为：" << FindKth(4,P) << endl;
	cout << "表中是否有元素3(有则显示其下标无则显示-1)：" << Find(3,P) << endl;
	cout << "表中是否有元素5(有则显示其下标无则显示-1)：" << Find(5,P) << endl;
	delete [] P;
	return 0;
	}

输出结果为：

该顺序表长度为：10
第 5 个元素为：4
-- 删除第 4 个元素 --
删除后第 5 个元素为：5
表中是否有元素 3 (有则显示其下标无则显示 - 1)：-1
表中是否有元素 5 (有则显示其下标无则显示 - 1)：4

# 三、线性表的链式存储

重要！！链表即不要求逻辑上相邻的两个元素物理上也相邻，通过 "链" 建立起数据元素之间的逻辑关系。
其插入和删除不需要移动数据元素，只需要修改链。

# 1. 定义

	typedef struct LNode *List;
	struct LNode {
	ElementType Data;
	List Next;// 存放指向下一个结点的指针
	}L;
	List PtrL;

# 2. 操作

其基本操作有

1.List Insert (ElementType X, int i, List PtrL) ;// 插入 (在第 i-1 (1<=i<=n+1) 个结点后插入一个值为 X 的新结点)
2.List FindKth (int K, List PtrL) ;// 按序号查找查找查找链表中第 K 个元素
List Find (ElementType X, List PtrL) ; // 按值查找：查找元素 K
3.List Delete (int i, List PtrL);// 删除操作 (删除链表第 i 个位置上的结点)
4.int Length (List PtrL)// 求表长

# (1) 插入操作

在第 i-1 (1 ≤ i ≤ n+1) 个结点后插入一个值为 X 的新结点
(1) 先构造一个新结点，用 s 指向 //malloc 分配空间将 s 的数据 Data 赋值为 X
(2) 再找到链表的第 i-1 个结点，用 p 指向
(3) 然后修改指针，插入结点 (p 之后插入新结点是 s)
// 先将 p 原先的指向 next 给 s 的 next 指针，再将 p 的 next 指针指向 s

	List Insert(ElementType X, int i, List PtrL) {
	List p, s;
	if(i == 1) {// 新节点插入到表头
	s = (List)malloc(sizeof(struct LNode));// 申请、填装节点
	s->Data = X;
	s->Next = PtrL;
	return s; // 返回新表头指针
	}
	p = Find(i-1,PtrL); // 查找第 i-1 个结点
	if(p == NULL) { // 第 i-1 个不存在无法插入
	printf("参数i错");
	return NULL;
	} else {
	s = (List)malloc(sizeof(struct LNode)); // 申请、填装结点
	s->Data = X;
	s->Next = p->Next; // 新节点插入在第 i-1 个节点的后面
	p->Next = s;
	return PtrL;
	}
	}

# (2) 查找

找到则返回指向该结点的指针，找不到返回 NULL

# 1. 按值查找：Find

按值查找：查找元素 K

	List Find(ElementType X, List PtrL) {
	List p = PtrL;
	while(p != NULL && p->Data != X)
	p = p->Next;
	if(p == NULL) {
	cout << "找不到该元素" << endl;
	return NULL;
	} else return p;
	}

# 2. 按序号查找：FindKth

按序号查找查找查找链表中第 K 个元素

	List FindKth(int K, List PtrL) {
	List p = PtrL;
	int i = 1;
	while (p != NULL && i < K) {
	p = p->Next;
	i++;
	}
	if(i == K) return p;// 找到第 K 个返回指针
	else { // 否则返回空指针
	cout << "找不到该元素" << endl;
	return NULL;
	}
	}

# (3) 删除操作

删除链表第 i 个位置上的结点
(1) 先找到链表的第 i-1 个结点，用 p 指向；//Find (i-1,PtrL);
(2) 再用指针 s 指向要被删除的结点 (p 的下一个结点)//s = p->Next;
(3) 然后修改指针，删除 s 所指向的结点 //p->Next = s->Next;
(4) 最后释放 s 所指结点的空间！ //free (s)

	List Delete(int i, List PtrL) {
	List p, s;
	if( i == 1) { // 若要删除的是表的第一个结点
	s = PtrL; //s 指向第 1 个结点
	if (PtrL != NULL) PtrL = PtrL->Next; // 从链表中删除
	else return NULL;
	free(s); // 释放被删除结点
	return PtrL;
	}
	p = FindKth(i-1, PtrL); // 查找第 i-1 个结点
	if (p == NULL) {
	printf("第%d个结点不存在", i-1);
	return NULL;
	} else if (p->Next == NULL) {
	printf("第%d个结点不存在",i);
	return NULL;
	} else {
	s = p->Next; //s 指向第 i 个结点
	p->Next = s->Next; // 从链表中删除
	free(s); // 释放被删除结点的空间
	return PtrL;
	}
	}

# (4) 求表长

	int Length(List PtrL) {
	List p = PtrL;//p 指向表的第一个节点
	int j = 0;
	while(p) {
	p = p->Next;
	j++;
	}
	return j;
	}

# 3. 完整代码演示

	// 链表
	#include <iostream>
	using namespace std;
	typedef int ElementType;
	const int MAXSIZE = 1000;
	// 1. 定义部分
	struct LNode;
	typedef LNode *List;
	struct LNode {
	ElementType Data;
	List Next; // 存放指向下一个结点的指针
	};
	List Insert(ElementType X,int i,List PtrL);
	// 插入 (在第 i-1 (1<=i<=n+1) 个结点后插入一个值为 X 的新结点)
	List FindKth(int K, List PtrL); // 按序号查找查找查找链表中第 K 个元素
	List Find(ElementType X, List PtrL); // 按值查找：查找元素 K
	List Delete(int i, List PtrL); // 删除操作 (删除链表第 i 个位置上的结点)
	int Length(List PtrL); // 求表长
	// 2. 操作函数
	//(1) 插入操作在第 i-1 (1 ≤ i ≤ n+1) 个结点后插入一个值为 X 的新结点
	List Insert(ElementType X, int i, List PtrL) {
	List p, s;
	if (i == 1) { // 新节点插入到表头
	s = new struct LNode; // 申请、填装节点
	s->Data = X;
	s->Next = PtrL;
	return s; // 返回新表头指针
	}
	p = Find(i - 1, PtrL); // 查找第 i-1 个结点
	if (p == NULL) { // 第 i-1 个不存在无法插入
	printf("参数i错");
	return NULL;
	} else {
	s = new struct LNode; // 申请、填装结点
	s->Data = X;
	s->Next = p->Next; // 新节点插入在第 i-1 个节点的后面
	p->Next = s;
	return PtrL;
	}
	}
	//(2) 查找找到则返回指向该结点的指针，找不到返回 NULL
	List Find(ElementType X, List PtrL) {// 按值查找查找元素 X
	List p = PtrL;
	while(p != NULL && p->Data != X)
	p = p->Next;
	if(p == NULL) {
	cout << "找不到该元素" << endl;
	return NULL;
	} else return p;
	}
	List FindKth(int K, List PtrL) {// 按序号查找查找第 K 个元素
	List p = PtrL;
	int i = 1;
	while (p != NULL && i < K) {
	p = p->Next;
	i++;
	}
	if(i == K) return p;// 找到第 K 个返回指针
	else { // 否则返回空指针
	cout << "找不到该元素" << endl;
	return NULL;
	}
	}
	//(3) 删除删除链表第 i 个位置上的结点
	List Delete(int i, List PtrL) {
	List p, s;
	if( i == 1) { // 若要删除的是表的第一个结点
	s = PtrL; //s 指向第 1 个结点
	if (PtrL != NULL) PtrL = PtrL->Next; // 从链表中删除
	else return NULL;
	delete [] s; // 释放被删除结点
	return PtrL;
	}
	p = FindKth(i-1, PtrL); // 查找第 i-1 个结点
	if (p == NULL) {
	printf("第%d个结点不存在", i-1);
	return NULL;
	} else if (p->Next == NULL) {
	printf("第%d个结点不存在",i);
	return NULL;
	} else {
	s = p->Next; //s 指向第 i 个结点
	p->Next = s->Next; // 从链表中删除
	delete [] s; // 释放被删除结点的空间
	return PtrL;
	}
	}
	//(4) 求表长
	int Length(List PtrL) {
	List p = PtrL;//p 指向表的第一个节点
	int j = 0;
	while(p) {
	p = p->Next;
	j++;
	}
	return j;
	}
	int main() {
	List P = NULL;
	for (int i = 0; i < 10; i++) {
	P = Insert(i, 1, P);// 头插法插入元素在表头
	}
	List s;
	cout << "该链表长度为：" << Length(P) << endl;
	cout << "第4个元素为：";
	s = FindKth(4, P);
	if(s) cout << s->Data << endl;
	cout << "--删除第4个元素--" << endl;
	Delete(4, P);
	cout << "删除后第4个元素为：" ;
	s = FindKth(4, P);
	if (s) cout << s->Data << endl;
	cout << "表中是否有元素6：";
	s = Find(6, P);
	if (s) cout << s->Data << endl;
	cout << "表中是否有元素5：";
	s = Find(5, P);
	if (s) cout << s->Data << endl;
	delete[] P;
	return 0;
	}

输出结果为：

该链表长度为：10
第 4 个元素为：6
-- 删除第 4 个元素 --
删除后第 4 个元素为：5
表中是否有元素 6：找不到该元素
表中是否有元素 5：5

# 一、线性表的抽象数据类型描述

# 二、顺序表

# 1. 定义

# 2. 操作

# (1) 创建空表

# (2) 查找下标为 K 的元素

# (3) 查找元素 X

# (4) 插入

# (5) 删除

# (6) 返回线性表的长度 n

# 3. 完整代码演示

# 三、线性表的链式存储

# 1. 定义

# 2. 操作

# (1) 插入操作

# (2) 查找

# 1. 按值查找：Find

# 2. 按序号查找：FindKth

# (3) 删除操作

# (4) 求表长

# 3. 完整代码演示

广义表、多重链表初接触