单向链表

  1 /*输入n，再输入n个（0 - 100）之间的正整数
  2 （1）    按输入次序建立单链表，并输出链表的值；（10分）
  3 （2）    对链表按值从小到大排序，并输出链表的值；（15分）
  4 （3）    删除值相同的结点，输出链表的值；（10分）
  5 （4）    将链表倒序，并输出。（5分）
  6 例如：输入 （文件名Test1.txt）
  7 13
  8 48 60 50 88 88 42 30 60 48 88 73 88 30
  9 输出
 10 48 60 50 88 88 42 30 60 48 88 73 88 30
 11 30 30 42 48 48 50 60 60 73 88 88 88 88
 12 30 42 48 50 60 73 88
 13 88 73 60 50 48 42 30*/
 14 #include <iostream>
 15 using namespace std;
 16 
 17 struct Node
 18 {
 19     int data;
 20     Node* next;
 21 };
 22 
 23 //初始化
 24 Node* InitNode()
 25 {
 26     Node *head = (Node*)malloc(sizeof(Node));
 27     if (head == NULL)   return NULL;
 28     (head)->data = 0;
 29     (head)->next = NULL;
 30     return head;
 31 }
 32 
 33 //头插法
 34 void HeadInsertNode(Node** head,int key)
 35 {
 36     Node* newnode = (Node*)malloc(sizeof(Node));
 37     newnode->data = key;
 38     newnode->next = (*head)->next;
 39     (*head)->next = newnode;
 40 }
 41 
 42 //尾插法
 43 void TailInsertNode(Node** head, int key)
 44 {
 45     Node* temp = *head;
 46     while (temp->next != NULL)
 47     {
 48         temp = temp->next;
 49     }
 50     Node* newnode = (Node*)malloc(sizeof(Node));
 51     newnode->data = key;
 52     newnode->next = NULL;
 53     temp->next = newnode;
 54 }
 55 
 56 //排序链表
 57 void SortNode(Node** head)
 58 {
 59     Node* t1;
 60     Node* t2;
 61     for (t1 = (*head)->next; t1 != NULL; t1 = t1->next)
 62     {
 63         for (t2 = t1->next; t2 != NULL; t2 = t2->next)
 64         {
 65             if (t1->data > t2->data)
 66             {
 67                 Node* t3 = (Node*)malloc(sizeof(Node));
 68                 t3->data = t1->data;
 69                 t1->data = t2->data;
 70                 t2->data = t3->data;
 71             }
 72         }
 73     }
 74 }
 75 
 76 //删除该结点
 77 void deleteNode(Node** pre)
 78 {
 79     Node* node = (*pre)->next;
 80     (*pre)->next = (*pre)->next->next;
 81     delete(node);
 82 }
 83 
 84 //删除相同元素
 85 void SameDelete(Node** head)
 86 {
 87     if ((*head)->next != NULL)
 88     {
 89         Node* nownode = (*head)->next;
 90         while (nownode != NULL)
 91         {
 92             if (nownode->next != NULL)
 93             {
 94                 if (nownode->next->data == nownode->data)
 95                 {
 96                     deleteNode(&nownode);
 97                 }
 98                 else
 99                     nownode = nownode->next;
100             }
101             else
102                 return;
103         }
104     }
105 }
106 
107 //输出链表
108 void PrintNode(Node** head)
109 {
110     if ((*head)->next != NULL)
111     {
112         Node* temp = (*head)->next;
113         while (temp != NULL)
114         {
115             cout << temp->data << " ";
116             temp = temp->next;
117         }
118         cout << endl;
119     }
120 }
121 
122 //翻转链表
123 void TurnOverNode(Node** head)
124 {
125     if ((*head)->next != NULL)
126     {
127         Node* pre;
128         Node* nownode = (*head)->next;
129         Node* nextnode = (*head)->next->next;
130         nownode->next = NULL;
131         while (nextnode != NULL)
132         {
133             pre = nownode;
134             nownode = nextnode;
135             nextnode = nextnode->next;
136             nownode->next = pre;
137         }
138         nextnode = (Node*)malloc(sizeof(Node));
139         nextnode->data = 0;
140         nextnode->next = nownode;
141         (*head) = nextnode;
142     }
143 }
144 
145 int main()
146 {
147     Node* head=InitNode();
148   
149     TailInsertNode(&head, 48);
150     TailInsertNode(&head, 60);
151     TailInsertNode(&head, 50);
152     TailInsertNode(&head, 88);
153     TailInsertNode(&head, 42);
154     TailInsertNode(&head, 30);
155     TailInsertNode(&head, 60);
156     TailInsertNode(&head, 48);
157     TailInsertNode(&head, 88);
158     TailInsertNode(&head, 73);
159     TailInsertNode(&head, 88);
160     TailInsertNode(&head, 30);
161     PrintNode(&head);
162 
163     SortNode(&head);
164     PrintNode(&head);
165 
166     SameDelete(&head);
167     PrintNode(&head);
168 
169     TurnOverNode(&head);
170     PrintNode(&head);
171 }