小董的BLOG
0%

数据结构_链表

发表于 更新于

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
 typedef struct list
{
	int num; 	//数据域
	struct list *last;	//指针域
}test;

void setlist(test* linkhead, int data)
{
   test *tmp=(test*)malloc(sizeof(test));//分配动态内存，防止生成野指针
   tmp->num=data;
   tmp->last=linkhead->last;
   linkhead->last=tmp;
}

int main()
{
   int a[3]={1,2,3};
   int i;
   test* head=(test*)malloc(sizeof(test));
   head->last=NULL;
   for(i=0;i<3;++i)
   {
      setlist(head,a[i]);
   }
   test* p= head->last;
   while(p!=NULL)
   {
      printf("%d ",p->num);
      p=p->next;
    }
   return 0;
}

前插法创建链表的步骤为（以创建两个节点为例）:

1
2
3
4
5
6
7
8
9
10
11
void setlist(test* linkhead, int data)
{
   //开辟一个新节点
   test *tmp=(test*)malloc(sizeof(test));
   //写入需要的数据
   tmp->num=data;
   //将节点的指针域指向linkhead的指针域
   tmp->last=linkhead->last;
   //将linkhead的指针域指向新节点首地址
   linkhead->last=tmp;
}

也就是说，创建第一个节点时，该节点的指针域先指向NULL后，linkhead指针域再指向该节点首地址。

当刚创建第二个节点时，情况如下：

当执行tmp->last=linkhead->last;时，由于linkhead的指针域此时指向tmp(1)（这里的1指第一块节点的内存空间）的首地址，所以tmp(2)的指针域会通过linkhead直接也指向tmp(1)的首地址:

这样之后，两个节点就通过指针链接在了一起，且tmp(2)在tmp(1)之前。

由此可以看出，前插法的原理就是以linkhead为媒介来链接节点，linkhead本身是不存储数据的

最后，执行linkhead->last=tmp;，将linkhead指针域指向第二个节点首地址，以供第三个节点的指针域找到第二个节点。

以此类推，假如现在创建了4个节点，那情况就应该像这样：

在例程中，由于前插法得到的链表顺序为最后输入的数据开始，所以最后打印的结果为3 2 1

尾插法

相对于前插法，尾插法使用起来逻辑会更加清晰，因为其链接顺序是在每一个节点后，所以尾插法要更容易理解一些。

在结构体复习 | 小董的BLOG (gitee.io)中讲到的列表就是使用的尾插法，核心代码如下：

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
typedef struct list
{
	int num;
	char name[30];
	struct list *next;
}test;

test *creat()
{
	test *linkhead,*linkend,*tmp;
	int i;
	for(i=0;i<3;i++)
	{
		tmp=(test*)malloc(sizeof(test));//分配动态内存
		scanf("%d %s",&tmp->num,tmp->name);
		if(i==0)
		{
			linkhead=tmp;//第一次先将当前节点赋给链头链尾
			linkend=tmp;
		}
		else//若不是第一次，先将当前节点存入上一个节点的next中，再将linkend更新为当前节点以供下一次访问
		{                                                                //当前节点的next
			linkend->next=tmp;//通过linkend直接指向内存中的一个struct list变量使其指向tmp的内存
			linkend=tmp;
         //以第二个节点为例，先将第linkend（也就是tmp(1)）的指针域指向二个节点首地址
         //再将linkend指向tmp(2)，以供后面的节点重复23、24行的操作
		}
	}
	linkend->next=NULL;
	return linkhead;
}

如果说前插法是通过linkhead为媒介进行链接，那尾插法就是通过linkend为媒介链接各节点。

3.双向链表的创建

同样分为使用前插法和后插法，但是尾插法会简单很多，所以先讲一下尾插法

尾插法创建双向链表

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
 typedef struct list
{
	int num;
	char name[30];
	struct list *last;	//存放上一节点
	struct list *next;	//存放下一节点
}test;

test *creat()
{
	test *linkhead,*linkend,*tmp;
	int i;
	for(i=0;i<3;i++)
	{
		tmp=(test*)malloc(sizeof(test)); 
		scanf("%d %s",&tmp->num,tmp->name);
		if(i==0)
		{
			linkhead=tmp;
			linkend=tmp;
			linkhead->last=NULL; //因为链头没有上一节点，固其last指针域指向NULL
		}
		else
		{
			tmp->last=linkend;	//把上一节点地址存入本节点的last指针中
			linkend->next=tmp;
			linkend=tmp;
		}
	}
	linkend->next=NULL;
	return linkhead;
}

尾插法由于其创建链表的方式为顺序创建，因此只需在原有的基础上添加存放上一节点的指针就行了

使用双向链表会增加内存，但是就可以通过任意节点找到其他节点了。

使用前插法创建双向链表

使用前插法的话会稍微麻烦一些，而且理解起来也会有点绕，感觉用尾插法好一些。

（这是我自己写的方法，感觉有点绕）

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
 typedef struct list
{
	int num; 	//数据域
	struct list *last;	
   struct list *next;	
}test;

