0724 双向链表

Part 1.双向链表的完成以下要求

1.双向链表的节点创建

双向链表相较于单向链表，函数的指针域多了一个指向前面的prev指针，每个节点的next指向上一个节点，prev指向下一个节点。创建一个结构体嵌套联合体，联合体储存普通节点的data，头节点的len。双向链表的头节点的prev指向NULL，尾节点的next指向NULL。在初始化的时候，直接将新节点的prev和next全指向NULL。

typedef struct Node
{union{int len;datatype data;};struct Node *next;struct Node *prev;
}*doublelinklist;doublelinklist create_node(int flag)
{doublelinklist s = (doublelinklist)malloc(sizeof(struct Node));if(s == NULL){return NULL;}if(flag == 1)s->len = 0;else if(flag == 0)s->data = 0;s->next = s->prev = NULL;return s;
}

2.双向链表的头插

双向链表的头插，需要创建一个新节点将值赋到新节点里，然后让head的next指向新节点，新节点的next指向head->next，新节点的prev指向head，head->next的prev指向新节点，如果新节点是第一个节点，则不需要进行head->next的prev指向新节点操作，因为head->next是NULL，NULL没有prev，不然会报段错误。

int head_insert(doublelinklist head,datatype element)
{if(head == NULL)return Faulse;doublelinklist p = create_node(0);	if(p == NULL)return Faulse;p->data = element;p->next = head->next;p->prev = head;if(head->next != NULL)head->next->prev = p;head->next = p;head->len++;return Sccuess;
}

3.双向链表的遍历

while循环当p没到NULL（链表没到尾的时候），循环输出data，并且下移p = p->next

int output(doublelinklist head)
{	if(head == NULL || head->len == 0)return Faulse;doublelinklist p = head->next;while(p != NULL){printf("%d\t",p->data);p = p->next;}printf("\n");return Sccuess;
}

4.双向链表的尾插

遍历循环找到链表的尾节点，将新节点的prev指向尾节点，尾节点的next指向新节点即可。新节点在申请的时候的next就指向NULL，所以不需要改指向，而尾节点的next为NULL，没有prev，也不需要指向。

int rear_insert(doublelinklist head,datatype element)
{if(head == NULL)return Faulse;doublelinklist p = head;while(p->next != NULL)p = p->next;doublelinklist s = create_node(0);	if(s == NULL)return Faulse;s->data = element;s->prev = p;p->next = s;head->len++;return Sccuess;
}

5.双向链表的头删

定义一个del指针指向首普通节点，将头节点的next指向del->next，判断这个第二个节点是不是NULL，如果是则不需要将del->next->prev指向head，如果不是则需要。

int head_delete(doublelinklist head)
{if(head == NULL || head->len == 0)return Faulse;doublelinklist p = head;doublelinklist del = p->next;p->next = del->next;if(del->next != NULL)del->next->prev = p;free(del);del = NULL;return Sccuess;
}

6.双向链表的尾删

循环找到要删除的节点p，定义一个del指向要删除的节点，p->prev->next指向p->next，释放del就行。

int rear_delete(doublelinklist head)
{	if(head == NULL || head->len == 0)return Faulse;doublelinklist p = head;while(p->next != NULL)p = p->next;doublelinklist del = p;p->prev->next = p->next;free(del);del = NULL;
}

7.双向链表的按位置查找

循环需要的位置次数，每次p下移，找到需要的位置，输出data就行

int position_search(doublelinklist head,int position)
{if(head == NULL || head->len == 0 || position > head->len || position < 1)return Faulse;doublelinklist p = head;for(int i = 0; i < position; i++){p = p->next;}printf("%d\n",p->data);return Sccuess;
}

8.双向链表的按位置删除

找到需要删除的位置的前一个位置p，将del定义为要删除的位置，p的next指向del的next，并判断del是不是最后一位，如果是NULL不需要prev，如果不是，del的next的prev需要指向p。

int position_delete(doublelinklist head,int position)
{if(head == NULL || head->len == 0 || position > head->len || position < 1)return Faulse;doublelinklist p = head;for(int i = 0; i < position-1; i++){p = p->next;}doublelinklist del = p->next;p->next = del->next;if(del->next != NULL)del->next->prev = p;free(del);del = NULL;return Sccuess;
}

9.双向链表的按位置修改

循环找位置p，找到位置修改p->data即可

int position_change(doublelinklist head,int position,datatype element)
{if(head == NULL || head->len == 0 || position > head->len || position < 1)return Faulse;doublelinklist p = head;for(int i = 0; i < position; i++){p = p->next;}p->data = element;return Sccuess;
}

10.双向链表的按位置插入

循环找到要插入的前一个位置p，申请一个新节点s，给s的data赋值，s要插入到p的后面，s的next指向p的next，s的prev指向p，p的next指向s的next，判断要插入的位置是不是在最后一位，如果是则不需要NULL的prev，不是则需要s的下一位的prev指向s。

int position_insert(doublelinklist head,int position,datatype element)
{if(head == NULL || head->len == 0 || position > head->len+1 || position < 1)return Faulse;doublelinklist p = head;for(int i = 0; i < position-1; i++){p = p->next;}doublelinklist s = create_node(0);	if(s == NULL)return Faulse;s->data = element;s->next = p->next;s->prev = p;p->next = s;if(p->next != NULL)p->next->prev = s;return Sccuess;
}