C语言——链表讲解

一时失言乱红尘 2022-03-02 06:59 203阅读 0赞

详细见原博文：[https://blog.csdn.net/endeavor\_g/article/details/80552680][https_blog.csdn.net_endeavor_g_article_details_80552680]

链表是一种常见的基础数据结构，结构体指针在这里得到了充分的利用。链表可以动态的进行存储分配，也就是说，链表是一个功能极为强大的数组，他可以在节点中定义多种数据类型，还可以根据需要随意增添，删除，插入节点。链表都有一个头指针，一般以head来表示，存放的是一个地址。链表中的节点分为两类，头结点和一般节点，头结点是没有数据域的。链表中每个节点都分为两部分，一个数据域，一个是指针域。说到这里你应该就明白了，链表就如同车链子一样，head指向第一个元素：第一个元素又指向第二个元素；……，直到最后一个元素，该元素不再指向其它元素，它称为“表尾”，它的地址部分放一个“NULL”（表示“空地址”），链表到此结束。

作为有强大功能的链表，对他的操作当然有许多，比如：链表的创建，修改，删除，插入，输出，排序，反序，清空链表的元素，求链表的长度等等。

初学链表，一般从单向链表开始

—>NULL  
head  
这是一个空链表。

\---->\[p1\]---->\[p2\]…---->\[pn\]---->\[NULL\]  
head p1->next p2->next pn->next  
有n个节点的链表。

创建链表

typedef struct student\{  
int score;  
struct student \*next;  
\} LinkList;  
一般创建链表我们都用typedef struct，因为这样定义结构体变量时，我们就可以直接可以用LinkList \*a;定义结构体类型变量了。

初始化一个链表，n为链表节点个数。

LinkList \*creat(int n)\{  
LinkList \*head, *node, end;//定义头节点，普通节点，尾部节点；  
head = (LinkList)malloc(sizeof(LinkList));//分配地址  
end = head; //若是空链表则头尾节点一样  
for (int i = 0; i < n; i++) \{  
node = (LinkList*)malloc(sizeof(LinkList));  
scanf("%d", &node->score);  
end->next = node;  
end = node;  
\}  
end->next = NULL;//结束创建  
return head;  
\}  
修改链表节点值

修改链表节点值很简单。下面是一个传入链表和要修改的节点，来修改值的函数。

void change(LinkList \*list,int n) \{//n为第n个节点  
LinkList \*t = list;  
int i = 0;  
while (i < n && t != NULL) \{  
t = t->next;  
i++;  
\}  
if (t != NULL) \{  
puts(“输入要修改的值”);  
scanf("%d", &t->score);  
\}  
else \{  
puts(“节点不存在”);  
\}  
\}  
删除链表节点

删除链表的元素也就是把前节点的指针域越过要删除的节点指向下下个节点。即：p->next = q->next;然后放出q节点的空间，即free(q);

void delet(LinkList \*list, int n) \{  
LinkList \*t = list, \*in;  
int i = 0;  
while (i < n && t != NULL) \{  
in = t;  
t = t->next;  
i++;  
\}  
if (t != NULL) \{  
in->next = t->next;  
free(t);  
\}  
else \{  
puts(“节点不存在”);  
\}  
\}

插入链表节点

我们可以看出来，插入节点就是用插入前节点的指针域链接上插入节点的数据域，再把插入节点的指针域链接上插入后节点的数据域。根据图，插入节点也就是：e->next = head->next; head->next = e;

增加链表节点用到了两个结构体指针和一个int数据。

void insert(LinkList \*list, int n) \{  
LinkList \*t = list, *in;  
int i = 0;  
while (i < n && t != NULL) \{  
t = t->next;  
i++;  
\}  
if (t != NULL) \{  
in = (LinkList*)malloc(sizeof(LinkList));  
puts(“输入要插入的值”);  
scanf("%d", &in->score);  
in->next = t->next;//填充in节点的指针域，也就是说把in的指针域指向t的下一个节点  
t->next = in;//填充t节点的指针域，把t的指针域重新指向in  
\}  
else \{  
puts(“节点不存在”);  
\}  
\}  
输出链表

输出链表很简单，边遍历边输出就行了。

while (h->next != NULL) {
    	h = h->next;
    	printf("%d  ", h->score);
    }

--------------------

[https_blog.csdn.net_endeavor_g_article_details_80552680]: https://blog.csdn.net/endeavor_g/article/details/80552680