双方向チェーンテーブル-設計と実現
7293 ワード
1.双方向チェーンテーブルは、通常のチェーンテーブルのすべての動作を完了し、通常のチェーンテーブルの逆方向遍歴効率が低いという問題を解決することができる.
双方向チェーンテーブルは通常のチェーンテーブルに比べてあまりヒントがなく、削除操作を挿入する際の異常処理に注意する必要があります.
0番ノードを削除する異常、1回目に挿入する異常、最後に削除する異常を挿入します.
ダイレクトコード
双方向チェーンテーブルは通常のチェーンテーブルに比べてあまりヒントがなく、削除操作を挿入する際の異常処理に注意する必要があります.
0番ノードを削除する異常、1回目に挿入する異常、最後に削除する異常を挿入します.
ダイレクトコード
#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)
");
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)
");
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)
");
return -1;
}
tlist = (TDLinkList *)list;
return tlist->length;
}
void DLinkList_Clear(DLinkList *list)
{
TDLinkList *tlist;
if(NULL == list)
{
printf("DLinkList_Length err (NULL == list)
");
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)
");
return NULL;
}
tlist = (TDLinkList *)list;
if(pos >= tlist->length)
{
printf("DLinkList_Get err (tlist->length >= pos)
");
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)
");
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)
");
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)
");
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)
");
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)
");
return NULL;
}
tlist = (TDLinkList *)list;
return tlist->slider;
}
DLinkListNode* DLinkList_Next(DLinkList *list)
{
TDLinkList *tlist;
if(NULL == list)
{
printf("DLinkList_Next err (NULL == list)
");
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)
");
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()
{
int ret = 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("
");
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("
");
while(DLinkList_Length(list))
{
DLinkList_Delete(list, 0);
}
system("pause");
return ;
}