用devc++

### 实现链表、栈和队列数据结构 以下是使用 Dev-C++ 编写 C/C++ 程序实现链表、栈和队列的具体方法，包括类型定义、主菜单设计、函数定义及其注释说明。 --- #### **1. 类型定义** 为了便于扩展和维护，可以分别定义 `Node` 结构体作为节点的基础单元，并在此基础上构建链表、栈和队列的数据结构。 ```cpp // 定义节点结构体 struct Node { int data; // 节点存储的数据 struct Node* next; // 指向下一个节点的指针 }; // 链表头结点初始化 typedef struct LinkedList { Node* head; } LinkedList; // 栈结构定义 typedef struct Stack { Node* top; // 栈顶指针 } Stack; // 队列结构定义 typedef struct Queue { Node* front; // 队首指针 Node* rear; // 队尾指针 } Queue; ``` 以上代码片段定义了三种基本数据结构所需的节点类型[^1]。 --- #### **2. 主菜单设计** 提供一个简单的命令行界面供用户选择不同的功能模块（如插入、删除、显示等）。 ```cpp void displayMenu() { printf("\n=== 数据结构操作 ===\n"); printf("1. 插入元素\n"); printf("2. 删除元素\n"); printf("3. 显示当前状态\n"); printf("4. 清空结构\n"); printf("5. 切换至其他数据结构 (链表/栈/队列)\n"); printf("0. 退出程序\n"); } ``` 此部分实现了交互式的菜单选项，方便测试不同场景下的行为表现[^2]。 --- #### **3. 函数定义与注释** ##### （1）链表的操作 - 创建新节点： ```cpp Node* createNode(int value) { Node* newNode = new Node(); // 动态分配内存空间给新的节点 if (!newNode) return NULL; // 如果失败则返回NULL newNode->data = value; // 初始化节点中的数值字段 newNode->next = nullptr; // 设置指向下一节点为空 return newNode; // 成功创建并返回该节点地址 } ``` - 添加到链表头部： ```cpp void insertAtHead(LinkedList *list, int value){ Node *temp=createNode(value); temp->next=list->head; // 将原链表挂接到新建节点之后 list->head=temp; // 更新链表头指针位置 } ``` ##### （2）栈的操作 - 压栈操作： ```cpp bool push(Stack* stack, int item) { Node* node = createNode(item); // 使用createNode生成新节点 if(node == nullptr){return false;} node->next=stack->top; // 新加入项成为最上面一层 stack->top=node; // 修改顶部指示器指向最新添加项目 return true; } ``` - 弹栈操作： ```cpp int pop(Stack* stack) { if(stack->top==nullptr)return INT_MIN;//如果堆叠已清空，则无法移除任何东西 //INT_MIN代表不可能的有效输出值之一 Node* temp=stack->top; //保存即将被销毁的那个节点的信息 int poppedValue=temp->data; //获取要弹出项目的具体数值 stack->top=stack->top->next; //让顶层往下移动一位 delete(temp); //释放旧顶端所占用的空间资源 return poppedValue; //最后把刚才取出来的那个数反馈回去即可 } ``` ##### （3）队列的操作 - 入队操作： ```cpp void enqueue(Queue* queue, int value) { Node* newNode = createNode(value); if(queue->rear != nullptr)//如果不是第一次插入的话... queue->rear->next=newNode; //...那么就连接到最后面去。 queue->rear=newNode; //无论如何都要更新尾巴的位置标记。 if(queue->front == nullptr)queue->front=queue->rear; //如果是首次填充的情况特殊处理一下前端起点。 } ``` - 出队操作： ```cpp int dequeue(Queue* queue) { if(queue->front == nullptr)return INT_MAX; //当队伍完全耗尽的时候尝试取出会报错！ Node* oldFront=queue->front; //记录下现在正准备丢弃掉的那一端。 int removedData=oldFront->data; //读取即将消失的数据内容。 queue->front=queue->front->next; //向前推进整个序列的一格距离。 if(queue->front == nullptr)queue->rear=nullptr; //若此时发现前面已经没有任何剩余成员存在了， //记得同步调整后端结束标志位的状态哦~ delete(oldFront); //清理不再使用的那片区域内的资料。 return removedData; //最终给出刚刚成功拿走的结果啦~ } ``` --- #### **4. 操作原理示意图** 由于文本环境限制，下面仅描述逻辑流程图的文字版示意： - **链表** - 头部 → 节点A → 节点B → ... → 尾巴(NULL) - **栈** - 底层 ← 中间层次 ← 最高层(top) - **队列** - Front(head) → Middle Elements → Rear(tail) --- #### **5. 总结分析** 通过上述实现可以看出，每种数据结构都有其特定的应用场合。例如，链表适合频繁增删但较少随机访问；而栈适用于解决递归问题或者需要遵循 LIFO 的情况；至于队列则是 FIFO 场景的最佳搭档[^3]。 此外，在实际开发过程中还需要注意边界条件判断以及异常处理机制的设计，比如防止越界访问或是非法输入等问题的发生。 --- ####