#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//定義一個學生結構體
typedef struct Stu
{
int id;
int score;
struct Stu *pnext;
}Stu;
//創建一個鏈表
Stu *create_Stu(int n)
{
//先定義一個頭結點，不存放有效數據
Stu *head = (Stu*)malloc(sizeof(Stu));
if (head == NULL)
return NULL;
head->id = -1;
head->score = -1;
head->pnext = NULL;
//輸入要加入的n個結點的信息，新的結點加到鏈表最后
Stu *tmp = head;
int i;
for (i = 0; i < n; i++)
{
Stu *new_node = (Stu*)malloc(sizeof(Stu));
if (new_node == NULL)
return NULL;
scanf("%d", &new_node->id);
scanf("%d", &new_node->score);
new_node->pnext = NULL;
//新節點加到鏈表最后
tmp->pnext = new_node;
tmp = new_node;
}
return head;
}
//將一個鏈表與另一個鏈表合并，返回第一個鏈表頭部
Stu *merge_Stu(Stu *students1, Stu *students2)
{
if (students1 == NULL || students2 == NULL)
return NULL;
//先找到第一個鏈表的尾結點
Stu *tmp1 = students1;
while (tmp1->pnext != NULL)
{
tmp1 = tmp1->pnext;
}
//出來之后tmp1就為第一個鏈表的尾結點
Stu *tmp2 = students2;
//第一個鏈表的尾結點連接第二個鏈表的首結點
tmp1->pnext = tmp2->pnext;
//不要忘記釋放第二個鏈表的頭結點
free(tmp2);
//返回合并之后的頭結點
return students1;
}
//鏈表結點排序重組
void sort_Stu(Stu *students)
{
if (students == NULL)
return;
Stu *pre = NULL;
Stu *cur = NULL;
Stu tmp;
//選擇法對結點進行排序
for (pre = students->pnext; pre->pnext != NULL; pre = pre->pnext)
{
for (cur = pre->pnext; cur != NULL; cur = cur->pnext)
{
if (pre->id > cur->id)
{
//數據域和指針域都要進行交換
//數據域交換
tmp = *pre;
*pre = *cur;
*cur = tmp;
//指針域交換
tmp.pnext = pre->pnext;
pre->pnext = cur->pnext;
cur->pnext = tmp.pnext;
}
}
}
}
//打印鏈表信息
void print_Stu(Stu *students)
{
if (students == NULL || students->pnext == NULL)
{
printf("invalid list!\n");
return;
}
Stu *cur = students->pnext; //指向首結點
while (cur != NULL)
{
printf("%d %d\n", cur->id, cur->score);
cur = cur->pnext;
}
}
//釋放整個鏈表
void destory_Stu(Stu *students)
{
if (students == NULL)
return;
Stu *s = students;
Stu *tmp = NULL; //用來保存當前所釋放的結點的下一個結點
while (s != NULL)
{
tmp = s->pnext;
free(s);
s = tmp;
}
}
int main()
{
int N, M;
scanf("%d %d", &N, &M);
//創建兩個鏈表
Stu *students1 = create_Stu(N);
Stu *students2 = create_Stu(M);
//合并兩個鏈表
Stu *students = merge_Stu(students1, students2);
//對新鏈表中的內容按學號升序排列并打印
sort_Stu(students);
print_Stu(students);
destory_Stu(students);
return 0;
}
//數據域和指針域都要進行交換
//數據域交換
tmp = *pre;
*pre = *cur;
*cur = tmp;
//指針域交換
tmp.pnext = pre->pnext;
pre->pnext = cur->pnext;
cur->pnext = tmp.pnext;
就是上面這個指針域和數據域交換了 |
