当前位置：首页 > news >正文

单链表的创建及排序

news 来源：原创 2024/9/29 7:50:59

分数 5

作者李卫明

单位杭州电子科技大学

1.1编写程序，建立2个带头结点单链表，输入若干整数将正整数插入第1个单链表，将负整数插入第2个单链表，插入前和插入后单链表保持递增或相等次序，显示2个单链表，最后销毁。程序不可存在内存泄漏。

输入格式:

若干整数。

输出格式:

每行显示一个链表，元素间用分隔符->分隔；共两行

输入样例:

100 2 3 -2 -8 -6 -9 -10 50 2 -1

输出样例:

2->2->3->50->100
-10->-9->-8->-6->-2->-1

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

栈限制

8192 KB

C程序如下：

#include<stdio.h>    
#include<stdlib.h>    // 定义链表结构体  
typedef struct LinkList {    int Data;              // 节点数据  struct LinkList *Next; // 指向下一个节点的指针  
} LinkList, *List;    // 创建头节点的函数原型  
List  CreatHead();  
// 显示链表的函数原型  
void Display(List L);  
// 销毁链表的函数原型  
List Destroy(List L);  
// 反转链表的函数原型（但此函数在代码中并未实现）  
void Reverse(List L);  int main() {  // 定义两个链表的头尾指针  List firstHead, firstTail, secondHead, secondTail;  // 创建两个链表的头节点  firstHead = CreatHead();  firstTail = firstHead;  // 初始时，头尾指针指向同一个头节点  secondHead = CreatHead();  secondTail = secondHead; // 同上  int v;  // 循环读取输入，直到文件结束  while (scanf("%d", &v) != EOF) {  if (v > 0) {  // 如果输入为正数，则添加到第一个链表  List L = CreatHead();  // 创建一个新的头节点（实际上应该只创建节点，而不是头节点）  L->Data = v;  firstTail->Next = L;   // 将新节点添加到第一个链表的尾部  firstTail = L;         // 更新第一个链表的尾指针  }  else {  // 如果输入为负数，则添加到第二个链表  List L = CreatHead();  // 同上，这里应该只创建节点  L->Data = v;  secondTail->Next = L;  // 将新节点添加到第二个链表的尾部  secondTail = L;        // 更新第二个链表的尾指针  }  }  Sort(firstHead);  Sort(secondHead);  // 显示两个链表  Display(firstHead);  Display(secondHead);  // 销毁两个链表  Destroy(firstHead);  Destroy(secondHead);  return 0; // 返回0表示程序正常结束  
}  // 创建头节点的函数实现  
List CreatHead() {    List p = (List)malloc(sizeof(LinkList));  // 分配内存给新节点  if (p == NULL) {    exit(EXIT_FAILURE); // 如果分配失败，则退出程序  }    p->Next = NULL;  // 初始化新节点的Next指针为NULL  return p;  // 返回新节点的指针  
}    // 显示链表的函数实现  
void Display(List L) {  List p = L->Next;  // 从头节点的下一个节点开始遍历链表  while (p) {    printf("%d", p->Data);  // 打印当前节点的数据  p = p->Next;           // 移动到下一个节点  if (p) printf("->");   // 如果下一个节点存在，则打印"->"  }    printf("\n");  // 打印换行符  
}  // 销毁链表的函数实现  
List Destroy(List L) {    List p = L;    while (p->Next) {  // 循环直到最后一个节点（不包括头节点）  List q = p->Next;  // 临时保存下一个节点的指针  p->Next = q->Next; // 将当前节点的Next指针指向下一个节点的下一个节点，跳过下一个节点  free(q);          // 释放被跳过的节点的内存  }    free(p); // 释放头节点的内存（虽然这在实际中可能不是必须的，因为头节点可能已经在其他地方被释放了）  return NULL; // 销毁函数应该返回NULL，而不是L = NULL（这是无效的，因为L是传入函数的值的一个拷贝）  
}    void Sort(List L) {List pStar, pcur,pMin;pStar = L->Next;int temp;for (;pStar != NULL;pStar = pStar->Next) {pMin = pStar;for (pcur = pMin->Next;pcur != NULL; pcur = pcur->Next) {if (pcur->Data < pMin->Data) {pMin = pcur;}}if (pStar != pMin) {temp = pMin->Data;pMin->Data = pStar->Data;pStar->Data = temp;}}
}