双向链表及双向循环链表接口设计
双向链表接口设计
由于带头结点更加方便用户进行数据访问，所以本次创建一条带头结点的双向不循环的链表。
创建新的头结点和新节点
//数据类型
typedef int datatype_t;
//创建结点类型
typedef struct doublelinckelist
{
datatype_t data;//数据
struct doublelinckelist *next;//直接后驱
struct doublelinckelist *prev;//直接前驱
}dobll_t;
//输出数据
void dobll_updata(datatype_t data)
{
printf("%d\n",data);
}
//新建表头
dobll_t *dobll_head(void)
{
dobll_t *head=(dobll_t *) calloc(1,sizeof(dobll_t));
if(NULL==head)
{
perror("failed to creat header");
exit(-1);
}
head->next=NULL;
head->prev=NULL;
return head;
}
//新建结点
dobll_t * dobll_newcode(datatype_t data)
{
dobll_t *new=(dobll_t*)calloc(1,sizeof(dobll_t));
//判断是否创建成功
if(NULL==new)
{
perror("calloc memory for new is failed");
exit(-1);
}
new->data=data;
new->next=NULL;
new->prev=NULL;
return new;
}
遍历输出
bool dobll_print(dobll_t *head)
{
dobll_t *move=head->next;
if(head->next==NULL)
{
perror("empty list,travel failed");
return false;
}
while(move->next!=NULL)
{
dobll_updata(move->data);
move=move->next;
}
return true;
}
找到指定结点
dobll_t* dobll_finddest(dobll_t *head,datatype_t dest)
{
if(head->next==NULL)
{
perror("empty list,find failed");
exit(-1);
}
dobll_t *move=head;
while(move->next)
{
move=move->next;
if(move->data==dest)
{
return move;
}
}
perror("can't find dest");
exit(-1);
}
查找尾结点
dobll_t* dobll_findfail(dobll_t *head)
{
dobll_t *move=head->next;
//判断是否为空链表
if(head->next==NULL)
{
perror("empty list,find failed");
exit(-1);
}
while(move->next!=NULL)
{
move=move->next;
}
return move;
}
插入结点(头插)
bool dobll_insthead(datatype_t data,dobll_t *head)
{
dobll_t *new=dobll_newcode(data);
if(NULL==new)
{
perror("can't insert new code");
return false;
}
if(head->next==NULL)
{
head->next=new;
}
head->next->prev=new;
new->next=head->next;
head->next=new;
return true;
}
插入结点（尾插）
bool dobll_insttail(datatype_t data,dobll_t *head)
{
dobll_t *tail=dobll_findfail(head),*new=dobll_newcode(data);
if(NULL==new)
{
perror("can't insert new code");
return false;
}
if(head->next==NULL)
{
head->next=new;
}
new->prev=tail;
tail->next=new;
return true;
}
插入结点（指定）
bool dobll_instpont(dobll_t *head,datatype_t data,datatype_t dest)
{
dobll_t *new=dobll_newcode(data),*dst=dobll_finddest(head,dest);
if(NULL==new)
{
perror("can't insert new code");
return false;
}
if(dst->next==NULL)
{
new->prev=dst;
dst->next=new;
}
new->next=dst->next;
dst=new->prev;
dst->next->prev=new;
dst->next=new;
return true;
}
删除结点(首删)
bool dobll_headel(dobll_t *head)
{
if(head->next==NULL)
{
perror("error:lincked is NULL");
return false;
}
dobll_t *first=head->next;
if(head->next->next==NULL)
{
head->next=NULL;
free(first);
return true;
}
head->next=first->next;
first->next=NULL;
first->next->prev=NULL;
free ( first);
return true;
}
尾删
bool dobll_taildel(dobll_t *head)
{
if(head->next==NULL)
{
perror("error:lincked is NULL");
return false;
}
dobll_t *last;
last =dobll_findfail(head);
if(head->next->next!=NULL)\
last->prev->next=NULL;
last->prev=NULL;
free(last);
return true;
}
指定删
bool dobll_destdel(datatype_t dest,dobll_t *head) //删除指定结点
{
if(head->next==NULL)
{
perror("emptY list,find failed");
return false;
}
dobll_t *dst=dobll_finddest(head,dest); //找到指定结点
if(dst->prev!=NULL)
{
dst->prev->next=dst->next;
dst->prev=NULL;
}
if(dst->next!=NULL)
{
dst->next->prev=dst->prev;
dst->next=NULL;
}
if(head->next->data==dest)
head->next=NULL;
free(dst);
}
双向循环链表接口设计
由于带头结点更加方便用户进行数据访问，所以本次创建一条带头结点的双向循环的链表。
创建表头及新结点
//数据类型
typedef int datatype_t;
//创建结点类型
typedef struct CirDoubLinList
{
datatype_t data;//数据
struct CirDoubLinList *next;//直接后驱
struct CirDoubLinList *prev;//直接前驱
}cdll_t;
//输出数据
void cdll_updata(datatype_t data)
{
printf("%d\n",data);
}
//新建表头
cdll_t *cdll_head(void)
{
//划分内存
cdll_t *head=(cdll_t *) calloc(1,sizeof(cdll_t));
//判断是否创建成功
if(NULL==head)
{
perror("failed to creat header");
exit(-1);
}
head->next=head;
head->prev=head;
return head;
}
//新建结点
cdll_t * cdll_newcode(datatype_t data)
{
//划分内存
cdll_t *new=(cdll_t*)calloc(1,sizeof(cdll_t));
//判断是否创建成功
if(NULL==new)
{
perror("calloc memory for new is failed");
exit(-1);
}
new->data=data;
new->next=new;
new->prev=new;
return new;
}
遍历并输出
bool cdll_print(cdll_t *head)
{
//定义指针
cdll_t *move=head->next;
//判断是否为空
if(head->next==head)
{
perror("empty list,travel failed");
return false;
}
//循环输出
while(move->next!=head->next)
{
cdll_updata(move->data);
move=move->next;
}
return true;
}
找到指定结点
cdll_t* cdll_finddest(cdll_t *head,datatype_t dest)
{
//判断链表是否为空
if(head->next==head)
{
perror("empty list,find failed");
exit(-1);
}
//定义指针指向第一个节点
cdll_t *move=head->next;
//遍历查找
while(move->next!=head->next)
{
if(move->data==dest)
{
return move;
}
move=move->next;
}
//未找到，函数终止并向终端反馈
perror("can't find dest");
exit(-1);
}
插入节点（头插）
bool cdll_insthead(datatype_t data,cdll_t *head)
{
//新建结点并存储数据
cdll_t *new=cdll_newcode(data);
//判断是否新建成功
if(NULL==new)
{
perror("can't insert new code");
return false;
}
//判断是否为空链表
if(head->next!=head)
{
new->prev=head->next->prev;
new->next=head->next;
head->next->prev=new;
}
head->next=new;
return true;
}
插入节点（尾插）
bool cdll_insttail(datatype_t data,cdll_t *head)
{
//记录尾结点地址，新建结点并将数据存入
cdll_t *tail=head->next->prev,*new=cdll_newcode(data);
//判断是否新建成功
if(NULL==new)
{
perror("can't insert new code");
return false;
}
//判断是否为空链表
if(head->next==head)
{
head->next=new;
}
new->prev=tail;
tail->next=new;
new->next=head;
return true;
}
指定插入
插入到指定数据的下一个结点
bool cdll_instpont(cdll_t *head,datatype_t data,datatype_t dest)
{
//新建结点并将数据存入，查找并记录目标节点位置
cdll_t *new=cdll_newcode(data),*dst=cdll_finddest(head,dest);
//判断是否新建成功
if(NULL==new)
{
perror("can't insert new code");
return false;
}
new->next=dst->next;
new->prev=dst;
dst->next->prev=new;
dst->next=new;
return true;
}
删除头结点
`bool cdll_headel(cdll_t *head)`
`{`
`//判断链表是否为空`
`if(head->next==head)`
`{`
`perror("error:lincked is NULL");`
`return false;`
`}`
`//记录首结点地址`
`cdll_t *first=head->next;`
`//判断链表中是否仅有`一个元素`
`if(head->next->next!=head)`
`{`
`head->next=first->next;`
`first->prev->next=first->next;`
`first->next->prev=first->prev;`
`}`
`else`
`{`
`head->next=head;`
`}`
`first->next=first->prev=NULL;`
`free ( first);`
`return true;`
`}`
删除尾部结点
bool cdll_taildel(cdll_t *head)
{
//判断链表是否为空
if(head->next==head)
{
perror("error:lincked is NULL");
return false;
}
//记录尾结点
cdll_t *last=head->next->prev;
//判断是否为唯一结点
if(head->next->next!=head)
{
last->prev->next=last->next;
last->next->prev=last->prev;
}
else
{
head->next=head;
}
last->next=last->prev=NULL;
free(last);
return true;
}
删除指定结点
bool cdll_destdel(datatype_t dest,cdll_t *head)
{
//判断链表是否为空
if(head->next==head)
{
perror("emptY list,find failed");
return false;
}
//记录指定结点地址
cdll_t *dst=cdll_finddest(head,dest);
//判断是否是唯一节点
if(head->next->next!=head)
{
dst->prev->next=dst->next;
dst->next->prev=dst->prev;
}
else
{
head->next=head;
}
dst->next=dst->prev=NULL;
free(dst);
}