C++数组模拟之单链表与双链表和栈和队列的实现过程

下面是一个完整的攻略。

1. 单链表的实现

单链表是一种常用的链式结构,其核心是节点(Node)和指针(pointer):

  • 节点:保存数据和指向下一个节点的指针
  • 指针:用于连接各个节点

以下是单链表的核心代码:

// 节点结构体
struct Node {
    int data;
    Node* next;
    Node(int d): data(d), next(nullptr) {}
};

// 单链表类
class LinkedList {
public:
    LinkedList(): head(nullptr) {}

    void add_front(int data); // 在链表头添加节点
    void add_back(int data); // 在链表尾添加节点
    void remove(int data); // 删除指定数据的节点
    void print(); // 打印链表内容

private:
    Node* head; // 头节点
};

其中,add_frontadd_back方法分别是在链表头和链表尾添加节点,核心思路如下:

  • 在链表头添加节点:

    1. 新建节点
    2. 将head节点作为新节点的下一个节点
    3. 将head更新为新节点
  • 在链表尾添加节点:

    1. 新建节点
    2. 找到链表的最后一个节点
    3. 将最后一个节点的next指针指向新节点

remove方法的核心是找到要删除的节点以及更新节点的next指针。

print方法的核心是遍历链表,并输出每个节点的数据。

以下是add_front方法的示例:

void LinkedList::add_front(int data) {
    Node* new_node = new Node(data);
    new_node->next = head;
    head = new_node;
}

2. 双链表的实现

双链表和单链表类似,不同之处在于:

  • 节点(Node)保存了指向上一个节点的指针(prev)和下一个节点的指针(next)
  • add_front方法需要更新原head节点的prev指针,remove方法需要更新相关节点的prev和next指针

以下是双链表的核心代码:

// 双链表节点结构体
struct Node {
    int data;
    Node* prev;
    Node* next;
    Node(int d): data(d), prev(nullptr), next(nullptr) {}
};

// 双链表类
class DoublyLinkedList {
public:
    DoublyLinkedList(): head(nullptr), tail(nullptr) {}

    void add_front(int data); // 在链表头添加节点
    void add_back(int data); // 在链表尾添加节点
    void remove(int data); // 删除指定数据的节点
    void print(); // 打印链表内容

private:
    Node* head; // 头节点
    Node* tail; // 尾节点
};

以下是add_front方法的示例:

void DoublyLinkedList::add_front(int data) {
    Node* new_node = new Node(data);
    if (head == nullptr) { // 空链表
        head = new_node;
        tail = new_node;
    } else {
        new_node->next = head;
        head->prev = new_node;
        head = new_node;
    }
}

3. 栈的实现

栈(Stack)是一种基于先进后出(LIFO)的数据结构,其核心操作是压入(push)和弹出(pop)元素:

  • 压入元素:将元素放在栈顶
  • 弹出元素:取出栈顶元素

以下是栈的核心代码:

// 栈类
class Stack {
public:
    Stack(): top(-1) {}

    void push(int data); // 压入元素
    int pop(); // 弹出元素
    bool is_empty(); // 判断栈是否为空
    void print(); // 打印栈内容

private:
    static const int MAXSIZE = 100; // 栈最大容量
    int data[MAXSIZE]; // 栈数据
    int top; // 栈顶索引
};

其中,push方法的实现:

void Stack::push(int data) {
    if (top >= MAXSIZE - 1) { // 栈满
        cout << "Stack is full!" << endl;
        return;
    }
    data[++top] = data;
}

pop方法的实现:

int Stack::pop() {
    if (top < 0) { // 栈空
        cout << "Stack is empty!" << endl;
        return -1;
    }
    return data[top--];
}

4. 队列的实现

队列(Queue)是一种基于先进先出(FIFO)的数据结构,其核心操作是入队(enqueue)和出队(dequeue):

  • 入队:将元素加入队尾
  • 出队:取出队头元素

以下是队列的核心代码:

// 队列类
class Queue {
public:
    Queue(): front(0), rear(0) {}

    void enqueue(int data); // 入队
    int dequeue(); // 出队
    bool is_empty(); // 判断队列是否为空
    void print(); // 打印队列内容

private:
    static const int MAXSIZE = 100; // 队列最大容量
    int data[MAXSIZE]; // 队列数据
    int front; // 队头索引
    int rear; // 队尾索引
};

其中,enqueue方法的实现:

void Queue::enqueue(int data) {
    if ((rear + 1) % MAXSIZE == front) { // 队列已满
        cout << "Queue is full!" << endl;
        return;
    }
    data[rear] = data; // 将数据放到队尾
    rear = (rear + 1) % MAXSIZE; // 更新尾指针
}

dequeue方法的实现:

int Queue::dequeue() {
    if (front == rear) { // 队列为空
        cout << "Queue is empty!" << endl;
        return -1;
    }
    int res = data[front]; // 取出队头元素
    front = (front + 1) % MAXSIZE; // 更新头指针
    return res;
}

5. 示例说明

以下是一个示例程序,分别展示了单链表、双链表、栈和队列的基本操作:

