Aotle

你所看到的惊鸿，都曾被平庸磨练

Aotle

数据结构之线性表

概念

线性表是数据结构中最简单的数据存储结构，可以理解为“线性的表”。

线性，是说数据在逻辑结构上具有线性关系。将具有线性关系的数据存储到计算机中所使用的存储结构称为线性表。

  • 首先是一个序列
  • 其次是有限的
  • 存储的数据本身的类型一定保持相同。
  • 线性表的开始元素没有前驱元素只有后继元素，线性表的结束元素没有后继元素只有前驱元素，除了开头元素和结尾元素以外，每个元素都有且只有一个前驱元素和后继元素。
  • 数据一旦用线性表存储，各个数据元素之间的相对位置就固定了。

存储结构

线性表的存储结构有顺序存储结构和链式存储结构两种，前者称为顺序表，后者称为链表。

顺序存储结构

顺序表就是把线性表中的所有元素按照某种逻辑顺序，依次存储到从指定位置开始的一块连续的存储空间，重点是连续的存储空间。

数组长度和线性表的长度区别：数组长度是存放线性表的存储空间的长度，存储分配后这个量一般是不变的，线性表的长度是线性表中数据元素的个数，随着线性表插入和删除操作的进行，这个量是变化的。

  • 在顺序表中，各个表项的逻辑顺序与其存放的物理顺序一致，即第i个表项存储于第i个物理位置（1<i≤n）。
  • 对顺序表中所有表项，既可以进行顺序访问，也可以进行随机访问。也就是说，既可以从表的第一个表项开始逐个访问表项，也可以按照表项的序号（亦称为下标）直接访问表项。

顺序表的静态存储表示：

1
2
3
4
5
6
#define maxSize 100
typedef int T;
typedef struct{
T data[maxSize];
int n;
}SeqList;

顺序表的动态存储表示：

1
2
3
4
5
typedef int T;
typedef struct{
T* data;
int maxSize，n;
}SeqList;

顺序表搜索算法：

1
2
3
4
5
6
7
8
9
template <class T>
int Seqlist<T>::search(T& x){
//搜索函数，在表中找到x，找到则返回元素位置，否则返回0
//last表示最后一个元素的数组标号，从0开始，表项是从1开始
    for(int i=0;i<=last;++i){
        if(data[i]==x) return i+1;
    }
    return 0;
}

顺序表插入算法：

1
2
3
4
5
6
7
8
9
10
11
12
template <class T>
bool Seqlist<T>::insert(int i,T& x){
//将新元素插入到表第i个元素之后，函数返回true，否则返回false
    if(last==maxsize-1)return false;
    if(i<0||i>last+1)return false;
    for(int j=last;j>=i;j--){
        data[j+1]=data[j];
    }
    data[i]=x;
	last++;
    return true;
}

顺序表删除算法：

1
2
3
4
5
6
7
8
9
10
11
12
template <class T>
bool Seqlist<T>::remove(int i,T& x){
//删除第i个表项，通过x返回删除的元素值，成功返回true
    if(last==-1)return false;
    if(i<1||i>last+1)return false;
    x=data[i-1];
    for(int j=i;j<=last;j++){
        data[j-1]=data[j];
    }
    last--;
    return true;
}

链式存储结构

链表，别名链式存储结构或单链表，用于存储逻辑关系为 “一对一” 的数据。与顺序表不同，链表不限制数据的物理存储状态，换句话说，使用链表存储的数据元素，其物理存储位置是随机的。线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的，这就意味着这些数据元素可以存在内存未被占用的任意位置。还有一点就是在顺序存储结构中，每个数据空间只需要存储数据元素的信息即可，但是在链式结构中，除了要存储数据元素信息外，还需要存储他的后继元素的存储位置。我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域，指针域中存储的信息称为指针或链，数据域和指针域组成数据元素的存储映像，称为结点。

单链表

单链表的定义
1
2
3
4
5
6
7
8
9
struct linknode{
	int data;
	linknode* link;
};
class list{
    private:
    	linknode* first;
    public:
};
单链表的查找算法
1
2
3
4
5
6
7
8
9
10
template <class T>
linknode<T>* list<T>::search(T X){
    //成功的时候返回地址，否则返回null
    linknode<T>* current = first->link;//带附加头结点
    while(current!=null){
        if(current->data==x)break;
        else current=current->link;
    }
    return current;
}
单链表的插入算法
1
2
3
4
5
6
7
8
9
10
11
template <class T>
bool list<T>::inscrt(int i,T& X){
    //将新元素插入i结点之后
    linknode<T> *current = locate(i);//return i address
    if(current==null)return false;
    linknode<T> *newnode = new linknode<T>(x);
    if(newnode==null){cerr<<"error"<<endl;exit(1)}
    newnnode->link=current->link;
    current->link=newnode;
    return true;
}
单链表的删除算法
1
2
3
4
5
6
7
8
9
10
11
template <class T>
bool list<T>::remove(int i,T& X){
    //将第i个元素删除，x返回被删除的值
    linknode<T> *current = locate(i-1);//return i-1 address
    if(current==null||current->link==null)return false;
    linknode<T> *del = current->link;
    x=del->data;
    current->link=del->link;
    delete del;
    return true;
}

循环链表

循环链表（circular list）是另一种形式的表示线性表的链表，它的结点结构与单链表相同，与单链表不同的是链表中表尾结点的link域中不是NULL，而是存放了一个指向链表开始结点的指针。这样，只要知道表中任何一个结点的地址，就能遍历表中其他任一结点。

双向链表

双向链表又称为双链表。使用双向链表（doubly linked list）的目的是为了解决在链表中访问直接前驱和直接后继的问题。因为在双向链表中每个结点都有两个链指针，一个指向结点的直接前驱，一个指向结点的直接后继，这样不论是向前驱方向搜索还是向后继方向搜索，其时间开销都只有O(1)。

静态链表

如果为数组中每一个元素附加一个链接指针，就形成静态链表结构。它允许我们不改变各元素的物理位置，只要重新链接就能够改变这些元素的逻辑顺序。由于它是利用数组定义的，在整个运算过程中存储空间的大小不会变化，因此称之为静态链表。
静态链表的每个结点由两个数据成员构成：data域存储数据，link域存放链接指针。所有结点形成一个结点数组。

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：http://aotle.top/2020/06/29/xianxingbiao1/

评论