首页 > 其他分享 >数据结构（一）

数据结构（一）

时间：2024-08-15 18:25:24浏览次数：7  
标签：Node NULL 队列 链表 newNode 数据结构 节点

目录

1.  链表（Linked List）

链表的基本类型

链表的基本操作

链表的C语言实现示例（单向链表）

链表的时间复杂度

链表的空间复杂度

2. 栈（Stack）

栈的基本操作

栈的实现

栈的应用场景

示例：中缀表达式转后缀表达式（逆波兰表达式）

3.队列

队列

应用场景

1.  链表（Linked List）

链表是一种常见的数据结构，用于存储元素集合。与数组不同，链表中的元素在内存中不是连续存储的，而是通过指针（或引用）连接。这种结构允许高效地插入和删除操作，但访问任意元素的时间复杂度较高。

链表的基本类型
  1. 单向链表（Singly Linked List）：
    • 每个节点包含数据部分和一个指向列表中下一个节点的指针。
  2. 双向链表（Doubly Linked List）：
    • 每个节点包含数据部分、一个指向列表中下一个节点的指针和一个指向前一个节点的指针。
  3. 循环链表（Circular Linked List）：
    • 可以是单向或双向的，其中最后一个节点指向第一个节点，形成一个环。
链表的基本操作
  • 插入（Insert）：在链表的指定位置插入一个新节点。
  • 删除（Delete）：从链表中删除指定位置的节点。
  • 查找（Search）：查找链表中是否存在某个特定值的节点，并返回其位置或节点本身。
  • 遍历（Traverse）：从头节点开始，访问链表中的每个节点，直到到达尾节点。
链表的C语言实现示例（单向链表）


c复制代码


#include <stdio.h> 
#include <stdlib.h> 
// 定义链表节点结构体 
typedef struct Node { 
int data; 
struct Node* next; 
} Node; 
// 创建新节点 
Node* createNode(int data) { 
Node* newNode = (Node*)malloc(sizeof(Node)); 
if (!newNode) { 
printf("Memory allocation failed\n"); 
exit(1); 
} 
newNode->data = data; 
newNode->next = NULL; 
return newNode; 
} 
// 在链表末尾添加节点 
void appendNode(Node** head, int data) { 
Node* newNode = createNode(data); 
if (*head == NULL) { 
*head = newNode; 
} else { 
Node* temp = *head; 
while (temp->next != NULL) { 
temp = temp->next; 
} 
temp->next = newNode; 
} 
} 
// 打印链表 
void printList(Node* head) { 
Node* temp = head; 
while (temp != NULL) { 
printf("%d -> ", temp->data); 
temp = temp->next; 
} 
printf("NULL\n"); 
} 
// 主函数示例 
int main() { 
Node* head = NULL; 
appendNode(&head, 1); 
appendNode(&head, 2); 
appendNode(&head, 3); 
printList(head); 
return 0; 
}


链表的时间复杂度


  • 插入和删除： 
  
    • 在链表头部进行插入和删除操作的时间复杂度为O(1)。
    • 在链表中间或尾部进行这些操作的时间复杂度为O(n)，因为需要遍历链表以找到正确的位置。
  • 查找：遍历链表以查找特定值的节点的时间复杂度为O(n)。


链表的空间复杂度


链表的空间复杂度主要取决于链表中的节点数。对于包含n个节点的链表，其空间复杂度为O(n)。这是因为每个节点都需要在内存中分配空间。




2. 栈（Stack）


栈是一种遵循后进先出（LIFO，Last In First Out）原则的数据结构。它只允许在栈顶进行添加（push）或删除（pop）元素的操作。栈是一种非常基础且常用的数据结构，在多种编程场景和算法中都有广泛的应用。


栈的基本操作


  1. push（压栈）：将一个元素添加到栈顶。
  2. pop（出栈）：移除栈顶的元素，并返回这个元素。
  3. peek（或top）：返回栈顶元素的值，但不移除它。
  4. isEmpty：检查栈是否为空。
  5. size：返回栈中元素的数量。


栈的实现


栈可以通过多种方式实现，最常见的有两种：


  1.  
    基于数组的栈：使用数组来存储栈中的元素，用一个变量来记录栈顶的位置。这种实现方式在大多数编程语言的标准库中都有提供，如Java的Stack类（尽管Java推荐使用Deque接口的实现类如ArrayDeque作为栈的实现），Python的list也可以很方便地用作栈。
     
  2.  
    基于链表的栈：使用链表来存储栈中的元素，链表的头部即为栈顶。这种实现方式在需要频繁进行栈操作时，比基于数组的栈更加高效，因为不需要移动元素来保持栈的顺序。
     


