动态链表排序，求解释代码，加注释

izhanghongcun

#include <iostream.h>
class TestClass
{
public:
        TestClass(int data=0)
        {
                this->data = data;
                this->next = NULL;
        };
        int data;
        TestClass* next;
};
void Insert(TestClass* p,int data)
{
        TestClass* temp=new TestClass(data);
        TestClass* pParent=p;
        TestClass* pNext=p->next;
        while(pNext)
        {
                if( data > pNext->data)
                {
                        //********1********
                        pParent->next=temp;
                        temp->next = pNext;
                        return;
                }
                else
                {
                        pParent = pNext;
                        //********2********
                        pNext=pNext->next;
                }
        }
        if( pNext == NULL)
        {
                pParent->next = temp;
                return;
        }
}
void printf(TestClass* p)
{
//********3********
        while(p->next!=NULL)
        {
                cout<<p->next->data<<" ";
                p = p->next;
        }
        cout<<endl;
}
void Delete(TestClass* p)
{
//********4********
        TestClass* temp1=p->next;
        TestClass* temp2;
        while(temp1 != NULL)
        {
                temp2 = temp1->next;
                delete temp1;
                temp1 = temp2;
        }
}
void main()
{
        int i=0;
        TestClass head;
        do
        {
                int data;
                cout<<"请输入一个数字: "<<endl;
                cin>>data;
                if( data == 0) break;
                Insert(&head,data);
        }while(1);
        printf(&head);
        Delete(&head);
        return;
}

SingleLove

1. 
   
2. #include <iostream>
   
3. using namespace std;
   
4. 
   
5. //定义一个类名为 TestClass 的类(本质上就是结构体)
   
6. class TestClass
   
7. {
   
8. public:
   
9.         TestClass(int data = 0)//构造函数：用于初始化
   
10.         {
    
11.                 this->data = data;
    
12.                 this->next = NULL;
    
13.         };
    
14.         int data;//数据域
    
15.         TestClass* next;//指针域
    
16. };
    
17. 
    
18. //插入节点
    
19. void Insert(TestClass* p, int data)//变量p保存的是头结点的地址;即指针指向头结点
    
20. {
    
21.         TestClass* temp = new TestClass(data);//创建一个新的节点；并用data来给这个节点的数据域初始化
    
22.         TestClass* pParent = p;//保存头节点
    
23.         TestClass* pNext = p->next;//保存首节点
    
24. 
    
25.         while (pNext)//只要有下一个节点就进行循环; 即：pNext != NULL
    
26.         {
    
27.                 if (data > pNext->data)//data存储的值 > 当前节点的数据域的值
    
28.                 {
    
29.                         //********1********
    
30.                         pParent->next = temp;//头节点的next指向temp
    
31.                         temp->next = pNext;
    
32.                         return;//中断函数
    
33.                 }
    
34.                 else//如果data <= 当前节点的数据域
    
35.                 {
    
36.                         //执行完下面这两句代码就是移动一个节点的距离
    
37.                         pParent = pNext;//移动指针变量pParent指向下一个节点
    
38.                         //********2********
    
39.                         pNext = pNext->next;//移动指针变量指向pNext本身的下一个节点
    
40.                        
    
41.                 }
    
42.         }
    
43. 
    
44. 
    
45.         //如果能执行到这里代表pParent指向的是尾结点； pNext指向的是NULL
    
46.         //此时新节点temp还没有跟原有链表建立关系；
    
47.         //新节点temp是要在原有链表的尾部插入；组成新的链表
    
48.         if (pNext == NULL)
    
49.         {
    
50.                 pParent->next = temp;//尾节点的next指向新节点temp；
    
51.                 //由于构造函数已经把temp的next初始化为NULL，这里不需要temp->next = NULL;
    
52. 
    
53. 
    
54.                 return;//中断函数
    
55.         }
    
56. }
    
57. 
    
58. //打印
    
59. void printf(TestClass* p)//定义一个指针指向头节点；即：TestClass *p = &head
    
60. {
    
61.         //********3********
    
62.         while (p->next != NULL)//当前节点的next指向的不是 NULL
    
63.         {
    
64.                 cout << p->next->data << " ";//打印当前节点的下一个节点的数据域
    
65.                 p = p->next;//移动一个节点
    
66.         }
    
67.         cout << endl;
    
68. }
    
69. 
    
70. //释放
    
71. void Delete(TestClass* p)//定义一个指针指向头节点；即：TestClass *p = &head
    
72. {
    
73.         //********4********
    
74.         TestClass* temp1 = p->next;//定义一个辅助指针指向首节点
    
75.         TestClass* temp2;//定义一个辅助指针
    
76.         while (temp1 != NULL)//指针变量temp1指向的不是NULL则进行循环
    
77.         {
    
78.                 temp2 = temp1->next;//保存当前节点的下一个节点
    
79.                 delete temp1;//释放当前节点
    
80.                 temp1 = temp2;//指针变量temp1指向temp2指向的节点
    
81.         }
    
82. }
    
83. 
    
84. 
    
85. //
    
86. void main()
    
87. {
    
88.         int i = 0;//定义变量i并初始化为0；貌似没看到在哪里用到
    
89.         TestClass head;//创建头结点
    
90.         do
    
91.         {
    
92.                 int data;//定义变量data
    
93.                 cout << "请输入一个数字: " << endl;
    
94.                 cin >> data;
    
95. 
    
96.                 if (data == 0) break;//如果输入的数字是0就跳出循环
    
97. 
    
98.                 Insert(&head, data);//调用函数Insert;把头节点的地址和输入的数字传给这个函数的形参
    
99.         } while (1);
    
100.         printf(&head);//调用printf()函 打印链表
     
101.         Delete(&head);//调用Delete()函数销毁链表
     
102.         return;
     
103. }

复制代码