c语言中创建动态链表 浏览次数：1383次悬赏分：0 | 提问时间：2008-8-20 21:57 | 提问者：loucy8050544
#include<stdio.h>
#include<malloc.h>
#define NULL 0
#define LEN sizeof(struct student)
struct student
{
long num;
float score;
struct student *next;
};
int n;
struct student *creat()
{
struct student *head,*p1,*p2;
n=0;
p1=p2=(struct student *)malloc(LEN);
p1->next=p2->next=NULL;
printf("input the records:\n");
scanf("%ld,%f",&p1->num,&p1->score);
head=NULL;
while(p1->num!=0)
{
n=n+1;/*结点数增加一*/
if(n==1) head=p1;
else p2->next=p1;
p2=p1;
p1=(struct student *)malloc(LEN);
scanf("%ld,%f",&p1->num,&p1->score);
}
p2->next=NULL;
return(head);
}
void print(struct student *head)
{
struct student *p;
p=creat();
if(head!=NULL)
{
do
{
printf("%ld,%f\n",p->num,p->score);
p=p->next;
}while(p!=NULL);
}
}
void main()
{
struct student *head;
head=creat();
print(head);
}
这段程序无法在vc++中运行出结果，请高人指点
推荐答案 给你些资料吧~仔细看，看完就明白链表了
10.7 用指针处理链表
10.7.1链标概述
链表是一种常见的重要的数据结构.它是动态地进行存储分配的一种结构.我们知道，用数组存放数据时,
必须事先定义固定的长度(即元素个数).比如，有的班级有100人，而有的班只有30人，如果要用同一个数组先后存放不同班级的，则必须定义长度为100的数组.如果事先难以确定一个班的最多人数，则必须把数组定得足够大，以能存放任何班级的.显然这将会浪费内存.链表则没有这种缺点，它根据需要开辟内存单元.图10.11表示最简单的一种链表(单向链表)的结构.链表有一个"头指针"变量，图中以head表示，它存放一个地址.
该地址指向一个元素.链表中每一个元素称为"结点"，每个结点都应包括两个部分：一为用户需要用的实际数据，二为下一个结点的地址.课以看出,head指向第一个元素；第一个元素又指向第二个元素;……，直到最后一个元素，该元素不再指向其它元素，它称为'表尾"，它的地址部分放一个"NULL"(表示"空地址").链表到此结束.
可以看到：链表中各元素在内存中可以不是连续存放的.要某一元素，必须先到上一个元素，根据它提供的下一元素地址才能到下一个元素.
如果不提供"头指针"(head)，则整个链表都无法访问.链表如同一条铁链一样，一环扣一环，中间是不能断开的.打个通俗的比方：幼儿园的老师带领孩子出来散步，老师牵着第一个小孩的手，第一个小孩的另一只手牵着第二个孩子,……，这就是一个"链"，最后一个孩子有一只手空着，他是"链尾".要这个队伍，必须先到老师，然后顺序到每一个孩子.
可以看到，这种链表的数据结构，必须利用指
针变量才能实现
.即：一个结点中应包含一个指针变量，用它存放下一结点的地址.
前面介绍了结构体变量，它包含若干成员.这些成员可以是数值类型，字符类型，数组类型，也可以是指针类型.这个指针类型可以是指向其它结构体类型数据，也可以指向它所在的结构体类型.例如:
struct student
{int num;
float score;
struct student *next;
next是成员名，它是指针类型的，它指向struct student类型数据(这就是next所在的结构体类型).用这种方法可以建立链表.见图10.12.
其中每一个结点都属于struct student类型，它的成员next存放下一结点的地址，程序设计人员可以不必具体知道地址值,
只要保证将下一个结点的地址放到前一结点的成员next中即可.
请注意：上面只是定义了一个struct student类型，并未实际分配存储空间.前面讲过，链表结构是动态地分配存储的，即在需要时才开辟一个结点的存储单元.怎样动态地开辟和释放存储单元呢 C语言编译系统的库函数提供了以下有关函数.
1.malloc(size) 在内存的动态存储区中分配一个长度为size的连续空间.
此函数的值(即"返回值")是一个指针，它的值是该分配域的起始地址.如果此函数未能成功地执行，则返回值为0.
2.calloc(n,size) 在内存的动态区存储中分配n个长度为size的连续空间.函数返回分配域的起始地址；如果分配不成功，返回0.
3.free(ptr) 释放由ptr指向的内存区.ptr是最近一次调用ca11或ma11oc函数时返回的值.
上面三个函数中，参数n和size为整型,ptr为字符型指针.
请注意：许多C版本提供的malloc和call0c函数得到的是指向字符型数据的指针.新标准C提供的ma110c和ca11oc函数规定为void*类型.
有了本节所介绍的初步知识，下面就可以对链表进行操作了(包括建立链表，插入或删除链表中一个结点等).有些概念需要在后面的应用中逐步建立和掌握.
10.7.2建立链表
所谓建立链表是指从无到有地建立起一个链表，即一个一个地输入各结点数据，并建立起前后相链的关系.下面通过一个例子来说明如何建立一个链表.
[例10.7]写一函数建立一个有5名的单向链表.
先考虑实现此要求的算法(见图10. 13).
设三个指针变量:head,p1,p2，它们都指向结构体类型数据.先用mal1oc函数开辟一个结点，并使p1,p2指向它.
然后从键盘读人一个学生的数据给pl所指的结点.我们约定学号不会为零，如果输入的学号为0，则表示建立链表的过程完成，该结点不应连接到链表中.先使head的值为NULL(即等于0)，这是链表为"空"时的情况(即head不指向任何结点，链表中无结点)，以后增加一个结点就使head指向该结点.
如果输入的pl一>num不等于0，而且输入的是第一个结点数据(n=1)时，则令head=p1,
即把p1的
值赋给head，也就是使head也指向新开辟的结点(图10.14).P1所指向的新开辟的结点就成为链表中第一个结点.然后再开辟另一个结点并使p1指向它，接着读入该结点的数据(见图10.15(a)).如果输入的p1->num!=0，则应链入第2个结点(n=2)，由于n!=1，则将p1的值赋给p2-->next，也就是使第一个结点的next成员指向第二个结点(见图10.15(b)).接着使p2=p1,
也就是使p2指向刚才建立的结点，见图10.15(c).再开辟一个结点并使pl指向它，并读入该结点的数据(见图10.16(a))，在第三次循环中，由于n=3(n!=1)，又将pl的值赋给p2一>next，也就是将第3个结点连接到第2个结点之后，并使p2=p1，使p2指向最后一个结点(见图10.16(b).
再开辟一个新结点，并使pl指向它,
输入该结点的数据(见图10.17(a)).由于pl一>num的值为0，不再执行循环，此新结点不应被连接到链表
中.此时将NULL赋给p2一>next，见图10.17(b).建立链表过程至此结束,pl最后所指的结点未链入链表中，第3个结点的next成员的值为NULL，它不指向任何结点.虽然pl指向新开辟的结点，但从链表中无法到该结点.
建立链表的函数可以如下:
#define NULL 0
#define LEN sizeof(struct student)
struct student molloc函数
{1ong num;
float score;
struct student *next;
};
int n;
struct student *creat()
/*此函数带回一个指向链表头的指针*/
{struct student *head;
struct student *p1, *p2;
n=0;
p1=p2=(struct student*)mal1oc(LEN);/*开辟一个新单元*/
scanf("%ld,%f",&pl一>num,&pl一>score);
head=NULL:
while (pl一>num!=0)
{n=n十1;
if(n==1) head=pl;
else p2一>next=p1;
p2=pl;
pl=(struct student*)malloc(LEN);
scanf("%1d,%f",&p1-->num,&pl一>score);
}
p2一>next=NULL;
return(head);
}
请注意:
(1)第一行为#define命令行，令NULL代表0，用它表示"空地址".第二行令LEN代表struct student结构体类型数据的长度,
sizeof是"求字节数运算符".
(2)第9行定义一个creat函数，它是指针类型，即此函数带回一个指针值，它指向一个struct student类型数据.实际上此creat函数带回一个链(3)malloc(LEN)的作用是开辟一个长度为LEN的内存区,LEN已定义为sizeof(struct student)，即结构体struct student的长度.在一般系统中,malloc带回的是指向字符型数据的指针.
而p1,p2是指向struct student类型数据的指针变量，二者所指的是不同类型的数据，这是不行的.因此必须用强制类型转换的方法使之类型一致，在malloc (LEN)之前加了"(struct student*)"，它的作用是使malloc返回的指针转换为指向struct student类型数据的指针.注意"*"号不可省略，否则变成转换成struct student类型了，而不是指针类型了.
(4)最后一行return后面的参数是head(head已定义为指针变量，指向struct student类型数据).因此函数返回的是head的值，也就是链表的头地址.
(5)n是结点个数.
(6)这个算法的思
路是：让pl指向新开的结点,p2指向链表中最后一个结点，把pl所指的结点连接在p2所指的结点后面，用"p2一>next=pl"来实现.
我们对建立链表过程作了比较详细的介绍,
读者如果对建立链表的过程比较清楚的话，对下面介绍的删除和插入过程也就比较容易理解了.
10.7.3输出链麦
将链表中各结点的数据依次输出.这个问题比较容易处理.首先要知道链表头元素的地址，也就是要知道head的值.然后设一个指针变量p，先指向第一个结点，输出p所指的结点，然后使p后移一个结点，再输出.直到链表的尾结点.
「例10.8]写出输出链表的函数print.
void print(head)
struct student *head;
{struct student *p;
printf("\nNow,These%drecords are:\n",n);
p=head;
if(head!=NULL)
do
{printf("%ld%5.1f\",p一>num,p—>score);
p=p一>next;
}while(p!=NULL);
算法可用图10.18表示.
其过程可用图10.19表示.p先指向第一结点，在输出完第一个结点之后,p移到图中p'虚线位置，指向第二个结点.程序中p=p一>next的作用是：将p原来所指向的结点中next的值赋给p,
而p一>next的值就是第二个结点的起始地址.将它赋给p就是使p指向第二个结点.
head的值由实参传过来，也就是将已有的链表的头指针传给被调用的函数，在print函数中从head所指的第一个结点出发顺序输出各个结点.
10.7.4 对链麦的删除操作
已有一个链表，希望删除其中某个结点.怎样考虑此问题的算法呢，先打个比方:
一队小孩(A.B.C.D.E)手拉手，如果某一小孩(C)想离队有事，而队形仍保持不变.只要将C的手从两边脱开,B改为与D拉手即可，见图10.20.图10.20(a)是原来的队伍，图10.20(b)是c离队后的队伍.
与此相仿，从一个链表中删去一个结点，并不是真正从内存中把它抹掉，而是把它从链表中分离开来，即改变链接关系即可.
[例10.9]写一函数以删除指定的结点.
我们以指定的学号作为删除结点的标志.例如，输入89103表示要求删除学号为89103的结点.解题的思路是这样的：从p指向的第一个结点开始，检查该结点中的num值是否等于输入的要求删除的那个学号.如果相等就将该结点删除，如不相等，就将p后移一个结点，再如此?下去，直到遇到表尾为止.
可以设两个指针变量pl和p2，先使pl指向第一个结点(图10.21(a)).如果要删除的不是第一个结点,
则使pl后指向下一个结点(将pl一>next赋给pl)，在此之前应将pl的值赋给p2，使p2指向刚才检查过的那个结点，见图10.21(b).如此一次一次地使p后移，直到到所要删除的结点或检查完全部链表都不到要删除的结点为止.如果到某一结点是要删除的结点，还要区分两种情况:①要删的是第一个结点(pl的值等于head的值，如图10.21(a)那样)，则应将pl一>next赋给head.见图10.21(c).
这时head指向原来第
二个结点.第一个结点虽然仍存在，但它已与链表脱离，因为链表中没有一个元素或头指针指向它.虽然p1还指向它，它仍指向第二个结点，但仍无济于事，现在链表的第一个结点是原来第二个结点，原来第一个结点"丢失".②如果要删除的不是第一个结点，则将pl一>next赋给p2一>next，见图10.21(d).p2一>next原来指向pl指向的结点(图中第二个结点)，现在p2一>next改为指向p1一>next所指向的结点
(图中第三个结点).pl所指向的结点不再是链表的一部分.
还需要考虑链表是空表(无结点)和链表中不到要删除的结点的情况.
图10.22表示解此题的算法.
删除结点的函数del如下:
struct student *del(head,num)
struct student *head;
1ong num;
{struct student *p1,*p2;
if(head==NULL) {printf("\nlist null!\n");goto end;}
p1=head;
whi1e (num!=pl一>num&&pl一>next!一NULL)/*pl指向的不是所要的结点，并且后面还有结点点*/
{p2=p1;pl=pl一>next;}/*后移一个结点*/
if (num==pl一>num) /*到了*/
{if (n1==head) head=pl一>next;/*若pl指向的是头结点，把第二个结点地址赋予head*/
e1se p2一>next=pl一>next;/*否则将下一结点地址赋给前一结点地址*\
printf("delete:%ld\n",num);
n=n-1;
}
else printf("%ld not been found!\n",num);/*不到该结点*/
end:
return(head);
}
函数的类型是指向struct student类型数据的指针,
它的值是链表的头指针.函数参数为head和要删除的学号num.head的值可能在函数执行过程中被改变(当删除第一个结点时).
10.7.5对链表的插入操作
将一个结点插入到一个已有的链表中.设已有的链表中各结点中的成员项num(学号)是按学号由小到大顺序排列的.
用指针变量p0指向待插入的结点,pl指向第一个结点.见图10.23(a).
将p0一>num与pl一>num相比较，如果p0一>num>pl一>num，则待插入的结点不应插在pl所指的结点
之前.此时将pl后移，并使p2指向刚才pl所指的结点，见图10.23(b).再将p1一>num与p0一>num比.如果仍然是p0一>num大，则应使pl继续后移，直到p0一>numnum为止.这时将p0所指的结点插到pl所指结点之前.但是如果p1所指的已是表尾结点，则pl就不应后移了.如果p0一>num比所有结点的num都大,
则应将p0所指的结点插到链表末尾.
如果插入的位置既不在第一个结点之前，又不在表尾结点之后，则将p0的值赋给p2一>next，即使p2一>next指向待插入的结点，然后将pl的值赋给p0->next，即使得p0一>next指向pl指向的变量.见图10.23(c).可以看到，在第一个结点和第二个结点之间已插入了一个新的结点.
如果插入位置为第一结点之前(即pl等于head时),
则将p0赋给head，将p1赋给p0->next.见图10.23(d).如果要插到表尾之后，应将p0赋给pl一>next,NULL赋给p0一>next，见图10.23(e).
以上算法可用图10.24表示.
[例10. 10]插入结点的
函数insert如下.
struct student *insert(head,stud)
struct student *head,*stud:
{struct student *p0,*p1,*p2;
pl=head;/*使pl指向第一个结点*/
p0=stud;/*p0指向要插入的结点*/
if (head==NULL)/*原来是空表*/
{head=p0;p0一>next=NULL;}/*使p0指向的结点作为第一个结点*/
else
{while ((p0一>num>pl一>num)&&(pl一>next!=NULL))
{p2=p1;p1=pl一>next;}/*p2指向刚才pl指向的结点,p1后移一个结点*/
if(p0->numnext=p0;/*插到p2指向的结点之后*/
p0—>next=p1;}
else
{pl一>next=p0;p0一>next=NULL;}}/*插到最后的结点之后*/
n=n+1; /*结点数加1*/
return(head);
}
函数参数是head和stud.stud也是一个指针变量，从实参传来待插入结点的地址给stud.语句p0=stud的作用是使p0指向待插入的结点.
函数类型是指针类型，函数值是链表起始地址head.
将以上建立，输出，删除，插入的函数组织在一个程序中，用main函数作主调函数.可以写出以下main函数.
main()
{struct student *head,stu;
1ong de1_num;
printf("input records:\n");
head=creat(); /*返回头指针*/
print(head); /*输出全部结点*/
printf("\ninput the deleted 0number:");
scanf("%ld",&de1_mum);/*输入要删除的学号*/
head=del(head,de1_num);/*删除后的头地址*/
print(head); /*输出全部结点*/
prinif("/ninput the inserted record:")/*输入要插入的记录*/
scanf("%ld,%f",&stu.num,&stu.score);
head=insert(head,&stu);/*返回地址*/
print(head);
}
此程序运行结果是正确的.
它只删除一个结点，插入一个结点.但如果想再插入一个结点，重复写上程序最后四行，即共插入两个结点.运行结果却是错误的.
input records:(建立链表)
89101,90
89103,98
89105,76
0,0
Now,These 3 records are:
89101 90.0
89103 98.0
89105 76.0
inpu the deleted number:
89103 (删除)
delete:89103
Now,These 2 records are:
89101 90.0 89105 76.0
input the inserted record:89102
90 (插入第一个结点)
Now,These 3 records are:
89101 90.0
89102 90.0
89105 76.0
input the inserted record:89104,99/(插入第二个结点)
Now,The 4 records are:
89101 90.0
89104 99.0
89104 99.0
89104 99.0
...
...
(无终止地输出89104的结点数据)
请读者将main与insert函数结合起来考察为什么会产生以上运行结果.
出现以上结果的原因是:stu是一个有固定地址的变量.第一次把stu结点插入到链表中.第二次若再用它来插入第二个结点，就把第一次结点的数据冲掉了.
实际上并没有开辟两个结点.读者可根据insert函数画出此时链表的情况.为了解决这个问题，必须在每插入一个结点时新开辟一个内存区.我们修改main函数，使之能删除多个结点(直到输入要删的学号为0)，能插入多个结点(直到输入要插入的学号为0).
main函数如下:
main()
{struct student *head,*stu;
1ong de1_num;
printf("input records:/n");
head=

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。