C和指针 第十二章 使用结构和指针 双链表和语句提炼

双链表中每个节点包含指向当前和之后节点的指针，插入节点到双链表中需要考虑四种情况：

1、插入到链表头部

2、插入到链表尾部

3、插入到空链表中

4、插入到链表内部

#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0

//指针fwd指向前一个节点，bwd指向后一个节点
typedef struct NODE {
	struct NODE *fwd;
	struct NODE *bwd;
	int value;
} Node;

//插入value到双链表中，rootPtr为指向节点的指针
int doubleLinklistInsert(Node *rootPtr, int value)
{
	Node *this;
	Node *next;
	Node *newNode;

	for(this = rootPtr; (next = this -> fwd) != NULL; this = next){
		//如果节点值已经存在
		if(next	-> value == value){
			return FALSE;
		}
		//找到插入位置
		if(next -> value > value){
			break;
		}
	}

	//分配内存
	newNode = (Node *)malloc(sizeof(Node));
	if(newNode == NULL){
		return FALSE;
	}

	newNode -> value = value;

	/*插入节点一共四种情况
	1.插入到头部
	2.插入到尾部
	3.插入到中间
	4.插入到空链表中
	*/
	//如果插入到头部部或者内部
	if(next != NULL){
		//插入到内部
		if(this != rootPtr){
			newNode -> fwd = next;
			newNode -> bwd = this;
			this -> fwd = newNode;
			next -> bwd = newNode;
		}else{
			//插入到头部,newNode的bwd为NULL
			newNode -> fwd = next;
			newNode -> bwd = NULL;
			rootPtr -> fwd = newNode;
			next -> bwd = newNode;
		}
	}else{
		//插入到尾部或者空表中
		if(this != rootPtr){
			//插入到尾部，修改根指针的bwd和fwd
			newNode -> fwd = NULL;
			newNode -> bwd = this;
			this -> fwd = newNode;
			rootPtr -> bwd = newNode;
		}else{
			//插入到空链表中
			newNode -> fwd = NULL;
			newNode -> bwd = NULL;
			this -> fwd = newNode;
			this -> bwd = newNode;
		}
	}

	return TRUE;
}

int main()
{
	Node third;
	Node second;
	Node first;

	third = (Node){NULL, &second, 4};
	second = (Node){&third, &first, 2};
	first = (Node){&second, NULL, 1};

	Node root = {&first, &third, -1};
	Node *rootPtr = &root;

	doubleLinklistInsert(rootPtr, 35);
	doubleLinklistInsert(rootPtr, -10);
	doubleLinklistInsert(rootPtr, 3);

	rootPtr = &root;
	while((rootPtr = rootPtr -> fwd) != NULL){
		printf("%d	", rootPtr -> value);
	}
	return 0;
}

　　运行：

优化：

1.语句提炼

对于下面的代码可以从if语句中，提取出共同的部分。

if(x = 3){
    i = 1;
    something;
}else{
    i = 1;
    something different;        
}

将共同的i=1,提取出if语句

 i = 1;
if(x = 3){
    something;
}else{
    something different;        
}

代码提炼：提取共同项

    if(next != NULL){
        newNode -> fwd = next;
        next -> bwd = newNode;
        //插入到内部
        if(this != rootPtr){
            newNode -> bwd = this;
            this -> fwd = newNode;
        }else{
            //插入到头部,newNode的bwd为NULL
            newNode -> bwd = NULL;
            rootPtr -> fwd = newNode;
        }
    }else{
        //插入到尾部或者空表中
        newNode -> fwd = NULL;
        this -> fwd = newNode;
        if(this != rootPtr){
            //插入到尾部，修改根指针的bwd和fwd
            newNode -> bwd = this;
            rootPtr -> bwd = newNode;
        }else{
            //插入到空链表中
            newNode -> bwd = NULL;
            this -> bwd = newNode;
        }
    }

对于下面的情况

if(field!= NULL){
    pointer = field;
}else{
    pointer=NULL;
}
//第二种情况field等于NULL，所以上面条件语句可以写成
pointer =field;

要找出看起来虽然不一样，但逻辑上是相同的代码，进行简化，这里第二个else中this此时是等于rootPtr的，所以相同, this转换成rootPtr，然后提取出。提取之后两个条件语句中都有：

        if(this != rootPtr){
            //插入到尾部，修改根指针的bwd和fwd
            newNode -> bwd = this;
            this -> fwd = newNode;
        }else{
            //插入到空链表中
            newNode -> bwd = NULL;
            rootPtr -> fwd = newNode;
        }    

提取出来：

    if(this != rootPtr){
        //插入到尾部，修改根指针的bwd和fwd
        newNode -> bwd = this;
        this -> fwd = newNode;
    }else{
        //插入到空链表中
        newNode -> bwd = NULL;
        rootPtr -> fwd = newNode;
    }
    
    if(next != NULL){
        newNode -> fwd = next;
        next -> bwd = newNode;
        //插入到内部
    }else{
        //插入到尾部或者空表中
        newNode -> fwd = NULL;
        rootPtr -> bwd = newNode;
    }

　　下面的第二个else中的next是NULL，所以NULL可以转换一下，继续提取出来：

    newNode -> fwd = next;
    if(next != NULL){
        next -> bwd = newNode;
    }else{
        rootPtr -> bwd = newNode;
    }

    if(this != rootPtr){
        newNode -> bwd = this;
        this -> fwd = newNode;
    }else{
        newNode -> bwd = NULL;
        rootPtr -> fwd = newNode;
    }

提取出来，最终简化版：

#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0

//指针fwd指向前一个节点，bwd指向后一个节点
typedef struct NODE {
    struct NODE *fwd;
    struct NODE *bwd;
    int value;
} Node;

//插入value到双链表中，rootPtr为指向节点的指针
int doubleLinklistInsert(Node *rootPtr, int value)
{
    Node *this;
    Node *next;
    Node *newNode;

    for(this = rootPtr; (next = this -> fwd) != NULL; this = next){
        //如果节点值已经存在
        if(next	-> value == value){
            return FALSE;
        }
        //找到插入位置
        if(next -> value > value){
            break;
        }
    }

    //分配内存
    newNode = (Node *)malloc(sizeof(Node));
    if(newNode == NULL){
        return FALSE;
    }

    newNode -> value = value;

    /*插入节点一共四种情况
    1.插入到头部
    2.插入到尾部
    3.插入到中间
    4.插入到空链表中
    */
    //如果插入到头部部或者内部

    newNode -> fwd = next;
    if(next != NULL){
        next -> bwd = newNode;
    }else{
        rootPtr -> bwd = newNode;
    }

    if(this != rootPtr){
        newNode -> bwd = this;
        this -> fwd = newNode;
    }else{
        newNode -> bwd = NULL;
        rootPtr -> fwd = newNode;
    }

    return TRUE;
}

int main()
{
    Node third;
    Node second;
    Node first;

    third = (Node){NULL, &second, 4};
    second = (Node){&third, &first, 2};
    first = (Node){&second, NULL, 1};

    Node root = {&first, &third, -1};
    Node *rootPtr = &root;

    doubleLinklistInsert(rootPtr, 35);
    doubleLinklistInsert(rootPtr, -10);
    doubleLinklistInsert(rootPtr, 3);

    rootPtr = &root;
    while((rootPtr = rootPtr -> fwd) != NULL){
        printf("%d	", rootPtr -> value);
    }
    return 0;
}

　　运行：

通过提炼语句，消除if语句中的重复语句。