使用C语言编写程序假设有两个按元素值递增次序排列的线性表,均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表,并要求利用原来两个单链表的结点存放归并后的单链表,并用main函数打印测试结果
时间: 2024-09-17 07:03:49 浏览: 40
已知线性表中的元素以值递增有序排列,并以单链表作存储结构。试写一高效的算法,删除表中所有值相同的多余元素(使得操作后的线性表中所有元素的值均不相同)
为了将两个已排序的单链表(升序)合并成一个降序的单链表,可以采用迭代或递归的方式。这里我们选择迭代法来实现,因为迭代通常更容易控制流程。
首先,我们需要定义链表节点结构体和一些辅助函数:
```c
// 定义链表节点结构
typedef struct ListNode {
int val;
struct ListNode* next;
} ListNode;
// 辅助函数,用于创建新节点
ListNode* createNode(int val) {
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
if (newNode != NULL) {
newNode->val = val;
newNode->next = NULL;
}
return newNode;
}
// 辅助函数,用于比较和交换节点
void swapNodes(ListNode** a, ListNode** b) {
int temp = (*a)->val;
(*a)->val = (*b)->val;
(*b)->val = temp;
}
// 归并过程的核心部分
ListNode* mergeDescending(ListNode* list1, ListNode* list2) {
ListNode* head = NULL; // 归并后链表的头指针
ListNode* tail = NULL; // 当前尾部节点
// 比较并选择较大的节点添加到归并链表中
while (list1 && list2) {
if (list1->val > list2->val) {
if (!head)
head = tail = list1;
else
tail->next = list1;
list1 = list1->next;
} else {
if (!head)
head = tail = list2;
else
tail->next = list2;
list2 = list2->next;
}
}
// 如果其中一个链表未遍历完,则将其剩余部分添加到归并链表尾部
if (list1)
tail->next = list1;
else
tail->next = list2;
return head;
}
```
接下来,在`main`函数中进行测试:
```c
int main() {
// 初始化两个示例链表(升序)
ListNode* list1 = createNode(1);
list1->next = createNode(3);
list1->next->next = createNode(5);
ListNode* list2 = createNode(2);
list2->next = createNode(4);
list2->next->next = createNode(6);
// 归并并打印结果
ListNode* mergedList = mergeDescending(list1, list2);
// 打印归并后的链表(降序)
while (mergedList) {
printf("%d ", mergedList->val);
mergedList = mergedList->next;
}
// 释放内存
freeListNode(mergedList); // 自定义的释放链表函数
return 0;
}
```
这个程序会创建两个升序的链表,然后通过`mergeDescending`函数合并它们,形成一个降序的链表,并在`main`中打印出来。注意你需要补充`freeListNode`函数来处理节点释放。
阅读全文