嵌入式培训之数据结构学习（三）gdb调试、单向链表练习、顺序表与链表对比

目录

一、gdb调试

（一）一般调试步骤与命令

（二）找段错误（无下断点的地方）

（三）调试命令

二、单向链表练习

1、查找链表的中间结点（用快慢指针）

2、找出链表倒数第k个结点（用快慢指针）

3、链表的逆序

4、链表的插入排序

三、顺序表和链表对比

四、循环链表

一、gdb调试

（一）一般调试步骤与命令

1、gcc -g （调试版本，内含调试信息与源码；eg：gcc -g main.c linklist.c）

2、gdb a.out（调试可执行文件，eg：gdb ./a.out）

3、b fun.c:36 设置断点，运行到这个位置，程序自动暂停

（b ：100 默认停在main.c的100行；

   b fun.c : 36  停在fun.c的36行

   b 函数名    eg: b InserPosLinkList）

4、 r  运行（出现页面要输入则输入）

5、n 执行下一步  步过（如果是函数，直接调用结束）

     s  步入自定义函数（系统函数不入）

6、使用p命令，查看变量或指针等数据

（p  变量：显示变量值，eg：p len

   p  指针：看地址，eg：p *data）

7、q命令 退出（y）

（二）找段错误（无下断点的地方）

1、gcc -g  （加上调试选项-g，eg：gcc main.c linklist.c -g）

2、gdb a.out （调试可执行文件，eg：gdb ./a.out）

3、按  r(run)  直接开始运行

4、重现错误

5、where 找出段错误的位置（出现栈结构信息，从下往上看，找到第一个不是自己写的往后退一个）

    eg：#0（第一个不是自己写的，往后退一个）

            #1（此处出现段错误）

            #2

（三）调试命令

二、单向链表练习

1、查找链表的中间结点（用快慢指针）

（1）算法实现：

LinkNode* FindMidLinkList(LinkList*ll)

// 定义函数，功能是查找链表的中间节点，参数为链表头指针，返回链表节点指针
{
    LinkNode* fast = ll->head; // 初始化快指针，指向链表头节点
    LinkNode* slow = ll->head; // 初始化慢指针，指向链表头节点
    while(fast) // 当快指针不为空时，进行循环
    {
        fast = fast->next; // 快指针向前移动一个节点
        if(NULL == fast) // 检查快指针是否为空（即到达链表末尾）
        {
            break; // 如果为空，跳出循环
        }
        slow = slow->next; // 慢指针向前移动一个节点
        fast = fast->next; // 快指针再向前移动一个节点
    }
    return slow; // 循环结束，返回慢指针，此时慢指针指向链表中间节点
}

（2）调试：

2、找出链表倒数第k个结点（用快慢指针）

（1）算法实现：

LinkNode* FindLastKLinkList(LinkList*ll,int k)

// 定义函数，功能是查找链表倒数第k个节点，参数为链表头指针和整数k，返回链表节点指针
{

    int len = GetSizeLinkList(ll);
    if(k < 0 || k > len)
    {
        return NULL;
    }
    LinkNode* slow = ll->head; // 初始化慢指针，指向链表头节点
    LinkNode* fast = ll->head; // 初始化快指针，指向链表头节点
    for(int i = 0 ;i < k ;i++) // 循环k次
    {
        fast = fast->next; // 快指针向前移动一个节点，共移动k次
    }
    while(fast) // 当快指针不为空时，进行循环
    {
        fast =fast->next; // 快指针向前移动一个节点
        slow= slow->next; // 慢指针向前移动一个节点
    }
    return slow; // 循环结束，返回慢指针，此时慢指针指向链表倒数第k个节点
}

（2）调试：

3、链表的逆序

（1）图解

（2）算法实现

int RevertLinkList(LinkList* ll)
{
    LinkNode* prev = NULL; // 定义指针prev，用于指向当前节点的前一个节点，初始化为NULL
    LinkNode* tmp = ll->head; // 定义指针tmp，指向链表头节点，用于遍历链表
    LinkNode* next = tmp->next; // 定义指针next，指向tmp的下一个节点，用于保存tmp后续节点，防止链表断裂
    int len = GetSizeLinkList(ll); // 调用GetSizeLinkList函数获取链表长度并存储在len中
    if(len<2) // 如果链表长度小于2，即链表为空或只有一个节点
    {
        return 1; // 无需反转，直接返回1
    }
    while (1) // 进入无限循环，用于遍历并反转链表
    {
        tmp->next = prev; // 将当前节点tmp的next指针指向它的前一个节点prev，实现当前节点的反转
        prev = tmp; // 将prev指针移动到当前节点tmp的位置，为下一轮循环做准备
        tmp = next; // 将tmp指针移动到原本保存的下一个节点next的位置
        if (NULL == tmp) break; // 如果tmp指向NULL，说明已经遍历到链表末尾，跳出循环
        next = next->next; // 将next指针移动到tmp当前指向节点的下一个节点，为下一轮循环保存后续节点
    }
    ll->head = prev; // 将链表的头节点更新为反转后链表的头节点（即原链表的尾节点）
    return 0; // 成功反转链表，返回0
}

