数据结构

链表

单链表

实现的功能
- ==插入==：头插，尾插，按位置插入
- ==删除==：头删，尾删，按位置删除，按值删除。
- ==更改==：根据位置改变值
- ==查找==：根据位置查找值，根据值查找第一次出现的位置
- ==其他==：长度，逆转，遍历
==其他说明==
- 头结点一般不存储数据
- 编写hpp文件时，注明#pragma once 之后在其他程序中直接引用

构建

==节点类==：

class Lnode//构建一个节点类
{
public:
	int data;
	Lnode *next;
};

==链表类==：

class linklist
{
public:
	linklist();//构造函数
	~linklist();//析构函数
	void travalLinklist();//遍历链表，输出链表的data 
	void createLinklist(int n);//创建一个链表
	int  GetLength();//得到链表的长度
	void DeleteElem(int data);//通过找到相同的值来删除节点
	void Deleteheadelem();
	Lnode* find(int n);//通过值找地址
	void reserve();//翻转链表
	void sort();
private:
	Lnode* head;
};

==链表创建头节点==：

linklist::linklist() {//创建一个只有头结点的链表，数据域类容为0，next指向null
	head = new Lnode;
	head->data = 0;
	head->next = NULL;
}
linklist::~linklist() {//销毁链表,链表不像顺序表那样free申请的空间的首地址就可以，而是每个节点都需要free
	Lnode* p;
	while (head->next!=NULL)
	{
		p = head;
		head = head->next;
		delete p;
	}
	delete head;
    head=nullptr;
    cout<<"链表已经销毁"<<endl;
}

链表中函数的实现：

链表创建：

void linklist::createLinklist(int n) {//从头结点开始延长链表
	Lnode* pnew, * ptemp;
	ptemp = head;
	if (n < 0)
	{
		cout << "输入的节点数有误" << endl;
		return;
	}
	for (int i = 0; i < n; i++) {
		pnew = new Lnode;
		cout << "请输入第" << i + 1 << "个节点的里的值:";
		cin >> pnew->data;
		pnew->next = NULL;
		ptemp->next = pnew;
		ptemp = pnew;
	}
}

遍历链表：

void linklist::travalLinklist() {//遍历链表，输出链表的值
	if (head == NULL || head->next == NULL)
	{
		cout << "链表为空表" << endl;/*链表为空表的判断方法：就是头结点是空节点
								或者头结点的指针域指向的是空节点，则这个链表为空表*/
	}
	else {
		Lnode* p = head;
		while (p->next != NULL)
		{
			p = p->next;
			cout << p->data<<" ";
		}
	}
}

链表长度：

int linklist::GetLength() {
	int count=0;
	Lnode* p = head;
	while (p->next!=NULL)
	{
		count++;
		p = p->next;
	}
	return count;
}

寻找数据：

Lnode* linklist::find(int n) {//输入这个节点的数据，返回节点的地址
	if (head == NULL || head->next == NULL) {
		cout << "链表为空表，不存在这个数据" << endl;
		return NULL;
	}
	else
	{
		Lnode* p = head->next;
		while (p->next != NULL)
		{
			if (p->data == n) {
				return p;
			}
			p = p->next;
		}
		return NULL;
	}
}

删除数据：

void linklist::DeleteElem(int n) {
	Lnode* ptemp = find(n);
	if (ptemp==head->next)
	{
		Deleteheadelem();
	}
	else
	{
		Lnode* p = head;
		while (p->next!=ptemp)//寻找删除的节点的上一个节点
		{
			p = p->next;
		}
		p->next = ptemp->next;
		delete ptemp;
		ptemp = nullptr;
	}

}

链表排序：

void linklist::sort() {//使用冒泡排序
	int len = GetLength();
	int temp;
	Lnode* p = head;
	for (int i = 0; i < len - 1; i++)
	{
		p = head->next;
		for (int j = 0; j < len - i - 1; j++) {
			if (p->data>p->next->data)//大的放后面，小的放前面
			{
				temp = p->data;
				p->data = p->next->data;
				p->next->data = temp;
			}
			p = p->next;
		}
	}
}

