印度小哥数据结构视频代码测试笔记
·
引子
最早看野火的开发板视频嵌入式Linux视频笔记----Linux基础入门
其中，P2 第1讲-为什么学习Linux开发 部分提到了C语言解释器GitHub - lotabout/write-a-C-interpreter: Write a simple interpreter of C. Inspired by c4 and largely based on it.
于是就看了手把手教你构建 C 语言编译器
看完发现没看懂，于是就去B站找文中提到的【如果要我说计算机专业最重要的三门课，我会说是《数据结构》、《算法》和《编译原理》。在我看来，能不能理解“递归”像是程序员的第一道门槛，而会不会写编译器则是第二道。】
于是就有了【强烈推荐】深入浅出数据结构 - 顶尖程序员图文讲解 - UP主翻译校对 (已完结)
看完了咖喱味的数据结构，感觉很有收获，于是决定把视频中的代码也测试下，就有了这篇笔记
我没翻墙，就用了评论里的别人整理的代码，修改了一点小错误，加了缩进，把部分C++代码改写为C代码
全部C/C++代码在这里https://download.csdn.net/download/gzc0319/88881845?spm=1001.2014.3001.5503
正文
P13: 双向链表的实现https://gist.github.com/mycodeschool/7429492 (C)
代码
/* Doubly Linked List implementation 双向链表的实现 */
#include<stdio.h>
#include<stdlib.h>
struct Node{
int data;
struct Node* next;
struct Node* prev;
};
struct Node* head; // global variable - pointer to head node. 全局变量--链表头指针
//Creates a new Node and returns pointer to it. 创建结点，返回指针
struct Node* GetNewNode(int x) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); //动态分配内存
newNode->data = x;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}
//Inserts a Node at head of doubly linked list 在链表头插入结点
void InsertAtHead(int x) {
struct Node* newNode = GetNewNode(x);
if(head == NULL) {
head = newNode;
return;
}
head->prev = newNode;
newNode->next = head; //曾经的第1个结点变为第2个结点
head = newNode;
}
//Inserts a Node at tail of Doubly linked list 在链表尾插入结点
void InsertAtTail(int x) {
struct Node* temp = head;
struct Node* newNode = GetNewNode(x);
if(head == NULL) {
head = newNode;
return;
}
while(temp->next != NULL) temp = temp->next; // Go To last Node 寻找最后1个结点
temp->next = newNode;
newNode->prev = temp;
}
//Prints all the elements in linked list in forward traversal order 从链表头开始打印所有元素
void Print() {
struct Node* temp = head;
printf("Forward: ");
while(temp != NULL) {
printf("%d ",temp->data);
temp = temp->next;
}
printf("\n");
}
//Prints all elements in linked list in reverse traversal order. 从链表尾开始打印所有元素
void ReversePrint() {
struct Node* temp = head;
if(temp == NULL) return; // empty list, exit 空链表，退出
// Going to last Node 找到最后一个结点
while(temp->next != NULL) {
temp = temp->next;
}
// Traversing backward using prev pointer 使用prev指针反向遍历
printf("Reverse: ");
while(temp != NULL) {
printf("%d ",temp->data);
temp = temp->prev;
}
printf("\n");
}
int main() {
/*Driver code to test the implementation*/
head = NULL; // empty list. set head as NULL.
// Calling an Insert and printing list both in forward as well as reverse direction.
InsertAtTail(2); Print(); ReversePrint();
InsertAtTail(4); Print(); ReversePrint();
InsertAtHead(6); Print(); ReversePrint();
InsertAtTail(8); Print(); ReversePrint();
InsertAtHead(1); Print(); ReversePrint();
}
运行效果
P15:使用数组实现栈 https://gist.github.com/mycodeschool/6878252 (C)
代码
// Stack - Array based implementation. 使用数组实现栈
// Creating a stack of integers. 整数栈
#include<stdio.h>
#define MAX_SIZE 101
int A[MAX_SIZE]; // integer array to store the stack 整型数组保存栈
int top = -1; // variable to mark top of stack in array 栈头
// Push operation to insert an element on top of stack. 入栈
void Push(int x)
{
if(top == MAX_SIZE -1) { // overflow case. 栈满
printf("Error: stack overflow\n");
return;
}
A[++top] = x; //成功入栈
}
// Pop operation to remove an element from top of stack. 出栈
void Pop()
{
if(top == -1) { // If stack is empty, pop should throw error. 栈空
printf("Error: No element to pop\n");
return;
}
top--; //成功出栈
}
// Top operation to return element at top of stack. 读栈顶元素
int Top()
{
return A[top];
}
// This function will return 1 (true) if stack is empty, 0 (false) otherwise 空栈返回1，否则0
int IsEmpty()
{
if(top == -1) return 1;
return 0;
}
// This function is just to test the implementation of stack. 测试栈的实现
// This will print all the elements in the stack at any stage. 打印栈中的所有元素
void Print() {
int i;
printf("Stack: ");
for(i = 0;i<=top;i++) printf("%d ",A[i]);
printf("\n");
}
int main() {
// Code to test the implementation.
// calling Print() after each push or pop to see the state of stack. 每次出栈入栈均打印栈中的所有元素
Push(2);Print();
Push(5);Print();
Push(10);Print();
Pop();Print();
Push(12);Print();
}运行效果
P18: 使用栈来检查表达式中的平衡括号https://gist.github.com/mycodeschool/7207410 (C++)
代码
/*
C程序，使用栈来检查表达式中的平衡括号。
给定一个由括号的打开和关闭字符组成的字符串表达式 - ()，大括号 - {} 和方括号 - []，我们需要检查符号是否平衡。
*/
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <stdlib.h>
// 检查括号是否匹配
bool ArePair(char opening, char closing) {
if (opening == '(' && closing == ')') return true;
else if (opening == '{' && closing == '}') return true;
else if (opening == '[' && closing == ']') return true;
return false;
}
//输入参数为待检测字符串
bool AreParanthesesBalanced(const char *exp) {
int stackSize = strlen(exp);
char *stack = (char *)malloc(stackSize * sizeof(char)); //动态分配栈空间
int top = -1;
for (int i = 0; i < stackSize; i++) //碰到括号才执行，其他符号直接跳过
{
if (exp[i] == '(' || exp[i] == '{' || exp[i] == '[')
{
stack[++top] = exp[i]; //入栈
}
else if (exp[i] == ')' || exp[i] == '}' || exp[i] == ']')
{
if ( top == -1 || !ArePair( stack[top--], exp[i] ) )
{
free(stack);
return false;
}
}
}
bool isBalanced = (top == -1); //此时栈空则证明括号匹配
free(stack);
return isBalanced;
}
int main() {
/* 测试函数 AreParanthesesBalanced */
char expression[100];
printf("Enter an expression: "); // 提醒用户输入表达式
fgets(expression, sizeof(expression), stdin);
// 从输入中删除换行符
expression[strcspn(expression, "")] = '\0';
if (AreParanthesesBalanced(expression))
printf("Balanced\n");
else
printf("Not Balanced\n");
return 0;
}
运行效果
P20: /输入由具体数字和加减乘除组合的后缀表达式【注意空格】，输出计算结果https://gist.github.com/mycodeschool/7702441 (C++)
代码
//输入由具体数字和加减乘除组合的后缀表达式【注意空格】，输出计算结果
//Enter Postfix Expression
//2 3 * 4 5 * + 9 -
//Output = 17
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>
#include<stdbool.h>
// 函数声明
int EvaluatePostfix(char *expression);
int PerformOperation(char operation, int operand1, int operand2);
bool IsOperator(char C);
bool IsNumericDigit(char C);
int main()
{
char expression[100];
printf("请输入后缀表达式：\n");
fgets(expression, sizeof(expression), stdin);
int result = EvaluatePostfix(expression);
printf("输出结果：%d\n", result);
return 0;
}
// 计算后缀表达式
int EvaluatePostfix(char *expression)
{
int S[100]; // 栈的大小为100
int top = -1; // 初始化栈顶指针
for (int i = 0; i < strlen(expression); i++)
{
// 如果字符是分隔符【空格或逗号】，跳过
if (expression[i] == ' ' || expression[i] == ',')
continue;
// 如果字符是操作符，弹出两个操作数，执行操作，并将结果压入栈中
else if (IsOperator(expression[i]))
{
int operand2 = S[top--];
int operand1 = S[top--];
int result = PerformOperation(expression[i], operand1, operand2);
S[++top] = result;
}
// 如果字符是数字，将其转换为整数并压入栈中
else if (IsNumericDigit(expression[i]))
{
int operand = 0;
while (i < strlen(expression) && IsNumericDigit(expression[i]))
{
operand = (operand * 10) + (expression[i] - '0');//十进制
i++;
}
i--;
S[++top] = operand;
}
}
return S[top];
}
//判断是否是数字
bool IsNumericDigit(char C)
{
if (C >= '0' && C <= '9')
return true;
return false;
}
//判断是否是加减乘除符号
bool IsOperator(char C)
{
if (C == '+' || C == '-' || C == '*' || C == '/')
return true;
return false;
}
int PerformOperation(char operation, int operand1, int operand2)
{
switch (operation)
{
case '+':
return operand1 + operand2;
case '-':
return operand1 - operand2;
case '*':
return operand1 * operand2;
case '/':
return operand1 / operand2;
default:
printf("意外错误\n");
return -1;
}
}
运行效果
P21:使用栈将中缀表达式转换为后缀表达式 https://gist.github.com/mycodeschool/7867739 (C++)
代码
//使用栈将中缀表达式转换为后缀表达式
//利用中缀表达式和后缀表达式的共同特性：操作数顺序相同
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 判断是否为操作符
int IsOperator(char C) {
if (C == '+' || C == '-' || C == '*' || C == '/' || C == '$')
return 1;
return 0;
}
// 判断是否为操作数--字母或数字
int IsOperand(char C) {
if (C >= '0' && C <= '9') return 1;
if (C >= 'a' && C <= 'z') return 1;
if (C >= 'A' && C <= 'Z') return 1;
return 0;
}
// 获取操作符的权重
int GetOperatorWeight(char op) {
int weight = -1;
switch (op)
{
case '+':
case '-':
weight = 1;break;
case '*':
case '/':
weight = 2;break;
case '$':
weight = 3;break;
}
return weight;
}
// 判断是否为右结合操作符
int IsRightAssociative(char op) {
if (op == '$') return 1;
return 0;
}
// 判断操作符 op1 是否具有比操作符 op2 更高的优先级
int HasHigherPrecedence(char op1, char op2) {
int op1Weight = GetOperatorWeight(op1);
int op2Weight = GetOperatorWeight(op2);
if (op1Weight == op2Weight) {
if (IsRightAssociative(op1)) return 0;
else return 1; //若操作符优先级相同，则栈中操作符op1因为早出现，所以优先级更高
}
return op1Weight > op2Weight ? 1 : 0;
}
// 将中缀表达式转换为后缀表达式
void InfixToPostfix(char *expression, char *postfix) {
int top = -1; // 栈顶指针
char stack[strlen(expression)]; // 栈
for (int i = 0; i < strlen(expression); i++)
{
if (expression[i] == ' ' || expression[i] == ',') continue; //忽略分隔符
if (IsOperator(expression[i])) // 判断是否为操作符
{
while (top != -1 && stack[top] != '(' && HasHigherPrecedence(stack[top], expression[i]))
{
*postfix++ = stack[top--]; //只有放入栈中的操作符优先级更高才可以放入后缀表达式
}
stack[++top] = expression[i];
}
else if (IsOperand(expression[i])) // 判断是否为操作数--字母或数字
{
*postfix++ = expression[i];
}
else if (expression[i] == '(') // 发现左括号则入栈
{
stack[++top] = expression[i];
}
else if (expression[i] == ')') // 碰到右括号则弹出栈中内容，直到遇到匹配的左括号
{
while (top != -1 && stack[top] != '(')
{
*postfix++ = stack[top--];
}
top--;
}
}
while (top != -1)
{
*postfix++ = stack[top--]; //弹出最后几个操作符
}
*postfix = '\0';
}
int main() {
char expression[100];
printf("请输入中缀表达式：\n");
scanf("%s", expression);
char postfix[100];
InfixToPostfix(expression, postfix);
printf("输出后缀表达式：%s\n", postfix);
return 0;
}
运行效果
P22: 用数组实现队列并进行入对出对操作https://gist.github.com/mycodeschool/7331785 (C++)
代码
//用数组实现队列并进行入对出对操作
#include <stdio.h>
#define MAX_SIZE 101 // 队列的最大大小
// 定义一个名为Queue的结构体
typedef struct {
int A[MAX_SIZE]; // 用于存储队列元素的数组
int front, rear; // 队首和队尾指针
} Queue;
// 初始化队列
void initQueue(Queue *q) {
q->front = -1;
q->rear = -1;
}
// 判断队列是否为空
int isEmpty(Queue *q) {
return (q->front == -1 && q->rear == -1);
}
// 判断队列是否已满--循环队列
int isFull(Queue *q) {
return (q->rear + 1) % MAX_SIZE == q->front;
}
// 入队操作--对尾入对
void enqueue(Queue *q, int x) {
printf("入队元素 %d\n", x);
if (isFull(q)) {
printf("错误：队列已满");
return;
}
if (isEmpty(q)) {
q->front = q->rear = 0;
}
else {
q->rear = (q->rear + 1) % MAX_SIZE;
}
q->A[q->rear] = x; // 入队
}
// 出队操作--对头出对
void dequeue(Queue *q) {
printf("出队操作");
if (isEmpty(q)) {
printf("错误：队列为空");
return;
} else if (q->front == q->rear) {
q->rear = q->front = -1; // 队列只有1个元素
} else {
q->front = (q->front + 1) % MAX_SIZE;
}
}
// 获取队首元素
int front(Queue *q) {
if (q->front == -1) {
printf("错误：无法从空队列中返回队首元素");
return -1;
}
return q->A[q->front];
}
// 打印队列中的元素（仅用于测试）
void print(Queue *q) {
int count = (q->rear + MAX_SIZE - q->front) % MAX_SIZE + 1;
printf("队列：");
for (int i = 0; i < count; i++) {
int index = (q->front + i) % MAX_SIZE; // 从队首开始循环遍历时的索引
printf("%d ", q->A[index]);
}
printf("\n\n");
}
int main() {
// 测试代码，打印每次入队或出队后的队列元素
Queue Q; // 创建一个队列实例
initQueue(&Q); // 初始化队列
enqueue(&Q, 2); print(&Q);
enqueue(&Q, 4); print(&Q);
enqueue(&Q, 6); print(&Q);
dequeue(&Q); print(&Q);
enqueue(&Q, 8); print(&Q);
}
运行效果
P23: https://gist.github.com/mycodeschool/7331785 (C++)
同P22
P24:用链表实现队列并进行入队出队操作 https://gist.github.com/mycodeschool/7510222 (C)
代码
//用链表实现队列并进行入队出队操作
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构体
struct Node {
int data; // 节点存储的数据
struct Node* next; // 指向下一个节点的指针
};
// 两个全局变量，用于存储队列的队首和队尾节点的地址
struct Node* front = NULL;
struct Node* rear = NULL;
// 入队操作，将1个整数插入队列尾部
void Enqueue(int x) {
struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
temp->data = x;
temp->next = NULL;
if (front == NULL && rear == NULL) { //空队列
front = rear = temp;
return;
}
rear->next = temp;
rear = temp;
}
// 出队操作，从队列头部移除1个整数
void Dequeue() {
struct Node* temp = front;
if (front == NULL) {
printf("队列为空");
return;
}
if (front == rear) {
front = rear = NULL; // 队列只有1个元素
} else {
front = front->next;
}
free(temp);
}
// 获取队首元素
int Front() {
if (front == NULL) {
printf("队列为空");
return 0;
}
return front->data;
}
// 打印队列中的元素
void Print() {
struct Node* temp = front;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
int main() {
// 测试代码，每次入队或出队后打印队列中的元素
Enqueue(2); Print();
Enqueue(4); Print();
Enqueue(6); Print();
Dequeue(); Print();
Enqueue(8); Print();
}
运行效果
P28:二叉搜索树的建立（插入） 与 查找 https://gist.github.com/mycodeschool/44e1a9183ab0e931f729 (C++)
代码
//二叉搜索树的建立（插入） 与 查找
#include <stdio.h>
#include <stdlib.h>
// 定义二叉搜索树节点结构体
struct BstNode {
int data;
struct BstNode* left;
struct BstNode* right;
};
// 在堆中创建一个新的节点
struct BstNode* GetNewNode(int data) {
struct BstNode* newNode = (struct BstNode*)malloc(sizeof(struct BstNode));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
// 向二叉搜索树中插入数据，返回根节点的地址
struct BstNode* Insert(struct BstNode* root, int data) {
if (root == NULL) { // 如果树为空
root = GetNewNode(data);
}
// 如果待插入的数据小于等于根节点的数据，则插入左子树
else if (data <= root->data) {
root->left = Insert(root->left, data);
}
// 否则，插入右子树
else {
root->right = Insert(root->right, data);
}
return root;
}
// 在二叉搜索树中搜索元素，如果找到元素则返回true
int Search(struct BstNode* root, int data) {
if (root == NULL) {
return 0; //找到
}
else if (root->data == data) {
return 1; //未找到
}
else if (data <= root->data) {
return Search(root->left, data);
}
else {
return Search(root->right, data);
}
}
int main() {
struct BstNode* root = NULL; // 创建一个空的二叉搜索树
/* 测试逻辑的代码 */
root = Insert(root, 15);
root = Insert(root, 10);
root = Insert(root, 20);
root = Insert(root, 25);
root = Insert(root, 8);
root = Insert(root, 12);
// 询问用户输入一个数字
int number;
printf("请输入要搜索的数字：");
scanf("%d", &number);
// 如果找到了数字，打印 "FOUND"
if (Search(root, number)) {
printf("Found\n");
}
else {
printf("Not Found\n");
}
}
运行效果
P33: 使用队列按层次遍历打印二叉树结点https://gist.github.com/mycodeschool/9507131 (C++)
核心思想：从队头取出一个节点访问，将节点的子节点加入队尾
代码
//使用队列按层次遍历打印二叉树结点
//核心思想：从队头取出一个节点访问，将节点的子节点加入队尾
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树结点结构体
struct Node {
char data;
struct Node *left;
struct Node *right;
};
// 函数：按层次遍历打印二叉树结点
void LevelOrder(struct Node *root) {
if (root == NULL) return;
// 使用队列存储待遍历的结点
struct Node *queue[100]; //指针数组
int front = -1, rear = -1;
// 将根结点入队
queue[++rear] = root;
// 当队列不为空时，继续遍历
while (front != rear) {
struct Node *current = queue[++front]; // 出队并打印
printf("%c ", current->data);
// 左子结点入队
if (current->left != NULL) {
queue[++rear] = current->left;
}
// 右子结点入队
if (current->right != NULL) {
queue[++rear] = current->right;
}
}
}
// 函数：在二叉搜索树中插入结点
struct Node* Insert(struct Node *root, char data) {
if (root == NULL) {
root = (struct Node *)malloc(sizeof(struct Node));
root->data = data;
root->left = root->right = NULL;
} else if (data <= root->data) {
root->left = Insert(root->left, data);
} else {
root->right = Insert(root->right, data);
}
return root;
}
int main() {
/* 创建示例二叉树
M
B Q
A C Z
*/
struct Node *root = NULL;
root = Insert(root, 'M'); root = Insert(root, 'B');
root = Insert(root, 'Q'); root = Insert(root, 'Z');
root = Insert(root, 'A'); root = Insert(root, 'C');
// 按层次遍历打印结点
LevelOrder(root);
printf("\n");
return 0;
}
运行效果
P34:使用递归进行二叉树前序 后序 中序遍历https://gist.github.com/mycodeschool/10016271 (C++)
代码
//使用递归进行二叉树前序 后序 中序遍历
#include<stdio.h>
#include<stdlib.h>
// 定义二叉树结点结构体
struct Node {
char data;
struct Node *left;
struct Node *right;
};
// 前序遍历函数
void Preorder(struct Node *root) {
if (root == NULL) return; // 递归结束条件：如果树/子树为空，返回并退出
printf("%c ", root->data); // 打印数据
Preorder(root->left); // 访问左子树
Preorder(root->right); // 访问右子树
}
// 中序遍历函数
void Inorder(struct Node *root) {
if (root == NULL) return; // 递归结束条件：如果树/子树为空，返回并退出
Inorder(root->left); // 访问左子树
printf("%c ", root->data); // 打印数据
Inorder(root->right); // 访问右子树
}
// 后序遍历函数
void Postorder(struct Node *root) {
if (root == NULL) return; // 递归结束条件：如果树/子树为空，返回并退出
Postorder(root->left); // 访问左子树
Postorder(root->right); // 访问右子树
printf("%c ", root->data); // 打印数据
}
// 向二叉搜索树中插入节点的函数
struct Node* Insert(struct Node *root, char data) {
if (root == NULL) {
root = (struct Node *)malloc(sizeof(struct Node));
root->data = data;
root->left = root->right = NULL;
} else if (data <= root->data) {
root->left = Insert(root->left, data);
} else {
root->right = Insert(root->right, data);
}
return root;
}
int main() {
/* 创建示例二叉树
M
B Q
A C Z
*/
struct Node *root = NULL;
root = Insert(root, 'M'); root = Insert(root, 'B');
root = Insert(root, 'Q'); root = Insert(root, 'Z');
root = Insert(root, 'A'); root = Insert(root, 'C');
// 前序遍历打印结点
printf("Preorder: ");
Preorder(root);
printf("\n");
// 中序遍历打印结点
printf("Inorder: ");
Inorder(root);
printf("\n");
// 后序遍历打印结点
printf("Postorder: ");
Postorder(root);
printf("\n");
return 0;
}
运行效果
P36: 在二叉搜索树中删除指定值的节点https://gist.github.com/mycodeschool/9465a188248b624afdbf (C++)
代码
//在二叉搜索树中删除指定值的节点
#include<stdio.h>
#include<stdlib.h>
// 定义二叉树结点结构体
struct Node {
int data;
struct Node *left;
struct Node *right;
};
// 查找二叉搜索树中的最小值
struct Node* FindMin(struct Node* root) {
while (root->left != NULL) {
root = root->left;
}
return root;
}
// 在二叉搜索树中删除指定值的节点
struct Node* Delete(struct Node *root, int data) {
if (root == NULL) {
return root;
}
// 去左子树找
else if (data < root->data) {
root->left = Delete(root->left, data);
}
// 去右子树找
else if (data > root->data) {
root->right = Delete(root->right, data);
}
else {
// 当前结点为叶子结点，直接删除
if (root->left == NULL && root->right == NULL) {
free(root);
root = NULL;
}
// 当前结点为最小的结点，当前结点父结点指向当前结点子结点
else if (root->left == NULL) {
struct Node *temp = root;
root = root->right;
free(temp);
}
// 当前结点为最大的结点，当前结点父结点指向当前结点子结点
else if (root->right == NULL) {
struct Node *temp = root;
root = root->left;
free(temp);
}
// 当前结点有两个子节点，在右子树找到最小值作为根结点，然后删除右子树重复值
else {
struct Node *temp = FindMin(root->right);
root->data = temp->data;
root->right = Delete(root->right, temp->data);
}
}
return root;
}
// 中序遍历（相当于从小到大遍历）二叉树并打印节点值
void Inorder(struct Node *root) {
if (root == NULL) {
return;
}
Inorder(root->left);
printf("%d ", root->data);
Inorder(root->right);
}
// 向二叉搜索树中插入节点
struct Node* Insert(struct Node *root, int data) {
if (root == NULL) {
root = (struct Node*)malloc(sizeof(struct Node));
root->data = data;
root->left = root->right = NULL;
} else if (data <= root->data) {
root->left = Insert(root->left, data);
} else {
root->right = Insert(root->right, data);
}
return root;
}
int main() {
/* 创建一个示例二叉搜索树
5
3 10
1 4 11
*/
struct Node* root = NULL;
root = Insert(root, 5); root = Insert(root, 10);
root = Insert(root, 3); root = Insert(root, 4);
root = Insert(root, 1); root = Insert(root, 11);
// 删除值为5的节点，可以修改这个值来测试其他情况
root = Delete(root, 5);
// 中序遍历并打印节点值
printf("Inorder: ");
Inorder(root);
printf("\n");
return 0;
}运行效果
P37: 在二叉搜索树中找到中序后继节点https://gist.github.com/mycodeschool/6515e1ec66482faf9d79 (C++)
逻辑
代码
// 在二叉搜索树中找到中序后继节点
#include<stdio.h>
#include<stdlib.h>
// 定义二叉树结点结构体
struct Node {
int data;
struct Node *left;
struct Node *right;
};
// 在二叉搜索树中查找指定值的节点
struct Node* Find(struct Node* root, int data) {
if (root == NULL) return NULL;
else if (root->data == data) return root; // 找到节点
else if (root->data < data) return Find(root->right, data);
else return Find(root->left, data);
}
// 在二叉搜索树中找到最小值的节点
struct Node* FindMin(struct Node* root) {
if (root == NULL) return NULL;
while (root->left != NULL)
root = root->left;
return root;
}
// 在二叉搜索树中找到中序后继节点
struct Node* Getsuccessor(struct Node* root, int data) {
struct Node* current = Find(root, data); // 先找到data对应的节点
if (current == NULL) return NULL;
if (current->right != NULL) { // 情况1：节点有右子树，中序后继节点就是右子树最小值
return FindMin(current->right);
}
else { // 情况2：没有右子树 - O(h)，中序后继节点就是某个祖先
struct Node* successor = NULL;
struct Node* ancestor = root;
while (ancestor != current) {
if (current->data < ancestor->data) {
successor = ancestor; // 到目前为止，这是最深节点，当前节点在其左侧
ancestor = ancestor->left;
}
else
ancestor = ancestor->right;
}
return successor;
}
}
// 中序遍历二叉树
void Inorder(struct Node* root) {
if (root == NULL) return;
Inorder(root->left); // 访问左子树
printf("%d ", root->data); // 打印数据
Inorder(root->right); // 访问右子树
}
// 在二叉搜索树中插入节点
struct Node* Insert(struct Node* root, int data) {
if (root == NULL) {
root = (struct Node*)malloc(sizeof(struct Node));
root->data = data;
root->left = root->right = NULL;
}
else if (data <= root->data)
root->left = Insert(root->left, data);
else
root->right = Insert(root->right, data);
return root;
}
int main() {
/* 创建示例二叉树
5
3 10
1 4 11
*/
struct Node* root = NULL;
root = Insert(root, 5); root = Insert(root, 10);
root = Insert(root, 3); root = Insert(root, 4);
root = Insert(root, 1); root = Insert(root, 11);
// 中序遍历二叉树
printf("Inorder Traversal: ");
Inorder(root);
printf("\n");
// 查找某个节点的中序后继节点
struct Node* successor = Getsuccessor(root, 1);
if (successor == NULL) printf("No successor Found\n");
else
printf("Successor of 1 is %d\n", successor->data);
}
运行效果
图邻接表的构造与遍历
代码参考《计算机软件技术基础》徐士良 算法2.29和2.30
代码
// 图邻接表的构造与遍历
// 代码参考《计算机软件技术基础》徐士良 算法2.29和2.30
#include "stdio.h"
#include "stdlib.h"
struct node // 单链表中节点结构
{
int num; // 图中节点编号
int val; // 节点值
struct node *next;
};
struct gpnode // 顺序存储空间中节点结构
{
char data;
struct node *link;
};
// 图邻接表的构造--该函数返回顺序存储空间的首地址
struct gpnode *creatgp(name,n)
int n;
char name[];
{
struct gpnode *head;
struct node *p;
int k,num,val; //节点编号和节点值
head = (struct gpnode *)malloc(n*sizeof(struct gpnode)); //顺序存储空间
// 依次对图中的每一个节点建立单链表
for(k=0;k<n;k++)
{
(head+k)->data=name[k]; // A B C D E
(head+k)->link=NULL;
printf("input linked list of %c :\n",name[k]);
scanf("%d,%d",&num,&val); // 获取节点编号和节点值
while(num>0) // 编号为1 2 3 4 5
{
// 将新节点加入到链表头部
p = (struct node *)malloc(sizeof(struct node)); // 单链表节点
p->num = num;
p->val = val;
p->next = (head+k)->link; // 新节点指向原来的第1个节点
(head+k)->link = p; // 将新节点链接到单链表表头
scanf("%d,%d",&num,&val);
}
}
return head;
}
// 图邻接表的遍历
// 递归函数
void static dfs(head,k,mark)
struct gpnode *head;
int k,*mark;
{
struct node* p;
printf("%c",(head+k-1)->data); // 输出当前节点值
mark[k-1] = 1; // 记录当前节点的查访标志
p = (head+k-1)->link; // 当前节点的第一个后件节点
while(p!=NULL)
{
if(mark[(p->num)-1]==0) // 该节点未被查访
dfs(head,p->num,mark);
p = p->next;
}
return;
}
void dfsgp(head,n)
struct gpnode *head;
int n;
{
int k,*mark;
mark = malloc( n*sizeof(int) ); // 标志数组空间
for(k=0;k<n;k++)
{
mark[k] = 0; // 标志数组初始化
}
k = 1; // 从第1个节点开始遍历
dfs(head,k,mark);
printf("\n");
free(mark);
return;
}
void main()
{
struct gpnode *head=NULL;
int n=5;
char name[]={'A','B','C','D','E'};
head = creatgp(name,n);
dfsgp(head,n);
}
运行效果
DAMO开发者矩阵，由阿里巴巴达摩院和中国互联网协会联合发起，致力于探讨最前沿的技术趋势与应用成果，搭建高质量的交流与分享平台，推动技术创新与产业应用链接，围绕“人工智能与新型计算”构建开放共享的开发者生态。
更多推荐
24
0- 0
已为社区贡献1条内容
所有评论(0)