线性结构--离散存储链表讲解

╰半橙微兮° 2022-03-18 02:07 223阅读 0赞

数据结构大体成上可以分成两种:  
  
1. 线性结构.  
2. 非线性结构( 树,图)  
  
**1. 什么是线性结构**  
       大概上可以这样定义: 加入所有的节点可以用一条直线连接起来. 就是线性结构...  
  
  
**2. 线性机构也可以分成两种:**  
       **1) 连续存储 (数组)**  
             也就是指每1个节点在物理内存上是相连的.  
  
     **  2) 离散存储(链表)**  
              节点在物理内存上并不一定相连, 而是利用指针来关联.

这篇文章主要讲的第二种.

**3. 链表的定义**

1.多个节点离散分配.

2.彼此通过指针相连.

3.每个节点只有1个前驱节点, 1个后续节点.

4.首节点没有前驱节点, 尾节点没有后续节点.

其中第1 2点也适用于树和图,   后面3 4点就用于区别树和图了.

**4.一些专业用语解析:**

**      1) 首节点:**

**                   **第一个存放有效数据的节点.

**      2)尾节点:**

**                   **最后一个存放有效数据的节点.尾节点的尾部指针为空

**       3) 头节点:**

**                   **第1个有效节点之前的那个节点.

头节点并不存放那个有效数据,  但是头节点跟后面每个节点的数据类型是一样的.

加头节点的目地主要是为了方便对链表的操作.

总之, 要注意头节点并不是首节点,  而是首节点前面的1个不存放有效数据的节点, 用于方便链表操作.

**4)头指针:**

**                  **指向头节点的指针, 也是头节点的地址

**5****)尾指针:**

**                  **指向尾节点的指针, 也是尾节点的地址

具体可以参考下图所

**5.确定1个链表所必须的几个参数**

首先: 如果是确定1个数组就必须知道数组的头指针 和 数组的长度.

但是链表是可以根据每个节点的尾部指针一直遍历下去, 如果遇到1个节点的尾部指针是空, 就认为它是尾节点.

如果希望通过1个函数来对数组进行处理,例如打印数组的函数,或者数组排序的函数,就要接受数组的头部指针,和数组的长度.

**       但是如果希望通过1个函数来对链表进行处理,**

**       则只需要1个参数:**

**                 就是链表的头部指针啦,  因为链表的长度等其他信息都可以推算出来的.**

**6. 如何用代码表示1个节点.**

**        **首先, 要明确两点:

1) 1个链表中每个节点的数据类型都是一样的.

2) 每个节点的数据都分两部分(域), 1是数据部分,  2是尾部指针.

所以结构体的数据类型不能是常规的数据类型(int /long / char 等) , 必须是结构体, 因为结构体才能可能有多个成员嘛.

而每个节点的尾部指针指向的是下1个相同类型的节点, 所以尾部指针的类型和结构体的类型是必须一样的.

struct person{
    		int id;
    		char name[16];
    		struct person * pnext;
    	};
    	
    	typedef struct person PERSON;

如上面代码,这样就定义了1个 简单的PERSON 类型的节点.

**7.链表的分类:**

**       7.1 单链表和双链表**

单链表中每1个只有1个指针域, 例如上面代码定义的就是单链表的结点

双链表中每个指针有2个指针域,   其中1个指针域指向下1个节点,  **另1个指向前1个结点.**

**       7.2 非循环链表和 循环链表**

这个容易理解,  如果尾节点的尾部指针指向首节点, 那么它就是1个循环链表.

**8.链表的一些算法:**

所谓算法就是对链表的一些操作了.

包括和很多种, 当然我只会实现几种最基本常用的算法:

新建1个链表

添加1个节点到尾部

插入节点

删除节点

遍历

查找某个节点

清空

销毁

求长度

排序

下面会对这些算法进行讲解和代码实现

**9. 1个单链表(非循环)容器的简单c语言实现例子**

**9.1. 编写头文件.**

**      **因为c语言并不是面向对象语言, 所以我们不能将编写好的链表容器作为1个类库, 所以要写个头文件,  那么别的文文件引用了这个头文件, 就可以使用这个链表容器了.

**     头文件代码如下:**

**     ****linklist1.h **

**//注意bool\_me.h 这是一个简单定义布尔类型 宏的头文件.**

