数据结构学习之——线性表网站首页 其他

数据结构学习之——线性表

fly2022. 2024-06-26 14:23:43

简介数据结构学习之——线性表

1、线性表的定义和基本操作

1.1、线性表的定义

线性表是具有相同数据类型的n个数据元素的有限序列，其中n为表长，当n=0时线性表是一个空表。若以L命名，则表示为
$L=left(a_{1}, a_{2,},cdots, a_{i}, a_{i+1}, cdots, a_{n} ight)$
$a_{1}$ 是唯一的“第一个”元素，又称表头元素； $a_{n}$ 是唯一的“最后一个”元素，又称表尾元素除第一个元素外，每个元素有且仅有一个直接前驱。除最后一个元素外，每个元素有且仅有一个直接后继。

线性表的特性：

表中元素的个数有限。
表中元素具有逻辑上的顺序性，表中元素有其先后次序。
表中元素都是数据元素，每个元素都是单个元素。
表中元素的数据类型都相同，这意味着每个元素占有相同大小的存储空间。
表中元素具有抽象性，即仅讨论元素间的逻辑关系，而不考虑元素究竟表示什么内容。

注意：线性表是一种逻辑结构，表示元素之间一对一的相邻关系。根据存储结构的不同可分为顺序表和链表。

1.2、线性表的基本操作

InitList(&L):初始化表。构造一个空的线性表。
Length (L)：求表长。返回线性表L的长度，即L中数据元素的个数。
LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的元素。
GetElem(L,i):按位查找操作。获取表L中第i个位置的元素的值。
Listinsert (&L, i, e)：插入操作。在表L中的第i个位置上插入指定元素e。
ListDelete (&L, i, &e):删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。
PrintList(L)：输出操作。按前后顺序输出线性表L的所有元素值。
Empty (L):判空操作。若L为空表，则返回true,否则返回false。
DestroyList(&L)：销毁操作。销毁线性表，并释放线性表L所占用的内存空间。

2、线性表的顺序表示

2.1、顺序表的定义

定义：线性表的顺序存储又称顺序表。它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。

位序：第1个元素存储在线性表的起始位置,第i个元素的存储位置后面紧接着存储的是第i+1个元素，称i为元素 $a_{i}$ 在线性表中的位序。因此，顺序表的特点是表中元素的逻辑顺序与其物理顺序相同。

线性表的顺序存储如下所示：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-5yu7FLsk-1685022761721)(./2_1.png)]

随机存储：每个数据元素的存储位置都和线性表的起始位置相差一个和该数据元素的位序成正比的常数，因此，顺序表中的任意一个数据元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。通常用高级程序设计语言中的数组来描述线性表的顺序存储结构。

内存分配方式：一维数组的内存分配方式有静态分配和动态分配。在静态分配时，由于数组的大小和空间事先已经固定，一旦空间占满，再加入新的数据就会产生溢出，进而导致程序崩溃。而在动态分配时，存储数组的空间是在程序执行过程中通过动态存储分配语句分配的，一旦数据空间占满，就另外开辟一块更大的存储空间，用以替换原来的存储空间，从而达到扩充存储数组空间的目的，而不需要为线性表一次性地划分所有空间。

特点：

顺序表最主要的特点是随机访问,即通过首地址和元素序号可在时间0(1)内找到指定的元素。
顺序表的存储密度高，每个结点只存储数据元素。
顺序表逻辑上相邻的元素物理上也相邻，所以插入和删除操作需要移动大量元素。

2.2、顺序表基本操作实现

#define InitSize 50                             //定义线性表的最大长度
typedef struct {
    int *data;                                  //指示动态分配数组的指针
    int length;                                 //数组的当前个数
}List;

void InitList(List &list) {                     //初始化表。构造一个空的线性表。
    list.data = new int[InitSize];              //初始动态内存分配
    list.length = 0;                            //初始当前长度
}

int Length(List list) {                         //求表长。返回线性表L的长度，即L中数据元素的个数。
    return list.length;                         //获取当前长度
}

int LocateElem(List list, int e) {              //按值查找操作。在表L中查找具有给定关键字值的元素。
    for (int i = 0; i < list.length; i++) { 
        if (list.data[i] == e) return i + 1;    //查找成功，返回位序
    }
    return 0;                                   //查找失败，返回0
}

int GetElem(List list, int i) {                 //按位查找操作。获取表L中第i个位置的元素的值。
    return list.data[i - 1];
}

