首页 > 代码库 > C和指针 (pointers on C)——第十二章:使用结构和指针
C和指针 (pointers on C)——第十二章:使用结构和指针
第十二章 使用结构和指针
这章就是链表。先单链表,后双向链表。
总结:
单链表是一种使用指针来存储值的数据结构。链表中的每个节点包含一个字段,用于指向链表的下一个节点。
有一个独立的根指针指向链表的第1个节点。单链表只能从一个方向遍历。
如何insert单链表:1、新节点的link字段必须设置为指向它的后面节点。2、前一个节点的link字段必须指向这个新节点。
为了防止可能会插入链表的起始位置这种情况,在C中,可以保存一个指向必须进行修改的link字段的指针,而不是保存一个指向前一个节点的指针。
双链表中的每个节点包含两个link字段:其中一个指向链表的下一个node,另一个指向前一个node。
双链表有两个根指针,一个指向第一个node,另一个指向最后一个node。因此遍历的过程中可以从任何一端开始,而且在遍历过程中够可以改变方向。
为了把一个新节点插入到双链表中,我们必须修改4个指针。新节点的前向和后向link字段必需被设置,前一个节点的fwd和后一个节点的bwd也要修改,指向新节点。
警告:
1、落到链表尾部的后面。
2、使用指针时应该格外小心,因为C并没有对他们的使用提供安全网。
3、从if语句中提炼语句可能会改变测试结果。
编程提示:
1、消除特殊情况使代码更易于维护。
2、不要轻易的进行提炼语句,这样会使你的语句更难维护。
编程实例:(本章就不再弄习题了,关于数据结构这块会有大量代码进行训练)
1、提炼后的单链表插入操作
#include "stdlib.h" typedef struct NODE { struct NODE *link; int value; } Node; int sll_int(register Node **linkp, int new_value) { register Node *current; //指向当前节点 register Node *new_node; //指向插入节点 /* ** 寻找正确插入位置,按顺序访问链表,直到有个值大于或等于新值 */ while ((current = current->link) != NULL && current->value < new_value) { linkp = ¤t->link; //移动linkp指向下一个Node的link } /* 分配新的内存,并存到新节点去 */ new_node = (NODE *) malloc (sizeof(NODE)); if (new_node == NULL) { return 0; } new_node->value = http://www.mamicode.com/new_value;>
2、双链表插入操作#include "stdlib.h" typedef struct NODE { struct NODE *fwd; struct NODE *bwd; int value; }Node; int dll_insert(Node *rootp, int value) { /* 把一个值插入到一个双向链表中,rootp是一个指向根节点的指针 value 是插入的新值 返回值:如果已经存在链表中,返回0 如果内存不足导致无法插入,返回-1,成功返回1; */ Node *this_node; Node *next_node; Node *new_node; for (this_node = rootp; next_node != NULL; this_node = next_node ) { if (next_node->value =http://www.mamicode.com/= value)>C和指针 (pointers on C)——第十二章:使用结构和指针
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。