2020-06-11數(shù)據(jù)結(jié)構(gòu) -- 第二章*線性表

線性結(jié)構(gòu)的基本特點(diǎn)是除第一個(gè)元素?zé)o直接前驅(qū)，最后一個(gè)元素?zé)o直接后繼之外，其他每個(gè)元素都有一個(gè)前驅(qū)和后繼。

2.1線性表(Linear List)的定義和特點(diǎn)：

定義：由n（n>=0）個(gè)數(shù)據(jù)特性相同的元素構(gòu)成的有限序列稱為線性表，n=0時(shí)稱為空表痴奏。

? ? ? ? 實(shí)例： $a_{1} ,a_{2} ,a_{3} ......a_{n}$

特點(diǎn)：

線性表特點(diǎn)

$a_{1}$ 稱為線性表的首節(jié)點(diǎn)， $a_{n}$ 稱為線性表的尾節(jié)點(diǎn)

$a_{1} ,a_{2} ...a_{i-1}$ 都是 $a_{i}$ 的前驅(qū)厌秒，其中 $a_{i-1}$ 是 $a_{i}$ 的直接前驅(qū)读拆；

$a_{i+1}，a_{i+2}...a_{n}$ 都是 $a_{i}$ 的后繼简僧，其中 $a_{i+1}$ 是 $a_{i}$ 的直接后繼建椰；

2.2線性表的邏輯結(jié)構(gòu)

線性表結(jié)點(diǎn)可以是單值元素

線性表節(jié)點(diǎn)可以是記錄行元素雕欺，關(guān)鍵字

2.3線性表的抽象數(shù)據(jù)類型定義

ADT List{

? ? ? ? 數(shù)據(jù)對(duì)象：D = { $a_{i}$ |? $a_{i} \in ElemSet,i = 1,2,....,n,n\geq 0$ }

? ? ? ? 數(shù)據(jù)關(guān)系：R = { $<a_{i-1},a_{i} >|a_{i-1},a_{i}\in D,i=2,...,n$ }

? ? ? ? 基本操作：

? ? ? ? ? ? ? ? 操作名1：

? ? ? ? ? ? ? ? ? ? ? ? 初始條件

? ? ? ? ? ? ? ? ? ? ? ? 操作結(jié)果1

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? .

? ??????????????????????????????.

}ADT List

2.4線性表的順序存儲(chǔ)和實(shí)現(xiàn)

順序存儲(chǔ)：把線性表的節(jié)點(diǎn)按邏輯順序依次存放在一組地址連續(xù)的存儲(chǔ)單元里岛马，用這種方法存儲(chǔ)的線性表簡(jiǎn)稱順序表棉姐。

特點(diǎn)：

? ? ? ? 線性表的邏輯順序與物理順序一致

? ? ? ? 數(shù)據(jù)元素之間的關(guān)系是以元素在計(jì)算機(jī)內(nèi)“物理位置相鄰”來(lái)體現(xiàn)。

線性表的順序存儲(chǔ)

第i-1個(gè)數(shù)據(jù)元素存儲(chǔ)地址為（i-1）*/存儲(chǔ)單元+LOC（a1）

順序表的基本操作：

? ? ? ? C語(yǔ)言定義結(jié)構(gòu)體

宏定義和結(jié)構(gòu)體定義

? ? ? ? 1）順序線性表初始化

表示給elem_array動(dòng)態(tài)分配指針啦逆，如果沒(méi)有分配到指針?lè)祷谽RROR否認(rèn)返回OK

? ? ? ? 2）順序線性表的插入

算法分析

C語(yǔ)言算法實(shí)現(xiàn)

js代碼實(shí)現(xiàn)順序線性表的插入：

js代碼實(shí)現(xiàn)線性表的插入算法操作

? ? ? ? 3）順序線性表的刪除

算法分析和C代碼實(shí)現(xiàn)一部分

C代碼實(shí)現(xiàn)剩余部分

js代碼實(shí)現(xiàn)順序線性表的刪除

js代碼實(shí)現(xiàn)順序線性表的刪除

2.5線性表的鏈?zhǔn)酱鎯?chǔ)

鏈?zhǔn)酱鎯?chǔ)：用一組任意的存儲(chǔ)單元存儲(chǔ)線性表中的數(shù)據(jù)元素伞矩，用這種方法存儲(chǔ)的線性表簡(jiǎn)稱線性鏈表。

