学習ノート------データ構造(C言語版)二重ループチェーンテーブル
7619 ワード
//Function realization.cpp
//main.cpp
//DoubleLinkList.h
//predefined.h
注意:二重ループチェーンテーブルの挿入と削除操作と単一チェーンテーブルの違い!
#include"predefined.h"
#include"DoubleLinkList.h"
Status ListInsert_DuL(DuLinkList *L,int i,ElemType e)
// 2.18： L i e，
//i 1<=i<= +1。
{
DuLinkList p,s;
if(!(p=GetElemP_DuL(*L,i))) return ERROR;
if(!(s=(DuLinkList)malloc(sizeof(DuLNode)))) return ERROR;
(*s).data=e;
(*s).prior=(*p).prior;
(*(*p).prior).next=s;
(*s).next=p;
(*p).prior=s;
return OK;
}
Status ListDelete_DuL(DuLinkList *L,int i,ElemType *e)
// 2.19： L i ，i 1<=i<= 。
{
DuLinkList p;
if(!(p=GetElemP_DuL(*L,i))) return ERROR;
*e=(*p).data;
(*(*p).prior).next=(*p).next;
(*(*p).next).prior=(*p).prior;
free(p);
return OK;
}
Status InitList_DuL(DuLinkList *L)//
{
(*L)=(DuLinkList)malloc(sizeof(DuLNode));
if(!(*L)) exit(OVERFLOW);
(**L).next=(**L).prior=*L;
return OK;
}
Status DestroyList_DuL(DuLinkList *L)//
{
DuLinkList p,q;
p=*L;
do
{
q=(*p).next;
free(p);
p=q;
}
while(p!=*L);
(*L)=NULL;
return OK;
}
Status ClearList_DuL(DuLinkList *L)//
{
DuLinkList p,q;
p=*L;
if(!p) return FALSE;
p=(*p).next;
while(p!=*L)
{
q=p;
p=(*p).next;
free(q);
}
(**L).next=(**L).prior=*L;
return OK;
}
Status ListEmpty_DuL(DuLinkList L)// ， TRUE。
{
if(L&&(*L).next==L&&(*L).prior==L) return TRUE;
else return FALSE;
}
Status ListLength_DuL(DuLinkList L)// L 。
{
ElemType n=0;
DuLinkList p;
if(L)
{
p=(*L).next;
while(p!=L)
{
n++;
p=(*p).next;
}
}
return n;
}
Status GetElem_DuL(DuLinkList L,int i,ElemType *e)// e L i
{
DuLinkList p;
int j=1;
p=(*L).next;
if(L)
{
while(p!=L&&ji) return ERROR;
*e=(*p).data;
return OK;
}
else return ERROR;
}
Status LocateElem_DuL(DuLinkList L,ElemType e,Status (*compare)(DuLinkList L,ElemType e))
// L e compare
{
DuLinkList p;
p=L;
Status n;
n=compare(p,e);
if(n) return n;
else return FALSE;
}
Status PriorElem_DuL(DuLinkList L,ElemType cur_e,ElemType *e)//
{
DuLinkList p;
p=(*L).next;
if(L)
{
while(p!=L)
{
if((*p).data==cur_e)
{
if((*p).prior==L) return ERROR;
else
{
*e=(*(*p).prior).data;
return OK;
}
}
p=(*p).next;
}
}
return ERROR;
}
Status NextElem_DuL(DuLinkList L,ElemType cur_e,ElemType *e)//
{
DuLinkList p;
p=(*L).next;
if(L)
{
while(p!=L)
{
if((*p).data==cur_e)
{
if((*p).next==L) return ERROR;
else
{
*e=(*(*p).next).data;
return OK;
}
}
p=(*p).next;
}
}
return ERROR;
}
DuLinkList GetElemP_DuL(DuLinkList L,int i)
// L i 。
{
DuLinkList p;
int j;
if(i>ListLength_DuL(L)+1||i<1) return NULL;
p=(*L).next;
for(j=1;j//main.cpp
#include"predefined.h"
#include"DoubleLinkList.h"
Status equal(DuLinkList L,ElemType e)
{
int i;
DuLinkList p;
p=(*L).next;
for(i=1;p!=L;i++)
{
if((*p).data==e) return i;
p=(*p).next;
}
return FALSE;
}
Status visit(DuLinkList L)
{
printf("%d ",(*L).data);
return OK;
}
int main()
{
DuLinkList La;
Status s;
int n,i,m;
ElemType e;
printf("Function 1
★ InitList_DuL(DuLinkList *L) ...
");
s=InitList_DuL(&La);
printf("▲ La: %d (0: 1: )
",s);
printf("Function 2
★ ListEmpty_DuL(DuLinkList L) ...
");
s=ListEmpty_DuL(La);
printf("▲ La : %d (0: 1: )
",s);
printf("Function 3
★ ListInsert_DuL(DuLinkList *L,int i,ElemType e) ...
");
printf("▲ La ：");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
printf("▲ La %d ：",i);
scanf("%d",&m);
s=ListInsert_DuL(&La,i,m);
printf("▲ ?:%d (1: 0: )
",s);
}
printf("
");
printf("Function 4
★ ListTraverse_DuL(DuLinkList L,Status (*visit)(DuLinkList L)) ...
");
printf("▲La ：La={");
ListTraverse_DuL(La,visit);
printf("}
");
printf("Function 5
★ ListLength_DuL(DuLinkList L) ...
");
s=ListLength_DuL(La);
printf("▲La ：%d
",s);
printf("Function 6
★ ListDelete_DuL(DuLinkList *L,int i,ElemType *e) ...
");
ListDelete_DuL(&La,3,&e);
printf("▲ La 3 ：\"%d\"
",e);
printf("▲La ：La={");
ListTraverse_DuL(La,visit);
printf("}
");
printf("Function 7
★ GetElem_DuL(DuLinkList L,int i,ElemType *e) ...
");
GetElem_DuL(La,3,&e);
printf("▲La \"%d\"
",e);
printf("Function 8
★ LocateElem_DuL(DuLinkList L,ElemType e,Status (*compare)(DuLinkList L,ElemType e)) ...
");
s=LocateElem_DuL(La,5,equal);
printf("▲La \"5\" %d
",s);
printf("Function 9
★ PriorElem_DuL(DuLinkList L,ElemType cur_e,ElemType *e) ...
");
PriorElem_DuL(La,5,&e);
printf("▲La \"5\" %d
",e);
printf("Function 10
★ NextElem_DuL(DuLinkList L,ElemType cur_e,ElemType *e) ...
");
NextElem_DuL(La,5,&e);
printf("▲La \"5\" %d
",e);
printf("Function 11
★ ClearList_DuL(DuLinkList *L) ...
");
printf("▲La :");
ListEmpty_DuL(La)?printf(" La ！！！
"):printf(" La ！！！
");
ClearList_DuL(&La);
printf("▲La :");
ListEmpty_DuL(La)?printf(" La ！！！
"):printf(" La ！！！
");
printf("Function 12
★ DestroyList_DuL(DuLinkList *L) ...
");
printf("▲La :");
La?printf(" La ！！！
"):printf(" La ！！！
");
DestroyList_DuL(&La);
printf("▲La :");
La?printf(" La ！！！
"):printf(" La ！！！
");
}//DoubleLinkList.h
typedef struct DuLNode
{
ElemType data;
struct DuLNode *prior;
struct DuLNode *next;
}DuLNode,*DuLinkList;
Status ListInsert_DuL(DuLinkList *L,int i,ElemType e);
Status ListDelete_DuL(DuLinkList *L,int i,ElemType *e);
Status InitList_DuL(DuLinkList *L);
Status DestroyList_DuL(DuLinkList *L);
Status ClearList_DuL(DuLinkList *L);
Status ListEmpty_DuL(DuLinkList L);
Status ListLength_DuL(DuLinkList L);
Status GetElem_DuL(DuLinkList L,int i,ElemType *e);
Status LocateElem_DuL(DuLinkList L,ElemType e,Status (*compare)(DuLinkList L,ElemType e));
Status PriorElem_DuL(DuLinkList L,ElemType cur_e,ElemType *e);
Status NextElem_DuL(DuLinkList L,ElemType cur_e,ElemType *e);
DuLinkList GetElemP_DuL(DuLinkList L,int i);
Status ListTraverse_DuL(DuLinkList L,Status (*visit)(DuLinkList L));
Status equal(DuLinkList L,ElemType e);
Status visit(DuLinkList L);//predefined.h
#include "stdio.h"
#include "stdlib.h"
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef int ElemType;注意:二重ループチェーンテーブルの挿入と削除操作と単一チェーンテーブルの違い!