#include "bool_me.h"
    #ifndef __LINKLIST1_H_H
    #define __LINKLIST1_H_H
    
    	struct person{
    		int id;
    		char name[16];
    		struct person * pnext;
    	};
    	
    	typedef struct person PERSON;
    
    	struct Link_person{   //just a struct for linklist,  it is not a node of linklist
    		PERSON * phead;   //address of the Headnode of linklist
    		PERSON * ptail;  // address of the tailnode, yes it's not a neccssity, but it can make the operation easily
    		int len; //numbers of the nodes which contains the userful data.it's not a neccssity, but it can make the operation easily
    		BOOL is_inited; // judge whether the linklist is inited
    	};
    		
    
    	typedef struct Link_person LINKPERSON;
    
    	//init a new block()
    	PERSON * person_new(int id,char *pname);
    
    	//init a Linklist
    	LINKPERSON * link_create(int len);
    
    	//judge whether the linklist is empty
    	BOOL link_is_empty(LINKPERSON * pLink);
    
    	//add a node to the tail of Linklist
    	BOOL link_add(LINKPERSON * plink, PERSON * pnode);
    	
       //traverse the linklist to print all of the node of linklist;
    	void link_traverse(LINKPERSON * pLink);
    
       //insert a node behind another node
    	BOOL link_insert(LINKPERSON * pLink, PERSON * pBefore, PERSON * pnode);
    	
       //insert a node behind another node
    	BOOL link_insertbyindex(LINKPERSON * pLink, int index, PERSON * pnode);
    
       //remove a node from the linklist
    	BOOL link_remove(LINKPERSON * pLink, PERSON * pnode);
    
       //delete a node from the linklist, and free the memory space of the node
    	BOOL link_delete(LINKPERSON * pLink, int index);
    	
    	//get a the index of a node, if not existed, return -1
    	int link_getindex(LINKPERSON * pLink, PERSON * pnode);
    	
    	//get the length of Linklist
    	int link_getlength(LINKPERSON * pLink);	
    
    	//clear a Linklist
    	BOOL link_clear(LINKPERSON * pLink);
     
    	//destroy a Linklist
    	BOOL link_free(LINKPERSON * pLink);
    	
    	//sort by id
    	void link_sort(LINKPERSON * pLink);
    
    	//get a node from linklist by index
    	PERSON * link_getnode(LINKPERSON * pLink, int index);
    
    #endif

讲解下,  这里我定义了两个结构体, 其中第1个结构体PERSON就是链表的节点类型

而第2个结构体LINKPERSON是1个链表本身的类型, 里面包含了链表的第1个(头节点)结构体的地址.  通常这个头节点是不存放有效数据的, 上面提过了.

第2个结构体里面存放了一些链表的关键信息, 虽然这些关键信息例如, 长度, 尾节点地址等都可以由头节点地址推算出来, 但是毕竟遍历推算是1个很浪费cpu时间的行为, 牺牲一些内存空间来方便运算啦

下面定义了若干提供给其他程序是使用的函数,  当然我这个例子是1个极其基本简单的例子, 也只会实现一些基本的功能的函数啦.

**9.2. 处理错误函数voidlink\_error();**

**         **恩, 虽然只是1个简单的实现例子, 但是国际惯例,我还是尽量写的专业一些吧..

代码如下:

**linklist1.c           //后面的函数都写在这个文件里**

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include "linklist1.h"
    
    static void link_error(const char * pErr);
    
    
    static void link_error(const char * pstr){
    	printf("%s\n", pstr);
    	exit(-1);
    }

**9.3. 创建1个新的节点函数 PERSON\* person\_new(int id,char\* pname)**

**        **为什么要专门写1个函数来创建node?

直接 PERSONnode1； 这样不就创建出1个结构体节点了吗?

没错, 但是这样创建的结构体变量是静态变量, 也就代表它所占的内存不能重复使用,  而且当这个节点被移除时, 它所占的内存也不能被清空啊.

所以我会单独写1个函数来创建1个新的节点

逻辑:

1.定义1个结构体指针

2. 为这个指针分配1块足够的内存

4. 给结构体的各成员赋值, 尾部指针为空指针.

3. 返回这个指针所指向的地址.

代码如下:

PERSON * person_new(int id, char * pname){
    	PERSON * pnode;
    	pnode = (PERSON *)malloc(sizeof(PERSON));
    	if (NULL == pnode){
    		link_error("fail to assign memory to PERSON");
    	}
    
    	pnode->id = id;
    	strcpy(pnode->name, pname);
    	pnode->pnext = NULL;
    	return pnode;
    }

**9.4.初始化(新建)1个链表函数 LINKPERSON \*link\_create(int len)**

**         **初始化1个链表,  其实这个逻辑不难理解,    至于为什么有1个参数len?   其实就是方便用户新建1个链表给这个链表分配数量为len的有效节点, 当然len 可以设成0啦, 这样这个链表就只有1个头节点了.