????????存儲(chǔ)鏈表中節(jié)點(diǎn)的一組任意存儲(chǔ)單元可以是連續(xù)的夏志，也可以是不連續(xù)的乃坤，甚至零散分布至內(nèi)存的任意位置上

????????鏈表中節(jié)點(diǎn)的邏輯順序和物理順序不一定相同。

為了正確表示結(jié)點(diǎn)間的邏輯關(guān)系沟蔑，在存儲(chǔ)每個(gè)結(jié)點(diǎn)值的同時(shí)湿诊，還必須存儲(chǔ)指示其直接后繼節(jié)點(diǎn)的地址，C中稱為指針瘦材，節(jié)點(diǎn)值（數(shù)據(jù)域）和地址（指針）兩者組成鏈表中的結(jié)點(diǎn)結(jié)構(gòu)厅须。

鏈表結(jié)點(diǎn)結(jié)構(gòu)

????????鏈表通過(guò)每個(gè)結(jié)點(diǎn)的地址將線性表的n個(gè)結(jié)點(diǎn)按其邏輯順序連接在一起。

????????每一個(gè)結(jié)點(diǎn)只包含一個(gè)地址域的鏈表稱為單鏈表食棕。

????????為操作方便朗和，總是在鏈表的第一個(gè)結(jié)點(diǎn)之前附設(shè)一個(gè)頭節(jié)點(diǎn)head指向第一個(gè)結(jié)點(diǎn)，頭節(jié)點(diǎn)的數(shù)據(jù)域可以不存儲(chǔ)任何信息（或鏈表長(zhǎng)度信息）簿晓。

下圖可以看出鏈表中節(jié)點(diǎn)的邏輯順序和物理順序不一定相同眶拉。

單鏈表示例

單鏈表的邏輯狀態(tài)

結(jié)點(diǎn)的描述與實(shí)現(xiàn)

C語(yǔ)言中，用帶指針的結(jié)構(gòu)體來(lái)描述

typedef struct Lnode{

????ElemType data憔儿；//數(shù)據(jù)域忆植，保存結(jié)點(diǎn)的值

????struct Lnode *next;//指針域

}LNode;? //結(jié)點(diǎn)的類型

結(jié)點(diǎn)的實(shí)現(xiàn)：

結(jié)點(diǎn)是通過(guò)動(dòng)態(tài)分配指針和釋放來(lái)實(shí)現(xiàn)，即需要時(shí)分配皿曲，不需要時(shí)釋放唱逢。是現(xiàn)實(shí)是分別使用C語(yǔ)言提供的標(biāo)準(zhǔn)函數(shù)：malloc(),realloc(),sizeof(),free()。

動(dòng)態(tài)分配：

p = (LNode*)malloc(sizeof(LNode));

函數(shù)malloc分配了一個(gè)類型為L(zhǎng)Node的結(jié)點(diǎn)變量的空間屋休，并將其首地址放如指針變量p中坞古。

動(dòng)態(tài)釋放：free（p）

系統(tǒng)回收由指針變量p所指向的內(nèi)存區(qū)，p必須是最近一次調(diào)用malloc函數(shù)時(shí)的返回值劫樟。

最常見(jiàn)的基本操作及其示意圖

結(jié)點(diǎn)的賦值

常見(jiàn)指針操作（1）

常見(jiàn)指針操作(2)

2.6單線性鏈表的基本操作

單項(xiàng)現(xiàn)象鏈表的基本操作

????//設(shè)計(jì)一個(gè)基于對(duì)象的鏈表

????//創(chuàng)建鏈表Node類

????function?Node(element){

????????this.element?=?element;

????????this.next?=?null;

????}

????//創(chuàng)建鏈表/增刪改查

