線性表
線性表描述
在現實的應用中,有兩種實作線性表資料元素存盤功能的方法
- 順序表存盤結構
- 鏈式存盤結構
線性表的特性
線性表是一種最基本,最簡單的常用資料結構,實際中,線性表都是以List ,stack,queue ,arr ,string等特殊的表現形式來使用
線性表是一個線性結構,他是一個含有n ≥ 0 節點的有限序列. (不過可以想到) 最小位沒有前驅(但是有后驅),最后位沒有后驅(但有前驅節點)
k1 ,k2 ,kn...
特征 :
必須存在 唯一的首位元素和唯一的最后元素
除最后的元素外,必須有唯一后繼, 除第一元素外都必須要有唯一前驅
線性表基本操作程序
Setnull (L) //: 清空 Length(L) //:表長度和各元素個數 Get(L,I) //獲取第i 個元素 Next(L,I) //獲取后繼元素 Locate(L,x)// 回傳指定元素位置， Insert(L,i,x); //插入元素 delete(L,x) ;//洗掉元素 empty(L); //是否為null
線性表的結構特定
均勻性:雖不同的資料表的資料元素各種各樣,但統一線性表元素必須有相同型別和長度
有序性:資料元素在線性表中的位置只取決于序,資料元素之前的相對位子上線性的,即存在唯一last[i] ,firt[i] 資料元素,出首尾元素外,其他元素只有一個資料源前趨,后面只有一個直接后繼.
總結
由于順序表的硬性規定,即用連續的存盤單元 順序存盤 線性表中的各個元素,所以當對順序表進行插入和洗掉時,必須必須移動資料才能實作線性表邏輯上的相鄰關系.極大損耗性能.
.net core 中以 線性表實作的 List 就是非常典型的特點 ,不適合remove 等操作 ,但訪問元素的速度非常快.
值得看的是微軟在原始碼中實作線性表最重要的動態擴容操作時 ,無論哪種os下,擴充直接 Capacity*2.
鏈表 01
問題:
我認為除去效率問題，其實linkedlist最重要的特性
是插入洗掉的時候迭代器不失效，
可以安全的存盤在其他資料結構中，
要牢記比起效率，正確性總是第一位的，
所以很多答案提到了記憶體池，lru等等，其實關鍵問題在于哈希表中存盤了指向鏈表元素的指標，
這種程式中一旦分配完句柄，指標就泄露到了容器外部（比如hashmap存盤了pageNode），
如果采用vector那種連續記憶體空間，一個insert騰挪，指標錯位，程式就錯了，
至于效率問題，LinkedList本身對快取的友好程度就不如vector，
在不要求元素排列順序的情況下，
vector可以把元素和rbegin(反向)進行交換再pop_back()，擦除
照樣是常數時間，還更快取友好，大概率比list快，
如果你去看memcache/linux的slab搞法，
就會發現它其實介于線性陣列和鏈表之間，兼顧了正確性和效率，
鏈表描述:
記憶體中內部的存盤方式,通常情況下可以認為是多個節點存盤一串的的結構
鏈表存盤結構
資料域 Data field
指標域 pointer field
強調: 指標域 一般指向下一個節點的地址 , 或者也可以認為是下一個節點的的參考(參考可以指向任意的物件)
指標域實作→ c 記憶體中的地址 ,地址唯一標記節點的位置 存的是陣列下標 → 存盤的是相對的地址的概念 下一個節點,也有存盤參考
只要相關結構中增加了一項指標域,結構就可以串成鏈表的結構
鏈表特點:
重點: 正常的鏈表的LastIndex 是NULL
至少必須包含兩個部分: 資料和指標域
鏈表的每個節點,通過指標域的值,形成了一個線性結構
ps 由于是通過指標區串聯成的一串,所以只允許從前向后依次訪問節點. 不允許用下標.
(訪問速度)也就成了o(n )
—也正是鏈表是一種松散的結構,由于指標域存盤的是下一個參考,也就是說我只要改變了指標的指向. 就可以完成動態的插入或修改(我可以吧插入地址,修改成修改前的下一個記憶體地址)
插入和修改洗掉都是o(1)的..
并不適合快速查找.
鏈表的實作
指標版
struct linkListNode{ linkListNode(int data):data(data),next(NULL){}; int data; linkListNode *next; }; void impleLinkList_bystruct(){ void Data_struct::impleLinkList_bystruct(){ linkListNode *head=NULL; head=new linkListNode(1); head->next =new linkListNode(2); head->next->next = linkListNode(3); head->next->next->next =new linkListNode(4); LinkListNode *p=head; while (p!=NULL) { cout << p->next << e } cout << endl; }
陣列下標
add 函式的作用地址index 節點后 添加一個地址為p的節點,并在讓p節點中存盤val
int next[10]; int data[10]; void LinkListadd(int ind ,int p,int val){ next[ind]=p; data[p]=val; return ; } void impleLinkList_byarr(){ int head =3 ; data[3]=0; //頭節點是3 //3節點后添加5節點,存的是1 LinkListadd(3,5,1); //五節點添加2節點,存的是2 LinkListadd(5,2,2); //2節點添加的是7節點 ,存的是3 LinkListadd(2,7,3); // 第二個是下一個節點 ,最后一個是值 LinkListadd(7,9,100); //構造了鏈表 int p =head; while(p=!0){ cout << "->" <<data[p] << endl; p =next[p]; } return 0; }
順序表02
順序表是在記憶體中以資料的形式保存的線性表，指一組地址連續的存單元依次存盤資料元素的線性結構,
所以使得線性表的邏輯結構上相鄰的資料元素存盤在相鄰的物理存盤單元,即通過資料源物理存盤的相鄰關系來反應資料元素之間上的邏輯上的相鄰關系
與陣列的區別 陣列在變以前就就必須確定陣列的長度,一旦確認,大小不允許更改.
順序表: 動態開辟的陣列大小且可以動態擴容 存盤型別必須一致, 需要一段連續的地址空間存盤
資料結構
存盤結構定義
以下定義兩種資料結構 將int 替換為 ElemTye 當做型別傳入即可
/* c2-1.h 線性表的動態分配順序存盤結構 */ #define LIST_INIT_SIZE 10 /* 線性表存盤空間的初始分配量 */ #define LIST_INCREMENT 2 /* 線性表存盤空間的分配增量 */ typedef struct { ElemType *elem; /* 存盤空間基址 */ int length; /* 當前長度 */ int listsize; /* 當前分配的存盤容量(以sizeof(ElemType)為單位) */ }SqList;
typedef struct seqVector{ //需要連續的存盤空間 int *data;//連續的存盤空間的首地址 他是沒有空間的 只是一個指標變數 所需要單獨申請 int size ,length; //size為總長度 當前空間存在的個數 }seqVector; seqVector * init(int n){ //申請存結構變數空間 seqVector *v=(seqVector *)malloc(sizeof(seqVector)); //向記憶體申請空間并強轉型別 //動態申請空間 記憶體堆申請 雖然是函式內部 堆疊區為8mb 堆區不受8mb限制 *****和loc相關的- malloc 需要主動釋放 //free 釋放 需要接受地址 address v->data=https://www.cnblogs.com/yijieyufu/p/(int *) malloc(sizeof(int)* n); //動態申請記憶體區 主動申請空間傳遞給這個欄位 v->size=n; v->length=0; return v; //自此空間和欄位 init 完成 }
順序表:實作
#include<stdio.h> #include<stdlib.h> #include<unistd.h> #include<fcntl.h> #include<string.h> #include<pthread.h> #include<time.h> //結構定義 typedef struct seqVector{ //需要連續的存盤空間 int *data;//連續的存盤空間的首地址 他是沒有空間的 只是一個指標變數 所需要單獨申請 int size ,length; //size為總長度 當前空間存在的個數 }seqVector; //這個容量大小 為n的存盤空間 seqVector * init(int n){ //申請存結構變數空間 seqVector *v=(seqVector *)malloc(sizeof(seqVector)); //向記憶體申請空間并強轉型別 //動態申請空間 記憶體堆申請 雖然是函式內部 堆疊區為8mb 堆區不受8mb限制 *****和loc相關的- malloc 需要主動釋放 //free 釋放 需要接受地址 address v->data=https://www.cnblogs.com/yijieyufu/p/(int *) malloc(sizeof(int)* n); //動態申請記憶體區 主動申請空間傳遞給這個欄位 v->size=n; v->length=0; return v; //自此空間和欄位 init 完成 } //2 銷毀操作 釋放記憶體空間 void clear(seqVector *v){ if(v==NULL) return; free(v->data); free(v); //如果你只釋放v 只是釋放順序表 //如 你不按照先后順序不銷毀 //但是陣列還存在,而代碼無法訪問v-data了 //你整個記憶體泄漏了 記憶體實際是找不到了 os 也找不到 ,你也找不到 return ; } //3 插入 int insert(seqVector *v, int index,int value){ if(v==NULL){ //初始化失敗了 return 0; } if(index <0 || index > v->length){ return 0; } //這就是滿了 if(v->length==v->size){ return 0; } //先把index 空出來 向后移動 /* for(int i=index;i<=v->length;i++){ // v->data[i+1]=v->data[i];//這特么是覆寫了 全覆寫成了當前index 的值了 } */ //移動一定要從后往前 for(int i=v->length;i>index;i--){ //由于他是大于index的 所以我減一是能訪到插入點的索引的 v->data[i]=v->data[i-1];//這才是后移動 } v->data[index]=value; v->length+=1; return 1; } int erase(seqVector *v,int index){ if(v==NULL) return 0; if(index < 0 || index>=v->length)return 0 ; for(int i=index +1 ;i< v->length;i++){ v->data[i-1]=v->data[i]; //從前向后移動 } v->length-=1; return 1; } //結構操作 // 操作步驟 // 1 : 初始化 生成一個順序表 // 2 : 銷毀 // 3 : 插入 // 4: 洗掉 // 查詢 int main() { srand(time(0)); #define MAX_OP 20 //必須初始化隨機種子 seqVector *sq =init(MAX_OP); for(int i=0;i<MAX_OP;i++){ int operators=rand()%2; //要么0 要1 int value=https://www.cnblogs.com/yijieyufu/p/rand()%100; int index =rand()%(sq->length+1); switch(operators){ case 0:{ printf("inert %d at %d to vector%d\n",value,index,insert(sq,index,value)); } break; case 1:{ printf("delete %d at %d form vector ",index,erase(sq,index)); } } } return 0; }
核心操作動態擴容陣列上界
int expand(seqVector *v){ //三種動態申請空間 //malloc ->只是申請空間 不能確定是否初始化 //calloc ->他可以直接初始化 主動清空為0值 //realloc ->重新分配記憶體 v->data=https://www.cnblogs.com/yijieyufu/p/(int *)realloc(v->data ,sizeof(int)* (v->size *2)); v->size *=2; // *=2; return 1; }
當前如果申請擴容陣列的方法 一旦強轉出現問題 則整個資料地址都會為NULL , 會造成代碼無法對資料區域進行訪問,則整個記憶體無法唄os 回收,記憶體出現泄漏.
最好不要在原來的記憶體空間上直接操作,我們需要將開辟回傳后的值賦值給新的變數
seqList 的理解,我們希望在add方法在像末尾取add元素占用常數時間 . 因此增加n個元素應該是線性的.
.net 中以 線性表實作的 List 就是非常典型的特點 ,不適合remove 等操作 ,但訪問元素的速度非常快.
但是也正是鏈表是一種松散的結構,由于指標域存盤的是下一個參考,也就是說我只要改變了指標的指向. 就可以完成動態的插入或修改(我可以吧插入地址,修改成修改前的下一個記憶體地址)
插入和修改洗掉都是o(1)的..
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/539928.html
標籤：其他
上一篇：基于知識圖譜的多模內容創作技術