鏈表數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)和鏈表有什么關(guān)系

來源：整理時(shí)間：2023-09-08 19:01:46 編輯：智能門戶手機(jī)版

本文目錄一覽

1，數(shù)據(jù)結(jié)構(gòu)和鏈表有什么關(guān)系
2，數(shù)據(jù)結(jié)構(gòu)typedef 鏈表
3，數(shù)據(jù)結(jié)構(gòu)的鏈表問題
4，數(shù)據(jù)結(jié)構(gòu)單鏈表
5，關(guān)于數(shù)據(jù)結(jié)構(gòu)中鏈表的實(shí)現(xiàn)
6，java里的鏈表指的是什么為什么需要鏈表

1，數(shù)據(jù)結(jié)構(gòu)和鏈表有什么關(guān)系

親~鏈表是數(shù)據(jù)結(jié)構(gòu)的一種哦~是包含關(guān)系哦~親~

就是頭結(jié)點(diǎn)的next指向下一個(gè)結(jié)點(diǎn)并且能一直找到最后一個(gè)結(jié)點(diǎn)的鏈表。

數(shù)據(jù)結(jié)構(gòu)和鏈表有什么關(guān)系

2，數(shù)據(jù)結(jié)構(gòu)typedef 鏈表

LNode是指你定義的結(jié)點(diǎn)類型，就是大括號(hào)中的包含指針域和數(shù)值域的變量。 *LinkList是指你所定義的是一個(gè)鏈表不是單個(gè)結(jié)點(diǎn)。。 LinkList L; L = malloc(sizeof(LinkList)); 是指申請(qǐng)一個(gè)鏈表的頭結(jié)點(diǎn)的空間，并使該鏈表的指針指向該結(jié)點(diǎn)。。。因?yàn)槔碚撋险f鏈表空間可以無限，即整個(gè)內(nèi)存的空間都可以為其所用，所以無需提前指定鏈表空間大小也可以繼續(xù)申請(qǐng)下一個(gè)結(jié)點(diǎn)的空間。。 LinkList L;是指定義一個(gè)鏈表。 L = malloc(sizeof(LinkList));是指為該鏈表申請(qǐng)頭結(jié)點(diǎn)，并使該鏈表的指針指向該結(jié)點(diǎn) LNode *p; p = malloc(sizeof(LNode)); 與上句不同，這句是指你申請(qǐng)一個(gè)結(jié)點(diǎn)的空間。 LNode *p;是先定義一個(gè)結(jié)點(diǎn)。p = malloc(sizeof(LNode));是指為該結(jié)點(diǎn)申請(qǐng)內(nèi)存空間。。注意一個(gè)結(jié)點(diǎn)和一個(gè)鏈表的區(qū)別就可以了。。

數(shù)據(jù)結(jié)構(gòu)typedef 鏈表

3，數(shù)據(jù)結(jié)構(gòu)的鏈表問題

List_INIT_SIZE,表示初始分配100個(gè)元素空間。 LIST_INCREMENT，表示當(dāng)100個(gè)元素空間被用完了后每次的再分配的增量。100滿了計(jì)算機(jī)自動(dòng)去找一塊能容納110個(gè)元素的地址空間，把前100個(gè)元素COPY過去，釋放原來100個(gè)元素的地址空間，修改Sqlist的指針指向新的內(nèi)存地址。120，130。。。以此類推。為什么要這樣呢？因?yàn)閿?shù)組必須要是連續(xù)的內(nèi)存地址，而原來100個(gè)元素的后面地址空間有可能被新的變量分配使用掉了。而每次我們?cè)黾?0個(gè)元素。避免每增加一個(gè)元素就去COPY一次前面的元素。 length，表示線性表長(zhǎng)度啦。就是裝有的元素個(gè)數(shù)的。初始化為0，表示沒有裝有元素。 size，表示線性表大小啦。就是最大容量。比如：你的線性表有111個(gè)元素，那么容量就應(yīng)該是120。為什么？至于List_INIT_SIZE*sizeof(Elemtype)，首先malloc的參數(shù)是以字節(jié)為單位。表示分配多少字節(jié)。Elemtype被定義為int類型，占4個(gè)字節(jié)。那么100個(gè)元素，每個(gè)元素4個(gè)字節(jié)總共該分配多少個(gè)字節(jié)呢？小學(xué)數(shù)學(xué)題吧！

