目录
一、双向循环链表存在的意义
数组这样的结构提供了连续内存的访问和使用,链表是对内存零碎空间的有效组织和使用,双向循环链表增大了访问的自由度。
二、节点的定义
{ //构造双向链表的结点,链表中所有结点的数据类型应该是相同的
int data;
struct node *pre;
struct node *next;
}DoubleLList_t;
三:实现
1:创建链表(即创建一个空链表)
双向链表头结点是指向自己的:head->next = head;head->pre = head;
DoubleLList_t * createList()
{
Node * head = (Node *)malloc(sizeof(Node));
if (NULL == head)
exit(-1);
head->pre = head;
head->next = head;
return head;
}
2:创建新结点
DoubleLList_t * DoubleLList_NewNode(DataType_t data)
DoubleLList_t* New = (DoubleLList_t*)calloc(1, sizeof(DoubleLList_t));//1.创建一个新结点并对新结点申请内存
if (NULL == New)
{
perror("Calloc memory for NewNode is Failed");
return NULL;
}
//2.对新结点的数据域和指针域(2个)进行初始化
New->data = data;
New->prev = NULL;
New->next = NULL;
return New;
}
3:遍历
(核心点:对头结点备份,用循环来tem->next指向下一个结点)
void traverseNList(Node* head)
{
DoubleLList_t* tmp = head->next;//对头节点的地址备份
while (tmp != head)
{
printf("%-3d", tmp->data);
tmp = tmp->next;
}
}
4:插入
头插入
void insertList(Node* head,int data)
{
DoubleLList_t* last=head->next;
Node * new=ode *)malloc(sizeof(Node));//或调用上面封装的函数接口DoubleLList_NewNode(data)
if (NULL == last)
exit(-1);
while (last->next != head->next ){ //遍历找出尾结点
printf("%-3d", last->data);
last = last->next;
}
last->next=new; //尾结点的地址指向
new->prev=last;//新结点指向尾结点
new->new=head->next;
head->next->prev=new;
head->next=new;
}
尾插入
DoubleLList_t * Tai_deletion(DoubleLList_t * head,int data){
DoubleLList_t* last=head->next;
Node * new=ode *)malloc(sizeof(Node));//或调用上面封装的函数接口DoubleLList_NewNode(data)
if (NULL == last)
exit(-1);
while (last->next != head->next ){ //遍历找出尾结点
printf("%-3d", last->data);
last = last->next;
}
new->prev=last;
last->next=new;
new->next=head->next;
head->next->prev=new;
}
中间插入
DoubleLList_t * inserposition(){
DoubleLList_t* p=head->next;
Node * new=ode *)malloc(sizeof(Node));//或调用上面封装的函数接口DoubleLList_NewNode(data)
if (NULL == last)
exit(-1);
while ((p->next!=p)&&(p->next!=head->next) ){ //遍历找出尾结点
printf("%-3d", p->data);
p = p->next;
}
new->next=p->next;
p->next->prev=new;
new->prev=p;
p->next=new;
}
标签:head,last,待测,结点,DoubleLList,next,链表,new,求长
From: https://www.cnblogs.com/wxp55/p/18156083