数据结构-单链表存储

        如果说，顺序表的所占用的内存空间是连续的，那么链表则是随机分配的不连续的，那么为了使随机分散的内存空间串联在一起形成一种前后相连的关系，指针则起到了关键性作用。

        

单链表的基本结构：

 

头指针：永远指向链表第一个节点的位置。

 头结点：不存任何数据的空节点，通常作为链表的第一个节点。对于链表来说，头节点不是必须的，它的作用只是为了方便解决某些实际问题。

首元结点：首个带有元素的结点。

其他结点：链表中其他的节点。

1、定义一个链表结点：

        包括数据域和指针域

typedef struct Link{
	char elem;//数据域 
	struct Link *next;//指针域，用来连接后继元素 
}link;//link为节点名，每个结点都是一个link结构体 

2、初始化单链表：

（1）创建一个头结点

（2）声明一个临时指针指向头结点

（3）用循环创建新的结点并赋值且依次相连

        newLink a；

        a->data=i;

        a->next=null;

        temp->next=a;

        temp=a;

过程如下：

 带头结点：

 
link * initLink(){
	link *p=(link*)malloc(sizeof(link));//创建头结点
	link*temp = p;//声明一个指针temp指向头结点，也就是头结点的地址赋值给指针变量(注意这不是头指针而是用来连接数组的临时指针变量)
	//生成链表
	for(int i=1;i<5;i++)
	{
		link *a=(link*)malloc(sizeof(link));//生成一个结点 
		a->elem=i;//给结点的数据域赋值
		a->next=NULL;//指针域设置为空 
		temp->next=a;//上一个结点的指针指向新增结点 
		temp=temp->next;//临时指针向后移动也可写成temp=a 
	} 
	//返回头结点，通过头节点的指针即可找到整个链表
    return p;
} 

无头结点的单链表初始化：

 
link * initLink2(){
	link *p=NULL;//创建头指针
	link*temp=(link*)malloc(sizeof(link));//创建首元结点
	//首元结点初始化
	temp->elem=1;
	temp->next=NULL;
	p=temp;//头结点指向首元结点
	//接下来从第二个结点开始创建
	for(int i=2;i<5;i++){
		//创建一个新结点并初始化
		link *a=(link*)malloc(sizeof(link));
		a->elem=i;
		a->next=NULL;
		//将temp结点与新建的a结点建立逻辑关系
		temp->next=a;
		temp=a;	
	}
	//返回建立的节点，只返回头指针 p即可，通过头指针即可找到整个链表
	return p; 
}

 

3、输出链表数据：

        带头结点：

void display(link *p){
	link*temp=p;//将temp指向头结点
	//只要temp指针指向的结点的next不是Null，就执行输出语句。
	while(temp->next){
		temp=temp->next;
		printf("%d ",temp->elem);
	} 
	printf("\n");
} 

          不带头结点：

void display2(link *p){
    link* temp=p;//将temp指针重新指向头结点
    //只要temp指针指向的结点的next不是Null，就执行输出语句。
    while (temp) {
        printf("%d ",temp->elem);
        temp=temp->next;
    }
    printf("\n");
}

4、完整代码：

#include
#include
 
typedef struct Link{
	int elem;//数据域 
	struct Link *next;//指针域，用来连接后继元素 
}link;//link为节点名，每个结点都是一个link结构体 
 
//带头结点 
link * initLink(){
	link *p=(link*)malloc(sizeof(link));//创建头结点
	link*temp = p;//声明一个指针temp指向头结点，也就是头结点的地址赋值给指针变量(注意这不是头指针而是用来连接数组的临时指针变量)
	//生成链表
	for(int i=1;i<5;i++)
	{
		link *a=(link*)malloc(sizeof(link));//生成一个结点 
		a->elem=i;//给结点的数据域赋值
		a->next=NULL;//指针域设置为空 
		temp->next=a;//上一个结点的指针指向新增结点 
		temp=temp->next;//临时指针向后移动也可写成temp=a 
	} 
	//返回头结点，通过头节点的指针即可找到整个链表
    return p;
} 
 
//不带头结点 
link * initLink2(){
	link *p=NULL;//创建头指针
	link*temp=(link*)malloc(sizeof(link));//创建首元结点
	//首元结点初始化
	temp->elem=1;
	temp->next=NULL;
	p=temp;//头结点指向首元结点
	//接下来从第二个结点开始创建
	for(int i=2;i<5;i++){
		//创建一个新结点并初始化
		link *a=(link*)malloc(sizeof(link));
		a->elem=i;
		a->next=NULL;
		//将temp结点与新建的a结点建立逻辑关系
		temp->next=a;
		temp=a;	
	}
	//返回建立的节点，只返回头指针 p即可，通过头指针即可找到整个链表
	return p; 
}
 
//带头结点 
void display(link *p){
	link*temp=p;//将temp指向头结点
	//只要temp指针指向的结点的next不是Null，就执行输出语句。
	while(temp->next){
		temp=temp->next;
		printf("%d ",temp->elem);
	} 
	printf("\n");
} 
 
//不带头结点 
void display2(link *p){
    link* temp=p;//将temp指针重新指向头结点
    //只要temp指针指向的结点的next不是Null，就执行输出语句。
    while (temp) {
        printf("%d ",temp->elem);
        temp=temp->next;
    }
    printf("\n");
}
 
int main()
{
	display(initLink());
	return 0;
}

输出结果：