4、链表的插入排序

LinkList* InsertSortLinklist(LinkList* ll)
{
    LinkNode* pins = ll->head; // 定义指针pins，指向链表头节点，用于定位插入位置
    LinkNode* ptmp = pins->next; // 定义指针ptmp，指向头节点的下一个节点，作为待插入节点
    LinkNode* next = ptmp->next; // 定义指针next，指向ptmp的下一个节点，用于保存ptmp后续节点，防止链表断裂
    ptmp->next = NULL; // 将待插入节点ptmp的next指针置空，使其暂时脱离原链表
    ll->head->next = NULL; // 将原链表头节点的next指针置空，原链表头节点成为新链表的第一个节点，且新链表初始只有这一个节点

    while(1) // 进入无限循环，用于遍历链表并进行插入排序
    {
        pins = ll->head; // 每次循环开始，将pins重新指向新链表头节点，从新链表头部开始寻找插入位置
        // 当pins后面还有节点，且待插入节点ptmp的年龄值大于pins节点和pins下一个节点的年龄值时
        while(pins->next && ptmp->data.age > pins->data.age && ptmp->data.age > pins->next->data.age) 
        {
            pins = pins->next; // 移动pins指针，向后寻找合适的插入位置
        }

        if(pins->data.age > ptmp->data.age) // 如果找到的位置pins节点的年龄值大于待插入节点ptmp的年龄值
        {
            ptmp->next = ll->head; // 将待插入节点ptmp的next指针指向新链表头节点
            ll->head = ptmp; // 更新新链表头节点为ptmp，即将ptmp插入到新链表头部
        }
        else // 否则（即pins节点的年龄值小于等于ptmp的年龄值）
        {
            ptmp->next = pins->next; // 将待插入节点ptmp的next指针指向pins的下一个节点
            pins->next = ptmp; // 将pins的next指针指向ptmp，即将ptmp插入到pins之后
        }
        ptmp = next; // 将ptmp指针移动到原本保存的下一个节点next的位置，准备处理下一个待插入节点
        if(NULL == ptmp) // 如果ptmp指向NULL，说明已经处理完所有节点
        {
            break; // 跳出循环
        }
        next = next->next; // 将next指针移动到ptmp当前指向节点的下一个节点，为下一轮循环保存后续节点
        ptmp->next = NULL; // 将待插入节点ptmp的next指针置空，使其暂时脱离原链表
    }
    return ll; // 返回排序后的链表头指针
}

三、顺序表和链表对比

1、存储方式
        顺序表 是一段连续的存储单元
        链表 是逻辑结构连续物理结构（在内存中的表现形式）不连续（因为是通过malloc获得的）

2、 时间性能
        查找 ：          顺序表O(1)      //按规则放，找的时候按规则找；支持随机访问

                              链表  O(n)        //只能从第一个往后找

        插入和删除：顺序表 O(n)      //整体前移与后移

                             链表   O(1)        //一次性改（只需把一个节点连上），与链表数据量无关

3、 空间性能
        顺序表 需要预先分配空间，大小固定；只放数据
        链表， 不需要预先分配，大小可变，动态分配；数据 + 指针域

四、循环链表

       1、 简单的来说，就是将原来单链表中最有一个元素的next指针指向第一个元素或

头结点，链表就成了一个环，头尾相连，就成了循环链表。circultlar linker list.

       2、  注意非空表，和空表。多数会加入头结点。

       3、 原来结束的条件是 p->next != NULL ------->>>>> p-next != Head 

4、练习：判断链表是否有环（用快慢指针）

int IsRingLinkList(LinkList* ll)  

// 定义函数判断链表是否有环，参数为链表指针，返回整型（0表示无环，1表示有环）
{
        LinkNode* fast = ll->head;  // 定义快指针fast，初始指向链表头节点
        LinkNode* slow = ll->head;  // 定义慢指针slow，初始也指向链表头节点
 
        while (fast)  // 当快指针不为空时进入循环（快指针为空时说明已遍历到链表末尾，无环）
        {
                fast = fast->next;  // 快指针先移动一步（每次移动两步的第一步）
                if (NULL == fast)  // 检查快指针移动后是否为空
                {
                        return 0;  // 若为空，说明链表无环，返回0
                }
 
                if (slow == fast)  // 检查慢指针和快指针是否相遇（相遇则说明有环）
                {
                return 1;  // 若相遇，返回1表示有环
                }
                fast = fast->next;  // 快指针再移动一步（完成每次移动两步）
                slow = slow->next;  // 慢指针每次移动一步
        }
        return 0;  // 循环结束后仍未相遇，说明链表无环，返回0
}