双向链表的头插，尾插，头删，尾删
头文件：（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;
} 
