思路
假设有多组数据，每一组都是按从小到大的顺序输入的，设计如下数据结构
前面一列是每一组数据的首部，后面是真正的数据，首部的定义为：
struct head { node* next; head* down; head* up; };
数据部分的定义为：
struct node { int data; node* next; };
1.我们称左上角为根，左下角为尾，根的前指针(up)和尾的后指针(down)为null，next指向数据，那么在输出的时候，只需要遍历第二列选出最小的数据即可，在输出该结点之后将该节点删除，并更新该数据结构。
2.定义两个指针p和q，分别用来遍历和指向最小数据。
a.如果q(指向最小数据的指针)指到了根，并且p->next->next=null,则表示根所在的一行已经输出完毕，需要更新根，于是判断根的下指针是否也为null，如果是，表示已经结束，如果不是则将下一行首部设置为根。
b.如果p->next->next不等于null，则只需要将p的next指向p的next的next即p->next = p->next->next。
c.如果q指向除根以外的首部，并且，后面有多的数据，则p->next = p->next->next，如果没有多余数据表示这一行已经全部输出，删除p和p->next指向的空间，并将p的上一行的首部的下指针指向p的下一行的首部，下一行的上指针指向p的上一行首部。
3.输出的时候只需要当前数据与前一个输出的数据不同即可。
代码：
1 namespace sort { 2 using namespace std; 3 struct node {//数据结点 4 int data; 5 node* next; 6 }; 7 struct head {//头结点 8 node* next; 9 head* down; 10 head* up; 11 }; 12 void create(node*& root) { 13 int tmp; 14 if (root == null) { 15 cin >> tmp; 16 if (tmp == -1)//输入-1是结束该行输入 17 return; 18 root = new node; 19 root->data = tmp; 20 root->next = null; 21 create(root->next); 22 } 23 return; 24 } 25 void destory(head*& root) { 26 head* p = root;//循环遍历指针 27 head* q = root->down;//每次都指向最小 28 node* tmp = null; 29 int num = 0;//保存前一次输出的值 30 while (p != null && q != null) 31 { 32 while (p != null) { 33 if (p->next->data < q->next->data) { 34 q = p; 35 p = p->down; 36 } 37 else { 38 p = p->down; 39 } 40 } 41 if (q->next->data != num) { 42 cout << q->next->data << " "; 43 num = q->next->data; 44 } 45 if (q->up == null) { 46 if (q->next->next == null) { 47 p = root; 48 if (root->down == null) { 49 delete root->next; 50 delete root; 51 return; 52 } 53 root->down->up = null; 54 root = root->down; 55 delete p->next; 56 delete p; 57 p = q = root; 58 } 59 else { 60 tmp = q->next; 61 q->next = q->next->next; 62 delete tmp; 63 tmp = null; 64 p = q = root; 65 } 66 }//if 67 else { 68 if (q->next->next == null) { 69 q->up->down = q->down; 70 if (q->down == null) { 71 q->up->down = null; 72 delete q->next; 73 delete q; 74 } 75 else { 76 q->down->up = q->up; 77 delete q->next; 78 delete q; 79 } 80 p = q = root; 81 } 82 else { 83 tmp = q->next; 84 q->next = q->next->next; 85 delete tmp; 86 tmp = null; 87 p = q = root; 88 }//else 89 }//else 90 }//while 91 } 92 void createhead(int n) {//n表示有几行数据 93 head* root = new head; 94 root->down = null; 95 root->up = null; 96 root->next = null; 97 create(root->next);//第一行单独创建 98 head* p = root; 99 for (int i = 1; i < n; i++) 100 { 101 head* n = new head; 102 n->down = null; 103 n->next = null; 104 n->up = p; 105 p->down = n; 106 p = n; 107 create(p->next); 108 } 109 destory(root); 110 } 111 }
调用：
1 int main() { 2 int num; 3 std::cin >> num; 4 sort::createhead(num); 5 }
运行结果：
如果有什么错误欢迎大家指正。
本文来自网络收集，不代表计算机技术网立场，如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址：https://www.ctvol.com/c-cdevelopment/602314.html