【数据结构】双向链表
发布时间:2020-12-15 06:31:07 所属栏目:安全 来源:网络整理
导读:双向链表较单向链表有更好的灵活性,具备前后指针,可以更方便的对链表进行操作,但程序设计也更复杂,需要同时考虑前后指针。这里同样对照单链表的基础操作,讨论 链表的创建、尾端添加元素、指定位置插入元素、删除指定单个元素节点、删除指定元素所有节点
双向链表较单向链表有更好的灵活性,具备前后指针,可以更方便的对链表进行操作,但程序设计也更复杂,需要同时考虑前后指针。这里同样对照单链表的基础操作,讨论链表的创建、尾端添加元素、指定位置插入元素、删除指定单个元素节点、删除指定元素所有节点、删除指定位置节点等基础操作。 1、双向链表的数据结构 typedef struct _Node { int value; struct _Node *prev; struct _Node *next; }Node;2、创建一个双向非循环链表 void createDoubleList(Node **ppDoubleList,int val) { Node *pDoubleList = NULL; pDoubleList = (Node *)malloc(sizeof(Node)); assert(NULL != pDoubleList); memset(pDoubleList,NULL,sizeof(Node)); pDoubleList->value = val; *ppDoubleList = pDoubleList; return; }3、链表尾端添加元素 异常情况:链表不存在 void addToTail(Node **ppDoubleList,int val) { Node *pNew = (Node *)malloc(sizeof(Node)); memset(pNew,sizeof(Node)); pNew->value = val; if (NULL == ppDoubleList) return; if (NULL == *ppDoubleList) { *ppDoubleList = pNew; return; } else { Node *pNode = *ppDoubleList; while (NULL != pNode->next) pNode = pNode->next; pNode->next = pNew; pNew->prev = pNode; return; } }4、指定位置插入元素 异常情况: 1) 链表为空 2) 插入位置为0 3) 插入位置大于链表长度 void insertNode(Node **ppDoubleList,int pos,int val) { if ((NULL == ppDoubleList) || (pos < 0)) return; if (NULL == *ppDoubleList) //链表为空,直接创建新链表 createDoubleList(ppDoubleList,val); Node *pNode,*pNew; pNode = *ppDoubleList; pNew = (Node *)malloc(sizeof(Node)); memset(pNew,sizeof(Node)); pNew->value = val; if (0 == pos) //插入链表首位置 { pNode->prev = pNew; pNew->next = pNode; *ppDoubleList = pNew; return; } while (--pos) { pNode = pNode->next; if (NULL == pNode) //插入位置大于链表长度 return; } pNew->next = pNode->next; pNode->next->prev = pNew; pNode->next = pNew; pNew->prev = pNode; return; }5、删除单个指定元素节点 异常情况: 1) 链表为空 2) 待删除元素为头结点元素 3) 链表仅一个节点,恰好为指定元素节点 4) 待删除节点是尾节点 5) 元素不存在链表中 /*删除单个指定元素节点*/ void deleteValue(Node **ppDoubleList,int value) { Node *pNode = *ppDoubleList; if ((NULL == ppDoubleList) || (NULL == *ppDoubleList)) return; /*删除元素在头节点*/ if (value == pNode->value) { *ppDoubleList = pNode->next; if (*ppDoubleList) //链表仅一个节点 (*ppDoubleList)->prev = NULL; } else { /*查找指定待删除元素节点*/ while (pNode->value != value) { pNode = pNode->next; if (NULL == pNode) //元素不存在 return; } if (pNode->next) //待删除元素是非尾节点 { pNode->prev->next = pNode->next; pNode->next->prev = pNode->prev; } else { //待删除元素为尾节点 pNode->prev->next = pNode->next; } } free(pNode); pNode = NULL; return; }6、删除所有指定元素 异常情况同删除节点 /*删除所有指定元素节点*/ void deleteAllValue(Node **ppDoubleList,int value) { Node *pNode = *ppDoubleList; if ((NULL == ppDoubleList) || (NULL == *ppDoubleList)) return; /*删除元素在头节点*/ if (value == pNode->value) { *ppDoubleList = pNode->next; if (*ppDoubleList) (*ppDoubleList)->prev = NULL; } else { /*查找指定待删除元素节点*/ while (pNode->value != value) { pNode = pNode->next; if (NULL == pNode) //元素不存在 return; } if (pNode->next) //待删除元素是非尾节点 { pNode->prev->next = pNode->next; pNode->next->prev = pNode->prev; } else { //待删除元素为尾节点 pNode->prev->next = pNode->next; } } free(pNode); pNode = NULL; return deleteAllValue(ppDoubleList,value); } 7、删除指定位置的节点 异常情况: 1) 链表不存在 2) 删除位置为头结点位置 3) 删除节点位置大于链表长度 4) 删除节点为尾节点 void deleteNode(Node **ppDoubleList,int pos) { Node *pNode = *ppDoubleList; //pNode为待删除节点 if ((NULL == ppDoubleList) || (NULL == *ppDoubleList) || (pos < 0)) return; /*删除首节点情况*/ if (0 == pos) { *ppDoubleList = pNode->next; (*ppDoubleList)->prev = NULL; } else { /*找到待删除节点*/ while (pos--) { pNode = pNode->next; if (NULL == pNode) //位置大于长度返回 return; } pNode->prev->next = pNode->next; if (pNode->next) //如果删除节点不是最后一个节点 pNode->next->prev = pNode->prev; } free(pNode); pNode = NULL; return; }至于打印链表以及统计链表节点个数和前面的单链表是一样的,这里就不赘述了 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |
相关内容