前言
線性結(jié)構(gòu)的基本特點是除了第一個元素?zé)o直接前驅(qū),最后一個元素?zé)o直接后續(xù)之外,其他每個數(shù)據(jù)元素都有一個前驅(qū)和后繼. 線性表是最基本且最常用的一種線性結(jié)構(gòu),同時它也是其他的數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ). 尤其是單鏈表是貫穿于整個數(shù)據(jù)結(jié)構(gòu)課程的基本技術(shù)點.
一. 線性表的定義和特點
在我們生活中有那些線性表的例子了?
例如,26個字母表; 例如學(xué)生基本信息表.每個學(xué)生為一個數(shù)據(jù)元素,包含學(xué)號,姓名,專業(yè)等數(shù)據(jù)項目.
滿足數(shù)據(jù)元素不同,但是在同一個線性表中的元素必定具有相同的特點,即屬于同一數(shù)據(jù)對象, 相鄰數(shù)據(jù)元素之間存在這個序偶關(guān)系. 諸如此類由(n>=0)個數(shù)據(jù)特性相同的元素構(gòu)成的有限序列稱為"線性表".
線性表中的元素的個數(shù)n定義為線性表的長度,如果n = 0則稱為空表.
對于非空的線性表和線性結(jié)構(gòu),其特點如下:
存在唯一的一個被稱作"第一個"的數(shù)據(jù)元素
存在唯一的一個唄稱作"最后一個"的數(shù)據(jù)元素
除了第一個之外,結(jié)構(gòu)中的每個數(shù)據(jù)元素均有一個前驅(qū)
除了最后一個之外,結(jié)構(gòu)中的每個數(shù)據(jù)元素都有一個后繼.
1.2 線性表的類型定義
線性表是一個相當(dāng)靈活的數(shù)據(jù)結(jié)構(gòu),其長度可根據(jù)需要增長或縮短,即對線性表的數(shù)據(jù)元素不僅可以進行訪問,而且可以對其進行插入和刪除等操作.
線性表結(jié)構(gòu)體設(shè)計
1.線性表的順序存儲
2.線性表->單鏈表節(jié)點
數(shù)據(jù)域+指針域
3.線性表->單向循環(huán)鏈表
與單向鏈表區(qū)別之處在于單向鏈表的最后的結(jié)點的指針域 next 是設(shè)置為null. 但是單向循環(huán)鏈表最后一個結(jié)點是重新指向它的第一個首元結(jié)點的位置;
3.1單向鏈表的創(chuàng)建 (采用尾插法)
在實現(xiàn)單向鏈表的創(chuàng)建時,需要考慮.你進行創(chuàng)建新增結(jié)點時的2種情況
第一種情況: 第一次創(chuàng)建; 第二種情況: 鏈表已經(jīng)創(chuàng)建成功,并且已經(jīng)存儲了相應(yīng)的結(jié)點. 需要在鏈表的末尾繼續(xù)新增數(shù)據(jù);
3.2單向循環(huán)鏈表插入數(shù)據(jù)
在往一個單向循環(huán)鏈表中插入數(shù)據(jù),需要提前分析2種情況.
第一種情況,則是插入的位置在首元結(jié)點上;
判斷輸入的位置是否是place = 1;
創(chuàng)建新的結(jié)點temp,并且做出合理的健壯性判斷;以及賦值
將新創(chuàng)建的結(jié)點temp 的next 指向原始的首元結(jié)點A的位置
通過循環(huán)找到鏈表最后一個尾結(jié)點,將尾結(jié)點的next 指針域指向 新創(chuàng)建的結(jié)點temp.
由于鏈表的首元結(jié)點,通過插入發(fā)生了改變,所以此時將*L指向新的首元結(jié)點temp
第二種情況,插入其他位置(包括鏈表中間/末尾);
判斷輸入的位置是否是
place = 1;創(chuàng)建新的結(jié)點
temp,并且做出合理的健壯性判斷;以及賦值;通過循環(huán)找到待插入的位置前一個結(jié)點
p ;將新創(chuàng)建的結(jié)點
temp指向p->next;將待插入結(jié)點的前一個結(jié)點
P 與新結(jié)點 temp之間連接起來;
3.3單向循環(huán)鏈表的刪除
在實現(xiàn)單向鏈表的創(chuàng)建時,需要考慮.你進行創(chuàng)建新增結(jié)點時的3種情況
第一種情況: 刪除的位置在首元結(jié)點上;
第二種情況: 刪除時,當(dāng)鏈表只剩下最后一個結(jié)點時;
第三種情況: 刪除其他位置上的結(jié)點;
4.線性表->雙向鏈表
5.線性表->雙向鏈表
