首页 > 其他分享 >PA0:关于剩余练习2

PA0:关于剩余练习2

时间:2024-01-19 15:58:51浏览次数:26  
标签:PA0 剩余 cur List 练习 list count 链表 指针

32、

双向链表在多数时候都优于单向链表,双向链表意味着它可以方便地访问自己的前驱节点和后继节点,代价只是多占用一点空间给指针。此外,作者也对应配了头指针和尾指针,在作者的例子里还有pop和push,那双指针就显得很重要了,单链表配单指针,会让pop和push变得更耗时间。

 

先看头文件部分

#define List_count(A) ((A)->count)

#define List_first(A) ((A)->first != NULL ? (A)->first->value : NULL)

#define List_last(A) ((A)->last != NULL ? (A)->last->value : NULL)    这个写法值得学习一下,在前面已经对结构体进行了定义,这里的宏就是直接把 链表元素数、首个元素值和最后元素值包装了起来。之后用前面的形式,看起来更加直观。

除此之外,后面还有一段宏,

#define LIST_FOREACH(L, S, M, V) ListNode *_node = NULL;\

    ListNode *V = NULL;\

    for(V = _node = L->S; _node != NULL; V = _node = _node->M)

  说实话以前没见过这种写法。在后面函数里,需要多次写循环体,作者在这里就用一个宏来替代后面的循环,要循环的时候直接list_foreach就行。在前两行代码的后面有斜杠,表示代码还没写完,后面还是代码。这段代码的用法就是直接在后文里需要用循环体的地方直接替换,充当循环。for循环条件里面的连等是同时对前面的所有变量赋相同的值,比如给V和_node同时赋值L-->S.

  关于循环里面的字母,L代表头指针,存储链表头结点地址;S是头结点里指向第一个节点的指针的名字,M是节点里指向下个节点的指针的名字,V是用来储存当前正在遍历节点的指针变量。 C语言里并没有规定字母必须是什么意思,这里只是我们人为地赋予了这个含义。需要注意的是,编译器不会检查到底输入了什么,所以字母对应位置输入别的也行,但是会报错。

  在实际代码中也可以看到这段宏的效果:

 LIST_FOREACH(list, first, next, cur) {
        if(cur->prev) {
            free(cur->prev);
        }
    }

就这样遍历释放掉了链表。

 

再看代码部分,

calloc(num,size)   连续分配num个size的连续空间   之后就是链表相关函数的具体代码。

void List_destroy(List *list)
{
    LIST_FOREACH(list, first, next, cur) {
        if(cur->prev) {
            free(cur->prev);
        }
    }

    free(list->last);
    free(list);
}  //逐个检查有没有前驱节点,有就销毁,最后再单独处理掉尾节点

 

关于单元测试这一块,项目没有要求,所以中间的就先跳过了,之后有空闲的时候再抽需要的回看。从代码上看,就是使用断言功能,对每一项函数进行功能测试。注意断言需要-g,没有debug项的话,断言功能会被自动忽略。 

尝试学习代码,对count计数进行检测:

char *test_count()
{
    // 测试count功能  假设一开始L链表内为空
    List_unshift(list, test1); //快速向头部增加元素
    mu_assert(count == 1, " Wrong count after operation ");

    List_unshift(list, test2);
    mu_assert(count == 2, " Wrong count after operation ");

    List_unshift(list, test3);
    mu_assert(count == 3, " Wrong count after operation ");

    count=-count;
    mu_assert(count == -3, “Wrong count after operation”);
    return NULL;
}

 

------------练习33----

链表冒泡相对来说比较好做,链表归并,说实话归并排序我平时没有用过,只是知道原理,要用起来还是第一次:

int List_bubble_sort(List *list,List_compare cmp)
{
    int length=List_count(list);
    if(length<=1) 
    {
        die("too few");
    } //只有一个元素,那也报错,没有必要排序
    //不过有必要考虑<0吗?因为count不应该出现小于0的情况 
    int i,j;
    ListNode *cur=list->next;   //我的代码没有用foreach宏,所以要单独定义 
    for(i=0;i<length;i++)
    {
        for(j=0;j<length-1;j++)
        {
            if(cmp(cur->value,cur->next->value)>0)//用cmp,这样之后方便换升降序 
            {
                ListNode_swap(cur,cur->next); //交换节点内容 
                cur=cur->next; //指针前进 
            }
        }
        cur=list->next;//走完一轮,cur指针要回到首位 
    } 
    
}  //链表冒泡排序 

