数据结构学习笔记(2.线性表之单链表)

线性表有两种：一种是顺序存储的叫顺序表，上节已经说过了，另一种是链式存储的叫链表，本节说的是单链表，即单向链表(每个节点中只包含一个指针域)。

本节知识点：

1.链表的好处：对于动态链表，可以对未知数据量的数据进行存储。插入和删除比顺序表方便的多，不用大量移动。

链表的缺点：除了数据信息，还需对额外的链表信息进行分配内存，占用了额外的空间。访问指定数据的元素需要顺序访问之前的元素。

2.链表的基本概念：

链表头(表头节点)：链表中的第一个节点，包含指向第一个数据元素的指针以及链表自身的一些信息(即链表长度length)

数据节点：链表中的代表数据元素的节点，包含指向下一个数据元素的指针和数据元素的信息

尾节点：链表中的最后一个数据节点，其下一元素指针为空，表示无后继

3.对于本节的可复用单链表的设计想法是这样的：

a. 可复用的顺序表中保存的是各个数据的地址，所以我最初想到的是在链表元素中也保存各个数据的地址：

使用这样的结构，add是链表中保存的数据，其实就是想复用保存的各种类型的地址，add是一个unsigned int型，用来保存各种数据类型的地址，next是链表结构，用来指向链表元素的下一个链表元素的。

b.但是这样的结构有一个问题，就是从使用的总空间(链表结构的空间+add中保存数据的空间)角度来看，add就是一个浪费空间的变量。因为在add中保存地址，为什么不强制类型成next的类型(此时next应该是链表第一个结构的类型)，直接使用这个地址把各种你想要存储的结构赋值给next，这样存储的各个结构就变成了，如图。

c.但是把所有的类型都转换成链表第一个元素的指针类型 再赋值给next 显得程序很不规整，所以最好直接给链表一个结构，把这些结构类型都统一强制类型转换成这个链表的类型，如下：

typedef struct Str_LinkList LinkListNode;  //这个结构体是链表的真身 
struct Str_LinkList   //每一个链表元素的结构都会包含这个结构  因为当给链表元素强制类型 
{                     //转换成(LinkListNode* )的时候  其实就是要开始对每个元素中的 LinkListNode进行赋值了 
	LinkListNode* next;
};

把什么链表头啊，链表元素啊，想要连接进入这个链表的各种结构都强制类型成LinkListNode* 但是要保证每个结构中都有LinkListNode* next 成员。

d.最后一点，就有点接受不了，也是为了代码的整洁，提高可读性，使链表结构都规整到LinkListNode这个结构中去，便于对链表进行管理，比如说双向链表的前驱和后继。把每个类型中的LinkListNode* next 成员 变成LinkListNode node。这里面有一个很好的c语言技巧，就是这个LinkListNode node必须要放在每个结构中(如 str)的第一个元素位置，即node的地址就是结构体str的地址，因为只有这样了，在把str强制类型转换成 n=(LinkListNode* )str的时候，访问n->next才是访问str.node->next的值，因为两者地址相同，切记一定要放到第一个元素的位置！！！

4.对于链表这个数据结构，一定要注意一个问题，也是这节我犯的一个很难发现的错误：

就是已经在链表中的元素，千万不要再一次往链表中进行插入，因为这样会导致从它插入的地方开始链表的后继就开始混乱了，把整个链表完全弄乱，出现你想不到的问题。

本节代码：

本节实现的是一个可以复用的单链表：

LinkList.c：

/*******************************************************************************************************
文件名：LinkList.c
头文件：LinkList.h 
时间： 2013/08/07
作者： Hao
功能:  可以复用 带有增 删 改 查 功能的单链表
难道： 1.typedef struct Str_LinkList LinkListNode;  //这个结构体是链表的真身 
		struct Str_LinkList   //每一个链表元素的结构都会包含这个结构  因为当给链表元素强制类型 
		{                     //转换成(LinkListNode* )的时候  其实就是要开始对每个元素中的 LinkListNode进行赋值了 
			LinkListNode* next;
		}; 
		这个链表结构在链表元素中起到的作用 是本节的难点 
		2.切记一个问题  就是已经是链表中元素的 千万不要再往链表中添加了 否则链表一定出现无穷的错误 
		3.对于pos值的问题  add、get、del三个函数中 的链表都是 从1开始的到length  0是链表头 
						  在add函数中pos为0的时候是和pos为1的情况是一样的  都是头插法  0~~~~~无穷大 
		                  在get函数中pos为0的时候是获得链表头 地址      0~~~~~length 
						  在del函数中pos为0的时候是无效的 del失败       1~~~~~length 
*******************************************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include "LinkList.h"

typedef struct str_list_head  //这个是链表头 其实也可以当作一个没有前驱的 链表元素 元素的内容是链表长度 
{
	//LinkListNode* next;
	LinkListNode head; //这个参数要特别重视 每一个链表元素结构的第一个参数一定是 LinkListNode
	                   //因为在寻找链表元素后继的时候 其实就是将链表元素强制类型转换成 LinkListNode*  然后给next进行赋值 其实就是给 LinkListNode变量赋值 
	int length; //链表长度 
}list_head;

/*******************************************************************************************************
函数名： Creat_LinkListHead
函数功能：创建一个链表的链表头 并给链表头分配空间
参数： void
返回值：ret 成功返回链表头地址  失败返回NULL 
*******************************************************************************************************/
LinkList* Creat_LinkListHead(void)
{
	list_head* ret = NULL;
	ret = (list_head* )malloc( sizeof(list_head)*1 );
	if(NULL != ret) //malloc分配成功 
	{
		ret -> length = 0;
		//ret -> next = NULL;
		ret -> head.next = NULL;
	}
	return (LinkList* )ret; 
}

