資料結構學習筆記（三）

    深入了解抽象資料類型;

ADT是一些操作的集合，是數學的抽象，在ADT的定義中根本沒涉及如何實作操作的集合，這個可以看作是子產品化設計的補充。這些操作在程式隻編寫一次，而程式中任何其他部分需要在該ADT上運作其中的一種操作時可以通過調用适當的函數來進行，若需要改變操作細節，隻需要修改運作這些ADT操作的例程就可以。

     對所有的表操作都可以通過使用數組來實作，雖然數組是動态指定的，但是還是需要對标的最大值進行估計，并且插入和删除操作需要二次時間，是以簡單數組一般不用來實作這種結構。而為了減少順序清單的插入和删除帶來的時間浪費，我們需要可以不連續儲存的形式，這符合鍊式清單的想法。

    然而有順序表轉換為鍊式清單會遇到一下三個問題：

1.不存在從表的前面插入元素的方法；

2.從最前面删除一個元素是一個特殊情況，因為它改變了表的起始位置，這将會造成表的丢失；

3.雖然上述指針移動很簡單，删除一個元素時，但是，這要求我們必須記住删除元素前面的表格元素。

然而當我們在開頭再加上一個空指針時就很容易的解決以上三個問題；

  接下來設計一個表，按照C語言的約定，作為list表和Position以及函數的原型都列在所謂的頭檔案中，具體的Node節點則在.C檔案中：

typedef int ElementType
		#ifdef _List_H
		struct Node;//聲明節點為結構體類型
		typedef struct Node *PtrToNode;
		typedef PrtToNode List;
		typedef PtrToNode Position;

		List MakeEmpty(List L);//置空函數
		int IsEmpty(List L);//是否為空
		int IsLast(List L);//是否是到最後了
		void Delete(ElementType X,List L);//删除指定位置的元素
		Position Find(ElementType X,List L);//傳回X在表中的位置
		Position FindPrevious(ElementType X,List L);//傳回X元素的前驅的位置
		void Insert(ElementTypeX, List L,Positon P);//在P處後面插入元素X插入元素
		void DEeleteList(List L);//删除整個表
		Position Header(List L);//表頭的位置
		Position First(List L);//表中第一個元素的位置
		Position Advance(Position P);//移動到位置P
		ElementType Retrieve(Position P);//P處的元素值

		#endif
           

     我們開始實作NODE節點的資訊：

     建立Node節點資訊的單元，包含一個資料體和一個指針

struct Node
        {
            ElementType Element;
            Position    Next;
        };
           

   實作第一個方法：将清單置空：

List
        MakeEmpty( List L )
        {
            if( L != NULL )
                DeleteList( L );
            L = malloc( sizeof( struct Node ) );
            if( L == NULL )
                FatalError( "Out of memory!" );
            L->Next = NULL;
            return L;
        }
           

    檢驗是否為空的函數實作如下：

int IsEmpty( List L )
        {
            return L->Next == NULL;
        }
           

檢驗資料是不是最後一個位置：

int IsLast( Position P, List L )
        {
            return P->Next == NULL;
        }
           

查找位置：

Position
        Find( ElementType X, List L )
        {
            Position P;

/* 1*/      P = L->Next;
/* 2*/      while( P != NULL && P->Element != X )
/* 3*/          P = P->Next;

/* 4*/      return P;
        }
           

若删除清單中的元素，則：

void
        Delete( ElementType X, List L )
        {
            Position P, TmpCell;

            P = FindPrevious( X, L );

            if( !IsLast( P, L ) )  /* Assumption of header use */
            {                      /* X is found; delete it */
                TmpCell = P->Next;
                P->Next = TmpCell->Next;  /* Bypass deleted cell */
                free( TmpCell );
            }
        }
           

尋找某個元素的前一個位置：

Position
        FindPrevious( ElementType X, List L )
        {
            Position P;

/* 1*/      P = L;
/* 2*/      while( P->Next != NULL && P->Next->Element != X )
/* 3*/          P = P->Next;

/* 4*/      return P;
        }
           

線上性表中插入某個資料：

void
        Insert( ElementType X, List L, Position P )
        {
            Position TmpCell;

/* 1*/      TmpCell = malloc( sizeof( struct Node ) );
/* 2*/      if( TmpCell == NULL )
/* 3*/          FatalError( "Out of space!!!" );

/* 4*/      TmpCell->Element = X;
/* 5*/      TmpCell->Next = P->Next;
/* 6*/      P->Next = TmpCell;
        }
           

删除整個清單：

void
        DeleteList( List L )
        {
            Position P;

/* 1*/      P = L->Next;  /* Header assumed */
/* 2*/      L->Next = NULL;
/* 3*/      while( P != NULL )
            {
/* 4*/          free( P );
/* 5*/          P = P->Next;
           

P=Tmp;
            }
        }
           

傳回表的位置和元素資訊等：包括表的Header，表的第一個元素的位置，以及元素的類型等

Position
        Header( List L )
        {
            return L;
        }

        Position
        First( List L )
        {
            return L->Next;
        }

        Position
        Advance( Position P )
        {
            return P->Next;
        }

        ElementType
        Retrieve( Position P )
        {
            return P->Element;
        }
           

     測試檔案如下：

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

void
PrintList( const List L )
{
    Position P = Header( L );

    if( IsEmpty( L ) )
        printf( "Empty list\n" );
    else
    {
        do
        {
            P = Advance( P );
            printf( "%d ", Retrieve( P ) );
        } while( !IsLast( P, L ) );
        printf( "\n" );
    }
}

main( )
{
    List L;
    Position P;
    int i;

    L = MakeEmpty( NULL );
    P = Header( L );
    PrintList( L );

    for( i = 0; i < 10; i++ )
    {
        Insert( i, L, P );
        PrintList( L );
        P = Advance( P );
    }
    for( i = 0; i < 10; i+= 2 )
        Delete( i, L );

    for( i = 0; i < 10; i++ )
        if( ( i % 2 == 0 ) == ( Find( i, L ) != NULL ) )
            printf( "Find fails\n" );

    printf( "Finished deletions\n" );

    PrintList( L );

    DeleteList( L );

    return 0;
}