删除头节点后的第一个节点：

void linklist::Deleteheadelem() {
	Lnode* p = head;
	if (p==nullptr||p->next==nullptr)
	{
		cout << "该表为空表" << endl;
	}
	else {
		Lnode* temp = nullptr;
		p = p->next;
		temp = p->next;
		delete p;
		p = nullptr;
		head->next = temp;
	}
}

链表逆转：

void linklist:: reserve() {
	Lnode* temp = new Lnode;
	temp->next = nullptr;
	Lnode* cur = head->next;
	Lnode* net = cur->next;
	while (net != nullptr) {
		cur->next = temp->next;
		temp->next = cur;
		cur = net;
		net = cur->next;
	}
	cur->next = temp->next;
	head->next = cur;
	delete temp;
	cout << "链表已逆转" << endl;
}

栈与队列

栈

栈是一种特殊的顺序表或者链表

它规定了先进栈的元素后出栈

栈的实现

创建链栈

class node//链栈的节点
{
public:
	int data;
	node* next = nullptr;
    node(int data,int *next=nullptr):data(data),next(next){};
};
class arrayStack
{
public:
	arrayStack(){head=new node();}
	~Stack();
	void StackPush(int a);//压栈
	bool isEmpty() {//判断栈是否为空
		if (head == nullptr || head->next == nullptr)
		{
			return 1;
		}
		else return 0;
	};
	point pop();//弹栈
private:
	node* head;//栈顶
  
};

压栈

