当前位置:首页 > 高性能开发 > 数据结构与算法

数据结构与算法——线性表链式储存结构(静态链表)

优良自学吧提供数据结构与算法——线性表链式储存结构(静态链表),数据结构与算法——线性表链式存储结构(静态链表)今天总结静态链表. 什么是静态链表? 我理解静态链表是一种伪链表,因为它没有使用指针。静态链表使用数组实现的,这个数组是一个结构体数组,结构体由数据域和指针域构成,与单链表不同的是,这个指针域并不是指针,而是一个整数,用来指向

数据结构与算法——线性表链式存储结构(静态链表)

今天总结静态链表.

什么是静态链表?

我理解静态链表是一种伪链表,因为它没有使用指针。静态链表使用数组实现的,这个数组是一个结构体数组,结构体由数据域和指针域构成,与单链表不同的是,这个指针域并不是指针,而是一个整数,用来指向下一个结点(数组下标)。

静态链表中实际上相当于有两个链表,一个时实际数据所构成的一个链表,另一个是数组中空元素所构成的链表,称为空闲链表或备用链表,用来存放插入进来的元素。

数据结构与算法——线性表链式储存结构(静态链表)

心得:静态链表感觉比单链表,双向链表绕很多,看书的时候,书上在释放结点空间那块写的很复杂,后来和我实现的发现对不上。于是,根据静态链表的理解,原理,自己实现,可能实现方法和书上或网上的不太一样,但是我觉得思路与原理是一样的。有不对的地方,希望能给指出来,我也是才学习这一块

实现代码:

<span style="font-family:Courier New;font-size:14px;">#include <iostream>

using namespace std;
const int MAX_SIZE = 100;
template <class T>
struct StaticNode {
    T data;
    int next;
};

template <class T>
class StaticLinkList {
public:
    StaticLinkList();
    StaticLinkList(T a[],int n);
    void Insert(int i,T x);        //在位置i处插入元素a
    T Delete(int i);               //删除第i个元素,返回被删的元素值
    int Get(int i);                //查找位置为i处的元素 返回在数组中的下标
    int NewNode();                 //申请结点空间
    void DeleteNode(int i);        //释放游标i指向的结点
    void PrintStaticLinkList();    //遍历链表
    int GetLength();               //获取链表的长度
private:
    int front;
    int tail;
    StaticNode<T> SArray[MAX_SIZE];
};

template <class T>
StaticLinkList<T>::StaticLinkList() {
    front = -1;         //空链表的头指针指向-1
    tail = 0;           //未分配空间的第一个元素的下标
    for(int i=0;i<MAX_SIZE-1;i++) {
        SArray[i].next = i+1;  //每个元素的next域指向下一个元素
    }
    SArray[MAX_SIZE-1] = -1; //最后一个元素的next域设为-1
}

template <class T>
StaticLinkList<T>::StaticLinkList(T a[],int n) {
    for(int i=0;i<MAX_SIZE-1;i++) {
        SArray[i].next = i+1;
    }
    SArray[MAX_SIZE-1].next = -1;
    for(int i=0;i<n;i++) {
        SArray[i].data = a[i];
    }
    front = 0;     //头指针指向第一个起始元素
    tail = SArray[n-1].next;  //指向第一个未分配空间的元素
    SArray[n-1].next = -1;   //将最后一个元素的next域设为-1

}

template <class T>
void StaticLinkList<T>::PrintStaticLinkList() {
    int k;
    if(front!=-1)   //front不为-1 链表非空 将当前头指针赋给k
         k = front;
    while(SArray[k].next!=-1) {
        cout<<SArray[k].data<<" ";
        k = SArray[k].next;
    }
    cout<<SArray[k].data;  //将next域等于-1的元素打印出来 即就是最后一个元素
    cout<<endl;
}

template <class T>
void StaticLinkList<T>::Insert(int i,T x) {
       int k = front;
       for(int j=1;j<i-1;j++) {
         k = SArray[k].next;
       }
       int p = NewNode();  //申请一个空间 实质是将第一个空闲空间的数组下标取出来
       SArray[p].data = x;
       SArray[p].next = SArray[k].next;
       SArray[k].next = p;
}


/**
    申请空间 该方法返回第一个为分配空间的元素的下标
*/
template <class T>
int StaticLinkList<T>::NewNode() {
    if(tail==-1) throw "空间不足";
    int pos = tail;
    tail = SArray[tail].next;
    return pos;
}

template <class T>
int StaticLinkList<T>::GetLength() {
    int count = 1; //计数器
    int p ;
    //链表非空
    if(front!=-1)
        p = front;
    while(SArray[p].next!=-1) {
        count++;
        p = SArray[p].next;
    }
    return count;

}
/**
    获取指定位置元素的所在数组中的下标
    思路:
    无论元素在数组中的什么位置,我们只要遍历获取到前一个位置元素
    那么它的next域指向的就是后继元素的数组下标
*/
template <class T>
int StaticLinkList<T>::Get(int i) {
    int p = front;
    for(int j=0;j<i-1;j++) {
        p = SArray[p].next;
    }
    return p;
}

/**
    释放结点所占的空间
    这里的释放其实 是将待删结点加入到空闲链表中 并没有动用数组本身
    所做的事情还是移动游标
*/
template <class T>
void StaticLinkList<T>::DeleteNode(int i) {
    if(i<0||i>MAX_SIZE-1||front==-1) throw "释放空间错误";
    SArray[i].next = tail;
    tail = i;

}
/**
    删除结点元素 这里要做的就是移动游标 使前一个结点指向待删结点的后一个结点
*/
template <class T>
T StaticLinkList<T>::Delete(int i) {
    int p = front;
    for(int j=1;j<i-1;j++) {
        p = SArray[p].next; //当前结点的前一个结点(数组下标)
    }

    int k = SArray[p].next; //当前待删结点的数组下标
    T x = SArray[k].data;
    SArray[p].next = SArray[k].next;
    DeleteNode(k);  //释放结点 参数为待删元素所在数组的下标
    return x;
}
int main()
{
    int a[6] = {1,5,6,8,3,0};
    StaticLinkList<int> SLinkList(a,6);
    cout<<"链表长度为:"<<endl;
    cout<<SLinkList.GetLength()<<endl;
    cout<<"遍历静态链表"<<endl;
    SLinkList.PrintStaticLinkList();
    cout<<"在位置3处插入元素4"<<endl;
    SLinkList.Insert(3,4);
    SLinkList.PrintStaticLinkList();
    cout<<"获取位置3的元素所在数组的下标:"<<endl;
    cout<<SLinkList.Get(3)<<endl;
    cout<<"删除位置4的元素"<<endl;
    SLinkList.Delete(4);
    SLinkList.PrintStaticLinkList();
    cout<<"在位置4处插入元素9"<<endl;
    SLinkList.Insert(4,9);
    SLinkList.PrintStaticLinkList();
    return 0;
}
</span>



(本文来自互联网,不代表搜站(http://www.ylzx8.cn/)的观点和立场)
本站所有内容来自互联网,若本站收录的信息无意侵犯了贵司版权,请给我们来信(ylzx8cn@163.com),我们会及时处理和回复,谢谢