데이터 구조 - 단일 순환 링크 의 역 치

10695 단어 데이터 구조
선두 노드 의 단일 순환 링크 를 역 설정 합 니 다.
방법 1:
      ,    ,                   ,                   ,                   。

C 언어 코드 구현:
void reverseList(PList x){
    if(x->head!=x->tail&&x->head->next!=x->tail){
        PNode p=x->head;
        PNode c=NULL,n=x->tail;
        //      
        x->tail=p->next;

        do{
            c=p->next;
            p->next=n;
            n=p;
            p=c;
        }while(p!=x->head);
    }
}

방법 2:
      ,          ,          ,          。

C 언어 코드 구현:
void reverseList(PNode x,PList l){
    if(x!=l->tail){
        reverseList(x->next,l);
        x->next->next=x;
    }
    //  head tail 
    if(x==l->head){
        PNode t=x->next;
        x->next=l->tail;
        l->tail=t;
    }
}

전체 디 버 깅 코드:
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

typedef struct Node{
    int data;
    Node *next;
}Node,*PNode;//   

typedef struct List{
    PNode head;
    PNode tail;
    int length;
}List,*PList;//  

void initList(PList x){
    PNode headNode=(PNode)malloc(sizeof(Node));
    if(!headNode)
        exit(0);
    headNode->data=0;
    headNode->next=headNode;
    x->head=headNode;
    x->tail=headNode;
    x->length=0;
}//      

int insertNode(PList x,int i,int e){
    if(i>x->length)
        return 1;

    PNode newNode=(PNode)malloc(sizeof(Node));
    if(!newNode)
        exit(0);
    newNode->data=e;

    PNode p=x->head;
    for(int j=0;j<i;j++)
        p=p->next;

    newNode->next=p->next;
    p->next=newNode;

    if(i==x->length)
        x->tail=newNode;

    x->length++;

    return 0;
}//     

int deleteNode(PList x,int i){
    if(i>x->length)
        return 1;

    PNode p=x->head;
    for(int j=0;j<i-1;j++)
        p=p->next;

    PNode delNode=p->next;
    p->next=delNode->next;

    if(i==x->length)
        x->tail=p;

    free(delNode);
    x->length--;

    return 0;
}//     

void outputList(PList x){
    PNode p=x->head->next;
    for(int i=0;i<x->length;i++){
        printf("%3d",p->data);
        p=p->next;
    }
    printf("
"
); }// int deleteList(PList x){ while(x->length>0){ deleteNode(x,x->length); x->length--; } free(x->head); x->head=NULL; x->tail=NULL; }// void reverseList(PNode x,PList l){ if(x!=l->tail){ reverseList(x->next,l); x->next->next=x; } // head tail if(x==l->head){ PNode t=x->next; x->next=l->tail; l->tail=t; } }// int main(){ // PList myList=(PList)malloc(sizeof(List)); initList(myList); // int e=0; printf(" (10 ):"); for(int i=0;i<10;i++){ scanf("%d",&e); insertNode(myList,myList->length,e); } // outputList(myList); // reverseList(myList->head,myList); // outputList(myList); // deleteList(myList); return 0; }

좋은 웹페이지 즐겨찾기