数据结构——“单链表“ 深度刨析单链表（图解+代码）_单链表的空表图示

一、线性表和单链表关系

线性表的链式存储结构就是链表

二、单链表概述

将线性表L=(a0 ,a1 ，······，an-1)中各元素分布在存储器的不同存储块，称为结点，通过地址或指针建立它们之间的联系，所得到的存储结构为链表结构，表中元素ai的结点形式如图：

其中，结点的data域存放数据元素ai，而next域是一个指针，指向ai的直接后继ai+1所在的结点。
于是，线性表L=(a0 ,a1 ，······，an-1)的结构如图：

• 不带头结点链表
  
  通常用头结点标识一个单链表，如L头指针为NULL表示空表，在单链表第一个结点之前附加一个结点，称为头结点
• 带头结点链表
• 头结点和头指针的区分：
  不管带不带头结点，头指针都始终指向链表的第一个结点，而头结点是带头结点的链表中的第一个结点，结点内通常不存储信息。

优点： 不要求大片连续空间，改变容量方便
缺点; 不可随机存取，要查找特定结点时，需要从表头开始遍历依次查找， 要耗费一定空间放指针

链表结点类型描述：

链表结构体定义

typedef struct node_t       //链表结构体定义
{
   
      data_t data;          //结点的数据域
      struct node_t *next;  //结点的后继指针域
}linknode_t , *linklist_t;

若说明
linknode_t A;        //结点声明
linklsit_t p = &A;   //指针声明
1
2
3
4
5
6
7
8
9
10

则结构变量A为所描述的结点，而指针变量p为指向此类型结点的指针（p的值为结点的地址），如图

设p指向链表中结点ai，如图

获取ai值，写作：p->data;而取ai+1值，写作：p->next->data。
另外，若指针p的值为NULL，则它不指向任何结点，此时取p->data或者p->next是错误的。
可调用C语言中malloc（）函数向系统申请结点的存储空间，例如：

linklist_t p;
p = (linklist_t )malloc( sizeof ( linknode_t ) );
1
2

则创建一个类型为linknode_t的结点，且该结点的地址已存入指针变量p中：

单链表的基本程序

三、单链表的基本操作（运算）

① 单链表的创建

1.1 创建空链表 再插入值（头插法建表）

文件1: linklist.h

#ifndef  __LINKLIST_H__
#define  __LINKLIST_H__

typedef int datatype;

typedef struct node{
   
     	datatype data;
	struct node *next;
}listnode ,*linklist;      //*linklist是指针

extern linklist list_create();   
//linklist 是返回值类型     extern是说这函数的定义在别的文件中

#endif
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

文件2：linklist.c

#include<stdio.h>
#include<stdlib.h>
#include"linklist.h"
 
 //创建空链表
linklist list_create(){
   

	linklist H;

	if((H =(linklist)malloc(sizeof(linknode)))== NULL)
	// ==优先级高于malloc 要先malloc在比较，就要在malloc加括号
	{
   
		printf("malloc failed!\n");
		return H;
	}
    
    //空链表赋值
	H->data = 0;  
	H->next = NULL;

	return H;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

文件3：test.c

#include<stdio.h>
#include<stdlib.h>
#include"linklist.h"

int main(){
   

   linklist H;        //定义H指针  指向链表

   H = list_create();  //创建链表

   return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

写个Makefile 来编译一下。

CFLAGS = -c -Wall -g
test:linklist.o test.o

.PHONY:clean
clean:
        rm *.o test
1
2
3
4
5
6

空链表创建成功

1.2 创建链表时 由用户输入值 （尾插法建表）

创建链表时 由用户输入值 ，输入特殊值，就不再创建链表了

算法思路：
依次读入表L=(a0 ,a1 ，······，an-1)中每一个元素ai（假设为整型），若ai != 结束符（-1），则ai创建一个结点，插入表尾，最后返回链表的头结点指针H。

文件1: linklist.h 尾插法建表

#ifndef  __LINKLIST_H__
#define  __LINKLIST_H__

typedef int datatype;

typedef struct node{
   
     	datatype data;
	struct node *next;
}listnode ,*linklist;

//创建空表1
extern linklist list_create();
//创建空表2
extern linklist list_create2();

extern int  list_head_insert(linklist H , datatype value); 
extern void list_show(linklist H);
#endif
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

用到的是尾插法

文件2：linklist.c

#include<stdio.h>
#include<stdlib.h>
#include"linklist.h"

//创建空表
linklist list_create(){
   

	linklist H;

	if((H =(linklist)malloc(sizeof(listnode)))== NULL)
	{
   
		printf("malloc failed!\n");
		return H;
	}

	H->data = 0;
	H->next = NULL;
	return H;
}
//尾插法建表
linklist list_create2(){
   

	linklist H,r,p;  //H头指针 r尾指针  p新结点指针

	int value;

	if((H =(linklist)malloc(sizeof(listnode)))== NULL) //创建空表
	{
   
		printf("malloc failed!\n");
		return H;
	}

	H->data = 0;
	H->next = NULL;
    r=H;  //r尾指针指向表尾结点
    
	while(1){
    //循环输入（尾插）
	   puts("input a number(-1 exit):");
	   scanf("%d",&value);
	   if(value == -1){
      //特殊输入退出尾插建表
	            break;
	   }else{
   
 
               //①开辟新结点内存
               if((p =(linklist)malloc(sizeof(listnode)))== NULL)
          	   {
   
         		printf("malloc failed!\n");
	        	return H;
        	   }
	        	p->data = value;   //新结点赋值
		        p->next = NULL;    //新结点指针指向NULL
 
                //尾插法
		        r->next = p;  //② 链表尾指针指向新结点头  
	         	r = p;        //③ 表尾指针指向链表尾结点
          }
	}
	return H;
}

//输出表内有效元素
void list_show(linklist H){
   

	while(H->next){
   
		printf("%d ",H->next->data);
		H = H->next;
	} 
	printf("\n");
}

//头插法
int list_head_insert(linklist H , datatype value)
{
   
	linklist p;

	if((p = (linklist)malloc(sizeof(listnode))) == NULL){
   
		printf("malloc failed\n");
		return -1;
	}
	p->data = value;
	p->next = H->next;
	H->next = p;
        
	return 0;
}
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

文件3：test.c

#include<stdio.h>
#include<stdlib.h>
#include"linklist.h"

int main(){
   

   linklist H;

  // H = list_create();
   
   H = list_create2();  //尾插法建立链表

  /* list_head_insert(H,10)
1
2
3
4
5
6
7
8
9
10
11
12
13