双循环链表的基本操作（不带头结点）
程序员文章站
2022-03-01 19:50:33
...
- Node.h
#ifndef NODE_H
#define NODE_H
#include <stdio.h>
#include <stdlib.h>
typedef struct NODE
{
int value;
struct NODE *prior, *next;
}Node, *DNode;
#endif- List.h
#ifndef LIST_H
#define LIST_H
#include "Node.h"
//初始化链表
void InitDouLinkList(DNode *pHead);
//头插建表
void InsertByHead(DNode *pHead, int value);
//尾插建表
void InsertByTail(DNode *pHead, int value);
//获取链表长度
int GetLength(DNode pHead);
//正向显示链表
void ShowDouLinkList(DNode pHead);
//反向显示链表
void ReverseShowLinkList(DNode pHead);
//头删
void DeleteByHead(DNode *pHead);
//尾删
void DeleteByTail(DNode *pHead);
//按值查找
DNode FindByValue(DNode pHead, int value);
//按索引查找
DNode FindByIndex(DNode pHead, int index);
void InsertByIndex(DNode *pHead, int index, int value);
//按索引删除
void DeleteByIndex(DNode* pHead, int index);
// 按索引修改
void UpdateByIndex(DNode pHead, int index, int value);
//按值修改
void UpdateByValue(DNode pHead, int oldval, int newval);
//按值删除
void DeleteByValue(DNode *pHead, int value);
//清空双链表(保留头结点）
void Clear(DNode* pHead);
#endif- List.c
#include "Node.h"
void InitDouLinkList(DNode *pHead)
{
*pHead = (DNode)malloc(sizeof(Node));
(*pHead)->prior = *pHead;
(*pHead)->next = *pHead;
}
void InsertByHead(DNode *pHead, int value)
{
DNode pNew = (DNode)malloc(sizeof(Node));
pNew->value = value;
if ((*pHead)->next == *pHead || (*pHead)->prior == *pHead)
{
(*pHead)->next = pNew;
(*pHead)->prior = pNew;
pNew->next = *pHead;
pNew->prior = *pHead;
}
else
{
(*pHead)->next->prior = pNew;
pNew->next = (*pHead)->next;
pNew->prior = (*pHead);
(*pHead)->next = pNew;
}
}
void InsertByTail(DNode *pHead, int value)
{
if ((*pHead)->next == *pHead || (*pHead)->prior == *pHead)
{
InsertByHead(pHead, value);
}
else
{
DNode pNew = (DNode)malloc(sizeof(Node));
pNew->value = value;
(*pHead)->prior->next = pNew;
pNew->prior = (*pHead)->prior;
pNew->next = *pHead;
(*pHead)->prior = pNew;
}
}
int GetLength(DNode pHead)
{
int count = 0;
DNode pos = pHead;
while (pos->next != pHead)
{
pos = pos->next;
count++;
}
return count;
}
void ShowDouLinkList(DNode pHead)
{
DNode pos = pHead;
while (pos->next != pHead)
{
pos = pos->next;
//pHead里面存的是第一个结点的地址,pHead->next->value是第一个数
printf("%d\t", pos->value);
}
}
void ReverseShowLinkList(DNode pHead)
{
DNode pos = pHead;
while (pos->prior != pHead)
{
pos = pos->prior;
printf("%d\t", pos->value);
}
}
void DeleteByHead(DNode *pHead)
{
if ((*pHead)->next != *pHead || (*pHead)->prior != *pHead)
{
DNode temp = (*pHead)->next;
(*pHead)->next = temp->next;
temp->next->prior = (*pHead);
free(temp);
temp = NULL;
}
}
void DeleteByTail(DNode *pHead)
{
if ((*pHead)->next != *pHead || (*pHead)->prior != *pHead)
{
DNode temp = (*pHead)->prior;
temp->prior->next = *pHead;
*pHead = temp->next;
free(temp);
temp = NULL;
}
}
DNode FindByValue(DNode pHead, int value)
{
DNode pos = pHead;
while (pos->value != value&&pos->next != pHead)
{
pos = pos->next;
}
return pos;
}
DNode FindByIndex(DNode pHead, int index)
{
DNode pos = pHead;
if (index >0 && index<GetLength(pHead))
{
for (int i = 0; i <= index; i++)
{
pos = pos->next;
}
}
return pos;
}
void InsertByIndex(DNode *pHead, int index, int value)
{
if (0 == index)
{
InsertByHead(pHead, value);
}
else if (index > 0 && index <= GetLength(*pHead))
{
DNode pos = *pHead;
for (int i = 0; i < index && pos->next != *pHead; i++)
{
pos = pos->next;
}
DNode pNew = (DNode)malloc(sizeof(Node));
pNew->value = value;
pNew->next = pos->next;
pos->prior = pNew;
pNew->prior = pos;
pos->next = pNew;
}
}
void DeleteByIndex(DNode* pHead, int index)
{
DNode pos = FindByIndex(*pHead, index);
if (pos != NULL)
{
if (pos->next != *pHead)
{
pos->prior->next = pos->next;
pos->next->prior = pos->prior;
free(pos);
pos = NULL;
}
else
{
pos->prior->next = pos->next;
pos->next->prior = pos->prior;
free(pos);
pos = NULL;
}
}
}
void UpdateByIndex(DNode pHead, int index, int value)
{
DNode pos = FindByIndex(pHead, index);
if (pos != NULL)
{
pos->value = value;
}
}
void UpdateByValue(DNode pHead, int oldval, int newval)
{
DNode pos = FindByValue(pHead, oldval);
while (pos != NULL&&pos->value == oldval)
{
pos->value = newval;
pos = FindByValue(pHead, oldval);
}
}
void DeleteByValue(DNode *pHead, int value)
{
DNode pos = FindByValue(*pHead, value);
while (pos != NULL&&pos->next != *pHead)
{
pos->prior->next = pos->next;
pos->next->prior = pos->prior;
free(pos);
pos = NULL;
pos = FindByValue(*pHead, value);
}
if (pos->next == *pHead && pos != NULL)
{
DeleteByTail(pHead);
}
}
void Clear(DNode* pHead)
{
while ((*pHead)->next != *pHead || (*pHead)->prior != *pHead)
{
DeleteByTail(pHead);
}
}
- main.c
#include "Node.h"
#include "List.h"
int main(void)
{
DNode pHead = NULL;
InitDouLinkList(&pHead);
//InsertByHead(&pHead, 1);
//InsertByHead(&pHead, 2);
// InsertByHead(&pHead, 3);
//InsertByHead(&pHead, 4);
InsertByTail(&pHead, 5);
InsertByTail(&pHead, 7);
InsertByTail(&pHead, 8);
InsertByTail(&pHead, 7);
InsertByTail(&pHead, 8);
//InsertByIndex(&pHead, 4, 55);
//UpdateByValue(pHead, 8, 88);
//DeleteByHead(&pHead);
//DeleteByTail(&pHead);
//UpdateByIndex(pHead, 4, 88);
//DeleteByIndex(&pHead, 4);
Clear(&pHead);
ShowDouLinkList(pHead);
//ReverseShowLinkList(pHead);
return 0;
}