无非分如下若干步:

**         **1.新建1个链表类型(自定义 LINKPERSON)指针

**         **2.动态给这个指针分配1个内存.

3. 动态分配1个头节点, 地址赋给 上面的链表类型的第1个成员plist,  这个成员就指向头节点的地址. 头节点不存放有效数据, 但是尾部指针设为空

4.根据len参数动态分配若干个 有效节点, 挂到头节点后面.

5. 给链表类型的其他成员赋值

6. 最后返回这个链表类型的地址.

还是有点复杂啊..

代码如下:

LINKPERSON * link_create(int len){
    	LINKPERSON * pLink = (LINKPERSON *)malloc(sizeof(LINKPERSON));
    	if (NULL == pLink){
    		link_error("fail to assign memory to LINKPERSON");
    	}
    
    	PERSON * phead = (PERSON *)malloc(sizeof(PERSON));
    	if (NULL == phead){
    		link_error("fail to assign memory to headnode");
    	}
    
    	phead->pnext = NULL;
    	pLink->phead = phead;
    	pLink->ptail = phead;
    	pLink->len = 0;
    	pLink->is_inited = TRUE;
    
    	if (len==0){
    		return pLink;
    	}
    
    	int i;
    	char * name[16];
    	PERSON * pnode;
    	for(i=0;i<len;i++){
    		char name[16];
    		sprintf(name,"node%d",i+1);
    		pnode = person_new(i+1,name);
    		if (FALSE == link_add(pLink,pnode)){
    			link_error("fail to add nodes!");
    		}
    	}
    
    	return pLink;
    }

从代码可以见到, 无论初始长度len是否为0 我都会有定义1个头节点,  然后根据len的长度循环将存放数据的有效节点挂到链表的尾部.

而新建1个节点用的是 person\_new() 函数, 这个函数上面写过了.

而将1个节点挂到链表尾部我用的是link\_add() 函数, 这个函数头文件也提到的, 下面就会讲解如下实现这个函数.

**9.5.将1个节点添加到链表尾部末尾函数 BOOLlink\_add(LINKPERSON \* pLink, PERSON \* pnode)**

**      **首先, 这个要添加的节点最好是动态分配的, 也就是说用我上面的person\_new() 生成的. 否则当移除这个节点就无法释放它的内存了**.**

**      **而添加1个节点到链表尾部逻辑上是很简单的..

1. 链表的尾节点的尾部指针指向这个要添加的节点

2.这个节点的尾部指针设为NULL.

3. 链表成员len+1

但是实际上还是有另外需要注意的问题.

a. 就是如何获取尾节点?

这个当然可以用头节点逐个推算出来了..   但是我头文件提过, 为了方便操作, 我会把尾节点的地址也保存在链表类型的结构体成员中..

b.判断 链表内是否已经有这个节点.

这个就跟数组不同了. 数组是可以存放相同的数据的,例如Arr\_add(10),这个函数可以重复执行.

链表呢, 因为链表是由节点组成的, 而唯一标识节点的是节点的地址.

假如链表添加1个节点, 但是这个节点的地址已经在这个链表中的话就出现下图中的问题了:

如下图:

![1365354565_3298.png][]

所以这个函数会判断下这个节点是否在链表中, 还是要遍历一次啊..  有更好方法的可以告诉我..

代码如下:

BOOL link_add(LINKPERSON * pLink, PERSON * pnode){
    	if (TRUE != pLink->is_inited){
    		link_error("the linklist is not inited yet");
    	}
    
    	if (NULL == pnode){
    		printf("pnode is empty!\n");
    		return -1;
    	}
    	
    	//judge whether pnode is existed in the linklist already
    	if (link_getindex(pLink,pnode) > -1){
    		printf("the node is existed in linklist already!\n");
    		return FALSE;
    	}
    
    	pLink->ptail->pnext = pnode;
    	pnode->pnext = NULL;
    	pLink->ptail = pnode;
    	pLink->len++;
    	return TRUE;
    }

可以见到, 我并没有每次都遍历求出 尾节点的地址,  而是把尾节点地址放到 链表类型的1个成员中, 方便操作啊~

上面只所以说遍历了1次, 似乎因为执行力获取节点序号函数  link\_getindex(),如果这个节点不存在, 则返回0. 下面就是这个函数的写法.

**9.6.****获取1个节点在链表中的位置.    intlink\_getindex(LINKPERSON \* pLink,PERSON \* pnode)**

**       **注意这个函数也用与判断节点是否存于链表中,  如果存在就返回位置index, 不存在就返回-1.

