C语言实现递增有序单链表的建立、合并与插入

问题描述

有两个非空有序表 A 和 B，A 表数据元素按严格递增顺序排列，B 表数据元素按严格递减顺序排列。要求完成以下操作：

分别用尾插法建立单链表 A，用头插法建立单链表 B，从而构建了两个递增有序的单链表。2. 合并 A 表和 B 表为一个递增的单链表 C，C 表中不允许有重复数据；要求 C 表仍然使用 A 表和 B 表的存储空间，不再额外申请存储空间。3. 在 C 表插入一个新元素 item，得到的新表仍然是一个没有重复数据的递增单链表。

C 代码实现c#include <stdio.h>#include <stdlib.h>

// 定义链表节点结构struct Node { int data; struct Node* next;};

// 尾插法建立有序链表 Avoid buildListA(struct Node** headA, int data) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = data; newNode->next = NULL; if (*headA == NULL) { headA = newNode; } else { struct Node current = *headA; while (current->next != NULL) { current = current->next; } current->next = newNode; }}

// 头插法建立有序链表 Bvoid buildListB(struct Node** headB, int data) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = data; if (*headB == NULL || data > (*headB)->data) { newNode->next = *headB; headB = newNode; } else { struct Node current = *headB; while (current->next != NULL && current->next->data > data) { current = current->next; } newNode->next = current->next; current->next = newNode; }}

// 合并链表 A 和 B 为 C，并去重struct Node* mergeLists(struct Node* headA, struct Node* headB) { struct Node* headC = headA; struct Node* tailC = headA; struct Node* currentA = headA->next; struct Node* currentB = headB; while (currentA != NULL && currentB != NULL) { if (currentA->data < currentB->data) { tailC->next = currentA; tailC = currentA; currentA = currentA->next; } else if (currentA->data > currentB->data) { tailC->next = currentB; tailC = currentB; currentB = currentB->next; } else { currentA = currentA->next; } } if (currentA != NULL) { tailC->next = currentA; } else { tailC->next = currentB; } return headC;}

// 在链表 C 中插入新元素 itemvoid insertElement(struct Node** headC, int item) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = item; newNode->next = NULL; if (*headC == NULL || item < (*headC)->data) { newNode->next = *headC; headC = newNode; } else { struct Node current = *headC; while (current->next != NULL && current->next->data < item) { current = current->next; } newNode->next = current->next; current->next = newNode; }}

// 打印链表void printList(struct Node* head) { struct Node* current = head; while (current != NULL) { printf('%d ', current->data); current = current->next; } printf(' ');}

int main() { struct Node* headA = NULL; struct Node* headB = NULL; // 依次插入有序表 A 的数据元素 buildListA(&headA, 1); buildListA(&headA, 3); buildListA(&headA, 5); // 依次插入有序表 B 的数据元素 buildListB(&headB, 4); buildListB(&headB, 2); buildListB(&headB, 0); printf('链表 A：'); printList(headA); printf('链表 B：'); printList(headB); struct Node* headC = mergeLists(headA, headB); printf('链表 C：'); printList(headC); insertElement(&headC, 6); printf('插入元素后的链表 C：'); printList(headC); return 0;}

代码说明

代码中使用了指针和动态内存分配来实现链表的操作。* buildListA 函数使用尾插法构建递增有序链表 A。* buildListB 函数使用头插法构建递增有序链表 B。* mergeLists 函数将链表 A 和 B 合并成一个新的递增有序链表 C，并去除重复元素。* insertElement 函数在链表 C 中插入一个新元素，并保持链表的有序性和唯一性。* printList 函数用于打印链表中的元素。

总结

本文提供的 C 代码清晰地展示了如何构建、合并和操作有序单链表，并有效地解决了去重和插入新元素的问题。这段代码结构清晰，易于理解和修改，可以作为学习数据结构和算法的良好参考。