/*******************************双链表**************************/ #include<stdio.h> #include<stdlib.h> #include<assert.h> #define FALSE 0 #define TRUE 1 // 双链表声明 typedef struct NODE { struct NODE *fwd; struct NODE *bwd; int value; }Node; // 双链表的创建,返回头指针 Node *CreatList(int n) { Node *head,*pNode,*sNode; int i; head=(Node *)malloc(sizeof(Node)); head->bwd=NULL; head->fwd=NULL; pNode=head; for(i=1;i<=n;i++) { sNode=(Node *)malloc(sizeof(Node)); sNode->value=i; sNode->bwd = NULL; sNode->fwd = NULL; pNode->fwd=sNode; sNode->bwd=pNode; pNode=sNode; } return(head); } // 打印双链表数据(传递双向链表头head) void print_link(Node *head) { Node *pNode=head->fwd; while(pNode!=NULL) { printf("%d\n",pNode->value); pNode=pNode->fwd; } } /*双链表的插入 ** 把一个值插入到双链表,rootp是一个指向根节点的指针 ** value 是欲插入的新值 ** 返回值:如果欲插入的值已存在链表中,函数返回0; ** 如果内存不足导致无法插入,函数返回-1;,如果插入成功,函数返回1; */ int dll_insert(Node *rootp,int value) { Node *thist; Node *next; Node *newnode; /*查看value是否存在链表中,有就返回, ** 否则为新值创建一个新的节点 ** thist 指向新节点之前那个节点 ** next 指向新节点之后那个节点 */ for(thist = rootp;(next = thist->fwd) != NULL;thist = next) { if (next->value == value) return 0; if (next->value > value) break; } newnode = (Node *)malloc(sizeof(Node)); if(newnode == NULL) return -1; newnode->value = value; /* ** 把新值添加到链表中 */ /* **最初版,分析了四种不同情况。 */ /* if(next != NULL) { // 情况1或者2:并非位于链表尾部 if(thist!=rootp) //情况1:并非位于链表的起始位置 { newnode->fwd = next; thist->fwd = newnode; newnode->bwd = thist; next->bwd = newnode; } else //情况2:位于链表的起始位置 { newnode->fwd = next; rootp->fwd = newnode; newnode->bwd = NULL; next->bwd = newnode; } } else //情况3或者4:位于链表尾部 { if(thist != rootp) //情况3:并非位于链表的起始位置 { newnode->fwd = NULL; thist->fwd = newnode; newnode->bwd = thist; rootp->bwd = newnode; } else //情况4:位于链表的起始位置 { newnode->fwd = NULL; rootp->fwd = newnode; newnode->bwd = NULL; rootp->bwd = newnode; } } */ /* **简化版,对比上面可读性不强,运行速度并不比前面的快。 */ newnode->fwd = next; thist->fwd = newnode; if(thist!=rootp) newnode->bwd = thist; else newnode->bwd = NULL; if(next != NULL) next->bwd = newnode; else rootp->bwd = newnode; return 1; } /*双链表的删除 ** 把一个值插入到双链表,rootp是一个指向根节点的指针 ** del 是指向欲移除节点的指针 ** 返回值: ** 如果链表不包含移除的节点,函数就返回假,否则返回真。 */ int dll_remove(Node *rootp, Node *del) { register Node *thist; assert( del != NULL); for(thist=rootp->fwd; thist != NULL; thist = thist->fwd) if(thist == del) break; if(thist == del) { /* ** Update fwd pointer of the previous node. */ if( thist->bwd == NULL ) rootp->fwd = thist->fwd; else thist->bwd->fwd = thist->fwd; /* ** Update bwd pointer of the next node. */ if( thist->fwd == NULL ) rootp->bwd = thist->bwd; else thist->fwd->bwd = thist->bwd; free( thist ); return TRUE; } else return FALSE; }
收藏0 举报
本版积分规则 发表回复 回帖并转播 回帖后跳转到最后一页
等级类勋章
发帖类勋章
时间类勋章
人才类勋章
293
3837
81
扫码关注 21ic 官方微信
扫码关注嵌入式微处理器
扫码关注电源系统设计
扫码关注21ic项目外包
扫码浏览21ic手机版
本站介绍 | 申请友情链接 | 欢迎投稿 | 隐私声明 | 广告业务 | 网站地图 | 联系我们 | 诚聘英才
京公网安备 11010802024343号