/*******************************************************************************************************
函数名：Destroy_LinkListHead
函数功能：释放一个链表头指针 
参数：LinkList* head 链表头指针 
返回值： ret 释放成功返回1  释放失败返回0 
*******************************************************************************************************/
int Destroy_LinkListHead(LinkList* head)
{
	int ret = 0; 
	list_head* lhead = (list_head* )head;
	if( NULL != lhead )
	{
		free(lhead);
		ret = 1;
	}
	return ret;
}

/*******************************************************************************************************
函数名:Get_Length
函数功能：获得链表的长度 
参数: LinkList* head 链表头指针 
返回值： ret 成功返回链表长度  失败返回0 
*******************************************************************************************************/
int Get_Length(LinkList* head) 
{
	int ret = 0;
	list_head* lhead = (list_head* )head;
	if( NULL != lhead )
	{
		ret = lhead -> length;
	}	
	return ret;
}

/*******************************************************************************************************
函数名：Clean_LinkListHead
函数功能：	清空链表 
参数： LinkList* head 链表头指针 
返回值：ret 成功返回1 失败返回0 
*******************************************************************************************************/
int Clean_LinkListHead(LinkList* head) 
{
	int ret = 0;
	list_head* lhead = (list_head* )head;
	if( NULL != lhead )
	{
		lhead -> length = 0;
		//lhead -> next = NULL;
		lhead -> head.next = NULL;
		ret = 1;
	}	
	return ret;
}

/*******************************************************************************************************
函数名:Add_LinkList
函数功能：往链表里面添加一个链表元素 如果pos的值是0(就是链表头)和1(链表的第一元素 链表元素个数是从1开始算的)都是头插法
          pos的值大于链表长度是尾插法  这里面pos值得注意的是 i=1 pos为a的时候 是把链表元素插入第a个元素的位置 
          当i=0 pos为a的时候 是把链表元素插入 第a个元素位置的后面    切忌：这里面0位置是链表头指针 从1开始是链表元素 
参数：   LinkList* head链表头指针    LinkListNode* Node插入元素的指针(被强制类型转化成LinkListNode*)  int pos 插入位置 
         pos的有效值范围是 从0到无穷大  
返回值： ret 插入成功返回1  插入失败返回0 
*******************************************************************************************************/
int Add_LinkList(LinkList* head, LinkListNode* Node, int pos)
{
	int ret = 0;
	int i = 0;
	list_head* lhead = (list_head* )head;
	LinkListNode* node = (LinkListNode* )head;
	ret=( NULL != node) && ( NULL != Node) && (pos >= 0);
	if(1 == ret)
	{
		for(i=1; ( (i<pos) && (node->next != NULL) ); i++)
		{
			node = node->next;
		}
		Node -> next = node -> next;
		node -> next = Node;
		
		lhead -> length++; 
	}
	return ret;
}

/*******************************************************************************************************
函数名：Get_LinkListNode
函数功能：获得链表中第pos个元素位置的链表元素 链表是从1开始的  0是链表头   pos为0的时候表示get链表头 
参数： LinkList* head链表头指针    int pos获得链表元素的位置  pos的有效取值范围是 1 到  length  0是链表头 
返回值： LinkListNode*类型 第pos个链表元素的地址 
*******************************************************************************************************/
LinkListNode* Get_LinkListNode(LinkList* head, int pos)
{
	int ret = 0;
	int i = 0;
	list_head* lhead = (list_head* )head;
	ret=( NULL != lhead) && (pos >= 0) && (pos <= lhead->length);
	if(1 == ret)
	{
		LinkListNode* node = (LinkListNode* )head;
		for(i=0; i<pos; i++) //执行 pos次   得到的是第pos位置的node 
		{
			node = node->next;
		}	
		return (LinkListNode*)node;
	}
	return NULL;
}