栈的应用场景


栈的应用非常广泛，包括但不限于：


  • 函数调用和返回：在编程语言的执行过程中，函数的调用和返回都是通过栈来实现的。每调用一个函数，就将其返回地址、参数等信息压入栈中；函数执行完毕后，再从栈中弹出这些信息以返回到之前的函数。
  • 浏览器的前进和后退功能：浏览器通过维护一个历史记录栈来实现页面的前进和后退功能。
  • 表达式求值：在计算器的表达式求值中，栈被用来将中缀表达式转换为后缀表达式（逆波兰表达式），并进行后缀表达式的求值。
  • 语法分析：在编译器的语法分析阶段，栈被用来检查括号的匹配性，以及处理其他需要后进先出逻辑的场景。
  • 递归的实现：虽然递归本身不是栈，但递归的调用过程实际上是通过系统调用栈来实现的。


示例：中缀表达式转后缀表达式（逆波兰表达式）


中缀表达式如12 + 3 * 2 - 9 / 3，转换为后缀表达式（逆波兰表达式）的过程大致如下：


  1. 初始化两个栈，一个用于存储操作数（这里简化为数字），一个用于存储运算符。
  2. 遍历中缀表达式的每个字符，如果是操作数，则直接压入操作数栈；如果是运算符，则根据运算符的优先级和栈顶的运算符来决定是压入运算符栈还是进行运算。
  3. 遍历完成后，将运算符栈中的运算符依次弹出并压入操作数栈（这一步可能需要一个额外的栈来辅助，或者确保运算符栈的弹出顺序正确）。
  4. 最后，操作数栈中的元素即为后缀表达式的元素，按顺序输出即可。


3.队列


队列（Queue）是一种先进先出（FIFO，First In First Out）的数据结构，它只允许在队列的一端（队尾）进行添加操作（入队），在另一端（队头）进行删除操作（出队）。下面我将给出一个基于链表实现的队列的基本定义和操作。


队列


基于链表的队列定义通常包含一个头指针（指向队列的第一个元素）和一个尾指针（指向队列的最后一个元素），以及队列的大小。链表节点通常包含数据和指向下一个节点的指针。




c复制代码


#include <stdio.h> 
#include <stdlib.h> 
// 定义链表节点 
typedef struct Node { 
int data; 
struct Node* next; 
} Node; 
// 定义队列 
typedef struct Queue { 
Node* front; // 队头指针 
Node* rear; // 队尾指针 
int size; // 队列大小 
} Queue; 
// 初始化队列 
void initQueue(Queue* q) { 
q->front = q->rear = NULL; 
q->size = 0; 
} 
// 入队操作 
void enqueue(Queue* q, int value) { 
Node* newNode = (Node*)malloc(sizeof(Node)); 
if (!newNode) { 
// 处理内存分配失败的情况 
return; 
} 
newNode->data = value; 
newNode->next = NULL; 
if (q->rear == NULL) { 
// 队列为空时，新节点即为队头和队尾 
q->front = q->rear = newNode; 
} else { 
// 将新节点添加到队尾，并更新队尾指针 
q->rear->next = newNode; 
q->rear = newNode; 
} 
q->size++; 
} 
// 出队操作 
int dequeue(Queue* q) { 
if (q->front == NULL) { 
// 队列为空时，无法出队 
return -1; // 或者其他错误码 
} 
Node* temp = q->front; 
int data = temp->data; 
q->front = q->front->next; 
if (q->front == NULL) { 
// 队列变为空时，更新队尾指针 
q->rear = NULL; 
} 
free(temp); 
q->size--; 
return data; 
} 
// 读取队头元素 
int peek(Queue* q) { 
if (q->front == NULL) { 
// 队列为空时，无法读取队头元素 
return -1; // 或者其他错误码 
} 
return q->front->data; 
} 
// 获取队列大小 
int getSize(Queue* q) { 
return q->size; 
} 
// 清空队列 
void clearQueue(Queue* q) { 
Node* current = q->front; 
Node* next; 
while (current != NULL) { 
next = current->next; 
free(current); 
current = next; 
} 
q->front = q->rear = NULL; 
q->size = 0; 
} 
// 注意：这里只是给出了基于链表实现的队列的基本框架和主要操作，实际应用中可能还需要添加其他功能，比如错误处理、动态内存管理的优化等。


应用场景


  • 网络请求存储在队列中：服务器接收到请求后，可以将其存储在队列中，然后按照接收的顺序逐一处理。
  • 事件处理（GUI系统中）：GUI系统会将用户操作（如点击、键盘输入等）封装成事件，并将这些事件存储在队列中，由事件分发器逐一处理。
  • 消息队列（MQ）：消息队列是一种跨进程的通信机制，用于在不同系统或应用之间传递消息。Kafka、RabbitMQ等都是流行的消息队列系统。
  • 线程池：线程池中的任务通常被存储在队列中，线程从队列中取出任务并执行。这样可以减少线程创建和销毁的开销，提高系统的并发性能。










