C Primer Plusの高度なデータ表示

抽象データ型(ADT)
タイプは何からなりますか?1つのタイプ(type)は、1つのプロパティセットと1つのオペレーションセットの2つの情報を指定します.
新しいデータ型を定義します.まず、構造を設計することによって、データを格納する方法を提供する必要があります.2つ目は、データを操作する方法を提供する必要があります.
コンピュータ科学は新しいタイプを定義する成功方法を研究した.この方法は3つのステップを使用して抽象から具体的なプロセスを完了する.

は、タイプの属性およびタイプに対して実行可能な操作の抽象的な説明を提供する.この記述は、特定の実装の制約を受けるべきではなく、特定のプログラミング言語の制約を受けるべきではない.このような正式な抽象記述は抽象データ型(ADT)

と呼ばれる.

ADTを実装するプログラミングインターフェース(関数の集合)を開発します.つまり、データを格納し、必要な操作を実行するための関数の集合を記述する方法を示します.たとえば、Cでは、構造の定義と構造を操作するための関数のプロトタイプを同時に提供することができます.

は、このインタフェースを実装するためにコードを記述する.このステップは重要ですが、この新しいタイプのプログラマーを使用するには、実装の詳細を理解する必要はありません.

抽象データ型-リストを例に説明する
タイプ名:
リスト#リスト#
タイプのプロパティ:
アイテムシーケンスを保存できます
タイプアクション:
リストを空のリストに初期化
 
リストが空かどうかを確認
 
リストが満たされているかどうかを確認します
 
リスト内のアイテムの数を決定
 
リストの最後にアイテムを追加
 
リストを巡回し、リスト内の各アイテムを処理します.
 
リストをクリア
 
リスト内の任意の場所に項目を挿入
 
リストからアイテムを削除
 
リストからアイテムを取り出します(リストは変更しません)
 
リスト内のアイテムを置換
 
リスト内のアイテムの検索
非公式で抽象的なリスト定義の場合:プロジェクトシーケンスを保存し、前の操作を適用できるデータオブジェクトです.この定義は、リストに格納できるアイテムを説明していません.配列またはリンクの構造セットまたは他のデータ形式を使用してこれらのアイテムを保存するかどうかは指定されていません.リスト内の要素の数を取得するなどの操作を実行する方法は指定されていません.これらはすべて実現に残された細部である.
   
C言語インタフェースの構築
単純リストのインタフェースには,1記述データがどのように表現されるか,2記述ADT動作を実現する関数の2つの部分がある.インタフェースの設計はADTの記述とできるだけ密接に一致しなければならない.したがって、intやstruct filmなどの専用タイプではなく、汎用的なItemタイプを使用して表現する必要があります.この方法の1つは,Cのtypedefツールを用いてItemを所望のタイプとして定義することである.次のようになります.

#define TSIZE 45  /*           */
struct film {
      char title[TSIZE];
      int rating;
};
typedef struct film Item;

チェーンテーブルの実装では、各リンクはノード(node)と呼ばれます.各ノードには、リストの内容を形成する情報と、次のノードへのポインタが含まれます.たとえば、次のようになります.

typedef struct node {
      Item item;
      struct node * next;  //          
} Node;
typedef Node * List;

↓等価

struct node {
     Item item;
     struct node * next;
};
typedef struct node Node;
typedef Node * List;       //        ，             

リスト内のアイテムの数を保存する変数を追加することもできます.

typedef struct list {
      Node * head;        //         
      int size;               //         
} List;

次の宣言を考慮します.

List movies;

moviesは、ノードへのポインタを確立したり、構造を確立したりするのではなく、リストを確立しています.moviesの正確なデータは、インタフェース層に表示されない実装の詳細を示す.
起動後、プログラムはカーソルをNULLに初期化する必要があります.リストタイプを使用する人は、詳細を心配する必要はありません.次のコードを使用できます.

InitializeList(movies);

プログラマは、リストを初期化するためにInitializeList()関数を使用するべきであることを知っているだけで、リスト変数の正確なデータ実装を知る必要はありません.これはデータの非表示の一例です.データ隠蔽は、高度なプログラミングとデータの詳細を隠す芸術です.InitializeList()の関数のプロトタイプは次のとおりです.

/*   ：          */
/*    ：plist       */
/*    ：            */
void InitializeList(List * plist);

C言語では、すべてのタイプと関数情報を1つのパッケージに統合する方法は、タイプ定義と関数プロトタイプ(「操作前」と「操作後」の注釈を含む)をヘッダファイルに格納することです.このファイルは、プログラマがこのタイプを使用するために必要なすべての情報を提供します.
 
