线性单链表合并问题
问题: 就是最后的Status MergeList_L()函数调用的时候程序会崩溃掉,麻烦帮我看看。 谢谢。#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef int ElemType;
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LNode, *Link, *Position;
typedef struct
{
Link head, tail;
int len;
}LinkList;
Status MakeNode(Link *p, ElemType e);
void FreeNode(Link *p);
Status InitList(LinkList *L);
Status ClearList(LinkList *L);
Status Destory(LinkList *L);
Status InsertList(LinkList *L, Link s);
void Traverse(LinkList *L);
void Append(LinkList *L, Link s);
ElemType GetCurElem(Link p);
Status IsEmpty(LinkList *L);
Position PriorPos(LinkList L, Link p);
Position NextPos(Link p);
Status compare(ElemType e1,ElemType e2);
Status ListTravese(LinkList L, void (*visit)(ElemType));
Status MergeList_L(LinkList *La, LinkList *Lb, LinkList *Lc, int (*compare)(ElemType e1, ElemType e2));
Status DelFirst(LinkList L, Link h, Link *q);
void FreeNode(Link p);
void main()
{
Link p, s, h;
LinkList L;
Status i;
int j;
Link q;
ElemType e;
// //归并链表
LinkList La, Lb, Lc;
if(!InitList(&La)) //初始化空的线性表La不成功
exit(-1); //异常退出
for(j = 1; j <= 10; j++)
{
MakeNode(&p, j*3);
InsertList(&La, p);
}
printf("La:\n");
Traverse(&La);
if(!InitList(&Lb)) //初始化空的线性表Lb不成功
exit(-1); //异常退出
for(j = 1; j <= 10; j++)
{
MakeNode(&p, j*2);
InsertList(&Lb, p);
}
printf("Lb:\n");
Traverse(&Lb);
// InitList(&Lc);
MergeList_L(&La, &Lb, &Lc, compare);
printf("Lc:\n");
Traverse(&Lc);
Destory(&La);
Destory(&Lb);
}
//分配由p指向e的结点
Status MakeNode(Link *p, ElemType e)
{
(*p) = (Link)malloc(sizeof(LNode));
if(!(*p))
return ERROR;
(*p)->data = e;
return OK;
}
void FreeNode(Link *p)
{
free(*p);
(*p) = NULL;
}
//创造一个空的线性表
Status InitList(LinkList *L)
{
Link p;
p = (Link)malloc(sizeof(LNode));
if(!p)
return ERROR;
p->next = NULL;
L->head = L->tail = p;
L->len = 0;
return OK;
}
//将线性表L重置为空表,并释放原链表的空间
Status ClearList(LinkList *L)
{
Link p, q;
if(L->head != L->tail)
{
p = q = L->head->next;
L->head = NULL;
while(p < L->tail)
{
p = q->next;
free(q);
q = p;
}
free(q);
L->tail = L->head;
L->len = 0;
}
return OK;
}
//销毁相信链表L, L不在存在
Status Destory(LinkList *L)
{
ClearList(L);
FreeNode(&(L->head)); //释放头结点
L->tail = NULL;
L->len = 0;
return OK;
}
//将s所指结点插入线性表
Status InsertList(LinkList *L, Link s)
{
L->tail->next = s;
L->tail = s;
L->len++;
return OK;
}
void Traverse(LinkList *L)
{
Link p;
p = L->head->next;
int i;
for(i = 0; i < L->len; i++)
{
printf("No.%d: %d\n", i, p->data);
p = p->next;
}
printf("The length of list is %d.\n", L->len);
}
//将指针s所指(彼此以指针相链)的一串结点链接在线性表L的最后一个结点
//之后,并改变链表L的指针指向新的尾结点
void Append(LinkList *L, Link s)
{
int i=1;
L->tail->next = s; //s接到L的尾部
while(s->next) //计算s的长度
{
i++;
s = s->next;
}
L->tail = s; //L的尾指针变成s的尾指针
L->len+=i; //增加长度
printf("i = %d\n", i);
}
//已知p指向线性链表中的一个结点,返回p所指元素的值
ElemType GetCurElem(Link p)
{
return p->data;
}
//若线性表为空,则返回TRUE,否则饭后FALSE
Status IsEmpty(LinkList *L)
{
if(!L->head->next)
return TRUE;
else
return FALSE;
}
////已知p指向线性表L中的一个结点,返回p所指结点的直接后继的位置
//若无后继,返回NULL
Position NextPos(Link p)
{
return p->next;
}
Status compare(ElemType e1,ElemType e2)
{
return e1 <= e2;
}
//依次对L的每个元素调用函数visit()。一旦visit()失败,则操作失败
Status ListTravese(LinkList L, void (*visit)(ElemType))
{
Link p;
p = L.head->next;
int i;
for(i = 0; i < L.len; i++)
{
visit(p->data);
p = p->next;
}
printf("\n");
return OK;
}
//已知h指向线性链表的头结点,删除链表中的第一个结点并以q返回
Status DelFirst(LinkList L, Link h, Link *q)
{
Link p;
MakeNode(q, 0); //初始胡q;
(*q)->data = h->next->data; //把第一个数据结点的值赋值给q
p = h->next; //使p指向第一个数据结点
h->next = p->next;
free(p);
L.len --;
return OK;
}
//释放链表L的头结点
void FreeNode(Link p)
{
free(p);
}
//已知单链表La和Lb的元素按值非递减排列
//归并La和Lb得到新的单链表Lc,Lc的元素也按值非递减排列
Status MergeList_L(LinkList *La, LinkList *Lb, LinkList *Lc, int (*compare)(ElemType e1, ElemType e2))
{
Link ha, hb, pa, pb, q;
ElemType a, b;
if(!InitList(Lc)) //存储空间分配失败
{
printf("Lc内存分配失败");
return ERROR;
}
ha = La->head;
hb = Lb->head;
pa = NextPos(ha);
pb = NextPos(hb);
while(!IsEmpty(La)&&!IsEmpty(Lb)) //pa和pb非空
{
a = GetCurElem(pa);
b = GetCurElem(pb);
if(compare(a, b)) //a<=b
{
DelFirst(*La, ha, &q); //删除La中的第一个元素,并以q返回
Append(Lc, q); //DelFirst 返回的q插入到Lc中
pa = NextPos(ha);
}
else
{
DelFirst(*Lb, hb, &q);
Append(Lc, q);
pa = NextPos(hb);
}
if(pa) //如果最后La中还剩有元素,全部合并到Lc中
Append(Lc, ha);
else
Append(Lc, hb);
FreeNode(ha); //释放La的头结点
FreeNode(hb); //释放Lb的头结点
}
return OK;
}