數(shù)據(jù)結(jié)構(gòu)的鏈表問題

4，數(shù)據(jù)結(jié)構(gòu)單鏈表

#ifndef LISTNODE_H#define LISTNODE_Htemplate<typename NODETYPE>class ListNode friend class List<NODETYPE>; public: ListNode(const NODETYPE &); NODETYPE getData() const; private: NODETYPE data; ListNode<NODETYPE> *nextPtr;}; template<typename NODETYPE>ListNode<NODETYPE>::ListNode(const NODETYPE &info) :data(info),nextPtr(0)} template<typename NODETYPE>NODETYPE ListNode<NODETYPE>::getData() constreturn data;}#endif

上QQ 聯(lián)系我

5，關(guān)于數(shù)據(jù)結(jié)構(gòu)中鏈表的實(shí)現(xiàn)

鏈表是用結(jié)構(gòu)體實(shí)現(xiàn)的（當(dāng)然，用類也行）鏈表打個(gè)比方，就好比尋寶，根據(jù)藏寶圖找到一個(gè)地址，到那個(gè)地址后，會(huì)有另一張藏寶圖，指向下一個(gè)寶藏的位置。。鏈表分為單向鏈表和雙向鏈表。顧名思義，單向鏈表就是你只能從一個(gè)鏈節(jié)找到下一個(gè)鏈節(jié)，而不能從這個(gè)鏈節(jié)回到上一個(gè)鏈節(jié)。而雙向鏈表正反都可以。你知道結(jié)構(gòu)體吧，里面可以認(rèn)為打包一些你需要的數(shù)據(jù)?；谶@個(gè)基礎(chǔ)，你可以在里面放一個(gè)該類型的結(jié)構(gòu)體的指針變量來存放下一個(gè)結(jié)構(gòu)體的地址，然后再放一些你需要存的數(shù)據(jù)。這樣一個(gè)一個(gè)安排好，用指針變量把他們連接起來，就組成了一個(gè)普通的單向鏈表。雙向鏈表亦是如此，只不過多了一個(gè)指針記錄前一個(gè)鏈節(jié)的地址。每一個(gè)結(jié)構(gòu)體變量叫做鏈節(jié)，它的下一個(gè)鏈節(jié)叫子節(jié)點(diǎn)，上一個(gè)鏈節(jié)叫做父節(jié)點(diǎn)，類比二叉樹。每一個(gè)鏈節(jié)的內(nèi)容分為兩部分，指針部分和數(shù)據(jù)部分，這個(gè)不難理解。鏈表由于是用指針連接起來的，所以麻煩就麻煩在這里，如果有一個(gè)小改動(dòng)，比如加一個(gè)元素到某一個(gè)位置，就必須改動(dòng)父節(jié)點(diǎn)、子節(jié)點(diǎn)的指針。添加節(jié)點(diǎn)、刪除節(jié)點(diǎn)等操作各有不同，甚至兩頭的改動(dòng)和中間的改動(dòng)都需要分開寫，這些都稱作鏈表的維護(hù)。雖然有些復(fù)雜，但是掌握了原理之后其實(shí)非常簡(jiǎn)單。建立鏈表的步驟是：先寫一個(gè)結(jié)構(gòu)體類型，明確你這個(gè)鏈表都需要哪些東西。比如：struct ListList * p; // 指針，記錄子節(jié)點(diǎn)的位置int value; // 數(shù)據(jù)成員，存放數(shù)據(jù)的變量};然后就可以建立鏈表了。List * head; // 首先申明一個(gè)頭指針，記錄鏈表的首地址，類似數(shù)組的首地址List * temp; // 一個(gè)臨時(shí)變量，之后你會(huì)知道他的作用head = new List; // 然后就新建一個(gè)鏈節(jié)，用new來建立head->p = NULL; // 把不需要的指針NULL是好習(xí)慣head->value = 0; // 記錄該節(jié)點(diǎn)的數(shù)據(jù)這樣就完成了一個(gè)鏈表的第一個(gè)鏈節(jié)的建立。之后的建立完全類似：head->p = new List; // 再新建一個(gè)節(jié)點(diǎn)temp = head->p; // 讓臨時(shí)指針指向這個(gè)新建的節(jié)點(diǎn)，以后的操作就可以用temp完成了temp->p = NULL; // 尾指針賦值為NULLtemp->value = 1; // 記錄該節(jié)點(diǎn)的數(shù)據(jù)。就是這樣，每個(gè)節(jié)點(diǎn)里面都有一個(gè)指針指向下一個(gè)節(jié)點(diǎn)，最后一個(gè)節(jié)點(diǎn)的指針（尾指針）是NULL，意味著鏈表的結(jié)束。鏈表建立之后，你就可以從首節(jié)點(diǎn)一個(gè)一個(gè)找，直到找到你想找的節(jié)點(diǎn)了。短距離可以：head->p->p->……->value;很長(zhǎng)的話就再用一個(gè)臨時(shí)變量中轉(zhuǎn)一下吧。

6，java里的鏈表指的是什么為什么需要鏈表

鏈表的確是一種數(shù)據(jù)結(jié)構(gòu)．而數(shù)據(jù)結(jié)構(gòu)就是一種存放數(shù)據(jù)的方式．鏈表就是和鐵鏈相似的．一個(gè)接著一個(gè)．一個(gè)扣著一個(gè)．比如：1，后面接著是2，然后是3，是連續(xù)的．1，2，3，就是這個(gè)鏈表的節(jié)點(diǎn)，就是數(shù)據(jù)存放的地方再通俗點(diǎn)．大學(xué)的校園生活：班級(jí)是這樣的．1年1班，1年2班，．．．．1年10班．班級(jí)就是節(jié)點(diǎn)，而班級(jí)里的學(xué)生，就是數(shù)據(jù)．他們是連續(xù)存儲(chǔ)的．但是內(nèi)存分分配不是連續(xù)的．有時(shí)間看下，＜數(shù)據(jù)結(jié)構(gòu)＞書上寫的很好．我就說到這吧．

java中的集合類有很多種,每個(gè)都有自己的一些特點(diǎn),推薦你專門在這方面研究一下,比方Vector,ArrayList,,LinkedList,Hashtable等,其中你問到的鏈表,是不是指LinkedList呢?LinkedList是集合類的一種,和其它集合類一樣都用于存放未知內(nèi)容和未知長(zhǎng)度的數(shù)據(jù)或者說對(duì)象.由于LinkedList的內(nèi)部實(shí)現(xiàn)是采用鏈表結(jié)構(gòu),所以它就取名為L(zhǎng)inkedList當(dāng)然ArrayList的內(nèi)部實(shí)現(xiàn)是采用數(shù)組結(jié)構(gòu),所以它就取名為ArrayList,呵呵,很好理解吧.它們就相當(dāng)于一個(gè)容器,跟數(shù)據(jù)一樣,可以存放數(shù)據(jù),但數(shù)組你必須在一開始就指定它里面的內(nèi)容是什么類型的,比方你必須 int[] array; 而集合類就沒有必要,只需要: Vector vector=new Vector();就可以,至于放里面存放數(shù)據(jù)就更簡(jiǎn)單了,它什么都可以放,只要是對(duì)象: String str="hello";vector.add(str);Integer i=10;vector.add(i);取數(shù)據(jù)的時(shí)候需要做類型強(qiáng)制轉(zhuǎn)換,因?yàn)槟惴诺臅r(shí)候沒有強(qiáng)制指定類型:String str=(String)vector.get(0);String i=(Integer)vecotr.get(1); 其它幾種集合類也和vector的用法接近,但有些會(huì)有些變化和特點(diǎn), 集合類是java語言的一個(gè)重點(diǎn)學(xué)習(xí)項(xiàng)目,一定要深入了解,不要光從百度上搜,一定要自己多看書,多做實(shí)例. <<java核心技術(shù)卷I>>中有專門的一章重點(diǎn)講解集合類

鏈表是一種重要的數(shù)據(jù)結(jié)構(gòu)，在程序設(shè)計(jì)中占有很重要的地位。c語言和c＋＋語言中是用指針來實(shí)現(xiàn)鏈表結(jié)構(gòu)的，由于java語言不提供指針，所以有人認(rèn)為在java語言中不能實(shí)現(xiàn)鏈表，其實(shí)不然，java語言比c和c＋＋更容易實(shí)現(xiàn)鏈表結(jié)構(gòu)。java語言中的對(duì)象引用實(shí)際上是一個(gè)指針（本文中的指針均為概念上的意義，而非語言提供的數(shù)據(jù)類型），所以我們可以編寫這樣的類來實(shí)現(xiàn)鏈表中的結(jié)點(diǎn)。 class node object data; node next;//指向下一個(gè)結(jié)點(diǎn) } 將數(shù)據(jù)域定義成object類是因?yàn)閛bject類是廣義超類，任何類對(duì)象都可以給其賦值，增加了代碼的通用性。為了使鏈表可以被訪問還需要定義一個(gè)表頭，表頭必須包含指向第一個(gè)結(jié)點(diǎn)的指針和指向當(dāng)前結(jié)點(diǎn)的指針。為了便于在鏈表尾部增加結(jié)點(diǎn)，還可以增加一指向鏈表尾部的指針，另外還可以用一個(gè)域來表示鏈表的大小，當(dāng)調(diào)用者想得到鏈表的大小時(shí)，不必遍歷整個(gè)鏈表。下圖是這種鏈表的示意圖：鏈表的數(shù)據(jù)結(jié)構(gòu) 我們可以用類list來實(shí)現(xiàn)鏈表結(jié)構(gòu)，用變量head、tail、length、pointer來實(shí)現(xiàn)表頭。存儲(chǔ)當(dāng)前結(jié)點(diǎn)的指針時(shí)有一定的技巧，pointer并非存儲(chǔ)指向當(dāng)前結(jié)點(diǎn)的指針，而是存儲(chǔ)指向它的前趨結(jié)點(diǎn)的指針,當(dāng)其值為null時(shí)表示當(dāng)前結(jié)點(diǎn)是第一個(gè)結(jié)點(diǎn)。那么為什么要這樣做呢？這是因?yàn)楫?dāng)刪除當(dāng)前結(jié)點(diǎn)后仍需保證剩下的結(jié)點(diǎn)構(gòu)成鏈表，如果pointer指向當(dāng)前結(jié)點(diǎn)，則會(huì)給操作帶來很大困難。那么如何得到當(dāng)前結(jié)點(diǎn)呢，我們定義了一個(gè)方法cursor(),返回值是指向當(dāng)前結(jié)點(diǎn)的指針。類list還定義了一些方法來實(shí)現(xiàn)對(duì)鏈表的基本操作，通過運(yùn)用這些基本操作我們可以對(duì)鏈表進(jìn)行各種操作。例如reset()方法使第一個(gè)結(jié)點(diǎn)成為當(dāng)前結(jié)點(diǎn)。insert(object d)方法在當(dāng)前結(jié)點(diǎn)前插入一個(gè)結(jié)點(diǎn)，并使其成為當(dāng)前結(jié)點(diǎn)。remove()方法刪除當(dāng)前結(jié)點(diǎn)同時(shí)返回其內(nèi)容，并使其后繼結(jié)點(diǎn)成為當(dāng)前結(jié)點(diǎn)，如果刪除的是最后一個(gè)結(jié)點(diǎn)，則第一個(gè)結(jié)點(diǎn)變?yōu)楫?dāng)前結(jié)點(diǎn)。鏈表類list的源代碼如下： import java.io.*; public class list /*用變量來實(shí)現(xiàn)表頭*/ private node head=null; private node tail=null; private node pointer=null; private int length=0; public void deleteall() /*清空整個(gè)鏈表*/ head=null; tail=null; pointer=null; length=0; } public void reset() /*鏈表復(fù)位，使第一個(gè)結(jié)點(diǎn)成為當(dāng)前結(jié)點(diǎn)*/ pointer=null; } public boolean isempty() /*判斷鏈表是否為空*/ return(length==0); } public boolean isend() /*判斷當(dāng)前結(jié)點(diǎn)是否為最后一個(gè)結(jié)點(diǎn)*/ if(length==0) throw new java.lang.nullpointerexception(); else if(length==1) return true; else return(cursor()==tail); } public object nextnode() /*返回當(dāng)前結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)的值，并使其成為當(dāng)前結(jié)點(diǎn)*/ if(length==1) throw new java.util.nosuchelementexception(); else if(length==0) throw new java.lang.nullpointerexception(); else node temp=cursor(); pointer=temp; if(temp!=tail) return(temp.next.data); else throw new java.util.nosuchelementexception(); } } public object currentnode() /*返回當(dāng)前結(jié)點(diǎn)的值*/ node temp=cursor(); return temp.data; } public void insert(object d) /*在當(dāng)前結(jié)點(diǎn)前插入一個(gè)結(jié)點(diǎn)，并使其成為當(dāng)前結(jié)點(diǎn)*/ node e=new node(d); if(length==0) tail=e; head=e; } else node temp=cursor(); e.next=temp; if(pointer==null) head=e; else pointer.next=e; } length＋＋; } public int size() /*返回鏈表的大小*/ return (length); } public object remove() /*將當(dāng)前結(jié)點(diǎn)移出鏈表，下一個(gè)結(jié)點(diǎn)成為當(dāng)前結(jié)點(diǎn)，如果移出的結(jié)點(diǎn)是最后一個(gè)結(jié)點(diǎn)，則第一個(gè)結(jié)點(diǎn)成為當(dāng)前結(jié)點(diǎn)*/ object temp; if(length==0) throw new java.util.nosuchelementexception(); else if(length==1) temp=head.data; deleteall(); } else node cur=cursor(); temp=cur.data; if(cur==head) head=cur.next; else if(cur==tail) pointer.next=null; tail=pointer; reset(); } else pointer.next=cur.next; length－－; } return temp; } private node cursor() /*返回當(dāng)前結(jié)點(diǎn)的指針*/ if(head==null) throw new java.lang.nullpointerexception(); else if(pointer==null) return head; else return pointer.next; } public static void main(string[] args) /*鏈表的簡(jiǎn)單應(yīng)用舉例*/ list a=new list (); for(int i=1;i<=10;i＋＋) a.insert(new integer(i)); system.out.println(a.currentnode()); while(!a.isend()) system.out.println(a.nextnode()); a.reset(); while(!a.isend()) a.remove(); } a.remove(); a.reset(); if(a.isempty()) system.out.println("there is no node in list \n"); system.in.println("you can press return to quit\n"); try system.in.read(); //確保用戶看清程序運(yùn)行結(jié)果 } catch(ioexception e) } } class node /*構(gòu)成鏈表的結(jié)點(diǎn)定義*/ object data; node next; node(object d) data=d; next=null; } } 讀者還可以根據(jù)實(shí)際需要定義新的方法來對(duì)鏈表進(jìn)行操作。雙向鏈表可以用類似的方法實(shí)現(xiàn)只是結(jié)點(diǎn)的類增加了一個(gè)指向前趨結(jié)點(diǎn)的指針。可以用這樣的代碼來實(shí)現(xiàn)： class node object data; node next; node previous; node(object d) data=d; next=null; previous=null; } } 當(dāng)然，雙向鏈表基本操作的實(shí)現(xiàn)略有不同。鏈表和雙向鏈表的實(shí)現(xiàn)方法，也可以用在堆棧和隊(duì)列的實(shí)現(xiàn)中，這里就不再多寫了，有興趣的讀者可以將list類的代碼稍加改動(dòng)即可。如果對(duì)您有幫助，請(qǐng)記得采納為滿意答案，謝謝！祝您生活愉快！vaela