????function?LinkedList(){

????????this.head?=?new?Node('head');//創(chuàng)建頭結(jié)點(diǎn)

????????this.find?=?find;?//查找結(jié)點(diǎn)

????????this.insert?=?insert;//插入結(jié)點(diǎn)

????????this.findPrev?=?findPrev;//找到某結(jié)點(diǎn)的前一結(jié)點(diǎn)

????????this.remove?=?remove;//刪除結(jié)點(diǎn)

????????this.display?=?display;//顯示鏈表元素

????????//查找對(duì)應(yīng)item的結(jié)點(diǎn)并返回

????????function?find(item){

????????????var?currentNode?=?this.head;//從頭節(jié)點(diǎn)開(kāi)始搜索

????????????//循環(huán)遍歷痪枫，直至找到item結(jié)束

????????????while(currentNode.element!=item){

????????????????currentNode?=?currentNode.next;

????????????}

????????????//返回item的結(jié)點(diǎn)

????????????return?currentNode;

????????}

????????//在item后插入新元素

????????function?insert(newElement,item){

????????????var?newNode?=?new?Node(newElement);//定義新元素結(jié)點(diǎn)

????????????var?current?=?this.find(item);//從鏈表中找到item結(jié)點(diǎn)

????????????newNode.next?=?current.currentNode;//將item元素的結(jié)點(diǎn)后繼賦值給新元素結(jié)點(diǎn)的后繼

????????????current.next?=?newNode;//item元素的后繼插入新元素

????????}

????????//顯示鏈表

????????function?display(){

????????????var?currentNode?=?this.head;

????????????while(!(currentNode.next==null)){

????????????????console.log(currentNode.next.element);

????????????????currentNode?=?currentNode.next;

????????????}

????????}

????????//刪除鏈表的item結(jié)點(diǎn)元素

????????//1.找到item結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)

????????function?findPrev(item){

????????????var?currentNode?=?this.head;//定義待刪除結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)

????????????/*

????????????算法分析：

????????????循環(huán)遍歷currentNode的下一個(gè)結(jié)點(diǎn)，如果找到對(duì)應(yīng)等于item的currentNode.next.element,

????????????while循環(huán)結(jié)束返回當(dāng)前的currentNode叠艳，即待刪除元素的前一個(gè)結(jié)點(diǎn)

????????????*/

????????????while(!(currentNode.next==null)?&&?currentNode.next.element!=item){

???????????????currentNode?=?currentNode.next;

????????????}

????????????return?currentNode;

????????}

????????//2.刪除item階段元素

????????function?remove(item){

????????????var?prevNode?=?this.findPrev(item);//找到待刪除結(jié)點(diǎn)的前一結(jié)點(diǎn)

????????????if(!(prevNode.next==null)){

????????????????prevNode.next?=?prevNode.next.next;

????????????}

????????}

????}

????//測(cè)試程序

????var?cities?=?new?LinkedList();

????cities.insert('北京','head');

????cities.insert('上海','北京');

????cities.insert('廣州','上海');

????cities.insert('天津','廣州');

????cities.display();//北京?上海?廣州?天津

????cities.remove('北京');

????cities.display();//上海?廣州?天津

????console.log(cities.find('上海').next)//Node?{element:?"廣州",?next:?Node}

????console.log(cities.find('天津').next);//undefined

</script>

雙向鏈表的基本操作

????//設(shè)計(jì)一個(gè)基于對(duì)象的雙向鏈表

????//創(chuàng)建鏈表Node類

????function?Node(element){

????????//data數(shù)據(jù)

????????this.element?=?element;

????????//后繼地址

????????this.next?=?null;

????????//前驅(qū)地址

????????this.previous?=?null;

????}

????//創(chuàng)建鏈表/增刪改查

