链表——双向链表

双向链表

结构体：

typedef int datatype;

typedef struct node_t

{

datatype data;//数据域 

struct node_t *next;//指向下一个节点的指针 next 下一个

struct node_t *prior;//指向前一个节点的指针 prior 前一个

}link_node_t,*link_list_t;

//将双向链表的头指针和尾指针封装到一个结构体里 

//思想上有点像学的链式队列

typedef struct doublelinklist

{

link_list_t head; //指向双向链表的头指针

link_list_t tail; //指向双向链表的尾指针

int len;

}double_node_t,*double_list_t;

头文件：

"[code=C]"

	
#include <stdio.h>
#include <stdlib.h>
typedef int datatype;
typedef struct node_t
{
	datatype data;//数据域 
	struct node_t *next;//指向下一个节点的指针 next 下一个
	struct node_t *prior;//指向前一个节点的指针 prior 前一个
}link_node_t,*link_list_t;

//将双向链表的头指针和尾指针封装到一个结构体里 
//思想上有点像学的链式队列
typedef struct doublelinklist
{
	link_list_t head; //指向双向链表的头指针
	link_list_t tail; //指向双向链表的尾指针
	int len;
}double_node_t,*double_list_t;
//1.创建一个空的双向链表
double_list_t createEmptyDoubleLinkList()；
//2.向双向链表的指定位置插入数据 post位置， data数据
int insertIntoDoubleLinkList(double_list_t p, int post, datatype data)；
//3.遍历双向链表
void showDoubleLinkList(double_list_t p)；
//4.删除双向链表指定位置的数据
int deletePostDoubleLinkList(double_list_t p, int post)；
//5.判断双向链表是否为空
int isEmptyDoubleLinkList(double_list_t p)；
//6.求双向链表的长度
int lengthDoubleLinkList(double_list_t p)；
//7.查找指定数据出现的位置 data被查找的数据
int searchPostDoubleLinkList(double_list_t p,datatype data)；
//8.修改指定位置的数据,post修改的位置 data被修改的数据
int changeDataDoubleLinkList(double_list_t p,int post, datatype data)；
//9.删除双向链表中的指定数据 data代表删除所有出现的data数据
int deleteDataDoubleLinkList(double_list_t p, datatype data)；



"[code=C/"

函数：

"[code=C]"
#include <stdio.h>
#include <stdlib.h>
typedef int datatype;
typedef struct node_t
{
	datatype data;//数据域 
	struct node_t *next;//指向下一个节点的指针 next 下一个
	struct node_t *prior;//指向前一个节点的指针 prior 前一个
}link_node_t,*link_list_t;

//将双向链表的头指针和尾指针封装到一个结构体里 
//思想上有点像学的链式队列
typedef struct doublelinklist
{
	link_list_t head;//指向双向链表的头指针
	link_list_t tail; //指向双向链表的尾指针
	int len;
}double_node_t,*double_list_t;
//1.创建一个空的双向链表
double_list_t createEmptyDoubleLinkList()
{
    
    double_list_t p=(double_node_t *)malloc(sizeof(double_node_t));
    if(p==NULL)
    {
        perror("p err");
        return NULL;
    }
    p->head= p->tail=(link_node_t *)malloc(sizeof(link_node_t));
    if(p->head==NULL)
    {
        perror("p err");
        return NULL;
    }
    p->len=0;
    p->head->next=NULL;
    p->head->prior=NULL;
    return p;
}
//2.向双向链表的指定位置插入数据 post位置， data数据
int insertIntoDoubleLinkList(double_list_t p, int post, datatype data)
{   
    link_list_t temp=NULL;
    if(post<0||post>p->len)
    {
        printf("insertIntoDoubleLinkList error");
        return -1;
    }
    link_list_t pnew=(link_list_t )malloc(sizeof(link_node_t));
        if(pnew==NULL)
    {
        perror("pnew err");
        return -1;
    }
   
   pnew->data=data;
   pnew->next=NULL;
   pnew->prior=NULL;

   if(post==p->len)//尾插
   {
       p->tail->next=pnew;
       pnew->prior=p->tail;
       p->tail=pnew;
   }
   else
   {
       if(post<p->len/2)//头插
       {
           temp=p->head;
          for(int i=0;i<=post;i++)
        {
         temp=temp->next;
        }
       }
       else
       {
         temp=p->tail;
         for(int i=0;i<=p->len-post-1;i++)
         {
             temp=temp->prior;
         }
       }
       temp->prior->next=pnew;
       pnew->prior=temp->prior;
       pnew->next=temp;
       temp->prior=pnew;
   }
p->len++;
return 0;
}
//3.遍历双向链表
void showDoubleLinkList(double_list_t p)
{
    link_list_t p1=p->head;
    // link_list_t p2=p->tail;
    while(p1->next!=NULL)
    {
        p1=p1->next;
        printf("%d  ",p1->data);
       
    }
    // while(p2!=p->head)
    // {
    //     printf("%d  ",p2->data);
    //     p2=p2->prior;
    // }
    printf("\n");
}
//4.删除双向链表指定位置的数据
int deletePostDoubleLinkList(double_list_t p, int post)
{
     link_list_t temp=NULL;
      if(post<0||post>p->len)
    {
        printf("deletePostDoubleLinkList error");
        return -1;
    }
    link_list_t pdel=NULL;
    if(post==p->len-1)
    {
       pdel=p->tail;
       p->tail=p->tail->prior;
        free (pdel);
        pdel=NULL;
    }
    else
    {
        if(post<p->len/2)
       {
           temp=p->head;
          for(int i=0;i<=post;i++)
        {
         temp=temp->next;
        }
       }
       else
       {
         temp=p->tail;
         for(int i=0;i<=p->len-post-1;i++)
         {
             temp=temp->prior;
         }
       }
       temp->prior->next=temp->next;
       temp->next->prior=temp->prior;
       free(temp);
       temp=NULL;
    }
    p->len--;
    return 0;
    

}
//5.判断双向链表是否为空
int isEmptyDoubleLinkList(double_list_t p)
{
return p->head==p->tail;
}
//6.求双向链表的长度
int lengthDoubleLinkList(double_list_t p)
{
    return p->len;
}
//7.查找指定数据出现的位置 data被查找的数据
int searchPostDoubleLinkList(double_list_t p,datatype data)
{
     link_list_t temp=NULL;
     int i=1;
     temp=p->head;
     while(temp->next!=NULL)
     {
      temp=temp->next;
      if(temp->data==data)
      {
        printf("%d  ",i);
       
      }   
      i++;
     }
     printf("\n");
     return -1;
    
}
//8.修改指定位置的数据,post修改的位置 data被修改的数据
int changeDataDoubleLinkList(double_list_t p,int post, datatype data)
{
   link_list_t temp=NULL;
   if(post<p->len/2)
   {
       temp=p->head;
       for(int i=0;i<=post;i++)
       temp=temp->next;
   }
   else
   {
       
       temp=p->tail;
       for(int i=0;i<p->len-post-1;i++)
       temp=temp->prior;
   }
   temp->data=data;
    return 0;
}
//9.删除双向链表中的指定数据 data代表删除所有出现的data数据
int deleteDataDoubleLinkList(double_list_t p, datatype data)
{    link_list_t pdel=NULL;
     link_list_t temp=NULL;
     int i=1;
     temp=p->head->next;
     while(temp!=NULL)
     {
      if (temp->data==data)
      {
          if(temp==p->tail)
          {
              p->tail=p->tail->prior;
              free(p->tail->next);
              p->tail->next=NULL;
          }
          else
          {
              temp->prior->next=temp->next;
               temp->next->prior=temp->prior;
               pdel=temp;
               temp=temp->next;
               free(pdel);
               pdel=NULL;
          }
          p->len--;
      }
      else
      {
          temp=temp->next;
      }
      

    //   if(temp->data==data)
    //   {
    //     deletePostDoubleLinkList(p, i);
    //   }

    //   temp=temp->next;
    //   i++;
     }
     return 0;
}
int main(int argc, char const *argv[])
{
    double_list_t p=createEmptyDoubleLinkList();
   
    insertIntoDoubleLinkList(p,0,1);
    insertIntoDoubleLinkList(p,1,2);
    insertIntoDoubleLinkList(p,2,3);
    insertIntoDoubleLinkList(p,3,4);
    insertIntoDoubleLinkList(p,4,3);
    showDoubleLinkList(p);
    deletePostDoubleLinkList(p, 2);
     showDoubleLinkList(p);
    searchPostDoubleLinkList(p,3);
    changeDataDoubleLinkList(p,2, 3);
    showDoubleLinkList(p);
    deleteDataDoubleLinkList(p, 3);
    showDoubleLinkList(p);
    return 0;
}

"[code=C/"