push(int a){
node* newNode=new node(t);//开辟一个新节点存数据
if(isEmpty()){
    head->next=newNode;
    newNode->next=nullptr;
}
    else{
node* temp=new node;
        temp->next=head->next;
        head->next=newNode;
        newNode->next=temp->next;
    }

出栈

int pop(){
if(isEmpty()){
cout<<"error,栈为空，无法弹出"<<endl;
}
else{
  temp->next=head->next;
  head->next=head->next->next;
  int data= temp->next->data;
  delete temp;
  return data;
  }
}

迷宫求解

这是一个大工程（:happy:）
先导入之前写的栈类

==创建表示迷宫坐标的点类==

class point//创建一个point类来存放矩阵中每个点的位置坐标与下一次的方向
{
public:
	int i;
	int j;
	int direction;//上下左右移动
	point(int r = 0, int c = 0, int d = 0) :i(r), j(c), direction(d) {};
};

==栈里面的data 类型不再是int类型，而是point类型==

使用一个结构体+函数来表示点向那个方向移动

typedef struct {
	int i, j;
}dir;
void how_to_move(dir move[4]) {//下（i+1），右（j+1），上（i-1),左(j-1)
	move[0].i = 1, move[0].j = 0;
	move[1].i = 0, move[1].j = 1;
	move[2].i= -1, move[2].j = 0;
	move[3].i = 0, move[3].j = -1;
}

最后用一个Getpath函数来得到路径

void getPath() {
	int i, j, x = 0, y = 0, d = 0;
	point start(1, 1, -1);//迷宫起点
	maze[1][1] = -1;//设置为走过的路
	point p;
	dir mymove[4];//4个方向
	how_to_move(mymove);
	Stack a;
	a.StackPush(start);
	while (!a.isEmpty()) {
		p = a.pop();
		i = p.i;
		j = p.j;
		d = p.direction + 1;
		while (d < 4) {//往一个方向走，如果能走通，那就把这个点压入栈，然后继续这个方向，看下一个点。如果下一个点的这个方向也能通，就继续把这个点压入栈。如果不通，就看这个点的其他方向，如果都不通，就把这点弹栈，然后看栈里的下一个点
			x = mymove[d].i + i;
			y = mymove[d].j + j;
			if (maze[x][y]==0)
			{
				p.direction = d;
				a.StackPush(p);
				i = x;
				j = y;
				maze[i][j] = -1;
				point nw(i, j, -1);
				a.StackPush(nw);
				if (i == 9 && j == 8)
				{
					while (!a.isEmpty()) {
						p = a.pop();
						if (p.direction == -1)
						{
							cout << "(" << p.i << "," << p.j << "," << p.direction + 3 << ")" << " ";
						}
						else
						{
							cout<< "(" << p.i << "," << p.j << "," << p.direction + 1 << ")" << " ";
						}
					}
					return;
				}
				else
				{
					break;//这个break是跳出while(d<4)这个循环，让新的栈顶来出栈
				}
			}
			else{ d++; }//这代表了一个方向是不通的，所以换另外一个方向
			
		}
	}
	cout << "迷宫没有通路" << endl;
	return;

}

队列

队列也是一种特殊的线性表，可以使用顺序表或者链表来实现
队列的特性：先进先出

环队列顺序实现

1 2	#include<iostream> using namespace std;

树

树的定义

有且只有一个称之为根的节点
有若干个互不相交的子树，这些子树本身也是一棵树

通俗定义

树是由节点和边组成
每个节点只有一个父节点但是可以有多个子节点
但是有一个节点例外，该节点没有父节点，此节点称为根节点

专业术语

深度：从根节点到最底层节点的层次称之为深度。根节点是第一层。
叶子节点：没有子节点的节点。（最底层的节点）
度：一个节点的子节点的个数
树的度：以含有最大子节点的那个节点的度称为树的度

树的类别
- 一般树：任意一个节点的子节点的个数不受限制
- 二叉树：任意一个节点的子节点的个数最多为两个。而且子节点的位置不可更改（子节点有顺序）
- 森林

二叉树的性质

在二叉树的第i层上最多有2^i-1^个节点（i>=1)
二叉树中如果深度为k,那么最多有2^k^-1个节点。(k>=1）
n0=n2+1.n0表示度数为0的节点数，n2表示度数为2的节点树。
具有n个节点的完全二叉树（完全二叉树是由满二叉树而引出来的，若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数(即1~~h-1层为一个满二叉树)，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。）的深度为[log~~2~n]+1(向下取整)

二叉树的存储
完全二叉树可以使用数组来实现。

一般树的存储可以使用完全二叉树的结构来存储。（可能会有很多垃圾点）浪费空间

二叉树的存储结构

链表存储：

struct treeNode{
int Data；
treeNode* left;//指向左子节点
treeNode* right;//指向右子节点
}

二叉树的遍历

==先序遍历==

遍历过程：访问根节点，先序遍历其左子树，先序遍历其右子树。

void preOrderTraversal(BinTree BT){
 if (BT){
 cout<<BT->Data;
 preOrderTraversal(BT->Left);
 preOrderTraversal(BT->Right);
 }
}

==中序遍历==

遍历过程：先序遍历其左子树，访问根节点。再遍历其右子树。是使用递归。

void InorderTraversal(BinTree BT){
if(BT){
InorderTraversal(BT->Left);
cout<<BT->Data;
InorderTraversal(BT->Right);
 }
}

==后序遍历==

遍历过程，后序遍历其左子树，然后右子树，最后是根

void PostOrderTraversal(BinTree BT){
if(BT){
PostOrderTraversal(BT->Left);
PostOrderTraversal(BT->Right);
cout<<BT->Data;
  }
}

树的同构

约定两棵树T1与T2,如果T1可以通过若干次的左右孩子的互换而变成T2，我们就称两棵树是同构的。

二叉树的表示结构：静态链表。即物理存储上使用数组，思想上上使用链表

结构中，用左右int 值存储的是它的左右儿子在数组中的下标。

根节点的寻找：静态链表的输入值中，根节点的输入不一定是第一个。那么根节点是哪一个，在数组的哪个位置就需要我们寻找。判断根节点的方法就是看哪个数据的下标没有被指到过。没有被指向过的数组元素就是根节点。