资料型态(Data

《资料型态(Data》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、資料型態(DataType)-程式語言的變數所能表示的資料種類*基本型態(PrimitiveType):integer,real,boolean,character(byte)*結構化型態(StructuredType):string,array,record/structureinti,j;charc;floatr;inti1[10],j1[10];floatr1[10];i1[0]=20;i2[1]=90;…串列(List)*有序串列可以是空的()或寫成(a1,a2,...,an)串列的表示法(representationoflists)*順序對應(Seq

2、uentialmapping)-array*鏈結串列(Linkedlist)-pointer堆疊與佇列(Stacks&Queues)*堆疊是一個有序串列，所有的insertion和deletion動作均在頂端(top)進行*具有後進先出(LIFO-lastinfirstout)特性*佇列是一個有序串列，所有的insertion和deletion是發生在串列的不同端，加入的一端稱為尾端(rear)，刪除的一端稱為前端(front)*具有先進先出(FIFO-firstinfirstout)特性Representationofastack:*aone-dimensi

3、onalarray:stack[0:n-1]*avariable:top*linkedlist*node:data,link*avariable:topRepresentationofaqueue:*aone-dimensionalarray:q[0:n-1]*twovariables:front&rear*linkedlist*node:data,link*twovariables:front&rearTrees*Atreeisafinitesetofoneormorenodes*樹是一個或多個節點(node)所組成的有限集合*有一個特殊的節點稱為樹根(ro

4、ot)*每一個節點底下有零個或一個以上的子樹(subtree):T1,T2,…,Tnn0*節點(node)*分支(branch,edge)*樹根(root)*子點(children)*父點(parent)*終端節點(leaf,terminalnodes)Trees*非終端節點(nonterminalnodes)*兄弟(siblings)*祖先(ancestorofanode):allthenodesalongthepathfromtheroottothatnode*分支度(degree):thenumberofsubtreesofanode*樹的分支度(de

5、greeofatree):themaximumdegreeofthenodesinthetree*階度(level):initiallylettherootbeatleveloneTrees*高度(height,depth):themaximumlevelofanynodeinthetree*Aforestisasetofn0disjointtrees*若一樹有n個nodes，則必有且唯有n-1個edges*AgraphwithoutacycleRepresentationofaTree:*linkedlist*node:data,link,tag*when

6、tag=1,datafieldcontainsapointertoalistratherthanadataitemBinaryTrees:*Anynodecanhaveatmosttwochildren*二元樹上每個節點的degree2*左子樹(leftsubtree)&右子樹(rightsubtree)*二元樹可以是空集合(empty)*Themaximumnumberofnodesonleveiofabinarytreeis2i-1*Themaximumnumberofnodesinabinarytreeofdepthkis2k-1,k>0.*Foran

7、ynon-emptybinarytree,ifn0isthenumberofterminalnodesandn2isthenumberofnodesofdegree2,thenn0=n2+1.二元樹的特例:*歪斜樹(skewedbinarytree)left-skewedbinarytree,right-skewedbinarytree*全滿二元樹(fullbinarytree)Thebinarytreeofdepthkthathasexactly2k-1nodes*完整二元樹(completebinarytree)Abinarytreewithnnodesa

8、nddepthkiscompletei