链表.docx
《链表.docx》由会员分享,可在线阅读,更多相关《链表.docx(20页珍藏版)》请在冰点文库上搜索。
链表
头文件:
#include
#include
#include/*malloc()等*/
#include/*INT_MAX等*/
#include/*EOF(=^Z或F6),NULL*/
#include/*atoi()*/
#include/*eof()*/
#include/*floor(),ceil(),abs()*/
#include/*exit()*/
1.顺序存储的线性表(相当于数组):
物理上相邻的随机存取的存储结构
实现代码:
#defineLIST_INIT_SIZE100
#defineLISTNEW100
typedefintElemType;//定义数据类型
typedefintStatus;
typedefstruct
{
ElemType*elem;//存储空间基址
intlength;//当前长度
intlistsize;//当前分配存储容量(sizeof(ElemType))
}Sqlist;
/*********************************************************************************************
*函数名称:
StatusInitList(Sqlist*L)
*功能描述:
初始化顺序存储的线性链表
*参数说明:
L线性表
*
*返回值:
Status值,运行成功标志
*********************************************************************************************/
StatusInitList(Sqlist*L)
{
(*L).elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if((*L).elem==NULL)//存储分配失败
{
printf("OverFlow\n");
exit(0);
}
(*L).length=0;//空表长为0
(*L).listsize=LIST_INIT_SIZE;//初始存储容量
printf("初始化成功\n");
return1;
}
/*********************************************************************************************
*函数名称:
StatusListInsert(Sqlist*L,inti,ElemTypee)
*功能描述:
顺序存储线性链表插入一个值
*参数说明:
L线性表
*i插入位置
*e插入元素
*返回值:
Status值,运行成功标志
*********************************************************************************************/
StatusListInsert(Sqlist*L,inti,ElemTypee)
{
if(i<1||i>(*L).length+1)//i值不合法
{
printf("i值不合法");
return0;
}
if((*L).length>=(*L).listsize)//当前存储空间已满,增加空间
{
ElemType*Newbase=(ElemType*)realloc((*L).elem,((*L).listsize+LISTNEW)*sizeof(ElemType));
if((*Newbase)==NULL)//分配失败
{
printf("EROR\n");
exit(0);
}
(*L).elem=Newbase;//新基址
(*L).listsize+=LISTNEW;//增加存储容量
}
intj=(*L).length+1;
for(;j>=i;j--)
{
(*L).elem[j]=(*L).elem[j-1];
}
(*L).elem[j]=e;
++(*L).length;
return1;
}
/*********************************************************************************************
*函数名称:
voidPrintList(SqlistL)
*功能描述:
顺序存储线性链表输出
*参数说明:
L线性表
*返回值:
无
*********************************************************************************************/
voidPrintList(SqlistL)
{
if(L.length>0)
{
for(inti=0;iprintf("%d\n",L.elem[i]);
}
}
voidmain()
{
SqlistL;
InitList(&L);
ListInsert(&L,1,1);
ListInsert(&L,1,2);
PrintList(L);
}
2.线性链表(单链表)
不可随机存取。
可以用任意的存储单元存储线性表的数据元素。
整个链表的存取需从头指针开始。
单链表可由头指针唯一确定。
初始化链表时,表头的指针域为空,此后空指针指向链表的末尾,作为判断链表结束的标志。
数据结构体(指针)分配内存后加一个判断if(!
L),确保分配到内存。
/*函数结果状态代码*/
#defineN5/*链表长度*/
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineINFEASIBLE-1
typedefintStatus;/*Status是函数的类型,其值是函数结果状态代码,如OK等*/
typedefintBoolean;/*Boolean是布尔类型,其值是TRUE或FALSE*/
typedefintElemType;/*元素类型*/
/*线性表的单链表存储结构*/
typedefstructLNode
{
ElemTypedata;
structLNode*next;
}LNode,*LinkList;
/*函数定义*/
StatusInitList(LinkList*Head);//初始化单链表
StatusListInsert(LinkListL,inti,ElemTypee);//在位置i插入元素e
StatusListPrint(LinkListL);//输出链表
StatusDesdroyList(LinkList*L);//销毁链表
StatusClearList(LinkListL);//使链表为空
StatusGetElem(LinkListL,inti,ElemType*e);//查找元素
intListLength(LinkListL);//计算链表长
StatusPrioElem(LinkListL,ElemTypecurrent,ElemType*Prio);//查找一个元素的前继
StatusListDelet(LinkListL,inti,ElemType*e);//在带头结点的单链线性表L中,删除第i个元素,并由e返回其值
voidRandCreateList(LinkList*L,intn);//采用随机数法创建一个链表
StatusListReseve(LinkList*L);//链表反序
StatusGetNthNodeFromBack(LinkListL,intn,ElemType*e);//查找单链表倒数第n个元素
intmain(void)
{
LinkListL;
ElemTypee=0,Prio,k;
inti=0,j=0;
RandCreateList(&L,10);//随机数生成链表
ListPrint(L);//输出链表
i=InitList(&L);//初始化空表
for(i=0;i{
scanf("%d",&e);
j=ListInsert(L,1,e);//插入元素
}
printf("OK\n");
ListPrint(L);//输出表
ListReseve(&L);//反转链表
ListPrint(L);//输出表
PrioElem(L,2,&Prio);//查找前继
printf("Prio=%d\n",Prio);
GetNthNodeFromBack(L,2,&Prio);
if(GetElem(L,4,&k))
{
printf("%d\n",k);
}
ListDelet(L,2,&k);
ClearList(L);
ListPrint(L);
printf("%d\n",ListLength(L));
DesdroyList(&L);
returnOK;
}
/*********************************************************************************************
*函数名称:
StatusInitList(LinkList*Head)
*功能描述:
初始化链表,产生一个空的链表,Head为表头
*参数说明:
Head表头
*返回值:
函数运行成功标志
*********************************************************************************************/
StatusInitList(LinkList*Head)
{
(*Head)=(LinkList)malloc(sizeof(structLNode));/*分配内存*/
if((*Head)==NULL)/*(*Head==NULL)内存分配失败*/
{
printf("ERROR:
InitialListFalse!
\n");
exit(ERROR);
}
(*Head)->next=NULL;/*表头指针为空*/
printf("SUCCESS:
InitialListSuccess!
\n");
returnOK;
}
/*********************************************************************************************
*函数名称:
StatusListInsert(LinkListL,inti,ElemTypee)
*功能描述:
在链表的位置i处插值e
*参数说明:
L链表
*i插入元素位置
*e要插入元素
*返回值:
函数运行成功标志
*********************************************************************************************/
StatusListInsert(LinkListL,inti,ElemTypee)
{
LinkListp=L,s;
intj=0;
if(L==NULL)//L==NULL
{
return(ERROR);
exit
(1);
}
while(p&&j{
p=p->next;
j++;
}
if(!
p||j>i-1)//i大于表长或小于1
{
return(ERROR);
}
s=(LinkList)malloc(sizeof(structLNode));/*生成新结点*/
s->data=e;/*插入L中*/
s->next=p->next;
p->next=s;
returnOK;
}
/*********************************************************************************************
*函数名称:
StatusListDelet(LinkListL,inti,ElemType*e)
*功能描述:
在带头结点的单链线性表L中,删除第i个元素,并由e返回其值
*参数说明:
L链表
*i删除元素位置
*e删除值
*返回值:
函数运行成功标志
*********************************************************************************************/
StatusListDelet(LinkListL,inti,ElemType*e)
{
LinkListp=L,s;
intj=0;
if(L==NULL)//L==NULL
{
return(ERROR);
exit
(1);
}
while(p&&j{
p=p->next;
j++;
}
if(!
p||j>i-1)//i位置不对
{
return(ERROR);
}
s=p->next;//删除并释放元素
p->next=s->next;
(*e)=s->data;
free(s);
printf("已删除%d\n",*e);
returnOK;
}
/*********************************************************************************************
*函数名称:
StatusListPrint(LinkListL)
*功能描述:
输出链表L
*参数说明:
L链表
*返回值:
函数运行成功标志
*********************************************************************************************/
StatusListPrint(LinkListL)
{
LinkListp=L;
p=L->next;
if(L==NULL)//L!
=NULL;
{
return(ERROR);
}
while(p)//p!
=NULL时输出p的值
{
printf("%d\n",p->data);
p=p->next;
}
return(OK);
}
/*********************************************************************************************
*函数名称:
StatusDesdroyList(LinkList*L)
*功能描述:
销毁链表L:
L已经存在
*参数说明:
L链表
*返回值:
函数运行成功标志
*********************************************************************************************/
StatusDesdroyList(LinkList*L)
{
LinkListp;
while(*L)//链表存在且未到表尾执行操作
{
p=(*L)->next;
free(*L);//释放内存
(*L)=p;//表头后移
}
printf("HaveBeanDestroyed");
return(OK);
}
/*********************************************************************************************
*函数名称:
StatusClearList(LinkListL)
*功能描述:
初始条件:
线性表L已存在。
操作结果:
将L重置为空表
*参数说明:
L链表
*返回值:
函数运行成功标志
*********************************************************************************************/
StatusClearList(LinkListL)
{
LinkListp,q;
p=L->next;
while(p)//未到表尾执行操作
{
q=p->next;
free(p);
p=q;
}
L->next=NULL;
printf("链表清空\n");
return(OK);
}
/*********************************************************************************************
*函数名称:
StatusGetElem(LinkListL,inti,ElemType*e)
*功能描述:
在链表中查找第i个元素
*参数说明:
L链表
*i查找元素位置
*e查找到的值(若成功的话)
*返回值:
函数运行标志
*********************************************************************************************/
StatusGetElem(LinkListL,inti,ElemType*e)
{
intj=1;//j做计数器
LinkListp;
p=L->next;
while(p!
=NULL&&j
{
p=p->next;
j++;
}
if(!
p||j>i)//第i个元素不存在
{
printf("未找到元素");
returnERROR;
}
*e=p->data;
printf("查找到元素\n");
returnOK;
}
/*********************************************************************************************
*函数名称:
intListLength(LinkListL)
*功能描述:
计算链表长度
*参数说明:
L链表
*返回值:
链表长度
*********************************************************************************************/
intListLength(LinkListL)
{
LinkListp=L->next;
inti=0;
while(p!
=NULL)
{
i++;
p=p->next;
}
returni;
}
/*********************************************************************************************
*函数名称:
StatusPrioElem(LinkListL,ElemTypecurrent,ElemType*Prio)
*功能描述:
在链表中查找一个元素的前继
*参数说明:
L链表
*current查找元素
*Prio前继
*返回值:
查找结果:
OK:
成功FALSE:
失败
*********************************************************************************************/
StatusPrioElem(LinkListL,ElemTypecurrent,ElemType*Prio)
{
LinkListp=L->next,q;
while(p->next)
{
q=p->next;
if(q->data==current)
{
(*Prio)=p->data;
printf("找到前继\n");
returnOK;
}
p=q;
}
return0;
}
/*********************************************************************************************
*函数名称:
voidRandCreateList(LinkList*L,intn)
*功能描述:
随机产生n个元素的值,建立带表头结点的单链线性表L(头插法)
*参数说明:
L链表
*n元素个数
*返回值:
无
*********************************************************************************************/
voidRandCreateList(LinkList*L,intn)
{
LinkListp;
srand(time(0));/*初始化随机数种子*/
inti;
(*L)=(LinkList)malloc(sizeof(structLNode));/*先建立一个带头结点的单链表*/
(*L)->next=NULL;
for(i=0;i{
p=(LinkList)malloc(sizeof(structLNode));/*生成新结点*/
p->data=rand()%100;/*随机生成100以内的数字*/
p->next=(*L)->next;
(*L)->next=p;/*