array linklist

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;}
}

........................................................................................................

通用串列
資料型態和個數可不固定

 

2007-03-05 18:56:12發表 0000-00-00 00:00:00修改   

數據分析
程式開發
計算機組織與結構
資料結構與演算法

Database and MySql
manage tool
windows
unix-like
linux service
network
network layer3
network layer2
network WAN
network service
作業系統
數位鑑識
資訊安全解決方案
資訊安全威脅
Cisco security
Cisco network
Cisco layer3
Cisco layer2



  登入      [牛的大腦] | [單字我朋友] Powered by systw.net