数据结构学习笔记 双向链表

……接上文

6.  双向链表

6.1 特性

逻辑结构：线性结构

存储结构：链式结构

操作：增删改查

建立双向链表结构体：

	//双向链表的节点定义 	typedef int datatype;
	typedef struct node_t
	{
		datatype data;//数据域 
		struct node_t *next;//指向下一个节点的指针 next 先前的
		struct node_t *prior;//指向前一个节点的指针 prior 下一个
	}link_node_t,*link_node_p;	//将双向链表的头指针和尾指针封装到一个结构体里 
	//思想上有点像学的链式队列
	typedef struct doublelinklist
	{
		link_node_p head; //指向双向链表的头指针
		link_node_p tail; //指向双向链表的尾指针
		int len; //用来保存当前双向链表的长度
	}double_list_t,*double_list_p;

6.2 双向链表相关操作

需要注意的是，与单链表不同，双链表创建过程中，每创建一个新节点都要与其前驱节点建立两次联系，分别是：

(1)  将新节点的 prior 指针指向直接前驱节点。

(2)  将直接前驱节点的 next 指针指向新节点。

1)  创建空的双向链表

//1.创建一个空的双向链表
double_list_p createEmptyDoubleLinkList()
{// 1. 申请空间存放头尾指针结构体
    double_list_p p = (double_list_p)malloc(sizeof(double_list_t));if(NULL == p){perror("createEmptyDoubleLinkList");return NULL;}
    p->len = 0;//2.初始化，头尾指针分别指向开辟头节点，因为当前链表为空
    p->head = p->tail = (link_node_p)malloc(sizeof(link_node_t));if(p->head == NULL){perror("p->head malloc failed!");return NULL;}    p->head->next = NULL;
    p->head->prior = NULL;return p;
}

2)  指定位置插入

// 2.向双向链表的指定位置插入数据 post位置， data数据
int insertIntoDoubleLinkList(double_list_p p, int post, datatype data)
{
    link_node_p temp = NULL; // 用来临时保存head或者tail的位置if (post < 0 || post > p->len){perror("insertIntoDoubleLinkList err");return -1;}    link_node_p pnew = (link_node_p)malloc(sizeof(link_node_t));if (pnew == NULL){perror("pnew malloc err");return -1;}// 初始化新节点
    pnew->data = data;
    pnew->prior = NULL;
    pnew->next = NULL;// 插入链表的尾巴if (post == p->len){
        p->tail->next = pnew;
        pnew->prior = p->tail;
        p->tail = pnew; // 移动尾指针}// 中间差else{if (post < p->len / 2) // 前半段{// temp移动到插入位置
            temp = p->head;for (int i = 0; i <= post; i++)
                temp = temp->next;}else // 后半段{
            temp = p->tail;for (int i = p->len - 1; i > post; i--)
                temp = temp->prior;}// 2) 进行插入操作(先连前面，再练后面)
        pnew->prior = temp->prior;
        temp->prior->next = pnew;
        pnew->next = temp;
        temp->prior = pnew;}
    p->len++;  // 插入完成，链表长度+1return 0;
}

3)  双向链表遍历

// 3.遍历双向链表
void showDoubleLinkList(double_list_p p)
{
    link_node_p temp = NULL;printf("正向遍历\n");
    temp = p->head;while (temp->next != NULL){
        temp = temp->next;printf("%d ", temp->data);}printf("\n");printf("反向遍历\n");
    temp = p->tail;while (temp != p->head){printf("%d ", temp->data);
        temp = temp->prior;}printf("\n----------------\n");
}

4)  判断双向链表是否为空

//4.判断双向链表是否为空
int isEmptyDoubleLinkList(double_list_p p)
{return p->len == 0;
}

5)  删除双向链表指定位置

