TODOLIST·

  • 前缀、后缀求值和中缀到后缀转化P20,P21
  • [ ]

前言·

可能有点乱，因为自己的数据结构当时和算法balabala的，学的比较混杂，野路子，现在上着大学的课，是听不懂了，一是为了准备考试，二是提高编程能力，关于计算机底层中也会对此有所要求，例如：链表、栈、队列

确实有个弹幕说的还是蛮好的，关于数据结构用哪个语言来学，其实是无所谓，但是例如Python已经给你写好了，那么锻炼就很少，（这个是理解的，但当时自己学的时候就对C写链表等等的很排斥，想用C++的stl，后悔，应该踏踏实实的）

数据结构：课程导论_哔哩哔哩_bilibili

暂时打算看这个视频

印度老师哈沙·苏里亚纳拉亚纳 - 维基蒂亚 (wikitia.com) | MyCodeSchool 的故事：悲剧，成就和两个永远改变了编程教育的朋友 (freecodecamp.org)

确实有点口音，1.25倍速无所谓，重点是老师思路的引导真的会有很大的帮助

本篇计划只放置链表、栈、队列的内容

关于树、图、排序查找算法的内容见下一讲

正文·

从数组到链表的引入与比较·

在这个印度老师讲到抽象，举了电视只需要知道功能，而不需要了解原理，像是API一样封装起来；然后又转变到ADT抽象数据类型，举了List列表(可以实现存储、增删等功能，函数封装)的例子，真的突然一惊，原来ADT是这个作用

第二节关于LINKED LIST的引入确实很棒：由于想要实现LIST的某些功能，当然这在数组里也可以直接实现，但是除了查询以外，增删的时间复杂度都是O(N)，不适合动态，于是就引出了下一节的Linked List

感觉数据结构真的其实是那个时代基于已有的基本数据类型，结合要解决的问题(经常需要增删)，于是发明了链表等等；但是在大学学习的时候却变成了直接灌输这个概念，所以既没能点燃兴趣，也不理解到底学这为了什么，按道理说这种填鸭式，让你学啥就学啥效率是该高的，但对于自己，知道为什么学，反而更容易去加深理解！

确实，链表相较于数组的存储，在内存中的地址是不连续的，自然在查找时时间不恒定，需要从最开始遍历；而数组是连续的内存块，可以根据a[0]的地址(基址)+4字节数*下标

  • 数组的查找O(1)，需要提前知道元素个数且固定
  • 如果存储的为复杂的数据类型，那么链表其实相对划算(不需要额外规划)
  • 内存碎片问题，可能不会有大的内存块，只有许多小的存储单元
  • 链表的插入操作，若给定前驱节点，则时间复杂度均为O(1)。否则只能按序或按值查找前驱节点，时间复杂度为O(n)。
  • 数组使用更为简单，链表须考虑段错误或内存泄露

链表 C/C++实现·

链表：头部插入一个节点·

除了head的全局变量或者return返回以外，也可以采用head=insert(&head,x); 和 Node* insert(Node** pointer,int x)的方式

1
2
3
4
5
6
7
8
Node* insert(Node* head,int x){
	struct Node* temp = (Node*)malloc(sizeof(struct Node));
	temp->data = x;
	temp->next = NULL;
	if(head != NULL) temp->next = head;
	head = temp;
	return head;
}

在任意位置插入一个节点·

1
2
3
4
5
6
7
8
9
//上面为定义temp1和对于插入第一个元素的特殊判断
Node* temp2 = head;
for(int i=0;i<n-2;i++){//第X个从1开始计数，而下标从0开始||遍历到待插入位置的前一个
	temp2 = temp->next;
}
//例如将1 2 4 插入变成1 2 3 4
//干想不好想，脑子里画个图
temp1->next = temp2->next;//代表3的next = 2->next(4)
temp2->next = temp1;//2->next = 3

关于指针、栈、堆、global的知识没有怎么听懂，深入的话可以考虑移步：【强烈推荐】4小时彻底掌握C指针 - 顶尖程序员图文讲解 - UP主翻译校对 (已完结)_哔哩哔哩_bilibili

本来感觉4小时没那么长，可是看目录中的内容只有指针这一项，啊吧啊吧

mycodeschool 印度的顶尖程序员Harsha Suryanarayana为你图文讲解指针，希望他深入浅出的讲解能够真正帮助你彻底搞懂C指针。

任意位置删除一个节点·

  • fix the link（更改节点next 注意首；尾next->NULL）
  • free the space （将删除后的节点释放）

(38 封私信 / 80 条消息) 什么是语法糖？ - 知乎 (zhihu.com) 语法糖 - 维基百科，自由的百科全书 (wikipedia.org)

这次的代码比较简单，最后又简单通过画图的方式重新演绎了一遍

