链表是什么及链表的优势
链表是一种介于数组的另外一种数据结构:
我们知道数组可以存放很多的元素,这些元素都是呈线性排列,也就是一个挨着一个连续存放
但是当元素足够多时,还能继续正常的存放吗?
事实上的不可以的,虽然系统的内存足够大,但是这些内存不都是连续的,这就导致会出现没有足够的空间去存储这些元素。
其次就是数组的大小需要你去申请,如果你申请的空间足够大,就会导致内存的浪费
而链表就很好的解决了这两个问题
链表的组成
链表的作用就是相当与数组一样,储存你数据的
但又不同于数组,链表把每一个游离的数据进行连接,连接的方法通过的是指针,也就是地址,
每一个链表都是由一个个结点组成,结点包含,一个是为我们存放数据的空间,另一个是存放下一个结点地址的空间,也就是所谓的数据域和地址域。
链表有时候包括了头结点,它是为了方便而设计的结点,这个头结点一般只包含地址域,也就是结点1的地址,一般情况下,头结点的数据域一般无意义。
最后的结点,指向的是NULL,用来限制链表的大小
单向链表结点的定义
说完链表的组成是结点,那单向链表的结点是如何定义的呢
1
2
3
4
5
6
7
8
9
|
struct Node //链表的结点 { int data; //结点的值 struct Node *next; //下一个结点的地址 }; |
单项链表的创建
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
//创建所需的结点 struct Node* createList( int n) { struct Node* first, * t, * last; int i; first = ( struct Node*) malloc ( sizeof ( struct Node)); //给第一个结点数据赋个值 scanf_s( "%d" , &first->data); last = first ; //在创建其他的结点 for (i = n - 1; i > 0; i--) { //再首尾中间插入结点.并赋值 t= ( struct Node*) malloc ( sizeof ( struct Node)); scanf_s( "%d" , &t->data); last->next = t; last=t; } last->next = NULL; //防止野指针的存在 return first; } |
其中的first,last,还有t,都是指针变量,用来存放各个节点的地址
sizeof(struct listnode)
函数返回结构体Node类型占用的字节数
malloc(sizeof(struct Node))
函数功能:系统从内存的空闲空间中,申请存放一个结点的存储空间。
(struct listnode *)malloc(sizeof(struct Node))
,函数返回一个指针(地址),指向刚分配给结构体的第一个字节的地址。
malloc函数在头文件stdlib.h中定义
打印出链表各个结点的数据
1
2
3
4
5
6
7
8
9
10
11
12
|
//再创建函数进行打印出各个结点的值 void printList( struct Node* first) { //把每一个字节数据域的都打印出来 struct Node* p = first; while (p != NULL) { printf ( "%d " , p->data); p = p->next; } printf ( "\n" ); } |
其中传入函数的是结构体指针
从第一个结点的数据域开始打印,到最后的NULL结束
(访问下一个数据域不能用p++,因为链表不是连续的,地址也不是连续的,如果要访问下一个数据,需要用p = p->next)
释放向系统申请的空间
1
2
3
4
5
6
7
8
9
10
11
|
void destoryList( struct Node* first) { struct Node* p = first, *tmp; while (p != NULL) { tmp = p->next; free (p); p = tmp; } } |
这里的 struct Node* p = first, *tmp;
就相当于 struct Node*p=first;
struct Node *tmp;
例题
从键盘输入一组整数,创建单向链表,并输出链表中的数据。
样例输入:2 5 7 6 3 4
样例输出:2 5 7 6 3 4
解答如下:
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
|
#include<stdio.h> #include<stdlib.h> #define N 6 //链表 struct Node { int data; struct Node* next; }; //创建所需的结点 struct Node* createList( int n) { struct Node* first, * t, * last; int i; first = ( struct Node*) malloc ( sizeof ( struct Node)); //给第一个结点数据赋个值 scanf_s( "%d" , &first->data); last = first ; //在创建其他的结点 for (i = n - 1; i > 0; i--) { //再首尾中间插入结点.并赋值 t= ( struct Node*) malloc ( sizeof ( struct Node)); scanf_s( "%d" , &t->data); last->next = t; last=t; } last->next = NULL; //防止野指针的存在 return first; } //再创建函数进行打印出各个结点的值 void printList( struct Node* first) { //把每一个字节数据域的都打印出来 struct Node* p = first; while (p != NULL) { printf ( "%d " , p->data); p = p->next; } printf ( "\n" ); } //释放头结点申请的空间 void destoryList( struct Node* first) { struct Node* p = first, *tmp; while (p != NULL) { tmp = p->next; free (p); p = tmp; } } int main() { struct Node* list; list = createList(N); printList(list); //输出头节点为list的链表 、、、、、、 destoryList(list); printf ( "\n" ); return 0; } |
到此这篇关于C语言链表与单链表详解的文章就介绍到这了,更多相关C语言 链表内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家!
原文链接:https://z-ming.blog.csdn.net/article/details/122400440