编写一个C语言程序,要求实现带头结点的链表的以下功能: 链表初始化、链表的建立(分别按头插法和尾插法两种方法建立两个链表:链表A和链表B,要求提供机会在键盘上分别依次输入两个链表的元素值)、链表A的按值查找(提供机会在键盘上输入要查找的值)、链表A的遍历、链表A的插入(提供机会在键盘上输入要插入的值和插入的位置)、链表A的删除(提供机会在键盘上输入要删除的值)、最后再把链表A和链表B进行合并,合并之后成链表C,要求链表C仍有序。(要求给出详尽的注释)
时间: 2023-05-27 07:01:51 浏览: 53
```
#include <stdio.h>
#include <stdlib.h>
//定义链表结点结构体
typedef struct node {
int data;
struct node *next;
}Node, *pNode;
//函数声明
pNode initList (); //链表初始化
pNode createListHead (pNode head); //头插法创建链表
pNode createListTail (pNode head); //尾插法创建链表
pNode searchList (pNode head); //按值查找链表
void traverseList (pNode head); //遍历链表
pNode insertList (pNode head); //插入结点到链表中
pNode deleteList (pNode head); //在链表中删除结点
pNode mergeList (pNode head1, pNode head2); //合并两个有序链表
int main () {
pNode headA = NULL;
pNode headB = NULL;
pNode headC = NULL;
//链表A的创建
printf("请依次输入链表A的元素值(以-1作为结尾):");
headA = createListTail(headA); //用尾插法创建链表A
printf("链表A的元素值为:");
traverseList(headA); //遍历链表A
//链表A的按值查找
headA = searchList(headA);
//链表A的插入
headA = insertList(headA);
printf("链表A插入后的元素值为:");
traverseList(headA); //遍历链表A
//链表A的删除
headA = deleteList(headA);
printf("链表A删除后的元素值为:");
traverseList(headA); //遍历链表A
//链表B的创建
printf("请依次输入链表B的元素值(以-1作为结尾):");
headB = createListHead(headB); //用头插法创建链表B
printf("链表B的元素值为:");
traverseList(headB); //遍历链表B
//链表合并
headC = mergeList(headA, headB);
printf("链表A和链表B合并后的元素值为:");
traverseList(headC); //遍历链表C
return 0;
}
//函数定义
//链表初始化
pNode initList () {
pNode head = (pNode)malloc(sizeof(Node)); //分配内存
head -> next = NULL; //初始化头结点的指针域为空
return head; //返回头结点的地址
}
//头插法创建链表
pNode createListHead (pNode head) {
int val;
head = initList(); //初始化链表
while (1) {
scanf("%d", &val);
if (val == -1) break; //输入值为-1时退出循环
pNode p = (pNode)malloc(sizeof(Node));
p -> data = val;
p -> next = head -> next; //插入结点到链表头部
head -> next = p;
}
return head;
}
//尾插法创建链表
pNode createListTail (pNode head) {
int val;
pNode tail = head; //定义尾指针
while (1) {
scanf("%d", &val);
if (val == -1) break; //输入值为-1时退出循环
pNode p = (pNode)malloc(sizeof(Node));
p -> data = val;
p -> next = NULL;
tail -> next = p; //插入结点到链表尾部
tail = p; //更新尾指针
}
return head -> next;
}
//按值查找链表
pNode searchList (pNode head) {
int val;
printf("请输入要查找的值:");
scanf("%d", &val);
pNode p = head -> next; //指向链表的首结点
while (p != NULL && p -> data != val) {
p = p -> next; //顺序往后查找
}
if (p == NULL) {
printf("没有找到这个值!\n");
} else {
printf("找到了这个值!\n");
}
return head;
}
//遍历链表
void traverseList (pNode head) {
pNode p = head;
while (p != NULL) {
printf("%d ", p -> data);
p = p -> next;
}
printf("\n");
}
//插入结点到链表中
pNode insertList (pNode head) {
pNode p = (pNode)malloc(sizeof(Node));
int val, pos;
printf("请输入要插入的值和插入位置:");
scanf("%d %d", &val, &pos);
//查找插入位置的前一个结点
pNode q = head;
for (int i = 1; i < pos; i++) {
if (q == NULL) {
printf("插入位置无效!\n");
return head;
}
q = q -> next;
}
//更新新结点的指针域
p -> data = val;
p -> next = q -> next;
//更新前一个结点的指针域
q -> next = p;
return head;
}
//在链表中删除结点
pNode deleteList (pNode head) {
int val;
printf("请输入要删除的值:");
scanf("%d", &val);
pNode p = head;
while (p -> next != NULL && p -> next -> data != val) {
p = p -> next; //顺序往后查找
}
if (p -> next == NULL) {
printf("没有找到这个值!\n");
} else {
//删除结点,并更新前一个结点的指针域
pNode q = p -> next;
p -> next = q -> next;
free(q); //释放空间
}
return head;
}
//合并两个有序链表
pNode mergeList (pNode head1, pNode head2) {
pNode p = head1 -> next;
pNode q = head2 -> next;
pNode head3 = initList();
pNode r = head3;
//进行合并
while (p != NULL && q != NULL) {
if (p -> data <= q -> data) {
r -> next = p;
p = p -> next;
} else {
r -> next = q;
q = q -> next;
}
r = r -> next;
}
//将剩余结点连接到链表3的最后
if (p != NULL) {
r -> next = p;
}
if (q != NULL) {
r -> next = q;
}
return head3 -> next;
}
```