c语言中创建动态链表 浏览次数：1383次悬赏分：0 | 提问时间：2008-8-20 21:57 | 提问者：loucy8050544
#include
#include
#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
{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=
creat();
print (head);
printf("/ninput the deleted number:");
scanf("%1d",&del_num);
while (de1_num!=0)
{head=del(head,del_num);
print(head);
printf("input the deleted number:");
scanf("%ld",&del_num);
printf("\ninput the inserted record:");
stu=(struct student*)malloc(LEN);
scanf("%1d,%f,",&stu一>num,&stu一>scor);
while (stu一>num!=0)
{head=insert(head,stu):
print(head);
prinif("input the inserted record:");
stu=(struct student*)malloc(LEN);
scanf("%1d,%f,&stu一>num,&stu一>score);
}
}
sum定义为指针变量,在需要插入时先用malloc函数开辟一个内存区,将其起始地址经强制类型转换后赋给stu,然后输入此结构体变量中各成员的值.对不同的插入对象,stu的值是不同的,每次指向一个新的结构体变量.在调用insert函数时,实参为head和stu,将已建立的链表起始地址传给insert函数的形参,将stu(既新开辟的单元的地址)传给形参stud,函数值返回经过插入之后的链表的头指针(地址).
运行情况如下:
input records:
89101,99
89103,87
89105,77
0,0
Now, These 3 records are.
89101 99.0
89103 87.0
89105 77.0
input the deleted number:89103
delete:89103
Now,These 2 records are:
89101 99.0
89105 77.0
input the de1eted number:89105
delete:89105
Now,These l records are:
89101 99.0
input the de1eted number:0
1nput the inserted record:89104,87
NOw,These 2 records are:
89101 99.0
89104 87.0
input the inserted record:89106,65
Now,These 3 records are:
89101 99.0
89104 87.0
89106 65.0
input the inserted record:0,0
对这个程序请读者仔细消化.
指针的应用领域很宽广,除了单向链表之外,还有环形链表,双向链表.此外还有队列,树,栈,图等数据结构.
有关这些问题的算法可以学习《数据结构>>课程,在此不作详述.
链表的C语言实现之单链表的实现
2005-05-01 10:38作者：leton2008出处：blog责任编辑：方舟
一、单链表的建立
有了动态内存分配的基础，要实现链表就不难了。
所谓链表，就是用一组任意的存储单元存储线性表元素的一种数据结构。链表又分为单链表、双向链表和循环链表等。我们先讲讲单链表。所谓单链表，是指数据接点是单向排列的。一个单链表结点，其结构类型分为两部分：
1、数据域：用来存储本身数据
2、链域或称为指针域：用来存储下一个结点地址或者说指向其直接后继的指针。
例：
typedef struct node
{
char name[20];
struct node *link;
}stud;
这样就定义了一个单链表的结构，其中char name[20]是一个用来存储姓名的字符型数组，指针*link是一个用来存储其直接后继的指针。
定义好了链表的结构之后，只要在程序运行的时候爱数据域中存储适
当的数据，如有后继结点，则把链域指向其直接后继，若没有，则置为NULL。
下面就来看一个建立带表头（若未说明，以下所指链表均带表头）的单链表的完整程序。
#include ＜stdio.h＞
#include ＜malloc.h＞ /*包含动态内存分配函数的头文件*/
#define N 10 /*N为人数*/
typedef struct node
{
char name[20];
struct node *link;
}stud;
stud * creat(int n) /*建立单链表的函数，形参n为人数*/
{
stud *p,*h,*s; /* *h保存表头结点的指针，*p指向当前结点的前一个结点，*s指向当前结点*/
int i; /*计数器*/
if((h=(stud *)malloc(sizeof(stud)))==NULL) /*分配空间并检测*/
{
printf("不能分配内存空间!");
exit(0);
}
h-＞name[0]='\0'; /*把表头结点的数据域置空*/
h-＞link=NULL; /*把表头结点的链域置空*/
p=h; /*p指向表头结点*/
for(i=0;i＜n;i++)
{
if((s= (stud *) malloc(sizeof(stud)))==NULL) /*分配新存储空间并检测*/
{
printf("不能分配内存空间!");
exit(0);
}
p-＞link=s; /*把s的地址赋给p所指向的结点的链域，这样就把p和s所指向的结点连接起来了*/
printf("请输入第%d个人的姓名",i+1);
scanf("%s",s-＞name); /*在当前结点s的数据域中存储姓名*/
s-＞link=NULL;
p=s;
}
return(h);
}
main()
{
int number; /*保存人数的变量*/
stud *head; /*head是保存单链表的表头结点地址的指针*/
number=N;
head=creat(number); /*把所新建的单链表表头地址赋给head*/
}
这样就写好了一个可以建立包含N个人姓名的单链表了。写动态内存分配的程序应注意，请尽量对分配是否成功进行检测。
、循环链表
循环链表是与单链表一样，是一种链式的存储结构，所不同的是，循环链表的最后一个结点的指针是指向该循环链表的第一个结点或者表头结点，从而构成一个环形的链。
循环链表的运算与单链表的运算基本一致。所不同的有以下几点：
1、在建立一个循环链表时，必须使其最后一个结点的指针指向表头结点，而不是象单链表那样置为NULL。此种情况还使用于在最后一个结点后插入一个新的结点。
2、在判断是否到表尾时，是判断该结点链域的值是否是表头结点，当链域值等于表头指针时，说明已到表尾。而非象单链表那样判断链域值是否为NULL。
二、双向链表
双向链表其实是单链表的改进。
当我们对单链表进行操作时，有时你要对某个结点的直接前驱进行操作时，又必须从表头开始查找。这是由单链表结点的结构所限制的。因为单链表每个结点只有一个存储直接后继结点地址的链
域，那么能不能定义一个既有存储直接后继结点地址的链域，又有存储直接前驱结点地址的链域的这样一个双链域结点结构呢？这就是双向链表。
在双向链表中，结点除含有数据域外，还有两个链域，一个存储直接后继结点地址，一般称之为右链域；一个存储直接前驱结点地址，一般称之为左链域。在c语言中双向链表结点类型可以定义为：
typedef struct node
{
int data; /*数据域*/
struct node *llink,*rlink; /*链域，*llink是左链域指针，*rlink是右链域指针*/
}JD;
当然，也可以把一个双向链表构建成一个双向循环链表。
双向链表与单向链表一样，也有三种基本运算：查找、插入和删除。
双向链表的基本运算：
1、查找
假若我们要在一个带表头的双向循环链表中查找数据域为一特定值的某个结点时，我们同样从表头结点往后依次比较各结点数据域的值，若正是该特定值，则返回指向结点的指针，否则继续往后查，直到表尾。
下例就是应用双向循环链表查找算法的一个程序。
#include ＜stdio.h＞
#include ＜malloc.h＞
#define N 10
typedef struct node
{
char name[20];
struct node *llink,*rlink;
}stud;
stud * creat(int n)
{
stud *p,*h,*s;
int i;
if((h=(stud *)malloc(sizeof(stud)))==NULL)
{
printf("不能分配内存空间!");
exit(0);
}
h-＞name[0]=’\0’;
h-＞llink=NULL;
h-＞rlink=NULL;
p=h;
for(i=0;i＜n;i++)
{
if((s= (stud *) malloc(sizeof(stud)))==NULL)
{
printf("不能分配内存空间!");
exit(0);
}
p-＞rlink=s;
printf("请输入第%d个人的姓名",i+1);
scanf("%s",s-＞name);
s-＞llink=p;
s-＞rlink=NULL;
p=s;
}
h-＞llink=s;
p-＞rlink=h;
return(h);
}
stud * search(stud *h,char *x)
{
stud *p;
char *y;
p=h-＞rlink;
while(p!=h)
{
y=p-＞name;
if(strcmp(y,x)==0)
return(p);
else p=p-＞rlink;
}
printf("没有查找到该数据!");
}
void print(stud *h)
{
int n;
stud *p;
p=h-＞rlink;
printf("数据信息为：\n");
while(p!=h)
{
printf("%s ",&*(p-＞name));
p=p-＞rlink;
}
printf("\n");
}
main()
{
int number;
char studname[20];
stud *head,*searchpoint;
number=N;
clrscr();
head=creat(number);
print(head);
printf("请输入你要查找的人的姓名:");
scanf("%s",studname);
searchpoint=search(head,studname);
printf("你所要查找的人的姓名是:%s",*&searchpoint-＞name);
}
各种排序发的适合区域
二分查找法、哈希查找法、二叉排序树查找法等各种查找算法。1. 线性表上的查找： 主要分为三种线性结构
：顺序表，有序顺序表，索引顺序表。对于第一种，我们采用传统查找方法，逐个比较。对于及有序顺序表我们采用二分查找法。对于第三种索引结构，我们采用索引查找算法。其中，二分查找还要特别注意适用条件以及其递归实现方法。 2.树表上的查找： 树表主要分为以下几种：二叉排序树，平衡二叉树，B树，键树。由于二叉排序树与平衡二叉树是一种特殊的二叉树，所以与二叉树的联系就更为紧密。 二叉排序树，它的中序遍历结果是一个递增的有序序列。平衡二叉树是二叉排序树的优化，其本质也是一种二叉排序树，只不过，平衡二叉树对左右子树的深度有了限定。 B树是二叉排序树的进一步改进，也可以把B树理解为三叉、四叉....排序树。因为这两种算法涉及到B树结点的分裂和合并，是一个难点。键树也称字符树，特别适用于查找英文单词的场合。一般不要求能完整描述算法源码，多是根据算法思想建立键树及描述其大致查找过程。 3.基本哈希表的查找算法： 哈希表查找的基本思想是：根据当前待查找数据的特征，以记录关键字为自变量，设计一个function，该函数对关键字进行转换后，其解释结果为待查的地址。堆排序属于选择排序类型的排序，是一树形选择排序。堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify实现的。 堆排序的最坏时间复杂度为O(nlgn)。堆排序的平均性能较接近于最坏性能。 由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。 堆排序是就地排序，辅助空间为O(1)， 它是不稳定的排序方法。堆排序，是利用堆这种数据结构的性质，通过堆元素的删除、调整等一系列操作将最小数选出放在堆顶。堆排序的特点是：在排序过程中，将R[l..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系【参见二叉树的顺序存储结构】，在当前无序区中选择关键字最大(或最小)的记录。堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征，使得在当前无序区中选取最大(或最小)关键字的记录变得简单。