當(dāng)前位置:首頁 > 芯聞號 > 充電吧
[導(dǎo)讀]1、線性表的定義---- 通常,定義線性表為n(n>=0)個數(shù)據(jù)元素(或稱為表元)的有限序列。記為L=(a1,a2,...,an). 其中L是表名,ai是表中的結(jié)點(diǎn),是不可再分割的數(shù)據(jù)。n是表中

1、線性表的定義

---- 通常,定義線性表為n(n>=0)個數(shù)據(jù)元素(或稱為表元)的有限序列。記為L=(a1,a2,...,an). 其中L是表名,ai是表中的結(jié)點(diǎn),

是不可再分割的數(shù)據(jù)。n是表中表元的個數(shù),也稱為表的長度,若n=0叫做空表。

---- 在非空的數(shù)據(jù)元素集合中,線性表的特點(diǎn)是:

--- ?1)存在唯一的一個稱作“第一個”的元素。

--- ?2)存在唯一的一個稱作“最后一個”的元素。

--- ?3)除第一個元素外,集合中的每個元素均只有一個直接前驅(qū)。

--- ?4)除最后一個元素外,集合中的每個元素均只有一個直接后繼。

其中3)4)兩個特點(diǎn)體現(xiàn)了線性表中元素之間的邏輯關(guān)系。

理解線性表的要點(diǎn):

--- 表中元素具有邏輯上的順序性,在序列中各元素排列有其先后次序。

--- 表中元素個數(shù)有限。

--- 表中元素都是數(shù)據(jù)元素。即每一個表元素都是不可再分的原子數(shù)據(jù)。

--- 表中元素的數(shù)據(jù)類型都相同。即每一個表元素占有相同數(shù)量的存儲空間。

--- 表中元素具有抽象性。僅討論表元素之間的邏輯關(guān)系,不考慮元素究竟表示什么內(nèi)容。

2、線性表的操作

---- 線性表的主要操作有:

--- ?1)表的初始化運(yùn)算:將線性表置為空表。

--- ?2)求表長度運(yùn)算:統(tǒng)計線性表中表元素個數(shù)。

--- ?3)查找運(yùn)算:查找線性表中第i個表元素或查找表中具有給定關(guān)鍵字值的表元素。

--- ?4)插入運(yùn)算:將新表元素插入到線性表第i個位置上,或插入到具有給定關(guān)鍵字值的表元素的前面或后面。

--- ?5)刪除運(yùn)算:刪除線性表第i個表元素或具有給定關(guān)鍵字值的表元素。

--- ?6)讀?。ㄔL問)運(yùn)算:讀取線性表第i個表元素的值。

--- ?7)復(fù)制運(yùn)算:復(fù)制線性表所有表元素到另一個線性表中。

3、線性表的實(shí)現(xiàn)

3.1、線性表的順序存儲

------ 線性表的順序存儲又稱為順序表。它用一組地址連續(xù)的存儲單元依次存儲線性表中的數(shù)據(jù)元素,從而使得邏輯關(guān)系相鄰的兩個

元素在物理位置上也相鄰。因此順序表的特點(diǎn)是表中各元素的邏輯順序與其物理順序相同。

------ 順序表的靜態(tài)存儲分配


#define?MaxSize?100?????????//顯式的定義表的最大容量
typedef?int?ElemType;???????//定義表元素的數(shù)據(jù)類型
typedef?struct?{????????????//順序表的定義
	ElemType?data[MaxSize];?//靜態(tài)分配存儲表元素的數(shù)組
	int?n;??????????????????//實(shí)際表元素個數(shù),0<=n<=MaxSize
}Sqlist;

在這種存儲方式下,表元素ai存儲在data[i-1]位置,存儲結(jié)構(gòu)如下圖:

假設(shè)順序表A的起始存儲位置為Loc(1),第i個表項(xiàng)的存儲位置為Loc(i),則有:Loc(i)=Loc(1)+(i-1) x sizeof(ElemType)

其中,Loc(1)是第一個表項(xiàng)的存儲位置,即數(shù)組中第0個元素位置。sizeof(ElemType)是表中每個元素所占空間的大小。根據(jù)這個計算

關(guān)系,可隨機(jī)存取表中的任一個元素。一維數(shù)組可以是靜態(tài)分配的,也可以是動態(tài)分配的。

----- ?在靜態(tài)分配存儲的情形下,由于數(shù)組的大小和空間事先已經(jīng)固定分配,一旦數(shù)據(jù)空間占滿,再加入新的數(shù)據(jù)就將產(chǎn)生溢出,此時

存儲空間不能擴(kuò)充,就會導(dǎo)致程序停止工作。

----- ?在動態(tài)分配存儲的情形下,存儲數(shù)組的空間是在程序執(zhí)行過程中通過動態(tài)存儲分配的語句分配的,一旦數(shù)據(jù)空間占滿,可以另外

