数据结构第三章 线性表

线性表：零个或多个数据元素的有限序列

注意：

（1）线性表是一个序列，元素之间是有顺序的，若元素存在多个，则第一个元素无前驱，最后一个元素无后继，其他每个元素都有且仅有一个前驱和后继。

（2）线性表是有限的，即元素个数是有限的。

（3）线性表元素的个数n(n>=0)定义为线性表的长度，当n=0时，称为空表。

在较复杂的线性表中，一个数据元素可以由若干个数据项组成

线性表的抽象数据类型

ADT 线性表(List)
Data
Operation
    InitList(*L);  //初始化操作，建立一个空的线性表L
	ListEmpty(L); //若线性表为空，返回true，否则返回false
	CLearList(*L); //清空线性表
	GetElem(L,i*e); //将线性表L中的第i个位置元素返回给e
	LocateElem(L,e); //在线性表L中查找与给定值e相等的元素，若查找成功，返回元素在表中的序号，否则返回0
	ListInsert(*L,i,e); //在线性表L中的第i个位置插入新元素e
	ListDelete(*L,i,*e); //删除线性表L中第i个位置元素，并用e返回其值
	ListLength(L); //返回线性表L中元素个数
endADT
1
2
3
4
5
6
7
8
9
10
11
12

上述是线性表的一些基本操作，对于不同的应用，基本操作不同，要根据实际情况使用。

例：实现两个线性表集合A和B的并集操作。即要把存在集合B中但不存在A中的数据元素插入到A中即可（也可将A中不存在元素插入B中，同理）

我们假设La表示集合A，Lb表示集合B，实现功能代码如下：

