C与指针-第十二章 链表

发表于   |   分类于   |  

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。

链表细则：

1)是由结构体和指针构成的。
2)包括两个部分一个是数据域和指针域。
3)链表中的结点分为两类：头结点和一般结点。头结点是没有数据域的。
4)基本操作有：初始化链表，增加结点和删除结点，求链表的长度等等。

链表主要包括：单向链表，双向链表，循环链表。

单向链表

含义：

单向链表（单链表）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始；链表是使用指针进行构造的列表；又称为结点列表，因为链表是由一个个结点组装起来的；其中每个结点都有指针成员变量指向列表中的下一个结点；
列表是由结点构成，head指针指向第一个成为表头结点，而终止于最后一个指向nuLL的指针。

用法：

//一个链表结构体的声明

1
2
3
4
typedef struct NODE{
	struct NODE *next;
	int	  data;
}Node;

单链表的指向，链表的起始位置我们成为根指针(root)，它指向链表的第一个节点。根指针不包含任何数据，它只是一个指针。
Node *root;
下一个节点的访问通过root->next来实现

1.初始化链表：

1
2
3
4
5
6
7
8
9
10
int InitNodeList(Node **node)
{
	*node=(Node*)malloc(sizeof(Node));//链表分配内存空间
	if(!*node)
	{
		return 0;
	}
	(*node)->next=NULL;
 	return 1;
}

注：初始化时，这里的指针为二级指针，因为我们想要获取链表的根指针，如果只传入一级指针，malloc后得到的为分配内存的首地址给node，而不能被主函数中指针变量root得到这个地址。

2.插入数据：

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
/*
按值的大小顺序进行插入，把值插入到合适的位置
*/
int InsertNodeList(Node **root,int data)
{
  Node *current;
  Node *previous;
  Node *new;

  current = *root;
  previous = NULL; /*用于判断新插入的值是否在第一个节点*/
  
  /*寻找正确的插入位置，按序访问链表，直到到达一个其值大于或等于新值的节点*/
  while(current != NULL && current->data < data)
  {
    previous = current;
    current  = current->next;
  }
  
  /*新节点分配内存空间*/
  new = (Node *)malloc(sizeof(Node));
  if(new == NULL)
  {
    return false;
  }
  /*新节点插入链表*/
  new->data = data;
  /*如果插入的值在根节点，把新节点指向根节点，否则前一个节点，指向新节点*/
  if (previous == NULL)
  {
    *root = new;
  }
  else
  {
    previous->next = new;
  }
  return true;
}

3.获取链表长度

1
2
3
4
5
6
7
8
9
10
11
12
13
int LengthNodeList(Node *root)
{
  int i = 0;
  Node *previous;
  previous=root->next;/*p指向链表的第一个结点。*/
  /*循环链表，直到节点为空*/
  while(previous)
  {
    i++;
    previous=previous->next;
  }
  return i;
}

4.删除节点：

1
2
3
4
5
6
7
8
9
10
11
12
void DestroyNodeList(Node *root)
{
  Node *current,*next;
  current=root;/*current 指向链表的根结点*/
  /*当节点指向为空，即到了链表末尾，跳出*/
  while(current)
  {
    next = current->next;/*指向当前结点的下一个结点。*/
    free(current);/*释放当前结点*/
    current = next;/*指向下一个结点*/
  }
}

5.调用：

1
2
3
4
5
6
7
8
9
10
int main(void)
{
	Node *root;
	int node_length = 0;
	InitNodeList(&root);  /*初始化链表，得到一个跟节点*/
	InsertNodeList(&root,10); /*向链表中插入一个数据*/
	node_length = LengthNodeList(root); /*获取链表长度*/
	DestroyNodeList(root); /*销毁链表*/
	return 0;
}

双向链表

含义：

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

特点：

1）在数据结构中具有双向指针
2）插入、删除数据的时候需要考虑前后的方向的操作

用法：

一个链表结构体的声明

1
2
3
4
5
typedef struct NODE{
	struct NODE *prev;
	struct NODE *next;
	int	  data;
}Node;

1.初始化链表：

1
2
3
4
5
6
7
8
9
10
11
int InitNodeList(Node **node)
{
	*node=(Node*)malloc(sizeof(Node));//链表分配内存空间
	if(!*node)
	{
		return 0;
	}
	(*node)->prev=NULL;
	(*node)->next=NULL;
 	return 1;
}

2.插入数据：

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
int InsertNodeList(register Node *root,int data)
{
  register Node *this;
  register Node *next;
  register Node *newnode;

  for(this = root;(next = this->next)!= NULL; this =next)
  {
    if(next->data == data)
    {
      return 0;
    }  
    if(next->data > data)
    {
      break;
    }  
  }
    /*新节点分配内存空间*/
  newnode = (Node *)malloc(sizeof(Node));
  if(newnode == NULL)
  {
    return -1;
  }
  
  /*新节点插入链表*/
  newnode->data = data;
  
  /*插入新节点*/
  newnode->next = next;
  this->next = newnode;
  
  if(this != root)
  {
    newnode->prev = this;
  }
  else
  {
    newnode->prev = NULL;
  }
  
  if(next != NULL)
  {
    next->prev = newnode;
  }
  else
  {
    root->prev = newnode;
  }
  return 1;
}

3.获取链表长度

1
2
3
4
5
6
7
8
9
10
11
12
13
int LengthNodeList(Node *root)
{
  int i = 0;
  Node *previous;
  previous=root->next;/*p指向链表的第一个结点。*/
  /*循环链表，直到节点为空*/
  while(previous)
  {
    i++;
    previous=previous->next;
  }
  return i;
}

4.删除节点：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void DestroyNodeList(Node *root)
{
  Node *current,*next;
  
  if(root == NULL)
  {
    return; 
  }
  
  current=root;/*current 指向链表的根结点*/
  /*当节点指向为空，即到了链表末尾，跳出*/
  while(current)
  {
    next = current->next;/*指向当前结点的下一个结点。*/
    free(current);/*释放当前结点*/
    current = next;/*指向下一个结点*/
  }
}

5.调用：

1
2
3
4
5
6
7
8
9
10
11
12
int main(void)
{
	Node *root;
	int node_length = 0;
	InitNodeList(&root);  /*初始化链表，得到一个跟节点*/
	InsertNodeList(root,10); /*向链表中插入一个数据*/
	InsertNodeList(root,20); /*向链表中插入一个数据*/
	node_length = LengthNodeList(root); /*获取链表长度*/
	printf("%d\n",node_length);
	DestroyNodeList(root); /*销毁链表*/
	return 0;
}
Tianger Ge wechat
如果您喜欢这篇文章，欢迎扫一扫我的微信公众号！