bool ListInsert(List& list, int i, int e) {     //插入操作。在表L中的第i个位置上插入指定元素e。
    if (i<1 || i>list.length + 1) return false; //判断i的范围是否有效
    if (list.length >= InitSize) return false;  //当前存储空间己满，不能插入
    for (int j = list.length; j >= i; j--)      //将第i个元素及之后的元素后移
        list.data[j] = list.data[j - 1];
    list.data[i - 1] = e;                       //在位置i处放入e
    list.length++;                              //线性表长度加1
    return true;
}

bool ListDelete(List& list, int i, int& e) {    //删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。
    if (i<1 || i>list.length) return false;     //判断i的范围是否有效
    e = list.data[i - 1];                       //将被删除的元素赋值给e
    for (int j = i; j < list.length; j++)       //将第i个位置后的元素前移
        list.data[j - 1] = list.data[j];
    list.length--;                              //线性表长度减1
    return true;
}

void PrintList(List list) {                     //输出操作。按前后顺序输出线性表L的所有元素值。
    for (int i = 0; i < list.length; i++) {     //循环输出线性表元素值
        cout << list.data[i] << " ";
    }
    cout << endl;
}

bool Empty(List list) {                         //判空操作。若L为空表，则返回true,否则返回false。
    return list.length == 0;
}

void DestroyList(List& list) {                  //销毁操作。销毁线性表，并释放线性表L所占用的内存空间。
    free(list.data);
    list.length = 0;
}

时间复杂度：

按值查找（顺序查找）： $O (n)$
按位查找： $O (1)$
插入操作： $O (n)$
删除操作： $O (n)$

3、线性表的链式表示

3.1、单链表的定义

定义：线性表的链式存储又称单链表，它是指通过一组任意的存储单元来存储线性表中的数据元素。为了建立数据元素之间的线性关系，对每个链表结点，除存放元素自身的信息外，还需要存放一个指向其后继的指针。

优缺点：利用单链表可以解决顺序表需要大量连续存储单元的缺点，但单链表附加指针域，也存在浪费存储空间的缺点。由于单链表的元素离散地分布在存储空间中，所以单链表是非随机存取的存储结构，即不能直接找到表中某个特定的结点。查找某个特定的结点时，需要从表头开始遍历，依次查找。

表示方式：通常用头指针来标识一个单链表，如单链表Z，头指针为NULL时表示一个空表。此外，为了操作上的方便，在单链表第一个结点之前附加一个结点，称为头结点。头结点的数据域可以不设任何信息，也可以记录表长等信息。头结点的指针域指向线性表的第一个元素结点。

头结点和头指针的区分:不管带不带头结点，头指针都始终指向链表的第一个结点，而头结
点是带头结点的链表中的第一个结点，结点内通常不存储信息。

3.2、单链表基本操作的实现（带头节点）

typedef struct LNode {                      //定义单链表节点类型
    int data;                               //数据域
    struct LNode* next;                     //指针域
}*LinkList;

LinkList List_HeadInsert(LinkList& L) {     //头插法
    LNode* s;
    int x;
    L = (LinkList)malloc(sizeof(LNode));    //创建头节点
    L->next = NULL;                         //初始为空链表
    cin >> x;                               //输入结点的值
    while (x != 9999) {
        s = (LinkList)malloc(sizeof(LNode));//创建新结点
        s->data = x;
        s->next = L->next;
        L->next = s;                        //将新节点插入表中，L为头指针
        cin >> x;
    }
    return L;
}

LinkList List_TailInsert(LinkList& L) {    //尾插法
    int x;
    L = (LinkList)malloc(sizeof(LNode));
    LNode* s, * r = L;                     //r为表尾指针
    cin >> x;
    while (x != 9999) {
        s = (LinkList)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;                       //r指向新的表尾结点
        r = s;
        cin >> x;
    }
    r->next = NULL;                        //尾结点指针置空
    return L;
}

LNode* GetElem(LinkList L, int i) {        //单链表按序号查找节点
    if (i < 1) return NULL;                //若i无效，则返回NULL
    int j = 1;                             //计数，初始为1
    LNode* p = L->next;                    //第1个结点指针赋给p
    while (p != NULL && j < i) {           //从第一个结点开始找，查找第i个结点
        p = p->next;
        j++;
    }
    return p;                              //返回第i个结点的指针，若i大于表长，则返回NULL
}

LNode* LocateElem(LinkList L, int e) {     //按值查找表结点
    LNode* p = L->next;
    while (p != NULL && p->data != e)      //从第1个结点开始查找data为e的结点
        p = p->next;
    return p;                              //找到返回结点指针，否则返回NULL
}

