array(陣列) 大小固定,各元素型別需相同,可直接存取某元素 說明:一群相同資料型態的資料存在連續的空間,所形成的集合,並具有固定的位置 優點:可計算出個資料記憶體位址,提供隨機存取的運作 缺點:插入與刪除困難,資料個數受限 適合:資料個數固定的靜態資料的查詢 陣列計算 s=起始位置 d=元素的位元組 r1=陣列1的索引數量 i1=陣列1要找的索引位置-陣列1開始位置(通常是0) 以row(列)為主: s+[i1*(r2*r3*...rn)+i2*(r3*...rn)+...i(n-1)*(rn)+in]*d ex:三維陣列[0:3,0:6,2:7],要找[3,2,2] 而r1=3,r2=7,r3=6(7-2+1) 而i1=3(3-0),i2=2(2-0),i3=0(2-2) 所以公式=s+[(3)*7*6 + (2)*6 + (0)]*d ps:c,pascal 以(col)行為主: ex:同上 只要把陣列反轉成為[2:7,0:6,0:3]並轉要找的為[2,2,3] 用相同公式及得到 r1=6,r2=7,r3=3 i1=0(2-2),i2=2(2-0),i3=3(3-0) 所以公式=s+[(0)*7*3 + (2)*3 + (3)]*d ps:fortran 一元n次多項式 poly(x)=c0+c1x^1+c2x^2+...cnx^n=(c0,c1,c2,...cn) ex:1+3x^3+36x^4 全部係數表示法,(要佔用的元素=最高次數+1) 1,0,0,3,36 佔用5個元素 非零項表示法,(若係數大多是零則用,可節省記憶體) 1.0 , 3.3 ,36.4 佔用6個元素.. sparse matrix(稀疏矩陣表示法) [列,行,值,指標]->[列,行,值,指標]->[列,行,值,指標]->... ex: 0 5 0 4 0 0 0 0 3 [1,2,5,指標]->[2,1,4,指標]->[3,3,3,指標]-> 反轉矩陣方法: 只要將列和行互換即可得到如下 ex:[1,2,4,指標]->[2,1,5,指標]->[3,3,3,指標]-> .........................................................................................................................
linked list(鏈結串列) 簡單的動態資料結構: 說明:一群相同資料型態的節點儲存在任意的空間,而節點會儲存資料及下一個節點的位置 優點:插入與刪除(因邏輯順序和實際順序不同,因此不需搬動其他資料),資料個數不限(但需額外空間存pointer) 缺點:只能透過鏈結欄位循序存取,不可直接存取某元素(需依串接順序掃描) 適用:資料個數變動的動態資料插入與刪除 可能問題:資料遺失,懸吊指標 應用:管理主記憶體單元 靜態記憶體配置,用陣列做 動態記憶體配置,用指標做 結構宣告: typedef struct listnode{ int data; struct listnode *next }listnode; listnode *head=null; 常見串列有以下: single linked list/chain(單鏈串列) 各節點只有一個link指向下一個節點 只能夠在目前節點之後進行插入運作及刪除運作,但因只有一個鏈結欄位,所以記憶體空間方面比雙鏈來得較有效率 bi-directional/double linked list(雙鏈串列) 各節點有兩個link欄位,分別指向前與後的節點,可提供較大的應用彈性 可在目前節點之後及之前進行插入運作及刪除運作,若應用上需要由目前節點往前後移動會比單鏈更有效率達成 circular list(循環串列) 串列結尾的link是指回串列開頭節點,在合併演算法及歸還空間演算法都是O(1) simple list(簡單串列) 串列結尾的link是空指標 插入節點 void insert(listnode *ptr,int value){ listnode *newnode; newnode=malloc(sizeof(struct listnode)); //產生新節點 newnode->data=value; newnode->link=ptr->link; //設定新節點的鏈節欄位 ptr->link=newnode; //將目前節點指向新節點 } 刪除下一個節點 void delete(listnode *ptr){ if(ptr==null||ptr->link==null){ printf("empty");} else{ listnode *nextnode; nextnode=ptr->link; //指向要刪除的節點 ptr->link=nextnode->link; //將目前節點指向被刪除節點的下一個節點 free(nextnode); //動態歸還節點 } } 在資料x後插入新節點 void find_insert(struct linklist *start,int finddata,struct linklist *newnode){ //start負責進入 struct linklist *next; //next負責移動 next=start; while(next!=NULL&&next->data==finddata){ next=next->link;} //尋找finddata if(next==NULL){ printf("finddata don't exist"); }else{ newnode->link=next->link next->link=newnode; } } recursive反轉節點 void inverse(listnode middle,listnode right){ if(right==null)head=middle; else{ left=middle; middle=right; right=right->link middle->link=left; inverse(middle,right); } } 非遞迴反轉節點 ..... 雙向鏈節插入某節點之後 void insert(node x,node y){ y->rlink=x->rlink; y->llnk=x; x->rlink=y; if(y->rlink!=null){ y->rlink->llink=y;} } ........................................................................................................ 通用串列 資料型態和個數可不固定 |