王道数P40 T6（单链表实现）

/**  * 用链表实现 王道P40 T6  *  * point:  * 排序链表：直接插入排序 o(n^2)，选择排序，冒泡排序(难度从易到难)  *  * ①算法思想：  * 使用直接插入排序，  * 让 p = L -> next; L -> next = NULL;  * 一开始，有序链表是空的，不断地从无序链表中取出节点，在有序链表中找到合适的插入位置，直到无序链表是空的。  *  * ②数据结构:  *  typedef struct LNode{         int data;         struct LNode *next;     }LNode,*LinkList;  *  * ③算法设计  */   #include <stdio.h> #include <iostream>  typedef struct LNode{     int data;     struct LNode* next; }LNode,*LinkList;   void InsertSort(LinkList &L){     LinkList p = L -> next,q;     LinkList u,r;//u在有序链表中找到合适的插入位置，r是u的前驱，这样才能在有序链表中插入操作     L -> next = NULL;     while(p){         r = L;         u = L -> next;         while(u && u -> data < p -> data){             r = u;             u = u -> next;             }         //找到了 u -> data >= p -> data 第一次插入空有序链表，将 p 插入到 u 前面         q = p -> next;//q 用来标记 p 下一个可以不断地从无序链表中取出数字         p -> next = u;         r -> next = p;         p = q;         } }