双方向チェーンテーブル-設計と実現


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 ; }