逻辑上也很清楚,  冲首节点起(不是头节点), 逐个判断, 直到到达尾节点, 这个过程不需要关心链表的长度.

而且这个遍历不包括头节点,所以如果把头节点作为参数, 一样会返回 -1,因为头节点不是存放数据的有效节点.

代码如下:

int link_getindex(LINKPERSON * pLink, PERSON * pnode){
    	if (TRUE != pLink->is_inited){
    		link_error("the linklist is not inited yet");
    	}
    
    	if (NULL == pnode){
    		printf("pnode is empty!\n");
    		return -1;
    	}
    
    	PERSON * pn = pLink->phead;
    	int i=0;
    	while (NULL != pn->pnext){
    		if (pn == pnode){
    			return i;
    		}
    		i++;
    		pn = pn->pnext;
    	}
    
    	return -1;
    }

** **

**9.7.** **判断链表是否阿为空 BOOL link\_is\_empty(LINKPERSON \* pLink).**

**        **这个就毫无难度啦,只需判断链表内是否只有头节点就ok了.

当然, 为了方便操作, 也可以判断 链表成员len  是否等于0

BOOL link_is_empty(LINKPERSON * pLink){
    	if (TRUE != pLink->is_inited){
    		link_error("the linklist is not inited yet");
    	}
    
    	if (NULL == pLink->phead->pnext){
    		return TRUE;
    	}
    
    	return FALSE;
    }

**9.8.**** ****遍历输出链表函数. void link\_traverse(LINKPERSON \* pLink)**

**        **这个要注意的是, 实际上就是遍历链表, 然后逐个输出节点.

只需定义1个指针,首先指向首节点(头节点的下1个), 然后输出.

再把这个指针指向被输出的指针的后1个, 继续输出,直到尾部指针为空(尾节点).

所以这个过程根本不关心链表的长度的.

void link_traverse(LINKPERSON * pLink){
    	if (TRUE != pLink->is_inited){
    		link_error("the linklist is not inited yet");
    	}
    
    	if (TRUE == link_is_empty(pLink)){
    		printf("the linklist is emptyi!");
    		return;
    	}
    
    	PERSON * pnode;
    	pnode = pLink->phead;  //phead
    
    	while(NULL != pnode->pnext){
    		pnode = pnode->pnext;
    		person_print(pnode);
    	}
    	return;
    }

**9.9.**** ****打印1个节点的函数. void ****person\_print(PERSON \* pnode)**

**   **就是上面用的person\_print(pnode)啦, 太简单不讲解了

static void person_print(PERSON * pnode){
    	printf("id is %d, name is %s\n", pnode->id, pnode->name );
    }

**9.10.**** 根据序号获取1个节点函数 PERSON \* link\_get(LINKPERSON \* pLink, int index)**

**       **相对来讲，这个函数就跟简单了。

首先， 判断参数 index 的范围， 如果少于0 ， 或者大于链表当前个数-1 ， 则返回1个空指针。

链表的个数怎么求？  这时我链表类型的len成员就发挥作用了..虽然作用意义不是很大.

然后根据index的值  遍历若干次就得到想找的节点地址啦。

代码如下：

PERSON * link_getnode(LINKPERSON * pLink, int index){
    	if (TRUE != pLink->is_inited){
    		link_error("the linklist is not inited yet");
    	}
    
    	if ( index < 0 || index > (pLink->len -1)){
    		printf("index is over the limit!\n");
    		return NULL;	
    	}
    	
    	int i;
    	PERSON * pnode = pLink->phead;	
    	for( i=0;i <= index ;i++){
    		pnode = pnode->pnext;
    			
    	}  	
    
    	return pnode;
    }

**9.11.****插入1个节点到另1个节点之后的函数 link\_insert(LINKPERSON \*pLink, PERSON \* pBefore, PERSON \* pnode);**

**     **通常来讲,  链表是整个数据结构的重点,  而插入节点的操作就是链表的重点..

讲下原理,   假如要将参数中的 pnode 插入到 pBefore的后面.

假如原来的pBefore 的后面是 pAfter.

那么pBefore\->pnext == pAfter   这个很简单.

而现在要把pnode 放到 pBefore 和pAfter 之间.  则pnode 在 pAfter前面

所以要执行:

pnode->pnext = pBefore->pnext         //相当与 pnode->pnext = pAfter

![1365426372_5719.png][]

然后pBefore 的后面是pnode, 所以再执行

pBefore->pnext = pnode

![1365426538_4662.png][]

就完成插入了.

那么对于这个函数, 逻辑上包括如下几点:

0. 判断pBefore 和 pnode 不是空指针

1. 判断 pBefore 是否存在于链表中, 如果不存在, 返回false.

2. 判断 pnode 是否已经存在于链表中, 如果是, 返回false.

3. 把pnode 插到pBefore 后面

4. 如果pnode 是最后1个节点.  则pLink的成员 ptail = pnode.

5. pLink->len++

6. return true.

代码如下

BOOL link_insert(LINKPERSON * pLink, PERSON * pBefore, PERSON * pnode){
    	if (TRUE != pLink->is_inited){
    		link_error("the linklist is not inited yet");
    	}
    
    	if (NULL == pBefore || NULL == pnode){
    		printf("pBefore or pnode is empty!\n");
    		return FALSE;
    	}
    
    	if (0 > link_getindex(pLink,pBefore)){
    		printf("pBefore is not existed in linklist!\n");
    		return FALSE;
    	}
    
    	if (-1 < link_getindex(pLink,pnode)){
    		printf("pnode is existed in linklist already!\n");
    		return FALSE;
    	}
    
    	pnode->pnext = pBefore->pnext;
    	pBefore->pnext = pnode;
    
    	if (NULL == pnode->pnext){
    		pLink->ptail = pnode;
    	}
    
    	pLink->len++;
    	return TRUE;
    }

**9.12. 插入1个节点到制定链表的位置link\_insertbyindex(LINKPERSON \*pLink, int index, PERSON \* pnode);**

**        **这个函数是把1个节点插入到链表的第 index  个节点后面(index 由0(首节点开始));

这个需要做的事情如下:

就是调用上面的函数啦

link\_insert(pLink, link\_getnode(index), pnode);         ...

但是假如  index 不是一个有效的数据, 比如超出了链表范围?

那么 link\_getnode(index)  就会返回空指针,  而 link\_insert 函数接收到空指针参素就会返回FALSE啊~

代码如下:

BOOL link_insertbyindex(LINKPERSON * pLink, int index, PERSON * pnode){
        if (TRUE != pLink->is_inited){
            link_error("the linklist is not inited yet");
        }
    
        return link_insert(pLink, link_getnode(pLink, index), pnode);
    }

**9.13.****将1个节点移除出链表BOOL link\_remove(LINKPERSON \* pLink, PERSON \*pnode);**

**      **见到我的头文件中又有remove又 有delete  其实他们作用并不相同,

首先,  remove 函数只会将节点pnode 移出链表, 不会释放这个节点的内存(free), 因为用户很可能还会将这个放到链表的其他地方或者放入另1条链表.

而delete 函数直接会将 具体位置的节点移除链表后,并销毁 , 释放出内存.

至于怎样移除出1个节点pnode?

1. 如果节点不再链表中,  返回FALSE

2.pnode 前1个节点指向 pnode->pnext

3.如果前1个节点的pnext 是空, 则带代表pnode 是1个尾节点, 把尾节点移除后,  pLink的成员ptail 的值改成pnode的前1个节点

问题来了, 怎样找到pnode 的前1个节点 pBefore, 如果是双链表,  直接可以由指针找到, 但是这个是单链表..

当然, 可以先用link\_getindex(pnode) 获得  pnode 的 index,  再用link\_getnode(index\-1) 获得 pBefore,但是这样就执行两次遍历了, 为了性能着想, 还是直接遍历吧..

代码如下:

BOOL link_remove(LINKPERSON * pLink, PERSON * pnode){
    	if (TRUE != pLink->is_inited){
    		link_error("the linklist is not inited yet");
    	}
    
    	if (NULL == pnode){
    		printf("pnode is empty!\n");
    		return -1;
    	}
    
    	PERSON * pBefore = pLink->phead;
    	while (NULL != pBefore->pnext ){
    		if (pBefore->pnext == pnode){
    			pBefore->pnext = pnode->pnext;
    			if (NULL == pBefore->pnext){ // pnode is ptail;
    				pLink->ptail = pBefore;
    				pLink->len--;
    				return TRUE;
    			}
    		}
    
    		pBefore = pBefore->pnext;
    	}
    
    	return FALSE; //pnode is not existed in the linklist before.
    }

**9.14****将1个节点移除出链表并释放内存BOOL link\_delete(LINKPERSON \*pLink,int index);**

**      **好吧, 这个函数实际上就是上面那个remove 函数, 然后再手动释放内存..

逻辑如下:

1. 利用link\_getnode() 函数获得要remove 的节点

2. 利用link\_remove 移除这个节点.

3. 手动释放内存.

代码如下:

BOOL link_delete(LINKPERSON * pLink, int index){
    	if (TRUE != pLink->is_inited){
    		link_error("the linklist is not inited yet");
    	}
    
    	PERSON * pnode = link_getnode(pLink, index);
    	if (NULL == pnode){
    		return FALSE;
    	}
    
    	if (TRUE == link_remove(pLink, pnode)){
    		free(pnode);
    		return TRUE;
    	}
    
    	return FALSE;
    
    }

**9.15  清空1张链表** **BOOL li**n**k\_clear(LINKPERSON \* pLink);**

**   **清空链表的意识就是把链表所有的节点移除?

那么可以循环执行 link\_remove吗?

执行一次link\_remove 就遍历1次啊...

其实清空1张链表 根本不需要遍历:

直接将头节点的尾部指针设为NULL  就ok啦!

代码如下:

BOOL link_clear(LINKPERSON * pLink){
    	if (TRUE != pLink->is_inited){
    		link_error("the linklist is not inited yet");
    	}
    
    	pLink->phead-> pnext = NULL;
    	pLink->ptail = pLink->phead;
    	pLink->len=0;
    	return TRUE;
    }

**9.16 ****销毁1张链表, BOOL link\_clear(LINKPERSON \* pLink);**

这个函数跟上面完全不同啊, 没那么简单~

首先这个函数分两步,  首先释放所有节点的内存,

然后释放这个链表类型(结构体)指针本身.

第2步很简单  直接free(pLink) 就ok了,  问题如何执行第一步呢?

循环去link\_delete吗?  问题每执行一次link\_delete 就执行1此 link\_remove里面每次都遍历1次啊..

为了避免渣性能, 还是手动循环去释放节点吧..

这里就有个问题了, 到底是从首节点开始释放内存呢?  还是由尾节点开始释放?

如果从尾节点开始释放,  你把尾节点释放后, 怎么找前1个节点? 除了遍历还真没有办法..

从首节点释放后, 怎么找下1个节点?? 这个就简单啊, 释放首节点前保存它的尾部节点指针就是了.

所以我们应该从首节点释放

代码如下:

BOOL link_free(LINKPERSON * pLink){
    	if (TRUE != pLink->is_inited){
    		link_error("the linklist is not inited yet");
    	}
    
    	PERSON * pnode = pLink->phead;
    	PERSON * pAfter =pnode->pnext;
    
    	//printf("free pnode which id is %d\n",pnode->id);
    	free(pnode); //free phead
    	while(NULL != pAfter){
    		pnode=pAfter;
    		//printf("free pnode which id is %d\n",pnode->id);
    		pAfter = pnode->pnext;
    		free(pnode);
    	}
    
    	free(pLink);
    	return TRUE;
    
    }

**9.17****链表排序算法(根据id成员的值) void link\_sort(LINKPERSON \* pLink)**

**    **当然这里还是讲解下最简单的冒泡排序法了,

冒泡排序法在对于数组来讲是十分容易实现的, 基本上都能背出来了~

代码如下:

int i,j,m;
    
    for (i=0; i<len - 1; i++){
            for(j=i+1;j<len; j++){
                    if (a[i] > a[j]){
                            m = a[i];
                            a[i]=a[j];
                            a[j]=m;
                    }
            }
    }

原理就是循环求出数组最小的值的元素, 放在最左边, 然后求出第二小的元素, 放在数组第2位.....

这里关键就是每比较一次, 如果左边的值大于右边的值

这个两个元素就会互相交互它们的值.

对于链表来讲, 实现原理也差不多的..

数组中用i, j两个变量来存储要比较的元素的位置.

那么在链表中, 我们可以定义2个指针pPre, pAfter来存储要比较节点的位置

数组中i的初始是第1个元素, 所以i=0 开始

对于i的每1个值.   j初始话是i后面1个元素. 所以j从 j=i+1 开始

那么对于链表来讲. pPre就从首节点开始,  所以pPre= phead->pnext  (phead 是头节点)

pAfter 从第pPre的后1个节点开始, 所以pAfter= pPre->pnext 开始.

数组中每执行1次循环, i 或j的值加1, 表示执行她们的下1个元素

链表中, 每执行1次循环. pPre 或 pAfter的地址指向下1个节点. 所以p=p->pnext

代码如下:

