C语言 单链表的插入删除操作

Question

两个单链表linklist1,linklist2。linklist1中结点包括学生的学号和下一个结点的指针，linklist2中结点包括linklist1链表每个学号对应的学生成绩。
把两个单链表合并成单链表conlink，结点包括学号，对应的成绩和下一个结点的指针，单链表按学号升序排列。
我的程序如下
#include "stdio.h"
struct linklist1
{int xh;
struct linklist1 *next;
};
struct linklist2
{int grade;
struct linklist2 *next;
};
struct conlink
{int xh;
int grade;
struct conlink *next;
};

struct linklist1 *creat1()
/**创建单链表a**/
{int i;
struct linklist1 *head,*p,*q;
head=(struct linklist1 *)malloc(sizeof(struct linklist1));
p=q=head;
for(i=0;i<5;i++)
{p=(struct linklist1 *)malloc(sizeof(struct linklist1));
scanf("%d",&(p->xh));
q->next=p;
q=p;
}
p->next=0;
return head;
}

struct linklist2 *creat2()
\**创建单链表b**\
{int i;
struct linklist2 *head,*p,*q;
head=(struct linklist2 *)malloc(sizeof(struct linklist2));
p=q=head;
for(i=0;i<5;i++)
{p=(struct linklist2 *)malloc(sizeof(struct linklist2));
scanf("%d",&(p->grade));
q->next=p;
q=p;
}
p->next=0;
return head;
}

scan(struct linklist1 *a,struct linklist2 *b,struct linklist1 **p,struct linklist2
**q)
\**查找单链表中学号最大的结点，存入*p,对应的成绩存入*q**\
{struct linklist1 *m;
int i=0,u=0;
m=a->next;
while(a->next!=0)
{a=a->next;
i++;
if(a->xh>m->xh)
{m=a;
u=i;
}
}
*p=m;
for(i=0;i<u;i++)
b=b->next;
*q=b;
}

conlink(struct conlink *head,struct linklist1 **p,struct linklist2 **q)
\**用头插法建立单链表c**\
{struct conlink *a;
a=(struct conlink *)malloc(sizeof(struct conlink));
a->xh=(*p)->xh;
a->grade=(*q)->grade;
a->next=head->next;
head->next=a;
}

outlist1(struct linklist1 *head,struct linklist1 **p)
/**删除a单链表中学号最大的结点（最大的结点用scan函数已经找出）**/
{while(head->next!=(*p))
head=head->next;
head->next=(*p)->next;
}

outlist2(struct linklist2 *head,struct linklist2 **q)
/**删除b单链表中对应的结点**/
{while(head->next!=(*q))
head=head->next;
head->next=(*q)->next;
}

output(struct conlink *head)
/**输出c链表**/
{
while(head->next!=0)
{printf("%d %d\n",head->next->xh,head->next->grade);
head=head->next;
}
}

main()
{struct linklist1 *a;
struct linklist2 *b;
struct linklist1 *p;
struct linklist2 *q;
struct conlink *head;
a=creat1();
b=creat2();
head=(struct conlink *)malloc(sizeof(struct conlink));
head->next=0;
while(a->next!=0)
{scan(a,b,&p,&q);
conlink(head,&p,&q);
outlist1(a,&p);
outlist2(b,&q);
}
output(head);
}我的程序总是在删除linklist1链表中结点时陷入死循环，请高手分析原因。

Answer 1

学到指针，也要开始学习C语言的调试技能了，发现问题，最好自己调试解决。

如果编程软件支持断点，单步调试等功能那就最好了，如果不支持，也可以使用printf()语句打印相关的变量值来进行调试。

主要问题出在scan()函数
scan(struct linklist1 *a,struct linklist2 *b,struct linklist1 **p,struct linklist2 **q)
{
struct linklist1 *m;
int i=0,u=0;
m=a->next;
while(a->next!=0)
{a=a->next;
i++;
if(a->xh>m->xh)/*当只剩下一个记录时,u=0*/
{m=a;
u=i;
}
}
*p=m;
for(i=0;i<u;i++) /* u=0时，这个循环不会执行 */
b=b->next;
*q=b; /* u=0时，这里就出错了 */
}

修改后的代码，有简单的调试信息输出
#include "stdio.h"
struct linklist1
{
int xh;
struct linklist1 *next;
};
struct linklist2
{
int grade;
struct linklist2 *next;
};

struct conlink
{
int xh;
int grade;
struct conlink *next;
};

struct linklist1 *creat1()
/**创建单链表a**/
{
int i;
struct linklist1 *head,*p,*q;
head=(struct linklist1 *)malloc(sizeof(struct linklist1));
p=q=head;
printf("please input 5 xh:\n");
for(i=0;i<5;i++)
{p=(struct linklist1 *)malloc(sizeof(struct linklist1));
scanf("%d",&(p->xh));
p->next=0;
q->next=p;
q=p;
}
return head;
}

struct linklist2 *creat2()
/**创建单链表b**/
{int i;
struct linklist2 *head,*p,*q;
head=(struct linklist2 *)malloc(sizeof(struct linklist2));
p=q=head;
printf("please input 5 grade:\n");
for(i=0;i<5;i++)
{p=(struct linklist2 *)malloc(sizeof(struct linklist2));
scanf("%d",&(p->grade));
p->next=0;
q->next=p;
q=p;
}
return head;
}

