目次
顺序表
链表
栈
队列
总结
补充
顺序表
实现
链表
实现
栈
实现
队列
实现
顺序表、链表、栈和队列都是线性数据结构，但它们在管理和访问数据方面有不同的特点和用途。以下是它们之间的主要区别：
顺序表
- 存储方式：在连续的内存空间中存储元素。
- 访问方式：通过索引直接访问，时间复杂度为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语言中的
实现
- #include <stdio.h>
- #include <stdlib.h>
- typedef struct {
- int *data;
- int size;
- } SequenceList;
- SequenceList *init_sequence_list(int size) {
- SequenceList *list = (SequenceList *)malloc(sizeof(SequenceList));
- list->data = (int *)malloc(size * sizeof(int));
- list->size = size;
- return list;
- }
- void free_sequence_list(SequenceList *list) {
- free(list->data);
- free(list);
- }
- void sequence_list_insert(SequenceList *list, int index, int value) {
- if (index < 0 || index > list->size) {
- printf("Index out of bounds\n");
- return;
- }
- for (int i = list->size; i > index; i--) {
- list->data[i] = list->data[i - 1];
- }
- list->data[index] = value;
- list->size++;
- }
- int sequence_list_get(SequenceList *list, int index) {
- if (index < 0 || index >= list->size) {
- printf("Index out of bounds\n");
- return -1;
- }
- return list->data[index];
- }
链表是由一系列节点构成，每个节点包罗数据域和指向下一个节点的指针。
实现
- #include <stdio.h>
- #include <stdlib.h>
- typedef struct Node {
- int value;
- struct Node *next;
- } LinkList;
- LinkList *init_link_list() {
- LinkList *head = (LinkList *)malloc(sizeof(LinkList));
- head->next = NULL;
- return head;
- }
- void free_link_list(LinkList *head) {
- LinkList *temp;
- while (head != NULL) {
- temp = head;
- head = head->next;
- free(temp);
- }
- }
- void link_list_insert(LinkList *head, int value) {
- LinkList *new_node = (LinkList *)malloc(sizeof(LinkList));
- new_node->value = value;
- new_node->next = head->next;
- head->next = new_node;
- }
栈是一种后进先出（LIFO）的数据结构。
实现
- #include <stdio.h>
- #include <stdlib.h>
- typedef struct {
- int *data;
- int top;
- int size;
- } Stack;
- Stack *init_stack(int size) {
- Stack *stk = (Stack *)malloc(sizeof(Stack));
- stk->data = (int *)malloc(size * sizeof(int));
- stk->top = -1;
- stk->size = size;
- return stk;
- }
- void free_stack(Stack *stk) {
- free(stk->data);
- free(stk);
- }
- void stack_push(Stack *stk, int value) {
- if (stk->top >= stk->size - 1) {
- printf("Stack overflow\n");
- return;
- }
- stk->data[++stk->top] = value;
- }
- int stack_pop(Stack *stk) {
- if (stk->top < 0) {
- printf("Stack underflow\n");
- return -1;
- }
- return stk->data[stk->top--];
- }
队列是一种先进先出（FIFO）的数据结构。
实现
- #include <stdio.h>
- #include <stdlib.h>
- #define QUEUE_SIZE 100
- typedef struct {
- int data[QUEUE_SIZE];
- int front;
- int rear;
- int count;
- } Queue;
- Queue *init_queue() {
- Queue *q = (Queue *)malloc(sizeof(Queue));
- if (q) {
- q->front = q->rear = 0;
- q->count = 0;
- }
- return q;
- }
- void free_queue(Queue *q) {
- free(q);
- }
- int is_queue_empty(Queue *q) {
- return q->count == 0;
- }
- int is_queue_full(Queue *q) {
- return q->count == QUEUE_SIZE;
- }
- void enqueue(Queue *q, int value) {
- if (is_queue_full(q)) {
- printf("Queue is full. Cannot enqueue.\n");
- return;
- }
- q->data[q->rear] = value;
- q->rear = (q->rear + 1) % QUEUE_SIZE;
- q->count++;
- }
- int dequeue(Queue *q) {
- if (is_queue_empty(q)) {
- printf("Queue is empty. Cannot dequeue.\n");
- return -1;
- }
- int value = q->data[q->front];
- q->front = (q->front + 1) % QUEUE_SIZE;
- q->count--;
- return value;
- }
- int main() {
- Queue *q = init_queue();
-
- enqueue(q, 1);
- enqueue(q, 2);
- enqueue(q, 3);
-
- printf("Dequeue: %d\n", dequeue(q));
- printf("Dequeue: %d\n", dequeue(q));
-
- if (is_queue_empty(q)) {
- printf("Queue is empty.\n");
- } else {
- printf("Queue is not empty.\n");
- }
-
- free_queue(q);
- return 0;
- }
|
