目录
  1. 1. 数据结构
    1. 1.1. 链表
      1. 1.1.1. 单链表
        1. 1.1.1.1. 构建
        2. 1.1.1.2. 链表中函数的实现:
          1. 1.1.1.2.1. 链表创建:
          2. 1.1.1.2.2. 遍历链表:
          3. 1.1.1.2.3. 链表长度:
          4. 1.1.1.2.4. 寻找数据:
          5. 1.1.1.2.5. 删除数据:
          6. 1.1.1.2.6. 链表排序:
          7. 1.1.1.2.7. 删除头节点后的第一个节点:
          8. 1.1.1.2.8. 链表逆转:
    2. 1.2. 栈与队列
      1. 1.2.1.
        1. 1.2.1.1. 栈的实现
          1. 1.2.1.1.1. 压栈
          2. 1.2.1.1.2. 出栈
          3. 1.2.1.1.3. 迷宫求解
      2. 1.2.2. 队列
        1. 1.2.2.1. 环队列顺序实现
    3. 1.3.
      1. 1.3.1. 树的定义
        1. 1.3.1.1. 通俗定义
        2. 1.3.1.2. 专业术语
      2. 1.3.2. 树的类别
      3. 1.3.3. 二叉树的性质
      4. 1.3.4. 二叉树的存储
        1. 1.3.4.1. 二叉树的存储结构
      5. 1.3.5. 二叉树的遍历
      6. 1.3.6. 树的同构
数据结构

数据结构

链表

单链表

  • 实现的功能

    • ==插入==:头插,尾插,按位置插入
    • ==删除==:头删,尾删,按位置删除,按值删除。
    • ==更改==:根据位置改变值
    • ==查找==:根据位置查找值,根据值查找第一次出现的位置
    • ==其他==:长度,逆转,遍历

  • ==其他说明==

    • 头结点一般不存储数据
    • 编写hpp文件时,注明#pragma once 之后在其他程序中直接引用

构建

==节点类==:

1
2
3
4
5
6
class Lnode//构建一个节点类
{
public:
int data;
Lnode *next;
};

==链表类==:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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;
};

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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;
}

链表中函数的实现:

链表创建:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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;
}
}
遍历链表:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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<<" ";
}
}
}
链表长度:
1
2
3
4
5
6
7
8
9
10
int linklist::GetLength() {
int count=0;
Lnode* p = head;
while (p->next!=NULL)
{
count++;
p = p->next;
}
return count;
}
寻找数据:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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;
}
}
删除数据:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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;
}

}
链表排序:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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;
}
}
}
删除头节点后的第一个节点:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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;
}
}
链表逆转:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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;
}

栈与队列

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

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

image-栈

栈的实现

  • 创建链栈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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;//栈顶

};
压栈
1
2
3
4
5
6
7
8
9
10
11
12
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;
}
出栈
1
2
3
4
5
6
7
8
9
10
11
12
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:)
  • 先导入之前写的栈类

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

1
2
3
4
5
6
7
8
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类型==

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

1
2
3
4
5
6
7
8
9
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函数来得到路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
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) 的结点数都达到最大个数(即1h-1层为一个满二叉树),第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。 )的深度为[log2~n]+1(向下取整)

    二叉树的存储

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

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

二叉树的存储结构

链表存储:

1
2
3
4
5
struct treeNode{
int Data;
treeNode* left;//指向左子节点
treeNode* right;//指向右子节点
}

二叉树的遍历

==先序遍历==

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

1
2
3
4
5
6
7
void preOrderTraversal(BinTree BT){
if (BT){
cout<<BT->Data;
preOrderTraversal(BT->Left);
preOrderTraversal(BT->Right);
}
}

==中序遍历==

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

1
2
3
4
5
6
7
void InorderTraversal(BinTree BT){
if(BT){
InorderTraversal(BT->Left);
cout<<BT->Data;
InorderTraversal(BT->Right);
}
}

==后序遍历==

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

1
2
3
4
5
6
7
void PostOrderTraversal(BinTree BT){
if(BT){
PostOrderTraversal(BT->Left);
PostOrderTraversal(BT->Right);
cout<<BT->Data;
}
}

树的同构

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

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

静态链表

静态树的结构

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

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

文章作者: Dr-xinyu
文章链接: https://dr-xinyu.github.io/2019/11/08/dataStructure/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 心雨
打赏
  • 微信
  • 支付寶