scann(struct linklist1 *a,struct linklist2 *b,struct linklist1 **p,struct linklist2
**q)
/**查找单链表中学号最大的结点，存入*p,对应的成绩存入*q**/
{
struct linklist1 *m = a->next;
printf("scan()...\n");
while(a->next && b->next)
{
a=a->next;
b=b->next;
if(a->xh >= m->xh)
{
*p=a;
*q=b;
printf("xh=%d grade = %d\n", (*p)->xh, (*q)->grade);
getch();
}
}
}

conlink(struct conlink *head,struct linklist1 *p,struct linklist2 *q)
/**用头插法建立单链表c**/
{
struct conlink *a;
printf("conlink()...\n");
a=(struct conlink *)malloc(sizeof(struct conlink));
a->xh=p->xh;
a->grade=q->grade;
a->next=head->next;
head->next=a;
}

outlist1(struct linklist1 *head,struct linklist1 *p)
/**删除a单链表中学号最大的结点（最大的结点用scan函数已经找出）**/
{
while(head->next && head->next!=p)
head=head->next;
head->next=p->next;
free(p);
}

outlist2(struct linklist2 *head,struct linklist2 *q)
/**删除b单链表中对应的结点**/
{
while(head->next && head->next!=q)
head=head->next;
head->next=q->next;
free(q);
}

output(struct conlink *head)
/**输出c链表**/
{
while(head->next!=0)
{
printf("%d %d\n",head->next->xh,head->next->grade);
head=head->next;
}
}

main()
{
struct linklist1 *a;
struct linklist2 *b;
struct linklist1 *p;
struct linklist2 *q;
struct conlink *head;
a=creat1();
b=creat2();
head=(struct conlink *)malloc(sizeof(struct conlink));
head->next=0;
while(a->next!=0)
{
scan(a,b,&p,&q);
conlink(head,p,q);
outlist1(a,p);
outlist2(b,q);
}
output(head);
getch();
}

Answer 2

while(a->next!=0)
a->next!=NULL
地址值肯定不会使用0这个地址……
p->next=0中，改成NULL

outlist1(struct linklist1 *head,struct linklist1 **p)
/**删除a单链表中学号最大的结点（最大的结点用scan函数已经找出）**/
{while(head->next!=(*p))
head=head->next;
head->next=(*p)->next;
}
最好加上一句 free （*p）;比较好

Answer 3

（问题1）struct linklist1 *creat1()
/**创建单链表a**/
{int i;
struct linklist1 *head,*p,*q;
p=q=(struct linklist1 *)malloc(sizeof(struct linklist1));
head=NULL;
for(i=0;i<5;i++)
{scanf("%d",&（p->xh)）;
if(i==0)head=p;
else q->next=p;
q=p;
p=(struct linklist1 *)malloc(sizeof(struct linklist1));
}
q->next=NULL; //结束标示
return head;
}
（问题2）注释应该时“/”，不是“\”;
（问题3）#include <stdlib.h>/*这个头文件时包含malloc函数和free函数*/
（问题4）有必要些那么多函数吗？不是一个linklist1对应一个linklist2，这样的话可以直接连接两个链表
完整代码：

#include <stdlib.h>
#include <stdio.h>

struct linklist1
{int xh;
struct linklist1 *next;
};
struct linklist2
{int grade;
struct linklist2 *next;
};
struct conlink
{int xh;
int grade;
struct conlink *next;
};

struct linklist1 *creat1()
/**创建单链表a**/
{int i;
struct linklist1 *head,*p,*q;
p=q=(struct linklist1 *)malloc(sizeof(struct linklist1));
head=NULL;
for(i=0;i<5;i++)
{
printf("%d ",i);
scanf("%d",&(p->xh));
if(i==0)head=p;
else q->next=p;
q=p;
p=(struct linklist1 *)malloc(sizeof(struct linklist1));
}
q->next=NULL;
return head;
free(p);free(q);free(head);
}
struct linklist2 *creat2()
/**创建单链表b**/
{int i;
struct linklist2 *head,*p,*q;
p=q=(struct linklist2 *)malloc(sizeof(struct linklist2));
head=NULL;
for(i=0;i<5;i++)
{printf("%d ",i);
scanf("%d",&(p->grade));
if(i==0)head=p;
else q->next=p;
q=p;
p=(struct linklist2 *)malloc(sizeof(struct linklist2));
}
q->next=NULL;
return head;
free(p);free(q);free(head);
}

struct conlink *link(struct linklist1 *a,struct linklist2 *b)
/**连接两个单链表**/
{
struct conlink *p,*q,*head;
int n=0;
head=NULL;
p=q=(struct conlink *)malloc(sizeof(struct conlink));

while (a!=NULL&&b!=NULL)
{
p->xh=a->xh;
p->grade=b->grade;
n++;
if (n==1) head=p;
else q->next=p;
q=p;
p=(struct conlink *)malloc(sizeof(struct conlink));
a=a->next;b=b->next;
}
q->next=NULL;
return head;
}

output(struct conlink *head)
/**输出c链表**/
{ struct conlink *p;
p=head;
if (head!=NULL)
{

do
{
printf("%d %d\n",p->xh,p->grade);

p=p->next;
} while(p!=NULL);
}
}

main()
{struct linklist1 *a;
struct linklist2 *b;

struct conlink *head;
a=creat1();
printf("\n\n\n");
b=creat2();

head=(struct conlink *)malloc(sizeof(struct conlink));
head=NULL;
head=link(a,b);
output(head);
free(a);free(b);free(head);
}

Answer 4

删除linklist1链表，没有必要那么麻烦啊 ，直接赋值为NULL就可以了