问题遇到的现象和发生背景
求两个链表的并集时出现死循环
问题相关代码,请勿粘贴截图
#include <stdio.h>
#include <stdlib.h>
typedef int DataType;
typedef struct node{
DataType data;
struct node *link;
}Node;
//尾指针始终指向链表中的最后一个节点
//初始化空集合
Node * initLinkList(){
Node * head=(Node*)malloc(sizeof(Node));//头节点
if(head==NULL){
printf("链表初始化失败\n");
return NULL;
}
head->link=NULL;
return head;
}
Node * creatNode(DataType ele){
Node *newNode=(Node*)malloc(sizeof(Node));
if(newNode==NULL){
printf("节点创建失败\n");
return NULL;
}
newNode->data=ele;
newNode->link=NULL;
return newNode;
}
Node* getTail(Node *L){
//获取尾指针不使用全局变量
Node *pMove=L;
while(pMove->link){
pMove=pMove->link;
}
return pMove;
}
void tailInsert(Node *L,DataType ele){
if(L==NULL){
printf("链表未初始化\n");
return ;
}
Node * newNode=creatNode(ele);
getTail(L)->link=newNode;
}
void searchData(Node *L,DataType ele){
if(L==NULL||L->link==NULL){
printf("集合未初始化或者集合为空\n");
return;
}
Node *pMove=L->link;
while(pMove){
if(pMove->data==ele){
printf("集合中包含该元素\n");
return;
}
pMove=pMove->link;
}
printf("集合中不包含该元素\n");
return;
}
void deleteData(Node *L,DataType ele){
//定义一个flag用于解决问题输出
//这样可以一次删除多个相同的元素
if(L==NULL||L->link==NULL){
printf("集合未初始化或者集合为空\n");
return;
}
//两个指针便于得到目标元素之前节点的指针
Node *pFast=L->link;
Node *pSlow=L;
while(pFast){
if(pFast->data==ele){
if(pFast->link!=NULL){
//删除pFast指向的节点(非尾节点)
pSlow->link=pFast->link;
return;
}else{
//尾节点
pSlow->link=pFast->link;
//此处对于尾节点的不同处理方式极易丢掉
//只使用封装的遍历函数还看不出这一问题
//若没有本句尾指针将仍指向已被删除的元素
return;
}
}
pFast=pFast->link;
pSlow=pSlow->link;
}
return;
}
Node * getUnion(Node *L1,Node *L2){
//其中一者为空
if(L1==NULL){
return L2;
}
if(L2==NULL){
return L1;
}
//对集合1中的数据进行遍历调用delet函数
//将两个集合中相同的元素删除掉
//感觉这里可以更简便但是暂时没想到办法
Node *pMove2=L2->link;
while(pMove2){
deleteData(L1,pMove2->data);
pMove2=pMove2->link;
}
//创建一个数组和一个统计变量来记录两个集合中的数据
//count为数组的索引其中的元素有count+1个
int count=0;
DataType * arr=(DataType*)malloc(sizeof(DataType));
//之前的指针已经指向末尾需要重新创建指针
Node *p1=L1->link;
while(p1){
arr[count]=p1->data;
p1=p1->link;
count++;
}
Node *p2=L2->link;
while(p2){
p2=p2->link;
}
for(int i=0;i<count;i++){
printf("%d\t",arr[i]);
}
// 创建一个新的集合(链表)使用尾插法添加数组中的元素
// Node *newList=initLinkList();
// for(int i=0;i<count;i++){
// tailInsert(newList,arr[i]);
// }
// return newList;
return NULL;
}
void ergodic(Node * L){
Node *p=L->link;
while(p){
printf("%d ",p->data);
p=p->link;
}
printf("\n");
}
int main()
{
Node *List=initLinkList();
Node *List1=initLinkList();
tailInsert(List,22);
tailInsert(List,33);
tailInsert(List,44);
tailInsert(List,55);
tailInsert(List1,15);
tailInsert(List1,22);
tailInsert(List1,45);
tailInsert(List1,29);
tailInsert(List1,90);
//ergodic(List);
Node * result=getUnion(List,List1);
//ergodic(result);
return 0;
}
上方的代码可以正常运行但下方的代码会进入死循环
#include <stdio.h>
#include <stdlib.h>
typedef int DataType;
typedef struct node{
DataType data;
struct node *link;
}Node;
//尾指针始终指向链表中的最后一个节点
//初始化空集合
Node * initLinkList(){
Node * head=(Node*)malloc(sizeof(Node));//头节点
if(head==NULL){
printf("链表初始化失败\n");
return NULL;
}
head->link=NULL;
return head;
}
Node * creatNode(DataType ele){
Node *newNode=(Node*)malloc(sizeof(Node));
if(newNode==NULL){
printf("节点创建失败\n");
return NULL;
}
newNode->data=ele;
newNode->link=NULL;
return newNode;
}
Node* getTail(Node *L){
//获取尾指针不使用全局变量
Node *pMove=L;
while(pMove->link){
pMove=pMove->link;
}
return pMove;
}
void tailInsert(Node *L,DataType ele){
if(L==NULL){
printf("链表未初始化\n");
return ;
}
Node * newNode=creatNode(ele);
getTail(L)->link=newNode;
}
void searchData(Node *L,DataType ele){
if(L==NULL||L->link==NULL){
printf("集合未初始化或者集合为空\n");
return;
}
Node *pMove=L->link;
while(pMove){
if(pMove->data==ele){
printf("集合中包含该元素\n");
return;
}
pMove=pMove->link;
}
printf("集合中不包含该元素\n");
return;
}
void deleteData(Node *L,DataType ele){
//定义一个flag用于解决问题输出
//这样可以一次删除多个相同的元素
if(L==NULL||L->link==NULL){
printf("集合未初始化或者集合为空\n");
return;
}
//两个指针便于得到目标元素之前节点的指针
Node *pFast=L->link;
Node *pSlow=L;
while(pFast){
if(pFast->data==ele){
if(pFast->link!=NULL){
//删除pFast指向的节点(非尾节点)
pSlow->link=pFast->link;
return;
}else{
//尾节点
pSlow->link=pFast->link;
//此处对于尾节点的不同处理方式极易丢掉
//只使用封装的遍历函数还看不出这一问题
//若没有本句尾指针将仍指向已被删除的元素
return;
}
}
pFast=pFast->link;
pSlow=pSlow->link;
}
return;
}
Node * getUnion(Node *L1,Node *L2){
//其中一者为空
if(L1==NULL){
return L2;
}
if(L2==NULL){
return L1;
}
//对集合1中的数据进行遍历调用delet函数
//将两个集合中相同的元素删除掉
//感觉这里可以更简便但是暂时没想到办法
Node *pMove2=L2->link;
while(pMove2){
deleteData(L1,pMove2->data);
pMove2=pMove2->link;
}
//创建一个数组和一个统计变量来记录两个集合中的数据
//count为数组的索引其中的元素有count+1个
int count=0;
DataType * arr=(DataType*)malloc(sizeof(DataType));
//之前的指针已经指向末尾需要重新创建指针
Node *p1=L1->link;
while(p1){
arr[count]=p1->data;
p1=p1->link;
count++;
}
Node *p2=L2->link;
while(p2){
arr[count]=p2->data;
p2=p2->link;
count++;
}
for(int i=0;i<count;i++){
printf("%d\t",arr[i]);
}
// 创建一个新的集合(链表)使用尾插法添加数组中的元素
// Node *newList=initLinkList();
// for(int i=0;i<count;i++){
// tailInsert(newList,arr[i]);
// }
// return newList;
return NULL;
}
void ergodic(Node * L){
Node *p=L->link;
while(p){
printf("%d ",p->data);
p=p->link;
}
printf("\n");
}
int main()
{
Node *List=initLinkList();
Node *List1=initLinkList();
tailInsert(List,22);
tailInsert(List,33);
tailInsert(List,44);
tailInsert(List,55);
tailInsert(List1,15);
tailInsert(List1,22);
tailInsert(List1,45);
tailInsert(List1,29);
tailInsert(List1,90);
//ergodic(List);
Node * result=getUnion(List,List1);
//ergodic(result);
return 0;
}
运行结果及报错内容
我想要达到的结果
arr数组能够正常储存元素