1, 双链表
1.1 双向链表的声明
在一个双链表中, 每个节点都包含两个指针 -- 指向前一个节点的指针和指向后一个节点的指针.
声明
- typedef struct NODE {
- struct NODE *fwd;
- struct NODE *bwd;
- int value;
- } Node;
根节点的 fwd 字段指向链表的第 1 个节点, 根节点的 bwd 字段指向链表的最后一个节点. 如果链表为空, 这两个字段都为 NULL. 链表的第 1 个节点的 bwd 字段和最后一个节点的 fwd 字段都为 NULL. 在一个有序的链表中, 各个节点将根据 value 字段的值以升序排列.
3.2 双向链表的插入
将一个新值插入到有序表中
函数原型
dll_insert( Node *rootp, int value );
dll_insert 接受两个参数, 一个指向根节点的指针和一个整型值.
插入节点时, 可能会遇到 4 中情况:
1, 新值可能必须插入到链表的中间位置
2, 新值可能必须插入到链表的起始位置
3, 新值可能必须插入到链表的结束位置
4, 新值可能必须既插入到链表的起始位置, 又插入到链表的结束位置
- /**
- 向双向链表中插入数据
- @param rootp 根节点
- @param value 带插入值
- @return 0 已经有值, -1 不能插入, 1 插入成功
- */
- int dll_insert( Dnode *rootp, int value) {
- Dnode *this;
- Dnode *next;
- Dnode *newnode;
- // 查看 value 是否已经存在于链表中, 如果是就返回. 否则, 为新值创建一个新节点 ("newnode" 将指向它)
- //this 将指向应该在新节点之前的那个节点
- //next 将指向应该在新节点之后的那个节点
- for( this = rootp; (next = this->fwd) != NULL; this = next){
- if (next->value == value) {
- return 0;
- }
- if (next->value> value) {
- break;
- }
- }
- newnode = (Dnode *)malloc( sizeof( Dnode) );
- if ( newnode == NULL) {
- return -1;
- }
- newnode->value = value;
- // 把新值添加到链表中
- if ( next != NULL) {
- // 情况 1,2 并非位于链表尾部.
- if ( this != rootp ) {// 情况 1 并非位于链表起始位置
- newnode->fwd = next;
- this->fwd = newnode;
- newnode->bwd = this;
- next->bwd = newnode;
- }else {// 情况 2 位于起始位置
- newnode->fwd = next;
- this->fwd = newnode;
- newnode->bwd = NULL;
- next->bwd = newnode;
- }
- }else {
- // 情况 3,4 位于链表的尾部
- if (this != rootp) {// 情况 3 并非位于链表的起始位置
- newnode->fwd = NULL;
- this->fwd = newnode;
- newnode->bwd = this;
- rootp->bwd = newnode;
- }else {// 情况 4 位于链表起始位置
- newnode->fwd = NULL;
- this->fwd = newnode;
- newnode->bwd = NULL;
- rootp->bwd = newnode;
- }
- }
- return 1;
- }
- // 添加节点的 4 种情况可以提炼
- if ( next != NULL) {
- // 情况 1 或 2 并非位于链表的尾部
- newnode->fwd = next;
- if (this != rootp ) {// 情况 1 并非位于链表的起始位置
- this->fwd = newnode;
- newnode->bwd = this;
- }else {// 情况 2 位于链表的起始位置
- rootp->fwd = newnode;
- newnode->bwd = NULL;
- }
- next->bwd = newnode;
- }else {
- // 情况 3 或 4 位于链表尾部
- newnode->fwd = NULL;
- if (this != rootp) {// 情况 3 并不位于链表起始位置
- this->fwd = newnode;
- newnode->bwd = this;
- }else {// 情况 4 位于链表起始位置
- rootp->fwd = newnode;
- newnode->bwd = NULL;
- }
- rootp->bwd = newnode;
- }
来源: http://www.bubuko.com/infodetail-2972347.html