首页 > 其他分享 >顺序表、链表、栈和队列总结

顺序表、链表、栈和队列总结

时间：2024-06-08 10:31:43浏览次数：29  
标签：Queue 顺序 return 队列 list stk 链表 int

目录

顺序表

链表

栈

队列

总结

补充

顺序表

实现

链表

实现

栈

实现

队列

实现

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

顺序表

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

链表

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

栈

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

队列

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

总结

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

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

补充

队列的实现

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

栈的实现

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的 代价比较小。

顺序表

是一种线性表，在C语言中通常通过数组来实现。它具有以下特点：

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

在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;
}

标签：Queue,顺序,return,队列,list,stk,链表,int
From： https://blog.csdn.net/2401_83427936/article/details/139520615

相关文章

  • 链表-双向链表
    之前实现的是单向链表,即每个节点有一个元素值和一个指向下一个元素的指针,是单向的.head->a->b->c1.现在来做一个双向的,即对每个节点来说,有两个指针,一个链向下一个元素,另一个链向上一个元素.head-><-b-><-c.链表初始化基本的操作套路和单链表是差不多的......
  • day3链表
    题目：https://leetcode.cn/problems/remove-linked-list-elements/submissions/537974263/题目解析：https://programmercarl.com/0203.移除链表元素.html这道题用了dummyHead，会简单非常多，但是需要注意的是，如果不用dummyHead的话，去除head为啥使用while而不是if呢？个人理解是，可......
  • 代码随想录第3天 | 链表 203.移除链表元素，707.设计链表，206.反转链表
    题目：203.移除链表元素思路：主要是头节点的删除问题，一种是直接在原链表上后移头节点设置虚拟头结点，指向原链表的头结点，在设置一个cur指针指向当前节点，虚拟头节点初始化后就不移动了，使用cur进行移动不要忘记释放删除节点的内存，自行设置的虚拟头节点也要释放时间复杂度:O(n)空......
  • 代码随想录训练营第三天 | 203.移除链表元素 707.设计链表 206.反转链表
    python定义链表val：数据域，节点存储的元素。next：指针域，指向下一个节点的指针，最后一个节点指向None表示空指针。点击查看代码classListNode:def__init__(self,val,next=None):self.val=valself.next=next203.移除链表元素题目：给你一个链表的......
  • 二叉链表---二叉树的简单实现
    实验内容将二叉链表视为森林的孩子兄弟链表，计算森林中叶子个数。代码实现#define_CRT_SECURE_NO_WARNINGS1#include<stdio.h>#include<stdlib.h>#include<string.h>#defineElemTypeinttypedefstructBtree{ ElemTypeelem; structBtree*lchild,*rchild......
  • Vue父子组件生命周期执行顺序
    顺序执行顺序：父组件先创建，然后子组件创建；子组件先挂载，然后父组件挂载，即“父beforeCreate->父create->子beforeCreate->子created->子mounted->父mounted”。在单一组件中，钩子的执行顺序是beforeCreate->created->mounted->…->destroyed，但当父子组件嵌套时，父组件和......
  • 232. 用栈实现队列
    typeMyQueuestruct{in,out[]int}funcConstructor()MyQueue{returnMyQueue{}}func(this*MyQueue)Push(xint){this.in=append(this.in,x)}//栈1转到栈2func(this*MyQueue)convent(){forlen(this.in)>0{this.o......
  • 141. 环形链表
    /***Definitionforsingly-linkedlist.*typeListNodestruct{*Valint*Next*ListNode*}*/funchasCycle(head*ListNode)bool{listMap:=map[*ListNode]struct{}{}forhead!=nil{if_,ok:=listMap[head];ok{......
  • 21. 合并两个有序链表
    packagemainimport"fmt"typeListNodestruct{ Valint Next*ListNode}//创建链表funccreateList(nums[]int)*ListNode{ head:=&ListNode{} tail:=head fori:=0;i<len(nums);i++{ node:=&ListNode{Val:nums[i]} t......
  • 206. 反转链表
    packagemainimport"fmt"typeListNodestruct{ Valint Next*ListNode}funcreverseList(head*ListNode)*ListNode{ varpre*ListNode//前驱节点指针 cur:=head//当前节点指针 forcur!=nil{ next:=cur.Next//临时存储next指针 cur.N......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99