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