数据结构_note

数据结构真的非常重要，不光是为了应付考试，至今觉得数据结构和编译原理没有学得特别好太遗憾了，给自己做个笔记

结合大话数据结构以及天勤2019数据结构计算机考研复习指导

PS：之前学数据结构的时候直接看严蔚敏的觉得太硬核了

第1章 绪论

具体是啥翻书，记录一下常用的
$$
O(1) <= O(log2(n)) <= O(n) <= O(nlog2(n)) <= O(n^2) <= O(n^3) <= O(2^n)
$$

第2章 线性表

线性表

定义：具有相同特性数据元素的一个有限序列，长度为元素个数

存储结构：顺序存储结构（顺序表）；链式存储结构（链表）

存储密度：结点值域所占存储量/节点结构所占存储量

1
2
顺序表：存储需要一块连续的存储空间，有随机访问特性，便于查找，可以随机存取以及顺序存取
链表：每个节点还需要包含逻辑关系信息，比如前驱和后继的地址，不需要连续的存储空间，可以动态分配，但没有随机访问特性，而且因为要存储地址信息，所以利用率低，便于插入，采取顺序存取

线性表结构定义

最常见的基本结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#define maxSize 100

//定义一个顺序表
typedef struct {
	int data[maxSize];  //存放顺序表元素数组
	int length;  //存放顺序表长度
}Sqlist;

//定义一个单链表
typedef struct LNode {
	int data;  //存放数据
	struct LNode *next;  //存放下一个节点的地址
}LNode;

//定义一个双向链表
typedef struct DLNode {
	int data;
	struct DLNode *prior;  //前驱结点的指针
	struct DLNode *next;  //后继结点的指针
}DLNode;

顺序表操作

插入元素

1
2
3
因为顺序表有序
第一步：找到位置
第二步：移动元素

删除元素

1
找到下表，删（向前移动）就完事了

单链表操作

[例1]已知A、B两个含有头结点的递增链表，并成一个元素非递减有序的链表

注：int *&p 定义一个指针引用,既可以改变指针指向的内容,也可以改变指针本身;

​ int *q 定义一个指针,可以改变指针指向的内容,但无法改变指针本身

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
//有序自增链表合并(合并后为自增)
void merge(LNode *A, LNode *B, LNode *&C) {
	LNode *p = A->next;  //指向第一个有数值的结点
	LNode *q = B->next;
	LNode *r;  //指向C的终端结点
	C = A;
	C->next = NULL;
	free(B);  //B的头结点已经没有用了，防止UAF
	r = C;
	while (p != NULL && q != NULL) {
		if (p->data <= q->data) {
			r->next = p;
			p = p->next;
			r = r->next;  //尾插法
		}
		else {
			r->next = q;
			q = q->next;
			r = r->next;
		}
		if (p != NULL)
			r->next = p;
		if (q != NULL)
			r->next = q;
	}
}

[例2]查找链表中是否存在元素值为x的结点，有的话就删了，返还1，否则返还0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//查找元素值并删除该结点
int findAndDelete(LNode *C, int x) {
	LNode *p, *q;
	p = C;
	//开始查找
	while (p->next != NULL) {
		if (p->next->data == x)
			break;  //找到了
		p = p->next;
	}
	if (p->next == NULL)
		return 0;  //没找到
	//开始删除结点
	else {
		q = p->next;
		p->next = p->next->next;
		free(q);
		return 1;  //完成删除
	}
}

刚开始还是比较容易的，暗自窃喜

双链表操作

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
//建立双向链表
void createDlistR(DLNode *&L, int a[], int n) {
	DLNode *s, *r;
	int i;
	L = (DLNode*)malloc(sizeof(DLNode));
	L->prior = NULL;
	L->next = NULL;
	r = L;  //尾插法
	for (i = 0; i < n; i++) {
		s = (DLNode*)malloc(sizeof(DLNode));  //创建一个新结点
		s->data = a[i];
		r->next = s;
		s->prior = r;
		r = s;
	}
	r->next = NULL;
}

