データ構造【線形テーブル(二)チェーンテーブル】自己構築アルゴリズムライブラリの循環二重チェーンテーブル
7391 ワード
/**データ構造【線形表(二)チェーン表】自作アルゴリズムライブラリの循環二重チェーン表*Copyright(c)2015煙台大学コンピュータと制御工学学院*All right reserved.*ファイル名:danlianbiao.cpp*タイトル:データ構造【線形表(二)チェーン表】循環二重チェーン表*分類:循環二重チェーン表*writer:羅海員*date:2015年10月04日*バージョン:V 1.0.1*オペレーティングシステム:XP*実行環境:VC 6.0*問題の説明:デュアルチェーンテーブルを作成する*ヒント:1.単一チェーンテーブルのストレージ構造を定義し、ヘッドプラグインとテールプラグインでデュアルチェーンテーブルを構築し、作成後の結果を表示します. 2.複雑度の要求、アルゴリズムを設計して専門の関数でアルゴリズムを実現します; 3.理論と実践を結合する*ダブルチェーンテーブルアルゴリズムライブラリアルゴリズムライブラリはプログラムのマルチファイル組織形式を採用し、2つのファイルを含む:1.ヘッダファイル:cdlinklist.h、二重チェーンテーブルのデータ構造を定義するコード、マクロ定義、アルゴリズムを実現する関数の宣言を含む. 2.ソースファイル:cdlinklist.cppは、各種アルゴリズムを実現する関数の定義を含む.アルゴリズムライブラリの作成中、テストを完了するために、同じプロジェクト(project)でmain.cppなどのソースファイルを作成し、main関数を作成し、関連するテストを完了します.
*/
*/
//
#ifndef CDLINKLIST_H_INCLUDED
#define CDLINKLIST_H_INCLUDED
//
typedef int ElemType;
typedef struct DNode //
{
ElemType data;
struct DNode *prior; //
struct DNode *next; //
} CDLinkList;
void CreateListF(CDLinkList *&L,ElemType a[],int n); //
void CreateListR(CDLinkList *&L,ElemType a[],int n); //
void InitList(CDLinkList *&L); //
void DestroyList(CDLinkList *&L); //
bool ListEmpty(CDLinkList *L); //
int ListLength(CDLinkList *L); //
void DispList(CDLinkList *L); //
bool GetElem(CDLinkList *L,int i,ElemType &e); //
int LocateElem(CDLinkList *L,ElemType e); //
bool ListInsert(CDLinkList *&L,int i,ElemType e); //
bool ListDelete(CDLinkList *&L,int i,ElemType &e); //
#endif // CDLINKLIST_H_INCLUDED
//
#include <stdio.h>
#include <malloc.h>
#include "cdlinklist.h"
void CreateListF(CDLinkList *&L,ElemType a[],int n) //
{
CDLinkList *s;
int i;
L=(CDLinkList *)malloc(sizeof(CDLinkList)); //
L->next=NULL;
for (i=0; i<n; i++)
{
s=(CDLinkList *)malloc(sizeof(CDLinkList));//
s->data=a[i];
s->next=L->next; // *s ,
if (L->next!=NULL) L->next->prior=s;
L->next=s;
s->prior=L;
}
s=L->next;
while (s->next!=NULL) // , s
s=s->next;
s->next=L; // next
L->prior=s; // prior
}
void CreateListR(CDLinkList *&L,ElemType a[],int n) //
{
CDLinkList *s,*r;
int i;
L=(CDLinkList *)malloc(sizeof(CDLinkList)); //
L->next=NULL;
r=L; //r ,
for (i=0; i<n; i++)
{
s=(CDLinkList *)malloc(sizeof(CDLinkList));//
s->data=a[i];
r->next=s;
s->prior=r; // *s *r
r=s;
}
r->next=L; // next
L->prior=r; // prior
}
void InitList(CDLinkList *&L) //
{
L=(CDLinkList *)malloc(sizeof(CDLinkList)); //
L->prior=L->next=L;
}
void DestroyList(CDLinkList *&L) //
{
CDLinkList *p=L,*q=p->next;
while (q!=L)
{
free(p);
p=q;
q=p->next;
}
free(p);
}
bool ListEmpty(CDLinkList *L) //
{
return(L->next==L);
}
int ListLength(CDLinkList *L) //
{
CDLinkList *p=L;
int i=0;
while (p->next!=L)
{
i++;
p=p->next;
}
return(i);
}
void DispList(CDLinkList *L) //
{
CDLinkList *p=L->next;
while (p!=L)
{
printf("%d ",p->data);
p=p->next;
}
printf("
");
}
bool GetElem(CDLinkList *L,int i,ElemType &e) //
{
int j=0;
CDLinkList *p;
if (L->next!=L) //
{
if (i==1)
{
e=L->next->data;
return true;
}
else //i 1
{
p=L->next;
while (j<i-1 && p!=L)
{
j++;
p=p->next;
}
if (p==L)
return false;
else
{
e=p->data;
return true;
}
}
}
else //
return 0;
}
int LocateElem(CDLinkList *L,ElemType e) //
{
int n=1;
CDLinkList *p=L->next;
while (p!=NULL && p->data!=e)
{
n++;
p=p->next;
}
if (p==NULL)
return(0);
else
return(n);
}
bool ListInsert(CDLinkList *&L,int i,ElemType e) //
{
int j=0;
CDLinkList *p=L,*s;
if (p->next==L) //
{
s=(CDLinkList *)malloc(sizeof(CDLinkList)); // *s
s->data=e;
p->next=s;
s->next=p;
p->prior=s;
s->prior=p;
return true;
}
else if (i==1) // i=1
{
s=(CDLinkList *)malloc(sizeof(CDLinkList)); // *s
s->data=e;
s->next=p->next;
p->next=s; // *s *p
s->next->prior=s;
s->prior=p;
return true;
}
else
{
p=L->next;
while (j<i-2 && p!=L)
{
j++;
p=p->next;
}
if (p==L) // i-1
return false;
else // i-1 *p
{
s=(CDLinkList *)malloc(sizeof(CDLinkList)); // *s
s->data=e;
s->next=p->next; // *s *p
if (p->next!=NULL) p->next->prior=s;
s->prior=p;
p->next=s;
return true;
}
}
}
bool ListDelete(CDLinkList *&L,int i,ElemType &e) //
{
int j=0;
CDLinkList *p=L,*q;
if (p->next!=L) //
{
if (i==1) //i==1
{
q=L->next; // 1
e=q->data;
L->next=q->next;
q->next->prior=L;
free(q);
return true;
}
else //i 1
{
p=L->next;
while (j<i-2 && p!=NULL)
{
j++;
p=p->next;
}
if (p==NULL) // i-1
return false;
else // i-1 *p
{
q=p->next; //q
if (q==NULL) return 0; // i
e=q->data;
p->next=q->next; // *q
if (p->next!=NULL) p->next->prior=p;
free(q); // *q
return true;
}
}
}
else
return false; //
}
// （ ）
#include <stdio.h>
#include "cdlinklist.h"
int main()
{
CDLinkList *A;
ElemType a[]= {1, 3, 2, 9, 0, 4, 5 ,6, 7, 8};
InitList(A);
CreateListF(A, a, 10);
printf("length: %d
", ListLength(A));
ListInsert(A, 4, 12);
printf("After Insert: ");
DispList(A);
DestroyList(A);
return 0;
}