ToB企服应用市场:ToB评测及商务社交产业平台

标题: 顺序表、链表、栈和队列总结 [打印本页]

---

作者: 拉不拉稀肚拉稀    时间: 2024-6-8 21:39
标题: 顺序表、链表、栈和队列总结
目次
顺序表
链表
栈
队列
总结
补充
顺序表
实现
链表
实现
栈
实现
队列
实现

---

    顺序表、链表、栈和队列都是线性数据结构，但它们在管理和访问数据方面有不同的特点和用途。以下是它们之间的主要区别：
顺序表

• 存储方式：在连续的内存空间中存储元素。
  
• 访问方式：通过索引直接访问，时间复杂度为O(1)。
  
• 插入/删除：在表尾插入或删除元素，时间复杂度为O(n)，因为可能必要移动元素。
  
• 动态性：通常必要预先分配固定巨细的存储空间，但如果必要，可以动态扩容。
  
• 内存占用：可能会有未使用的内存空间，因为通常会分配比当前所需更大的空间。
  

链表

• 存储方式：由一系列节点构成，每个节点包罗数据域和指向下一个节点的指针。
  
• 访问方式：必要重新节点开始遍历，时间复杂度为O(n)。
  
• 插入/删除：在恣意位置插入或删除元素，时间复杂度为O(1)，因为只需改变指针。
  
• 动态性：可以动态地分配节点，因此不必要预先分配固定巨细的存储空间。
  
• 内存占用：每个节点只存储数据和指向下一个节点的指针，因此可能更节流内存。
  

栈

• 特点：后进先出（LIFO）的数据结构。
  
• 存储方式：可以是顺序表或链表的情势。
  
• 访问方式：只能访问栈顶元素，时间复杂度为O(1)。
  
• 插入/删除：只能在栈顶插入或删除元素，时间复杂度为O(1)。
  
• 动态性：可以是固定巨细的，也可以是动态扩容的。
  
• 内存占用：与顺序表雷同，可能会有未使用的内存空间。
  

队列

• 特点：先进先出（FIFO）的数据结构。
  
• 存储方式：可以是顺序表或链表的情势。
  
• 访问方式：只能访问队头或队尾元素，时间复杂度为O(1)。
  
• 插入：在队尾插入元素，时间复杂度为O(1)。
  
• 删除：从队头删除元素，时间复杂度为O(1)。
  
• 动态性：可以是固定巨细的，也可以是动态扩容的。
  
• 内存占用：与顺序表雷同，可能会有未使用的内存空间。
  

总结

• 顺序表和链表的主要区别在于存储方式和内存利用率。顺序表得当随机访问，而链表得当动态插入和删除。
  
• 栈和队列都是线性数据结构，但它们的利用方式不同。栈是后进先出的，而队列是先进先出的。
  
• 栈和队列通常都可以用顺序表或链表来实现，根据必要选择。
  

选择哪种数据结构取决于具体应用场景和对数据利用的频繁程度。
补充

队列的实现

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数 组头上出数据，效率会比较低。
栈的实现

栈的实现一样平常可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的 代价比较小。
顺序表
是一种线性表，在C语言中通常通过数组来实现。它具有以下特点：

• 连续的内存空间：顺序表中的元素存储在一块连续的内存空间中。
  
• 随机访问：可以通过下标直接访问任何一个位置的元素，访问时间为常数时间O(1)。
  
• 固定容量：通常情况下，顺序表的容量是固定的，当必要存储的元素个数凌驾当前容量时，必要进行扩容利用。
  

在C语言中实现顺序表，必要定义以下几个根本利用：

• 初始化：创建一个空的顺序表。
  
• 插入：在顺序表的指定位置插入一个元素。
  
• 删除：删除顺序表中指定位置的元素。
  
• 查找：查找顺序表中某个元素的索引。
  
• 扩容：当顺序表满时，增长其容量。
  
• 打印：打印顺序表中的所有元素。
  

下面是一个简单的顺序表在C语言中的
实现

1. #include <stdio.h>
2. #include <stdlib.h>
4. typedef struct {
5.     int *data;
6.     int size;
7. } SequenceList;
9. SequenceList *init_sequence_list(int size) {
10.     SequenceList *list = (SequenceList *)malloc(sizeof(SequenceList));
11.     list->data = (int *)malloc(size * sizeof(int));
12.     list->size = size;
13.     return list;
14. }
16. void free_sequence_list(SequenceList *list) {
17.     free(list->data);
18.     free(list);
19. }
21. void sequence_list_insert(SequenceList *list, int index, int value) {
22.     if (index < 0 || index > list->size) {
23.         printf("Index out of bounds\n");
24.         return;
25.     }
26.     for (int i = list->size; i > index; i--) {
27.         list->data[i] = list->data[i - 1];
28.     }
29.     list->data[index] = value;
30.     list->size++;
31. }
33. int sequence_list_get(SequenceList *list, int index) {
34.     if (index < 0 || index >= list->size) {
35.         printf("Index out of bounds\n");
36.         return -1;
37.     }
38.     return list->data[index];
39. }