/*******************************************************************************************************
函数名：Del_LinkListNode
函数功能：删除链表中第pos位置的链表元素 
参数： LinkList* head链表头指针    int pos删除链表元素的位置  pos是删除的链表元素的位置 跟get和add中的
       pos是配套的  有效取值范围依然是 1到 length  在这个函数里面由于不能删除链表头 所以pos为0的时候无效 
返回值： LinkListNode* ret这个返回值很重要 因为这个删除仅仅是把链表元素踢出了链表 并没有free开辟的内存
         应该通过这个返回的地址free  释放内存
		 删除成功返回 删除链表元素的地址   删除失败返回 NULL 
*******************************************************************************************************/
LinkListNode* Del_LinkListNode(LinkList* head, int pos)
{
	LinkListNode* ret = NULL;
	int i = 0;
	list_head* lhead = (list_head* )head;
	if(( NULL != lhead) && (pos > 0) && (pos <= lhead->length))
	{
		LinkListNode* node = (LinkListNode* )head;
		for(i=1; i<pos; i++)//执行 pos次   得到的是第pos位置的node  这个方法行不通 
		{                   //因为要想删除第pos位置的node 应该先找到它上一个链表元素 
			node = node->next; //所以这里面i=1 比get函数少执行了一次  得到第pos-1位置的node 
		}
		ret = node->next;
		node->next = ret->next;	
		
		lhead->length--;
	}
	return (LinkListNode*)ret;
}

LinkList.h：

#ifndef __LinkList_H__
#define __LinkList_H__

typedef void LinkList;  //这个是为了 封装方便 
typedef struct Str_LinkList LinkListNode;  //这个结构体是链表的真身 
struct Str_LinkList   //每一个链表元素的结构都会包含这个结构  因为当给链表元素强制类型 
{                     //转换成(LinkListNode* )的时候  其实就是要开始对每个元素中的 LinkListNode进行赋值了 
	LinkListNode* next;
};

LinkList* Creat_LinkListHead(void);

int Destroy_LinkListHead(LinkList* head);

int Get_Length(LinkList* head);

int Clean_LinkListHead(LinkList* head);

int Add_LinkList(LinkList* head, LinkListNode* Node, int pos);

LinkListNode* Get_LinkListNode(LinkList* head, int pos);

LinkListNode* Del_LinkListNode(LinkList* head, int pos); 
 
#endif

main.c：

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>
#include "LinkList.h"

typedef struct student
{
	//LinkListNode* next;
	LinkListNode node;
	int num;
	char name[30];
}str;
int main(int argc, char *argv[]) 
{
	str str1,str2,str3,str4,str5,str6,*strp;
	int i=0;
	LinkList* list_head;
	list_head = Creat_LinkListHead();
	
	str1.num = 1;
	strcpy(str1.name,"haohao");
	
	str2.num = 2;
	strcpy(str2.name,"ququ");
	
	str3.num = 3;
	strcpy(str3.name,"popo");
	
	str4.num = 4;
	strcpy(str4.name,"wowo");
	
	str5.num = 5;
	strcpy(str5.name,"tiantian");

	str6.num = 6;
	strcpy(str6.name,"cheche");
	
	Add_LinkList(list_head, (LinkListNode*)&str1, 0);
	Add_LinkList(list_head, (LinkListNode*)&str2, 0);
	Add_LinkList(list_head, (LinkListNode*)&str3, 0);
	Add_LinkList(list_head, (LinkListNode*)&str4, 0);
	Add_LinkList(list_head, (LinkListNode*)&str5, 0);
	strp = (str*)Del_LinkListNode(list_head, 5);
	printf("%d\n",strp->num);
	printf("%s\n",strp->name);
	printf("\n");
	for(i=1; i<= Get_Length(list_head); i++)
	{
		strp = (str*)Get_LinkListNode(list_head, i);
		printf("%d\n",strp->num);
		printf("%s\n",strp->name);
	} 
	printf("\n");
	Add_LinkList(list_head, (LinkListNode*)&str6, 3);	
	for(i=1; i<= Get_Length(list_head); i++)
	{
		strp = (str*)Get_LinkListNode(list_head, i);
		printf("%d\n",strp->num);
		printf("%s\n",strp->name);
	} 
		
	
	Clean_LinkListHead(list_head);
	Destroy_LinkListHead(list_head);
	return 0;
}

课后练习：

1.对于上节顺序表中的unsigned int型保存数据地址，可不可用void*

这个问题已经得到了唐老师的解答，其实使用void* 最好了，因为使用unsigned int 仅仅能够在32位机上面运行成功，在64位机上运行就会出错的！！！

2.对于有头链表和无头链表的区别

所谓有头链表，就是有头结点的链表，头结点是一个链表元素，但不存放数据。无头链表就是没有头结点的链表。相比之下有头链表比无头链表，方便很多，优点也很多。

无头链表就是在谭浩强老师的c语言书中的那个链表。就是没有头结点，只有一个指针指向链表第一个元素。这个指针被叫做链表头。 个人建议使用有头链表！！！

3.对顺序表和单链表添加一个反转操作

a.对于顺序表 其实就是在不断的交换

b.对于链表 我觉得还是使用双向链表吧，解决这个问题就方便了~~~