C语言编程精讲之链表

RE.ER嵌入式学院 http://www.re-er.com.cn 简单链表 RE.ER嵌入式学院--http://www.re-er.com.cn n 什么是链表？ 链表是一种通过结构体其指针成员共同组成的线性数据 结构。 RE.ER嵌入式学院--http://www.re-er.com.cn DATA link DATA link DATA link DATA link NULL head 以上是一个单链表的逻辑图。 容易看出，链表中的每一个节点都由两部分组成： 1、数据域（DATA）； 2、指针域（link）。 RE.ER嵌入式学院--http://www.re-er.com.cn DATA link DATA link DATA link DATA link NULL head 链表的数据域和指针域都是节点结构体的成员。 数据域用于存储数据； 指针域是指向节点结构体类型的指针。 RE.ER嵌入式学院--http://www.re-er.com.cn DATA link DATA link DATA link DATA link NULL head struct node{ //一个可以用于构建链表的结构体类型 void *DATA; struct node *link; } RE.ER嵌入式学院--http://www.re-er.com.cn DATA link DATA link DATA link DATA link NULL head 头指针：每一个链表都有一个头(head)指针，作为链表的起 始点，整个链表的操作都必须从head指针开始进行。当head 指针为空时，代表链表没有节点。 RE.ER嵌入式学院--http://www.re-er.com.cn DATA link DATA link DATA link DATA link NULL head 非循环链表的最后一个节点的link指针总是指向NULL。 RE.ER嵌入式学院--http://www.re-er.com.cn n 链表的部分基本操作 increase() //增加一个节点 print() //遍历并打印链表 cleanup() //清空链表 RE.ER嵌入式学院--http://www.re-er.com.cn 实现 n 在结构体中申明一个指向这种结构体的指针，并用这个指 针记录下一个这种结构体的地址，这样，就可以利用结构 体和结构体中的指针依次链接成为一个链表。 RE.ER嵌入式学院--http://www.re-er.com.cn 我们的节点结构体类型 typedef struct st { int num; char name[20]; struct st *next; }ST; RE.ER嵌入式学院--http://www.re-er.com.cn n ST * increase(ST *head, ST *node) 函数的实现。 RE.ER嵌入式学院--http://www.re-er.com.cn ST * increase(ST *head, ST *node) head NULL 如果链表为空，则head指向NULL node指针指向一个结构体，结构体成 员都已经被赋上相应的值 添加链表的第一个节点，只需把 head指针指向node指向的节点。node NULL RE.ER嵌入式学院--http://www.re-er.com.cn node指针的由来 ST* buildnod(int a, char*str) { ST *temp = (ST*)malloc(sizeof(ST)); if(temp == NULL) { return NULL; } temp->num = a; strcpy(temp->name, str); temp->next = NULL; return temp; } node NULL RE.ER嵌入式学院--http://www.re-er.com.cn ST * increase(ST *head, ST *node) 如果链表不为空，则head != NULL 1、添加到链表最尾部 准备添加第2个节点 head NULL node NULL 需要遍历整个链表，找到最后一个节 点，然后把尾指针指向新加入的节点 temp = head; while(temp->next !=NULL) { temp = temp->next; } temp->next = node; RE.ER嵌入式学院--http://www.re-er.com.cn ST * increase(ST *head, ST *node) 1、添加到链表最尾部 head NULL node NULL 2、添加到链表头部 将node节点的next指针指向head， 然后把head指针指向新的头部并返回 node->next = head; head = node; RE.ER嵌入式学院--http://www.re-er.com.cn ST * increase(ST *head, ST *node) head node NULL NULL 类似increase() 的函数，head指针有可能被改变，则我们需 要通过返回值或传head指针地址的方式设计代码。 如：head = increase(head, node); 如果head指针地址作为参数则申明应为 int increase(ST **headp, ST *node); //推荐 调用函数语句：increase(&head, node); RE.ER嵌入式学院--http://www.re-er.com.cn 遍历一个链表 temp NULL 链表的任何操作都是从头节点开始的，遍历链表是很多链 表操作的基础。如打印、计数、查找等等。 head RE.ER嵌入式学院--http://www.re-er.com.cn 遍历一个链表 temp NULL 如果有一个temp指针也指向头节点，则很常见的两种遍历 链表语句是： while(temp != NULL){temp = temp->next;} while(temp->next != NULL){temp = temp->next;} head RE.ER嵌入式学院--http://www.re-er.com.cn 遍历一个链表 head NULL while(temp != NULL){temp = temp->next;} while(temp->next != NULL){temp = temp->next;} 在以上循环的语句块内加入如 printf(“%s\n”,temp->str); //打印 if(temp->num == NUM){ break; } //查找 等语句 就可以实现不同的功能。cleanup()也可以通过这样实现。 RE.ER嵌入式学院--http://www.re-er.com.cn 建立函数creat() n 建立链表的函数creat()实际上可以通过循环调用buildnode() 和increase()得到。 n 甚至可以认为，这个函数（功能）本身就是多余的。 RE.ER嵌入式学院--http://www.re-er.com.cn 练习 n 使用链表完成 st_increase() st_count() st_print() st_search() st_cleanup()