小惠珠哦

这个屌丝很懒，什么也没留下！

热门标签

大话数据结构--线性表

作者：小惠珠哦 | 2024-07-09 05:52:21

踩

大话数据结构--线性表

线性表的顺序存储结构，说白了，和刚才的例子一样，就是在内存中找了块地儿，通过占位的形式，把一定内存空间给占了，然后把相同数据类型的数据元素依次存放在这块空地中。既然线性表的每个数据元素的类型都相同，所以可以用C语言(其他语言也相同)的一维数组来实现顺序存储结构，即把第一个数据元素存到数组下标为0的位置中，接着把线性表相邻的元素存储在数组中相邻的位置。

为了建立一个线性表，要在内存中找块地，于是这块地的第一个位置就非常关键，它是存储空间的起始位置。

代码比较简单就不写出来了，截图好了。

这里，我们就发现描述顺序存储结构需要三个属性:

存储空间的起始位置: 数组data,它的存储位置就是存储空间的存储位置。

线性表的最大存储容量:数组长度MaxSize。

线性表的当前长度: length。

3.3.3数据长度与线性表长度区别

数组的长度是存放线性表的存储空间的长度，存储分配后这个量是一般是不变的

线性表的长度是线性表中数据元素的个数，随着线性表插入和删除操作的进行，

这个量是变化的。

在任意时刻，线性表的长度应该小于等于数组的长度。

3.3.4 地址计算方法

由于我们数数都是从1开始数的，线性表的定义也不能免俗，起始也是1,可C 语言中的数组却是从0开始第一个下标的，于是线性表的第i个元素是要存储在数组下标为i-1的位置，即数据元素的序号和存放它的数组下标之间存在对应关系

其实，内存中的地址，就和图书馆或电影院里的座位一样，都是有编号的。**存储器中的每个存储单元都有自己的编号,这个编号称为地址。当我们占座后，占座的第一个位置确定后，后面的位置都是可以计算的。**试想一下，我是班级成绩第五名，我后面的10名同学成绩名次是多呢?当然是6, 7, …15，因为5 +1，5+2, .，. 5+ 10。由于每个数据元素，不管它是整型、实型还是字符型，它都是需要占用一定的存储单元空间的。假设占用的是c个存储单元，那么线性表中第i+1个数据元素的存储位置和第i个数据元素的存储位置满足下列关系(LOC表示获得存储位置的函数)。

LOC(ai)= LOC(ai)+c

所以对于第i个数据元素a的存储位置可以由a1推算得出:

LOC(ai)= LOC(ai)+(i-1)*c

用图更好理解呢！

通过这个公式，你可以随时算出线性表中任意位置的地址，不管它是第一个还是最后一个，都是相同的时间。那么我们对每个线性表位置的存入或者取出数据，对于计算机来说都是相等的时间，也就是一个常数，因此用我们算法中学到的时间复杂度的概念来说，它的存取时间性能为0(1)。 我们通常把具有这一特点的存储结构称为随机存取结构。

3.4 顺序存储结构的插入与删除

===============================================================================

3.4.1 获得元素操作

对于线性表的顺序存储结构来说，如果我们要实现GetElem 操作，即将线性表L中的第i个位置元素值返回，其实是非常简单的。就程序而言，只要i的数值在数组下标范围内，就是把数组第i-1下标的值返回即可。来看代码:

#define OK 1

#define ERROR 0

#define TRUE 1

#define FALSE 0

typedef int Status;

/Status是函数的类型，其值是函数结果状态代码，如OK等/

/*初始条件:顺序线性表L已存在，1≤i≤ListLength(L) */

/操作结果:用e返回L中第i个数据元素的值/

Status GetElem (SqList L,int i,ElemType *e)

{

if (L.1ength==01I 1<1 11 i>L.length)

return ERROR;

*e=L.data[i-1] ;

return OK;

}

注意这里返回值类型Status 是-一个整型，返回OK代表1, ERROR代表0。之后代码中出现就不再详述。

3.4.2 插入操作

刚才我们也谈到，这里的时间复杂度为0(1)。我们现在来考虑，如果我们要实现ListInsert (*L,e),即在线性表L中的第i个位置插入新元素e，应该如何操作?

插入算法的思路:

如果插入位置不合理，抛出异常;

如果线性表长度大于等于数组长度，则抛出异常或动态增加容量;

从最后一个元素开始向前遍历到第i个位置,分别将它们都向后移动一个位置;

将要插入元素填入位置i处;

表长加1。

/初始条件:顺序线性表L已存在，1≤i≤ListLength(L)，/

/操作结果:在L中第i个位置之前插入新的数据元素e, L的长度加1/

Status ListInsert (SqList *L,int i, ElemType e)

