首页 > 代码库 > 单链表的排序
单链表的排序
单链表的逆序:
由于链表不同于数组一样,所以将排好序的结点放到另一个链表中去,然后再由头指针指向该链表。
1 void Link::Sort(Node * Head) { 2 3 Node * Root = NULL; // 头指针,作为一个新链表指针,将所有结点链接到这里 4 Node * Tail = NULL; // 尾指针 5 Node * pMin = NULL; // 作为待操作链表结点中最小结点的前驱 6 Node * min = NULL; // 最小结点的指针 7 Node * p = NULL; // 操作指针 8 9 // 第一次Head是没有进过初始化的结点,所以它的data是一个负无穷值 10 while (Head != NULL) { 11 min = Head; // 将最小值链接到Root中以后,需要重新设置默认最小值 min为头的第一个结点,再找出真正最小结点 12 for (p = Head; p->next != NULL; p = p->next) { // 由于要设置前驱,所以不从 p=p->next开始 13 if (p->next->data < min->data) { 14 pMin = p; 15 min = p->next; 16 } 17 } // 获得最小结点 18 // 将最小结点插入到 Root中去,但是需要判断最小值是不是头结点,如果是就不必链接到Root 19 // 因为最后面会将Root中的链表又重新链接到Head中去 20 if (Root == NULL) { 21 // 当Root为空的时候,Root就是第一个结点,也是最小的 22 Root = min; 23 Tail = min; 24 } 25 else { 26 // 已经存在头结点了,需要插入到链表中,即末尾 27 Tail->next = min; 28 Tail = min; 29 } 30 31 if (min == Head) { 32 // 当最小值是链表中的第一个结点的时候,只需要后移一位就行了 33 Head = Head->next; 34 } 35 else { 36 // 当不是第一个结点的时候,则让当前最小结点断开链表,故此借助 前驱 pMin指向 min的下一个结点 37 pMin->next = min->next; 38 } 39 } // 获得有序链表 Root,Root中的结点都来自于Head中 40 if (Root != NULL) { 41 // Root不为空,表明有结点链接上来了,链表中都是结点尾指针,没有设置链表结束符 ->next=NULL; 42 Tail->next = NULL; 43 } 44 Head = Root; // 将Root中排序好的结点链接到Head上去 45 }
1 #include <iostream> 2 using namespace std; 3 4 struct Node { 5 char data; 6 Node * next; 7 }; 8 9 class Link { 10 public: 11 Link(); 12 ~Link(); 13 void Sort(Node *); 14 void Output(); 15 Node * getHead(); 16 private: 17 Node * Head; 18 void Create(); 19 }; 20 21 int main() { 22 23 cout << "ASCII码大小为:数字 < 大写字母 < 小写字母。注:数字10代表两个字符1,0" << endl; 24 Link L1; 25 L1.Output(); 26 L1.Sort(L1.getHead()); 27 cout << "排序后:" << endl; 28 L1.Output(); 29 30 system("pause"); 31 return 0; 32 } 33 34 void Link::Sort(Node * Head) { 35 36 Node * Root = NULL; // 头指针,作为一个新链表指针,将所有结点链接到这里 37 Node * Tail = NULL; // 尾指针 38 Node * pMin = NULL; // 作为待操作链表结点中最小结点的前驱 39 Node * min = NULL; // 最小结点的指针 40 Node * p = NULL; // 操作指针 41 42 // 第一次Head是没有进过初始化的结点,所以它的data是一个负无穷值 43 while (Head != NULL) { 44 min = Head; // 将最小值链接到Root中以后,需要重新设置默认最小值 min为头的第一个结点,再找出真正最小结点 45 for (p = Head; p->next != NULL; p = p->next) { // 由于要设置前驱,所以不从 p=p->next开始 46 if (p->next->data < min->data) { 47 pMin = p; 48 min = p->next; 49 } 50 } // 获得最小结点 51 // 将最小结点插入到 Root中去,但是需要判断最小值是不是头结点,如果是就不必链接到Root 52 // 因为最后面会将Root中的链表又重新链接到Head中去 53 if (Root == NULL) { 54 // 当Root为空的时候,Root就是第一个结点,也是最小的 55 Root = min; 56 Tail = min; 57 } 58 else { 59 // 已经存在头结点了,需要插入到链表中,即末尾 60 Tail->next = min; 61 Tail = min; 62 } 63 64 if (min == Head) { 65 // 当最小值是链表中的第一个结点的时候,只需要后移一位就行了 66 Head = Head->next; 67 } 68 else { 69 // 当不是第一个结点的时候,则让当前最小结点断开链表,故此借助 前驱 pMin指向 min的下一个结点 70 pMin->next = min->next; 71 } 72 } // 获得有序链表 Root,Root中的结点都来自于Head中 73 if (Root != NULL) { 74 // Root不为空,表明有结点链接上来了,链表中都是结点尾指针,没有设置链表结束符 ->next=NULL; 75 Tail->next = NULL; 76 } 77 Head = Root; // 将Root中排序好的结点链接到Head上去 78 } 79 80 Link::Link() { 81 Head = new Node(); 82 Head->next = NULL; 83 Create(); 84 } 85 Link::~Link() { 86 Node * p = NULL; 87 while (Head != NULL) { 88 p = Head; 89 Head = Head->next; 90 delete p; 91 } 92 } 93 94 void Link::Create() { 95 96 Node * p = Head; 97 char ch; 98 cout << "创建单链表,请输入一个结点(#作为结束符):" << endl; 99 cin >> ch; 100 Node * tem = NULL; 101 while (ch != ‘#‘) { 102 tem = new Node(); 103 tem->data =http://www.mamicode.com/ ch; 104 p->next = tem; 105 p = tem; 106 cin >> ch; 107 } 108 p->next = NULL; 109 110 } 111 112 void Link::Output() { 113 Node * p = Head->next; 114 while (p != NULL) { 115 cout << p->data << " "; 116 p = p->next; 117 } 118 cout << endl; 119 } 120 Node * Link::getHead() { 121 return Head; 122 }
单链表的排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。