数据结构——链表——带头结点的双向循环链表
程序员文章站
2022-03-15 19:59:14
...
带头结点的双向循环链表
#include<stdlib.h>
#include<stdio.h>
#include"headList.h"
/*
功能:创建一个空链表
参数:无
返回值:
失败返回NULL
成功返回头结点的地址
*/
List * createLkList()
{
List * list = (List *)malloc(sizeof(List));
if(list == NULL)
{
printf("malloc fail\n");
return NULL;//失败返回NULL
}
list->first = NULL;
list->last = NULL;
list->n = 0;//现在还是空链表
return list;
}
/*
功能:往链表中插入一个元素
参数:
@list 头结点的地址
@x 待插入的数据
返回值:无
*/
int insert(List * list,ElemType x)
{
//1,分配空间
Node * p = (Node *)malloc(sizeof(Node));
if(p == NULL)
{
printf("分配内存失败\n");
return 0;
}
//2,保存数据
p->data = x;
p->next = NULL;
p->prev = NULL;
//3,把该节点插入到链表中
if(list->first == NULL)//if(list->n == n)
{
list->first = p;
list->last = p;
}
else
{
#if 1
//尾插法
list->last->next = p;
p->prev = list->last;
list->last = p;
#else
//头插法
list->first->prev = p;
p->next = list->first;
list->first = p;
#endif
}
list->last->next = list->first;
list->first->prev = list->last;
list->n ++;
return 1;
}
/*
功能:输出一个链表的所有节点数据
参数:
@l 该链表的头结点的地址
返回值:无
*/
void printfLkList(List * l)
{
Node * p = l->first;
int i;
for(i=0;i<l->n;i++)
{
printf("%d ",p->data);
p = p->next;
}
printf("\n");
}
/*
功能:清空一个空链表
参数:
@list 该链表的头结点的地址
返回值:无
*/
void cleanList(List *list)
{
Node * p = list->first;
Node * q = NULL;
int i;
for(i=0;i<list->n;i++)
{
q = p->next;
p->next = NULL;
p->prev = NULL;
free(p);
p = q;
}
list->first=list->last=NULL;
list->n = 0;
}
/*
功能:销毁一个空链表
参数:
@list 该链表的头结点的地址
返回值:无
*/
void destroyList(List * list)
{
cleanList(list);
free(list);
}
/*
功能:查找list链表中是否存在一个值为x的元素
参数:
@list 该链表的头结点的地址
@x 查询的数据
返回值:
找到了返回1
没找到返回0
*/
int find(List * list,ElemType x)
{
Node * p = list->first;
int i;
for(i=0;i<list->n;i++)
{
if(p->data == x)
{
return 1;
}
p = p->next;
}
return 0;
}
/*
功能:往一个有序链表中插入一个节点,使之仍然有序
参数:
@list 该链表的头结点的地址
@x 待插入的数据
返回值:无
*/
void insertElem(List * list,ElemType x)
{
Node * p = (Node *)malloc(sizeof(Node));
p->data = x;
p->next = NULL;
p->prev = NULL;
Node * q = list->first;
Node * r = NULL;
//找到第一个比我大的元素
int i;
for(i=0;i<list->n;i++)
{
if(q->data > x)
{
break;
}
r = q;
q = q->next;
}
if(i==list->n)//没找到,插入到最后
{
list->last->next = p;
p->prev = list->last;
list->last = p;
list->last->next = list->first;
list->first->prev = list->last;
}
else if(q == list->first)//第一个就比我大
{
p->next = list->first;
list->first->prev = p;
list->first = p;
list->last->next = list->first;
list->first->prev = list->last;
}
else//中间位置
{
r->next = p;
p->next = q;
p->prev = r;
q->prev = p;
}
list->n ++;
}
/*
功能:删除一个链表中值为x的节点
参数:
@list 该链表的头结点的地址
@x 待删除的数据
返回值:
删除成功返回1
没有这个元素返回0
*/
int delete(List * list,ElemType x)
{
Node * p = list->first;
Node * r = NULL;
int i;
for(i=0;i<list->n;i++)
{
if(p->data == x)
{
break;
}
r = p;
p = p->next;
}
if(i==list->n)//没找到
return 0;
if(i<list->n)//找到了
{
//分情况删除
if(p == list->first)//删除的是第一个
{
list->first = p->next;
//list->first->prev = NULL;
p->next = NULL;
p->prev = NULL;
free(p);
list->last->next = list->first;
list->first->prev = list->last;
}
else if(p == list->last)//删除的是最后一个
{
list->last = r;
p->prev = NULL;
p->next = NULL;
free(p);
list->last->next = list->first;
list->first->prev = list->last;
}
else//中间
{
r->next = p->next;
p->next->prev = r;
p->next = NULL;
p->prev = NULL;
free(p);
}
list->n --;
}
return 1;
}
上一篇: 智能侦查和人工智能技术的融合应用