c语言链表.docx
《c语言链表.docx》由会员分享，可在线阅读，更多相关《c语言链表.docx（12页珍藏版）》请在冰点文库上搜索。
c语言链表
#include＜stdio.h＞
#include＜malloc.h＞/*包含动态内存分配函数的头文件*/
#defineN10/*N为人数*/
typedefstructnode
{
charname[20].
structnode*link.
}stud.
stud*creat（intn）/*建立单链表的函数，形参n为人数*/
{
stud*p,*h,*s./**h保存表头结点的指针，*p指向当前结点的前一个结点，*s指向当前结点*/
inti./*计数器*/
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个人的姓名",i1）.
scanf（"%s",s-＞name）./*在当前结点s的数据域中存储姓名*/
s-＞link=NULL.
p=s.
}
return（h）.
}
main（）
{
intnumber./*保存人数的变量*/
stud*head./*head是保存单链表的表头结点地址的指针*/
number=N.
head=creat（number）./*把所新建的单链表表头地址赋给head*/
}
假设在一个单链表中存在2个连续结点p、q（其中p为q的直接前驱），若我们需要在p、q之间插入一个新结点s，那么我们必须先为s分配空间并赋值，然后使p的链域存储s的地址，s的链域存储q的地址即可。
（p-＞link=s;s-＞link=q），这样就完成了插入操作。
下例是应用插入算法的一个例子：
#include＜stdio.h＞
#include＜malloc.h＞
#include＜string.h＞
#defineN10
typedefstructnode
{
charname[20];
structnode*link;
}stud;
stud*creat（intn）/*建立单链表的函数*/
{
stud*p,*h,*s;
inti;
if（（h=（stud*）malloc（sizeof（stud）））==NULL）
{
printf（"不能分配内存空间!
"）;
exit（0）;
}
h-＞name[0]='\0';
h-＞link=NULL;
p=h;
for（i=0;i＜n;i++）
{
if（（s=（stud*）malloc（sizeof（stud）））==NULL）
{
printf（"不能分配内存空间!
"）;
exit（0）;
}
p-＞link=s;
printf（"请输入第%d个人的姓名:
",i+1）;
scanf（"%s",s-＞name）;
s-＞link=NULL;
p=s;
}
return（h）;
}
stud*search（stud*h,char*x）/*查找函数*/
{
stud*p;
char*y;
p=h-＞link;
while（p!
=NULL）
{
y=p-＞name;
if（strcmp（y,x）==0）
return（p）;
elsep=p-＞link;
}
if（p==NULL）
printf（"没有查找到该数据!
"）;
}
voidinsert（stud*p）/*插入函数，在指针p后插入*/
{
charstuname[20];
stud*s;/*指针s是保存新结点地址的*/
if（（s=（stud*）malloc（sizeof（stud）））==NULL）
{
printf（"不能分配内存空间!
"）;
exit（0）;
}
printf（"请输入你要插入的人的姓名:
"）;
scanf（"%s",stuname）;
strcpy（s-＞name,stuname）;/*把指针stuname所指向的数组元素拷贝给新结点的数据域*/
s-＞link=p-＞link;/*把新结点的链域指向原来p结点的后继结点*/
p-＞link=s;/*p结点的链域指向新结点*/
}
main（）
{
intnumber;
charfullname[20];/*保存输入的要查找的人的姓名*/
stud*head,*searchpoint;
number=N;
head=creat（number）;/*建立新链表并返回表头指针*/
printf（"请输入你要查找的人的姓名:
"）;
scanf（"%s",fullname）;
searchpoint=search（head,fullname）;/*查找并返回查找到的结点指针*/
insert（searchpoint）;/*调用插入函数*/
}
//链表操作:
建立、插入、删除、查找、倒置、删除等基本操作
//喜洋洋制作
#include
#include
typedefstructLNode
{
intdata;
structLNode*next;
}LNode,*Llist;
LNode*creat_head（）;//创建一个空表
voidcreat_list（LNode*,int）;//创建一个长度为n的线性链表
voidinsert_list（LNode*,int,int）;//插入一个元素
intdelete_list（LNode*,int）;//删除一个元素
intfound_list（LNode*,int）;//链表查询
voidreverse（LNode*）;//倒置整个链表
voiddelete_whole（LNode*）;//删除整个链表
voidprint_list（LNode*）;//打印链表
main（）
{
LNode*head;
intn,n2;
intx,i;
intb;
chartemp1,temp2;
head=creat_head（）;
printf（"请输入链表的节点个数n="）;
scanf（"%d",&n）;
printf（"\n请输入数据：
\n"）;
creat_list（head,n）;//创建链表
print_list（head）;
printf（"\n*********************************************************\n"）;
printf（"\n下面进行链表插入元素\n"）;
printf（"\n请输入您需要插入的元素x="）;
scanf（"%d",&x）;
printf（"\n请输入即将插入的位置i="）;
scanf（"%d",&i）;
insert_list（head,x,i）;//插入元素
print_list（head）;
printf（"\n*********************************************************\n"）;
printf（"\n下面进行链表删除元素\n"）;
printf（"\n请输入即将删除元素的位置：
i="）;
scanf（"%d",&i）;
b=delete_list（head,i）;//删除元素
print_list（head）;
printf（"\n\n成功删除元素：
%d",b）;
printf（"\n*********************************************************\n"）;
printf（"\n下面进行链表查询\n"）;
printf（"\n请输入即将查询的元素：
x="）;
scanf（"%d",&n2）;
if（found_list（head,n2）>0）//链表查询
printf（"找到了，在第%d的位置上",found_list（head,n2））;
else
printf（"没有找到!
"）;
printf（"\n*********************************************************\n"）;
printf（"\n是否倒置整个链表？
Y/N\n"）;
fflush（stdin）;
scanf（"%c",&temp1）;
if（'Y'==temp1）//倒置链表
{
reverse（head）;
print_list（head）;
}
printf（"\n*********************************************************\n"）;
printf（"\n是否删除整个链表？
Y/N\n"）;
fflush（stdin）;
scanf（"%c",&temp2）;
if（'Y'==temp2）//删除链表
{
delete_whole（head）;
printf（"\n成功删除整个链表\n"）;
}
}
//创建一个空链表
LNode*creat_head（）
{
LNode*p;
p=（Llist）malloc（sizeof（LNode））;
if（NULL==p）
printf（"内存申请失败！
"）;
else
{
p->next=NULL;
return（p）;
}
}
//创建一个长度为n的线性链表
voidcreat_list（LNode*head,intn）
{
LNode*p,*q;
inti;
p=head;
for（i=1;i<=n;i++）
{
q=（Llist）malloc（sizeof（LNode））;
if（NULL==p）
printf（"内存申请失败！
"）;
else
{
printf（"data:
"）;scanf（"%d",&q->data）;
q->next=NULL;
p->next=q;
p=q;
}
}
}
//插入一个元素
voidinsert_list（LNode*head,intx,inti）
{
intj=0;
LNode*p,*s;
p=head;
while（（p!
=NULL）&&（j{
p=p->next;
j++;
}
if（p==NULL）exit（0）;
s=（Llist）malloc（sizeof（LNode））;
if（NULL==p）
printf（"内存申请失败！
"）;
else
{
s->data=x;
s->next=p->next;
p->next=s;
}
}
//删除一个元素
intdelete_list（LNode*head,inti）
{
LNode*p,*q;
intj=0;
intx;
p=head;
while（（p!
=NULL）&&（j{
p=p->next;
j++;
}
if（p==NULL）exit（0）;
q=p->next;
p->next=q->next;
x=q->data;
free（q）;
q=NULL;
return（x）;
}
//删除整个链表
voiddelete_whole（LNode*head）
{
LNode*p,*q;
p=head;
while（p!
=NULL）
{
q=p->next;
free（p）;
p=q;
}
}
//倒置链表
voidreverse（LNode*head）
{
LNode*p,*s,*t;
p=head;
s=p->next;
while（s->next!
=NULL）//主要置换过程
{
t=s->next;
s->next=p;
p=s;
s=t;
}
s->next=p;
head->next->next=NULL;//收尾
head->next=s;//赋头
}
//打印链表
voidprint_list（LNode*head）
{
LNode*p;
for（p=head->next;p!
=NULL;）
{
printf（"%d",p->data）;
p=p->next;
}
}
//链表查询
intfound_list（LNode*head,intn）
{
LNode*p;
inti=1;
for（p=head->next;p!
=NULL;）
{
if（n==p->data）
{
returni;
}
i++;
p=p->next;
}
if（NULL==p）
return0;
}
升级会员 