谷歌网站地图生成器,公司网站域名注册流程,最新域名查询ip,网页制作公司 贵阳前言
在实际项目中#xff0c;单向链表经常被用来解决排队问题#xff0c;因为链表允许动态地添加和移除元素#xff0c;非常适合模拟队列#xff08;FIFO#xff0c;先进先出#xff09;的行为。 这里的链表包含头节点#xff0c;头结点的数据用来记录链表长度#x…前言
在实际项目中单向链表经常被用来解决排队问题因为链表允许动态地添加和移除元素非常适合模拟队列FIFO先进先出的行为。 这里的链表包含头节点头结点的数据用来记录链表长度该链表支持任意任意位置插入插队、尾插按序排队依据数据删除找不到数据则返回错误依据位置删除超过链表节点数则返回失败。
参考数据结构——单向链表-CSDN博客
有纰漏请指出转载请说明。
学习交流请发邮件 1280253714qq.com
单向链表在排队应用中的解决方案 单向链表在实际项目中的应用非常广泛特别是在处理排队问题时其灵活性和高效性使其成为理想的数据结构之一。以下是一些单向链表在实际项目中应用于排队问题的例子 1. 订单处理系统 在电商或餐饮等行业中订单处理系统需要高效地管理大量的订单请求。使用单向链表可以将新到达的订单添加到链表的尾部表示订单队列的末尾。处理订单时可以从链表的头部开始依次处理每个订单直到队列为空。这种方式能够确保订单按照到达的顺序被处理同时支持快速的插入和删除操作。 2. 任务调度系统 在操作系统或分布式系统中任务调度系统负责管理和分配计算资源给各个任务。使用单向链表可以将待调度的任务按照优先级或到达时间排序形成一个任务队列。调度器可以从链表的头部开始依次选择任务进行调度。当任务完成后可以从链表中删除该任务节点。这种方式能够确保任务按照预定的顺序被调度同时支持动态的插入和删除操作。 3. 网络连接管理 在网络通信中服务器需要管理大量的客户端连接。使用单向链表可以将每个客户端连接作为一个节点添加到链表中形成一个连接队列。服务器可以遍历链表对每个连接进行处理如发送数据、接收数据或关闭连接等。当有新连接到达时可以将其添加到链表的尾部当连接关闭时可以从链表中删除该节点。这种方式能够高效地管理网络连接支持快速的插入和删除操作。 4. 事件驱动系统 在事件驱动的应用程序中如游戏或实时监控系统事件需要按照发生的时间顺序被处理。使用单向链表可以将事件按照发生时间排序形成一个事件队列。事件处理器可以遍历链表依次处理每个事件。当有新事件到达时可以将其插入到链表的合适位置以保持事件的顺序性。这种方式能够确保事件按照正确的时间顺序被处理同时支持动态的插入操作。 5. 打印机队列管理 在打印系统中打印机需要管理多个打印任务。使用单向链表可以将每个打印任务作为一个节点添加到链表中形成一个打印任务队列。打印机可以遍历链表依次处理每个打印任务。当有新的打印任务到达时可以将其添加到链表的尾部当任务完成后可以从链表中删除该节点。这种方式能够高效地管理打印任务确保任务按照到达的顺序被处理。 综上所述单向链表在实际项目中的应用非常广泛特别是在处理排队问题时。其灵活性和高效性使其成为管理动态数据集合的理想选择之一。 单向链表操作相关函数
typedef int data_t;typedef struct node {data_t data;struct node * next;
}listNode, * linkList;linkList list_create(void) //创建链表即头节点
{linkList list;list (linkList)malloc(sizeof(listNode));//给节点动态分配内存if (list NULL)//判断是否申请内存成功 {return list;} //如果成功了则进行赋初值list-data 0; //一般存放节点个数list-next NULL;//刚开始时没有节点插入链表所以该头节点即是尾节点return list; //返回头节点指针
}int list_tail_insert(linkList list, data_t data) //传入待插入的链表地址和待插入的数据
{linkList p NULL;//定义临时指针变量linkList q NULL;if (list NULL) //检验传入的链表是否有效{return -1;}//创建新节点并检查有效性存放待插入数据if ((p (linkList)malloc(sizeof(listNode))) NULL){return -1;}p-data data;p-next NULL;q list;while (q-next ! NULL) //遍历链表找尾部{q q-next;}q-next p;//插入链表尾部的next指针指向新节点list-data;//插入数据后数据个数加一 return 0;
}// 插入函数位置从0开始计数
int list_insert_at_position(linkList list, int position, data_t data) {linkList p NULL; // 新节点指针linkList q list; // 用于遍历的临时指针linkList prev NULL; // 用于记录当前节点的前一个节点int i 0; // 位置计数器// 检查位置是否有效非负且不大于当前链表长度if (position 0) {return -1; // 位置无效}// 创建新节点并检查内存分配是否成功if ((p (linkList)malloc(sizeof(listNode))) NULL) {return -1; // 内存分配失败}p-data data;p-next NULL;if (list-nextNULL position0) {list-data 1;list-next p;} else{q q-next; //跳过头节点// 遍历链表找到插入位置while (q ! NULL i position) {prev q;q q-next;i;}// 检查位置是否超出了链表长度if (i position) {// 如果i大于position说明position是在链表尾部或之后的位置应该插入到尾部prev-next p;} else {// 否则插入到指定位置if (prev ! NULL) {p-next q;prev-next p;} else {// 如果prev是NULL说明position是0应该插入到链表头部p-next list;list p;}}list-data;//插入数据后数据个数加一 }return 0; // 插入成功
}//寻找链表上某一位置的节点的地址返回该节点地址
linkList list_get_addr(linkList list, int pos) //传入链表指针和待寻找节点的位置
{linkList p NULL;int i -1;if (list NULL) {return NULL;}if (pos -1) {return list;//如果是-1则返回链表头节点因为用0表示第一个节点的位置}p list;while (i pos) //遍历寻找{p p-next;if (p NULL) //没有到达指定位置链表已经结尾了位置错误返回NULL{return NULL;}i; }return p;
}int list_deleteBaseOnPos(linkList list, int pos)
{linkList p NULL;linkList deleteNode NULL;if (list NULL) return -1;p list_get_addr(list, pos-1);//寻找待删除节点的上一个节点if (p NULL) {return -1;//没有找到则返回}if (p-next NULL) //如果要删除的节点不存在则返回{return -1;}deleteNode p-next;//找到要删除的节点//将待删除的next指针赋给上一个节点的next指针p-next deleteNode-next;//也可以用p-next p-next-next;//释放删除节点的内存free(deleteNode);deleteNode NULL;list-data--;//删除节点后数据个数减一 return 0;
}int list_deleteBaseOnData(linkList list, data_t data)
{int pos 0;linkList p NULL;linkList q NULL;linkList deleteNode NULL;if (list NULL) return -1;q list-next;while (q-data ! data) //遍历链表找相同数据{q q-next;pos;if (pos list-data){return -1;//没有找到则返回}}p list_get_addr(list, pos-1);//寻找待删除节点的上一个节点if (p NULL) {return -1;//没有找到则返回}if (p-next NULL) //如果要删除的节点不存在则返回{return -1;}deleteNode p-next;//找到要删除的节点//将待删除的next指针赋给上一个节点的next指针p-next deleteNode-next;//也可以用p-next p-next-next;//释放删除节点的内存free(deleteNode);deleteNode NULL;list-data--;//删除节点后数据个数减一 return 0;
}
实例
int main(void)
{ linkList list; list list_create();//外部调用函数进行创建if (list NULL)return -1;list_insert_at_position(list,0,7);list_tail_insert(list, 6);//在链表尾部进行插入list_tail_insert(list, 2);//在链表尾部进行插入list_tail_insert(list, 5);//在链表尾部进行插入list_tail_insert(list, 3);//在链表尾部进行插入list_tail_insert(list, 4);//在链表尾部进行插入list_insert_at_position(list,2,1);list_deleteBaseOnData(list, 2);list_deleteBaseOnPos(list, 3);while (1){}
}
仿真结果
变量定义 创建链表
list list_create(); 在第“0”个位置插入数据7
list_insert_at_position(list,0,7); 依次尾插数据6 2 5 3 4 list_tail_insert(list, 6);//在链表尾部进行插入 list_tail_insert(list, 2);//在链表尾部进行插入 list_tail_insert(list, 5);//在链表尾部进行插入 list_tail_insert(list, 3);//在链表尾部进行插入 list_tail_insert(list, 4);//在链表尾部进行插入 在第“2”个位置插入数据1
list_insert_at_position(list,2,1); 找到数据为2的节点并删除
list_deleteBaseOnData(list, 2);
