初学者对链表的一些疑惑,希望解答
为什么两个链表L1,L2最后不指空?导致输出的结果不是NULL。
#include <stdio.h>
#include <stdlib.h>
typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node {
ElementType Data;
PtrToNode Next;
};
typedef PtrToNode List;
List Read(); /* 细节在此不表 */
void Print( List L ); /* 细节在此不表;空链表将输出NULL */
List Merge( List L1, List L2 );
int main()
{
List L1, L2, L;
L1 = Read();
L2 = Read();
L = Merge(L1, L2);
Print(L);
Print(L1);
Print(L2);
return 0;
}
/* 你的代码将被嵌在这里 */
List Merge(List L1, List L2){
List head = NULL,rear;
head = (List)malloc(sizeof(struct Node));
head->Next = NULL;rear = head;
L1 = L1->Next; L2 = L2->Next;
while(L1&&L2){
if(L1->Data >= L2->Data){
rear->Next = L2;
L2 = L2->Next;
}
else if(L1->Data < L2->Data){
rear->Next = L1;
L1 = L1->Next;
}
rear = rear->Next;
}
while(L1!=NULL) {
//printf("L2空\n");
rear->Next = L1;
rear = rear->Next;
L1 = L1->Next;
}
while(L2!=NULL){
//printf("L1空\n");
rear->Next = L2;
rear = rear->Next;
L2 = L2->Next;
}
return head;
}
List Read() {
int n; // 链表节点数
List head = NULL, tail = NULL; // 头指针和尾指针
scanf("%d", &n); // 读取节点数
head = (List)malloc(sizeof(struct Node)); // 创建空链表头
tail = head; // 尾指针初始化为头指针
while (n--) { // 循环读取节点数据,并插入链表中
// 创建新节点
PtrToNode p = (PtrToNode)malloc(sizeof(struct Node));
p->Next = NULL;
// 读取节点数据
scanf("%d", &(p->Data));
// 将新节点插入到链表尾部
tail->Next = p;
tail = p;
}
return head; // 返回链表头
}
void Print(List L) {
if (L == NULL) { // 如果链表为空表,直接输出 NULL
printf("NULL\n");
return;
}
PtrToNode p = L->Next;
while (p != NULL) { // 逐个输出节点的数据值
printf("%d", p->Data);
p = p->Next;
if (p != NULL) {
printf(" ");
} else {
printf("\n");
}
}
}
因为是带头结点的链表,在List Merge(List L1, List L2) 函数里稍作改变即可实现,修改如下,改动处见注释,供参考:
#include <stdio.h>
#include <stdlib.h>
typedef int ElementType;
typedef struct Node* PtrToNode;
struct Node {
ElementType Data;
PtrToNode Next;
};
typedef PtrToNode List;
List Read(); /* 细节在此不表 */
void Print(List L); /* 细节在此不表;空链表将输出NULL */
List Merge(List L1, List L2);
int main()
{
List L1, L2, L;
L1 = Read();
L2 = Read();
L = Merge(L1, L2);
Print(L);
Print(L1);
Print(L2);
return 0;
}
/* 你的代码将被嵌在这里 */
List Merge(List L1, List L2) {
List head = NULL, rear, p1, p2; // 修改
head = (List)malloc(sizeof(struct Node));
head->Next = NULL; rear = head;
p1 = L1; L1 = L1->Next; p2 = L2; L2 = L2->Next; // 修改
p1->Next = NULL; p2->Next = NULL; // 修改
while (L1 && L2) {
if (L1->Data >= L2->Data) {
rear->Next = L2;
L2 = L2->Next;
}
else if (L1->Data < L2->Data) {
rear->Next = L1;
L1 = L1->Next;
}
rear = rear->Next;
}
while (L1 != NULL) {
//printf("L2空\n");
rear->Next = L1;
rear = rear->Next;
L1 = L1->Next;
}
while (L2 != NULL) {
//printf("L1空\n");
rear->Next = L2;
rear = rear->Next;
L2 = L2->Next;
}
return head;
}
List Read() {
int n; // 链表节点数
List head = NULL, tail = NULL; // 头指针和尾指针
scanf("%d", &n); // 读取节点数
head = (List)malloc(sizeof(struct Node)); // 创建空链表头
head->Next = NULL; // 修改
tail = head; // 尾指针初始化为头指针
while (n--) { // 循环读取节点数据,并插入链表中
// 创建新节点
PtrToNode p = (PtrToNode)malloc(sizeof(struct Node));
p->Next = NULL;
// 读取节点数据
scanf("%d", &(p->Data));
// 将新节点插入到链表尾部
tail->Next = p;
tail = p;
}
return head; // 返回链表头
}
void Print(List L) {
if (L == NULL || L->Next == NULL) { // 修改
printf("NULL\n");
return;
}
PtrToNode p = L->Next;
while (p != NULL) { // 逐个输出节点的数据值
printf("%d", p->Data);
p = p->Next;
if (p != NULL) {
printf(" ");
}
else {
printf("\n");
}
}
}
Print函数并没有输出链表的最后一个节点的指针,而是只输出了链表中每个节点的值。因此,即使链表L1和L2的最后一个节点由于合并后变成了合并后链表L的最后一个节点而指向了NULL,Print函数也不会输出NULL,而是输出最后一个节点的值。
此外,Merge函数中也没有出现链表未指向NULL的情况。在合并两个链表时,rear指向的是合并后链表L的最后一个节点,而该节点的Next指针已经被初始化为NULL。因此,在将L1和L2中的节点插入到合并后链表L时,rear指针总是指向合并后链表L的最后一个节点,而不会指向NULL。
如果想要在Print函数中输出链表的最后一个节点的指针,可以修改Print函数。
void Print(List L) {
if (L == NULL) { // 如果链表为空表,直接输出 NULL
printf("NULL\n");
return;
}
PtrToNode p = L->Next;
while (p != NULL) { // 逐个输出节点的数据值
printf("%d", p->Data);
p = p->Next;
if (p != NULL) {
printf(" ");
} else {
printf(", Next: %p\n", p);
}
}
}
这个修改后的Print函数在输出链表中最后一个节点的值后,会输出最后一个节点的指针值(即Next指针),以便检查链表是否已经指向了NULL。
这个函数很简单就不赘述了,直接上代码。
①函数声明
void DestoryLink(Link_p*);
//释放整个链表空间 ,把L指针赋值为NULL
②函数功能实现
void DestoryLink(Link_p*L)
{
Link_p temp;
while((*L) != NULL)
{
temp = (*L);
(*L) = (*L)->next;
free(temp);
}
}