????? THU数据结构(上)(2023spring） 完成啦(?????)

**THU数据结构(上)课程总结**

**课程简介**

本课程是清华大学计算机系的必修课之一，主要内容包括线性表、栈、队列、树等基本数据结构的理论基础和实现。通过学习本课程，我们可以掌握这些数据结构的定义、运算、应用以及它们在实际问题中的使用。

**一、线性表**

###1.1 定义线性表是指零个或多个元素按一定顺序排列起来的集合体，通常用一个一维数组来表示。线性表的基本操作包括插入、删除和查找等。

###1.2 实现

c// 线性表的定义typedef struct {
 int data[100]; // 元素数组 int length; // 元素个数} LinearTable;

// 线性表的初始化函数void initLinearTable(LinearTable *lt) {
 lt->length =0;
}

// 线性表的插入函数void insertLinearTable(LinearTable *lt, int pos, int value) {
 if (pos < 1 || pos > lt->length +1) {
 printf("插入位置错误!
");
 return;
 }
 for (int i = lt->length; i >= pos -1; i--) {
 lt->data[i] = lt->data[i -1];
 }
 lt->data[pos -1] = value;
 lt->length++;
}

// 线性表的删除函数void deleteLinearTable(LinearTable *lt, int pos) {
 if (pos < 1 || pos > lt->length) {
 printf("删除位置错误!
");
 return;
 }
 for (int i = pos -1; i < lt->length; i++) {
 lt->data[i] = lt->data[i +1];
 }
 lt->length--;
}

// 线性表的查找函数int searchLinearTable(LinearTable *lt, int value) {
 for (int i =0; i < lt->length; i++) {
 if (lt->data[i] == value) {
 return i +1;
 }
 }
 return -1;
}

###1.3 应用线性表在实际问题中的应用非常广泛，例如：

* 链式存储结构：链式存储结构是指使用指针来连接各个元素的数据结构。链式存储结构可以有效地解决线性表中插入和删除操作的问题。
* 栈和队列：栈和队列都是基于线性表的数据结构，它们分别支持后进先出(LIFO)和先进先出(FILO)的访问顺序。

**二、栈**

###2.1 定义栈是指一个元素集合体，遵循后进先出的原则。栈的基本操作包括入栈和出栈等。

###2.2 实现

c// 栈的定义typedef struct {
 int data[100]; // 元素数组 int top; // 栈顶指针} Stack;

// 栈的初始化函数void initStack(Stack *s) {
 s->top = -1;
}

// 栈的入栈函数void push(Stack *s, int value) {
 if (s->top ==99) {
 printf("栈已满!
");
 return;
 }
 s->data[++s->top] = value;
}

// 栈的出栈函数int pop(Stack *s) {
 if (s->top == -1) {
 printf("栈为空!
");
 return -1;
 }
 return s->data[s->top--];
}

###2.3 应用栈在实际问题中的应用包括：

* 表达式求值：栈可以用于表达式的求值，例如计算 `a + b * c` 等。
* 回溯算法：栈可以用于回溯算法中，例如解决迷宫问题等。

**三、队列**

###3.1 定义队列是指一个元素集合体，遵循先进先出的原则。队列的基本操作包括入队和出队等。

###3.2 实现

c// 队列的定义typedef struct {
 int data[100]; // 元素数组 int front; // 队头指针 int rear; // 队尾指针} Queue;

// 队列的初始化函数void initQueue(Queue *q) {
 q->front =0;
 q->rear = -1;
}

// 队列的入队函数void enqueue(Queue *q, int value) {
 if (q->rear ==99) {
 printf("队列已满!
");
 return;
 }
 q->data[++q->rear] = value;
}

// 队列的出队函数int dequeue(Queue *q) {
 if (q->front > q->rear) {
 printf("队列为空!
");
 return -1;
 }
 return q->data[q->front++];
}

###3.3 应用队列在实际问题中的应用包括：

* 线程通信：队列可以用于线程之间的通信，例如生产者-消费者问题等。
* 缓冲区管理：队列可以用于缓冲区的管理，例如网络传输等。

**四、树**

###4.1 定义树是指一个元素集合体，遵循父子关系。树的基本操作包括插入和删除等。

###4.2 实现

c// 树的定义typedef struct Node {
 int data; // 元素值 struct Node *left; // 左孩子 struct Node *right; // 右孩子} TreeNode;

// 树的初始化函数void initTree(TreeNode **root) {
 *root = NULL;
}

// 树的插入函数void insertTreeNode(TreeNode **root, int value) {
 if (*root == NULL) {
 *root = (TreeNode *)malloc(sizeof(TreeNode));
 (*root)->data = value;
 (*root)->left = NULL;
 (*root)->right = NULL;
 } else {
 // 根据值大小决定插入左子树还是右子树 if ((*root)->data < value) {
 insertTreeNode(&(*root)->right, value);
 } else {
 insertTreeNode(&(*root)->left, value);
 }
 }
}

// 树的删除函数void deleteTreeNode(TreeNode **root, int value) {
 // 根据值大小决定删除左子树还是右子树 if ((*root)->data < value) {
 deleteTreeNode(&(*root)->right, value);
 } else if ((*root)->data > value) {
 deleteTreeNode(&(*root)->left, value);
 } else {
 // 找到要删除的节点 TreeNode *node = *root;
 // 如果只有一个孩子，直接将孩子赋值给当前节点 if (node->left == NULL && node->right == NULL) {
 free(node);
 *root = NULL;
 } else if (node->left != NULL && node->right == NULL) {
 TreeNode *temp = node->left;
 free(node);
 *root = temp;
 } else if (node->left == NULL && node->right != NULL) {
 TreeNode *temp = node->right;
 free(node);
 *root = temp;
 } else {
 // 如果有两个孩子，找到后继节点 TreeNode *predecessor = findPredecessor(&(*root)->left, value);
 // 将后继节点的值赋值给当前节点 (*root)->data = predecessor->data;
 // 删除后继节点 deleteTreeNode(&(*root)->left, value);
 }
 }
}

// 找到树中最小的元素int findMin(TreeNode *node) {
 while (node->left != NULL) {
 node = node->left;
 }
 return node->data;
}

###4.3 应用树在实际问题中的应用包括：

* 文件系统管理：树可以用于文件系统的管理，例如目录结构等。
* 数据库索引：树可以用于数据库索引的建立和维护。

**五、总结**

本文主要介绍了线性表、栈、队列和树这四种基本数据结构的定义、实现和应用。通过学习这些数据结构，我们可以更好地理解计算机科学中的基础概念，并且能够在实际问题中运用它们来解决问题。

**参考文献**

* 《算法导论》(第三版) - Cormen, Thomas H., et al.
* 《数据结构与算