嵌入式学习的第二十天-数据结构-调试+链表的一般操作

一、调试

1.一般调试

2.找段错误

二、链表的一般操作

1.单链表的修改

int ModifyLinkList(LinkList*ll,char*name,DATATYPE*data)
{
    DATATYPE * tmp = FindLinkList(ll, name);
    if(NULL == tmp)
    {
        return 1;
    }
    memcpy(tmp,data,sizeof(DATATYPE));
    return 0;
}

2.单链表的销毁

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;
}

3.查找中间节点

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

    while(fast)
    {
        fast =fast->next;
        if(NULL == fast)
        {
            break;;
        }
        slow = slow->next;
        fast =fast->next;
    }

    return slow;
}

 4.找倒数第k个节点

/**
 * @brief 查找倒数第k个节点
 * 
 * @param ll 需要查找的链表
 * @param k 倒数第k个节点
 * @return LinkNode* 找到对应的节点
 */
LinkNode*FindKLastLinkList(LinkList*ll,int k)
{
    LinkNode*slow = ll->head;
    LinkNode*fast = ll->head;
    
    int i = 0;
    for(i = 0;i<k;++i)
    {
        fast =fast->next;
    }
    while (fast) 
    {
        fast =fast->next;
        slow = slow->next;
    }
    return slow;
}

5.链表的逆序

int ReverseLinkList(LinkList*ll)
{
    LinkNode*prev = NULL;
    LinkNode*tmp = ll->head;
    LinkNode*next = tmp->next;
    int len = GetSizeLinkList(ll);
    if(len<2)
    {
        return 1;
    }
    
    while(1)
    {
        tmp->next = prev;
        prev = tmp;
        tmp = next;
        if(NULL == tmp) break;
        next = next->next;   
    }
      ll->head = prev;
    return 0;
}

6.链表的排序(插入法排序) 

int SertSortLinkList(LinkList*ll)
{
    LinkNode*pinsert = ll->head;
    LinkNode*ptmp = pinsert->next;
    LinkNode*next = ptmp->next;
    ptmp->next = NULL;
    ll->head->next = NULL;
    while (1) 
    {
        pinsert = ll->head;
        while (pinsert->next&&ptmp->data.age>pinsert->data.age&&ptmp->data.age>pinsert->next->data
        .age)
        {
            pinsert=pinsert->next;
        }

        if(pinsert->data.age>ptmp->data.age)
        {
            ptmp->next=ll->head;
            ll->head=ptmp;
        }
        else
        {
            ptmp->next=pinsert->next;
            pinsert->next=ptmp;
        }
        ptmp=next;
        if(NULL==ptmp)
        {
            break;
        }
        next=next->next;
        ptmp->next=NULL;
    }
    return 0;
}

7.循环链表

int circultlarLinkList(LinkList* ll)
{
  LinkNode* slow = ll->head;
  LinkNode* fast = 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;
}

三、顺序表和链表的优缺点

1.存储方式

• 顺序表是一段连续的存储单元
• 链表是逻辑结构连续物理结构（在内存中的表现形式）不连续

2.时间性能

（1）查找：顺序表O(1)  链表  O(n)

（2）插入和删除：顺序表 O(n)  链表   O(1)

3.空间性能

• 顺序表 需要预先分配空间，大小固定
• 链表， 不需要预先分配，大小可变，动态分配