int time=1;
test* InsertList(test *head,int val)
{
   test *tmp,*end;
   tmp=(test *)malloc(sizeof (test));
	if(time==1) //建立第一个节点时将该节点作为链尾
	{
		tmp->num=val;
		tmp->last=head->last;
		head->last=tmp;	
		end=tmp;	//end作为链尾将一直指向第一个建立的节点，后续不再改变end
	}
	else
	{
		tmp->num=val;
		tmp->last=head->last;
		head->last->next=tmp;	//将上一个节点的next指针指向当前节点（有点套娃的感觉）
		head->last=tmp;
		tmp->next=NULL; //每个节点的next先清零，为了让最后一个节点指向null
	}
	++time;
	return end;
}

int main()
{
   int a[3]={1,2,3};
   int i;
   test *linkhead, *linkend;
   linkhead=(test *)malloc(sizeof (test));
   linkhead->last=NULL;
   for(i=2;i>=0;--i) //由于是前插法，所以输入倒序输入
   {
      linkend=InsertList(linkhead,a[i]);
   }
   test *p1,*p2;
   p1=linkhead->last;
   p2=linkend;
   while(p1!=NULL)
   {
      printf("%d\n",p1->num);
      p1=p1->last;      
   }
   while(p2!=NULL)
   {
      printf("%d\n",p2->num);
      p2=p2->next;      
   }
	system("pause");
   return 0;   
}

在写这个双向链表时我遇见了个问题：对于linkend变量，我在主函数中定义后，像通过像linkhead一样的方式对linkend进行改变，但是始终无法实现：

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
void InsertList(test *head,test *end;int val)
{
   test *tmp,*end;
   tmp=(test *)malloc(sizeof (test));
	if(time==1) 
	{
		tmp->num=val;
		tmp->last=head->last;
		head->last=tmp;	
		end=tmp;	
	}
	else
	{
		tmp->num=val;
		tmp->last=head->last;
		head->last->next=tmp;	
		head->last=tmp;
		tmp->next=NULL;
	}
	++time;
}

int main()
{
   test *linkhead, *linkend;
   linkhead=(test *)malloc(sizeof (test));
   linkhead->last=NULL;
	...
}

如果在主函数中没有对linkend分配内存，linkend将成为一个野指针，无法指向字符值常量。

但是如果分配了内存，由于linkhead是通过last成员来寻找链表，但是linkend却无法像linkhead一样正常实现功能，在经过整整一天的查找资料＆调试后，终于发现了原因：

当一个函数的形参是结构体指针时，这个形参本身的地址（不是所指向的地址）和实参的地址（也不是所指向的地址）是不同的。用例程举例：

  • &linkend≠&end，因此，在函数中改变形参end所指向的内容是完全不会影响实参linkend的，因为此时这两位可以理解成两个变量

那这时大家肯定会有个疑惑：那linkhead为什么就可以实现想要链表功能呢？

我们仔细看InsertList函数中的内容，你肯定会发现，函数中没有出现直接操作linkhead的操作，只有操作linkhead成员的操作，这里就引出了一个折磨了我半天的知识点：

  • 对于一个结构体指针形参，形参名的地址和实参名的地址是不能划等号的，但是形参成员的地址和实参成员的地址是完全相同的，用例程举个例子

    1
    2
    &linkend≠&end
    linkend->next=end->next      (=是等于的意思，不是赋值的意思)

其实这里的解释有点类似于在结构体复习 | 小董的BLOG (gitee.io)最后我对一重指针的解释：

  • 假如有两个并列的指针指向同一个变量，你不能通过改变其中一个指针的指向来影响另一个指针的指向

那么这时又引出了一个问题，形参end和实参linkend指向哪里？

先说一下结论：linkend和end都指向linkend的第一个成员num的地址。

也就是说，形参end和实参linkend作为两个不同的指针变量，他们指向了同一个地址（也许可以通过这一特性来写一个链表？但是我不想写了😋）

其实这个知识点符合我们对形参和指针变量的认知，所以这里比较重要的点其实是：

  • 不同于数组，结构体指针名地址≠第一个成员的地址，但指针名指向第一个成员的地址，可以理解为，结构体指针名指向一块内存，该内存是由若干个结构体成员组成的，这些成员的类型在定义结构体时确定。

这也加深了我对end=(LNode*)malloc(sizeof (LNode));的理解，其实就是一个指针指向了一块内存，但是可以通过结构体的方式访问这块内存中的成员

总结

  • 当一个函数的参数是结构体指针时，操作这个函数的形参名不会影响实参，同时这个形参名的作用域只限于函数体；但是操作这个形参的任何成员等同于直接操作实参的对应成员，因为它们本身的地址是相同的
  • 结构体指针名指向第一个成员的地址

所以，结构体指针并不一定要指向一个明确的结构体，当他指向一块内存时，可以通过直接赋值结构体指针成员的方式操作这块内存（这块内存其实就是一个隐式的，没有具体名字的结构体）

一些感想：好久没有遇到过这么折磨的问题了，一开始完全没有头绪，网络上对于这方面的讲解也是几乎没有，还好找到了这篇博客启发了我C语言理解指针作为形参作用（博客中用的C++，但是原理是完全相同的）