编写程序,建立2个带头结点单链表,输入若干整数将正整数插入第1个单链表,将负整数插入第2个单链表,插入前和插入后单链表保持递增或相等次序,显示2个单链表,最后销毁。程序不可存在内存泄漏。)基础上合并2个单链表,合并前后单链表保持递增或相等次序,显示合并前后单链表。注意不可存在内存泄漏。
时间: 2024-03-13 10:42:53 浏览: 98
我编写的实现单链表的程序
好的,我已经明白你的问题了。下面是针对你的问题的解答:
首先,为了实现这个功能,我们需要定义一个带头结点的单链表结构体,如下所示:
```c
typedef struct Node {
int data;
struct Node *next;
} Node, *LinkedList;
```
接下来,我们需要实现几个函数,用于建立、插入、输出和销毁单链表。
1. 建立单链表函数createLinkedList,用于建立一个空的单链表。
```c
LinkedList createLinkedList() {
LinkedList head = (LinkedList) malloc(sizeof(Node));
head->next = NULL;
return head;
}
```
2. 插入单链表函数insertLinkedList,用于将一个整数插入到单链表中。
```c
void insertLinkedList(LinkedList head, int data) {
Node *p = head;
while (p->next != NULL && p->next->data <= data) {
p = p->next;
}
Node *newNode = (Node *) malloc(sizeof(Node));
newNode->data = data;
newNode->next = p->next;
p->next = newNode;
}
```
3. 输出单链表函数printLinkedList,用于输出单链表中的所有整数。
```c
void printLinkedList(LinkedList head) {
Node *p = head->next;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
```
4. 销毁单链表函数destroyLinkedList,用于销毁单链表并释放内存空间。
```c
void destroyLinkedList(LinkedList head) {
Node *p = head;
while (p != NULL) {
Node *q = p;
p = p->next;
free(q);
}
}
```
接下来,我们可以根据题目要求,分别建立两个单链表,并将正整数插入到第一个单链表中,将负整数插入到第二个单链表中,最后输出这两个单链表。
```c
int main() {
LinkedList list1 = createLinkedList();
LinkedList list2 = createLinkedList();
int n;
while (scanf("%d", &n) != EOF) {
if (n > 0) {
insertLinkedList(list1, n);
} else {
insertLinkedList(list2, n);
}
}
printLinkedList(list1);
printLinkedList(list2);
destroyLinkedList(list1);
destroyLinkedList(list2);
return 0;
}
```
最后,我们需要实现合并两个单链表的函数mergeLinkedLists,将两个单链表合并成一个。
```c
LinkedList mergeLinkedLists(LinkedList head1, LinkedList head2) {
LinkedList head = (LinkedList) malloc(sizeof(Node));
head->next = NULL;
Node *p = head;
Node *p1 = head1->next;
Node *p2 = head2->next;
while (p1 != NULL && p2 != NULL) {
if (p1->data <= p2->data) {
p->next = p1;
p1 = p1->next;
} else {
p->next = p2;
p2 = p2->next;
}
p = p->next;
}
if (p1 != NULL) {
p->next = p1;
}
if (p2 != NULL) {
p->next = p2;
}
return head;
}
```
最后,我们可以在主函数中调用mergeLinkedLists函数,将两个单链表合并成一个,并输出合并前后的单链表。
```c
int main() {
LinkedList list1 = createLinkedList();
LinkedList list2 = createLinkedList();
int n;
while (scanf("%d", &n) != EOF) {
if (n > 0) {
insertLinkedList(list1, n);
} else {
insertLinkedList(list2, n);
}
}
LinkedList list = mergeLinkedLists(list1, list2);
printLinkedList(list1);
printLinkedList(list2);
printLinkedList(list);
destroyLinkedList(list1);
destroyLinkedList(list2);
destroyLinkedList(list);
return 0;
}
```
阅读全文