//5.删除双向链表指定位置数据
int deletePostDoubleLinkList(double_list_p p,int post)
{
    link_node_p temp = NULL;// 1. 容错判断if(isEmptyDoubleLinkList(p) || post >= p->len || post < 0){error("deletePostDoubleLinkList err\n");return -1;}//2.对删除位置进行分析，分为两种情况if(post == p->len-1) // //删除的是链表最后一个节点{// 1)将尾指针向前移动一个位置
        p->tail = p->tail->prior;// 2)释放被删除节点，也就是最后一个节点free(p->tail->next);// 3)将最后一个节点与链表断开
        p->tail->next = NULL;}else    // 中间删除{if(post < p->len/2)  // 说明在前半段{
            temp = p->head;for (int i = 0; i <= post; i++)
                temp = temp->next;}else    // 说明在后半段{
            temp = p->tail;for (int i = p->len-1; i > post; i--){
                temp = temp->prior;}}// 进行删除操作
        temp->prior->next = temp->next;
        temp->next->prior = temp->prior;free(temp);
        temp = NULL;}// 3. 双向链表的长度-1
    p->len--;return 0;
}

6)  求双向链表的长度

//6.求双向链表的长度
int lengthDoubleLinkList(double_list_p p)
{return p->len;
}

7)  查找指定数据出现的位置

//7.查找指定数据出现的位置 data被查找的数据
int searchPostDoubleLinkList(double_list_p p,datatype data)
{
    link_node_p temp = p->head;int post =0;  // 保存位置while(temp->next != NULL){
        temp = temp->next;if(temp->data == data){return post;}
        post++;}return -1;
}

8)  修改指定位置的数据

//8.修改指定位置的数据,post修改的位置 data被修改的数据
int changeDataDoubleLinkList(double_list_p p,int post, datatype data)
{if(isEmptyDoubleLinkList(p) || post >= p->len || post < 0){perror("changeDataDoubleLinkList err");return -1;}
    link_node_p temp = NULL;if(post < p->len/2) // 说明在前半段{
        temp = p->head;for (int i = 0; i <= post; i++)
            temp = temp->next;}else{
        temp = p->tail;for (int i = p->len-1; i > post; i--)
            temp = temp->prior;}
    temp->data = data;return 0;
}

9)  删除双向链表中指定数据

// 9.删除双向链表中的指定数据 data代表删除所有出现的data数据
/*
    思想：从头节点后节点开始用指针h遍历，相当于遍历无头链表，遇到需要删除节点的就用h指向它然后删除，如果不需要删除则h继续往后走一个。这里因为是双向链表可以找到前驱，所以不需要每次指向被删除节点的前一个然后跨过了。
*/
void deleteDataDoubleLinkList(double_list_p p, datatype data)
{
    link_node_p h = p->head->next;
    link_node_p pdel = NULL;while (h != NULL) // 遍历双向链表(相当于遍历无头单向链表){if (h->data == data) // 相等{if (h == p->tail)  // 尾节点{
                p->tail = p->tail->prior;free(p->tail->next);
                p->tail->next = NULL;
                h = NULL;}else // 中间节点{
                h->prior->next = h->next;
                h->next->prior = h->prior;
                pdel = h;
                h = h->next;free(pdel);
                pdel = NULL;}
            p->len--;}else{
            h = h->next;}}
}

main函数代码：

int main(int argc, char const *argv[])
{// int i;
    double_list_p p = createEmptyDoubleLinkList();for (int i = 0; i < 5; i++){insertIntoDoubleLinkList(p, i, i);}showDoubleLinkList(p);deletePostDoubleLinkList(p, 2);printf("len is %d\n", lengthDoubleLinkList(p));showDoubleLinkList(p);deletePostDoubleLinkList(p, 3);showDoubleLinkList(p);printf("1 post is: %d\n", searchPostDoubleLinkList(p, 1));int len = lengthDoubleLinkList(p);for (int i = 0; i < len; i++){deletePostDoubleLinkList(p, 0);}printf("len is %d\n", lengthDoubleLinkList(p));showDoubleLinkList(p);printf("is Empty? %d\n", isEmptyDoubleLinkList(p));free(p);
    p = NULL;return 0;
}

                                                                                                                                 未完待续……