数据结构--双向链表，双向循环链表

双向链表的头插，尾插，头删，尾删

头文件：（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;                           
}