{

int k;

if (L->length==MAXSIZE) /顺序线性表已经满/

return ERROR;

if(i<1 || i>L->length+1) /当i不在范围内时/

return ERROR;

if (i<=L->length) /若插入数据位置不在表尾/

{

for (k=L->length-l;k>=i-1;k–)/将要插入位置后数据元素向后移动一位/

L->data[k+1]-L->data[k];

}

L->data[i-1]=e; /将新元素插入/

L-> length++;

return OK;

}

3.4.3 删除操作

书上讲的例子很有意思，哈哈哈哈！！！

删除算法的思路:

如果删除位置不合理，抛出异常;

取出删除元素;

从删除元素位置开始遍历到最后-一个元素位置，分别将它们都向前移动一个位置;

表长减1

/初始条件:顺序线性表L已存在，1≤i≤ListLength(L)，/

/操作结果:删除在L中第i个数据元素，并用e返回其值, L的长度减1/

Status ListDelete(SqList *L,int i, ElemType *e)

{

int k;

if (L->length==0) /顺序线性表已经满/

return ERROR;

if(i<1 || i>L->length+1) /当i不在范围内时/

return ERROR;

if (i<=L->length) /若数据位置不在表尾/

{

for (k = i;k < L->length;k++)/将要插入位置后数据元素向后移动一位/

L->data[k+1]-L->data[k];

}

L->data[i-1]=e; /将新元素插入/

L-> length++;

return OK;

}

下面讨论下时间复杂度

当要插入或删除的元素在最后一个位置，那么时间复杂度为O（1），因为不需要移动元素

最坏的情况当然是插入或删除第一个元素，此时所有的元素都要向后移，时间复杂度为O（n）

以上平均下来，为（n-1）/2

通过前面讨论过时间复杂度的推导，可以得出，平均时间复杂度还是0[n)。这说明什么?线性表的顺序存储结构，在存、读数据时，不管是哪个位置，时间复杂度都是0(1);而插入或删除时，时间复杂度都是0[n)。**这就说明，它比较适合元素个数不太变化，而更多是存取数据的应用。**当然，它的优缺点还不只这些…

3.4.4 线性表顺序存储结构的优缺点

3.5 线性表的链式存储结构

=============================================================================

3.5.1 顺序存储结构不足的解决办法

前面讲的线性表的顺序存储结构。它是有缺点的，最大的缺点就是插入和删除时需要移动大量元素，这显然就需要耗费时间。能不能想办法解决呢?

为什么当插入和删除时，就要移动大量元素，仔细分析后，发现原因就在于相邻两元素的存储位置也具有邻居关系，他们在内存中也是挨着的，中级没有空袭，当然就无法快速介入，而删除后，当中就会留出空隙，自然需要弥补。

干脆所有元素都不要考虑相邻位置了，哪里有空位就到哪里，而只是让每个元素知道它下一个元素的位置，这样就可以在第一个元素时，就知道第二个元素的位置（内存地址），在第二个元素时，再找到第三个的位置（内存地址）

3.5.2线性表链式存储结构定义

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。这就意味着，这些数据元素可以存在内存未被占用的任意位置

以前在顺序结构中，每个数据元素只需要存数据元素信息就可以了。现在链式结构中,除了要存数据元素信息外，还要存储它的后继元素的存储地址。

1.数据域和指针域

因此，为了表示每个数据元素ai 与其直接后继数据元素ai+1 之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息(即直接后继的存储位置)。我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称做指针或链。这两部分信息组成数据元素ai的存储映像，称为结点(Node)。

书上说的太好了，看书真的比看视频更有收获！！！

同学们，快去看书吧！

n个结点(a的存储映像)链结成一个链表,即为线性表(a1, a2, an)的链式存储结构，因为此链表的每个结点中只包含一个指针域，所以叫做单链表。单链表正是通过每个结点的指针域将线性表的数据元素按其逻辑次序链接在一起

2.头指针

对于线性表来说，总得有个头有个尾，链表也不例外。我们把链表中第一个结点的存储位置叫做头指针，那么整个链表的存取就必须是从头指针开始进行了。之后的每一个结点，其实就是上一个的后继指针指向的位置。想象一下，最后一个结点，它的指针指向哪里?最后一个，当然就意味着直接后继不存在了，所以我们规定，线性链表的最后一个结点指针为“空”(通常用NULL或“^”符号表示)。

有时，我们为了更加方便地对链表进行操作，**会在单链表的第一个结点前附设一个结点，称为头结点。**头结点的数据域可以不存储任何信息，谁叫它是第一个呢，有这个特权。也可以存储如线性表的长度等附加信息，头结点的指针域存储指向第一个结点的指针

3.5.3 头指针与头结点的异同

异同点如下：

3.5.4 线性表链式存储结构代码描述

/线性表的单链表存储结构/

typedef struct Node

{

ElemType data;

struct Node *next;

} Node;

