C++数据结构——表

1.简介

形如A1，A2,、、、、An是一个一般的表，我们说这个表的大小为n。而且我们将大小为0的表叫做空表。

2.基本结构

首先我们来讲讲表的两种基本实现方式：顺序结构和链式结构
顺序结构：顺序结构使用的是数组来实现各种数据结构，它的好处是能够快速的找到对应的元素，缺点是数组要求我们提前给出表的大小（这是非常严重的局限，尤其是你根本不确定表的大小的时候）并且插入和删除操作会消耗线性时间（在数组中进行插入和删除，后面的元素都要跟着向后/向前挪动一位，不要小看这个消耗，在你插入删除操作频繁时，这样的消耗是巨大的）。
链式结构：链式结构使用的是带有指针的结构实现，由于指针可以不连续存储，所以可以避免顺序结构的插入删除操作所花的线性开销，缺点是不能够直接通过下标查找（对比数组的查找），所以我们会专门写一个查找函数。
由于顺序结构可以直接使用数组实现且基本原理与链式结构相同，且缺点更为明显所以我们一般不使用顺序结构实现表，并且在本作者数据结构专栏中都会使用链式结构（除非顺序结构实现有独特之处）。

链表分为：单链表、双向链表、单双向循环链表等，它们的基本结构图如下：

单链表

双向链表

单向循环链表

在链表的创建过程中，我们基本都会创建一个头结点，头结点的作用是人为的给我们的链表找到入口，会给你接下来的操作带来很大的便利，推荐使用头结点。

3.头插法与尾插法

头插法

尾插法

上图中的方法就是头插法与尾插法的过程示例，步骤分别用编号表示
①：首先将待插入的结点连接到后结点
②：前结点连接到待插入结点
③：将原本前结点与后结点的连接删除
我们可以发现两种插入方式的步骤都是一样的，有区别的是插入时的位置（头插法一直在头结点后插入，尾插法一直在表的末尾插入）和插入后结点编号的顺序（头插法是4321，尾插法是1234），在使用时我们需要注意需求选择不同的插入方式，比如表中我们可以选择尾插法，这样我们在遍历表时我们可以得到顺序的编号。

4.表的基本操作

表的基本操作有增（Insert）、删（Delete）、查（Find）、判空（isEmpty）、判断末尾（isLast）

4.1链表的类型申明

typedef struct node* Node;
struct node{
	int Element;
	Node next;
};

4.2判空函数

//判断链表是否为空
bool isEmpty(Node head){
	return head->next==NULL;//如果头结点的下一个为空，证明为空链表
}

4.3判断末尾函数

//判断当前结点是否为末尾结点
bool isLast(Node L){
	return L->next==NULL;//如果当前结点的下一个为空，那么当前结点即为末尾结点
}

你突然发现，怎么判空函数和判断末尾的函数是一样的？它们的形式是一样的，但是含义却不一样，判空函数传进来的结点参数必须是头结点，只有当头结点的下一个结点为空的时候链表才是空的，而判断末尾函数所传进来的结点参数可以是链表中的任意一个结点，所以通常还需要遍历结点。

4.4插入函数

//插入一个值为x的结点,插入到参数结点的后面
void Insert(int x,Node L){
	Node p=new node;
	p->Element=x;
	p->next=L->next;//图中：步骤1
	L->next=p;//步骤2、3，将前结点连接到待插入结点，那么前结点与后结点的连接自然就断了
}

头插法和尾插法在传参时结点参数应该为头结点，尾插法传入末尾结点

4.5查找函数

//查找值为x的前驱结点
Node find(int x,Node L){
	Node p;
	p=L;
	while(p->next!=NULL&&p->next->Element!=x){
		p=p->next;
	}
	return p;
}

思考：为什么我们要找值为X的前驱结点，而不是它本身

4.6删除函数

想要删除一个结点，只需要将它的前驱结点和后驱结点链接起来，然后删除它本身就可以了

//删除一个值为x的结点
void Delete(int x,Node L){
	if(isEmpty(L))//如果链表为空，则直接返回
		return ;
	Node p=new node;
	p=findx(x,L);//找到值为X的前驱结点
	if(!isLast(p)){//
        Node temp=new node;
		temp=p->next;//temp结点是结点2的一个复制品
		p->next=temp->next;//步骤①完成时，P与2结点、2与3结点之间的链接自然断裂
		delete(temp);
	}
}

思考：我们为什么不直接用结点2找到结点3，而是用一个它的复制品

5.完整代码

#include<iostream>
using namespace std;
typedef struct node* Node;
struct node{
	int Element;
	Node next;
};
bool isEmpty(Node head){
	return head->next==NULL;
}
bool isLast(Node L){
	return L->next==NULL;
}
Node findx(int x,Node L){
	Node p;
	p=L;
	while(p->next!=NULL&&p->next->Element!=x){
		p=p->next;
	}
	return p;
}
void insert(int x,Node L){
	Node p=new node;
	p->Element=x;
	p->next=L->next;
	L->next=p;
}
void Delete(int x,Node L){
	if(isEmpty(L))
		return ;
	Node p=new node;
	Node temp=new node;
	p=findx(x,L);
	if(!isLast(p)){
		temp=p->next;
		p->next=temp->next;
		delete(temp);
	}
}
void print(Node L){//输出函数
	while(L->next!=NULL){
		cout<<L->next->Element<<" ";
		L=L->next;
	}
	cout<<endl;
}
int main(){
	Node head=new node;
	head->next=NULL;//一定要指向NULL，因为判空等函数以此作为条件，还有些含义自己可以琢磨一下
//	头插法
//	for(int i=0;i<5;i++){
//		insert(i+1,head);
//	}

// 尾插法
	Node flag=new node;
	flag=head;//flag作为末尾结点传入
	for(int i=0;i<5;i++){
		insert(i+1,flag);
		flag=flag->next;
	}
	
	print(head);
	insert(6,head);
	print(head);
	Delete(3,head);
	print(head);
	return 0;
}

循环和双向链表基于上面的代码，自己可以尝试一下。

第一次写博客，有什么不足的地方欢迎大家指出