11 - 데이터 구조링크 관련 조작

/ / 동적 으로 비 순환 단일 체인 표를 만 들 고 헤드 포인터 PNODE createList (void) 를 되 돌려 줍 니 다. /링크 void traverseList (PNODE pHead); /빈 bool isEmpty (PNODE pHead) 인지 여부; /링크 길이 int listSize (PNODE pHead); /요소 삽입, pos - 위치 (첫 번 째 노드 는 색인 1), value - 노드 삽입 값  bool insert(PNODE pHead, int pos, int value); // 하나의 요 소 를 삭제 합 니 다. pValue - 노드 를 삭제 하 는 데이터 필드 bool delete (PNODE pHead, int pos, int * pValue); /정렬, 거품 상승 순서,  void sort(PNODE pHead); // 정렬, 빨리 정렬, 
void sort_2(PNODE pHead);
전체 프로그램 
05-node.c

#include <stdio.h>  // print / scanf
#include <malloc.h> // malloc
#include <stdlib.h> // exit
#include <stdbool.h>// bool

typedef struct Node
{
    int data;   //    
    struct Node * pNext; //    
} NODE, * PNODE; 
// NODE <==> struct Node, PNODE<==>struct Node *

//           ,       
PNODE createList(void);
//     
void traverseList(PNODE pHead);
//     
bool isEmpty(PNODE pHead);
//     
int listSize(PNODE pHead);
//       , pos-  (       1), value-       
bool insert(PNODE pHead, int pos, int value);
//       , pValue-        
bool delete(PNODE pHead, int pos, int * pValue);
//   ,      , 
void sort(PNODE pHead);
//   ,      , 
void sort_2(PNODE pHead);

int main(void)
{
    PNODE pHead = NULL; // <==> struct Node * pHead;

    //           
    pHead = createList();
    
    //       
    if (isEmpty(pHead))
    {
        printf("    ? YES
");
    }
    else 
    {
        printf("    ? NO
");
    }
    

    //      
    printf("     ? %d
", listSize(pHead));

    //     
    traverseList(pHead);     
    
    //   
/*
    int pos, value;
    printf("          
");
    printf("pos = ");
    scanf("%d", &pos);
    printf("value = ");
    scanf("%d", &value);

    insert(pHead, pos, value);
    traverseList(pHead);
*/
    //   
/**/
    int pos, value;
    printf("          
");
    printf("pos = ");
    scanf("%d", &pos);

    delete(pHead, pos, &value);
    printf("       value = %d
", value);

    traverseList(pHead);


    //   -   
    sort(pHead);

    //   -   
    sort_2(pHead);

    traverseList(pHead);

    return 0;
}

PNODE createList(void)
{
    int length; //     ,      
    printf("     length = ");
    scanf("%d", &length);

    //    .
    PNODE pHead = (PNODE) malloc( sizeof(NODE) );
    if ( NULL == pHead)
    {
        printf("        !!");
        exit(-1);
    }    

    //    
    PNODE pTail = pHead;
    pTail->pNext = NULL;

    //      
    int i;
    int value;  //         
    for (i = 0; i < length; ++i)
    {
        printf("     %2d      : ", i+1);
        scanf("%d", &value);

        PNODE pNewNode = (PNODE) malloc(sizeof(NODE));  //        
        pNewNode->data = value; //       
        //          
        pTail->pNext = pNewNode;    
        pNewNode->pNext = NULL; //          

        pTail = pNewNode;   //              .

    }

    return pHead;
}

void traverseList(PNODE pHead)
{   
    PNODE pNode = pHead->pNext; //      
    printf("  : ");
    while (NULL != pNode)
    {
        printf("%3d", pNode->data);
        pNode = pNode->pNext;   //        
    }

    printf("
");
    return;
}

bool isEmpty(PNODE pHead)
{
    if ( NULL == pHead || NULL == pHead->pNext)
    {
        return true;
    }
    return false;
}

int listSize(PNODE pHead)
{
    int count = 0;  //    ,

    PNODE pNode = pHead->pNext; //      

    while (NULL != pNode)
    {
        ++count;
        pNode = pNode->pNext;
    }
    
    return count;
}

bool insert(PNODE pHead, int pos, int value)
{
    if (pos < 1 || pos > listSize(pHead))
    {
        printf("    , 0 < pos < %d 
", listSize(pHead)+1);
        return false;
    }
    
    //                  
    PNODE pNode = pHead; //      ,    0
    int count = 0;
    while (count < pos - 1)
    {
        pNode = pNode->pNext;
        ++count;
    }

    //     
    PNODE pNew = (PNODE) malloc( sizeof(NODE) );
    pNew->data = value;

    //   
    pNew->pNext = pNode->pNext;
    pNode->pNext = pNew;

    return true;
}

bool delete(PNODE pHead, int pos, int * pValue)
{
    if (pos < 1 || pos > listSize(pHead))
    {
        printf("    , 0 < pos < %d 
", listSize(pHead)+1);
        return false;
    }

    int count = 0; //    
    PNODE pNode = pHead; //      

    //                  
    for (; count < pos - 1; ++count)
    {
        pNode = pNode->pNext;
    }

    //       
    PNODE pTemp = pNode->pNext; // pTemp            
    pNode->pNext = pTemp->pNext;

    //           
    *pValue = pTemp->data;

    //     
    free(pTemp); 

    return true;
}

void sort(PNODE pHead)
{
    int i, j;
    int length = listSize(pHead);
    int temp;
    PNODE pNode = NULL;

    for (i = 0; i < length - 1; ++i)
    {
        pNode = pHead->pNext;   //      
        for (j = 0; j < length - 1 - i; ++j)
        {
            if (pNode->data > pNode->pNext->data)
            {
                temp = pNode->data;
                pNode->data = pNode->pNext->data;
                pNode->pNext->data = temp;
            }
            pNode = pNode->pNext;   
        }
    }

    return;
}

void sort_2(PNODE pHead)
{
    int i, j;
    int length = listSize(pHead);
    int temp;
    PNODE pLeft, pRight;

    pLeft = pHead;

    for (i =0; i < length -1; ++i)
    {
        pLeft = pLeft->pNext;
        pRight = pLeft->pNext;

        for (j = i + 1; j < length; ++j)
        {
            if (pLeft->data < pRight->data)
            {
                temp = pLeft->data;
                pLeft->data = pRight->data;
                pRight->data =temp;
            }
            pRight = pRight->pNext;
        }
    }

    return;
}