単鎖表の実現と分析(C Primer Plus(第5版)第17章高級データ表示-プログラムリスト17.4を例に)
抽象データ型のヘッダファイル(list.h):データ構造を定義し、ユーザーインタフェースにプロトタイプを提供する

/*            */
#ifndef LIST_H_
#define LIST_H_
#include <stdbool.h>
/*          */
#define TSIZE 45
struct film {
    char title[TSIZE];
    int rating;
};
/*        */
typedef struct film Item;

typedef struct node {
    Item item;
    struct node * next;
} Node;
typedef Node * List;  //   Node(struct node)     

/*      */
/*   ：                  */
/*    ：plist            */
/*    ：            */
void InitializeList(List * plist);

/*   ：                               */
/*    ：plist                       */
/*    ：          true：    true */
bool ListIsEmpty(const List plist);

/*   ：                                 */
/*    ：plist                       */
/*    ：          true：    true */
bool ListIsFull(const List * plist);

/*   ：                               */
/*    ：plist                       */
/*    ：                            */
unsigned int ListItemCount(const List * plist);

/*   ：                              */
/*    ：item                        */
/*         plist                       */
/*    ：      ，            , */
/*             true：    false             */
bool AddItem(Item item, List * plist);

/*   ：                             */
/*    ：plist                           */
/*         pfun      ，                    */
/*           Item                           */
/*    ：pfun                    */
void Traverse(const List * plist, void (*pfun)(Item item));

/*         (   )                           */
/*    ：plist                           */
/*    ：                              */
/*                                         */
void EmptyTheList(List * plist);

#endif // LIST_H_

インタフェースを実装するための関数コードの提供

#include <stdio.h>
#include <stdlib.h>
#include "list.h"
//              
static void CopyToNode(Item item, Node * pnode);

void InitializeList(List * plist)
{
    *plist = NULL;
}
bool ListIsEmpty(const List plist)
{
    if(plist == NULL)
        return true;
    else
        return false;
}
bool ListIsFull(const List * plist)
{
    Node * pt;
    bool full;

    pt = (Node *)malloc(sizeof(Node));
    if(pt == NULL)
        full = true;
    else
        full = false;
    free(pt);
    return full;
}
unsigned int ListItemCount(const List * plist)
{
    unsigned int count = 0;
    Node * pnode = *plist;

    while(pnode != NULL)
    {
        ++count;
        pnode = pnode->next;
    }
    return count;
}
//        
bool AddItem(Item item, List * plist)
{
    Node * pnew;
    Node * scan = *plist;

    pnew = (Node *)malloc(sizeof(Node));
    if(pnew == NULL)
        return false;
    CopyToNode(item, pnew); // pnew->item = item;
    pnew->next = NULL;
    if(scan == NULL)
        *plist = pnew;
    else
    {
        while(scan->next != NULL)
            scan = scan->next;
        scan->next = pnew;
    }
    return true;
}
void Traverse(const List * plist, void (*pfun)(Item item))
{
    Node * pnode = *plist;
    while(pnode != NULL)
    {
        (*pfun)(pnode->item);
        pnode = pnode->next;
    }
}
void EmptyTheList(List * plist)
{
    Node * psave;
    while(*plist != NULL)
    {
        psave = (*plist)->next;
        free(*plist);
        *plist = psave;
    }
}
static void CopyToNode(Item item, Node * pnode)
{
    pnode->item = item;
}

リストインタフェースを特定のプログラミング問題のソースファイルに適用する

#include <stdio.h>
#include <stdlib.h>
#include "list.h"

void showmovies(Item item);

int main(void)
{
    List movies; //        
    Item temp;

    //        
    InitializeList(&movies);
    //         
    if(ListIsFull(&movies))
    {
        fprintf(stderr, "No memory available! Bye!
");
        exit(1);
    }
    //      
    puts("Enter first movie title: ");
    while(gets(temp.title) != NULL && temp.title[0] != '\0')
    {
        puts("Enter your rating <0-10>: ");
        scanf("%d", &temp.rating);
        while(getchar() != '
')
            continue;
        //            
        if(AddItem(temp, &movies) == false)
        {
            fprintf(stderr, "Problem allocating memory
");
            break;
        }
        //        ，        
        if(ListIsFull(&movies))
        {
            puts("The list is now full.");
            break;
        }
        puts("Enter next movies title (empty line to stop): ");
    }
    //   
    if(ListIsEmpty(movies))
        printf("No data entered.");
    else
    {
        printf("Here is the movie list: 
");
        Traverse(&movies, showmovies);
    }
    printf("You entered %d movies.
", ListItemCount(&movies));
    //   
    EmptyTheList(&movies);
    printf("Bye!
");

    return 0;
}
void showmovies(Item item)
{
    printf("Movie: %s Rating: %d
", item.title, item.rating);
}