链表.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;/*
升级会员 