鏈表描述:
記憶體中內部的存盤方式,通常情況下可以認為是多個節點存盤一串的的結構
鏈表存盤結構
資料域 Data field
指標域 pointer field
強調: 指標域 一般指向下一個節點的地址 , 或者也可以認為是下一個節點的的參考(參考可以指向任意的物件)
指標域實作→ c 記憶體中的地址 ,地址唯一標記節點的位置
存的是陣列下標 → 存盤的是相對的地址的概念
下一個節點,也有存盤參考
完結: 只要相關結構中增加了一項指標域,結構就可以串成鏈表的結構
鏈表特點:
至少必須包含兩個部分: 資料和指標域
鏈表的每個節點,通過指標域的值,形成了一個線性結構
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; }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/536119.html
標籤：其他