DIV CSS 佈局教程網

 DIV+CSS佈局教程網 >> 網頁腳本 >> JavaScript入門知識 >> AJAX入門 >> AJAX詳解 >> 和arden一起學算法--第三天
和arden一起學算法--第三天
編輯:AJAX詳解     

第三天    抽象數據類型ADT

先給定義:抽象數據類型abstract data type是一種只通過接口訪問的數據類型(值的集合以及作用於其上的運算組合)。

A set of data values and associated Operations that are precisely specifIEd independent of any particular implementation.

主要在於這個詞abstract。它使得此data type只能通過接口來訪問數據。數據的表示法及實現的運算都存在在實現中,用戶不能通過接口看到實現。想想,有點OO的意思吧, 它和class這樣的東西有這樣的共同點(封裝怎麼也算是OO三個重要特點之一),按照我的理解來說,class便是一種ADT,或者它在語法層面更高級一點。

真正的ADT比較苛刻,我們的串不算一個。為什麼?我們都可以直接提領它和它的地址,沒有接口在中間。我們可以string str=”this is a string”;printf(“%c”, str[1]);不需要寫一個函數來代替這個運算符:printf(“%c”,str.getchar(1));當然我們可以定做一個完全ADT的string。

下面給一個熟悉的例子:下堆棧STACK。

其實就是我們說的LIFO(last in first out)的堆棧,和它對應的那個我們常叫它隊列FIFO(first in first out)。

我們假設這個抽象數據類型有這樣幾種操作:初始化、壓棧、出棧、清空。

在stack.h中我們定義下面的函數:此代碼寫在stack.h中

void stack_init( int );

Int stack_empty();

void stack_push(item);

Item stack_pop();

下面在選擇實現方式的時候,我們可以有很多種方法:自己完全定義或者拿來現成的。數組可以吧,鏈表也可以,

給一個數組的實現:

#include <stdlib.h>

#include "Item.h"

#include "STACK.h"

static Item *s;

static int N;

void STACKinit(int maxN)

  { s = malloc(maxN*sizeof(Item)); N = 0; }

int STACKempty()

  { return N == 0; }

void STACKpush(Item item)

  { s[N++] = item; }

Item STACKpop()

  { return s[--N]; }

 

我使用其它的好不好?比如串?不好,串太狹隘了,字符已經局限了它的作為,此處非它擅長(並不是不行,只是在效率和實現復雜度上不可取)。

看起來一個ADT並不復雜,定義好數據和接口便可以付諸使用。現實是,這個棧的邏輯關系並不復雜,對於很有經驗的熟悉的東西作ADT可能容易。面對一個新問題,我們如何周全的設計它是關鍵。

先看看怎麼用這個stack。

逆波蘭這個名次在數據結構中一定聽說過。正是使用棧的好時候。看看這個後綴表達式:5 9 8 + 4 6 * * 7 + *

我們需要人化一下:我們容易看懂的表達式是這樣的:5*((9+8)*(4*6)+7)

這個轉換過程我們需要借助堆棧幫我們完成,讀取一個逆波蘭式,如果是數字壓入棧,如果是運算符,將前面兩個入棧的

pop出來和讀到的運算符計算,再將結果壓入棧。就是這樣一個過程,我們看看代碼如何實現:

#include <stdio.h>

#include <string.h>

#include "Item.h"

#include "STACK.h"

main(int argc, char *argv[])

  { char *a = argv[1]; int i, N = strlen(a);

    STACKinit(N);

    for (i = 0; i < N; i++)

      {

        if (a[i] == '+')

          STACKpush(STACKpop()+STACKpop());

        if (a[i] == '*')

  &nbsp;       STACKpush(STACKpop()*STACKpop());

        if ((a[i] >= '0') && (a[i] <= '9'))

          STACKpush(0);

        while ((a[i] >= '0') && (a[i] <= '9'))

          STACKpush(10*STACKpop() + (a[i++]-'0'));

      }

    printf("%d \n", STACKpop());

  }  

Ok,看出來了為了簡便沒有給出減法和除法的運算,因為這兩個運算沒有交換率,寫出代碼可能復雜些,不利於我們理解棧的使用。

會使用現成的ADT還沒有變成英雄,我們還需要自己來規劃並實現自己想得到的ADT。參考上面已經實現的ADT,我們可以照貓畫虎,畫多了就會得心應手。既然這樣我們來畫一個FIFO。比較麻煩的是,堆棧其實就在操作一個內存地址,進去出來都是這裡,哈,這是一個只有一個門的房間。FIFO隊列有前門和後門,前門出後門進。在實現其數據操作時需要兩個內存位置,稍微復雜了一些。先自己想想怎麼做,然後看下面的代碼好了。

void QUEUEinit(int);

 int QUEUEempty();

void QUEUEput(Item);

Item QUEUEget();

-----

#include <stdlib.h>

#include "Item.h"

#include "QUEUE.h"

typedef struct QUEUEnode* link;

struct QUEUEnode { Item item; link next; };

static link head, tail;

link NEW(Item item, link next)     

  { link x = malloc(sizeof *x);>

    x->item = item; x->next = next;    

    return x;                        

  }                                  

void QUEUEinit(int maxN)

  { head = NULL; }

int QUEUEempty()

  { return head == NULL; }

QUEUEput(Item item)

  {

    if (head == NULL)

      { head = (tail = NEW(item, head)); return; }

    tail->next = NEW(item, tail->next);

  tail = tail->next;

  }

Item QUEUEget()

  { Item item = head->item;

    link t = head->next;

    free(head); head = t;

    return item;

  }
XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved