目录

深入理解常见数据结构及其时间复杂度 —— 基于C语言的实现与分析

目录

单链表（Singly Linked List）

简介

结构定义

基本操作及时间复杂度

代码示例

初始化链表

插入头部

插入尾部

删除头部

删除尾部

查找元素

遍历链表

完整示例

双链表（Doubly Linked List）

简介

结构定义

基本操作及时间复杂度

代码示例

初始化链表

插入头部

插入尾部

删除头部

删除尾部

查找元素

遍历链表

完整示例

循环链表（Circular Linked List）

简介

结构定义

基本操作及时间复杂度

代码示例

初始化链表

插入尾部

插入头部

删除头部

删除尾部

查找元素

遍历链表

完整示例

栈（Stack）

简介

结构定义

基本操作及时间复杂度

代码示例

初始化栈

入栈

出栈

获取栈顶元素

判断空栈

完整示例

队列（Queue）

简介

结构定义

基本操作及时间复杂度

代码示例

初始化队列

入队

出队

获取队头元素

判断空队

完整示例

总结：数据结构时间复杂度比较表

如何确定时间复杂度

实例分析

附录：完整C语言代码示例

单链表

双链表

循环链表

栈

队列

总结

关键点回顾

应用场景

选择合适的数据结构

附加说明

链表与数组的比较

栈与队列的比较

结语

深入理解常见数据结构及其时间复杂度 —— 基于C语言的实现与分析

在计算机科学中，数据结构是组织和存储数据的方式，旨在高效地执行各种操作，如插入、删除、查找和遍历。不同的数据结构适用于不同类型的问题，因此理解它们的特点和时间复杂度对于编写高效的程序至关重要。

本文将详细讲解几种常见的数据结构，尤其是与链表相关的结构，结合C语言的代码示例，深入分析它们的时间复杂度，帮助您全面掌握这些基础知识。

目录

  1. 单链表（Singly Linked List）
  2. 双链表（Doubly Linked List）
  3. 循环链表（Circular Linked List）
  4. 栈（Stack）
  5. 队列（Queue）
  6. 总结：数据结构时间复杂度比较表
  7. 如何确定时间复杂度
  8. 附录：完整C语言代码示例

单链表（Singly Linked List）

简介

单链表是一种基本的链式数据结构，其中每个节点包含一个数据域和一个指向下一个节点的指针。单链表的优点在于动态内存分配，适用于需要频繁插入和删除操作的场景。

结构定义



c


复制代码


typedef struct Node { int data; struct Node* next; } Node; 


基本操作及时间复杂度



 
  

   操作
   描述
   时间复杂度
   说明
  

 
 
  

   创建链表
   初始化一个空链表
   O(1)
   设置头指针为NULL
  

  

   插入头部
   在链表头部插入新节点
   O(1)
   只需修改头指针和新节点的next指针
  

  

   插入尾部
   在链表尾部插入新节点
   O(n)
   需要遍历整个链表找到尾节点
  

  

   插入任意位置
   在指定位置插入新节点
   O(n)
   需要遍历到指定位置
  

  

   删除头部
   删除链表的第一个节点
   O(1)
   只需修改头指针
  

  

   删除尾部
   删除链表的最后一个节点
   O(n)
   需要遍历链表找到尾节点的前驱节点
  

  

   删除任意节点
   删除指定位置的节点
   O(n)
   需要遍历到指定节点
  

  

   查找元素
   查找链表中是否存在某个元素
   O(n)
   需要遍历整个链表最坏情况下
  

  

   遍历链表
   访问链表中的每个节点
   O(n)
   线性时间
  

 



代码示例


以下是单链表的一些基本操作的C语言实现。


初始化链表




c


复制代码


#include <stdio.h> #include <stdlib.h> // 节点结构体 typedef struct Node { int data; struct Node* next; } Node; // 初始化链表（创建空链表） Node* initializeList() { return NULL; } 


插入头部




c


复制代码


// 在链表头部插入新节点 void insertAtHead(Node** head_ref, int new_data) { Node* new_node = (Node*)malloc(sizeof(Node)); new_node->data = new_data; new_node->next = *head_ref; *head_ref = new_node; } 


插入尾部




c


复制代码


// 在链表尾部插入新节点 void insertAtTail(Node** head_ref, int new_data) { Node* new_node = (Node*)malloc(sizeof(Node)); new_node->data = new_data; new_node->next = NULL; if (*head_ref == NULL) { *head_ref = new_node; return; } Node* last = *head_ref; while (last->next != NULL) { last = last->next; } last->next = new_node; } 


删除头部




c


复制代码


// 删除链表头部节点 void deleteHead(Node** head_ref) { if (*head_ref == NULL) return; Node* temp = *head_ref; *head_ref = temp->next; free(temp); } 


删除尾部




c


复制代码


// 删除链表尾部节点 void deleteTail(Node** head_ref) { if (*head_ref == NULL) return; if ((*head_ref)->next == NULL) { free(*head_ref); *head_ref = NULL; return; } Node* temp = *head_ref; while (temp->next->next != NULL) { temp = temp->next; } free(temp->next); temp->next = NULL; } 


查找元素




c


复制代码


// 查找链表中是否存在某个元素 int searchElement(Node* head, int key) { Node* current = head; while (current != NULL) { if (current->data == key) return 1; // 找到 current = current->next; } return 0; // 未找到 } 


遍历链表




c


