3、顺序表、内存、类型、python中的list
1、內(nèi)存、類(lèi)型本質(zhì)、連續(xù)存儲(chǔ)
1、內(nèi)存本質(zhì)
2、C 語(yǔ)言實(shí)例-計(jì)算 int, float, double 和 char 字節(jié)大小
使用 sizeof 操作符計(jì)算int, float, double 和 char四種變量字節(jié)大小。
sizeof 是 C 語(yǔ)言的一種單目操作符，如C語(yǔ)言的其他操作符++、--等，它并不是函數(shù)。
sizeof 操作符以字節(jié)形式給出了其操作數(shù)的存儲(chǔ)大小。
#include <stdio.h>int main() {int integerType;float floatType;double doubleType;char charType;// sizeof 操作符用于計(jì)算變量的字節(jié)大小printf("Size of int: %ld bytes\n",sizeof(integerType));printf("Size of float: %ld bytes\n",sizeof(floatType));printf("Size of double: %ld bytes\n",sizeof(doubleType));printf("Size of char: %ld byte\n",sizeof(charType));return 0; }?
?
32 位的系統(tǒng)
存儲(chǔ)單元Size of int: 4 bytes Size of float: 4 bytes Size of double: 8 bytes Size of char: 1 byte3、連續(xù)存儲(chǔ)：一組相同類(lèi)型的數(shù)據(jù)
?
?2、順序表
這樣的一組序列元素的組織形式，我們可以將其抽象為線(xiàn)性表。一個(gè)線(xiàn)性表是某類(lèi)元素的一個(gè)集合，還記錄著元素之間的一種順序關(guān)系。線(xiàn)性表是最基本的數(shù)據(jù)結(jié)構(gòu)之一，在實(shí)際程序中應(yīng)用非常廣泛，它還經(jīng)常被用作更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)基礎(chǔ)。?
根據(jù)線(xiàn)性表的實(shí)際存儲(chǔ)方式，分為兩種實(shí)現(xiàn)模型：
- 順序表，將元素順序地存放在一塊連續(xù)的存儲(chǔ)區(qū)里，元素間的順序關(guān)系由它們的存儲(chǔ)順序自然表示。
- 鏈表，將元素存放在通過(guò)鏈接構(gòu)造起來(lái)的一系列存儲(chǔ)塊中。
?
3、順序表的基本形式
?
?（1）基本順序表
?? ?
圖a表示的是順序表的基本形式，數(shù)據(jù)元素本身連續(xù)存儲(chǔ)，每個(gè)元素所占的存儲(chǔ)單元大小固定相同，元素的下標(biāo)是其邏輯地址， 而元素存儲(chǔ)的物理地址（實(shí)際內(nèi)存地址）可以通過(guò)存儲(chǔ)區(qū)的起始地址Loc (e0)加上邏輯地址（第i個(gè)元素）與存儲(chǔ)單元大小（c）的乘積計(jì)算而得，即：Loc(ei) = Loc(e0) + c*i故，訪(fǎng)問(wèn)指定元素時(shí)無(wú)需從頭遍歷，通過(guò)計(jì)算便可獲得對(duì)應(yīng)地址，其時(shí)間復(fù)雜度為O(1)。?
?
?
（2）元素外圍順序表
如果元素的大小不統(tǒng)一，則須采用圖b的元素外置的形式，將實(shí)際數(shù)據(jù)元素另行存儲(chǔ)，而順序表中各單元位置保存對(duì)應(yīng)元素的地址信息（即鏈接）。由于每個(gè)鏈接所需的存儲(chǔ)量相同，通過(guò)上述公式，可以計(jì)算出元素鏈接的存儲(chǔ)位置，而后順著鏈接找到實(shí)際存儲(chǔ)的數(shù)據(jù)元素。
注意，圖b中的c不再是數(shù)據(jù)元素的大小，而是存儲(chǔ)一個(gè)鏈接地址所需的存儲(chǔ)量，這個(gè)量通常很小。圖b這樣的順序表也被稱(chēng)為對(duì)實(shí)際數(shù)據(jù)的索引，這是最簡(jiǎn)單的索引結(jié)構(gòu)。
?
4、順序表的結(jié)構(gòu)與實(shí)現(xiàn)
1、順序表的結(jié)構(gòu)
一個(gè)順序表的完整信息包括兩部分，一部分是表中的元素集合，另一部分是為實(shí)現(xiàn)正確操作而需記錄的信息，即有關(guān)表的整體情況的信息，
這部分信息主要包括元素存儲(chǔ)區(qū)的容量和當(dāng)前表中已有的元素個(gè)數(shù)兩項(xiàng)
?
2、順序表的兩種基本實(shí)現(xiàn)方式
?? ? ? ? ?
?
圖a為一體式結(jié)構(gòu)，存儲(chǔ)表信息的單元與元素存儲(chǔ)區(qū)以連續(xù)的方式安排在一塊存儲(chǔ)區(qū)里，兩部分?jǐn)?shù)據(jù)的整體形成一個(gè)完整的順序表對(duì)象。
一體式結(jié)構(gòu)整體性強(qiáng)，易于管理。但是由于數(shù)據(jù)元素存儲(chǔ)區(qū)域是表對(duì)象的一部分，順序表創(chuàng)建后，元素存儲(chǔ)區(qū)就固定了。
圖b為分離式結(jié)構(gòu)，表對(duì)象里只保存與整個(gè)表有關(guān)的信息（即容量和元素個(gè)數(shù)），實(shí)際數(shù)據(jù)元素存放在另一個(gè)獨(dú)立的元素存儲(chǔ)區(qū)里，通過(guò)鏈接與基本表對(duì)象關(guān)聯(lián)。
?
3、元素存儲(chǔ)區(qū)替換
一體式結(jié)構(gòu)由于順序表信息區(qū)與數(shù)據(jù)區(qū)連續(xù)存儲(chǔ)在一起，所以若想更換數(shù)據(jù)區(qū)，則只能整體搬遷，即整個(gè)順序表對(duì)象（指存儲(chǔ)順序表的結(jié)構(gòu)信息的區(qū)域）改變了。
分離式結(jié)構(gòu)若想更換數(shù)據(jù)區(qū)，只需將表信息區(qū)中的數(shù)據(jù)區(qū)鏈接地址更新即可，而該順序表對(duì)象不變。
# 多添加幾個(gè)數(shù)據(jù) 1、重新申請(qǐng)一塊空間，空白內(nèi)存 2、數(shù)據(jù)搬遷，釋放掉以前的3、Li指向新的內(nèi)存起始地址0X523
?? ? ? ??? ??
?
如果采用分離式‘’
4、元素存儲(chǔ)區(qū)擴(kuò)充：以空間換時(shí)間
采用分離式結(jié)構(gòu)的順序表，若將數(shù)據(jù)區(qū)更換為存儲(chǔ)空間更大的區(qū)域，則可以在不改變表對(duì)象的前提下對(duì)其數(shù)據(jù)存儲(chǔ)區(qū)進(jìn)行了擴(kuò)充，所有使用這個(gè)表的地方都不必修改。
只要程序的運(yùn)行環(huán)境（計(jì)算機(jī)系統(tǒng)）還有空閑存儲(chǔ)，這種表結(jié)構(gòu)就不會(huì)因?yàn)闈M(mǎn)了而導(dǎo)致操作無(wú)法進(jìn)行。
人們把采用這種技術(shù)實(shí)現(xiàn)的順序表稱(chēng)為動(dòng)態(tài)順序表，因?yàn)槠淙萘靠梢栽谑褂弥袆?dòng)態(tài)變化。
?
?
?5、python列表實(shí)現(xiàn)
? （1）順序表添加與刪除元素
a. 尾端加入元素，時(shí)間復(fù)雜度為O(1)b. 非保序的加入元素（不常見(jiàn)），時(shí)間復(fù)雜度為O(1)c. 保序的元素加入，時(shí)間復(fù)雜度為O(n)
?
?
a. 刪除表尾元素，時(shí)間復(fù)雜度為O(1)b. 非保序的元素刪除（不常見(jiàn)），時(shí)間復(fù)雜度為O(1)c. 保序的元素刪除，時(shí)間復(fù)雜度為O(n)
?
（2）python中的順序表
?
（3）list就是一種采用分離式技術(shù)實(shí)現(xiàn)的動(dòng)態(tài)順序表
?
刪除list表的復(fù)雜度是O(n)
?
轉(zhuǎn)載于:https://www.cnblogs.com/venicid/p/9384058.html
總結(jié)
以上是生活随笔為你收集整理的3、顺序表、内存、类型、python中的list的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： 切图工具优化的几点总结
- 下一篇： 如何把一个二维数组的地址赋给一个二维指针