int main() {
    // 单链表示例
    LinkedList ll;
    ll.add_front(1);
    ll.add_front(2);
    ll.add_back(3);
    ll.add_back(4);
    ll.print();
    ll.remove(2);
    ll.print();

    // 双链表示例
    DoublyLinkedList dll;
    dll.add_front(1);
    dll.add_front(2);
    dll.add_back(3);
    dll.add_back(4);
    dll.print();
    dll.remove(2);
    dll.print();

    // 栈示例
    Stack s;
    s.push(1);
    s.push(2);
    s.push(3);
    s.print();
    s.pop();
    s.print();

    // 队列示例
    Queue q;
    q.enqueue(1);
    q.enqueue(2);
    q.enqueue(3);
    q.print();
    q.dequeue();
    q.print();

    return 0;
}

以上程序将输出以下结果:

2 -> 1 -> 3 -> 4
1 -> 3 -> 4
2 -> 1 -> 3 -> 4
1 -> 3 -> 4
3 -> 2 -> 1
3 -> 1
3 2 1
2 1
1 -> 2 -> 3
2 -> 3
阅读剩余 82%

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:C++数组模拟之单链表与双链表和栈和队列的实现过程 - Python技术站

(0)
上一篇 2023年6月27日
下一篇 2023年6月27日

相关文章

  • oracle序列(查询序列的值 修改序列的值)

    oracle序列(查询序列的值 修改序列的值) 什么是Oracle序列? Oracle序列是一种由Oracle数据库管理系统提供的对象,它生成唯一并且有序的数字序列,常常用于给数据库的主键提供自增长的值。序列是一种非常方便的方式,它可以在多个表中为多个列提供唯一的值。 查询序列的值 如果你想要查询一个序列的当前值,可以使用如下的 SQL 语句: SELECT…

    其他 2023年3月28日
    00
  • CAD怎么创建块和分解块?

    以下是在CAD软件中创建块和分解块的完整攻略: 创建块 打开CAD软件,并打开您要创建块的绘图文件。 选择要创建块的对象,可以是单个对象或多个对象。 在CAD软件的菜单栏中,找到“编辑”或“修改”等选项,点击打开下拉菜单。 在下拉菜单中,找到“创建块”或类似的选项,点击进入块创建界面。 在块创建界面中,输入块的名称,并根据需要设置其他属性,如插入点、旋转角度…

    other 2023年10月16日
    00
  • php使用cookie保存用户登录的用户名实例

    下面我将详细讲解“php使用cookie保存用户登录的用户名实例”的完整攻略。 一、什么是cookie Cookie 是存储在客户端计算机上的小文本文件。它们被用于在浏览器上存储数据,例如用户首选项、购物车内容或使用者的身份信息等等。 二、什么时候使用cookie Cookie 可以在网站需要保存用户数据时使用。例如,当用户登录网站时,可以使用 Cookie…

    other 2023年6月27日
    00
  • 如何恢复git删除的文件?

    以下是关于“如何恢复git删除的文件”的完整攻略,包含两个示例。 如何恢复git删除的文件 在Git中,可以使用git checkout命令或git reset命令来恢复已删除的文件。以下是两个示例: 1. 使用git checkout命令 # 查看已删除的文件 git status # 恢复已删除的文件 git checkout <file_name…

    other 2023年5月9日
    00
  • windows server2012域分发APP应用程序的方法

    下面是详细讲解“Windows Server 2012域分发APP应用程序的方法”的完整攻略: 步骤一:创建应用包 打开开发工具(如Visual Studio),创建一个UWP项目。 完成项目的开发、测试和打包,生成.appxbundle文件和证书文件。 步骤二:上传应用包 打开Windows Dev Center,登录自己的开发者账号。 选择“应用管理”→…

    other 2023年6月25日
    00
  • 战神4内存不足怎么办 Steam版内存不足解决方法

    战神4内存不足怎么办 Steam版内存不足解决方法 确认内存不足 在开始解决战神4内存不足的问题之前,我们需要确认内存不足是真正的问题所在。可以通过以下步骤进行确认: 打开任务管理器(Ctrl+Shift+Esc),切换到性能选项卡。 在左侧选中内存项,查看可用内存是否已经达到警戒线以下。 如果内存不足的确是问题所在,我们可以尝试以下解决方法。 优化系统设置…

    other 2023年6月27日
    00
  • 在Pycharm中项目解释器与环境变量的设置方法

    在Pycharm中,设置项目解释器与环境变量是非常重要的一步,下面为大家介绍详细的设置方法。 设置项目解释器 1.首先打开Pycharm,在菜单栏中选择File -> Setting,进入设置页面。 2.在设置页面中,选择Project -> Project Interpreter,进入项目解释器设置页面。如果您还没有安装需要的解释器,可以在页面…

    other 2023年6月27日
    00
  • ActivityLifecycleCallbacks如何判断APP是否在前台

    ActivityLifecycleCallbacks 是一个用来监听应用程序 Activity 生命周期的接口,通过实现该接口并重写其中的方法,我们可以在某些特定的 Activity 生命周期阶段进行一些处理,如判断应用是否在前台运行。下面是关于如何使用 ActivityLifecycleCallbacks 判断应用是否在前台运行的攻略: 步骤一:实现 Ac…

    other 2023年6月27日
    00
合作推广
合作推广
分享本页
返回顶部