一个博客

随便写写

0%

链表的部分函数实现（一）

发表于 更新于

之前我们已经完成了链表的基本函数，现在再来实现一些其他的功能。

链表头保存数据大小

这个是可选的，因为突然想到，所以就加进来了。一般链表保存的都是同一种类型的数据，所以它们应该具有相同的大小（如果大小真的不同那就保存指针，指针大小都是相同的），而且链表保存的数据类型在创建时就可以确定，所以我们可以在LinkListHeader里面增加一个成员变量size来保存一个数据的大小，这样就只需要在创建链表的时候指定一次大小，往后的操作都不需要额外传入数据的大小了，这样一行的长度就可以短一些，但是需要写一个函数来获取数据的大小，因为整体比较简单，就不贴代码了。

链表的遍历

链表也是一个数组，数组最常用的一个操作应该是遍历，所以还需要实现链表的遍历。直接按索引用for循环来遍历当然也可以，但是通过索引查找数据会重复遍历很多次，性能会很差，所以最好不要通过索引遍历。当然还有可能会这样写for(Node *p = l->next; p != l; p = p->next)这样就不会有上面的问题，但是根据操作的规范，我们不应该直接操作结构的内部数据，应该将它当作黑箱，只使用它的接口。所以我的想法就是为节点也实现几个接口。

Node的接口

首先应该给节点增加Next和Previous操作，但是我这个是循环链表，还需要判断指向的是不是头节点，要解决这个问题有两种方法：

  1. 给头节点新增一个parent节点，用于保存头节点，然后将头节点的parent设为NULL，这样就可以很好的辨别头节点了，缺点是节点的成员变量从3个变成了4个，所占的空间增加了33%。
  2. Next和Previous增加一个参数，传递头节点，然后判断返回的节点不为头节点，缺点是多一个参数，而且不好看，反直觉，要是长期使用，那就不应该写得这么奇怪。

这里我选择了第一种，增加parent节点，并且为Node新建一个头文件和c文件，将节点和链表分离，因为事到如今我觉得这个节点不再是链表的附庸了，它也有了自己的函数，和自己的作用，所以是时候把它从链表的文件里分离出来了。

Node的接口也很简单，就是对每个成员变量写个Get/Set，就完成了，因为过于简单繁琐，就不贴代码了，以后有空再把链表里面所有的->都改用Node的接口实现。然后给出个用Node遍历的示范，代码如下：

1
for(Node *p = LinkListGetFront(l); NodeGetParent(p); p = NodeGetNext(p))

写到一半人就犯懒了，如果以后每次都写这么长一个for那人肯定会疯掉，这里面有价值的就两个东西，遍历的变量名，也就是p，还有起始位置，所以我们再写个define，代码如下：

1
#define LinkListFor(p,q) for(Node *p = q; NodeGetParent(p); p = NodeGetNext(p))

p为循环用的变量名，q为起始位置。下面附带个反向版本的：
如下：

1
#define LinkListForReverse(p,q) for(Node *p = q; NodeGetParent(p); p = NodeGetPrevious(p))

用函数指针遍历链表

之前看的教材是让函数接受一个函数指针作为参数，然后遍历每个节点的数据对其调用那个函数，但是遍历能做的事情太多了，而且会返回不同数量的值，要实现起来很复杂，所以我一开始没想用这种方式，直到我发现：

1
2
3
4
5
6
7
8
9
10
11
12
#include<stdio.h>
int main()
{
	int a=0;
	void p()
	{
		printf("%d",a);
		a++;
	}
	p();p();p();
	return 0;
}

这段代码居然编译通过了，而且返回012，这就说明函数内可以定义函数，据我猜测应该是局部函数，这个p只能在main内调用，并且可以修改main内的局部变量。如果是这样那就可以在遍历时通过修改局部变量来实现不同的返回值，然后传入的函数返回值为int，这样可以实现break，当返回值非0时终止遍历，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void LinkListEach(LinkList l, int (*fun)(void *))
{
    if (LinkListIsEmpty(l))
    {
        return;
    }
    Node *a = l->next;
    while (a != l)
    {
        if(fun(a->data))
        {
            return;
        }
        a = a->next;
    }
}

下面给出一个使用示范，遍历链表求最大值，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include "LinkList.h"
#include <stdio.h>
int main()
{
    int m=0;
    LinkList l;
    LinkListCreate(&l,sizeof(int));
    for (int i = 0; i < 10; i++)
    {
        LinkListInsertTail(l, &i);
    }
	int fun(void* data)
	{
		int n=*(int*)data;
		m=n>m?n:m;
		return 0;
	};
    LinkListEach(l, fun);
	printf("%d\n",m);
    return 0;
}

写这段示范的时候已经把下面的想法之一，用链表头保存数据大小实现了，所以跟之前的写法不一样。

嗯……以上代码编译通过了，但是报警告了，但是运行结果符合预期，警告还不知道什么意思，以后再了解，应该是函数作用域的问题。

再附带个反向遍历的，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void LinkListEachReverse(LinkList l, int (*fun)(void *))
{
    if (LinkListIsEmpty(l))
    {
        return;
    }
    Node *a = l->pre;
    while (a != l)
    {
        if(fun(a->data))
        {
            return;
        }
        a = a->pre;
    }
}

希望不会有机会用到这个函数，其实只用LinkListFor应该就够了。但是可以不用，但是不能没有。

链表的交换

交换数组中两个值也是数组的常用操作，链表的交换操作也可以有很多实现，例如自己写个交换两个void*的变量的值的函数，然后用LinkListGetData获取变量的值作为参数，但是我现在也没有自己的swap函数，而且为了使用方便，还是为链表写个交换函数吧，代码如下：

1
2
3
4
5
6
void LinkListSwap(void *a, void *b)
{
    void *d = a;
    a = b;
    b = d;
}

链表的排序

排序也是数组的重要操作之一，其实C语言带有个叫做qsort的快速排序，但是这个只能排序连续的数组，不能排序链表，用上面的函数手动实现好像也可以，但是写起来太麻烦了，所以也封装成函数。不过本人学艺不精，只会冒泡排序、选择排序和归并排序，而且归并排序写起来太麻烦了，所以这里先用个选择排序占位，反正就是，可以不用，但不能没有。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void LinkListSort(LinkList l, int (*fun) (void*, void*))
{
    LinkListFor(p, LinkListGetFront(l))
    {
        void *d = NodeGetData(p);
        void *a = d;
        LinkListFor(q, NodeGetNext(p))
        {
            void *b = NodeGetData(q);
            a = fun(a, b) ? a : b;
        }
        if(a != d)
        {
            LinkListSwap(a, d);
        }
    }
}

看见这个东西，我觉得还不如将链表转换为连续的数组，然后对它用qsort，所以接下来就写个将链表转换成数组的函数。