靜態(tài)鏈表——數(shù)據(jù)結(jié)構(gòu)預(yù)習(xí)

其實(shí)一般有單鏈表的話寓辱，應(yīng)該用不著靜態(tài)鏈表赤拒。然而并不是什么編程語言都有指針诱鞠，這時(shí)靜態(tài)鏈表可以起到單鏈表的作用航夺。靜態(tài)鏈表的思考方式還蠻巧妙崔涂。
特點(diǎn)：
1、靜態(tài)鏈表是一個(gè)足夠大的結(jié)構(gòu)體數(shù)組，大概是分成數(shù)據(jù)+游標(biāo)的形式帝雇。數(shù)組里面有數(shù)據(jù)的為一部分（姑且叫數(shù)據(jù)域吧）蛉拙，沒有數(shù)據(jù)的（即未使用的數(shù)組元素）叫做備用鏈表。
2吮廉、數(shù)組的第0個(gè)和最后1個(gè)元素作特殊處理畸肆，它們的data不存放數(shù)據(jù)轴脐。
3、數(shù)組的第0個(gè)元素的游標(biāo)存放備用鏈表第1個(gè)節(jié)點(diǎn)的下標(biāo)恬涧。
4碴巾、數(shù)組的最后一個(gè)元素的游標(biāo)存放數(shù)據(jù)域第1個(gè)節(jié)點(diǎn)的下標(biāo)（相當(dāng)于單鏈表的頭節(jié)點(diǎn)）

優(yōu)點(diǎn)：和動(dòng)態(tài)鏈表一樣厦瓢，刪除和插入元素時(shí)間復(fù)雜度低
不足：和數(shù)組一樣，需要提前分配一塊較大的空間碳锈、
可以參考一下這篇文章https://www.cnblogs.com/dongry/p/10210609.html
額……建議畫圖理解欺抗，圖畫得步驟較多售碳，不是很難畫，自己動(dòng)手吧。??
強(qiáng)烈推薦這篇https://blog.csdn.net/qq_37668436/article/details/104519005?utm_medium=distribute.pc_relevant.none-task-blog-baidujs-1寫得很棒贸人，但是不自己動(dòng)手寫是學(xué)不會(huì)的间景。主要參考這篇文章做筆記。

image.png

#include <iostream>
#include<stdlib.h>
using namespace std;
constexpr auto maxsize = 7;//本來是#define maxsize 7艺智，被vs建議修改為這樣

typedef struct node
{
    char data;//數(shù)據(jù)
    int cur;//游標(biāo)倘要，模擬鏈表的指針
}Node[maxsize];
void init(Node L);//創(chuàng)建備用鏈表
int getlength(Node L);//不包括頭尾節(jié)點(diǎn)，求鏈表元素個(gè)數(shù)/數(shù)據(jù)域長度
int get(Node L);//提取空閑變量十拣，分配下標(biāo)
void insert(Node L,int i,char newdata);//靜態(tài)鏈表中i位置插入一個(gè)元素
void Free(Node L, int k);//釋放節(jié)點(diǎn)
bool Delete(Node L, int i, char* key);//刪除第i個(gè)元素
void Traverse(Node L);//遍歷

int main()
{
    Node L;
    cout << "初始化鏈表：";
    init(L);
    cout << "初始化后鏈表長度：" << getlength(L) << endl;
    cout << "插入a、b夭问、c泽西、d、e" << endl;
    insert(L, 1, 'a');
    insert(L, 1, 'b');
    insert(L, 1, 'c');
    insert(L, 1, 'd');
    insert(L, 1, 'e');
    cout << "插入后的長度：" << getlength(L) << ",遍歷鏈表得各元素分別為：";
    Traverse(L);
    char key;
    Delete(L, 2, &key);
    cout << "刪除的元素值為：" << key<<endl;
    cout << "插入后的長度：" << getlength(L) << ",遍歷鏈表得各元素分別為：";
    Traverse(L);

    return 0;
}
void init(Node L)
{
    for (int i = 0; i < maxsize - 1; i++)
    {
        L[i].cur = i + 1;//將每個(gè)數(shù)組分量鏈接到一起,最后一個(gè)元素指向的是尾節(jié)點(diǎn)
    }
    L[maxsize - 1].cur = 0;//備用鏈表的最后一個(gè)空元素的cur指向0缰趋，這一行不能省捧杉。
}
int getlength(Node L)
{
    int i = L[maxsize - 1].cur;//從倒數(shù)第一個(gè)數(shù)據(jù)域元素開始遍歷，很想單鏈表的
    int j = 0;
    while (i)
    {
        j++;
        i = L[i].cur;//相當(dāng)于就是p = p->next
    }
    return j;
}
int get(Node L)//新插入一個(gè)元素之后需要重新修改L[0].cur的值
{
    //若備用鏈表非空秘血，則返回分配的結(jié)點(diǎn)下標(biāo)味抖，否則返回 0（當(dāng)分配最后一個(gè)結(jié)點(diǎn)時(shí)，該結(jié)點(diǎn)的游標(biāo)值為 0）即特點(diǎn)3的體現(xiàn)
    int i = L[0].cur;//獲取可以插入的位置 
    if (i)//如果不是空表
    {
        L[0].cur = L[i].cur;//更新L[0]為剛才插入位置的cur灰粮，用來記錄當(dāng)前鏈表新的可插入位置 
    }
    return i;//返回可插入位置 
}
void insert(Node L, int i, char newdata)
{
    if (i<1 || i>getlength(L) + 1)//判斷插入點(diǎn)是否合理
    {
        exit(1);
    }
    //找可插入的地方 
    int j = get(L);// Ｗ猩！粘舟！修改了上文說的第一個(gè)數(shù)红柱，文章見鏈接
    int k = maxsize - 1; //找鏈表頭 
    if (j)
    {//定位到插入的位置的前一個(gè)位置k 
        for (int l = 1; l <= i - 1; l++)
        {
            k = L[k].cur;//相當(dāng)于就是p = p->next
        }
        //插入操作 
        L[j].data = newdata;
        L[j].cur = L[k].cur;
        L[k].cur = j;
    }
}
void Free(Node L, int k)
{
    L[k].cur = L[0].cur;//這應(yīng)該是游標(biāo)不能重復(fù)，換一下
    L[0].cur = k;//被刪除元素已經(jīng)變成了備用鏈表的第一個(gè)節(jié)點(diǎn)了
}
//刪除第i個(gè)元素

bool Delete(Node L, int i, char* key)
{
    if (i < 1 || i > getlength(L))
    {
        return false;
    }
    //找鏈表頭 
    int k = maxsize - 1;
    //定位到刪除的地方的前一個(gè) 
    for (int l = 1; l <= i - 1; l++)
    {
        k = L[k].cur;
    }
    int j = L[k].cur;//由k找到j(luò)蓖乘，像鏈表的next域锤悄，上一個(gè)找到下一個(gè)的尋法
    *key = L[j].data;
    L[k].cur = L[j].cur;//換一下游標(biāo)免得重復(fù)
    Free(L, j);
    return true;
}

//遍歷
void Traverse(Node L)
{
    int k = maxsize - 1;
    while (L[k].cur)
    {
        k = L[k].cur;
        cout<<L[k].data<<" ";
    }
    printf("\n");
}