[练习33]链表算法: 冒泡排序，合并排序（单元测试）

通过“愚蠢的方式”“学习C的艰难方式”

链接列表对排序非常不利. 如果需要排序，我们还有其他更好的数据结构可用. 之所以使用这两种算法，是因为使用链表来实现它们要困难一些c语言单链表冒泡排序，并且还可以让您考虑如何更有效地执行链表操作.

首先c语言单链表冒泡排序，布局文件list_algos.h，list_algos.c，list_algos_tests.c

liblcthw$ ls -R
.:
bin  LICENSE  Makefile  README.md  src  tests
./bin:
./src:
lcthw
./src/lcthw:
dbg.h  list_algos.c  list_algos.h  list.c  list.h
./tests:
list_algos_tests.c  list_tests.c  minunit.h  runtests.sh

[1] 打开 wiki 的页面，例如：冒泡排序（bubble sort）
[2] 阅读算法描述，观察图例
[3] 在纸上画出大致算法排序过程
[4] 回到wiki页面，复制、粘贴 “伪代码”（非C代码）到`list_algos.c`的冒泡函数里
[5] 把 伪代码 翻译成 C代码
[6] 使用单元测试来保证函数正常工作
[7] 重复步骤[5]~[6] 直到测试通过
[8] 添加更多测试，用来检测边缘情况，例如：空链表、已经排序过的链表等
[9] 实在做不出来可以“作弊”，看liblcthw库里的代码

anno-m:~/Desktop/liblcthw$ make
cc -g -O2 -Wall -Wextra -Isrc -rdynamic -DNDEBUG  -fPIC   -c -o src/lcthw/list_algos.o src/lcthw/list_algos.c
cc -g -O2 -Wall -Wextra -Isrc -rdynamic -DNDEBUG  -fPIC   -c -o src/lcthw/list.o src/lcthw/list.c
ar rcs build/liblcthw.a src/lcthw/list_algos.o src/lcthw/list.o
ranlib build/liblcthw.a
cc -shared -o build/liblcthw.so src/lcthw/list_algos.o src/lcthw/list.o
cc -g -O2 -Wall -Wextra -Isrc -rdynamic -DNDEBUG     tests/list_algos_tests.c  -ldl build/liblcthw.a -o tests/list_algos_tests
cc -g -O2 -Wall -Wextra -Isrc -rdynamic -DNDEBUG     tests/list_tests.c  -ldl build/liblcthw.a -o tests/list_tests
sh ./tests/runtests.sh
Running unit tests:
----
RUNNING: ./tests/list_algos_tests
ALL TESTS PASSED
Tests run: 2
tests/list_algos_tests PASS
----
RUNNING: ./tests/list_tests
ALL TESTS PASSED
Tests run: 6
tests/list_tests PASS

typedef int (*List_compare) (const void *a, const void *b);

int List_bubble_sort(List * list, List_compare cmp)
{
  // . . . 
      if (cmp(cur->value, cur->next->value) > 0) {
 // . . .
}

char *test_bubble_sort()
{
// . . . 
    int rc = List_bubble_sort(words, (List_compare) strcmp);
// . . .
}

返回值

如果lhs按字典顺序在rhs中首先出现，则为负.

如果lhs和rhs相等，则它们为零.

如果按字典顺序在rhs之后出现lhs，则为正值.

/*****    list_algos.c    *****/
inline void ListNode_swap(ListNode * a, ListNode * b)
{
    void *temp = a->value;
    a->value = b->value;
    b->value = temp;
}

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-227284-1.html