typedef struct Node *LinkList; /定义 LinkList/

从这个结构定义中,我们也就知道，结点由存放数据元素的数据域和存放后继结点地址的指针域组成。

假设p是指向线性表第i个元素的指针，则该结点ai的数据域我们可以用p->data来表示，p->data的值是一个数据元素，结点ai的指针域可以用p->next来表示，p->next 的值是一个指针。p->next指向谁呢?当然是指向第i+1个元素，即指向ai+1 的指针也就是说，如果p->data=ai,那么p->next->data=ai+1

上面这段话需要反复咀嚼！！！甚至自己可以拿笔画一下，多画几次就记住了~

p指针一个结点，相当于干了两件事

分别是指向了结点的数据域与和指针域

指向数据域是p->data

指向指针域是指针域里本来有个指针，p呢，它又指向这个指针，这个指针呢有指向下一个结点的data所以就有了上面这个图

以此类推

太详细了有木有啊~！！！

3.6 单链表的读取

=========================================================================

在线性表的顺序存储结构中，我们要计算任意-一个元素的存储位置是很容易的。但在单链表中，由于第i个元素到底在哪?没办法-开始就知道，必须得从头开始找。因此，对于单链表实现获取第i个元素的数据的操作GetElem,在算法上，相对要麻烦一些。

获得链表第i个数据的算法思路:

1.声明一个结点p指向链表第一个结点，初始化j从1开始;

2.当j<i时，就遍历链表，让p的指针向后移动，不断指向下一结点，j 累加1;

3.若到链表末尾p为空，则说明第i个元素不存在;

4.否则查找成功，返回结点p的数据。.

/*初始条件:顺序线性表L已存在，1≤i≤ListLength (L) */

/操作结果:用e返回L中第i个数据元素的值/

Status GetElem ( LinkList L,int i, ElemType*e)

{

int j;

LinkList P; /声明一结点 p/

P= L->next; /让p指向链表L的第一个结点/

j=1; /j为计数器/

while (p && j<i) /p不为空或者计数器j还没有等于i时，循环继续/

{

p= p->next; /让p指向下一个结点/

++j;

}

if (!pHI j>i )

return ERROR; /第i个元素不存在/

*e = p->data; /取第i个元素的数据/

return OK;

}

说白了，就是从头开始找，直到第i个元素为止。由于这个算法的时间复杂度取

决于i的位置，当i=1时，则不需遍历，第一个就取出数据了，而当i=n时则遍历n-1次才可以。因此最坏情况的时间复杂度是O(n)。

由于单链表的结构中没有定义表长，所以不能事先知道要循环多少次，因此也就不方便使用for来控制循环。其主要核心思想就是‘工作指针后移”，这其实也是很多算法的常用技术。

3.7 单链表的插入与删除

============================================================================

3.7.1 单链表的插入

先来看单链表的插入。假设存储元素e的结点为s,要实现结点p、p->next 和s .

之间逻辑关系的变化，只需将结点s插入到结点p和p->next之间即可。可如何插入呢?

根本用不着惊动其他结点，只需要让s->next和p->next的指针做一点改变即可。

s->next=p->next; p->next=s;

就是说让p的后继节节点改成s的后继节点，再把s变成p的后继节点

这段话需要多去体会，看不懂的可以再往前复习一下！很久好理解的

如果先p->next = s;再s->next= p->next行不行呢？

不行哦，因为第一句会使得p->next给覆盖成s的地址了。那么s->next = p->next，其实就等于s->next = s

这一点要是不懂的话一定要自己画个图，然后再写上过程

对于单链表的表头和表尾的特殊情况，操作是相同的

单链表第i个数据插入结点的算法思路:

1.声明一结点p指向链表第一个结点，初始化j从1开始;

2.当j<i时，就遍历链表，让p的指针向后移动，不断指向下一-结点，j累加1;

3.若到链表末尾p为空，则说明第i个元素不存在;

4.否则查找成功，在系统中生成-一个空结点s;

5.将数据元素e赋值给s->data;

6.单链表的插入标准语句s->next=p->next p->next=s;

7.返回成功。

代码实现：

#include <stdio.h>/*初始条件:顺序线性表L已存在，1≤i≤ListLength (L)，/操作结果: 在L中第1个位置之前插入新的数据元素 e,L的长度加 1/Status ListInsert(LinkList *L, int i, ElemType e){ int j; LinkList p, s; p = *L; j = 1; while (p && j < i) //寻找第i个结点，通过让p指针一直向后指，直到找到目标元素为止 { p = p->next; ++j; } if(!p || j > i) return ERROR; s = (LinkList)malloc(sizeof(Node));//生成新的结点 s->data = e; s->next = p->next; p->next = s; return OK; }

实际代码是执行不通的，主要是学习这个思想

核心思想就是工作指针后移