void union(List *La,List *Lb)
{
    int La_len,Lb_len,i;
    ElemType e;
    la_len = ListLength(La);  //获取线性表的长度
    lb_len = ListLength(La);
    for (i=1;i<=Lb_len;i++)
    {
        GetElem(Lb,i,e); //取Lb中第i个元素赋值给e
        if(!LocateElem(La,e,equal)) //判断La中是否存在与e相同的数据元素
            ListInsert(La,++La_len,e); //判断为真则向La插入元素
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

线性表的顺序存储结构

顺序存储定义

线性表的顺序结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素

线性表的顺序存储的结构代码：

#define MAXSIZE 20  //存储空间最大存储容量
typedef int ElemType;
typedef struct
{
	ElemType data[MAXSIZE];  //数组存储数据元素，最大值为MAXSIZE
	int length;  //线性表当前长度
}SqList;
1
2
3
4
5
6
7

由此可看出，顺序存储结构有三个属性：

• 存储空间的起始位置，数组data的存储位置就是存储空间的存储位置
• 线性表的最大存储容量：数组长度MAXSIZE
• 线性表当前长度：length

地址计算方法

存储器中每个存储单元都有自己的编号，这个编号称为地址

假设占用的是c个存储单元，那么线性表中第 i+1 个数据元素的存储位置和第 i 个数据元素的存储位置满足下列关系(LOC表示获取存储位置的函数)：
$$LOC(a_{i+1})=LOC(a_i)+c$$

$$LOC(a_{i+1})=LOC(a_1)+(i-1)c$$

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

获得元素操作

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
Status GetElem(SqList L,int i,ElemType *e)
{
	if(L.length == 0 || i < 1 || i > L.length) //判断线性表是否存在且i值合理
		return ERROR;
	*e=L.data(i-1);
	return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12

插入操作

插入算法的思路：

• 如果插入位置不合理，则抛出异常
• 如果线性表长度大于等于数组长度，则抛出异常或动态增加容量
• 从最后一个元素开始向前遍历到第i个位置，分别都将它们向后移动一个位置
• 将要插入元素填入位置i处
• 表长加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-1;k>=i-1;k--)
            L->data[k+1]=L->dat[k];
    }
    L->data[i-1]=e;
    L->length++;
    return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

删除操作

删除算法的思路：

• 如果删除位置不合理，则抛出异常
• 取出删除元素
• 从删除元素位置遍历到最后一个元素位置，分别都将它们都向前移动一个位置
• 表长减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;
    *e=L->data[i-1];
    if (i<=L->length) //若删除元素不是最后一个位置
    {
        for (k=i;k<L->length;k++)
            L->data[k-1]=L->dat[k];
    }
    L->length--;
    return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

插入和删除的时间复杂度都为O(n)

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

---

线性表的链式存储结构

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

n个结点链结成一个链表，即为线性表的链式存储结构，因为此链表中的每个结点只包含一个指针域，所以叫做单链表。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0ZLBAIFP-1595644078260)(http://myimg.zhengjc.cn/images/2020/07/24/image-20200725081016531.png)]

链表中第一个结点的存储位置叫做头指针，线性链表的最后一个结点指针为空。

为了更加方便的对链表进行操作，在单链表的第一个结点前附设一个结点，称为头结点。头结点的数据域可以不存储任何信息，也可以存储如线性表的长度等附加信息，头结点的指针域存储的是指向第一个结点的指针。

头指针和头指针的异同

线性表的链式存储的结构代码：

typedef struct Node{
    ElemType data;
    struct Node *next;
} Node;
typedef struct Node *LinkList;
1
2
3
4
5

单链表的读取

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

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

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

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

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

实现代码算法如下：

Status GetElem(LiskList 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(!p || j>i)
        return ERROR;
    *e = p->data;  //取第i个元素数据
    return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

此算法的时间复杂度为O(n)

单链表的插入与删除

单链表的插入

单链表第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. 返回成功

实现代码算法如下：

Status ListInsert(LiskList *L,int i,ElemType e)
{
    int j;
    LinkList p;  
    p=L->next;  
    j = 1; 
    while(p && j<i) //p不为空且j不等于i使，循环继续
    {
        p=p->next; //p指向下一结点
        ++j;
    }
    if(!p || j>i)
        return ERROR;
    s = (LinkList)malloc(sizeof(Node));  //生成新结点
    s->data = e;
    s->next = p->next;
    p->next = s;
    return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

单链表的删除

单链表第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. 返回成功

实现代码算法如下：

Status ListDelete(LiskList *L,int i,ElemType *e)
{
    int j;
    LinkList p,q;  
    p=*L;  
    j = 1; 
    while(p->next && j<i) 
    {
        p=p->next; //p指向下一结点
        ++j;
    }
    if(!(p->next) || j>i)
        return ERROR;
    q = p->next;
    p->next = q->next;
    *e = q->data;
    free(q);
    return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

单链表的插入和删除的时间复杂度都为O(1)

单链表的整表创建

单链表整表创建的算法思路（头插法）：

1. 声明一结点p和计数器变量i；
2. 初始化一空链表L；
3. 让L的头结点的指针指向Null，即建立一个带头结点的单链表；
4. 循环：
   • 生成一新结点赋值给p；
   • 随机生成一数字赋值给p的数据域p->data；
   • 将p插入到头结点和前一新结点之间。

实现代码算法如下：

void CreateListHead(LinkList *L,int n)
{
    LinkList p;
    int i;
    stand(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; //插入到表头
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

单链表整表创建（尾插法）：

实现代码算法如下：

void CreateListTail(LinkList *L,int n)
{
    LinkList p,r;
    int i;
    stand(time(0));  //初始化随机数种子
    *L = (LinkList)malloc(sizeof(Node));
    r = *L;
    for (i=0; i<n; i++)
    {
        p = (Node*)malloc(sizeof(Node));
        p->data = rand()%100+1;  //随机生成100以内的数字
        r->next = p;  //将表尾终端结点的指针指向新结点
        r = p; //将当前的新结点定义为表尾终端结点
    }
    r->next = NULL; //表示当前链表结束
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

单链表的整表删除

单链表的整表删除算法思路：

1. 声明一结点p和q；
2. 将第一个结点赋值给p；
3. 循环：
   • 将下一结点赋值给q；
   • 释放p；
   • 将q赋值给p。

实现代码算法如下：

Status CLearList(LinkList *L)
{
    LinkList p,q;
    p = (*L)->next;
    while(p)
    {
        q = p->next;
        free(p);
        p=q;
    }
    (*L)->next = NULL;
    return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

单链表结构与顺序存储结构优缺点

静态链表

用数组描述的链表叫做静态链表

#define MAXSIZE 1000  //存储空间最大存储容量
typedef struct
{
	ElemType data;
	int cur;  //游标（Cursor）为0时表示无指向
}Component,StaticLinkList[MAXSIZE];
1
2
3
4
5
6

静态链表的插入操作

将所有未被使用过的及已被删除的分量用游标链成一个备用的链表，每当进行插入时，便可以从备用链表上取得第一个结点作为待插入的新结点

/*若备用空间链表非空，则返回分配的结点下标，否则返回0*/
int Malloc_SSL(StaticLinkList space)
{
    int i = space[0].cur;// 当前数组第一个元素的cur的存值返回其下标
    if(space[0].cur)
        space[0].cur = space[i].cur;//以使用一个分量，故将下一分量用来当做备用
    return i;
}
1
2
3
4
5
6
7
8

/*在L中第i个元素之前插入新的数据元素e*/
Status ListInsert(StaticLinkList L,int i,ElemType e)
{
    int j,k,l;
    k = MAX_SIZE - 1;//k是最后一个元素的下标
    if (i<1 || i>ListLength(L) + 1)
        return ERROR;
    j = Malloc_SSL(L);//获得空闲分量的下标
    if (j)
    {
        L[j].data = e;
        for(l=1;l<=i-1;l++)  //找到第i个元素之前的位置
            k = L[k].cur;
        L[j].cur = L[k].cur;
        L[k].cur = j;
        return OK;
    }
    return ERROR;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

静态链表的删除操作

/*将下标为k的空闲结点回收到备用链表*/
void  Free_SSL(StaticLinkList space,int k)
{
    space[k].cur = space[0].cur;// 把第一个元素的cur值赋给要删除的分量cur
    space[0].cur = k;//把要删除的分量下标赋值给第一个元素的cur
}
1
2
3
4
5
6

/*删除在L中第i个数据元素e*/
Status ListDelete(StaticLinkList L,int i)
{
    int j,k;
    k = MAX_SIZE - 1;//k是最后一个元素的下标
    if (i<1 || i>ListLength(L))
        return ERROR;
    for(j=1;j<=i-1;j++)  //找到第i个元素之前的位置
        k = L[k].cur;
    j = L[k].cur;
    L[k].cur = L[j].cur;
    Free_SSL(L,j);
    return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

静态链表的优缺点

循环链表

将单链表中终端节点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表

双向链表

双向链表是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。

/*双向链表存储结构*/
typedef struct DulNode{
    ElemType data;
    struct DulNode *prior;
    struct DulNode *next;
} DulNode,*DuLinkList;
1
2
3
4
5
6

对于双向链表中的某一结点p，它的前驱的后继和后继的前驱都是它自己，即

p->next->prior = p = p->prior->next
1

双向链表的插入操作

s->prior = p;
s->next = p->next;
p->next->prior = s;
p->next = s;
1
2
3
4

双向链表的删除操作

p->prior->next = p->next;
p->next->prior = p->prior;
free(p);
图片转存中...(img-tU6vj64f-1595644078272)]

```c
/*双向链表存储结构*/
typedef struct DulNode{
    ElemType data;
    struct DulNode *prior;
    struct DulNode *next;
} DulNode,*DuLinkList;
1
2
3
4
5
6
7
8
9
10
11
12

对于双向链表中的某一结点p，它的前驱的后继和后继的前驱都是它自己，即

p->next->prior = p = p->prior->next
1

双向链表的插入操作

[外链图片转存中…(img-6TXO7Qdr-1595644078274)]

s->prior = p;
s->next = p->next;
p->next->prior = s;
p->next = s;
1
2
3
4

双向链表的删除操作

[外链图片转存中…(img-IzQT0sHB-1595644078279)]

p->prior->next = p->next;
p->next->prior = p->prior;
free(p);
1
2
3