创建单链表详解之C语言版

一、单链表

链表是用一组任意的存储单元存储数据元素。如果是存储线性表中的元素，则称为线性链表。
链表中的结点地址在内存中可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。因此链表中结点的逻辑顺序和物理顺序不一定相同。
如果链表的结点中只有一个指针域，则该链表称为单链表，这也是常用的线性表的存储模式。
单链表适合于比较频繁的增加或者删除线性表中元素，不需要移动元素。

二、创建单链方法

创建单链表的方法主要有“头插入法”和“尾插入法”。顾名思义，“头插入法”就是始终在表头位置插入新的结点，而“尾插入法”就是在链表的末尾插入新的结点。
1.头插入法
假设有线性表a={ 1,2,3 }，则使用头插入法创建单链表的过程如下：
1）首先生成链表的表头结点（如果需要），同时让指针h指向该结点

2）插入元素1。先创建一个新结点，存储1，然后将其链接到h的后面。

3）插入元素2。继续创建一个新结点，存储2，然后将其链接到h的后面。

4）继续插入元素3。创建一个新结点，存储3，然后将其链接到h的后面。

平铺之后得到：

2.尾插入法
假设有线性表a={ 1,2,3 }，则使用尾插入法创建单链表的过程如下：
1）首先生成链表的表头结点（如果需要），同时让指针h指向该结点

2）插入元素1。创建一个新结点，存储1，然后将其链接到h的后面。

3）插入元素2。创建一个新结点，存储2，然后将其链接到结点1的后面。

4）插入元素3。创建一个新结点，存储3，然后将其链接到结点2的后面。

在尾插入法创建单链表的过程中，为了方便实现插入的工作，引入一个临时指针p指向链表中最后一个结点，则再插入新结点时，就可以利用p建立链接。
例如：

插入元素3的时候，就可以利用p把新结点链接到链表的末尾：

对应的算法为：

p->next = s;
p = s;
1
2

三、创建单链算法之C程序
根据已知的数组创建单链表。
链表结点结构：

typedef  struct  Lnode
{   
	int           data;     //数据域
	struct Lnode  *next;    //指针域
}LNode;
1
2
3
4
5

1.头插入法

LNode* CreateListHeader( int a[], int n )
{  
	int i;
	LNode  *head, *s;
	head = ( LNode* )malloc( sizeof( LNode ) ); 
	head->next = NULL; //创建单链表的表头结点
	for( i = 0; i < n; i++ )
	{    
		s = ( LNode* )malloc( sizeof( LNode ) ); 
		s->data = a[i];	 
		s->next = head->next;
		head->next = s;
	}
	return (head);   
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.尾插入法

LNode* CreateListTailer( int a[], int n )
{  
	int i;
	LNode  *head, *s, *p;
	head = ( LNode* )malloc( sizeof( LNode ) ); 
	head->next = NULL; //创建单链表的表头结点
	p = head;
	for( i = 0; i < n; i++ )
	{    
		s = ( LNode* )malloc( sizeof( LNode ) ); 
		s->data = a[i];	 
		s->next = NULL;
		p->next = s;
		p = s;
	}
	return (head);   
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

3.完成的测试代码（仅供参考）

#include"stdio.h"
#include"malloc.h" 
typedef  struct  Lnode
{   
	int           data;     //数据域
	struct Lnode  *next;    //指针域
}LNode; 
LNode* CreateListHeader( int a[], int n );
LNode* CreateListTailer( int a[], int n );
int main()
{
	LNode *head1, *head2, *p;
	int a[] ={ 1, 2, 3, 4, 5 }; 
	int n = 5;
	head1 = CreateListHeader( a, n );
	printf( "头插入法创建单链表：" );
	p = head1->next;
	while( p != NULL )
	{
		printf( "%5d", p->data );
		p = p->next;
	}
	printf( "\n" );
	printf( "尾插入法创建单链表：" );
	head2 = CreateListTailer( a, n );
	p = head2->next;
	while( p != NULL )
	{
		printf( "%5d", p->data );
		p = p->next;
	}
	printf( "\n" );
	return 0;
}
// 头插入法创建单链表,链表的头结点head作为返回值
LNode* CreateListHeader( int a[], int n )
{  
	int i;
	LNode  *head, *s;
	head = ( LNode* )malloc( sizeof( LNode ) ); 
	head->next = NULL; //创建单链表的表头结点
	for( i = 0; i < n; i++ )
	{    
		s = ( LNode* )malloc( sizeof( LNode ) ); 
		s->data = a[i];	 
		s->next = head->next;
		head->next = s;
	}
	return (head);   
}
// 尾插入法创建单链表,链表的头结点head作为返回值
LNode* CreateListTailer( int a[], int n )
{  
	int i;
	LNode  *head, *s, *p;
	head = ( LNode* )malloc( sizeof( LNode ) ); 
	head->next = NULL; //创建单链表的表头结点
	p = head;
	for( i = 0; i < n; i++ )
	{    
		s = ( LNode* )malloc( sizeof( LNode ) ); 
		s->data = a[i];	 
		s->next = NULL;
		p->next = s;
		p = s;
	}
	return (head);   
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

4.测试结果