值得一提的是,我看了作者给出的样例代码,按照这种写法,似乎冒泡只执行了一层,但冒泡应该是有两层循环才有效果。不知道是不是哪里看漏了。

链表这种逻辑结构,相比于数组,并不适合用于排序和读写,因为数组在逻辑上是连续的,支持随机读写,但链表不行,不管是只有头指针还是首尾指针都有,都没办法做到随机存取。进行排序时要自己维护链表,所以就显得十分麻烦。

标签:PA0,剩余,cur,List,练习,list,count,链表,指针
From: https://www.cnblogs.com/namezhyp/p/17973103

相关文章

  • 31.定语从句-定语从句的练习-2
    穿自己的鞋不仅方便,而且还确保一点不用管别人的感受。先找主谓宾——不仅。。。而且(notnoly...butalso)连接的2个句子 不用管别人的感受是来解释一点的同位语Wearingmyownshoesis(proves)notonlyconvenientbutalsoensuresapointthatthefellingsofothersc......
  • 有趣的小练习(持续更新~)
    有趣的小练习使用生成器实现range()函数defmy_range(start,stop=None,step=1):ifnotstop:#如果只传了一个参数,就调整参数stop=start#相当于start=0,stop=传的值start=0whilestart<stop:#只要start小于stop就执行输出语句......
  • 练习1:面向对象
    使用面向对象的思想,编写自定义描述狗的信息。设定属性包括:品种,年龄,心情,名字;方法包括:叫,跑。要求:设置属性的私有访问权限,通过公有的get,set方法实现对属性的访问限定心情只能有“心情好”和“心情不好”两种情况,如果无效输入进行提示,默认设置“心情好”。设置构造......
  • 练习2:面向对象
    以面向对象的思想,编写自定义类描述ITpractitioner。设定属性包括:姓名,年龄,技术方向,工作年限,工作单位和职务;方法包括:工作要求:1)设置属性的私有访问权限,通过公有的get,set方法实现对属性的访问2)限定IT从业人员必须年满15岁,无效信息需提示,并设置默认年龄为15。3)......
  • 练习3:面向对象
    #请使用面向对象的思想,设计自定义类,描述出租车和家用轿车的信息。设定1)出租车类:属性包括:车型,车牌,所属出租公司;方法包括:启动,停止2)家用轿车类:属性包括:车型,车牌,车主姓名;方法包括:启动,停止要求1)分析出租车和家用轿车的公共成员,提取出父类—汽车类2)利用继承机制,实现出......
  • 30.定语从句-定语从句的练习-1
    练习夜莺用生命换来的玫瑰花被扔掉了Therose___that/which___thenightingale(夜莺)exchangedwithhislifewasdiscarded(抛弃,扔掉)。 withhislifewasdiscarded——是介词短语,不能做宾语。 这些圆顶的建筑物看起来很漂亮。Buildings____whose___roofsareroun......
  • 练习
    在控制台中输出99乘法表(做出之后,想一想能不能使用一行代码生成)双重for循环forjinrange(5):#外层for循环控制的行数foriinrange(5):#内层for循环控制的列数print('*',end='\t')print()print("------------------------------------------------")需求:打印三角......
  • 函数练习1
    练习:定义一个函数,函数接收2个参数,第一个参数是一个大字符串,第二个参数是一个字符,函数功能是判断该字符在大字符串中出现的次数defget_str_count(big_str,s):count=0foriinbig_str:ifi==s:count+=1print(f'{s}字符在大字符串中共出现了{count}次。。')get_str_count(......
  • 练习题1
    使用面向对象的思想,编写自定义描述狗的信息。设定属性包括:品种,年龄,心情,名字;方法包括:叫,跑。要求:1)设置属性的私有访问权限,通过公有的get,set方法实现对属性的访问2)限定心情只能有“心情好”和“心情不好”两种情况,如果无效输入进行提示,默认设置“心情好”。3)设置构造......
  • PA0:关于练习题
    练习11: 附加题:复制操作:i=0;while(i<argc){states[i]=argv[i];i++;}如果还要考虑安全性,那就在循环体里面增加判断:i=0;j=0;while(i<argc){states[i]=argv[i];i++;j++;if(j>=......