结构体和指针

链表

包含数据的独立数据结构的集合，通过链表和指针连接在一起，节点通常是动态分配的，也有数组组成的，但是通过指针遍历

单链表

每个节点包含有指向下一个节点的指针，最后一个指向NULL

只要找到了第一个节点就可以访问后面的节点，可以用一个指针保存第一个指针的地址

typedef struct NODE{
    struct NODE *link;
    int value;
}Node;

在单列表之中插入

遍历的时候保存上一个节点的地址

把之前的指针改为插入的值，把插入的指针改为下一个节点的地址

问题：

• 注意末尾数据的判断

• 注意第一个数据的插入，要更改root指针，需要传入一个指向root的指针，实际上为结构体的二重指针

改进：只需要记录每次的节点指向下一节点的指针的地址就足够了

  1 #include <stdio.h>                                                                    
  2 #include <stdlib.h>
  3 typedef struct NODE{
  4     struct NODE *link;
  5     int value;
  6 }Node;
  7 
  8 #define FALSE  0
  9 #define TRUE   1
 10 //参数：指向保存第一个结构体位置的指针的指针，要插入的值
 11 int sile_insert(Node **linkp, int new_value)
 12 {
 13     Node *current;//用来保存现在的结构体的指针
 14     Node *new;//用来保存下一个数组的位置
 15     while((current = *linkp) != NULL &&
 16         current->value < new_value)//在要插入地址之后位置出来
 17         linkp = &current->link;//指向对应的指针的地址，这是插入前位置
 18 
 19     new = (Node *)malloc(sizeof(Node));
 20     if(new == NULL)
 21         return FALSE;
 22     new->value = new_value;
 23 
 24     new->link = current;
 25     *link  = new;                                                                     
 26     return TRUE;
 27 }

双链表

每个节点包括两个指针，指向前一个字节，指向后一个字节的指针

typedef struct NODE{
    struct NODE *fwd;
    struct NODE *bwd;
    int value;
}Node;

• 根节点：fwd指向以一个节点，bwd指向最后一个节点

• 第一个节点的bwd=NULL

• 最后一个节点的fwd = NULL

在双链表中插入

有四种可能

• 起始位置
• 结束位置
• 中间位置
• 起始和结束

#include <stdlib.h>
#include <stdio.h>
typedef struct NODE{
    struct NODE *fwd;
    struct NODE *bwd;
    int value;
}Node;
int dll_insert(Node *rootp, int value)
{
    Node *this;
    Node *next;
    Node *newnode;
    
    for(this = rootp; (next = this->fwd) != NULL; this = 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)
    {
        newnode->fwd = next;
        if(this != rootp){//位于中间位置
        	this->fwd = nownode;
        	newnode->bwd = this;
        }
        else{//位于起始位置，并且不是结尾
        	rootp->fwd = nownode;
        	newnode->bwd = NULL;
        }
        next->bwd = newnode;
    }
    else
    {
        newnode->fwd = NULL;
        if(this != rootp){//位于末尾位置，不是起始
        	this->fwd = nownode;
        	newnode->bwd = this;
        }else
        {//位于起始和末尾
        	this->fwd = nownode;
        	newnode->bwd = NULL;
        }
        rootp->bwd = newnode;
    }
	return 1;
}

代码简化：

• 把if语句之中的重复代码提取出来 **注：**提取出的代码不会影响判断代码的进行

• 对现有的代码进行总结

newnode->fwd = next;
if(this != rootp)
{
	this->fwd = newnode;
    newnode->bwd = this;
}
else{
    root->fwd = newnode;
    newnode->bwd = NULL;
}
if(next != NALL)
    next->bwd = newnode;
else
    rootp->bwd = newnode;

写法化简

newnode->fwd = next;
this->fwd = newnode;
newnode->bwd = this != rootp ? this :NULL;
(next != NULL ? next : rootp) ->bwd = newnode;