行业知识
印度小哥数据结构视频代码测试笔记
2026-11-02 21:34:31
来源：互联网转载
引子
���早看野火的开发板视频嵌入式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#includestruct 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#define MAX_SIZE 101int 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，否则0int 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= '0' && C = '0' && C = 'a' && C = 'A' && C op2Weight ? 1 : 0;}// 将中缀表达式转换为后缀表达式void InfixToPostfix(char *expression, char *postfix) { int top = -1; // 栈顶指针 char stack[strlen(expression)]; // 栈 for (int i = 0; i 运行效果
P22: 用数组实现队列并进行入对出对操作https://gist.github.com/mycodeschool/7331785 (C++)
代码
//用数组实现队列并进行入对出对操作#include #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 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 #include // 定义链表节点结构体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 #include // 定义二叉搜索树节点结构体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 data) { root->left = Insert(root->left, data); } // 否则，插入右子树 else { root->right = Insert(root->right, data); } return root;}// 在二叉搜索树中搜索元素，如果找到元素则返回trueint Search(struct BstNode* root, int data) { if (root == NULL) { return 0;//找到 } else if (root->data == data) { return 1;//未找到 } else if (data 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 #include // 定义二叉树结点结构体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 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#include// 定义二叉树结点结构体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 data) { root->left = Insert(root->left, data); } else { root->right = Insert(root->right, data); } return root;}int main() { /* 创建示例二叉树 M B QA 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#include// 定义二叉树结点结构体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 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 data) { root->left = Insert(root->left, data); } else { root->right = Insert(root->right, data); } return root;}int main() { /* 创建一个示例二叉搜索树 5 3 101 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#include// 定义二叉树结点结构体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 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 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 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;kdata=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
上一篇：xshell怎么连db服务器?
下一篇：hand怎么读英语语音?
