[데이터 구조] 양 방향 링크 정의 와 기본 작업

7278 단어 데이터 구조
양 방향 링크:
양 방향 링크 의 정의:
typedef struct DuLNode{
    LElemType data;
    struct DuLNode *next;
    struct DuLNode *pre;
    DuLNode ( LElemType Data=0,struct DuLNode *Pre=NULL,struct DuLNode *Next=NULL){
        data=Data;
        next=Next;
        pre=Pre;
    }
}DuLNode,*DuLinkList;

양 방향 링크 기본 작업 의 실현:
(1) 、 초기 화 작업 InitDuLinkList( &L )
(2) 단일 체인 시트 를 만 드 는 작업 CreateDuLinkList(&L , n)
(3) 선형 표 가 빈 표 인지 판단 하기 ListIsEmpty (L)
(4), 선형 표 의 길이 ListLength (L)
(5), 선형 표 의 i 번 째 요소 GetElem (L, i, & e)
(6), 원소 e 가 선형 테이블 에 있 는 위치 찾기 LocateElem (L, e)
(7) 、 삽입 작업 ListInsert (& L, i, e)
(8) 、 삭제 작업 LIstDelete (& L, i, & e) 
(1) 、 초기 화 작업 InitLinkList( &L )
void InitDuLinkList(DuLinkList &L){
    L=new DuLNode;
}

(2) 단일 체인 시트 를 만 드 는 작업 CreateLinkList(&L , n)
void CreateLinkList_Tail(DuLinkList &L,int n=0){ //   
    L=new DuLNode;
    DuLinkList Pre=L,p;
    LElemType data;
    for(int i=1;i<=n;i++){
        printf("    %d data :
",i); cin>>data; p=new DuLNode(data,Pre); Pre->next=p; Pre=p; } }

 
void CreateLinkList_Head(DuLinkList &L ,int n=0){//   
    L=new DuLNode;
    DuLinkList Pre=L,p,s;
    LElemType data;
    for(int i=1;i<=n;i++){
        printf("    %d data :
",i); cin>>data; p=new DuLNode(data,Pre,Pre->next); s=Pre->next; if(s) s->pre=p; Pre->next=p; } }

(3) 선형 표 가 빈 표 인지 판단 하기 ListIsEmpty (L)
int ListIsEmpty(DuLinkList &L){
    if(L->next){
        return 1;
    }return 0;
}

(4), 선형 표 의 길이 ListLength (L)
int ListLength(DuLinkList L){
    int len=0;
    DuLinkList p=L->next;
    while(p){
        len++;
        p=p->next;
    }
    return len;
}

(5), 선형 표 의 i 번 째 요소 GetElem (L, i, & e)
void GetElem(DuLinkList L,int i,LElemType &e){
    int j=1;
    DuLinkList p=L->next;
    while(p&&jnext;
    }
    if(j>i||!p){
        printf("");
        return ;
    }
    e=p->data;
}

(6), 원소 e 가 선형 테이블 에 있 는 위치 찾기 LocateElem (L, e)
LElemType LocateElem(DuLinkList L, LElemType e){
    int j=1;
    DuLinkList p=L->next;
    while(p&&p->data!=e){
        j++;
        p=p->next;
    }
    if(!p){
        printf("LocateElem  not found %d
",e); return -1; } return j; }

(7) 、 삽입 작업 ListInsert (& L, i, e)
void ListInsert(DuLinkList L, int i, LElemType e){
    int j=0;
    DuLinkList p=L,s;
    while(p&&jnext;
    }
    if(!p||i-1next)){  //         
        printf("ListInsert index %d error
",i); return ; } s=new DuLNode(e,p,p->next); (p->next)->pre=s; s->pre=p; p->next=s; }

(8) 、 삭제 작업 LIstDelete (& L, i, & e)
void ListDelete(DuLinkList &L,int i,LElemType &e){
    int j=0;
    DuLinkList p=L,s;
    while(p->next&&jnext;
    }
    if(!p->next||i<=j){
        printf("\" ListDelete \" index : %d error
",i); return ; } s=p->next; p->next=s->next; (s->next)->pre=p; e=s->data; delete s; }

 
완전한 테스트 코드
#include
#include
#include
#include
#define LElemType int
using namespace std;
typedef struct DuLNode{
    LElemType data;
    struct DuLNode *next;
    struct DuLNode *pre;
    DuLNode ( LElemType Data=0,struct DuLNode *Pre=NULL,struct DuLNode *Next=NULL){
        data=Data;
        next=Next;
        pre=Pre;
    }
}DuLNode,*DuLinkList;

void InitDuLinkList(DuLinkList &L){
    L=new DuLNode;
}
void CreateLinkList_Tail(DuLinkList &L,int n=0){ //   
    L=new DuLNode;
    DuLinkList Pre=L,p;
    LElemType data;
    for(int i=1;i<=n;i++){
        printf("    %d data :
",i); cin>>data; p=new DuLNode(data,Pre); Pre->next=p; Pre=p; } } void CreateLinkList_Head(DuLinkList &L ,int n=0){// L=new DuLNode; DuLinkList Pre=L,p,s; LElemType data; for(int i=1;i<=n;i++){ printf(" %d data :
",i); cin>>data; p=new DuLNode(data,Pre,Pre->next); s=Pre->next; if(s) s->pre=p; Pre->next=p; } } void OutputDuLinkList(DuLinkList &L){ DuLinkList p=L->next,t; printf("
"); while(p){ printf("%d
",p->data); t=p; p=p->next; } printf("
"); p=t; while(p->pre){ printf("%d
",p->data); p=p->pre; } } int ListIsEmpty(DuLinkList &L){ if(L->next){ return 1; }return 0; } int ListLength(DuLinkList L){ int len=0; DuLinkList p=L->next; while(p){ len++; p=p->next; } return len; } void GetElem(DuLinkList L,int i,LElemType &e){ int j=1; DuLinkList p=L->next; while(p&&jnext; } if(j>i||!p){ printf(""); return ; } e=p->data; } LElemType LocateElem(DuLinkList L, LElemType e){ int j=1; DuLinkList p=L->next; while(p&&p->data!=e){ j++; p=p->next; } if(!p){ printf("LocateElem not found %d
",e); return -1; } return j; } void ListInsert(DuLinkList L, int i, LElemType e){ int j=0; DuLinkList p=L,s; while(p&&jnext; } if(!p||i<=j){ printf("ListInsert index %d error
",i); return ; } s=new DuLNode(e,p,p->next); (p->next)->pre=s; p->next=s; } void ListDelete(DuLinkList &L,int i,LElemType &e){ int j=0; DuLinkList p=L,s; while(p->next&&jnext; } if(!p->next||i<=j){ printf("\" ListDelete \" index : %d error
",i); return ; } s=p->next; p->next=s->next; (s->next)->pre=p; e=s->data; delete s; } int main() { DuLinkList La; LElemType e=0,t; CreateLinkList_Tail(La,5); //CreateLinkList_Head(La,5); OutputDuLinkList(La); printf("len=%d
",ListLength(La)); for(int i=1;i<=5;i++){ GetElem(La,i,e); printf("%d
",e); } /*printf(" :
"); scanf("%d",&e); t=LocateElem(La,e); if(t!=-1){ printf("Found!!! %d
",t); }*/ ListInsert(La,2,123); OutputDuLinkList(La); e=0; ListDelete(La,2,e); OutputDuLinkList(La); if(e!=0){ printf(" : %d
",e); } return 0; }

 

좋은 웹페이지 즐겨찾기