????function?LinkedList(){

????????this.head?=?new?Node('head');//創(chuàng)建頭結(jié)點(diǎn)

????????this.find?=?find;?//查找當(dāng)前結(jié)點(diǎn)

????????this.insert?=?insert;//插入結(jié)點(diǎn)

????????this.findPrevious?=?findPrevious;//找到某結(jié)點(diǎn)的前一結(jié)點(diǎn)

????????this.remove?=?remove;//刪除結(jié)點(diǎn)

????????this.display?=?display;//顯示鏈表元素

????????this.findLast?=?findLast;//查找鏈表最后一個(gè)元素

????????this.dispReverse?=?dispReverse;//反向顯示

????????//查找對(duì)應(yīng)item的結(jié)點(diǎn)并返回

????????function?find(item){

????????????var?currentNode?=?this.head;//從頭節(jié)點(diǎn)開(kāi)始搜索

????????????//循環(huán)遍歷奶陈，直至找到item結(jié)束

????????????while(currentNode.element!=item){

????????????????currentNode?=?currentNode.next;

????????????}

????????????//返回item的結(jié)點(diǎn)

????????????return?currentNode;

????????}

????????//在item后插入新元素

????????function?insert(newElement,item){

????????????var?newNode?=?new?Node(newElement);//定義新元素結(jié)點(diǎn)

????????????var?current?=?this.find(item);//從鏈表中找到item結(jié)點(diǎn)

????????????newNode.next?=?current.currentNode;//將item元素的結(jié)點(diǎn)后繼賦值給新元素結(jié)點(diǎn)的后繼

????????????newNode.previous?=?current;//將item元素賦值給新元素結(jié)點(diǎn)的前驅(qū)

????????????current.next?=?newNode;//item元素的后繼插入新元素

????????}

????????//顯示鏈表

????????function?display(){

????????????var?currentNode?=?this.head;

????????????while(!(currentNode.next==null)){

????????????????console.log(currentNode.next.element);

????????????????currentNode?=?currentNode.next;

????????????}

????????}

????????//刪除鏈表的item結(jié)點(diǎn)元素

????????//1.找到item結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)

????????function?findPrevious(item){

????????????var?currentNode?=?this.head;//定義待刪除結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)

????????????/*

????????????算法分析：

????????????循環(huán)遍歷currentNode的下一個(gè)結(jié)點(diǎn)，如果找到對(duì)應(yīng)等于item的currentNode.next.element,

????????????while循環(huán)結(jié)束返回當(dāng)前的currentNode附较，即待刪除元素的前一個(gè)結(jié)點(diǎn)

????????????*/

????????????while(!(currentNode.next==null)?&&?currentNode.next.element!=item){

???????????????currentNode?=?currentNode.next;

????????????}

????????????return?currentNode;

????????}

????????//2.刪除item階段元素

????????function?remove(item){

????????????var?currentNode?=?this.find(item);//找到當(dāng)前待刪除結(jié)點(diǎn)

????????????if(!(prevNode.next==null)){

????????????????currentNode.previous.next?=?currentNode.next;//前一個(gè)元素結(jié)點(diǎn)的的后繼指向當(dāng)前元素的下一個(gè)元素結(jié)點(diǎn)

????????????????currentNode.next.previous?=?currentNode.previous//后一個(gè)元素結(jié)點(diǎn)的前驅(qū)指向當(dāng)前元素的前一個(gè)元素結(jié)點(diǎn)

????????????????currentNode.next?=?null;//當(dāng)前結(jié)點(diǎn)后繼為空

????????????????currentNode.previous?=?null;//當(dāng)前結(jié)點(diǎn)前驅(qū)為空

????????????}

????????}

????????//雙向鏈表查找最后一個(gè)結(jié)點(diǎn)

????????function?findLast(){

????????????var?currentNode?=?this.head;//從頭節(jié)點(diǎn)開(kāi)始搜索

????????????//循環(huán)遍歷,直到地址為空

????????????while(!(currentNode.next==null)){

????????????????currentNode?=?currentNode.next;

????????????}

????????????//最后的結(jié)點(diǎn)

????????????return?currentNode;

????????}

????????//反序顯示雙向鏈表中的元素

????????function?dispReverse(){

????????????var?currentNode?=?this.findLast();

????????????while(!(currentNode.previous==null)){

????????????????console.log(currentNode.element);

????????????????currentNode?=?currentNode.previous;

????????????}

????????}

????}

????//測(cè)試程序

????var?cities?=?new?LinkedList();

????cities.insert('北京','head');

????cities.insert('上海','北京');

????cities.insert('廣州','上海');

????cities.insert('天津','廣州');

????cities.display();//北京?上海?廣州?天津

????cities.dispReverse();//天津?廣州?上海?北京

????console.log(cities.find('上海').next)//Node?{element:?"廣州",?next:?Node}

????console.log(cities.find('天津').next);//undefined

</script>

2.7循環(huán)鏈表

循環(huán)鏈表是一種頭尾相接的鏈表吃粒，其特點(diǎn)是最后一個(gè)結(jié)點(diǎn)的指針指向鏈表的頭節(jié)點(diǎn)，整個(gè)鏈表的指針域連接成一個(gè)環(huán)拒课。

從循環(huán)鏈表的任意一個(gè)結(jié)點(diǎn)出發(fā)，都可以找到鏈表中的其他結(jié)點(diǎn)。