void link_sort(LINKPERSON * pLink){
    	if (TRUE != pLink->is_inited){
    		link_error("the linklist is not inited yet");
    	}
    
    	if (pLink->len < 2){
    		return;
    	}
    
    	PERSON * pPre; //phead
    	PERSON * pAfter;
    
    	PERSON * pPB; //used to save the node address which before the pPre
    	PERSON * pAB; //used to save the node address which before the pAfter
    	PERSON * m;
    
    	for (pPB=pLink->phead,pPre=pLink->phead->pnext; NULL != pPre->pnext; pPB=pPre,pPre=pPre->pnext){
    		for (pAB=pPre,pAfter=pPre->pnext; NULL != pAfter; pAB=pAfter,pAfter=pAfter->pnext){
    			if (pPre->id > pAfter->id){
    				link_exchange(pPB,pAB);
    				m = pPre;
    				pPre = pAfter;
    				pAfter = m;
    			};
    		}
    	}
    }

注意上面, 我还定义多两个指针, 专门指向, pPre 和 pAfter 的前1个节点地址,

就是pPB->pnext == pPre        pAB->pnext ==pAfter

为什么这样做, 是因为单链表中无法由1个节点求出上1个节点的地址(只能根据尾部指针得到下1个节点的地址)

在数组中,

如果比较一次  a\[i\] > a\[j\]  之后在就会交换它们的值,

链表比较 pPre->id >pAfter->id 后,   当然也可以互相交换他们的id值,

例如

int m=pPre->id;
    pPre->id = pAfter->id;
    pAfter->id =m;
    
    char n[16]=pPre->name;
    pPre->name=pAfter->name;
    pAfter->name=n;

但是对于1个节点来讲, 地址没有变化, 但是成员值变化了.

实际应用中  , 大部分希望1个节点里面的成员值不会产生变化, 而是节点本身在链表中的位置变化

而且当1个节点的成员非常多时,  交换全部成员的值的成本往往大于交换他们在链表中位置的成本.

我用了

link_exchange(pPB,pAB);

这个函数来交换pPre, 和pAfter的地址,

但是注意传的参数是他们的上1个节点, 而是他们本身.

为什么呢, 下面会讲解这个函数.

假如 pPre指向的是链表第2个节点,  pAfter 指向的是第4个节点

那么交换节点后,  pPre 就指向链表中第4个节点了,  而pAfter 指向第2个节点了.  因为他们指向的节点在链表中的位置换了嘛...

所以根据冒泡排序法的原理, pPre 要指向前面的节点, 而pAfter 要指向后面的节点.

所以我们还要把 pPre 和 pAfter所指向的地址互换.  让pPre 指回第2个节点. 而pAfter 指回第4个节点.

所以要执行

m = pPre;
    pPre = pAfter;
    pAfter = m

来交换他们的地址啊.

**9.18****链表交换两个节点的下1个节点函数BOOL link\_exchange(LINKPERSON\*pPB, LINKPERSON \* pAB)**

**     **当然, 可以先执行link\_remove 再 link\_insert到适当的位置达到目地, 但是就执行了若干次无谓的遍历动作, 不推荐!

**     **注意的是, 这个函数交换的不是pPB 和  pAB的位置,  是交换 pPB->pnext 和 pAB->pnext 的位置.

为什么要这样呢, 看到后面就明白了.

首先图解交换两个节点位置要做的操作:

**假如我要交换下图中节点2 和 节点4 的位置.**

**![1365525745_8702.png][]**

**1.首先节点2的前1个节点1的尾部指针指向节点4**

![1365525990_5139.png][]

**2.然后节点4的原本的前1个节点3的尾部指针指向节点2**

**![1365526129_3622.png][]'**

**3.然后节点2的尾部指针指向节点4的尾部指针地址(节点5)**

**![1365526283_1133.png][]**

**4.然后节点4的尾部指针指向节点2原本的尾部指针地址(节点3)**

**![1365526535_9372.png][]**

好了, 经过上面4部后就完成节点2和节点4的位置交换了, 原来顺序是1 2 3 4 5,     后来根据指针就是1 4 3 2 5啦

经过总结, 可以发现上面4步实际上可以总结成为2步:

1. 交换节点2和节点4的前1个节点,     也就是节点2 和 节点4 的前1个节点的尾部指针的值互换

2. 交换节点2和节点4的后1个节点 ,    也就是节点2 和 节点4 的尾部地址的值互换

第2步很简单

无非就是  p2->pnext  和 p4->pnext 互换

问题来了,

第1步怎么实现呢,   因为根据p2 和 p4 无法知道 p1 和 p3的地址啊,   单链表只能单向求1下1个节点地址,  而不能往前退的.

所以!

'我们在这个函数中, 参数不要定为 p2 和 p4 ,  而是把他们的前1个节点  p1 和  p3 作为参数传入来

那么

p2==p1->pnext

p4==p3->pnext

