簡(jiǎn)介
- 線性表是最常用且最簡(jiǎn)單的一種數(shù)據(jù)結(jié)構(gòu)际乘，簡(jiǎn)而言之就是n個(gè)數(shù)據(jù)元素的有限序列或渤。
- 線性表的順序表示和實(shí)現(xiàn)：
線性表的順序指用一組地址連續(xù)的存儲(chǔ)單元一次存儲(chǔ)線性表的數(shù)據(jù)元素朋魔。以元素在計(jì)算機(jī)內(nèi)的“物理位置相鄰”來(lái)表示線性表中數(shù)據(jù)元素之間的邏輯關(guān)系函荣。每個(gè)數(shù)據(jù)元素的存儲(chǔ)位置和線性表的起始位置相差一個(gè)和數(shù)據(jù)元素在線性表中的位序成正比的常數(shù)。只要我確定了存儲(chǔ)線性表的起始位置浸踩，線性表中任一數(shù)據(jù)元素都可以隨機(jī)存取叔汁，所以線性表的順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)（存取的時(shí)候可以直接獲得線性表中的某一數(shù)據(jù)，像數(shù)組检碗，可以通過(guò)下標(biāo)直接獲取數(shù)組中的任一元素据块，而不需要像鏈表那樣需要通過(guò)指針從頭遍歷查找，但是線性表的順序存儲(chǔ)缺點(diǎn)是插入元素或者刪除元素都有進(jìn)行大量的移動(dòng)后裸，而鏈表就不用瑰钮，只需要修改指針）冒滩。
線性表的創(chuàng)建很簡(jiǎn)單：
//初始化線性表
int IinitListSpace(LIN* V){
V->elem = (int*)malloc(MAX_FORM_SIZE*sizeof(int));
if(!V->elem)exit(OVERFLOW);
V->length = 0;
V->sizes = MAX_FORM_SIZE;
return 1;
}
//初始化線性表數(shù)據(jù)
int InitListData(LIN* V){
int i =0;
for(i =0 ; i<10 ; i++) {
V->elem[i] = i;
V->length++;
if(V->length >= MAX_FORM_SIZE)break;
}
return 1;
}
//向線性表任意位置插入數(shù)據(jù)
int InsertListData(LIN* V){
int data;
int space;
int i;
printf("\n請(qǐng)輸入需要插入的位置和整數(shù)\n");
scanf("%d",&space);
scanf("%d",&data);
if(space<1||space > V->length+1)return 0;
//如果空間已經(jīng)占滿微驶，這增加空間
if(V->length >= V->sizes){
//重新給線性表分配內(nèi)存，在原來(lái)的基礎(chǔ)上增加內(nèi)存空間
V->elem = (int*)realloc(V->elem,(MAX_FORM_SIZE+MAX_FORM_LENTH)*sizeof(int));
if(!V->elem)exit(OVERFLOW);
V->sizes = MAX_FORM_SIZE+MAX_FORM_LENTH;
}
printf("插入之前的線性表數(shù)據(jù)\n");
for(i =0 ; i < V->length ; i++){
printf("%d ",V->elem[i]);
}
//插入數(shù)據(jù)，移動(dòng)數(shù)據(jù)
for(i = V->length ; i >= space -1 ; i-- ) V->elem[i+1] = V->elem[i];
V->elem[space-1] = data;
V->length +=1;
printf("\n插入之后的線性表數(shù)據(jù)\n");
for(i =0 ; i < V->length ; i++){
printf("%d ",V->elem[i]);
}
return 1;
}
線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)：存儲(chǔ)結(jié)構(gòu)的特點(diǎn)是用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素（這組存儲(chǔ)單元可以是連續(xù)的因苹，也可以不是連續(xù)的）苟耻。用線性鏈表表示線性表時(shí)，數(shù)據(jù)元素之間的邏輯關(guān)系是由結(jié)點(diǎn)中的指針指示的扶檐，也就是說(shuō)凶杖，指針位數(shù)據(jù)元素之間的邏輯映射，則邏輯相鄰的兩個(gè)元素其存儲(chǔ)的物理位置不要求緊鄰款筑，這種存儲(chǔ)結(jié)構(gòu)為非順序映像或鏈?zhǔn)接诚瘛?
線性鏈表的創(chuàng)建：
//線性鏈表相關(guān)操作
void* InitLinkList(LinkList V){
int i;
Node* P;
V = (LinkList)malloc(sizeof(Node));
if(!V)exit(OVERFLOW);
V->next = NULL;//建立一個(gè)帶頭節(jié)點(diǎn)的單鏈表
V->data = 0;
for(i = 0 ; i< 10 ;i++){
P = (LinkList)malloc(sizeof(Node));//生成節(jié)點(diǎn)
if(!P)exit(OVERFLOW);
//scanf("%d",&(P->data));
P->data = i;
P->next = V->next;
V->next = P;
V->data++;
}
return V;
}
這里講一下for循環(huán)里面怎么創(chuàng)建一個(gè)鏈表的：函數(shù)傳進(jìn)一個(gè)V鏈表智蝠，其指向下一個(gè)結(jié)點(diǎn)為NULL，這里我把鏈表的第一結(jié)點(diǎn)拿來(lái)做頭結(jié)點(diǎn)奈梳，當(dāng)然可以重新定義一個(gè)杈湾。在for循環(huán)里面，
當(dāng)執(zhí)行第一次for循環(huán)后攘须，鏈表呈現(xiàn)這個(gè)樣子：執(zhí)行P->next = V->next;后漆撞，P的下一個(gè)結(jié)點(diǎn)指向V的下一個(gè)結(jié)點(diǎn)，而V->next = NULL于宙，所以這時(shí)P的下一個(gè)結(jié)點(diǎn)不指向任何對(duì)象（或者對(duì)象為空）浮驳，也就是P->next = NULL；執(zhí)行V->next = P; 后捞魁，V的下一個(gè)結(jié)點(diǎn)指向P至会，也就是V的下一個(gè)結(jié)點(diǎn)指向，P的下一個(gè)結(jié)點(diǎn)指向NULL谱俭，這里不要因?yàn)镻->next = V->next;而以為P的下一個(gè)結(jié)點(diǎn)指回本身了奋献，指向的是NULL，所以就是V(next)——> P(next)——>NULL;
當(dāng)執(zhí)行第二次for循環(huán)后旺上，鏈表程序的樣子：執(zhí)行P->next = V->next;新生成的P結(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)指向V的下一個(gè)結(jié)點(diǎn)瓶蚂，但是執(zhí)行完第一次for循環(huán)后，V的下一個(gè)結(jié)點(diǎn)（V->next）指向了P宣吱，所以新的P節(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)指向了上一個(gè)P節(jié)點(diǎn)窃这，執(zhí)行V->next = P后，相當(dāng)于斷開(kāi)了第一次for循環(huán)后征候，V下一個(gè)結(jié)點(diǎn)指向第一P結(jié)點(diǎn)之間的鏈接杭攻。而將V的下一個(gè)結(jié)點(diǎn)指向新生成的P節(jié)點(diǎn)，這下就變成了：V(next)——>P（next）(第二次新生成的結(jié)點(diǎn))——>P（next）（第一次生成的結(jié)點(diǎn)）——>NULL疤坝，以次內(nèi)推兆解，一個(gè)鏈表就建立了，其實(shí)這個(gè)過(guò)程是從表尾開(kāi)始向表頭建立鏈表的跑揉，所以打印輸出的時(shí)候是反過(guò)來(lái)的锅睛。
注意：很多人可能在寫(xiě)鏈表的創(chuàng)建埠巨，插入和刪除的時(shí)候，會(huì)出現(xiàn)這樣的錯(cuò)誤现拒，定義一個(gè)指針類型的鏈表變量（如：LinkList *List）辣垒，然后把這個(gè)變量傳遞給函數(shù)的形參（插入和刪除的函數(shù)不再main()所在的同意文件里），然后函數(shù)的返回值為void印蔬，在創(chuàng)建好鏈表后勋桶，依然把List傳遞給插入和刪除的函數(shù)，或者在main（）里面打印輸出鏈表值侥猬，這時(shí)編譯不會(huì)出錯(cuò)例驹，運(yùn)行就出錯(cuò)了，很多人認(rèn)為我傳遞的是指針變量退唠，是地址啊眠饮，怎么在main（）里面不能用呢，至于怎么回事铜邮，自己看一下指針?lè)矫娴闹R(shí)仪召，我用了一段時(shí)間的java，c有點(diǎn)忘了松蒜。解決辦法就是把建好的鏈表返回來(lái)就可以了扔茅。
下面是java的鏈表實(shí)現(xiàn)程序：
import java.util.Scanner;
public class LinkList{
private int num = 0;
private class Node{
String elem;
Node next;
public Node(){
this.elem = null;
this.next = null;
}
}
private Node getNode(){
return new Node();
}
private Node LinkListInit(){
System.out.println("初始化線性鏈表");
Node root = new Node();//構(gòu)造頭節(jié)點(diǎn)
root.elem = "根節(jié)點(diǎn)";
for(int i = 0 ; i < 10 ; i++){
Node node = new Node();
node.elem = "第" + i + "節(jié)點(diǎn)";
node.next = root.next;
root.next = node;
root.elem = "一共" + i + "節(jié)點(diǎn)";
}
return root;
}
private void outPut(Node root){
for(int i = 0 ; i < 10 ; i++){
if(root != null){
System.out.println(root.elem);
root = root.next;
}
}
}
private Node deleteLinkList(Node root){
Node ret = new Node();
ret = root;
Scanner scanner = new Scanner(System.in);// 創(chuàng)建輸入流掃描器
System.out.println("請(qǐng)輸入需要?jiǎng)h除元素的位置：");// 提示用戶輸入
int space = scanner.nextInt();// 獲取用戶輸入的一行文本
if(ret != null) {
for(int i = 1 ; i < space ; i++){
if(ret == null){
System.out.println("你輸入的位置不正確：");
return root;
}
ret = ret.next;
}
}
else{
System.out.println("請(qǐng)輸入的位置不正確：");
}
ret.next = (ret.next).next;
num++;
root.elem = "一共" + (9 - num) + "節(jié)點(diǎn)" ;
return root;
}
public static void main(String[] args){
LinkList link = new LinkList();
Node root = link.getNode();
root = link.LinkListInit();//初始化鏈表
link.outPut(root);//打印出每個(gè)節(jié)點(diǎn)值
root = link.deleteLinkList(root);
link.outPut(root);//打印出每個(gè)節(jié)點(diǎn)值
}
}
靜態(tài)鏈表的表示：用數(shù)組描述的鏈表，需要預(yù)先分配一定的空間秸苗。但解決了數(shù)據(jù)插入和刪除是需要的移動(dòng)元素的缺點(diǎn)召娜，靜態(tài)鏈表插入和刪除數(shù)據(jù)是不需要移動(dòng)數(shù)據(jù)元素。好像數(shù)組里面有了鏈表的特性惊楼。
那為什么要用靜態(tài)鏈表呢玖瘸，不是有鏈表嗎？鏈表是嚴(yán)重依賴指針的檀咙，在沒(méi)有指針語(yǔ)法的語(yǔ)言里面那我們?cè)撛趺磳?shí)現(xiàn)類似鏈表的功能呢雅倒？那就要用靜態(tài)鏈表了。
靜態(tài)鏈表的使用思想是怎么樣的呢弧可？靜態(tài)鏈表里蔑匣。我們把數(shù)組的每一個(gè)分量（也就是數(shù)據(jù)項(xiàng)）表示一個(gè)結(jié)點(diǎn)，里面存儲(chǔ)數(shù)值和一個(gè)下標(biāo)數(shù)值棕诵，這個(gè)下標(biāo)數(shù)值就像鏈表里的*next一樣裁良，存儲(chǔ)的值 = 它所指向的那個(gè)數(shù)據(jù)的在數(shù)組中的位置。例如下面的：（下標(biāo)為0的定義位頭節(jié)點(diǎn)校套，指向0表示數(shù)組結(jié)束）价脾。[圖片上傳失敗...(image-bdb8df-1545565392987)]
它的邏輯結(jié)構(gòu)是這樣的：
那么我們插入數(shù)據(jù)是可以將數(shù)據(jù)插入任意空的地址空間，然后想鏈表那樣修改對(duì)應(yīng)的下標(biāo)值就是了笛匙，也不用移動(dòng)數(shù)據(jù)：程序如下：
StaticList* StaticList_Create(int capacity) // O(n)
{
TStaticList* ret = NULL;
int i = 0;
if( capacity >= 0 )
{
ret = (TStaticList*)malloc(sizeof(TStaticList) + sizeof(TStaticListNode) * (capacity + 1));
}
if( ret != NULL )
{
ret->capacity = capacity;
ret->header.data = 0;
ret->header.next = 0;
for(i=1; i<=capacity; i++)
{
ret->node[i].next = AVAILABLE;
}
}
return ret;
}
int StaticList_Insert(StaticList* list, StaticListNode* node, int pos) // O(n)
{
TStaticList* sList = (TStaticList*)list;
int ret = (sList != NULL);
int current = 0;
int index = 0;
int i = 0;
ret = ret && (sList->header.data + 1 <= sList->capacity);
ret = ret && (pos >=0) && (node != NULL);
if( ret )
{
for(i=1; i<=sList->capacity; i++)
{
if( sList->node[i].next == AVAILABLE )
{
index = i;
break;
}
}
sList->node[index].data = (unsigned int)node;
sList->node[0] = sList->header;
for(i=0; (i<pos) && (sList->node[current].next != 0); i++)
{
current = sList->node[current].next;
}
sList->node[index].next = sList->node[current].next;
sList->node[current].next = index;
sList->node[0].data++;
sList->header = sList->node[0];
}
return ret;
}
循環(huán)鏈表：這個(gè)在前面的基礎(chǔ)上增加指針就可以實(shí)現(xiàn)侨把，這里就不講了犀变。
總結(jié)：為什么用線性表順序存儲(chǔ)：方便隨機(jī)存取，但是插入和刪除需要大量移動(dòng)數(shù)據(jù)座硕，能夠繼續(xù)增加存儲(chǔ)空間大小弛作，不能動(dòng)態(tài)生成涕蜂，因?yàn)槊看畏峙鋬?nèi)存時(shí)內(nèi)存不一定是連續(xù)的华匾，而順序表不能通過(guò)指針指向下一個(gè)元素，所以不能動(dòng)態(tài)生成机隙。
問(wèn)什么用鏈表:能動(dòng)態(tài)生成蜘拉，不需要移動(dòng)元素，存儲(chǔ)靈活等
為什么用靜態(tài)鏈表:在不支持指針的語(yǔ)言中也能實(shí)現(xiàn)鏈表的存儲(chǔ)和操作等
工程地址：http://download.csdn.net/detail/tuoguang/9164793
打開(kāi)工具dev-c++：
