資料結構總複習datastructure+

《資料結構總複習datastructure+》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、資料結構總複習什麼是Datastructure?將資料群組織起來的抽象資料型態，稱為資料結構。典型的資料結構資料表格(Table)堆疊(stack)佇列(queue)串列(list)樹(tree)圖形(graph)table,stack,queue：可用陣列表現出來List,tree,graph：適合用指標表現出來。堆疊(Stack)將資料依序從堆疊下面儲存起來，並視需要從堆疊的上面將資料取出的方式之資料結構，稱為堆疊。PushStackEtoptopAtopDtopEStackADOuttoptop堆疊(Stack)【特性】：後進先出(LIFO)LIFO

2、：lastinfirstout。【動作】：push：儲存資料進堆疊。pop：將資料從堆疊中取出。Push的演算法：inttop=0;//top初值為0push(n){if(top0){top--;k=stack[top];returnk;}elsereturn-1;}佇列(queue)處理資料的方式先進先出。FIFO：FirstInFirstOutin佇列(queue)outheadtailqueue[0]que

3、ue[1]queue[2]queue[N-1]佇列(queue)現設有queue[0]至queue[n-1]共n個元素的陣列，表示佇列開頭的指標設為head，表示佇列尾端的指標設為tail。取出資料：在head進行。head=head+1。儲存資料：在tail位置進行。tail=tail+1;佇列初始狀態：head=tail=0佇列為空：當head=tail時。佇列為滿：tail+1為n時。inoutheadtailqueue[0]queue[1]queue[2]queue[N-1]佇列(queue)解決佇列使用一次就無法使用的問題：當head=tail

4、=n時。將陣列尾端queue[n-1]與開頭queue[0]連結起來成為一個環形佇列。inoutheadtailqueue[0]queue[1]queue[2]queue[N-1]鏈結串列(LinkedList)鏈結串列是一種有順序的串列ptraddressoffirstnodeptr->dataptr->linkdatanodeLink(tonextnode)LinkedList的優點它比循序的串列(sequentiallist，如陣列)更容易做任意資料的「插入」(insertions)與「刪除」(deletions)。在「mat」和「cat」之間加入「

5、sat」:Getanodethatiscurrentlyunused;letitsaddressbepaddr.Setthedatafieldofthisnodetomat.Setpaddr’slinkfieldtopointtotheaddressfoundinthelinkfieldofthenodecontainingcat.Setthelinkfieldofthenodecontainingcattopointtopaddr.以結構定義一個LinkList必要的宣告如下:typedefstructlist_node*list_pointer;typ

6、edefstructlist_node{chardata[4];list_pointerlink;};list_pointerptr=NULL;建立一個新節點(node)產生一個新的nodeptr=(list_pointer)malloc(sizeof(list_node));//配置一個指標空間把字串資料“bat“放入list中strcpy(ptr->data,“bat”);ptr->link=NULL;ptraddressoffirstnodeptr->dataptr->linkNULLtabptraddressoffirstnodeptr->da

7、taptr->linkCreateatwo-nodelisttypedefstructlist_node*list_pointer;typedefstructlist_node{intdata;list_pointerlink;};list_pointerptr=NULL;list_pointercreate2(){list_pointerfirst,second;first=(list_pointer)malloc(sizeof(list_node));second=(list_pointer)malloc(sizeof(list_node));seco

8、nd->link=NULL;second->data=20;fir