最后編輯于：2020.06.11 15:36:27

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

禁止轉(zhuǎn)載揽涮，如需轉(zhuǎn)載請(qǐng)通過(guò)簡(jiǎn)信或評(píng)論聯(lián)系作者涕烧。

人面猴
序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌，老刑警劉巖劝堪，帶你破解...
沈念sama閱讀 206,214評(píng)論 6贊 481
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場(chǎng)離奇詭異揉稚，居然都是意外死亡秒啦，警方通過(guò)查閱死者的電腦和手機(jī)，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 88,307評(píng)論 2贊 382
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門搀玖，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)帝蒿，“玉大人，你說(shuō)我怎么就攤上這事巷怜「鸪” “怎么了？”我有些...
開(kāi)封第一講書人閱讀 152,543評(píng)論 0贊 341
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵延塑，是天一觀的道長(zhǎng)绣张。經(jīng)常有香客問(wèn)我，道長(zhǎng)关带，這世上最難降的妖魔是什么侥涵？我笑而不...
開(kāi)封第一講書人閱讀 55,221評(píng)論 1贊 279
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮宋雏，結(jié)果婚禮上芜飘，老公的妹妹穿的比我還像新娘。我一直安慰自己磨总，他們只是感情好嗦明，可當(dāng)我...
茶點(diǎn)故事閱讀 64,224評(píng)論 5贊 371
惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
文/花漫我一把揭開(kāi)白布。她就那樣靜靜地躺著蚪燕，像睡著了一般娶牌。火紅的嫁衣襯著肌膚如雪。梳的紋絲不亂的頭發(fā)上馆纳，一...
開(kāi)封第一講書人閱讀 49,007評(píng)論 1贊 284
城市分裂傳說(shuō)
那天诗良，我揣著相機(jī)與錄音，去河邊找鬼鲁驶。笑死鉴裹，一個(gè)胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播径荔，決...
沈念sama閱讀 38,313評(píng)論 3贊 399
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開(kāi)眼葛作，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼！你這毒婦竟也來(lái)了猖凛？” 一聲冷哼從身側(cè)響起，我...
開(kāi)封第一講書人閱讀 36,956評(píng)論 0贊 259
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤绪穆，失蹤者是張志新（化名）和其女友劉穎辨泳，沒(méi)想到半個(gè)月后，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體玖院，經(jīng)...
沈念sama閱讀 43,441評(píng)論 1贊 300
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡菠红，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 35,925評(píng)論 2贊 323
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了难菌。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片试溯。...
茶點(diǎn)故事閱讀 38,018評(píng)論 1贊 333
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡，死狀恐怖郊酒，靈堂內(nèi)的尸體忽然破棺而出遇绞，到底是詐尸還是另有隱情，我是刑警寧澤燎窘，帶...
沈念sama閱讀 33,685評(píng)論 4贊 322
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布摹闽，位于F島的核電站，受9級(jí)特大地震影響褐健，放射性物質(zhì)發(fā)生泄漏付鹿。R本人自食惡果不足惜，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 39,234評(píng)論 3贊 307
男人毒藥：我在死后第九天來(lái)索命
文/蒙蒙一蚜迅、第九天我趴在偏房一處隱蔽的房頂上張望舵匾。院中可真熱鬧，春花似錦谁不、人聲如沸坐梯。這莊子的主人今日做“春日...
開(kāi)封第一講書人閱讀 30,240評(píng)論 0贊 19
一樁弒父案刹帕，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)烛缔。三九已至，卻和暖如春轩拨，著一層夾襖步出監(jiān)牢的瞬間践瓷，已是汗流浹背。一陣腳步聲響...
開(kāi)封第一講書人閱讀 31,464評(píng)論 1贊 261
情欲美人皮
我被黑心中介騙來(lái)泰國(guó)打工亡蓉，沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留晕翠，地道東北人。一個(gè)月前我還...
沈念sama閱讀 45,467評(píng)論 2贊 352
代替公主和親
正文我出身青樓，卻偏偏與公主長(zhǎng)得像淋肾，于是被迫代替她去往敵國(guó)和親硫麻。傳聞我的和親對(duì)象是個(gè)殘疾皇子，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 42,762評(píng)論 2贊 345