当前位置：首页 > web >正文

自学嵌入式 day21 - 数据结构双向链表

web 2025/8/20 18:13:58

1.双向链表

2.基础操作

（1）头部插入

int InsertHeadDouLinkList(DouLinkList *dl,DATATYPE *data)
{
   DouLinkNode *newnode = (DouLinkNode *)malloc(sizeof(DouLinkNode));//定义新节点来存储需插入的数据
       if(NULL == newnode)//判断结点空间是否申请成功
       {
fprintf(stderr,"intertHeadDouLinkList malloc");
return 1;
       }
   memcpy(&newnode -> data,data,sizeof(DATATYPE));//将需插入的数据装入新结点
  //初始化新结点中的指针内容

    newnode -> next = NULL;
   newnode -> prev = NULL;
   newnode -> next = dl -> head;//连接新结点和链表
   if(dl -> head)//判断链表是否为空
   {
       dl -> head -> prev = newnode;
   }
   dl -> head = newnode;//连接头指针与新结点
   dl -> clen++;
   return 0;
}

（2）打印（正向打印，反向打印）

int ShowDouLinkList(DouLinkList *dl,DIR dir)
{
   if(FORWADR == dir)//正向打印
   {
       DouLinkNode *tmp = dl -> head;
       while(tmp)//遍历
       {
           printf("%s,%c,%d,%d\n",tmp -> data.name,tmp -> data.sex,tmp -> data.age,tmp -> data.score);
           tmp = tmp -> next;
       }
   }
   else if(BACKWADR == dir)//反向打印，从末尾开始向前打印
   {
       DouLinkNode *tmp = dl -> head;
       while(tmp -> next)//遍历链表，使初始位置指向最后结点
       {
           tmp = tmp -> next;
       }
       while(tmp)//反向遍历链表
       {
           printf("%s,%c,%d,%d\n",tmp -> data.name,tmp -> data.sex,tmp -> data.age,tmp -> data.score);
           tmp = tmp -> prev;
       }
   }
}

（3）尾部插入

int IsEmptyLinkList(DouLinkList *dl)
{
   return 0 == dl -> clen;
}

int InsertTaiDouLinkList(DouLinkList *dl,DATATYPE *data)
{
   if(IsEmptyLinkList(dl))//判断链表是否为空
   {
       return InsertHeadDouLinkList(dl,data);
   }
   else
   {
       DouLinkNode *newnode = malloc(sizeof(DouLinkNode));//申请新结点存储待插入数据
       if(NULL == newnode)//判断新结点空间是否申请成功
       {
           fprintf(stderr,"insertTaiDouLinkList malloc\n");
           return 1;
       }
       memcpy(&newnode -> data,data,sizeof(DATATYPE));//存入待插入数据
       newnode -> next = NULL;//初始化新结点指针
       newnode -> prev = NULL;
       DouLinkNode *tmp = dl -> head;//定义新指针，指向头指针
       while(tmp -> next)//遍历链表
       {
           tmp = tmp -> next;
       }
       newnode -> prev = tmp;//将新结点插入链表尾部
       tmp -> next = newnode;
       dl -> clen++;
   }
   return 0;
}

（4）指定位置插入

int GetsizeofDouLinkList(DouLinkList *dl)
{
   return dl -> clen;
}

int InsertPosDouLinkList(DouLinkList *dl,DATATYPE *data,int pos)
{
   int len = GetsizeofDouLinkList(dl);//算出链表长度
   if(0 == pos)//头部插入
   {
       return InsertHeadDouLinkList(dl,data);
   }
   else if(pos == len)//尾部插入
   {
       return InsertTaiDouLinkList(dl,data);
   }
   else
   {
       DouLinkNode *newnode = malloc(sizeof(DouLinkNode));
       if(NULL == newnode)
       {
           fprintf(stderr,"InsertPosDouLinkList malloc\n");
           return 1;
       }
       memcpy(&newnode -> data,data,sizeof(DATATYPE));
       newnode -> next = NULL;
       newnode -> prev = NULL;
       DouLinkNode *tmp = dl -> head;
       for(int i = 0;i < pos;++i)//遍历链表，定位待插位置
       {
           tmp = tmp -> next;
       }
       newnode -> next = tmp;//将新结点和待插位置的前结点和后结点连接
       newnode -> prev = tmp -> prev;
       tmp -> prev = newnode;
       newnode -> prev ->next = newnode;
       dl ->clen++;

   }
   return 0;
}

（5）查找

DouLinkNode *FindDouLinkList(DouLinkList *dl,char *name)
{
   int len = GetsizeofDouLinkList(dl);//获取链表长度
   DouLinkNode *tmp = dl -> head;//定义新指针，指向头指针
   for(int i = 0;i < len;++i)//遍历链表
   {
       if(0 == strcmp(tmp -> data.name,name))//用已给name查找结点
       {
           return tmp;
       }
       tmp = tmp -> next;
   }
   return NULL;
}

（6）替换

int ModifyDouLinkLinst(DouLinkList *dl,char *name,DATATYPE *data)
{
   DouLinkNode *ret = FindDouLinkList(dl,name);//查找结点
   if(NULL == ret)//判断是否找到结点
   {
       return 1;
   }
   memcpy(&ret -> data,data,sizeof(DATATYPE));//替换数据
   return 0;
}

练习：

（1）销毁

int DestroyDouLinkList(struct DouLinkList* dl)
{
   DouLinkNode *tmp = dl -> head;//定义新指针，指向头指针
   DouLinkNode *ret ;
   while(tmp)//遍历链表
   {
       ret = tmp;
       tmp = tmp -> next;
       free(ret);//释放结点空间
       ret = NULL;
   }
   free(dl);
   dl = NULL;
   return 0;

}

（2）删除

int DeleteDouLinkList(struct DouLinkList* dl,char* name)
{
   DouLinkNode *tmp = FindDouLinkList(dl,name);//查找待删结点
   if(NULL == tmp -> prev)//头删
   {
       dl -> head = tmp -> next;
       tmp -> next -> prev = NULL;
       dl -> clen--;
       free(tmp);
       tmp = NULL;
       return 0;
   }
   else if(NULL == tmp -> next)//尾删
   {
       tmp -> prev -> next = NULL;
       dl -> clen--;
       free(tmp);
       tmp = NULL;
       return 0;
   }
   else
   {
       tmp -> prev ->next = tmp -> next;
       tmp -> next ->prev = tmp -> prev;
       dl -> clen--;
       free(tmp);
       tmp = NULL;
       return 0;
   }
}

（3）逆序

int RevertDouLinkList(struct DouLinkList* dl)
{
   DouLinkNode *p = NULL;//定义一个指向被逆转结点的指针，初始位空指针
   DouLinkNode *tmp = dl -> head;//定义一个指向待逆转结点的指针，初始化位头指针
   DouLinkNode *n = tmp ->next;//定义一个指向待逆转结点next的指针，辅助遍历链表
   int len = GetsizeofDouLinkList(dl);
   if(len < 2)//逆序链表长度必须大于1
   {
       return 1;
   }
   while(1)
   {
       tmp -> next = p;//将待逆序结点指向被逆序节点
       tmp -> prev = n;

       p = tmp;//p++
       tmp = n;//tmp++
       if(NULL == tmp)//判断指针是否为空
       {
           break;//指针为空时结束循环
       }
       n = n -> next;//n++

   }
   dl -> head = p;//将头指针指向已逆序后的链表首位
   return 0;
}