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;}
}
…………………………………………………………………………………………..
通用串列
資料型態和個數可不固定