//双链表查找元素为某值的结点
DLNode* findNode(DLNode *C, int x) {
	DLNode *p = C->next;
	while (p != NULL) {
		if (p->data == x)
			break;
		p = p->next;
	}
	return p;  //返还结点
}

//往双向链表插入节点
//略

//从双向链表删除节点
//略

插入和删除没必要详细些，无非就是单链表拆卸转向双链表拆卸，unlink的操作

循环链表的操作

循环链表可以分为循环单链表与循环双链表，有单链表和双链表演变而来

总而言之，尾节点指回头结点就好了（双链表无非就是两个方向都要指）

第七章 排序

直接插入排序

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
#pragma once
#include<stdio.h>
#include<stdlib.h>

/*
直接插入排序
找出第一个不满足顺序排列的元素
在之前顺序的队列中找到自己的位置并插入
可能会引起越界问题，可以选择哨兵，但我不喜欢，我比较喜欢用if
*/

void directInsert(int array[], int n) {
	int key = array[n];
	int i = n;
	while (array[i - 1] > key) {
		array[i] = array[i - 1];
		i--;
		if (i == 0)
			break;
	}
	array[i] = key;
}

void directInsortSort(int array[], int n) {
	int i;
	for (i = 1; i < n; i++) {
		directInsert(array, i);
	}
}

折半插入排序

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
#pragma once
#include<stdio.h>
#include<stdlib.h>

/*
直接插入排序的改进
直接找到最终位置然后插入
这次用哨兵方便，因为要考虑下标的二分问题
*/

void halfinsert(int array[], int n) {
	int temp;

	for (int i = 1; i < n; i++) {
		int low = 0;
		int hight = i - 1;
		temp = array[i];

		while (hight >= low) {
			int mid = (low + hight) / 2;
			if (array[mid] > temp) {
				hight = mid - 1;
			}
			else {
				low = mid + 1;
			}
		}

		for (int j = i - 1; j > hight; j--) {
			array[j + 1] = array[j];
		}

		array[hight + 1] = temp;
	}
}

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#pragma once
#include<stdio.h>
#include<stdlib.h>

/*
一个 so easy 的冒泡排序
*/

void bubble(int array[], int n) {
	for (int i = 0; i < n-1; i++) {
		if (array[i] > array[i + 1]) {
			int temp = array[i];
			array[i] = array[i+1];
			array[i+1] = temp;
		}
	}
}

void bubbleSort(int array[], int n) {
	for (int i = 0; i < n - 1; i++)
		bubble(array, n);
}

快速排序

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
#pragma once
#include<stdio.h>
#include<stdlib.h>

/*
对冒泡排序的改进
分而治之
递归
*/

int quick(int array[], int low, int high) {
	int pivot = array[high];
	while (low < high) {
		while (low < high&&array[low] <= pivot) low++;
		array[high] = array[low];
		while (low < high&&array[high] >= pivot) high--;
		array[low] = array[high];
	}
	array[low] = pivot;
	return low;
}

void quickSort(int array[], int low, int high) {
	if (low < high) {
		int pivot = quick(array, low, high);
		quickSort(array, low, pivot - 1);
		quickSort(array, pivot + 1, high);
	}
}

简单选择排序

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
#pragma once
#include<stdio.h>
#include<stdlib.h>

/*
一个简单的选择排序
每轮找一个最大的元素出来（找过的就不能找了）
然后交换位置
*/

int findMaxPos(int array[], int n) {
	int max = array[0];
	int pos = 0;
	for (int i = 1; i < n; i++) {
		if (max < array[i]) {
			max = array[i];
			pos = i;
		}
	}
	return pos;
}

void selectSort(int array[], int n) {
	for (int i = 0; i < n - 1; i++) {
		int pos = findMaxPos(array, n-i);
		int temp = array[pos];
		array[pos] = array[n - i - 1];
		array[n - i - 1] = temp;
	}
}

二路归并排序

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
#pragma once
#include<stdio.h>
#include<stdlib.h>

/*
分为n个子序表
两两归并
*/