再分配一塊更大的存儲空間,用以代換原來的存儲空間,從而達(dá)到擴(kuò)充存儲數(shù)組空間的目的,同時需將表示數(shù)組大小的常量maxSize

放在順序表的結(jié)構(gòu)內(nèi)定義,可以動態(tài)地記錄擴(kuò)充后數(shù)組空間的大小,提高結(jié)構(gòu)的靈活性。

------ 順序表的動態(tài)存儲分配


#define?InitSize?100		//表長度的初始定義
typedef?int?ElemType;		//定義表元素的數(shù)據(jù)類型
typedef?struct?{		//順序表的定義
	ElemType?*data;		//指示動態(tài)分配數(shù)組的指針
	int?maxSize,n;		//數(shù)據(jù)的最大容量和當(dāng)前表元素的個數(shù)
}Seqlist;
//初始的動態(tài)分配語句為
data?=?(ElemType?*)malloc(sizeof(ElemType)*InitSize);
//C++?data=new?ElemType[InitSize];
maxSize?=?InitSize;n=0;

3.2、線性表的鏈?zhǔn)酱鎯?/p>

------ ?線性表的鏈?zhǔn)酱鎯τ址Q為線性鏈表。在這種結(jié)構(gòu)中數(shù)據(jù)元素存儲在結(jié)點(diǎn)中,結(jié)點(diǎn)之間在空間上可以連續(xù),也可以不連續(xù),通過

結(jié)點(diǎn)內(nèi)附的鏈接指針來表示元素之間的邏輯關(guān)系。因此在線性鏈表中邏輯上相鄰的表元素在物理上不一定相鄰。

以前在順序結(jié)構(gòu)中,每個數(shù)據(jù)元素只需要存數(shù)據(jù)元素信息就可以了,現(xiàn)在鏈?zhǔn)浇Y(jié)構(gòu)中,除了要存數(shù)據(jù)元素信息外,還要存儲它的后繼

元素的存儲地址。因此,為了表示每個數(shù)據(jù)元素ai與其直接后繼數(shù)據(jù)元素a(i+1)之間的邏輯關(guān)系,對數(shù)據(jù)元素ai來說,除了存儲其本身

的信息之外,還需存儲一個指示其直接后繼的信息(即直接后繼的存儲地址/位置)。

------ ?存儲數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域,存儲直接后繼位置的域稱為指針域。指針域中存儲的信息稱做指針或鏈。這兩部分信息組成

數(shù)據(jù)元素ai的存儲映像,稱為結(jié)點(diǎn)(Node)。n個結(jié)點(diǎn)鏈接成一個鏈表,即為線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。

最簡單的線性鏈表是單鏈表(鏈表的每個結(jié)點(diǎn)中只包含一個指針域),用C語言描述如下:

typedef?int?ElemType;		//定義表元素的數(shù)據(jù)類型
typedef?struct?node?{		
	ElemType?data;
	struct?node?*next;
}Node,*LinkList;

此時,使用一個指向鏈表結(jié)點(diǎn)的指針head標(biāo)識鏈表的表頭:

Node?*head;LinkList?head;

為了表示鏈表收尾,鏈表最后一個結(jié)點(diǎn)的鏈接指針應(yīng)置為空。

4、其他線性鏈表的形式

---- 根據(jù)結(jié)點(diǎn)中指針信息的實(shí)現(xiàn)方式,還有其他幾種鏈表結(jié)構(gòu):

--- ?1)雙向鏈表:每個結(jié)點(diǎn)包含兩個指針,指明直接前驅(qū)和直接后繼元素,可在兩個方向上遍歷其后及其前的元素。

--- ?2)循環(huán)鏈表:表尾結(jié)點(diǎn)的后繼指針指向表中的第一個結(jié)點(diǎn),可在任何位置上遍歷整個鏈表。

--- ?3)靜態(tài)鏈表:借助數(shù)組來描述線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。(兩個數(shù)據(jù)域,一個存放數(shù)據(jù)元素,一個存儲該元素的后繼在數(shù)組中的下標(biāo))

在鏈?zhǔn)酱鎯Y(jié)構(gòu)中,只需要一個指針(頭指針)指向第一個結(jié)點(diǎn),就可以順序訪問到表中的任意一個元素。為了簡化對鏈表狀態(tài)的判定

和處理,特別引入一個不存儲數(shù)據(jù)元素的結(jié)點(diǎn),稱為頭結(jié)點(diǎn),將其作為鏈表的第一個結(jié)點(diǎn)并令頭指針指向該結(jié)點(diǎn)。

