『アルゴリズム一』—一方向チェーン表

前言
名言:プログラム=データ構造+アルゴリズムですので、最近は「プログラマの実用的なアルゴリズム」をよく見てください.
一方向チェーン
チェーンは比較的簡単なデータ構造かもしれません.人の認知はモデルに依存していますので、チェーンは生活の中車チェーンというものによく対応できます.
チェーンの中の一環
キーポイントはチェーンの一環をどう表しますか?経典の定義は以下の通りです.

//     
struct Node
{
    char *City;
    int Temp;
    struct Node *next;
};

typedef struct Node * Link;

操作
データ構造があり、常にデータを操作します.次に片方向リンク表の通常動作を提供します.
1、初期化操作

void CreateLite()
{
    head = NULL;  //   
    iNodeCount = 0; //    
}

2、ノードを追加して一つのチェーンにノードを追加するのは簡単ですが、いくつかの場合には特殊処理が必要です.例えば、空のテーブル(つまり、最初のノードを追加することです.)、最初の時は、それを特殊処理します.

int AddNodeAscend(Link to_add)
{
    Link  pn,
          pre,
          curr;
    struct Node dumy;  //            ！！！！！

    pn = (Link)malloc(sizeof( struct Node));
    if ( NULL == pn )
    {
        return 0;
    }
    memcpy( pn , to_add ,sizeof(struct Node));

    dumy.next = head;
    pre = &dumy;
    curr = head;

    int i;
    for (; curr != NULL ; pre = curr, curr = curr->next)
    {
    }
    pre->next = pn;
    pn->next = curr;

    head = dumy.next;
    return 1;
}

3、ノードの削除

int DeleNode(Link to_Del)
{
    Link curr,
         pre;
    int i;

    if ( NULL == head )
    {
        return 0;
    }

    for ( pre = NULL , curr = head; curr != NULL;pre = curr, curr = curr->next)
    {
        i = NodeCmp(to_Del, curr);
        if ( curr != NULL && 0 ==i )
        {
            if ( pre)
            {
                pre->next = curr->next;
            }
            else
            {
                head = curr->next;
            }

            FreeNode(curr); 
            iNodeCount -= 1;
            return 1;
        }
    }
    return 0;
}

4、メモリを解放する操作(重要です.メモリが漏れないようにしてください.)

void FreeNode(Link to_free)
{
    free( to_free->City );
    free(to_free);
}

締め括りをつける
一方通行のチェーンは簡単で使いやすいですが、一定の制限があります.
付録(完全な定義を与える)

#ifndef LINK_H
#define LINK_H

//     
struct Node
{
    char *City;
    int Temp;
    struct Node *next;
};

typedef struct Node * Link;

int AddNodeAscend(Link to_add); //            
void CreateLite( void ); //       
int DeleNode( Link to_Del); //      
int DuplicateNode( Link , Link ); //      
void FreeNode(Link to_free); //      
void ShowNode( void ); //    
int NodeCmp(Link , Link ) ; //      
#endif

#include "Link.h"
#include <stdlib.h>
#include <string>
Link head;
int iNodeCount;

int AddNodeAscend(Link to_add)
{
    Link  pn,
          pre,
          curr;
    struct Node dumy;  //      

    pn = (Link)malloc(sizeof( struct Node));
    if ( NULL == pn )
    {
        return 0;
    }
    memcpy( pn , to_add ,sizeof(struct Node));

    dumy.next = head;
    pre = &dumy;
    curr = head;

    int i;
    for (; ; pre = curr, curr = curr->next)
    {
        if ( NULL == curr )
        {
            break; //    
        }
        i = NodeCmp(pn,curr);
        if ( i <= 0 )
        {
            break;
        }
    }

    if ( curr && 0 == i)
    {
        if ( 0 == DuplicateNode(curr ,pn ) )
        {
            return 1;
        }
    }

    pre->next = pn;
    pn->next = curr;

    head = dumy.next;
    return 1;
}

int DuplicateNode( Link inLinst, Link duplicate)
{
    FreeNode(duplicate);
    return 0;
}

int DeleNode(Link to_Del)
{
    Link curr,
         pre;
    int i;

    if ( NULL == head )
    {
        return 0;
    }

    //curr = head; 
    //i = NodeCmp(to_Del,curr);

    for ( pre = NULL , curr = head; curr != NULL;pre = curr, curr = curr->next)
    {
        i = NodeCmp(to_Del, curr);
        if ( curr != NULL && 0 ==i )
        {
            if ( pre)
            {
                pre->next = curr->next;
            }
            else
            {
                head = curr->next;
            }

            FreeNode(curr); 
            iNodeCount -= 1;
            return 1;
        }
    }
    return 0;
}

int NodeCmp(Link a, Link b)
{
    if ( a->Temp != b->Temp )
    {
        return a->Temp - b->Temp;
    }
    else
    {
        return strcmp(a->City ,b->City);
    }
}

void CreateLite()
{
    head = NULL;
    iNodeCount = 0;
}

void FreeNode(Link to_free)
{
    free( to_free->City );
    free(to_free);
}

void ShowNode()
{
    Link pn;
    int count, median;

    for ( count = 0 ,pn = head;pn;pn = pn->next)
    {
        count +=1;
    }

    median = count/2+1;

    if ( count)
    {
        count = 0;
        for ( pn = head; pn;pn = pn->next)
        {
            printf("%-20s: %3d",pn->City,pn->Temp);
            count += 1;
            if ( count == median )
            {
                printf("----Median-----");
            }
            printf("
");
        }

    }
    else
    {
        printf("Empty list
");
    }
}