int *aid = (int *)malloc((10 + 1) * sizeof(int));
void merge(int array[], int low, int mid, int high) {
	for (int k = low; k < high; k++)
		aid[k] = array[k];
	int i, j, k;
	for (i = low, j = mid + 1, k = i; i < mid&&j <= high; k++) {
		if (aid[i] <= aid[j])
			array[k] = aid[i++];
		else
			array[k] = aid[j++];
	}
	while (i <= mid) array[i++] = aid[i++];
	while (j <= high) array[k++] = aid[j++];
}

void mergeSort(int array[], int low, int high) {
	if (low < high) {
		int mid = (low + high) / 2;
		mergeSort(array, low, mid);
		mergeSort(array, mid + 1, high);
		merge(array, low, mid, high);
	}
}

个别算法小结

二叉树非递归后序遍历

其实我个人觉得递归的逻辑很容易理解，想学习用非递归来遍历二叉树的契机是因为一道题目让我不得不学起来，因为非递归后序遍历可以很快找出二叉树中根结点到某结点之间的路径

非递归后序遍历应该是三种遍历中最难的了，可以一步一步来

先列出存储结构代码

1
2
3
4
5
6
typedef struct TreeNode
{
    int Data;
    BinTree Left;
    BinTree Right;
}BiTNode，*BiTree;

我们先解决一下中序的非递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void InOrderTraversal(BiTree BT)
{ 
    BiTree T = BT;
    Stack S = CreatStack(MaxSize); //创建并初始化堆栈S
    while(T || !IsEmpty(S))
　　{
    　　while(T)    //一直向左并将沿途节点压入堆栈
    　　{ 
       　　 Push(S,T);
        　　T = T->Left;
    　　}
    　　if(!IsEmpty(S))
    　　{
       　　 T = Pop(S);                //节点弹出堆栈
       　　 printf("%d\n", T->Data);    //（访问） 打印结点
      　　  T = T->Right;              //转向右子树
    　　}
　　}
}

中序的逻辑其实不复杂，借助了一个辅助栈，如果发现该点有左结点，就将其压入栈，直到没有发现左节点时弹出，然后还需要检查弹出的这个结点是否有有结点，然后对这个有结点又要找是否有左结点，有的话再次压入栈中，周而复始，不断查询的过程，可能说的有点乱，抱歉，画个图就懂了

然后接下来就是后序的遍历咯

先序遍历顺序：根节点-左孩子-右孩子
后序遍历顺序：左孩子-右孩子-根节点
后序遍历倒过来：根节点-右孩子-左孩子

对比发现，先序和后序（倒）访问顺序只有左孩子和右孩子颠倒了一下

那么我们在先序遍历的时候左右调换，依次压入栈，然后出栈即可获得

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
void PostOrderTraversal(BiTree BT)
{
    BiTree T = BT;
    Stack S1 = CreatStack(MAX_SIZE);    //创建并初始化堆栈S1
    Stack S2 = CreatStack(MAX_SIZE);    //创建并初始化堆栈S2   
    while(T || !IsEmpty(S1))
    {
        while(T)        //一直向右并将沿途节点访问（压入S2）后压入堆栈S1 
        {
            Push(S2, T);
            Push(S1, T);
            T = T->Right;
        }
        if (!IsEmpty(S1))
        {
            T = Pop(S1);    //节点弹出堆栈
            T = T->Left;  //转向左子树
        }
    }
    while(!IsEmpty(S2))    //访问（打印）S2中元素
    {
        T = Pop(S2);
        printf("%d\n", T->Data);
    }          
}

这个方法空间复杂度确实一般，但我觉得比较好理解，还有另一种思路，等派上用处了再学吧

本文作者： xiaoyuyu
本文链接： http://woaixiaoyuyu.github.io/2019/03/28/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-note/
版权声明： 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处！
赏

谢谢你请我吃糖果

扫一扫，分享到微信

微信分享二维码
本站总访问量次 本站访客数人

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

记录成长的点滴<br><br>涉猎颇广的信息技术爱好者<br>希望未来的xiaoyuyu<br>可以成为优秀的工程师