反转一个链表（迭代法）·

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct Node* Reverse(struct Node* head){
	struct Node *current,*prev,*next;//提出了当前和上一个结点的区分与记录
    current = head;
    prev = NULL;//头节点的上一个当然是NULL
    while(current != NULL){
        //顺序当然是有讲究的，是一步步推导出来的
        next = current->next;//关键：放在第一步，其余的也是往后移动即可
        current->next = prev;//现在的next节点是上一个，实现反转
        prev = current;
        current = next;
    }
    head = prev;
    return head;
}

当然自己只是抄了一遍代码

打印一个链表（递归）·

1
2
3
4
5
void ReversePrint(struct *p){
    if(p==NULL) return ;//递归结束
    ReversePrint(p->next);//**递归体**
    printf("%d "p->data);//与上一行若是调换顺序则为先打印
}

同时也讲了一些函数栈调用的知识，不懂

(3条消息) 使用递归顺序和逆序输出单链表_递归逆序打印单链表_逆羽飘扬的博客-CSDN博客

函数内，递归体前的顺序执行，递归体后的倒序执行

感觉直接这么记忆也可以

反转一个链表（递归）·

1
2
3
4
5
6
7
8
9
10
11
void Reverse(struct Node *p){
    if(p->next == NULL){
        head = p;//手动更换头节点,递归到达第一个节点替换
        return ;
    }
    Reverse(p->next);
    struct Node* q=p->next;//赋值
	q->next=p;//添加链接
    //上面两行也可写成p->next->next = p;
    p->next=NULL;//删除p节点的next，同时也为最后一个的节点设置next=NULL
}

双向链表的介绍与实现·

栈STACK·

对于ADT，重要的是其特性和操作，而非实现的细节，故而第一节只是简单地过一下。

特性：A list with the restriction that insertion and deletion ,can be performed only from one end,called the top.

操作：PUSH,POP,ISEMPTY,TOP

使用数组/链表实现一个栈·

直接用数组来构造栈，确实无论从理解还是实现都很简单，每次都是变动、调用last 的索引，就不写代码了

关于链表实现栈，直接采用头插法即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct Node* top = NULL;
void Push(int x){
	struct Node* temp = (struct Node*)malloc(sizeof(struct Node*));
	temp->data = x;
	temp->link = top;//link means Next,top means head
	top = temp;
}
void Pop(){
	struct Node *temp;
	if(top == NULL) return ;
	temp = top;
	top = top->link;
	free(temp);
}

栈：反转一个字符串或链表·

反转字符串利用了栈后进先出的特性

数组：

1
2
3
4
5
6
7
8
9
10
void Reverse(char *C,int n){
	stack<char> S;//STL库   数据结构类型<数据类型>  名称;
	for(int i=0;i<n;i++){
		S.push(C[i]);
}
	for(int i=0;i<n;i++){
		C[i] = S.top();
		S.pop();
}
}

当然也可以像数组常规的那样：在首尾分别定义i和j，向中间遍历，i j不等交换，相等结束。（元素个数单双）

链表：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void Reverse(){
	if(head == NULL) return ;
	stack<struct Node*> S;
	Node* temp = head;
	while(temp != NULL){
		S.push(temp);
		temp = temp->next;
	}
	temp = S.top();
	head = temp;
	S.pop();
	while(!S.empty()){
		temp->next = S.top();//一开始不理解为什么stack里next方向明明是正的，为什么能逆置
		//才知道其实靠的是这一步
		S.pop();
		temp = temp->next;
	}
	temp->next = NULL;
}

栈：检查括号的匹配性：·

原理：左括号入栈，右括号匹配（若此时栈为空也false），相同删掉，最后列表为空则匹配

使用栈的好处：只需要处理top单个元素（和前一个比较），插入、删除是O(1)

pintia上有道类似的题目，是升级成了程序检验（单行变多行，混杂非括号元素）大括号小括号，并且需给出缺失的是左括号还是右括号，忘是不是要求只能有一个缺失

这种不需要写代码，只给出伪代码的，自己听着更舒服，但实际上，这是一种偷懒的行为

栈：前缀、中缀、后缀的基本概念·

主题：对算数和逻辑表达式求值（Evaluation of expression）

中缀表达式：<operand><operator><operand> 操作数 操作符 操作数（当然，操作数也可以是括号括起来的表达式）

操作符的操作顺序：括号–>幂运算–>乘法除法–>加法减法

基于上述的操作顺序问题，提出了不需要括号也不会产生顺序歧义的表达式，不需要关心操作符的优先级或结合律的规则：

前缀（波兰）表达式和后缀表达式：

1
2
3
中缀：p-q  前缀：-pq   后缀： p q - 
中缀：a+b*c  前缀：+a*bc   后缀：abc * +
结合中缀表达式，画括号就理解了

前缀、后缀求值和中缀到后缀转化跳过

队列概念及数组、链表的实现·

队列可以用来模拟一系列需要等待的场景

队尾入队、对头出队、判空、取队头

数组的实现：

下标0到n-1，若空，入队，若空rear和front置0（判空条件为均为-1）；反之仅rear++，A[rear]=X（rear为索引）

最后又讲了循环队列的概念