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

自学嵌入式 day20-数据结构链表

news 2025/5/20 5:19:52

注：gdb调试工具用法

3.链表的常规操作

（6）尾部插入

int InsertTailLinkList(LinkList* ll, DATATYPE* data)
{
if (IsEmptyLinkList(ll))//判断链表是否为空
{
return InsertHeadLinkList(ll, data);
}
else
{
LinkNode* newnode = malloc(sizeof(LinkNode));//定义一个新结点，并申请空间
if (NULL == newnode)//判断空间是否申请成功
{
fprintf(stderr, "InsertTailLinkList malloc");
return 1;
}

memcpy(&newnode->data, data, sizeof(DATATYPE));//将data复制到新结点
newnode->next = NULL;//将新结点下一位指向空指针

LinkNode* tmp = ll->head;//定义新结点并指向头指针
while (tmp->next)//遍历链表
{
tmp = tmp->next; // tmp++;
}
tmp->next = newnode;//将新结点接在链表的尾部
ll->clen++;
}
return 0;
}

（7）按指定位置插入

int InsertPosLinkList(LinkList* ll, DATATYPE* data, int pos)
{
int len = GetSizeLinkList(ll);//获得链表的长度

if (pos < 0 || pos > len)//判断输入位置是否正确
{
return 1;
}
if (0 == pos) // 头部插入
{
return InsertHeadLinkList(ll, data);
}
else if (pos == len) // 尾部插入
{
return InsertTailLinkList(ll, data);
}
else
{
LinkNode* newnode = malloc(sizeof(LinkNode));//定义并申请新结点的空间
if (NULL == newnode)//判断空间是否申请成功
{
fprintf(stderr, "InsertPosLinkList malloc");
return 1;
}
memcpy(&newnode->data, data, sizeof(DATATYPE));
newnode->next = NULL;
int i = 0;
LinkNode* tmp = ll->head;
for (i = 0; i < pos - 1; ++i)//定位需插入的指定位置
{
tmp = tmp->next;
}
newnode->next = tmp->next;//将新结点连接在指定位置前后
tmp->next = newnode;
}
ll->clen++;
return 0;
}

（8）销毁

int DestroyLinkList(LinkList **ll)
{
   while(1)
   {
       LinkNode *tmp = (*ll) -> head;
       if(NULL == tmp)
       {
           break;
       }
       (*ll) -> head = (*ll) -> head -> next;
       free(tmp);
   }
   free(*ll);
   *ll = NULL;
   return 0;
}

（9）找中间结点

LinkNode *MidFindLinkList(LinkList *ll)
{
   LinkNode *slow = ll -> head;//定义新指针，指向头指针
   LinkNode *fast = ll -> head;//定义新指针，指向头指针
   while(fast)//每次循环fast结点向后移2位，slow结点向后移1位，fast位移距离是slow的两倍
   {
       fast = fast -> next;
       if(NULL == fast)
       {
           break;
       }
       fast = fast -> next;
       slow = slow -> next;
   }
   return slow;//slow所处位置即链表中间位置
}

（10）查找倒数第k个结点

LinkNode *LaskFindLinkList(LinkList *ll,int k)
{
   LinkNode *slow = ll -> head;
   LinkNode *fast = ll -> head;
   for(int i = 0;i < k;++i)//让fast从制定k处结点开始向后移动
   {
       fast = fast ->next;
   }
   while(fast)
   {
       fast = fast -> next;
       slow = slow -> next;
   }
   return slow;//slow所处结点即倒数第k结点
}

（11）链表的逆序

int RevertLinkList(LinkList *ll)
{
   LinkNode *prev = NULL;//定义一个指向被逆转结点的指针，初始为空指针
   LinkNode *tmp = ll -> head;//定义一个指向待逆转结点的指针
   LinkNode *next = ll -> head -> next;//定义待逆转节点next指向的指针
   int len = GetSizeLinkList(ll);
   if(len < 2)//逆序链表长度必须大于1
   {
       return 1;
   }
   while(1)
   {
       tmp -> next = prev;//将待逆转结点指向被逆转节点
       prev = tmp;//prev++
       tmp = next;//tmp++
       if(NULL == tmp)//判断tmp是否是空指针
       {
           break;
       }
       next = next -> next;//next++

   }
   ll -> head = prev;//将头指针指向以逆转的链表首位
   return 0;
}

练习：

（1）链表的排序

int InsertSortLinkList(LinkList* ll)
{
   LinkNode *pins = ll -> head;//定义一个指针指向头指针，代表已排序的链表
   LinkNode *ptmp = pins -> next;//定义一个指针指向pins->next，代表需要排序的链表
   LinkNode *next = ptmp -> next;//定义一个指针指向ptmp->next，协助遍历需要排序的结点
   ptmp -> next = NULL;//提取需要排序的结点
   ll -> head -> next = NULL;//协助首次遍历已排序的链表
   while(1)
   {
       pins = ll -> head;
       while(pins -> next && ptmp -> data.age >pins -> data.age && ptmp -> data.age > pins ->next -> data.age)//遍历已排序的链表，并使pins指向待排序结点连接的正确的位置
       {
           pins = pins -> next;
       }
       if(pins -> data.age > ptmp -> data.age)//首插
       {
           ptmp -> next = ll -> head;
           ll -> head = ptmp;
       }
       else//将结点插入pins指向的结点和pins ->next指向的结点
       {
           ptmp -> next = pins -> next;
           pins -> next = ptmp;
       }

       ptmp = next;//遍历需排序的结点
       if(NULL == ptmp)//循环终止条件
       {
           break;
       }
       next = next -> next;
       ptmp -> next = NULL;//提出需排序的结点
   }
}

（2）判断链表是否有环

int IsRingLinkList(LinkList*ll)
{
LinkNode* fast = ll->head;
LinkNode * slow =ll->head;

while(fast)
{
fast =fast->next;
if(NULL == fast)
{
return 0;;
}

if(slow == fast)
{
return 1;
}
fast =fast->next;
slow = slow->next;

}
return 0;
}