问题遇到的现象和发生背景
以链表为背景求集合的并集时出现死循环
问题相关代码,请勿粘贴截图
#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;
int flag=0;
while(pFast){
if(pFast->data==ele){
//判断pFast->link->data是否为目标值
Node *pFaster=pFast;
if(getTail(pFast)->data==ele){
flag=1;
}
while(pFaster->link->data==ele&&pFaster->link->link!=NULL){
// if(pFaster->link==NULL){
// break;
// }
//如果pFaster->link==NULL
//说明pFaster即将被赋值为尾指针
// printf("%d\t",pFaster->link->data);
pFaster=pFaster->link;
}
pFast=pFaster;
//找到需要删除的元素
if(pFast->link!=NULL){
//删除节点非尾节点
pSlow->link=pFast->link;
pFast=pFast->link;
}else{
pSlow->link=pFast->link;
break;
}
}
pFast=pFast->link;
pSlow=pSlow->link;
}
if(flag==1){
Node *p=L;
while(p->link->link!=NULL){
p=p->link;
}
p->link=NULL;
}
return;
}
Node * getUnion(Node *L1,Node *L2){
//其中一者为空
if(L1==NULL){
return L2;
}
if(L2==NULL){
return L1;
}
//对集合1中的数据进行遍历调用delet函数
//将两个集合中相同的元素删除掉
//感觉这里可以更简便但是暂时没想到办法
Node *pMove1=L1->link;
while(pMove1){
deleteData(L2,pMove1->data);
pMove1=pMove1->link;
}
//创建一个新的集合并对删除元素后的集合进行遍历
Node* result =initLinkList();
Node* p1=L1->link;
Node* p2=L2->link;
while(p1){
if(isHaveData(result,p1->data)==0){
tailInsert(result,p1->data);
}
p1=p1->link;
}
while(p2){
if(isHaveData(result,p2->data)==0){
tailInsert(result,p2->data);
}
p2=p2->link;
}
return result;
//return newList;
}
Node *getInterSection(Node* L1,Node* L2){
if(L1->link==NULL){
return NULL;
}
if(L2->link==NULL){
return NULL;
}
Node *result =initLinkList();
Node *p1=L1->link;
while(p1){
Node *p2=L2->link;
while(p2){
if(p1->data==p2->data&&(isHaveData(result,p1->data)==0)){
tailInsert(result,p1->data);
}
p2=p2->link;
}
p1=p1->link;
}
return result;
}
int isHaveData(Node * L,DataType ele){
//若链表中有元素ele则返回1否则返回0
Node *pMove =L->link;
while(pMove){
if(pMove->data==ele){
return 1;
}
}
return 0;
}
int getEleNum(Node *L){
if(L==NULL||L->link==NULL){
return 0;
}
Node* pMove=L->link;
int count=1;
while(pMove){
pMove=pMove->link;
count++;
}
return count;
}
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,44);
tailInsert(List,44);
tailInsert(List1,15);
tailInsert(List1,22);
tailInsert(List1,45);
tailInsert(List1,29);
tailInsert(List1,90);
tailInsert(List1,22);
tailInsert(List1,11);
tailInsert(List1,20);
tailInsert(List1,20);
tailInsert(List1,20);
tailInsert(List1,44);
tailInsert(List1,44);
tailInsert(List1,44);
tailInsert(List1,44);
tailInsert(List1,44);
tailInsert(List1,44);
tailInsert(List1,44);
//deleteData(List,44);
//ergodic(List);
Node * result2=getUnion(List,List1);
ergodic(result2);
//ergodic(List);
return 0;
}