首页 > 代码库 > 线性表之双向链表
线性表之双向链表
一，双向链表的基础知识
1.双向链表的概念
双向链表是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。所以在双向链表的每个结点中都有两个指针域，一个指向其前驱结点，一个指向其后继结点。
2.双向链表实现的难点
- 每一个数据元素有两个指针域，一个指向其前驱结点，一个指向其后继结点。
- 第一个结点的前驱为NULL，最后一个节点的后继为NULL。
二，双向链表的实现
1.双向链表的基本功能(DoubleLinkList.h)
# ifndef DOUBLE_LINK_LIST# define DOUBLE_LINK_LIST/* 业务节点 */typedef void Node;/* 链表节点(被包含) */typedef struct DoubleNode{ struct DoubleNode * prev; struct DoubleNode * next;}DoubleNode;/* 双向链表 */typedef struct DoubleLinkList{ Node * ptr; DoubleNode header; DoubleNode slider; int length;}DoubleLinkList;/* 创建链表 */DoubleLinkList * createList();/* 清空链表 */void clear(DoubleLinkList * list);/* 销毁链表 */void destory(DoubleLinkList * list);/* 链表长度 */int length(DoubleLinkList * list);/* 链表是否为空 */int empty(DoubleLinkList * list);/* 插入链表 */void insert(DoubleLinkList * list, int pos, Node * node);/* 删除链表 */Node * del(DoubleLinkList * list, int pos);/* 删除某个元素 */Node * delNode(DoubleLinkList * list, Node * node);/* 获取链表 */Node * get(DoubleLinkList * list, int pos);/* 重置游标 */void resetSlider(DoubleLinkList * list);/* 游标下移 */Node * next(DoubleLinkList * list);/* 游标上移 */Node * prev(DoubleLinkList * list);/* 获取当前游标的结点 */Node * current(DoubleLinkList * list);# endif
2.双向链表基本功能的实现(DoubleLinkList.c)
# include<stdio.h># include<stdlib.h># include"DoubleLinkList.h"/* 创建链表 */DoubleLinkList * createList(){ DoubleLinkList * list = (DoubleLinkList *)malloc(sizeof(DoubleLinkList)); /* 初始化头指针 */ list->ptr = &(list->header); /* 初始化头结点 */ list->header.next = NULL; list->header.prev = NULL; /* 初始化游标 */ list->slider.next = NULL; /* 初始化链表长度 */ list->length = 0; return list;}/* 清空链表 */void clear(DoubleLinkList * list){ /* 置空头结点 */ list->header.next = NULL; list->header.prev = NULL; /* 置空游标 */ list->slider.next = NULL; /* 置空链表长度 */ list->length = 0;}/* 销毁链表 */void destory(DoubleLinkList * list){ if (list != NULL) { free(list); list = NULL; }}/* 链表长度 */int length(DoubleLinkList * list){ return list->length;}/* 链表是否为空 */int empty(DoubleLinkList * list){ if (list->length <= 0) { return 1; } else { return 0; }}/* 插入链表 */void insert(DoubleLinkList * list, int pos, Node * node){ if (list == NULL) { printf("链表为NULL\n"); return; } /* 判断插入位置合法性 */ pos = pos < 0 ? 0 : pos; pos = pos > length(list) ? length(list) : pos; /* 将业务结点转换为链表结点 */ DoubleNode * _node = (DoubleNode *)node; /* 判断是否是第一次插入 */ if (length(list) == 0) { list->header.next = _node; _node->prev = NULL; _node->next = NULL; list->length++; return; } /* 判断是否是插入头部 */ if (pos == 0) { list->header.next->prev = _node; _node->next = list->header.next; list->header.next = _node; _node->prev = NULL; } else { DoubleNode * posNode = list->header.next; DoubleNode * previous = posNode; for (int i = 0; i < pos; i++) { previous = posNode; posNode = posNode->next; } previous->next = _node; _node->prev = previous; posNode->prev = _node; _node->next = posNode; } list->length++;}/* 删除链表 */Node * del(DoubleLinkList * list, int pos){ if (list == NULL) { printf("链表为NULL\n"); return NULL; } if (length(list) == 0) { printf("链表长度为0,删除失败\n"); return NULL; } /* 判断删除位置合法性 */ pos = pos < 0 ? 0 : pos; pos = pos > length(list) ? length(list) : pos; /* 定义删除的返回结点 */ DoubleNode * result = NULL; /* 判断是否删除第一个 */ if (pos == 0) { result = list->header.next; list->header.next = list->header.next->next; list->header.next->prev = NULL; } else { DoubleNode * posNode = list->header.next; DoubleNode * previous = posNode; for (int i = 0; i < pos; i++) { previous = posNode; posNode = posNode->next; } result = posNode; previous->next = posNode->next; posNode->next->prev = previous; } list->length--; return result;}/* 删除某个元素 */Node * delNode(DoubleLinkList * list, Node * node){ /* 找出该元素位置 */ int pos = -1; /* 遍历寻找 */ for (int i = 0; i < length(list); i++) { Node * tmp = get(list, i); if (tmp == node) { pos = i; } } /* 如果未找到退出 */ if (pos == -1) { printf("未找到该元素\n"); return NULL; } /* 找到后删除 */ Node * result = del(list, pos); return result;}/* 获取链表 */Node * get(DoubleLinkList * list, int pos){ DoubleNode * posNode = list->header.next; for (int i = 0; i < pos; i++) { posNode = posNode->next; } return posNode;}/* 重置游标 */void resetSlider(DoubleLinkList * list){ list->slider.next = list->header.next;}/* 游标下移 */Node * next(DoubleLinkList * list){ if (list->slider.next->next != NULL) { DoubleNode * result = list->slider.next; list->slider.next = list->slider.next->next; return result; } return NULL;}/* 游标上移 */Node * prev(DoubleLinkList * list){ if (list->slider.next->prev != NULL) { DoubleNode * result = list->slider.next; list->slider.next = list->slider.next->prev; return result; } return NULL;}/* 获取当前游标的结点 */Node * current(DoubleLinkList * list){ return list->slider.next;}
3.双向链表的测试
# define _CRT_SECURE_NO_WARNINGS# include<stdio.h># include<string.h># include"DoubleLinkList.h"typedef struct Student{ DoubleNode next; char name[64]; int age;}Student;int main(){ Student s1; strcpy(s1.name, "刘备"); s1.age = 56; Student s2; strcpy(s2.name, "关羽"); s2.age = 40; Student s3; strcpy(s3.name, "张飞"); s3.age = 38; /* 创建双向链表 */ DoubleLinkList * list = createList(); /* 插入数据 */ insert(list, 0, &s1); insert(list, 0, &s2); insert(list, 0, &s3); /* 遍历 */ printf("##############基本遍历##############\n"); for (int i = 0; i < length(list); i++) { Student * stu = (Student *)get(list,i); printf("name = %s,age = %d\n", stu->name, stu->age); } /* 删除 */ del(list, 0); printf("##############删除0号位置后遍历##############\n"); for (int i = 0; i < length(list); i++) { Student * stu = (Student *)get(list, i); printf("name = %s,age = %d\n", stu->name, stu->age); } /* 删除节点 */ delNode(list,&s2); printf("##############删除s2后遍历##############\n"); for (int i = 0; i < length(list); i++) { Student * stu = (Student *)get(list, i); printf("name = %s,age = %d\n", stu->name, stu->age); } /* 重置游标 */ resetSlider(list); Student * ss1 = (Student *)current(list); printf("##############重置游标##############\n"); printf("name = %s,age = %d\n", ss1->name, ss1->age); /* 游标下移 */ next(list); Student * ss2 = (Student *)current(list); printf("##############游标下移##############\n"); printf("name = %s,age = %d\n", ss2->name, ss2->age); next(list); Student * ss3 = (Student *)current(list); printf("##############游标下移##############\n"); printf("name = %s,age = %d\n", ss3->name, ss3->age); /* 游标上移 */ prev(list); ss2 = (Student *)current(list); printf("##############游标上移##############\n"); printf("name = %s,age = %d\n", ss2->name, ss2->age);}
线性表之双向链表
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。