数据结构--链表
网上关于链表的文章很多，比我写的好的前辈也多不胜数。工作一年总是感觉前面学的后面忘，于是就诞生了写博客的想法，把自己的工作学习历程记下来互勉。思来想去还是把链表作为我的处女博吧，毕竟这是我踏入程序员路上写的第一个数据结构，以下内容在忐忑、羞射的心情下编写。如果有什么不能忍的地方欢迎大家指正!
–与链表无关纯属矫情
谈到链表之前，就想先说一下线性表。线性表是最基本、也是最常用的一种数据结构。一个线性表是多个数据的集合，除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。线性表有两种存储方式，一种是顺序存储结构，另一种是链式存储结构。
我们常用的数组就是一种典型的顺序存储结构。链表就是下面要详细说的链式存储结构。
顺序存储结构就是两个相邻的元素在内存中也是相邻的，这种存储方式的优点是查询比较方便，通过首地址和偏移量就可以访问到某个元素，匹配的查找算法也有好多，最快的可以达到O(logn)。缺点是插入删除很不方便，复杂度最坏能达到O(n)，例如你想在某个位置插入/删除元素，你需要将这个位置之后的所有元素都后移/前移一位。另外一个不方便的地方是元素数量的确定，必须在使用前创建一个足够大的数组放置所有的元素，但是开辟的数组空间往往不能够充分的利用造成资源浪费。
链式存储结构就是相邻的两个元素在内存中不一定相邻，这种存储方式的优点是只需要操作指针就可以添加删除元素，比较方便，时间复杂度为O(1)；另外一个优点就是节省内存，元素在需要添加的时候才开辟内存，不需要的时候就释放，也不需要事先预估元素的数量，相对于顺序存储结构要灵活许多。缺点就是查找的算法比较少，一般只能通过遍历查找，时间复杂度为O(n)，还有一个缺点就是申请或者释放内存会消耗时间，如果频繁的对内存申请释放，消耗的时间是很可观的。
链表中的元素称为结点，一般由两部分组成：指针域和值域，值域可以是基本数据类型也可以是结构体等复杂数据类型，存放需要的具体数据；指针域为指向下一个节点的指针。根据指针域的不同链表可以分为单向链表，双向链表，循环链表等等。
如上图所示就是一个由四个节点组成的单向链表，其中每个Data和Next为一个节点，第一个节点称为头节点，最后一个节点称为尾节点，Head为一个指向头节点的指针。Data为节点的值域，用来存放数据；Next为节点的指针域，指向下一个节点。尾节点的指针域为空。
链表的操作主要是围绕着指针域和对内存的申请释放进行，一般的操作就是增、删、改、查。头节点可以与其他的节点数据类型不同，头节点的值域中可以存放一些链表的信息，比如说链表的长度，创建时间，创建人等等。
下面还是以一个简单的C程序来具体操作一下。
整个程序由三个文件组成Chain——chain.h 存放一些类型、函数等的声明
|——chain.c 存放函数的具体实现
|——main.c 调用、测试实现的函数
|____Makefile MakeFile文件，编译的时候使用，如果是初次接触的话请忽略，后续的博客中会更新。
以下为chain.h文件
#ifndef _CHAIN_H_ #define _CHAIN_H_ /*声明一些数据类型*/ typedef int datatype;//声明链表存储的数据类型 typedef unsigned short uint16; typedef unsigned char bool; /*返回结果*/ typedef enum { TRUE, FALSE }bool_val; /*声明链表节点*/ typedef struct node { datatype data; struct node* next; }ListNode; /*声明链表头*/ typedef struct head { char info[20]; unsigned short length; ListNode* next; }ListHead; /*一下为一些链表操作函数的声明*/ ListHead* CreateList();//创建链表 bool ViewList(ListHead* head);//遍历链表 bool AddNodeByLoc(ListHead* head, uint16 loc, datatype data);//在指定位置添加节点 bool DelNodeByLoc(ListHead* head, uint16 loc);//删除指定位置的节点 bool ModNodeByLoc(ListHead* head, uint16 loc, datatype data);//修改指定位置的节点数据 datatype FindDataByLoc(ListHead* head, uint16 loc);//返回指定位置的节点数据 bool DestoryList(ListHead* head);//销毁链表 #endif
chain.h
以下为chain.c文件
#include <stdio.h> #include <stdlib.h> #include <string.h> #include "chain.h" /*创建链表*/ ListHead* CreateList() { ListHead* head = NULL; head = (ListHead*)malloc(sizeof(ListHead)); //申请内存 memset(head, 0, sizeof(head)); /*初始化链表信息*/ head -> length = 0; strcpy(head -> info, "CangLing's List"); head -> next = NULL; return head; } /*遍历链表*/ bool ViewList(ListHead* head) { /*合法性判断*/ if(head == NULL) { return FALSE; } ListNode* p = NULL; /*打印链表信息*/ printf("The List Info is %s\n",head -> info); printf("The List Length is %d\n",head -> length); /*输出节点内容*/ p = head -> next; while(p != NULL) { printf("%d\n",p -> data); p = p -> next; } return TRUE; } /*根据位置添加节点，大于链表长度的位置添加在链表末尾*/ bool AddNodeByLoc(ListHead* head, uint16 loc, datatype data) { /*合法性判断*/ if((head == NULL) || (loc == 0)) { return FALSE; } bool_val ret = FALSE; ListNode* node = head -> next; ListNode* tmp = NULL; /*初始化要创建的节点*/ ListNode* p = (ListNode*)malloc(sizeof(ListNode)); p -> data = data; p -> next = NULL; if(head -> length == 0)//对只有头节点的链表进行处理 { head -> next = p; p -> next = NULL; } else if(loc <= head -> length)//对1<loc<length的情况进行处理 { /*添加在头节点之后*/ if(loc == 1) { head -> next = p; p -> next = node; } else { /*寻找对应位置的前一个节点*/ while(loc > 2) { loc--; node = node -> next; } tmp = node -> next;//保存loc位置的节点地址 node -> next = p;//将要添加的节点放在loc位置 p -> next = tmp; } } else//对loc>length的情况进行处理 { while(node -> next != NULL) { node = node -> next; } node -> next = p; } head -> length++;//修改链表信息 ret = TRUE; return ret; } /*删除loc位置的节点*/ bool DelNodeByLoc(ListHead* head, uint16 loc) { /*进行合法性判断*/ if((head == NULL) || (loc == 0) || (loc > head -> length)) { return FALSE; } bool_val ret = FALSE; ListNode* tmp = head -> next; ListNode* freenode = NULL; if(loc == 1)//针对第一个节点的处理 { freenode = tmp; head -> next = tmp -> next; } else//对1<loc<length的情况进行处理 { while(loc > 2)//找到loc的前一个节点 { loc--; tmp = tmp -> next; } freenode = tmp -> next;//保存要释放的节点地址 tmp -> next = freenode -> next; } /*释放节点并修改链表信息*/ free(freenode); head -> length --; return ret; } /*修改loc位置的节点信息*/ bool ModNodeByLoc(ListHead* head, uint16 loc, datatype data) { /*合法性判断*/ if((head == NULL) || (loc == 0) || (loc > head -> length)) { return FALSE; } bool_val ret = FALSE; ListNode* tmp = head -> next; while(loc > 1)//找到loc节点 { tmp = tmp -> next; loc --; } tmp -> data = data;//修改节点数据 return ret; } /*返回loc节点的数据*/ datatype FindDataByLoc(ListHead* head, uint16 loc) { /*合法性判断*/ if((head == NULL) || (loc == 0) || (loc > head -> length)) { return FALSE; } datatype ret = 0; ListNode* tmp = head -> next; while(loc > 1)//找到loc节点 { tmp = tmp -> next; loc --; } ret = tmp -> data; return ret; } bool DestoryList(ListHead* head) { ListNode* p = NULL; ListNode* node = NULL; if(head == NULL) { return TRUE; } /*释放除头节点之外的节点*/ p = head -> next; while(p != NULL) { node = p; p = p -> next; free(node); } /*释放头节点*/ free(head); return TRUE; }
chain.c
以下为main.c文件
#include <stdio.h> #include "chain.h" int main() { int i = 0; ListHead* head = NULL; head = CreateList();//创建链表 printf("Now we will Add four Nodes\n"); for(i = 1; i < 5; i++) { AddNodeByLoc(head, i, i);//添加链表节点 } ViewList(head);//遍历链表 printf("Now we will Delete the third Node\n"); DelNodeByLoc(head, 3);//删除链表的第三个节点 ViewList(head); printf("Now we will modify the third Node to 5\n"); ModNodeByLoc(head, 3, 5);//将第三个节点的信息修改为5 ViewList(head); printf("Now we will view the second Node\n"); printf("%d\n",FindDataByLoc(head, 2));//查看第二个节点的数据 DestoryList(head);//销毁链表 }
main.c
以下为MakeFile文件
main: chain.o main.o #生成main依赖的文件 #执行命令cc chain.o main.o -o main生成最终的可执行文件main cc chain.o main.o -o main main.o: main.c chain.h #生成main.o依赖的文件 chain.o: chain.c chain.h #生成chain.o依赖的文件 #删除生成的中间文件 clean: rm *.o main
MakeFile
上面的四个文件我在Linux的环境下使用，将上面的文件放在同一个文件夹下，输入make运行，完成后生成chain.o main.o以及可执行文件main，运行make clean清除三个编译生成的文件。
这里我简单说一下什么是Makefile。在Windows下编译工作都由IDE来完成，例如VC6.0编译工程，你不需要管文件之间的依赖关系。但是在Linux环境下这部分工作由MakeFile完成。MakeFile关系到整个工程的编译规则，一个工程下文件不计其数，按模块、类型、功能分放在不同的目录下，MakeFile指定了一系列规则来指定哪些文件先编译，哪些文件需要后编译，哪些文件需要重新编译，甚至还有一些更复杂的功能操作。它带来的好处就是“自动化编译”，一旦写好MakeFile文件，工程的编译只需要一个make命令，整个工程就会全自动编译。上面就是我为链表写的一个很简单的MakeFile文件，后续的博客中会更新MakeFile的相关用法。
如果很不习惯也可以直接运行编译命令gcc main.c chain.c -o main当然也可以直接复制三个文件的内容直接在VC6.0下运行，效果是一样的。
下面是链表运行的结果