C|双向链表——设计与实现
【C|双向链表——设计与实现】1.双向链表可以完成普通链表的所有操作，并且解决了普通链表逆向遍历效率低的问题。
双向链表相对于普通链表没有多大提示，需要注意的就是插入删除操作时的异常处理，
插入删除0号节点的异常，第一次插入的异常，最后一次删除的异常。
直接代码
#ifndef __DLINKLIST_H__
#define __DLINKLIST_H__typedef void DLinkList;
typedef struct DLinkListNode{
struct DLinkListNode *next;
struct DLinkListNode *pre;
}DLinkListNode;
DLinkList* DLinkList_Create();
void DLinkList_Destory(DLinkList *list);
int DLinkList_Length(DLinkList *list);
void DLinkList_Clear(DLinkList *list);
DLinkListNode* DLinkList_Get(DLinkList *list, int pos);
int DLinkList_Insert(DLinkList *list, DLinkListNode *node, int pos);
DLinkListNode* DLinkList_Delete(DLinkList *list, int pos);
//new
DLinkListNode* DLinkList_DeleteNode(DLinkList *list, DLinkListNode *node);
DLinkListNode* DLinkList_Reset(DLinkList *list);
DLinkListNode* DLinkList_Current(DLinkList *list);
DLinkListNode* DLinkList_Next(DLinkList *list);
DLinkListNode* DLinkList_Pre(DLinkList *list);
#endif#include
#include
#include
#include "DLinkList.h"typedef struct _tag_DLinkList{
DLinkListNode header;
int length;
DLinkListNode *slider;
}TDLinkList;
DLinkList* DLinkList_Create()
{
TDLinkList *tlist;
tlist = (TDLinkList *)malloc(sizeof(TDLinkList));
if(NULL == tlist)
{
printf("DLinkList_Create err NULL == tlist)\n");
return NULL;
}
memset(tlist, 0, sizeof(TDLinkList));
return tlist;
}
void DLinkList_Destory(DLinkList *list)
{
TDLinkList *tlist;
if(NULL == list)
{
printf("DLinkList_Destory err (NULL == list)\n");
return ;
}
tlist = (TDLinkList *)list;
free(tlist);
tlist = NULL;
return ;
}
int DLinkList_Length(DLinkList *list)
{
TDLinkList *tlist;
if(NULL == list)
{
printf("DLinkList_Length err (NULL == list)\n");
return -1;
}
tlist = (TDLinkList *)list;
return tlist->length;
}
void DLinkList_Clear(DLinkList *list)
{
TDLinkList *tlist;
if(NULL == list)
{
printf("DLinkList_Length err (NULL == list)\n");
return ;
}
tlist = (TDLinkList *)list;
memset(tlist, 0, sizeof(TDLinkList));
return ;
}
DLinkListNode* DLinkList_Get(DLinkList *list, int pos)
{
TDLinkList *tlist;
int i;
DLinkListNode *current;
if(NULL == list || pos < 0)
{
printf("DLinkList_Get err (NULL == list || pos < 0)\n");
return NULL;
}
tlist = (TDLinkList *)list;
if(pos >= tlist->length)
{
printf("DLinkList_Get err (tlist->length >= pos)\n");
return NULL;
}
current = (DLinkListNode *)tlist;
for(i = 0;
i < pos;
i++)
current = current->next;
return current->next;
}
int DLinkList_Insert(DLinkList *list, DLinkListNode *node, int pos)
{
TDLinkList *tlist;
int i;
DLinkListNode *current, *next;
if(NULL == list || NULL == node || pos < 0)
{
printf("DLinkList_Insert err (NULL == list || NULL == node || pos < 0)\n");
return -1;
}
tlist = (TDLinkList *)list;
if(pos > tlist->length)
pos = tlist->length;
current = (DLinkListNode *)tlist;
for(i = 0;
i< pos;
i++)
current = current->next;
next = current->next;
node->next = next;
current->next = node;
if(next != NULL)
{
next->pre = node;
tlist->slider = node;
}
node->pre = current;
if(current == (DLinkListNode *)tlist)
node->pre = NULL;
tlist->length++;
return 0;
}
DLinkListNode* DLinkList_Delete(DLinkList *list, int pos)
{
TDLinkList *tlist;
int i;
DLinkListNode *current, *next, *ret;
if(NULL == list || pos < 0)
{
printf("DLinkList_Delete err (NULL == list || pos < 0)\n");
return NULL;
}
tlist = (TDLinkList *)list;
if(pos >= tlist->length)
pos = tlist->length-1;
current = (DLinkListNode *)tlist;
for(i = 0;
i< pos;
i++)
current = current->next;
ret = current->next;
next = ret->next;
current->next = next;
if(next != NULL)
{
next->pre = current;
if(current == (DLinkListNode *)tlist)
next->pre = NULL;
}
tlist->length--;
if(tlist->slider == ret)
tlist->slider = ret->next;
return ret;
}DLinkListNode* DLinkList_DeleteNode(DLinkList *list, DLinkListNode *node)
{
TDLinkList *tlist;
int i;
DLinkListNode *current;
if(NULL == list || NULL == node)
{
printf("DLinkList_DeleteNode err ((NULL == list || NULL == node)\n");
return NULL;
}
tlist = (TDLinkList *)list;
current = (DLinkListNode *)tlist;
for(i = 0;
i < tlist->length;
i++)
{
current = current->next;
if(node == current)
{
DLinkList_Delete(list, i);
return current;
}
} return NULL;
}DLinkListNode* DLinkList_Reset(DLinkList *list)
{
TDLinkList *tlist;
if(NULL == list)
{
printf("DLinkList_Reset err ((NULL == list)\n");
return NULL;
}
tlist = (TDLinkList *)list;
tlist->slider = tlist->header.next;
return tlist->slider;
}DLinkListNode* DLinkList_Current(DLinkList *list)
{
TDLinkList *tlist;
if(NULL == list)
{
printf("DLinkList_Current err (NULL == list)\n");
return NULL;
}
tlist = (TDLinkList *)list;
return tlist->slider;
}DLinkListNode* DLinkList_Next(DLinkList *list)
{
TDLinkList *tlist;
if(NULL == list)
{
printf("DLinkList_Next err (NULL == list)\n");
return NULL;
}
tlist = (TDLinkList *)list;
if(tlist->slider != NULL)
tlist->slider = tlist->slider->next;
return tlist->slider;
}DLinkListNode* DLinkList_Pre(DLinkList *list)
{
TDLinkList *tlist;
if(NULL == list)
{
printf("DLinkList_Pre err (NULL == list)\n");
return NULL;
}
tlist = (TDLinkList *)list;
if(tlist->slider != NULL)
tlist->slider = tlist->slider->pre;
return tlist->slider;
}
#include
#include
#include
#include "DLinkList.h"typedef struct _Teacher
{
DLinkListNode node;
int age;
char name[64];
}Teacher;
typedef struct _Teacher2
{
DLinkListNode node;
int age;
char name[64];
}Teacher2;
typedef struct _Teacher3
{
DLinkListNode node;
int age;
char name[64];
int age3;
}Teacher3;
void main()
{
intret = 0, i = 0;
DLinkList* list = NULL;
Teacher *tmp;
Teacher t1, t2, t3, t4,t5;
t1.age = 31;
t2.age = 32;
t3.age = 33;
t4.age = 34;
t5.age = 35;
list = DLinkList_Create();
if(NULL == list)
{
return;
}
DLinkList_Insert(list, (DLinkListNode *)&t1, 0);
DLinkList_Insert(list, (DLinkListNode *)&t2, 0);
DLinkList_Insert(list, (DLinkListNode *)&t3, 0);
DLinkList_Insert(list, (DLinkListNode *)&t4, 0);
DLinkList_Insert(list, (DLinkListNode *)&t5, 0);
do{
tmp = (Teacher *)DLinkList_Current(list);
if(tmp != NULL)
{
printf("tmp->age = %d ",tmp->age);
DLinkList_Next(list);
}
}while(tmp);
printf("\n");
DLinkList_Reset(list);
for(i = 0;
i < DLinkList_Length(list);
i++)
{
Teacher *tmp = (Teacher *)DLinkList_Get(list, i);
if(tmp == NULL)
return;
printf("tmp->age = %d ",tmp->age);
}
printf("\n");
while(DLinkList_Length(list))
{
DLinkList_Delete(list, 0);
} system("pause");
return ;
}推荐阅读
- 急于表达——往往欲速则不达
- 慢慢的美丽
- 《真与假的困惑》???|《真与假的困惑》??? ——致良知是一种伟大的力量
- 2019-02-13——今天谈梦想（）
- 考研英语阅读终极解决方案——阅读理解如何巧拿高分
- Ⅴ爱阅读，亲子互动——打卡第178天
- 低头思故乡——只是因为睡不着
- 取名——兰
- 每日一话（49）——一位清华教授在朋友圈给大学生的9条建议
- 广角叙述|广角叙述 展众生群像——试析鲁迅《示众》的展示艺术