リスト - C（宿題）

Question

私は以下を実装しようとしています。

// Destructive Abstract data type ilist 

    struct ilist_ADT; 
    typedef struct ilist_ADT *ilist; 
    // prototype for secret implementation 
    // do not rely on ilist being a pointer 

    ilist iempty(); 
    // returns an empty ilist 

    int iempty_huh(ilist il); 
    // returns 1 (true) if il is empty 
    // returns 0 (false) if il is not empty 

    int ifirst(ilist il); 
    // returns the first element in il 
    // il must not be empty 

    ilist icons_destroy(int in, ilist il); 
    // returns an ilist with in added as the first element of il 
    // references to il cease to be valid ilists 
    // the result must eventually be consumed by one of: 
    //  icons_destroy, irest_destroy, idelete 

    ilist irest_destroy(ilist il); 
    // modifies il to remove the first element, and returns the modified ilist 
    // frees the memory associated with the first element 
    // references to il cease to be valid ilists 
    // the result (if non-empty) must eventually be consumed by one of: 
    //  icons_destroy, irest_destroy, idelete 

    ilist icopy(ilist il); 
    // returns a new copy of il that continues to be a valid 
    // ilist with the same elements even when il is destroyed 
    // the result must eventually be consumed by one of: 
    //  icons_destroy, irest_destroy, idelete 

    int ilength(ilist il); 
    // computes the number of elements in il 

    void idelete(ilist il); 
    // frees the storage for ilist 
    // all further references to il become invalid 
    // NOTE: every ilist created by icons_destroy or 
    //   irest_destroy or icopy must eventually be destroyed 
    //   by being consumed by icons_destroy or 
    //   irest_destroy or idelete 

私は最初のアイコンに焦点を当てた、と私は、次のような非破壊アイコンがあります。

ilist icons(int in, ilist il) {  
    ilist r = malloc(sizeof(struct ilist_ADT)); 
    r->first = in; 
    r->rest = il; 
    r->length = 1 + ilength(il); 
    return r; 

} 

どのように正確に私は、これは実装に合うようになるだろうか？言い換えれば、私はそれを破壊的にするにはどうすればいいのですか？

Answer 1

"破壊的"とは、関数（またはoopのメソッドの受信者）への引数が変更可能であることを意味します。非破壊関数とは、引数を変更せずに、変更されたコピーを返します。破壊的な関数を可能にする利点は、そのコピーを作成する必要がないということです。したがって、通常はもっと少ないmallocが必要です（この例では数は同じです）。あなたはilist ilを使用して誰もが（あなたが何かをしたことの重リンクリストで、この唯一の作品を気付くことはありません！：有効な未修正のリストのエントリをcon'ingすると、元のilist ilを維持していることがわかります提供iconsの実装では

コース）。

は

破壊的な実装で最初あなたは、引数を修正するために、それはまた、あなたが有意義な方法で引数を修正することになっていることを意味ことができます：あなたはそのようなことを変更する必要があり、まだへの参照を持っている人元ilist ilはと表示されますを参照してください。あなたはそうのようにこれを行うことができます：

// observation: the names are not the best, i would call it destructiveICons 
// (and ->first should be called ->value) 
ilist icons_destroy(int in, ilist il) { 
    ilist second = malloc(sizeof(struct ilist_ADT)); 
    second->length = il->length 
    second->first = il->first 
    second->rest = il->rest; 
    il->length += 1; 
    il->rest = second; 
    il->first = in; 
    return il; 
} 

今ilist ilに参照を保持している他の誰かが古い以前に最初の要素に続く新しい最初の要素が表示されます。

Answer 2

私はこの実装が破壊的であると見ることができると思いますが（私は実際には "破壊的"という意味を理解していません）。
（ゴミを収集しない言語で）動的に割り当てられたデータ構造を使用する場合、最も重要な問題は、最終的にデータをリリースする責任があるかどうかです。 iconsの実装では、新しいハンドルを使用してリリースを行う必要があります。古いハンドルは使用しないでください。この意味で、古いハンドルはもはや有効ではありません。

あなたは物事を変えることができるので、古いハンドルは本当に使用できなくなります。 ilistがチェーン内の最初のものであることを示すフィールドを追加し、エレメントの追加/削除時にフィールドを維持することができます。その後、すべてのAPIは、それらに与えられたハンドルが最初でない場合、動作を拒否することができます。