線性表损话、鏈?zhǔn)酱鎯Y(jié)構(gòu)
線性表是相對于邏輯結(jié)構(gòu)侦啸，鏈?zhǔn)酱鎯Y(jié)構(gòu)是相對于物理存儲。即邏輯上是一個接一個丧枪，物理存儲上是隨機的光涂。
鏈?zhǔn)酱鎯Φ奶攸c
關(guān)鍵字
頭結(jié)點、尾結(jié)點拧烦、數(shù)據(jù)域忘闻、指針
特點
頭結(jié)點：數(shù)據(jù)域為空，指針指向第一個結(jié)點
尾結(jié)點：數(shù)據(jù)與不為空恋博，指針指向空
Java代碼實現(xiàn)
查詢
類結(jié)構(gòu)：
- MyLink
- SelectLinkList
- SelectLinkListTest
MyLink是用來構(gòu)造鏈?zhǔn)酱鎯ο蠓辍electLinkList用來查詢出指定位置的對象、SelectLinkListTest是測試
代碼實現(xiàn)
MyLink.java
public class MyLink {
/**
* 數(shù)據(jù)域
*/
private int data;
/**
* 所指向的下一個對象的地址
*/
private MyLink nextLink;
public MyLink() {
}
public MyLink(MyLink nextLink) {
this.nextLink = nextLink;
}
public MyLink(int data, MyLink nextLink) {
this.data = data;
this.nextLink = nextLink;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public MyLink getNextLink() {
return nextLink;
}
public void setNextLink(MyLink nextLink) {
this.nextLink = nextLink;
}
}
SelectLinkList.java
public class SelectLinkList {
/**
* 用來幫助循環(huán)構(gòu)建MyLink對象
*/
private MyLink[] links;
/**
* 假定傳入MyLink[10]交播，即要創(chuàng)建10個MyLink對象重虑。這10個對象中是不應(yīng)該包含頭節(jié)點的。
* 因為傳入的數(shù)組中秦士，所有位置都要包含數(shù)據(jù)缺厉；而MyLink的對象中頭節(jié)點的構(gòu)造方法是
* MyLink(MyLink nextLink)，所以在這里拿出來。
*/
private MyLink myLinkHeader = null;
/**
* 為了傳入自定義MyLink[]的長度
* @param links
*/
public SelectLinkList(MyLink[] links) {
this.links = links;
}
/**
* 循環(huán)構(gòu)建MyLink對象提针。
* @return
*/
public void createLink() {
//拿到長度命爬，知道構(gòu)造的節(jié)點是從哪里開始
int a = links.length;
//鏈?zhǔn)浇Y(jié)構(gòu)中除了尾節(jié)點，其他節(jié)點必須包含當(dāng)前對象所指向下一個對象的地址辐脖，
//那么構(gòu)造時就必須知道后一個節(jié)點的位置饲宛，所以必須從后往前構(gòu)造。先構(gòu)造最后一個結(jié)點嗜价。
links[a - 1] = new MyLink(a, null);
//循環(huán)構(gòu)造MyLink對象艇抠，i=a-1相對于長度（個數(shù)）來說是倒數(shù)第二，所以其中l(wèi)inks[i-1]就表示倒數(shù)第二位的元素
//久锥，從后往前構(gòu)造到links[0]家淤，頭節(jié)點需要自己手動構(gòu)造。i相對于長度瑟由，所以links[0]對應(yīng)i就是1絮重，
//也就是說只能循環(huán)到i=1
for (int i = a - 1; i >= 1; i--) {
links[i - 1] = new MyLink(i, links[i]);
}
//構(gòu)造頭節(jié)點，指向數(shù)組第一個元素
myLinkHeader = new MyLink(links[0]);
}
/**
* 查出傳入k位置的數(shù)據(jù)域和下一個節(jié)點的地址
* @param k
* @return
*/
public MyLink getLink(int k) throws Throwable {
if (k<1 || k>links.length) {
throw new Throwable("查詢位置不合理");
}
//k是查找出k位置的元素歹苦，j是開始計數(shù)的位置青伤；0是因為會多出一個頭節(jié)點，先從頭開始殴瘦，頭不計入查找的數(shù)組潮模。
int j = 0;
//用一個MyLink對象來不斷接收被重新賦對象。它先指向頭
MyLink myLink = myLinkHeader;
//從頭開始找痴施，直到
while (j < k) {
myLink = myLink.getNextLink();
j++;
}
return myLink;
}
}
SelectLinkListTest.java
public class SelectLinkListTest {
public static void main(String[] args) {
//循環(huán)構(gòu)造myLink
MyLink[] myLinks = new MyLink[10];
SelectLinkList selectLinkList = new SelectLinkList(myLinks);
selectLinkList.createLink();
//獲取k位置的數(shù)據(jù)域中的數(shù)據(jù)
MyLink link;
try {
link = selectLinkList.getLink(6);
System.out.println("獲取的數(shù)值域中數(shù)據(jù)為：" + link.getData());
} catch (Throwable throwable) {
throwable.printStackTrace();
}
}
}
結(jié)果
結(jié)果應(yīng)該是：
image.png
如果輸入的getLink()參數(shù)不滿足條件：
image.png
插入
其特點是擎厢，在i位置插入，插入元素的指針指向原來i位置指針指向的元素辣吃，那么將原來i-1位置的元素的指針改為指向插入的元素动遭。
類結(jié)構(gòu)：
- InsertLinkList.java
- InsertLinkListTest.java
InsertLinkList構(gòu)造線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)，并提供插入和查詢方法神得；InsertLinkListTest測試厘惦。
代碼實現(xiàn)
InsertLinkList
public class InsertLinkList {
/**
* 用來幫助循環(huán)構(gòu)建MyLink對象
*/
private MyLink[] links;
/**
* 假定傳入MyLink[10]，即要創(chuàng)建10個MyLink對象哩簿。這10個對象中是不應(yīng)該包含頭節(jié)點的宵蕉。
* 因為傳入的數(shù)組中，所有位置都要包含數(shù)據(jù)节榜；而MyLink的對象中頭節(jié)點的構(gòu)造方法是
* MyLink(MyLink nextLink)羡玛，所以在這里拿出來。
*/
private MyLink myLinkHeader = null;
/**
* 為了傳入自定義MyLink[]的長度
* @param links
*/
public InsertLinkList(MyLink[] links) {
this.links = links;
}
/**
* 循環(huán)構(gòu)建MyLink對象宗苍。
* @return
*/
public void createLink() {
//拿到長度稼稿，知道構(gòu)造的節(jié)點是從哪里開始
int a = links.length;
//鏈?zhǔn)浇Y(jié)構(gòu)中除了尾節(jié)點薄榛，其他節(jié)點必須包含當(dāng)前對象所指向下一個對象的地址，
//那么構(gòu)造時就必須知道后一個節(jié)點的位置让歼，所以必須從后往前構(gòu)造敞恋。先構(gòu)造最后一個結(jié)點。
links[a - 1] = new MyLink(a, null);
//循環(huán)構(gòu)造MyLink對象谋右，i=a-1相對于長度（個數(shù)）來說是倒數(shù)第二硬猫，所以其中l(wèi)inks[i-1]就表示倒數(shù)第二位的元素
//，從后往前構(gòu)造到links[0]改执，頭節(jié)點需要自己手動構(gòu)造啸蜜。i相對于長度，所以links[0]對應(yīng)i就是1天梧，
//也就是說只能循環(huán)到i=1
for (int i = a - 1; i >= 1; i--) {
links[i - 1] = new MyLink(i, links[i]);
}
//構(gòu)造頭節(jié)點，指向數(shù)組第一個元素
myLinkHeader = new MyLink(links[0]);
}
/**
* 在i位置屁股后面插入myLink對象
* @param myLink
* @param i
*/
public void insertLink(MyLink myLink,int i) {
MyLink myLinkMove = myLinkHeader.getNextLink();
if (i == 0) {
//在頭位置插入myLink對象霞丧，讓myLink對象指向頭指針指向的對象呢岗，頭結(jié)點指向myLink對象
myLink.setNextLink(myLinkMove);
myLinkHeader.setNextLink(myLink);
}else if (i>=1 && i<links.length-1){
//遍歷獲取到插入位置i的myLink對象
for (int k = 1; k < i ; k++) {
myLinkMove = myLinkMove.getNextLink();
}
//獲取i位置的沒有Link對象的下一對象
MyLink myLink2 = myLinkMove.getNextLink();
//插入的對象的指針為原來位置指向下一結(jié)點的指針
myLink.setNextLink(myLink2);
//將插入位的對象的指針設(shè)置為要插入的對象
myLinkMove.setNextLink(myLink);
}else {
//插入的位置超出或等于長度時，獲取到末尾結(jié)點蛹尝，讓末尾結(jié)點的指針執(zhí)行myLink對象
MyLink myLinkLast = links[links.length-1];
myLinkLast.setNextLink(myLink);
}
}
/**
* 查出傳入k位置的數(shù)據(jù)域和下一個節(jié)點的地址
* @param k
* @return
*/
public MyLink getLink(int k) throws Throwable {
if (k<1 || k>links.length+1) {
throw new Throwable("查詢位置不合理");
}
//k是查找出k位置的元素后豫，j是開始計數(shù)的位置；0是因為會多出一個頭節(jié)點突那，先從頭開始挫酿，頭不計入查找的數(shù)組置森。
int j = 0;
//用一個MyLink對象來不斷接收被重新賦對象岔冀。它先指向頭
MyLink myLink = myLinkHeader;
//從頭開始找，直到
while (j < k) {
myLink = myLink.getNextLink();
j++;
}
return myLink;
}
}
InsertLinkListTest
public class InsertLinkListTest {
public static void main(String[] args) {
//循環(huán)構(gòu)造myLink
MyLink[] myLinks = new MyLink[10];
InsertLinkList insertLinkList = new InsertLinkList(myLinks);
insertLinkList.createLink();
//插入
MyLink myLink = new MyLink(19,null );
insertLinkList.insertLink(myLink, 2);
try {
MyLink link = insertLinkList.getLink(3);
System.out.println(link.getData());
} catch (Throwable throwable) {
throwable.printStackTrace();
}
}
}
結(jié)果
image.png