那么第1步   把 p1->pnext 和 p3->pnext 的值互换就ok啦

第二步呢,   因为p1->pnext 和  p3->pnext 的值互换过了.

所以p1->pnext 就是p4啊    p3->pnext 就是p2啊   ,  而我们上面见过第2步是 p2->pnext 的值和 p4->pnext的值互换

所以就是 p3->pnext->pnext 的值 和 p1->pnext->pnext 的值互换啊!

代码如下:

static void link_exchange(PERSON * pPB, PERSON * pAB){
    	//this function will exchange the place of the next nodes of pPB and pAB
    	//if pPB->pnext == pPre ; pAB->pnext == pAfter
    	//after exchange, pPre and pAfter will exchange their index in the linklist
    
    	PERSON * m;
    	//first , exchange their Pre node;
    	m = pPB->pnext;
    	pPB->pnext = pAB->pnext;
    	pAB->pnext = m;
    
    	//then . exchange their next node;
    	m=pPB->pnext->pnext;
    	pPB->pnext->pnext = pAB->pnext->pnext;
    	pAB->pnext->pnext = m;
    }

**9.19****写个小程序来测试一下这个链表容器**

其实就是写1个c文件, 引用这个链表容器的头文件,调用我上面写的函数,就是可以测试了

代码如下啦:

int link_1(){
    	//const char *n = "gateman poon";
    	PERSON * p1 = person_new(1,"Jason Poon" );
    
    	LINKPERSON * plink1 = link_create(10);
    	//LINKPERSON * plink2;
    	//link_traverse(plink2);
    
    	//PERSON * p3;
    	//printf("id is %d, name is %s\n",p3->id, p3->name);
    	
    	free(p1);
    	p1 = link_getnode(plink1, 3);
    
    	link_insert(plink1, link_getnode(plink1,4), person_new(24, "Gateman"));
    	link_insertbyindex(plink1, 5, person_new(11, "Nedved"));
    	link_remove(plink1, link_getnode(plink1,7));
    	link_delete(plink1, 7);
    	link_add(plink1, person_new(12, "Cindy"));
    	link_add(plink1, person_new(24, "Gateman"));
    	link_add(plink1, person_new(11, "Nvd11"));
    	link_add(plink1, person_new(49, "Lulu"));
    	link_add(plink1, person_new(47, "Alice"));
    	link_traverse(plink1);
    
    	printf("will be sort now!\n\n");
    	link_sort(plink1);
    	link_traverse(plink1);
    	//link_clear(plink1);
    	link_free(plink1);
    	//link_traverse(plink1);
    
    	//printf("id is %d, name is %s\n",p1->id, p1->name);
    	printf("link1 done\n");
    	return 0;
    
    }

输出:

![1365528100_6810.png][]

**10,一些总结,**

数组的优点:

存取速度快, 因为根据头部指针就可以根据下标定位到对应的元素.

缺点:

实现必须知道数组的长度

需要连续的内存空间

插入和删除速度慢. 一旦插入或删除1个元素, 意味这大量元素要向前或向后移动1位.

链表的优点:

空间几乎不用限制, 而数组必须要有连续的内存空间

插入和删除元素的速度很快, 只需要修改部分指针.

链表缺点:

存储速度慢. 因为要找1个元素就必须一直遍历下去..

**    本文的函数就写到这里了,  其实还有很多功能没有实现, 例如求链表有效长度(这个太简单),   两个链表的对接(这个...也不难啦)等..  怎么说呢, 虽然伪算法不难看懂, 但是真正用代码来实现还是有点复9杂啊...**

**    关键就是对于指针的理解了, 对于数据结构, 指针机会就是一切啊....**

[1365354565_3298.png]: https://img-my.csdn.net/uploads/201304/08/1365354565_3298.png
[1365426372_5719.png]: https://img-my.csdn.net/uploads/201304/08/1365426372_5719.png
[1365426538_4662.png]: https://img-my.csdn.net/uploads/201304/08/1365426538_4662.png
[1365525745_8702.png]: https://img-my.csdn.net/uploads/201304/10/1365525745_8702.png
[1365525990_5139.png]: https://img-my.csdn.net/uploads/201304/10/1365525990_5139.png
[1365526129_3622.png]: https://img-my.csdn.net/uploads/201304/10/1365526129_3622.png
[1365526283_1133.png]: https://img-my.csdn.net/uploads/201304/10/1365526283_1133.png
[1365526535_9372.png]: https://img-my.csdn.net/uploads/201304/10/1365526535_9372.png
[1365528100_6810.png]: https://img-my.csdn.net/uploads/201304/10/1365528100_6810.png