Permalink
Find file Copy path
e39cecc Nov 18, 2018
1 contributor

Users who have contributed to this file

272 lines (237 sloc) 6.23 KB
/**
* @ProjectName:DoubleLinkedList 双向链表算法实现
* @Author: MagicDevil.Top (MagicDevil.Zhang@gmail.com)
* @Description: 实现功能:初始化双向链表、添加元素、插入元素、更新元素、删除元素、清空表、查找元素数量、获取指定索引的元素内容、查询指定索引前驱元素、查询指定索引后继元素、查找元素所在的索引位置、导出指针数组、打印所有元素
*/
#include <stdio.h>
#include <windows.h>
#define SUCCESS 1
#define ERROR -1
#define ElemType int
#define StatusType int
//自定义单链表类型
typedef struct DuLNode
{
ElemType data; //单链表存储
struct DuLNode *prior, *next; //前、后链表节点的指针
} DuLNode, *DoubleLinkedList;
//1.初始化单链表
StatusType InitDoubleLinkedList(DoubleLinkedList &L)
{
L = (DoubleLinkedList)malloc(sizeof(DuLNode));
L->data = NULL;
L->prior = NULL;
L->next = NULL;
return SUCCESS;
}
//2.添加元素
StatusType AddDoubleLinkedList(DoubleLinkedList &L, ElemType content)
{
if (!L->data)
{ //空节点自动覆盖
L->data = content;
return SUCCESS;
}
if (L->next)
{
return AddDoubleLinkedList(L->next, content); //递归到最后一个链表元素
}
else
{
//新建一个新节点
DoubleLinkedList temp;
InitDoubleLinkedList(temp);
temp->data = content;
//将新节点连接到最后节点位置
temp->prior = L;
temp->next = NULL;
L->next = temp;
return SUCCESS;
}
return ERROR;
}
//3.插入元素
StatusType InsertDoubleLinkedList(DoubleLinkedList &L, ElemType content, int index)
{
if (!L->next && index != 0)
{ //递归抵达最后元素,但仍未到指定元素,返回ERROR
return ERROR;
}
if (index == 0)
{
DoubleLinkedList temp;
InitDoubleLinkedList(temp);
//将需要插入的元素与被插入的元素内容交换并连接,以实现前后位置的伪交换
temp->data = L->data;
L->data = content;
temp->next = L->next;
temp->prior = L;
L->next = temp;
return SUCCESS;
}
else
{
return InsertDoubleLinkedList(L->next, content, index - 1); //递归到指定索引的元素
}
return ERROR;
}
//4.更新元素
StatusType UpdateDoubleLinkedList(DoubleLinkedList &L, int index, ElemType content)
{
if (index)
{
UpdateDoubleLinkedList(L->next, index - 1, content); //递归到指定索引的元素
}
if (L && index == 0)
{ //到达指定元素且该链表不为空
L->data = content;
return SUCCESS;
}
return ERROR;
}
//5.删除元素
StatusType DeleteDoubleLinkedList(DoubleLinkedList &L, int index)
{
if (index == 0)
{ //头结点删除
DoubleLinkedList g;
g = L;
L = L->next;
L->prior = NULL;
free(g);
return SUCCESS;
}
if (index != 1)
{ //定位到要删除的指定位置前的元素
DeleteDoubleLinkedList(L->next, index - 1);
}
if (L->next && index == 1)
{
DoubleLinkedList g = L->next; //标记垃圾内存
L->next = g->next; //跨连接后面的元素
g->next->prior = L;
free(g);
return SUCCESS;
}
return ERROR;
}
//6.清空表
StatusType ClearDoubleLinkedList(DoubleLinkedList &L)
{
if (L->next)
{
ClearDoubleLinkedList(L->next); //遍历所有元素
}
free(L->next); //清空尾巴保留头结点
L->data = NULL;
L->next = NULL;
return SUCCESS;
}
//7.查找元素数量
StatusType getDoubleLinkedListNum(DoubleLinkedList &L)
{
if (L)
{
return 1 + getDoubleLinkedListNum(L->next);
}
}
//8.获取指定索引的元素内容
ElemType getDoubleLinkedList(DoubleLinkedList &L, int index)
{
if (!L->next && index != 0)
{ //抵达最后元素时还未到指定元素
return ERROR;
}
if (index == 0)
{
return L->data;
}
else
{
return getDoubleLinkedList(L->next, --index);
}
return ERROR;
}
//9.获取指定索引的前驱元素内容
ElemType getPriorDoubleLinkedList(DoubleLinkedList &L, int index)
{
return L->prior->data;
}
//10.获取指定索引的后继元素内容
ElemType getNextDoubleLinkedList(DoubleLinkedList &L, int index)
{
return L->next->data;
}
//11.查找元素所在的索引位置
int indexOfDoubleLinkedList(DoubleLinkedList &L, ElemType content)
{
if (!L->next && L->data != content)
{ //递归到最后元素时仍未到找到要查找的元素,返回ERROR
return ERROR;
}
if (L->data == content)
{
return 0; //当到达要查找的元素时,返回0以结束递归
}
else
{
int x = indexOfDoubleLinkedList(L->next, content); //检测后一个递归是否是未查找到(ERROR)
return (x != ERROR ? 1 + x : ERROR); //三目运算,若后一个递归元素未查找到,告诉先一个递归元素未查找到(返回ERROR),以此循环,直到首个函数返回ERROR
}
return ERROR;
}
//12.导出指针数组
ElemType *toArrayDoubleLinkedList(DoubleLinkedList &L)
{
StatusType getLinkedListNum(DoubleLinkedList & L);
DoubleLinkedList s;
s = L;
ElemType *x;
x = (ElemType *)malloc(sizeof(ElemType) * getDoubleLinkedListNum(L));
for (int i = 0; s != NULL; i++)
{
*(x + i) = s->data;
s = s->next;
}
return x;
}
//13.打印所以元素
StatusType PrintDoubleLinkedList(DoubleLinkedList &L)
{
int foot = 0;
int flag = 0;
int num = 0;
DoubleLinkedList s;
s = L;
printf("List Information\n");
while (flag == 0)
{
if (s->next == NULL)
{ //当遍历到最后一个元素时退出
flag = 1;
}
num++;
printf(" |- List %d : %d\n", foot++, s->data);
s = s->next;
}
printf("Num : %d\n", num);
return SUCCESS;
}
int main(int argc, char const *argv[])
{
DoubleLinkedList p;
InitDoubleLinkedList(p);
AddDoubleLinkedList(p, 1);
AddDoubleLinkedList(p, 3);
AddDoubleLinkedList(p, 5);
AddDoubleLinkedList(p, 7);
InsertDoubleLinkedList(p, 10, 2);
UpdateDoubleLinkedList(p, 1, 5);
DeleteDoubleLinkedList(p, 1);
//ClearDoubleLinkedList(p);
PrintDoubleLinkedList(p);
printf("%d\n", getDoubleLinkedListNum(p));
printf("%d\n", indexOfDoubleLinkedList(p, 1));
system("pause");
return 0;
}