3.7.2 单链表的删除

删除结点只需要将删除结点的前驱指针绕过，指向它的后继结点即可

我们所要做的，实际上就是一步，p->next=p->next>next, 用q来取代p->next,即是

q = p->next;p->next=q->next

解读这两句代码，也就是说让p的后继的后继结点改成p的后继结点。

单链表第i个数据删除结点的算法思路

1.声明一结点p指向链表第一一个结点，初始化j从1开始

2.当j<i时，就遍历链表，让p的指针向后移动，不断指向下一个结点, j累加1

3.若到链表末尾p为空，则说明第i个元素不存在

4.否则查找成功，将欲删除的结点p->next赋值给q

5.单链表的删除标准语句p->next=q->next

6.将q结点中的数据赋值给e,作为返回

7.释放q结点

8.返回成功

代码实现

初始条件:顺序线性表L已存在，1≤i≤ListLength (L)

操作结果: 删除L中的第i个数据元素，并用e返回其值，L中的长度减1

Status ListDelete (LinkList *L, int i, ElemType *e){ int j; LinkList p,q; P = *L; j = 1; while (p->next && j< i) /遍历寻找第 i个元素/ { P = P->next; ++j; } if (!(p->next) || j > i) return ERROR; /第i个元素不存在/ q = p->next; p->next = q->next; /将q的后继赋值给p的后继/ *e= q->data; /将q结点中的数据给e/ free (q) ; /让系统回收此结点，释放内存/ return OK;}

代码看不懂的，可以再回去画一遍图

分析一下刚才我们讲解的单链表插入和删除算法，我们发现，它们其实都是由两部分组成:第一部分就是遍历查找第i个元素;第二部分就是插入和删除元素。

从整个算法来说，我们很容易推导出:它们的时间复杂度都是O(n)。如果在我们不知道第i个元素的指针位置，单链表数据结构在插入和删除操作上，与线性表的顺序存储结构是没有太大优势的。但如果，我们希望从第i个位置,插入10个元素，对于顺序存储结构意味着，每一次插入都需要移动n-i个元素，每次都是O(n)。而单链表，我们只需要在第一次时，找到第i个位置的指针，此时为0(n)，接下来只是简单地通过赋值移动指针而已，时间复杂度都是0(1)。显然，对于插入或删除数据越频繁的操作，单链表的效率优势就越是明显。

3.8 单链表的整表创建

===========================================================================

顺序存储结构的创建，其实就是一个数组的初始化，即声明一个类型和大小的数组并赋值的过程。而单链表和顺序存储结构就不一样，它不像顺序存储结构这么集中，它可以很散，是一种动态结构。对于每个链表来说，它所占用空间的大小和位置是不需要预先分配划定的，可以根据系统的情况和实际的需求即时生成。

所以创建单链表的过程就是一个动态生成链表的过程。即从空表的初始状态起，依次建立各个元素结点，并逐个插入链表

单链表整表创建的算法思路：

1.声明一结点p和计数器变量i；

2.初始化一空链表L

3.让L的头结点的指针指向null，即建立一个带头结点的单链表

4.循环：

生成一新结点赋值给p

随机生成一数字赋值给p的数据域p-》data；

将p插入到头结点与前一新结点之间

随机产生n个元素的值，建立带表头结点的单链线性表L(头插法)

void CreateListHead(LinkList *L,int n){ LinkList p; int i; srand (time(0)) ; /初始化随机数种子/ *L = (LinkList) malloc (sizeof (Node)); (*L) -> next = NULL; /先建立一个带头结点的单链表/ for(i=0; i<n; i++ ) { P = (LinkList) malloc(sizeof (Node) ); /生成新结点/ p->data = rand()%100+1; /随机生成100以内的数字/ p->next = (*L)->next; (*L)->next = p; /插入到表头/ }}

在算法代码里，最长用的是插队的办法，就是始终让新结点在第一的位置。这种算法简称为头插法

为什么新来的到第一的位置，每次把新结点都插在终端结点的后面，这种算法称之为尾插法

代码如下：

void CreateListTail(LinkList *L,int n){ LinkList p,r; int i; srand(time(0)); *L = (LinkList) malloc (sizeof(Node)); //L为整个线性表 r = *L; //*r 为指向尾部的结点; for (i = 0; i < n; i++) { p = (Node *)malloc(sizeof(Node)); //生成新结点 p->data = rand() % 100 +1; r->next = p; r = p; //将当前结点的新结点定义为终端节点 } r->next = NULL; }

注意L与r的关系，L是指整个单链表，而r是指向尾结点的变量, r会随着循环不断地变化结点，而L则是随着循环增长为一个多结点的链表。

注意啊，r是一个变量！！！

值得注意的是r->next = p；的含义，其实就算将刚才的表尾终端结点r的指针指向新结点p