数据结构--双向链表，双向循环链表
双向链表的头插，尾插，头删，尾删
头文件：（head.h）
#include <string.h>
#include <stdlib.h>
typedef char datatype;
typedef struct node
{
datatype data;
struct node* next;
struct node* prev;
}*Doublelink;
Doublelink Create_node();
Doublelink insert(Doublelink head,datatype element);
void show(Doublelink head);
Doublelink head_delete(Doublelink head);
Doublelink tail_insert(Doublelink head,datatype element);
Doublelink tail_delete(Doublelink head);
#endif
test.c
#include"head.h"
int main(int argc, const char *argv[])
{
Doublelink head=NULL;
int n;
datatype element;
printf("请输入要插入数据的个数：");
scanf("%d",&n);
for(int i=0;i<n;i++)
{
printf("请输入插入的数据：");
// scanf(" %c",&element);
getchar();
element=getchar();
head=insert(head,element);//头插
}
head=head_delete(head); //头删
show(head); //遍历
printf("请输入尾插插入的个数：");
scanf("%d",&n);
for(int i=0;i<n;i++)
{
printf("请输入插入的数据：");
// scanf(" %c",&element);
getchar();
element=getchar();
head=tail_insert(head,element);//尾插
}
head=tail_delete(head);
show(head);
return 0;
}
main.c
#include"head.h"
Doublelink Create_node()
{
Doublelink s=(Doublelink)malloc(sizeof(struct node));
if(NULL==s)
return NULL;
s->data=0;
s->next=s->prev=NULL;
return s;
}
//头插
Doublelink insert(Doublelink head,datatype element)
{
Doublelink s=Create_node();
s->data=element;
if(NULL==head)
{
head=s;
}
else
{
s->next=head;
head->prev=s;
head=s;
}
return head;
}
//遍历
void show(Doublelink head)
{
if(NULL==head)
{
return;
}
//正向遍历
Doublelink p=head;
while(p->next!=NULL)
{
printf("%c\t",p->data);
p=p->next;
}
printf("%c\n",p->data);
//反向遍历
/* while(p!=NULL)
{
printf("%c\t",p->data);
p=p->prev;
}
*/
}
//头删
Doublelink head_delete(Doublelink head)
{
//判断链表是否为空
if(NULL==head)
{
return head;
}
//链表存在多个节点
Doublelink del=head;
head=head->next;
free(del);
del=NULL;
return head;
}
//尾插
Doublelink tail_insert(Doublelink head,datatype element)
{
Doublelink s=Create_node();
s->data=element;
//链表为空
if(NULL==head)
{
head=s;
return head;
}
//链表节点个数>=1
Doublelink p=head;
while(p->next!=NULL)
{
p=p->next;
}
p->next=s;
s->prev=p;
return head;
}
//尾删
Doublelink tail_delete(Doublelink head)
{
if(NULL==head)
{
return head;
}
Doublelink p=head;
while(p->next!=NULL)
{
p=p->next;
}
if(p->prev!=NULL)
{
p->prev->next=NULL;
}
free(p);
p=NULL;
return head;
}
双向循环链表的头插，头删，尾插，尾删
head.h
#ifndef __HEAD_H__
#define __HEAD_H__
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef char datatype;
typedef struct node
{
datatype data;
struct node* next;
struct node* prev;
}*Doublelink;
Doublelink Create_node();
Doublelink insert(Doublelink head,datatype element);
void show(Doublelink head);
Doublelink head_delete(Doublelink head);
Doublelink tail_insert(Doublelink head,datatype element);
Doublelink tail_delete(Doublelink head);
#endif
test.c
#include"head.h"
int main(int argc, const char *argv[])
{
Doublelink head=NULL;
int n;
datatype element;
printf("请输入要插入数据的个数：");
scanf("%d",&n);
for(int i=0;i<n;i++)
{
printf("请输入插入的数据：");
// scanf(" %c",&element);
getchar();
element=getchar();
head=insert(head,element);//头插
}
head=head_delete(head); //头删
show(head); //遍历
printf("请输入尾插插入的个数：");
scanf("%d",&n);
for(int i=0;i<n;i++)
{
printf("请输入插入的数据：");
// scanf(" %c",&element);
getchar();
element=getchar();
head=tail_insert(head,element);//尾插
}
head=tail_delete(head);
show(head);
return 0;
}
main.c
#include"head.h"
Doublelink Create_node()
{
Doublelink s=(Doublelink)malloc(sizeof(struct node));
if(NULL==s)
return NULL;
s->data=0;
s->next=s->prev=s;
return s;
}
//头插
Doublelink insert(Doublelink head,datatype element)
{
//创建节点
Doublelink s=Create_node();
s->data=element;
//链表为空链表
if(NULL==head)
{
head=s;
}
//链表节点数>=1
else
{
Doublelink real=head->prev;
s->next=head;
head->prev=s;
head=s;
real->next=head;
head->prev=real;
}
return head;
}
//遍历
void show(Doublelink head)
{
if(NULL==head)
{
return;
}
//正向遍历
Doublelink p=head;
while(p->next!=head)
{
printf("%c\t",p->data);
p=p->next;
}
printf("%c\n",p->data);
}
//头删
Doublelink head_delete(Doublelink head)
{
//判断链表是否为空
if(NULL==head)
{
return head;
}
//链表存在多个节点
Doublelink p=head;
//找到最后一个节点的位置
while(p->next!=head)
{
p=p->next;
}
Doublelink del=head;
head=head->next;
//连接头尾，让链表重新循环
p->next=head;
head->prev=p;
free(del);
del=NULL;
return head;
}
//尾插
Doublelink tail_insert(Doublelink head,datatype element)
{
//创建节点
Doublelink s=Create_node();
s->data=element;
//链表为空
if(NULL==head)
{
head=s;
return head;
}
//链表节点个数>=1
Doublelink p=head;
while(p->next!=head)
{
p=p->next;
}
p->next=s;
//连接表头和表尾
s->next=head;
head->prev=s;
return head;
}
//尾删
Doublelink tail_delete(Doublelink head)
{
//判断链表是否为空
if(NULL==head)
{
return head;
}
Doublelink p=head;
p=head->prev;
//如果链表只有一个节点
if(head->next==head)
{
free(p);
return NULL;
}
//删除尾节点
p->prev->next=head;
head->prev=p->prev;
free(p);
p=NULL;
return head;
}