复制代码

链表

链表是由一系列节点构成，每个节点包罗数据域和指向下一个节点的指针。
实现

1. #include <stdio.h>
2. #include <stdlib.h>
4. typedef struct Node {
5.     int value;
6.     struct Node *next;
7. } LinkList;
9. LinkList *init_link_list() {
10.     LinkList *head = (LinkList *)malloc(sizeof(LinkList));
11.     head->next = NULL;
12.     return head;
13. }
15. void free_link_list(LinkList *head) {
16.     LinkList *temp;
17.     while (head != NULL) {
18.         temp = head;
19.         head = head->next;
20.         free(temp);
21.     }
22. }
24. void link_list_insert(LinkList *head, int value) {
25.     LinkList *new_node = (LinkList *)malloc(sizeof(LinkList));
26.     new_node->value = value;
27.     new_node->next = head->next;
28.     head->next = new_node;
29. }

复制代码

栈

栈是一种后进先出（LIFO）的数据结构。
实现

1. #include <stdio.h>
2. #include <stdlib.h>
4. typedef struct {
5.     int *data;
6.     int top;
7.     int size;
8. } Stack;
10. Stack *init_stack(int size) {
11.     Stack *stk = (Stack *)malloc(sizeof(Stack));
12.     stk->data = (int *)malloc(size * sizeof(int));
13.     stk->top = -1;
14.     stk->size = size;
15.     return stk;
16. }
18. void free_stack(Stack *stk) {
19.     free(stk->data);
20.     free(stk);
21. }
23. void stack_push(Stack *stk, int value) {
24.     if (stk->top >= stk->size - 1) {
25.         printf("Stack overflow\n");
26.         return;
27.     }
28.     stk->data[++stk->top] = value;
29. }
31. int stack_pop(Stack *stk) {
32.     if (stk->top < 0) {
33.         printf("Stack underflow\n");
34.         return -1;
35.     }
36.     return stk->data[stk->top--];
37. }

复制代码

队列

队列是一种先进先出（FIFO）的数据结构。
实现

1. #include <stdio.h>
2. #include <stdlib.h>
4. #define QUEUE_SIZE 100
6. typedef struct {
7.     int data[QUEUE_SIZE];
8.     int front;
9.     int rear;
10.     int count;
11. } Queue;
13. Queue *init_queue() {
14.     Queue *q = (Queue *)malloc(sizeof(Queue));
15.     if (q) {
16.         q->front = q->rear = 0;
17.         q->count = 0;
18.     }
19.     return q;
20. }
22. void free_queue(Queue *q) {
23.     free(q);
24. }
26. int is_queue_empty(Queue *q) {
27.     return q->count == 0;
28. }
30. int is_queue_full(Queue *q) {
31.     return q->count == QUEUE_SIZE;
32. }
34. void enqueue(Queue *q, int value) {
35.     if (is_queue_full(q)) {
36.         printf("Queue is full. Cannot enqueue.\n");
37.         return;
38.     }
39.     q->data[q->rear] = value;
40.     q->rear = (q->rear + 1) % QUEUE_SIZE;
41.     q->count++;
42. }
44. int dequeue(Queue *q) {
45.     if (is_queue_empty(q)) {
46.         printf("Queue is empty. Cannot dequeue.\n");
47.         return -1;
48.     }
49.     int value = q->data[q->front];
50.     q->front = (q->front + 1) % QUEUE_SIZE;
51.     q->count--;
52.     return value;
53. }
55. int main() {
56.     Queue *q = init_queue();
57.    
58.     enqueue(q, 1);
59.     enqueue(q, 2);
60.     enqueue(q, 3);
61.    
62.     printf("Dequeue: %d\n", dequeue(q));
63.     printf("Dequeue: %d\n", dequeue(q));
64.    
65.     if (is_queue_empty(q)) {
66.         printf("Queue is empty.\n");
67.     } else {
68.         printf("Queue is not empty.\n");
69.     }
70.    
71.     free_queue(q);
72.     return 0;
73. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4