复制代码


// 打印链表中的所有元素 void printList(Node* head) { Node* temp = head; while (temp != NULL) { printf("%d -> ", temp->data); temp = temp->next; } printf("NULL\n"); } 


完整示例




c


复制代码


int main() { Node* head = initializeList(); // 插入元素 insertAtHead(&head, 3); insertAtHead(&head, 2); insertAtTail(&head, 4); insertAtTail(&head, 5); printf("链表内容: "); printList(head); // 输出: 2 -> 3 -> 4 -> 5 -> NULL // 删除头部 deleteHead(&head); printf("删除头部后: "); printList(head); // 输出: 3 -> 4 -> 5 -> NULL // 删除尾部 deleteTail(&head); printf("删除尾部后: "); printList(head); // 输出: 3 -> 4 -> NULL // 查找元素 int key = 4; if (searchElement(head, key)) printf("元素 %d 存在于链表中。\n", key); else printf("元素 %d 不存在于链表中。\n", key); return 0; } 


输出：




rust


复制代码


链表内容: 2 -> 3 -> 4 -> 5 -> NULL 删除头部后: 3 -> 4 -> 5 -> NULL 删除尾部后: 3 -> 4 -> NULL 元素 4 存在于链表中。 




双链表（Doubly Linked List）


简介


双链表与单链表类似，但每个节点包含两个指针：一个指向下一个节点（next），另一个指向前一个节点（prev）。这使得双链表在双向遍历和某些操作上更加高效。


结构定义




c


复制代码


typedef struct DNode { int data; struct DNode* prev; struct DNode* next; } DNode; 


基本操作及时间复杂度



 
  

   操作
   描述
   时间复杂度
   说明
  

 
 
  

   创建链表
   初始化一个空双链表
   O(1)
   设置头和尾指针为NULL
  

  

   插入头部
   在双链表头部插入新节点
   O(1)
   只需修改头指针和新节点的next与prev指针
  

  

   插入尾部
   在双链表尾部插入新节点
   O(1)
   通过尾指针直接访问，无需遍历
  

  

   删除头部
   删除双链表的第一个节点
   O(1)
   只需修改头指针和新的头节点的prev指针
  

  

   删除尾部
   删除双链表的最后一个节点
   O(1)
   通过尾指针直接访问，无需遍历
  

  

   插入任意位置
   在指定位置插入新节点
   O(n)
   需要遍历到指定位置
  

  

   删除任意节点
   删除指定位置的节点
   O(n)
   需要遍历到指定节点
  

  

   查找元素
   查找双链表中是否存在某个元素
   O(n)
   需要遍历整个链表最坏情况下
  

  

   遍历链表
   访问链表中的每个节点
   O(n)
   双向遍历
  

 



代码示例


以下是双链表的一些基本操作的C语言实现。


初始化链表




c


复制代码


// 初始化双链表（创建空链表） DNode* initializeDList() { return NULL; } 


插入头部




c


复制代码


// 在双链表头部插入新节点 void insertDAtHead(DNode** head_ref, int new_data) { DNode* new_node = (DNode*)malloc(sizeof(DNode)); new_node->data = new_data; new_node->prev = NULL; new_node->next = *head_ref; if (*head_ref != NULL) (*head_ref)->prev = new_node; *head_ref = new_node; } 


插入尾部




c


复制代码


// 在双链表尾部插入新节点 void insertDAtTail(DNode** head_ref, int new_data) { DNode* new_node = (DNode*)malloc(sizeof(DNode)); new_node->data = new_data; new_node->next = NULL; if (*head_ref == NULL) { new_node->prev = NULL; *head_ref = new_node; return; } DNode* last = *head_ref; while (last->next != NULL) last = last->next; last->next = new_node; new_node->prev = last; } 


删除头部




c


复制代码


// 删除双链表头部节点 void deleteDHead(DNode** head_ref) { if (*head_ref == NULL) return; DNode* temp = *head_ref; *head_ref = temp->next; if (*head_ref != NULL) (*head_ref)->prev = NULL; free(temp); } 


删除尾部




c


复制代码


// 删除双链表尾部节点 void deleteDTail(DNode** head_ref) { if (*head_ref == NULL) return; DNode* temp = *head_ref; // 如果链表只有一个节点 if (temp->next == NULL) { free(temp); *head_ref = NULL; return; } // 遍历到尾节点 while (temp->next != NULL) temp = temp->next; // 更新前驱节点的next指针 temp->prev->next = NULL; free(temp); } 


查找元素




c


复制代码


// 查找双链表中是否存在某个元素 int searchDElement(DNode* head, int key) { DNode* current = head; while (current != NULL) { if (current->data == key) return 1; // 找到 current = current->next; } return 0; // 未找到 } 


遍历链表




c


复制代码


// 打印双链表中的所有元素 void printDList(DNode* head) { DNode* temp = head; while (temp != NULL) { printf("%d <-> ", temp->data); temp = temp->next; } printf("NULL\n"); } 


完整示例




c


复制代码


int main() { DNode* head = initializeDList(); // 插入元素 insertDAtHead(&head, 3); insertDAtHead(&head, 2); insertDAtTail(&head, 4); insertDAtTail(&head, 5); printf("双链表内容: "); printDList(head); // 输出: 2 <-> 3 <-> 4 <-> 5 <-> NULL // 删除头部 deleteDHead(&head); printf("删除头部后: "); printDList(head); // 输出: 3 <-> 4 <-> 5 <-> NULL // 删除尾部 deleteDTail(&head); printf("删除尾部后: "); printDList(head); // 输出: 3 <-> 4 <-> NULL // 查找元素 int key = 4; if (searchDElement(head, key)) printf("元素 %d 存在于双链表中。\n", key); else printf("元素 %d 不存在于双链表中。\n", key); return 0; } 


输出：




rust


复制代码


双链表内容: 2 <-> 3 <-> 4 <-> 5 <-> NULL 删除头部后: 3 <-> 4 <-> 5 <-> NULL 删除尾部后: 3 <-> 4 <-> NULL 元素 4 存在于双链表中。 




循环链表（Circular Linked List）


简介


循环链表是链表的一种变体，其尾节点的next指针指向头节点，形成一个环。这种结构适用于需要循环访问数据的场景，如实现循环队列。


结构定义




c


复制代码


typedef struct CNode { int data; struct CNode* next; } CNode; 


基本操作及时间复杂度



 
  

   操作
   描述
   时间复杂度
   说明
  

 
 
  

   创建链表
   初始化一个空循环链表
   O(1)
   设置头指针为NULL
  

  

   插入头部
   在循环链表头部插入新节点
   O(n)
   需要找到尾节点以更新其next指针
  

  

   插入尾部
   在循环链表尾部插入新节点
   O(n)
   需要遍历整个链表找到尾节点
  

  

   删除头部
   删除循环链表的第一个节点
   O(n)
   需要找到尾节点以更新其next指针
  

  

   删除尾部
   删除循环链表的最后一个节点
   O(n)
   需要遍历链表找到尾节点的前驱节点
  

  

   查找元素
   查找循环链表中是否存在某个元素
   O(n)
   需要遍历整个链表最坏情况下
  

  

   遍历链表
   访问链表中的每个节点
   O(n)
   线性时间，直到回到头节点
  

 



代码示例


以下是循环链表的一些基本操作的C语言实现。


初始化链表




c


复制代码


// 初始化循环链表（创建空链表） CNode* initializeCList() { return NULL; } 


插入尾部




c


复制代码


// 在循环链表尾部插入新节点 void insertCAtTail(CNode** head_ref, int new_data) { CNode* new_node = (CNode*)malloc(sizeof(CNode)); new_node->data = new_data; if (*head_ref == NULL) { new_node->next = new_node; // 自指向形成循环 *head_ref = new_node; return; } CNode* temp = *head_ref; while (temp->next != *head_ref) temp = temp->next; temp->next = new_node; new_node->next = *head_ref; } 


插入头部




c


复制代码


// 在循环链表头部插入新节点 void insertCAtHead(CNode** head_ref, int new_data) { CNode* new_node = (CNode*)malloc(sizeof(CNode)); new_node->data = new_data; if (*head_ref == NULL) { new_node->next = new_node; *head_ref = new_node; return; } CNode* temp = *head_ref; while (temp->next != *head_ref) temp = temp->next; temp->next = new_node; new_node->next = *head_ref; *head_ref = new_node; } 


删除头部




c


复制代码


// 删除循环链表头部节点 void deleteCHead(CNode** head_ref) { if (*head_ref == NULL) return; // 如果只有一个节点 if ((*head_ref)->next == *head_ref) { free(*head_ref); *head_ref = NULL; return; } CNode* last = *head_ref; while (last->next != *head_ref) last = last->next; CNode* temp = *head_ref; *head_ref = (*head_ref)->next; last->next = *head_ref; free(temp); } 


删除尾部




c


复制代码


// 删除循环链表尾部节点 void deleteCTail(CNode** head_ref) { if (*head_ref == NULL) return; // 如果只有一个节点 if ((*head_ref)->next == *head_ref) { free(*head_ref); *head_ref = NULL; return; } CNode* temp = *head_ref; CNode* prev = NULL; while (temp->next != *head_ref) { prev = temp; temp = temp->next; } prev->next = *head_ref; free(temp); } 


查找元素




c


复制代码


// 查找循环链表中是否存在某个元素 int searchCElement(CNode* head, int key) { if (head == NULL) return 0; CNode* current = head; do { if (current->data == key) return 1; // 找到 current = current->next; } while (current != head); return 0; // 未找到 } 


遍历链表




c


复制代码


// 打印循环链表中的所有元素 void printCList(CNode* head) { if (head == NULL) { printf("循环链表为空。\n"); return; } CNode* temp = head; do { printf("%d -> ", temp->data); temp = temp->next; } while (temp != head); printf("(回到头部)\n"); } 


完整示例




c


复制代码


int main() { CNode* head = initializeCList(); // 插入元素 insertCAtTail(&head, 3); insertCAtTail(&head, 4); insertCAtHead(&head, 2); insertCAtTail(&head, 5); printf("循环链表内容: "); printCList(head); // 输出: 2 -> 3 -> 4 -> 5 -> (回到头部) // 删除头部 deleteCHead(&head); printf("删除头部后: "); printCList(head); // 输出: 3 -> 4 -> 5 -> (回到头部) // 删除尾部 deleteCTail(&head); printf("删除尾部后: "); printCList(head); // 输出: 3 -> 4 -> (回到头部) // 查找元素 int key = 4; if (searchCElement(head, key)) printf("元素 %d 存在于循环链表中。\n", key); else printf("元素 %d 不存在于循环链表中。\n", key); return 0; } 


输出：




rust


复制代码


循环链表内容: 2 -> 3 -> 4 -> 5 -> (回到头部) 删除头部后: 3 -> 4 -> 5 -> (回到头部) 删除尾部后: 3 -> 4 -> (回到头部) 元素 4 存在于循环链表中。 




栈（Stack）


简介


栈是一种后进先出（LIFO）的数据结构，只允许在一端进行插入和删除操作。栈常用于函数调用管理、表达式求值、撤销操作等。


结构定义


栈可以通过数组或链表实现。本文采用链表实现，以便动态扩展。




c


复制代码


typedef struct StackNode { int data; struct StackNode* next; } StackNode; 


基本操作及时间复杂度



 
  

   操作
   描述
   时间复杂度
   说明
  

 
 
  

   初始化栈
   创建一个空栈
   O(1)
   设置栈顶指针为NULL
  

  

   入栈
   将元素压入栈顶
   O(1)
   在链表头部插入新节点
  

  

   出栈
   弹出栈顶元素
   O(1)
   删除链表头部节点
  

  

   获取栈顶
   查看栈顶元素
   O(1)
   访问链表头部节点
  

  

   判断空栈
   检查栈是否为空
   O(1)
   判断头指针是否为NULL
  

 



代码示例


初始化栈




c


复制代码


// 初始化栈 StackNode* initializeStack() { return NULL; } 


入栈




c


复制代码


// 将元素压入栈顶 void push(StackNode** top_ref, int new_data) { StackNode* new_node = (StackNode*)malloc(sizeof(StackNode)); new_node->data = new_data; new_node->next = *top_ref; *top_ref = new_node; } 


出栈




c


复制代码


// 弹出栈顶元素 int pop(StackNode** top_ref) { if (*top_ref == NULL) { printf("栈为空，无法弹出。\n"); return -1; // 或其他错误码 } StackNode* temp = *top_ref; int popped = temp->data; *top_ref = temp->next; free(temp); return popped; } 


获取栈顶元素




c


复制代码


// 获取栈顶元素 int peek(StackNode* top) { if (top == NULL) { printf("栈为空。\n"); return -1; // 或其他错误码 } return top->data; } 


判断空栈




c


复制代码


// 判断栈是否为空 int isEmpty(StackNode* top) { return (top == NULL); } 


完整示例




c


复制代码


int main() { StackNode* stack = initializeStack(); // 入栈 push(&stack, 10); push(&stack, 20); push(&stack, 30); // 获取栈顶元素 printf("栈顶元素: %d\n", peek(stack)); // 输出: 30 // 出栈 printf("弹出元素: %d\n", pop(&stack)); // 输出: 30 printf("弹出元素: %d\n", pop(&stack)); // 输出: 20 // 判断是否为空 if (isEmpty(stack)) printf("栈为空。\n"); else printf("栈不为空。\n"); // 输出: 栈不为空。 return 0; } 


输出：




makefile


复制代码


栈顶元素: 30 弹出元素: 30 弹出元素: 20 栈不为空。 




队列（Queue）


简介


队列是一种先进先出（FIFO）的数据结构，允许在一端（队尾）插入元素，在另一端（队头）删除元素。队列常用于任务调度、宽度优先搜索等场景。


结构定义


队列通常通过链表实现，维护头指针和尾指针以优化插入和删除操作。




c


复制代码


typedef struct QNode { int data; struct QNode* next; } QNode; typedef struct Queue { QNode* front; QNode* rear; } Queue; 


基本操作及时间复杂度



 
  

   操作
   描述
   时间复杂度
   说明
  

 
 
  

   初始化队列
   创建一个空队列
   O(1)
   设置前端和后端指针为NULL
  

  

   入队
   将元素插入队尾
   O(1)
   通过尾指针直接插入新节点
  

  

   出队
   删除队头元素
   O(1)
   删除头节点并更新前端指针
  

  

   获取队头
   查看队头元素
   O(1)
   访问前端节点
  

  

   判断空队
   检查队列是否为空
   O(1)
   判断前端指针是否为NULL
  

 



代码示例


初始化队列




c


复制代码


// 初始化队列 Queue* initializeQueue() { Queue* q = (Queue*)malloc(sizeof(Queue)); q->front = q->rear = NULL; return q; } 


入队




c


复制代码


// 将元素插入队尾 void enqueue(Queue* q, int new_data) { QNode* new_node = (QNode*)malloc(sizeof(QNode)); new_node->data = new_data; new_node->next = NULL; if (q->rear == NULL) { q->front = q->rear = new_node; return; } q->rear->next = new_node; q->rear = new_node; } 


出队




c


复制代码


// 删除队头元素 int dequeue(Queue* q) { if (q->front == NULL) { printf("队列为空，无法出队。\n"); return -1; // 或其他错误码 } QNode* temp = q->front; int dequeued = temp->data; q->front = q->front->next; if (q->front == NULL) q->rear = NULL; free(temp); return dequeued; } 


获取队头元素




c


复制代码


// 获取队头元素 int getFront(Queue* q) { if (q->front == NULL) { printf("队列为空。\n"); return -1; // 或其他错误码 } return q->front->data; } 


判断空队




c


复制代码


// 判断队列是否为空 int isQueueEmpty(Queue* q) { return (q->front == NULL); } 


完整示例




c


复制代码


int main() { Queue* q = initializeQueue(); // 入队 enqueue(q, 10); enqueue(q, 20); enqueue(q, 30); // 获取队头元素 printf("队头元素: %d\n", getFront(q)); // 输出: 10 // 出队 printf("出队元素: %d\n", dequeue(q)); // 输出: 10 printf("出队元素: %d\n", dequeue(q)); // 输出: 20 // 判断是否为空 if (isQueueEmpty(q)) printf("队列为空。\n"); else printf("队列不为空。\n"); // 输出: 队列不为空。 // 清空队列 dequeue(q); // 弹出30 if (isQueueEmpty(q)) printf("队列为空。\n"); // 输出: 队列为空。 return 0; } 


输出：




makefile


复制代码


队头元素: 10 出队元素: 10 出队元素: 20 队列不为空。 队列为空。 




总结：数据结构时间复杂度比较表


为了便于理解和比较，以下表格总结了本文介绍的几种数据结构及其常见操作的时间复杂度。



 
  

   数据结构
   操作
   时间复杂度
   说明
  

 
 
  

   单链表
   插入头部
   O(1)
   在链表头部插入新节点，无需遍历
  

  

   
   插入尾部
   O(n)
   需要遍历整个链表找到尾节点
  

  

   
   删除头部
   O(1)
   只需修改头指针
  

  

   
   删除尾部
   O(n)
   需要遍历链表找到尾节点的前驱节点
  

  

   
   查找元素
   O(n)
   需要遍历整个链表
  

  

   
   遍历链表
   O(n)
   线性时间
  

  

   双链表
   插入头部
   O(1)
   只需修改头指针和新节点的prev指针
  

  

   
   插入尾部
   O(1)
   通过尾指针直接访问，无需遍历
  

  

   
   删除头部
   O(1)
   只需修改头指针和新的头节点的prev指针
  

  

   
   删除尾部
   O(1)
   通过尾指针直接访问，无需遍历
  

  

   
   查找元素
   O(n)
   需要遍历整个链表
  

  

   
   遍历链表
   O(n)
   双向遍历
  

  

   循环链表
   插入头部
   O(n)
   需要找到尾节点以更新其next指针
  

  

   
   插入尾部
   O(n)
   需要遍历整个链表找到尾节点
  

  

   
   删除头部
   O(n)
   需要找到尾节点以更新其next指针
  

  

   
   删除尾部
   O(n)
   需要遍历链表找到尾节点的前驱节点
  

  

   
   查找元素
   O(n)
   需要遍历整个链表
  

  

   
   遍历链表
   O(n)
   线性时间，直到回到头节点
  

  

   栈
   入栈
   O(1)
   在链表头部插入新节点
  

  

   
   出栈
   O(1)
   删除链表头部节点
  

  

   
   获取栈顶
   O(1)
   访问链表头部节点
  

  

   
   判断空栈
   O(1)
   判断头指针是否为NULL
  

  

   队列
   入队
   O(1)
   通过尾指针直接插入新节点
  

  

   
   出队
   O(1)
   删除头节点并更新前端指针
  

  

   
   获取队头
   O(1)
   访问前端节点
  

  

   
   判断空队
   O(1)
   判断前端指针是否为NULL
  

 





如何确定时间复杂度


时间复杂度描述了算法执行所需时间与输入规模之间的关系。确定时间复杂度的方法包括：


    
 
  1. 
  
    分析操作步骤：
    
  
      
   
    • 分解算法为基本操作，评估每个操作的时间成本。
      • 
   
    • 识别关键步骤，如循环、递归等，它们通常决定了整体时间复杂度。
      • 
  
    2. 
 
  2. 
  
    识别循环和递归：
    
  
      
   
    • 单层循环： 循环次数与输入规模线性相关，时间复杂度为O(n)。
      • 
   
    • 嵌套循环： 时间复杂度为O(n²)等，具体取决于嵌套层数。
      • 
   
    • 递归： 分析递归关系式，常用主定理求解时间复杂度。
      • 
  
    3. 
 
  3. 
  
    利用已知的算法复杂度：
    
  
      
   
    • 利用已知的排序算法、搜索算法等的时间复杂度，作为参考。
      • 
  
    4. 
 
  4. 
  
    常数时间操作：
    
  
      
   
    • 指针操作、赋值等通常为O(1)时间，不随输入规模变化。
      • 
  
    5. 
 
  5. 
  
    结合数据结构特性：
    
  
      
   
    • 不同数据结构的操作复杂度取决于其内部实现和维护的信息（如链表是否维护尾指针）。
      • 
  
    6. 



实例分析


以单链表插入尾部为例：




c


复制代码


void insertAtTail(Node** head_ref, int new_data) { Node* new_node = (Node*)malloc(sizeof(Node)); new_node->data = new_data; new_node->next = NULL; if (*head_ref == NULL) { *head_ref = new_node; return; } Node* last = *head_ref; while (last->next != NULL) { last = last->next; } last->next = new_node; } 


时间复杂度分析：


    
 
  1. 创建新节点： O(1)
    2. 
 
  2. 检查链表是否为空： O(1)
    3. 
 
  3. 遍历链表到尾部： 最坏情况下需要遍历整个链表，O(n)
    4. 
 
  4. 插入新节点： O(1)
    5. 



总时间复杂度： O(n) + O(1) = O(n)




附录：完整C语言代码示例


为了便于参考，以下汇总了本文提到的各数据结构的完整C语言代码示例。请根据需要分模块使用。


单链表




c


复制代码


#include <stdio.h> #include <stdlib.h> // 单链表节点 typedef struct Node { int data; struct Node* next; } Node; // 初始化链表 Node* initializeList() { return NULL; } // 插入头部 void insertAtHead(Node** head_ref, int new_data) { Node* new_node = (Node*)malloc(sizeof(Node)); new_node->data = new_data; new_node->next = *head_ref; *head_ref = new_node; } // 插入尾部 void insertAtTail(Node** head_ref, int new_data) { Node* new_node = (Node*)malloc(sizeof(Node)); new_node->data = new_data; new_node->next = NULL; if (*head_ref == NULL) { *head_ref = new_node; return; } Node* last = *head_ref; while (last->next != NULL) last = last->next; last->next = new_node; } // 删除头部 void deleteHead(Node** head_ref) { if (*head_ref == NULL) return; Node* temp = *head_ref; *head_ref = temp->next; free(temp); } // 删除尾部 void deleteTail(Node** head_ref) { if (*head_ref == NULL) return; if ((*head_ref)->next == NULL) { free(*head_ref); *head_ref = NULL; return; } Node* temp = *head_ref; while (temp->next->next != NULL) temp = temp->next; free(temp->next); temp->next = NULL; } // 查找元素 int searchElement(Node* head, int key) { Node* current = head; while (current != NULL) { if (current->data == key) return 1; current = current->next; } return 0; } // 打印链表 void printList(Node* head) { Node* temp = head; while (temp != NULL) { printf("%d -> ", temp->data); temp = temp->next; } printf("NULL\n"); } // 测试单链表 int main() { Node* head = initializeList(); insertAtHead(&head, 3); insertAtHead(&head, 2); insertAtTail(&head, 4); insertAtTail(&head, 5); printf("链表内容: "); printList(head); // 输出: 2 -> 3 -> 4 -> 5 -> NULL deleteHead(&head); printf("删除头部后: "); printList(head); // 输出: 3 -> 4 -> 5 -> NULL deleteTail(&head); printf("删除尾部后: "); printList(head); // 输出: 3 -> 4 -> NULL int key = 4; if (searchElement(head, key)) printf("元素 %d 存在于链表中。\n", key); else printf("元素 %d 不存在于链表中。\n", key); return 0; } 


双链表




c


复制代码


#include <stdio.h> #include <stdlib.h> // 双链表节点 typedef struct DNode { int data; struct DNode* prev; struct DNode* next; } DNode; // 初始化双链表 DNode* initializeDList() { return NULL; } // 插入头部 void insertDAtHead(DNode** head_ref, int new_data) { DNode* new_node = (DNode*)malloc(sizeof(DNode)); new_node->data = new_data; new_node->prev = NULL; new_node->next = *head_ref; if (*head_ref != NULL) (*head_ref)->prev = new_node; *head_ref = new_node; } // 插入尾部 void insertDAtTail(DNode** head_ref, int new_data) { DNode* new_node = (DNode*)malloc(sizeof(DNode)); new_node->data = new_data; new_node->next = NULL; if (*head_ref == NULL) { new_node->prev = NULL; *head_ref = new_node; return; } DNode* last = *head_ref; while (last->next != NULL) last = last->next; last->next = new_node; new_node->prev = last; } // 删除头部 void deleteDHead(DNode** head_ref) { if (*head_ref == NULL) return; DNode* temp = *head_ref; *head_ref = temp->next; if (*head_ref != NULL) (*head_ref)->prev = NULL; free(temp); } // 删除尾部 void deleteDTail(DNode** head_ref) { if (*head_ref == NULL) return; DNode* temp = *head_ref; if (temp->next == NULL) { free(temp); *head_ref = NULL; return; } while (temp->next != NULL) temp = temp->next; temp->prev->next = NULL; free(temp); } // 查找元素 int searchDElement(DNode* head, int key) { DNode* current = head; while (current != NULL) { if (current->data == key) return 1; current = current->next; } return 0; } // 打印双链表 void printDList(DNode* head) { DNode* temp = head; while (temp != NULL) { printf("%d <-> ", temp->data); temp = temp->next; } printf("NULL\n"); } // 测试双链表 int main() { DNode* head = initializeDList(); insertDAtHead(&head, 3); insertDAtHead(&head, 2); insertDAtTail(&head, 4); insertDAtTail(&head, 5); printf("双链表内容: "); printDList(head); // 输出: 2 <-> 3 <-> 4 <-> 5 <-> NULL deleteDHead(&head); printf("删除头部后: "); printDList(head); // 输出: 3 <-> 4 <-> 5 <-> NULL deleteDTail(&head); printf("删除尾部后: "); printDList(head); // 输出: 3 <-> 4 <-> NULL int key = 4; if (searchDElement(head, key)) printf("元素 %d 存在于双链表中。\n", key); else printf("元素 %d 不存在于双链表中。\n", key); return 0; } 


循环链表




c


复制代码


#include <stdio.h> #include <stdlib.h> // 循环链表节点 typedef struct CNode { int data; struct CNode* next; } CNode; // 初始化循环链表 CNode* initializeCList() { return NULL; } // 插入尾部 void insertCAtTail(CNode** head_ref, int new_data) { CNode* new_node = (CNode*)malloc(sizeof(CNode)); new_node->data = new_data; if (*head_ref == NULL) { new_node->next = new_node; *head_ref = new_node; return; } CNode* temp = *head_ref; while (temp->next != *head_ref) temp = temp->next; temp->next = new_node; new_node->next = *head_ref; } // 插入头部 void insertCAtHead(CNode** head_ref, int new_data) { CNode* new_node = (CNode*)malloc(sizeof(CNode)); new_node->data = new_data; if (*head_ref == NULL) { new_node->next = new_node; *head_ref = new_node; return; } CNode* temp = *head_ref; while (temp->next != *head_ref) temp = temp->next; temp->next = new_node; new_node->next = *head_ref; *head_ref = new_node; } // 删除头部 void deleteCHead(CNode** head_ref) { if (*head_ref == NULL) return; if ((*head_ref)->next == *head_ref) { free(*head_ref); *head_ref = NULL; return; } CNode* last = *head_ref; while (last->next != *head_ref) last = last->next; CNode* temp = *head_ref; *head_ref = (*head_ref)->next; last->next = *head_ref; free(temp); } // 删除尾部 void deleteCTail(CNode** head_ref) { if (*head_ref == NULL) return; if ((*head_ref)->next == *head_ref) { free(*head_ref); *head_ref = NULL; return; } CNode* temp = *head_ref; CNode* prev = NULL; while (temp->next != *head_ref) { prev = temp; temp = temp->next; } prev->next = *head_ref; free(temp); } // 查找元素 int searchCElement(CNode* head, int key) { if (head == NULL) return 0; CNode* current = head; do { if (current->data == key) return 1; current = current->next; } while (current != head); return 0; } // 打印循环链表 void printCList(CNode* head) { if (head == NULL) { printf("循环链表为空。\n"); return; } CNode* temp = head; do { printf("%d -> ", temp->data); temp = temp->next; } while (temp != head); printf("(回到头部)\n"); } // 测试循环链表 int main() { CNode* head = initializeCList(); insertCAtTail(&head, 3); insertCAtTail(&head, 4); insertCAtHead(&head, 2); insertCAtTail(&head, 5); printf("循环链表内容: "); printCList(head); // 输出: 2 -> 3 -> 4 -> 5 -> (回到头部) deleteCHead(&head); printf("删除头部后: "); printCList(head); // 输出: 3 -> 4 -> 5 -> (回到头部) deleteCTail(&head); printf("删除尾部后: "); printCList(head); // 输出: 3 -> 4 -> (回到头部) int key = 4; if (searchCElement(head, key)) printf("元素 %d 存在于循环链表中。\n", key); else printf("元素 %d 不存在于循环链表中。\n", key); return 0; } 


栈




c


复制代码


#include <stdio.h> #include <stdlib.h> // 栈节点 typedef struct StackNode { int data; struct StackNode* next; } StackNode; // 初始化栈 StackNode* initializeStack() { return NULL; } // 入栈 void push(StackNode** top_ref, int new_data) { StackNode* new_node = (StackNode*)malloc(sizeof(StackNode)); new_node->data = new_data; new_node->next = *top_ref; *top_ref = new_node; } // 出栈 int pop(StackNode** top_ref) { if (*top_ref == NULL) { printf("栈为空，无法弹出。\n"); return -1; } StackNode* temp = *top_ref; int popped = temp->data; *top_ref = temp->next; free(temp); return popped; } // 获取栈顶元素 int peek(StackNode* top) { if (top == NULL) { printf("栈为空。\n"); return -1; } return top->data; } // 判断栈是否为空 int isEmpty(StackNode* top) { return (top == NULL); } // 打印栈 void printStack(StackNode* top) { StackNode* temp = top; printf("栈内容: "); while (temp != NULL) { printf("%d -> ", temp->data); temp = temp->next; } printf("NULL\n"); } // 测试栈 int main() { StackNode* stack = initializeStack(); push(&stack, 10); push(&stack, 20); push(&stack, 30); printStack(stack); // 输出: 30 -> 20 -> 10 -> NULL printf("栈顶元素: %d\n", peek(stack)); // 输出: 30 printf("弹出元素: %d\n", pop(&stack)); // 输出: 30 printf("弹出元素: %d\n", pop(&stack)); // 输出: 20 if (isEmpty(stack)) printf("栈为空。\n"); else printf("栈不为空。\n"); // 输出: 栈不为空。 return 0; } 


队列




c


复制代码


#include <stdio.h> #include <stdlib.h> // 队列节点 typedef struct QNode { int data; struct QNode* next; } QNode; // 队列结构 typedef struct Queue { QNode* front; QNode* rear; } Queue; // 初始化队列 Queue* initializeQueue() { Queue* q = (Queue*)malloc(sizeof(Queue)); q->front = q->rear = NULL; return q; } // 入队 void enqueue(Queue* q, int new_data) { QNode* new_node = (QNode*)malloc(sizeof(QNode)); new_node->data = new_data; new_node->next = NULL; if (q->rear == NULL) { q->front = q->rear = new_node; return; } q->rear->next = new_node; q->rear = new_node; } // 出队 int dequeue(Queue* q) { if (q->front == NULL) { printf("队列为空，无法出队。\n"); return -1; } QNode* temp = q->front; int dequeued = temp->data; q->front = q->front->next; if (q->front == NULL) q->rear = NULL; free(temp); return dequeued; } // 获取队头元素 int getFront(Queue* q) { if (q->front == NULL) { printf("队列为空。\n"); return -1; } return q->front->data; } // 判断队列是否为空 int isQueueEmpty(Queue* q) { return (q->front == NULL); } // 打印队列 void printQueue(Queue* q) { QNode* temp = q->front; printf("队列内容: "); while (temp != NULL) { printf("%d -> ", temp->data); temp = temp->next; } printf("NULL\n"); } // 测试队列 int main() { Queue* q = initializeQueue(); enqueue(q, 10); enqueue(q, 20); enqueue(q, 30); printQueue(q); // 输出: 10 -> 20 -> 30 -> NULL printf("队头元素: %d\n", getFront(q)); // 输出: 10 printf("出队元素: %d\n", dequeue(q)); // 输出: 10 printf("出队元素: %d\n", dequeue(q)); // 输出: 20 if (isQueueEmpty(q)) printf("队列为空。\n"); else printf("队列不为空。\n"); // 输出: 队列不为空。 // 清空队列 dequeue(q); // 弹出30 if (isQueueEmpty(q)) printf("队列为空。\n"); // 输出: 队列为空。 return 0; } 




总结


本文深入探讨了几种常见的数据结构，包括单链表、双链表、循环链表、栈和队列。通过详细的C语言代码示例，展示了每种数据结构的基本操作及其时间复杂度。理解这些数据结构及其性能特点对于编写高效的程序至关重要。


关键点回顾


    
 
  1. 
  
    链表系列：
    
  
      
   
    • 单链表： 插入头部和删除头部操作为O(1)，插入尾部和删除尾部为O(n)。
      • 
   
    • 双链表： 通过维护前驱指针，插入和删除尾部操作可优化为O(1)。
      • 
   
    • 循环链表： 尾部节点指向头部，适用于需要循环访问的场景，但某些操作仍需O(n)时间。
      • 
  
    2. 
 
  2. 
  
    栈（Stack）：
    
  
      
   
    • 主要操作入栈和出栈均为O(1)，适用于后进先出（LIFO）的需求。
      • 
  
    3. 
 
  3. 
  
    队列（Queue）：
    
  
      
   
    • 主要操作入队和出队均为O(1)，适用于先进先出（FIFO）的需求。
      • 
  
    4. 



应用场景


    
 
  • 链表： 适用于需要频繁插入和删除操作的场景，如动态内存分配、实现其他数据结构（如栈和队列）。
    • 
 
  • 栈： 常用于函数调用管理、表达式求值、深度优先搜索等。
    • 
 
  • 队列： 常用于任务调度、广度优先搜索、缓冲区管理等。
    • 



选择合适的数据结构


在选择数据结构时，需要根据具体问题的需求和操作频率来决定。例如：


    
 
  • 如果需要频繁在头部插入和删除元素，单链表和栈是合适的选择。
    • 
 
  • 如果需要双向遍历或频繁在尾部插入和删除元素，双链表是更好的选择。
    • 
 
  • 如果需要先进先出的操作，队列是理想的选择。
    • 





附加说明


链表与数组的比较



 
  

   特性
   链表
   数组
  

 
 
  

   插入与删除
   O(1)（已知位置）
   O(n)
  

  

   随机访问
   O(n)
   O(1)
  

  

   内存利用
   动态分配，内存利用率高
   静态分配，可能有内存浪费或不足
  

  

   空间需求
   需要额外的指针空间
   连续内存空间，较紧凑
  

  

   实现复杂度
   较高
   较低
  

 



链表适用于需要动态插入和删除操作的场景，而数组适用于需要快速随机访问的场景。


栈与队列的比较



 
  

   特性
   栈（Stack）
   队列（Queue）
  

 
 
  

   访问方式
   后进先出（LIFO）
   先进先出（FIFO）
  

  

   主要操作
   push, pop, peek
   enqueue, dequeue, front
  

  

   应用场景
   函数调用、表达式求值、撤销操作
   任务调度、宽度优先搜索、缓冲区管理
  

 





结语


理解和掌握常见数据结构及其时间复杂度是计算机科学和软件工程中的基础技能。通过本文的详细解析和C语言实现，您应该能够更好地理解这些数据结构的内部机制和性能特点，并在实际编程中灵活应用。不断练习和应用这些知识，将帮助您编写更高效、更可靠的代码。


如果您有任何疑问或需要进一步的解释，欢迎随时提问！


 
  

        # 数据结构
      
        # c语言
      
        # 开发语言
      
  
 
 Logo 
魔乐社区
 
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
 
 
  
更多推荐
  
cover
 
【计算机视觉】Pixel逐像素分类&Mask掩码分类理解摘要
 
 
avatar 魔乐社区
 
 
计算机视觉（opencv）实战三十二——CascadeClassifier 人脸微笑检测（摄像头）
 
本文从原理到实现，详细介绍了基于 OpenCV Haar 分类器的人脸与微笑检测：讲解了 Haar 特征和级联检测原理。对代码逐行拆解并解释参数含义。画出完整流程图，帮助理解执行过程。给出了常见问题和优化建议，甚至扩展到深度学习方法。这种方法简单、轻量、实时性好，非常适合入门和小型应用项目。但如果需要更高准确率和更强鲁棒性，建议使用深度学习检测器替代 Haar 分类器。
 
avatar 魔乐社区
 
cover
 
小杰机器学习（seven）——贝叶斯分类
 
 
avatar 魔乐社区