单链表断链问题
/*本程序用于生成数据元素值递增有序的单链表,算法思想:先用CreateList()函数生成一个初始的链表,再用函数ListSort()对链表进行数据元素值自小到大的排序,再用函数DelrepetElem()删除元素值重复的结点.这样就得到一个数据元素值递增有序的单链表了.可问题是:ListSort()函数不能正确处理程序传递给它的链表(发生断链现象,而程序传递给它的确实是链表的引用,怎么还会有断链?*/
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<conio.h>
#include<time.h>
typedef struct LNode
{
int data;
struct LNode *next;
}LNode,*LinkList;
int DisplayList(LinkList head)//输出链表中的数据域的值
{
if(head==NULL)
{
printf("链表为空!\n");
return 0;
}
LinkList p=head;
while(p->next!=NULL)
{
printf("%5d ->",p->data);
p=p->next;
}
printf("%5d",p->data);//输出最后一个数据
printf("\n");
return 0;
}
int CreateList(LinkList &head)//生成链表的函数定义
{
int i=0;
LinkList p=NULL,q=NULL;
head=NULL;
srand( (unsigned)time( NULL ) );
for(i=0;i<30;i++)
{
p=(LinkList)malloc(sizeof(LNode));
p->data=rand()%100*7;
if(head==NULL)
head=p;
else
q->next=p;
q=p;
}
if(head!=NULL)
{
q->next=NULL;
}
return 1;
}
void ListSort(LinkList head)
{
if(head==NULL || head->next==NULL){}
else
{
LinkList pre,lp,p,q,s;
pre=head;q=p=pre->next;head->next=NULL;
while(p!=NULL)
{
s=(LinkList)malloc(sizeof(LNode));
s->data=q->data;s->next=NULL;
p=p->next;free(q);q=p;//记得释放原结点
if(s->data < head->data)
{
s->next=head;
head=s;
}
else
{
pre=head;lp=pre->next;
while(lp!=NULL && s->data > lp->data)
if(s->data > lp->data)
{
pre=lp;lp=lp->next;
}
s->next=lp;pre->next=s;
}
}
}
}
int DelrepetElem(LinkList head)//删除链表中重复的结点
{
LinkList pre=head,lp;
if(pre!=NULL)
{
while(pre->next!=NULL)
if(pre->data != pre->next->data)
pre=pre->next;
else
{
lp=pre->next;
pre->next=lp->next;
free(lp);
}
}
return 1;
}
void main()
{
LinkList head;
CreateList(head);//生成链表la
printf("初始生成时链表la的数据为：\n");
DisplayList(head);
ListSort(head);
printf("经排序后的链表la的数据为：\n");
DisplayList(head);
DelrepetElem(head);
printf("经排序且删除相同元素后的链表la的数据为：\n");
DisplayList(head);
}
算法
[解决办法]
楼主在原来的链表中free(q)了当然会断链啊，另外还有head->next=NULL这些操作也是不合适的
下面的代码仅供参考：
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<conio.h>
#include<time.h>
typedef struct LNode
{
int data;
struct LNode *next;
}LNode,*LinkList;
int DisplayList(LinkList head)//输出链表中的数据域的值
{
if(head==NULL)
{
printf("链表为空!\n");
return 0;
}
LinkList p=head;
while(p->next!=NULL)
{
printf("%5d ->",p->data);
p=p->next;
}
printf("%5d",p->data);//输出最后一个数据
printf("\n");
return 0;
}
int CreateList(LinkList &head)//生成链表的函数定义
{
int i=0;
LinkList p=NULL,q=NULL;
head=NULL;
srand( (unsigned)time( NULL ) );
for(i=0;i<30;i++)
{
p=(LinkList)malloc(sizeof(LNode));
p->data=rand()%100*7;
if(head==NULL)
head=p;
else
q->next=p;
q=p;
}
if(head!=NULL)
{
q->next=NULL;
}
return 0;
}
LinkList SortLinkList(LinkList h)
{
LinkList hh=h,pr,p,pp,ppr,temp,ph;
int min;
int flag=1; //是否是头一次的节点
ph=h;
while(h!=NULL)
{
min=h->data;
p=h;
pr=p;
ppr=pr;
pp=p;
/*
排好顺序的链表为头节点hh开头，每次都从h节点开头的
链表冒泡出数值最小的节点，接到hh链表开头的链表尾部。
*/
//开始冒泡
while(p!=NULL)
{
if(p->data<min) //找出 节点值数据最小的节点
{
ppr=pr; //最小节点的父节点
pp=p; //最小节点
min=p->data; //节点的最小数值
}
pr=p;
p=p->next;
}
/*
找到h节点之后，数值最小的节点， pp代表该最小节点
ppr为pp的先驱节点
*/
if(ppr==pp)
{
h=pp;
ph->next=h;
if(flag==1) //在还未建立头节点时，先建立头节点，hh代表该头节点
{
hh=h;flag=0; //头节点h之前的节点都是已经按从小到达的顺序排好顺序的节点，
}
}else
{
/*
如果最小节点不是头节点p的后驱节点的话
就把头节点h和最小数值节点兑换
*/
if(h!=ppr)
{
/*
交换节点 h和pp
用到两个的节点的先驱节点ph和ppr
*/
temp=h->next;
ppr->next=h;
h->next=pp->next;
pp->next=temp;
h=pp;
if(flag==1){hh=h;flag=0;}
else
{
ph->next=h;
}
}else
{ /*
如果最小节点p是头节点h的后驱节点的话
调换两个节点
*/
h->next=pp->next;
pp->next=h;
h=pp;
if(flag==1){hh=h;flag=0;}
else{
ph->next=pp;
}
}
}
ph=h;//ph为头节点h移动时的先驱节点
h=h->next;
}
return hh;
}
int DelrepetElem(LinkList head)//删除链表中重复的结点
{
LinkList pre=head,lp;
if(pre!=NULL)
{
while(pre->next!=NULL)
if(pre->data != pre->next->data)
pre=pre->next;
else
{
lp=pre->next;
pre->next=lp->next;
free(lp);
}
}
return 1;
}
void main()
{
LinkList head;
CreateList(head);//生成链表la
printf("初始生成时链表la的数据为：\n");
DisplayList(head);
head = SortLinkList(head);
printf("经排序后的链表la的数据为：\n");
DisplayList(head);
DelrepetElem(head);
printf("经排序且删除相同元素后的链表la的数据为：\n");
DisplayList(head);
}
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<conio.h>
#include<time.h>
typedef struct LNode
{
int data;
struct LNode *next;
}LNode,*LinkList;
int DisplayList(LinkList head)//输出链表中的数据域的值
{
if(head==NULL)
{
printf("链表为空!\n");
return 0;
}
LinkList p=head;
while(p->next!=NULL)
{
printf("%5d ->",p->data);
p=p->next;
}
printf("%5d",p->data);//输出最后一个数据
printf("\n");
return 0;
}
int CreateList(LinkList &head)//生成链表的函数
{
int i=0;
LinkList p=NULL,q=head; //q始终指向最后一个节点
head=NULL;
srand( (unsigned)time( NULL ) );
for(i=0;i<30;i++)
{
p=(LinkList)malloc(sizeof(LNode));
p->data=rand()%100*7;
if(head==NULL)
{
head=p;
p->next = NULL; //尾节点指针域设置为NULL
}
else
q->next=p;
q=p;
}
if(head!=NULL)
{
q->next=NULL;
}
return 1;
}
void ListSort(LinkList head) //对链表中的数据进行排序
{
if(head==NULL
------解决方案--------------------
head->next==NULL)
{
return ;
}
else
{
LinkList pre,lp,p,q,s;
pre=head;
q=p=pre->next;
head->next=NULL;
while(p!=NULL)
{
s=(LinkList)malloc(sizeof(LNode));
s->data=q->data;
s->next=NULL;
p=p->next;
free(q);
q=p;//记得释放原结点
if(s->data < head->data)
{
s->next=head;
head=s;
}
else
{
pre=head;
lp=pre->next;
while(lp!=NULL && s->data > lp->data)
{
pre = lp;
lp = lp->next;
}
if(NULL == lp) //lp == NULL
{
s->next = lp;
pre->next = s;
//pre=lp;
//lp=lp->next;
}
else //s->data < lp->data
{
s->next = pre->next;
pre->next = s;
}
}
}
}
}
int DelrepetElem(LinkList head)//删除链表中重复的结点
{
LinkList pre=head,lp;
if(pre!=NULL)
{
while(pre->next!=NULL)
if(pre->data != pre->next->data)
pre=pre->next;
else
{
lp=pre->next;
pre->next=lp->next;
free(lp);
}
}
return 1;
}
void main()
{
LinkList head;
CreateList(head);//生成链表la
printf("初始生成时链表la的数据为：\n");
DisplayList(head);
ListSort(head);
printf("经排序后的链表la的数据为：\n");
DisplayList(head);
DelrepetElem(head);
printf("经排序且删除相同元素后的链表la的数据为：\n");
DisplayList(head);
}
