C语言编程精讲之链表

hhhkhhh

贡献于2012-02-23

字数:0 关键词: C/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 structnode{//一个可以用于构建链表的结构体类型 void *DATA; structnode *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 我们的节点结构体类型 typedefstructst { intnum; char name[20]; structst*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指针地址作为参数则申明应为 intincrease(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()

下载文档,方便阅读与编辑

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 8 金币 [ 分享文档获得金币 ] 2 人已下载

下载文档

相关文档