在C这种没有提供基础数据结构的语言里,最适合自己来学习链表的结构了。
在上次学C的时候,知道了链表的基础,所以写起来还是比较简单的。最基础的单项链表,每一个节点存储数据和指向下一个节点的指针就可以了。
在制作链表的时候,如果使用typedef,一定要给结构起一个名字,因为之后要包含同种类型的指针,会反复使用到。
创建链表和遍历
最简单的单链表,每个节点指向下一个链表,如果没有,就指向NULL。
在遍历的时候,时刻检查当前节点的下一个是不是NULL,是的话说明到达了链表的底部。
#include "chapter06/linkedlist.h" void walk(struct island * islands){ for (; islands != NULL; islands=islands->next) { printf("%s %s %s\n", islands->name, islands->opens, islands->closes); } } int main(int argc, char *argv[]){ //创建四个结构 island island1 = {"island1", "09:00", "17:00", NULL}; island island2 = {"island2", "08:00", "18:00", NULL}; island island3 = {"island3", "10:00", "16:00", NULL}; island island4 = {"island4", "09:00", "15:00", NULL}; //链在一起 island1.next = &island2; island2.next = &island3; island3.next = &island4; //用指向第一个节点的指针当做整个链表的指针 island *linked_islands = &island1; //遍历链表 walk(linked_islands); }
单链表直接就用指针遍历就可以了,如果当前指针不是null,说明至少存在一个节点,处理完当前节点的数据后,将指针指向next,这样继续判断,如果是NULL了,说明已经遍历完了所有节点。
动态内存分配
在上边的程序中,实际上是写死了4个节点,编译器已经为这个四个节点分配完了空间。
在现实里,可能不知道会有几个节点,需要动态的扩展内存,此时就要使用stdlib.h
标准库中的malloc
和free
函数用来动态申请内存和释放内存了。
先来创建一个返回一个新建岛的函数:
island * create_new_island(char * name){ //将void * 指针赋值给 island * 指针 island *i = malloc(sizeof(island)); i->name = name; i->opens = "09:00"; i->closes = "18:30"; i->next = NULL; return i; }
malloc返回的是一个通用指针类型,也就是void * 类型,实际上malloc只是按照大小来申请,所以需要将其转换成我们需要的类型。
为了验证可以动态添加,来让用户输入名称:
//动态输入2个岛名字 char name[80]; scanf("%s", name); island *i1 = create_new_island(name); scanf("%s", name); island *i2 = create_new_island(name); island5.next = i1; i1->next = i2; //遍历链表 walk(linked_islands);
但是遍历之后,发现两个岛的名字是一样的,这是因为我们使用了同一个char 数组指针,只要修改了其中一个,另外一个也会修改,这里可以使用一个新的库函数:string.h
库中的strdup()
函数。
这个函数接受一个char*,然后会将其中的内容复制到堆上,之后返回一个指向这个字符串。注意,由于这个也是动态申请的字符,所以一样需要释放。
然后来修改新建岛的代码:
island * create_new_island(char * name){
island *i = malloc(sizeof(island));
i->name = strdup(name);
i->opens = "09:00";
i->closes = "18:30";
i->next = NULL;
return i;
}
这里其他的内容我们都传入了字符串字面量也就是常量,所以没有问题(这里没有用fgets是因为会读取换行符)。
之后就可以用全部动态的方式来组成链表了。组成的方式是:首先用一个指针当做链表的头部,设置初始值为NULL。生成第一个节点的时候,这个指针就指向其,然后不再变动。
再使用第二个指针表示链表的尾部,最开始的时候也指指向NULL。在第一次新增的时候,指向第一个节点。之后新增加一个节点的时候,先把自己当前指向的节点的next指向下一个节点,然后自己去指向下一个节点也就是最后一个节点。
int main(int argc, char *argv[]){ island *start = NULL; island *current = NULL; island *end = NULL; char name[6]; name[0] = 'c'; name[1] = 'o'; name[2] = 'n'; name[3] = 'y'; name[5] = '\0'; int j = 33; for (; j < 127; j++) { name[4] = (char) j; current = create_new_island(name); if (start == NULL) { start = current; end = start; } end->next = current; end = end->next; } walk(start); }
这里只是一个最简单的用链表存储内容。这里还没有用到增删改查,实际上用到增删改查的时候,选择指针指向那个元素很重要。比如删除的时候,就不能仅仅只用最后一个指针,这样无法完成操作。要遍历到next的next为null,也就是倒数第二个才可以,然后先回收最后一个,然后将倒数第二个的next置为NULL。
释放链表
有了新建链表,就要释放链表,注意释放的顺序很重要。
首先是节点里的字符串释放,一个字符串放在堆上,要先释放,否则释放链表的节点之后就要失去对这个字符串的引用。
第二是释放链表的顺序,在链表生成的时候,是一个一个链上去,那需要一个一个从尾部释放吗。
如果需要一次性释放全部的链表,是不需要的,只需要从最前边开始,用两个指针,一个指向当前,一个指向下一个,先释放当前,然后让当前的指针指向下一个,下一个指向再下一个,再释放当前,一直到当前的指针为NULL为止。
void releaseall(island * linked_island){ island *current = NULL; island *next = NULL; if (linked_island == NULL) { return; } else{ current = linked_island; } while (current != NULL) { free(current->name); next = current->next; free(current); current = next; } printf("释放完成\n"); }
Head First C的书里代码和这个逻辑一样,只不过将每个循环最后都做的current = next;
放到for循环体里,看着更简明。
这是按顺序释放一整条链表。如果从链表中删除元素,就不能简单的这么操作了,必须有一个引用指向被删除的元素,释放完字符串和节点才行。
这就是最基础的数据结构了。待之后到专门的数据结构C语言实现中再来看。
感觉读入字符串的玩意也很绕,fgets,get,和scanf也各不相同。