线性表栈队列的应用实现

真题回放： （1）用随机函数生成10个3位整数（100-999），把这些整数应用入队操作方式于队列之中 （2）把这一些整数存于单链表中，然后读取一个整数，以该值为基准把单链表分割为两部分，所有小于该值的节点排在大于或等于该值的节点前面

考点分析： 这一道题考察的是链式存储结构的队列的基本操作，比如入队，出队，以及队伍的遍历

代码思路：

建立数据存储结构模型 struct LinkQuene { int data;//数据域 LinkQuene* next;//指针域 }; 链式存储结构的入队操作 void EnQuene(LinkQuene* head, int array[],int n) { LinkQuene* rear = head; for (int i = 0; i < n; i++) { LinkQuene* pnew = new LinkQuene; pnew->data = array[i]; pnew->next = NULL; cout << "第" << i+1 << "个入队元素：" << pnew->data << endl; rear->next = pnew; rear = pnew; } } 链式存储结构的队列出队操作 void DeQuene(LinkQuene* head) { int i = 1; while (head->next) { LinkQuene* pnode = head->next; LinkQuene* pnode1 = pnode->next; cout << "第" << i << "出队的元素:" << head->next->data << endl; head->next = pnode1; i++; } } 遍历链式存储结构的队列 void OrderQuene(LinkQuene* head) { LinkQuene* pnode = head->next; int i = 1; while (pnode) { cout << "第" << i << "个元素是:" << pnode->data << " " ; pnode = pnode->next; i++; } cout << endl; }

题目的核心：

把这一些整数存于单链表中，然后读取一个整数，以该值为基准把单链 表分割为两部分，所有小于该值的节点排在大于或等于该值的节点前面

定位需要找的元素所对应的节点

LinkQuene* Point(LinkQuene* head, int find) {//pnode2是定位元素所在的节点，pnode1是定位元素的前驱节点 LinkQuene* pnode = head->next; while (pnode) { if (pnode->next->data == find) return pnode; pnode = pnode->next; } return NULL; }

根据题意将定位的元素设置为中心将链队切成两半

void Arrangement(LinkQuene* head,LinkQuene* des) { LinkQuene* ltag;//左子链的首元节点 LinkQuene* rtag;//右子链的首元节点 //将该条链以对应的节点为中心切成两条子链 LinkQuene* pnode = head->next; while (pnode) { if (pnode->next == des) break; pnode = pnode->next; } ltag = head->next; rtag = des->next; pnode->next = NULL; des->next = NULL; head->next = des; //先遍历左端子链 while (ltag) { if (ltag->data < des->data) { LinkQuene* ptemp = ltag; ltag = ltag->next; ptemp->next = head->next; head->next = ptemp; } else if (ltag->data >= des->data) { LinkQuene* ptemp = ltag; ltag = ltag->next; ptemp->next = des->next; des->next = ptemp; } } //遍历右子链 while (rtag) { if (rtag->data < des->data) { LinkQuene* ptemp = rtag; rtag = rtag->next; ptemp->next = head->next; head->next = ptemp; } else if (rtag->data >= des->data) { LinkQuene* ptemp = rtag; rtag = rtag->next; ptemp->next = des->next; des->next = ptemp; } } }