数据结构(一)

**数据结构（一）**

在计算机科学中，数据结构是指组织、存储和操作数据的方式。它是计算机程序设计中的一个基本概念，决定了程序的性能、效率和可维护性。数据结构的选择直接影响到程序的执行速度、内存占用量以及代码的复杂度。

**1. 数组**

数组是一种最简单也是最常见的线性表数据结构。它是由一组相同类型的元素组成的序列，每个元素都有一个唯一的索引或下标。

c// 定义一个整型数组，大小为5int arr[5] = {1,2,3,4,5};

// 访问和修改数组元素arr[0] =10; // 修改第一个元素printf("%d
", arr[0]); // 输出第一个元素的值

**2. 链表**

链表是一种非连续存储的线性表数据结构。每个结点包含一个元素和一个指向下一个结点的指针。

c// 定义一个链表结点结构体typedef struct Node {
 int data;
 struct Node* next;
} Node;

// 创建一个链表Node* head = NULL;
Node* tail = NULL;

// 添加结点到链表尾部void addNode(int data) {
 Node* newNode = (Node*)malloc(sizeof(Node));
 newNode->data = data;
 newNode->next = NULL;

 if (head == NULL) {
 head = newNode;
 tail = newNode;
 } else {
 tail->next = newNode;
 tail = newNode;
 }
}

// 输出链表元素void printList() {
 Node* temp = head;
 while (temp != NULL) {
 printf("%d ", temp->data);
 temp = temp->next;
 }
 printf("
");
}

**3. 栈**

栈是一种后进先出的线性表数据结构。它遵循 LIFO（Last In First Out）原则，意味着最后添加的元素将首先被移除。

c// 定义一个整型栈，大小为5int stack[5] = {1,2,3,4,5};

// 进栈和出栈操作void push(int data) {
 if (top < 5) {
 stack[++top] = data;
 }
}

void pop() {
 if (top > -1) {
 printf("%d
", stack[top--]);
 }
}

**4. 队列**

队列是一种先进先出的线性表数据结构。它遵循 FIFO（First In First Out）原则，意味着最先添加的元素将首先被移除。

c// 定义一个整型队列，大小为5int queue[5] = {1,2,3,4,5};

// 入队和出队操作void enqueue(int data) {
 if (rear < 4) {
 queue[++rear] = data;
 }
}

void dequeue() {
 if (front > -1) {
 printf("%d
", queue[front++]);
 }
}

**5. 树**

树是一种非线性的数据结构，用于表示层次关系。每个结点代表一个元素，其子结点代表该元素的下属。

c// 定义一个二叉树结点结构体typedef struct Node {
 int data;
 struct Node* left;
 struct Node* right;
} Node;

// 创建一个二叉树Node* root = NULL;

// 添加结点到二叉树中void addNode(int data) {
 Node* newNode = (Node*)malloc(sizeof(Node));
 newNode->data = data;
 newNode->left = newNode->right = NULL;

 if (root == NULL) {
 root = newNode;
 } else {
 // 根据数据大小决定添加到左子树还是右子树 if (data < root->data) {
 addNodeToLeft(root, newNode);
 } else {
 addNodeToRight(root, newNode);
 }
 }
}

// 添加结点到左子树中void addNodeToLeft(Node* node, Node* newNode) {
 if (node->left == NULL) {
 node->left = newNode;
 } else {
 // 递归添加到左子树的左子树或右子树中 addNodeToLeft(node->left, newNode);
 }
}

// 添加结点到右子树中void addNodeToRight(Node* node, Node* newNode) {
 if (node->right == NULL) {
 node->right = newNode;
 } else {
 // 递归添加到右子树的左子树或右子树中 addNodeToRight(node->right, newNode);
 }
}

**6. 图**

图是一种非线性的数据结构，用于表示任意两个结点之间的关系。每个结点代表一个元素，其邻接结点代表该元素与其他元素之间的连接。

c// 定义一个图结点结构体typedef struct Node {
 int data;
 struct Edge* edges;
} Node;

// 定义一个图边结构体typedef struct Edge {
 int to;
 struct Edge* next;
} Edge;

// 创建一个图Node* head = NULL;

// 添加结点到图中void addNode(int data) {
 Node* newNode = (Node*)malloc(sizeof(Node));
 newNode->data = data;
 newNode->edges = NULL;

 if (head == NULL) {
 head = newNode;
 } else {
 // 根据数据大小决定添加到左子树还是右子树 addNodeToGraph(head, newNode);
 }
}

// 添加结点到图中void addNodeToGraph(Node* node, Node* newNode) {
 if (node->edges == NULL) {
 node->edges = (Edge*)malloc(sizeof(Edge));
 node->edges->to = newNode->data;
 node->edges->next = NULL;

 // 添加边到图中 addEdgeToGraph(node, newNode);
 } else {
 // 递归添加到左子树的左子树或右子树中 addNodeToGraph(node->edges, newNode);
 }
}

// 添加边到图中void addEdgeToGraph(Node* node, Node* newNode) {
 Edge* newEdge = (Edge*)malloc(sizeof(Edge));
 newEdge->to = newNode->data;
 newEdge->next = NULL;

 // 将新边添加到结点的邻接链表中 if (node->edges == NULL) {
 node->edges = newEdge;
 } else {
 Edge* temp = node->edges;
 while (temp->next != NULL) {
 temp = temp->next;
 }
 temp->next = newEdge;
 }
}

以上是数据结构的基本概念和常见数据结构的实现。这些数据结构在计算机科学中广泛应用于各种领域，如数据库管理、图形处理、网络通信等。