bool ListInsert(LinkList L, int i, int e) {//插入操作，在第i个位置插入data为e的结点
    LNode* p = GetElem(L, i);              //查找到第i个结点
    LNode* s;
    if (p == NULL) {
        p = GetElem(L, i - 1);             //不存在第i-1和i个结点
        if (p == NULL) return false;
        s->data = e;                       //最后一个结点是第i-1个结点，插入到尾端
        s->next = NULL;
        p->next = s;
        return true;
    }
    s = (LinkList)malloc(sizeof(LNode));   
    s->data = p->data;                     //使用前插法将元素插入到第i个结点
    s->next = p->next;
    p->data = e;
    p->next = s;
    return true;
}

bool ListDelete(LinkList L, int i) {       //删除操作，删除第i个位置的结点
    LNode* p = GetElem(L, i);              //查找到第i个结点
    if (p == NULL) return false;
    LNode* s = p->next;
    p->data = s->data;                     //将p结点的后续结点的data复制到p结点的data
    p->next = s->next;                     //令p结点指向后续结点的后续结点
    free(s);                               //释放
}

int Length(LinkList L) {                   //求表长。返回单链表表L的长度，即L中数据元素的个数。
    int l = 0;                             //初始化为0
    LNode* p = L->next;
    while (p != NULL) {                    //循环遍历单链表,计算表长
        l++;                               //长度加一
        p = p->next;
    }
    return l;                              //返回表长
}

时间复杂度：

头插法： $O (n)$
尾插法： $O (n)$
按序号查找结点： $O (n)$
按值查找结点： $O (n)$
插入操作： $O (n)$
删除操作： $O (n)$
求表长操作： $O (n)$

3.3、双链表

双链表在单链表的结点中增加了一个指向其前驱的prior指针，因此双链表中的按值查找和按位查找的操作与单链表的相同。但双链表在插入和删除操作的实现上，与单链表有着较大的不同。这是因为"链”变化时也需要对prior指针做出修改，其关键是保证在修改的过程中不断链。此外，双链表可以很方便地找到其前驱结点，因此，插入、删除操作的时间复杂度仅为0(1)。

注意：双链表的插入和删除要同时注意前驱和后驱指针的修改。

3.4、循环链表

循环单链表：循环单链表和单链表的区别在于，表中最后一个结点的指针不是NULL,而改为指向头结点，从而整个链表形成一个环，在循环单链表中，表尾结点r的next域指向L,故表中没有指针域为NULL的结点，因此，循环单链表的判空条件不是头结点的指针是否为空，而是它是否等于头指针。

循环双链表：由循环单链表的定义不难推出循环双链表。不同的是在循环双链表中，头结点的prior指针还要指向表尾结点，在循环双链表L中，某结点p为尾结点时，p->next==L；当循环双链表为空表时，其头结点的prior域和next域都等于L。

注意：循环链表需要注意的是其表空时头节点的指针指向。

3.5、静态链表

定义：静态链表借助数组来描述线性表的链式存储结构，结点也有数据域data和指针域next,
与前面所讲的链表中的指针不同的是，这里的指针是结点的相对地址(数组下标)，又称游标。和顺序表一样，静态链表也要预先分配一块连续的内存空间。静态链表以next==-l作为其结束的标志。静态链表的插入、删除操作与动态链表的相同,只需要修改指针，而不需要移动元素。

3.6、顺序表和链表的比较

存取方式：顺序表可以顺序存取，也可以随机存取，链表只能从表头顺序存取元素。
逻辑结构和物理结构：采用顺序存储时，逻辑上相邻的元素，对应的物理存储位置也相邻。而采用链式存储时，逻辑上相邻的元素，物理存储位置不一定相邻，对应的逻辑关系是通过指针链接来表示的。
查找、插入和删除：对于按值查找，顺序表无序时，两者的时间复杂度均为 $O (n)$ ；顺序表有序时，可采用折半查找，此时的时间复杂度为 $O(log_{2}n)$ 。对于按序号查找，顺序表支持随机访问，时间复杂度仅为 $O (1)$ ，而链表的平均时间复杂度为 $O (n)$ 。顺序表的插入、删除操作，平均需要移动半个表长的元素，时间复杂度为 $O (n)$ 。链表的插入、删除操作，只需修改相关结点的指针域即可。
空间分配：顺序存储在静态存储分配情形下，一旦存储空间装满就不能扩充，若再加入新元素，则会出现内存溢出，因此需要预先分配足够大的存储空间。预先分配过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。动态存储分配虽然存储空间可以扩充，但需要移动大量元素，导致操作效率降低，而且若内存中没有更大块的连续存储空间，则会导致分配失败。链式存储的结点空间只在需要时申请分配，只要内存有空间就可以分配，操作灵活、高效。