頭結(jié)點(diǎn)的數(shù)據(jù)域可以不存儲任何信息,也可以存儲如線性表長度等類的附加信息,頭結(jié)點(diǎn)的指針域存儲指向第一個結(jié)點(diǎn)的指針(即第一個

元素結(jié)點(diǎn)的存儲位置)。此時,單鏈表的頭指針指向頭結(jié)點(diǎn)。如下圖所示:




本站聲明: 本文章由作者或相關(guān)機(jī)構(gòu)授權(quán)發(fā)布,目的在于傳遞更多信息,并不代表本站贊同其觀點(diǎn),本站亦不保證或承諾內(nèi)容真實(shí)性等。需要轉(zhuǎn)載請聯(lián)系該專欄作者,如若文章內(nèi)容侵犯您的權(quán)益,請及時聯(lián)系本站刪除。
換一批
延伸閱讀

9月2日消息,不造車的華為或?qū)⒋呱龈蟮莫?dú)角獸公司,隨著阿維塔和賽力斯的入局,華為引望愈發(fā)顯得引人矚目。

關(guān)鍵字: 阿維塔 塞力斯 華為

加利福尼亞州圣克拉拉縣2024年8月30日 /美通社/ -- 數(shù)字化轉(zhuǎn)型技術(shù)解決方案公司Trianz今天宣布,該公司與Amazon Web Services (AWS)簽訂了...

關(guān)鍵字: AWS AN BSP 數(shù)字化

倫敦2024年8月29日 /美通社/ -- 英國汽車技術(shù)公司SODA.Auto推出其旗艦產(chǎn)品SODA V,這是全球首款涵蓋汽車工程師從創(chuàng)意到認(rèn)證的所有需求的工具,可用于創(chuàng)建軟件定義汽車。 SODA V工具的開發(fā)耗時1.5...

關(guān)鍵字: 汽車 人工智能 智能驅(qū)動 BSP

北京2024年8月28日 /美通社/ -- 越來越多用戶希望企業(yè)業(yè)務(wù)能7×24不間斷運(yùn)行,同時企業(yè)卻面臨越來越多業(yè)務(wù)中斷的風(fēng)險,如企業(yè)系統(tǒng)復(fù)雜性的增加,頻繁的功能更新和發(fā)布等。如何確保業(yè)務(wù)連續(xù)性,提升韌性,成...

關(guān)鍵字: 亞馬遜 解密 控制平面 BSP

8月30日消息,據(jù)媒體報道,騰訊和網(wǎng)易近期正在縮減他們對日本游戲市場的投資。

關(guān)鍵字: 騰訊 編碼器 CPU

8月28日消息,今天上午,2024中國國際大數(shù)據(jù)產(chǎn)業(yè)博覽會開幕式在貴陽舉行,華為董事、質(zhì)量流程IT總裁陶景文發(fā)表了演講。

關(guān)鍵字: 華為 12nm EDA 半導(dǎo)體

8月28日消息,在2024中國國際大數(shù)據(jù)產(chǎn)業(yè)博覽會上,華為常務(wù)董事、華為云CEO張平安發(fā)表演講稱,數(shù)字世界的話語權(quán)最終是由生態(tài)的繁榮決定的。

關(guān)鍵字: 華為 12nm 手機(jī) 衛(wèi)星通信

要點(diǎn): 有效應(yīng)對環(huán)境變化,經(jīng)營業(yè)績穩(wěn)中有升 落實(shí)提質(zhì)增效舉措,毛利潤率延續(xù)升勢 戰(zhàn)略布局成效顯著,戰(zhàn)新業(yè)務(wù)引領(lǐng)增長 以科技創(chuàng)新為引領(lǐng),提升企業(yè)核心競爭力 堅(jiān)持高質(zhì)量發(fā)展策略,塑強(qiáng)核心競爭優(yōu)勢...

關(guān)鍵字: 通信 BSP 電信運(yùn)營商 數(shù)字經(jīng)濟(jì)

北京2024年8月27日 /美通社/ -- 8月21日,由中央廣播電視總臺與中國電影電視技術(shù)學(xué)會聯(lián)合牽頭組建的NVI技術(shù)創(chuàng)新聯(lián)盟在BIRTV2024超高清全產(chǎn)業(yè)鏈發(fā)展研討會上宣布正式成立。 活動現(xiàn)場 NVI技術(shù)創(chuàng)新聯(lián)...

關(guān)鍵字: VI 傳輸協(xié)議 音頻 BSP

北京2024年8月27日 /美通社/ -- 在8月23日舉辦的2024年長三角生態(tài)綠色一體化發(fā)展示范區(qū)聯(lián)合招商會上,軟通動力信息技術(shù)(集團(tuán))股份有限公司(以下簡稱"軟通動力")與長三角投資(上海)有限...

關(guān)鍵字: BSP 信息技術(shù)
關(guān)閉
關(guān)閉