데이터 구조 학습 노트 - 선형 표 (양 방향 링크, 순환 링크)
14126 단어 데이터 구조
본 고 는 양 방향 링크, 순환 링크 의 기본 적 인 조작 을 토론 한다.
2. 양 방향 링크
2.1 양 방향 링크 의 저장 구조
typedef struct DuLNode
{
ElemType data;
DuLNode *prior,*next;
}DuLNode,*DuLinkList;2.2 양 방향 링크 의 기본 조작 (선두 결점)
(1) 선두 결점 의 양 방향 링크 L 중 i 번 째 위치 전에 요소 e 를 삽입 하고 i 의 합 법 치 는 1 ≤ i ≤ 표 장 + 1 이다.
Status ListInsert(DuLinkList L,int i,ElemType e)
{
int j = 0;
DuLinkList p = L, s;
// i-1
while (j < i-1 && p)
{
p = p->next;
j++;
}
if (!p || j > i-1)
return ERROR;
s = (DuLinkList)malloc(sizeof(DuLNode));
if (!s) exit(OVERFLOW);
s->data = e;
// 1
if (!p->next)
{
s->next = p->next;
s->prior = p;
p->next = s;
}
// 1
else
{
s->next = p->next;
p->next->prior = s;
p->next = s;
s->prior = p;
}
return OK;
}（2 ） 선두 결점 의 양 방향 링크 L 의 제 i 요 소 를 삭제 하고 i 의 합 법 치 는 1 ≤ i ≤ 표 장
// L i ，i 1≤i≤
Status ListDelete(DuLinkList L,int i,ElemType &e)
{
int j = 0;
DuLinkList p = L, q;
// i , p
while (j < i-1 && p->next)
{
p = p->next;
j++;
}
if (!p->next || j > i-1)
return ERROR;
q = p->next;
e = q->data;
//
if (q->next)
{
p->next = q->next;
q->next->prior = p;
}
//
else
{
p->next = q->next;
}
free(q);
return OK;
}(3) 다른 기본 동작 은 매우 간단 합 니 다. 여기 서 더 이상 일일이 열거 하지 않 고 그 를 제 다운로드 자료 (dulist. cpp) 에 넣 고 main 함 수 를 포함 하여 이 기본 동작 들 을 테스트 합 니 다.
3. 순환 링크
3.1 꼬리 포인터 의 단일 순환 링크 를 설치한다.
// 12
#include "ds.h"
using namespace std;
//#define TEST_ALGO
typedef int ElemType;
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
void InitList(LinkList &L);
void DestoryList(LinkList &L);
void ClearList(LinkList &L); // L
Status ListEmpty(LinkList L);
int ListLength(LinkList L);
Status GetElem(LinkList L, int i, ElemType &e);
int LocateElem(LinkList L, ElemType e, Status(*compare)(ElemType, ElemType));
Status PriorElem(LinkList L, ElemType cur_e, ElemType &pre_e);
Status NextElem(LinkList L, ElemType cur_e, ElemType &next_e);
Status InsertList(LinkList &L, int i, ElemType e); // L
Status DeleteList(LinkList &L, int i, ElemType &e); // L
void ListTraverse(LinkList L, void(*vi)(ElemType &e));
void MergeList(LinkList &La,LinkList Lb);
Status compare(ElemType e1, ElemType e2);
void print(ElemType &e);
void InitList(LinkList &L)
{ // ： L
L=(LinkList)malloc(sizeof(LNode)); // ， L
if(!L) //
exit(OVERFLOW);
L->next=L; //
}
void DestroyList(LinkList &L)
{ // ： L
LinkList q,p=L->next; // p
while(p!=L) //
{
q=p->next;
free(p);
p=q;
}
free(L);
L=NULL;
}
void ClearList(LinkList &L) // L
{ // ： L 。 ： L
LinkList p,q;
L=L->next; // L
p=L->next; // p
while(p!=L) //
{
q=p->next;
free(p);
p=q;
}
L->next=L; //
}
Status ListEmpty(LinkList L)
{ // ： L 。 ： L ， TRUE， FALSE
if(L->next==L) //
return TRUE;
else
return FALSE;
}
int ListLength(LinkList L)
{ // ：L 。 ： L
int i=0;
LinkList p=L->next; // p
while(p!=L) //
{
i++;
p=p->next;
}
return i;
}
Status GetElem(LinkList L,int i,ElemType &e)
{ // i ， e OK， ERROR
int j=1; // ，j
LinkList p=L->next->next; // p
if(i<=0||i>ListLength(L)) // i
return ERROR;
while(jnext;
j++;
}
e=p->data; // i
return OK;
}
int LocateElem(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType))
{ // ： L ，compare()
// ： L 1 e compare() 。
// ， 0
int i=0;
LinkList p=L->next->next; // p
while(p!=L->next)
{
i++;
if(compare(p->data,e)) //
return i;
p=p->next;
}
return 0;
}
Status PriorElem(LinkList L,ElemType cur_e,ElemType &pre_e)
{ // ： L
// ： cur_e L ， ， pre_e ，
// ，pre_e
LinkList q,p=L->next->next; // p
q=p->next;
while(q!=L->next) // p
{
if(q->data==cur_e)
{
pre_e=p->data;
return TRUE;
}
p=q;
q=q->next;
}
return FALSE; //
}
Status NextElem(LinkList L,ElemType cur_e,ElemType &next_e)
{ // ： L
// ： cur_e L ， ， next_e ，
// ，next_e
LinkList p=L->next->next; // p
while(p!=L) // p
{
if(p->data==cur_e)
{
next_e=p->next->data;
return TRUE;
}
p=p->next;
}
return FALSE; //
}
Status ListInsert(LinkList &L,int i,ElemType e) // L
{ // L i e
LinkList p=L->next,s; // p
int j=0;
if(i<=0||i>ListLength(L)+1) // i
return ERROR;
while(jnext;
j++;
}
s=(LinkList)malloc(sizeof(LNode)); //
s->data=e; // L
s->next=p->next;
p->next=s;
if(p==L) //
L=s;
return OK;
}
Status ListDelete(LinkList &L,int i,ElemType &e) // L
{ // L i ， e
LinkList p=L->next,q; // p
int j=0;
if(i<=0||i>ListLength(L)) // i
return ERROR;
while(jnext;
j++;
}
q=p->next; // q
p->next=q->next;
e=q->data;
if(L==q) //
L=p;
free(q); //
return OK;
}
void ListTraverse(LinkList L,void(*vi)(ElemType &))
{ // ：L 。 ： L vi()
LinkList p=L->next->next; // p
while(p!=L->next) // p
{
vi(p->data);
p=p->next;
}
printf("
");
}
//
void MergeList(LinkList &La,LinkList Lb)
{ // Lb La ， La
LinkList p=Lb->next;
Lb->next=La->next;
La->next=p->next;
free(p);
La=Lb;
}
Status compare(ElemType a, ElemType b)
{
if (a == b)
return TRUE;
else
return FALSE;
}
void print(ElemType &e)
{
printf("%d ", e);
}
int main()
{
LinkList L;
ElemType e;
int j;
Status i;
InitList(L); // L
i=ListEmpty(L);
printf("L i=%d(1: 0: )
",i);
ListInsert(L,1,3); // L 3,5
ListInsert(L,2,5);
i=GetElem(L,1,e);
j=ListLength(L);
printf("L =%d, 1 %d。
",j,e);
printf("L ：");
ListTraverse(L,print);
PriorElem(L,5,e); // 5
printf("5 %d。
",e);
NextElem(L,3,e); // 3
printf("3 %d。
",e);
printf("L %d(1: 0: )
",ListEmpty(L));
j=LocateElem(L,5,compare);
if(j)
printf("L %d 5。
",j);
else
printf(" 5
");
i=ListDelete(L,2,e);
printf(" L 2 ：
");
if(i)
{
printf(" %d, L ：",e);
ListTraverse(L,print);
}
else
printf(" ！
");
ClearList(L);
printf(" L ，L ：%d(1: 0: )
",ListEmpty(L));
DestroyList(L);
//
int n=5,k;
LinkList La,Lb;
InitList(La);
for(k=1;k<=n;k++)
ListInsert(La,k,k);
printf("La="); // La
ListTraverse(La,print);
InitList(Lb);
for(k=1;k<=n;k++)
ListInsert(Lb,1,k*2);
printf("Lb="); // Lb
ListTraverse(Lb,print);
MergeList(La,Lb);
printf("La+Lb="); //
ListTraverse(La,print);
return 0;
} 3.2 양 방향 순환 링크 (선두 노드)
// (14 )
#include "ds.h"
using namespace std;
typedef int ElemType;
typedef struct DuLNode
{
ElemType data;
DuLNode *prior,*next;
}DuLNode,*DuLinkList;
void InitList(DuLinkList &L);
void DestroyList(DuLinkList &L);
void ClearList(DuLinkList L);
Status ListEmpty(DuLinkList L);
int ListLength(DuLinkList L);
Status GetElem(DuLinkList L,int i,ElemType &e);
DuLinkList GetElemP(DuLinkList L,int i); //
int LocateElem(DuLinkList L,ElemType e,Status(*compare)(ElemType,ElemType));
Status PriorElem(DuLinkList L,ElemType cur_e,ElemType &pre_e);
Status NextElem(DuLinkList L,ElemType cur_e,ElemType &next_e);
Status ListInsert(DuLinkList L,int i,ElemType e);
Status ListDelete(DuLinkList L,int i,ElemType &e);
void ListTraverse(DuLinkList L,void(*vi)(ElemType));
void ListTraverseBack(DuLinkList L,void(*print)(ElemType));
int compare(ElemType a,ElemType b);
void print(ElemType c);
void InitList(DuLinkList &L)
{ // L
L=(DuLinkList)malloc(sizeof(DuLNode));
if(L)
L->next=L->prior=L;
else
exit(OVERFLOW);
}
void DestroyList(DuLinkList &L)
{ // ： L
DuLinkList q,p=L->next; // p
while(p!=L) // p
{
q=p->next;
free(p);
p=q;
}
free(L);
L=NULL;
}
void ClearList(DuLinkList L) // L
{ // ：L 。 ： L
DuLinkList q,p=L->next; // p
while(p!=L) // p
{
q=p->next;
free(p);
p=q;
}
L->next=L->prior=L; //
}
Status ListEmpty(DuLinkList L)
{ // ： L 。 ： L ， TRUE， FALSE
if(L->next==L&&L->prior==L)
return TRUE;
else
return FALSE;
}
int ListLength(DuLinkList L)
{ // ：L 。 ： L
int i=0;
DuLinkList p=L->next; // p
while(p!=L) // p
{
i++;
p=p->next;
}
return i;
}
Status GetElem(DuLinkList L,int i,ElemType &e)
{ // i ， e OK， ERROR
int j=1; // j
DuLinkList p=L->next; // p
while(p!=L&&jnext;
j++;
}
if(p==L||j>i) // i
return ERROR;
e=p->data; // i
return OK;
}
int LocateElem(DuLinkList L,ElemType e,Status(*compare)(ElemType,ElemType))
{ // ：L ，compare()
// ： L 1 e compare() 。
// ， 0
int i=0;
DuLinkList p=L->next; // p 1
while(p!=L)
{
i++;
if(compare(p->data,e)) //
return i;
p=p->next;
}
return 0;
}
Status PriorElem(DuLinkList L,ElemType cur_e,ElemType &pre_e)
{ // ： cur_e L ， ， pre_e ，
// ， ，pre_e
DuLinkList p=L->next->next; // p 2
while(p!=L) // p
{
if(p->data==cur_e)
{
pre_e=p->prior->data;
return TRUE;
}
p=p->next;
}
return FALSE;
}
Status NextElem(DuLinkList L,ElemType cur_e,ElemType &next_e)
{ // ： cur_e L ， ， next_e ，
// ，next_e
DuLinkList p=L->next->next; // p 2
while(p!=L) // p
{
if(p->prior->data==cur_e)
{
next_e=p->data;
return TRUE;
}
p=p->next;
}
return FALSE;
}
DuLinkList GetElemP(DuLinkList L,int i) //
{ // L i 。i 0， 。 i ，
// NULL( 2.18、2.19 )
int j;
DuLinkList p=L; // p
if(i<0||i>ListLength(L)) // i
return NULL;
for(j=1;j<=i;j++)
p=p->next;
return p;
}
Status ListInsert(DuLinkList L,int i,ElemType e)
{ // L i e，i 1≤i≤ +1
// 2.18， +1
DuLinkList p,s;
if(i<1||i>ListLength(L)+1) // i
return ERROR;
p=GetElemP(L,i-1); // L i p
if(!p) // p=NULL, i ( 1 )
return ERROR;
s=(DuLinkList)malloc(sizeof(DuLNode));
if(!s)
return OVERFLOW;
s->data=e;
s->prior=p; // i-1
s->next=p->next;
p->next->prior=s;
p->next=s;
return OK;
}
Status ListDelete(DuLinkList L,int i,ElemType &e) // 2.19
{ // L i ，i 1≤i≤
DuLinkList p;
if(i<1) // i
return ERROR;
p=GetElemP(L,i); // L i p
if(!p) // p=NULL, i
return ERROR;
e=p->data;
p->prior->next=p->next;
p->next->prior=p->prior;
free(p);
return OK;
}
void ListTraverse(DuLinkList L,void(*visit)(ElemType))
{ // L ， visit()
DuLinkList p=L->next; // p
while(p!=L)
{
visit(p->data);
p=p->next;
}
printf("
");
}
void ListTraverseBack(DuLinkList L,void(*visit)(ElemType))
{ // L ， visit()。
DuLinkList p=L->prior; // p
while(p!=L)
{
visit(p->data);
p=p->prior;
}
printf("
");
}
int compare(ElemType a,ElemType b)
{
if (a == b)
return TRUE;
else
return FALSE;
}
void print(ElemType c)
{
printf("%d ", c);
}
int main()
{
DuLinkList L;
int i,n;
Status j;
ElemType e;
InitList(L);
for(i=1;i<=5;i++)
ListInsert(L,i,i); // i i
printf(" ：");
ListTraverse(L,print); //
printf(" ：");
ListTraverseBack(L,print); //
n=2;
ListDelete(L,n,e); // n
printf(" %d ， %d， ：",n,e);
ListTraverse(L,print); //
printf(" %d
",ListLength(L));
printf(" ：%d(1: 0: )
",ListEmpty(L));
ClearList(L); //
printf(" ， ：%d(1: 0: )
",ListEmpty(L));
for(i=1;i<=5;i++)
ListInsert(L,i,i); // 5
ListTraverse(L,print); //
n=3;
j=GetElem(L,n,e); // n e
if(j)
printf(" %d %d
",n,e);
else
printf(" %d
",n);
n=4;
i=LocateElem(L,n,compare);
if(i)
printf(" %d %d
",n,i);
else
printf(" %d
",n);
j=PriorElem(L,n,e);
if(j)
printf("%d %d
",n,e);
else
printf(" %d
",n);
j=NextElem(L,n,e);
if(j)
printf("%d %d
",n,e);
else
printf(" %d
",n);
DestroyList(L);
return 0;
}좋은 웹페이지 즐겨찾기