标签：Node,NULL,队列,链表,newNode,数据结构,节点	

From： https://blog.csdn.net/m0_61832483/article/details/140946236
      

      




      

      

        
相关文章

        

          
    
 
  • 数据结构
    数据结构莫队intn,m;/*====================*/intS;structQuery{	intl,r,idx;	Query(int_l=0,int_r=0,int_idx=0)	{		l=_l,r=_r,idx=_idx;	}	friendbooloperator<(constQuery&a,constQuery&b)	{		return(a.l/S==b.l......
     
  • 【数据结构】TreeMap和TreeSet
    目录前言TreeMap实现的接口内部类常用方法TreeSet实现的接口常用方法前言Map和set是一种专门用来进行搜索的容器或者数据结构，其搜索的效率与其具体的实例化子类有关。一般把搜索的数据称为关键字（Key），和关键字对应的称为值（Value），将其称之为Key-value的键值对。......
     
  • 知识改变命运 数据结构【顺序表】
    1.线性表线性表（linearlist）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列…线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组......
     
  • 高阶数据结构（Java）：AVL树插入机制的探索
    目录1、概念1.1什么是AVL树2.1平衡因子3、AVL树节点的定义4、AVL树的插入机制4.1初步插入节点4.2更新平衡因子4.3 提升右树高度4.3.1右单旋4.3.2左右双旋4.4 提升左树高度4.4.1左单旋 4.4.2右左双旋5、AVL树的验证6、AVL树的删除1、概念1.1什......
     
  • 【数据结构】详细介绍线性表中的顺序表，带你复盘实现细节，附上顺序表编程练习题
    目录一.线性表二.顺序表 1.静态顺序表与动态顺序表2.动态顺序表的接口实现 2.1顺序表初始化 2.2判断是否需要扩容  2.3 顺序表指定位置插入2.4 顺序表头插2.5 顺序表尾插2.6 顺序表指定位置删除2.7 顺序表头删2.8 顺序表尾删2.9 顺序表查找2.1......
     
  • 数据结构之链表超详解（1）
     一人我饮酒醉醉把佳人成双对两眼是独相随只求他日能双归娇女我轻扶琴燕嬉我紫竹林痴情红颜心甘情愿千里把你寻说红颜我痴情笑曲动我琴声妙轻狂高傲懵懂无知只怪太年少弃江山我忘天下斩断情丝无牵挂千古留名传佳话我两年征战已白发一生征战何人陪谁是谁非谁相随戎马一......
     
  • 一次函数最优化数据结构
    哎呀没写完，明天再补吧李超线段树一个节点维护递归到这个点，包含整个区间，并且在mid处取值最大的线段。若有两条线段，其中x比y在mid处值更大，如果x在l和r处值都比y大，显然y没有用。否则y只可能在左区间或右区间比x优。李超线段树利用单侧递归保证时间复杂度。但是李超线段树不便于......
     
  • 嵌入式软件--数据结构与算法 DAY 12
    数据结构和算法是程序的核心，虽然在嵌入式应用中很少会用到，但了解认知这种思维过程是非常有必要的。一个好的程序员应该把数据结构和算法看的比代码更重要。1.数据结构是什么？定义1(宏观)：数据结构是为了高效访问数据而设计出的一种数据的组织和存储方式。定义2(微观)：数据结构......
     
  • 嵌入式软件--数据结构与算法 DAY 13
    在嵌入式中，对算法的要求不高，但顺序查找和冒泡排序是经典算法，必须掌握。1.算法定义算法是一个用于解决特定问题的有限指令序列（计算机可以执行的操作）。通俗的理解就是可以解决特定问题的方法。2.时间复杂度时间复杂度不是执行完一段程序的总时间，而是描述为一个算法中基本操作......
     
  • [OI] 可持久化数据结构
    学了一年OI才看懂这句话：\(\logn\)是以什么为底的？其实没什么区别因为我们自动忽略常数，因此\(\log_{a}n=\frac{\log_{x}n}{\log_{x}a}=\log_{x}n\)可持久化数组可持久化数组是基于可持久化线段树的一种数据结构.它可以支持如下操作：单点修改查询历史版本在历史版......
     
    •            
          

        

      

    

    

      
赞助商

      




      

      
阅读排行

      

        
      

    

  





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

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

    
Copyright © 2020-2023  IPS99  版权所有 IPS99