第3章线性表

第3章线性表

3.2 线性表的定义

零个或多个数据元素的有限序列。

若将线性表标记为(a1, ..., ai-1,ai,ai+1,...,an)，则表中ai-1领先于ai，称ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素。当i=1,2,...,n-1时，ai有且仅有一个直接后继，当i=1,2,3,...,n时，ai有且仅有一个直接前驱元素。

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

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

3.2线性表的抽象数据类型

线性表的抽象数据类型定义：

ADT 线性表
Data
	线性表的数据对象集合为{a1,a2,...,an},每个元素的类型均为DataTye。其中，除第一个元素a1外，每一个元素有且只有一个直接前驱元素，除最后一个元素an外，每一个元素有且只有一个直接后继元素。数据元素之间的关系时一对一的关系。
Operation
	InitList(*L):	初始化操作，建立一个空的线性表L。
	ListEmpty(L):	如线性表为空，返回true，否则返回false。
	ClearList(*L):	将线性表清空。
	GetElem(L,i,*e):将线性表L中第i个位置的元素值返回给e。
	LocateElem(L,e):在线性表中查找与给定值e相等的元素，如果查找成功，返回该元素在表中序号表示成功；否则
					返回0表示失败。
	ListInsert(*L,i,e):在线性表中第i个位置插入元素e。
	ListDelete(*L,i,*e):删除线性表中第i个位置元素，并用e返回其值。
	ListLength(L):	返回线性表L的元素个数。
endADT

对于不同的应用，线性表的基本操作时不同的，上述操作时最基本的，对于实际问题中涉及的关于线性表的更复杂操作，完全可以使用这些基本操作的组合实现。

如两个相同元素类型的线性表A和B进行合并到A：

void unionL(List *La, List b)
{
	int La_len, Lb_len, i;
	ElemType e;					//声明与La和Lb相同的数据元素e	
	La_len = ListLength(*La);	//求线性表的长度
	Lb_len	= ListLength(Lb);
	for ( i = 1; i <= Lb_len; i++)
	{
		GetElem(Lb, i, &e);		//取Lb中第i个数据元素赋值给e
		if(!LocateElem(*La, e))	//La中不存在和e相同数据元素
			ListInsert(La, ++La_len, e);	//插入
	}
}

3.4线性表的顺序存储结构

3.4.1 顺序存储定义

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

3.4.2顺序存储方式

C语言一维数组实现顺序存储结构

#define MAXSIZE 20	//存储空间初始化分配量
typedef int ElemType;	//ElemType类型根据实际情况而定，这里假设为int
typedef struct
{
    ElemType data[MAXSIZE];	//数组存储数据元素，最大值为MAXSIZE
    int length;	//线性表当前长度
}SqList;

3.4.2 数组长度与线性表的长度区别

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

线性表长度为线性表中存储数据元素的个数。

3.4.3 地址计算方法

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

假设每个数据元素占用c个存储单元，则第i+1个数据元素的存储位置和第i个数据元素的存储位置满足下列关系(LOC表示获取存储位置的函数)

LOC(ai+1) = LOC(ai)+c

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

3.5 顺序结构的插入与删除

3.5.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 GetEleme(SqList L, int i, ElemType *e)
{
	if (L.length == 0 || i < 1 || i > L.length
		return ERROR;
	*e = L.data[i-1];
	return OK;
}

3.5.2 插入操作

插入算法思路

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

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

  • 从最后一个元素开始向前遍历到第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 - 1; k >= i - 1; k++)
			L->data[k+1] = L->data[k];
	}
	L->data[i-1] = e;
	L->length++;
	return OK;
}

3.5.3 删除操作

删除算法的思路

  • 如果删除位置不合理，抛出异常。
  • 取出删除数据元素。
  • 从删除数据元素的位置开始遍历到最后一个数据元素的位置，分别将他们向前移动一个位置。
  • 表长减1。

实现代码：

/*
*初始条件：顺序线性表L已经存在，1<=i<=ListenLength(L)
*操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1
*/
Status ListDelete(SqList *L, int i, ElemType *e)
{
    int k;
     if (0 == L->length) //线性表为空
         return ERROR;
     if (i < 1 || i > L->Length)	//删除位置不正确
         return ERROR;
    *e = L->data[i-1];
    if (i<L->length)
    {
        for (k=i; k<L->length;k++)
            L->data[k-1] = L->data[k];
    }
    L->length--;
    return OK;
}

3.5.4 先行顺序表的优缺点

优点 缺点
无须为表述表中元素之间的逻辑关系而额外增加存储空间。 插入和删除操作需要移动大量元素。
可以快读的存取表中任一位置的元素。 当线性表长度变化较大时，难以确定存储空间的容量。
造成存储空间的“碎片”。

3.6 线性表的链式存储结构

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

舒徐存储结构的缺点插入和删除需要移动大量的数据元素，解决方法：

所有的数据元素不考虑相邻位置，哪里有空位就存储在哪里，当前 数据元素知道下一个数据元素的位置即可。

插入：当i位置插入的时候，将i-2个元素的下一个元素指向新插入的元素，新插入的元素指向原i-1个元素的位置。

删除：当i位置删除时，删除i-1位置的元素，并将i-2元素的下一个元素 指向i元素的位置。

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

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

n个结点(ai的存储映像)链结成一个链表，即为线性表(a1, a2, ... , an)的链式存储结构，因为此链表的每个结点中只包含一个指针域，所以叫做单链表。

图3-6-2

链表中第一个结点的存储位置叫做头指针。

线性链表的最后一个结点指针为"空"。

图3-6-3

在链表中第一个结点前附设一个结点，称为头结点

图3-6-4

3.6.3 头指针与头结点的异同

头指针 头结点
头指针时指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针。 头结点是为了操作和统一的方便而设立的，放在第一个元素结点之前，其数据域一般无意义（也可存放链表的长度）。
头指针具有标识作用，所以常用头指针冠以链表的名字。 有了头结点，对在第一个元素节点之前插入结点和删除第一个结点，其操作和其他结点的操作就统一了。
无论链表是否为空，头指针均不为空。头指针时链表必要的元素。 头结点不一定时链表必须要素。

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

单链表中，在C语言中可以用结构指针描述。

/*
*线性表的单链表存储结构
*/
typedef struct Node
{
    ElemType data;
    struct Node *next;
} Node;
typedef struct Node *LinkList;

结点由存放数据元素的数据域和存放后继结点地址的指针域组成。

链表中两个数据元素关系如下图：

图3-6-10

3.7 单链表的读取

获取链表中第i个数据元素的算法思路：

  1. 声明一个指针p指向链表第一个结点，初始化j从1开始。
  2. 当j<i时，就遍历链表，让p指针的位置向后移动，不断指向下一个结点，j累加1；
  3. 若链表末尾p为空，则说明第i个结点不存在；
  4. 否则查找成功。
/*
*初始条件：顺序线性表L已经存在，1<=i<=ListLength(L);
*操作结果：用e返回L中第i个数据元素的值。
*/
Status GetElem(LinkList L, int i, ElemType *e)
{
    int j;
    LinkList p;
    p = L->next;
    j = 1;
    while (p && j < 1)
    {
        p = p->next;
        ++j;
    }
    if ( !p || j > 1)
        return ERROR;
    *e = p->data;
    return OK;
}

注：

链表带头结点，不存储任何数据，指向第一个结点。

3.8 单链表的插入与删除

3.8.1 单链表的插入

假设存储元素e的结点为s，将s插入到结点p和p->next的操作：

图3-8-1

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

插入后的链表结构

图3-8-3

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

实现算法如下：

/*
* 初始条件：顺序线性表L已存在，1<=i<=ListLength(L)
* 操作结果：在L中第i个结点位置之前插入新的数据元素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-1个结点
	{
		p = p->next;
		++j;
	}
	if(!p || j > i)						//第i个结点不存在
		return ERROR;
	s = (LinkList)malloc(sizeof(Node));	//生成新的结点(C标准函数)
	s->data = e;
	s->next = p->next;					//将p的后继结点赋值给s的后继
	p->next = s;						//将s赋值给p的后继
	return OK;
}

3.8.2 单链表的删除

图3-8-5

删除结点q，需获取到p结点的指针，将前继结点p的后继结点指向q的后继结点，然后删除p。

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

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

  1. 声明一指针p指向链表头指针，初始化j从1开始；
  2. 当j<1时，就遍历链表，让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 < 1)			//遍历寻找第i个结点
	{
		p = p->next;
		++j;
	}
	if ( ! (p->next) || j > i)			//第i个结点不存在
		return ERROR;
	q = p->next;
	p->next = q->next;					//将q的后继赋值给p的后继
	*e = q->data;						//将q结点的数据赋值给e
	free(q);							//释放q结点
	return OK;
}

对于插入或删除数据越频繁的操作，单链表的效率越明显。

3.9 单链表的整表创建

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

  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;						//插入到表头
    }
}

头插法：始终让新结点在第一的位置。

图3-9-1

尾插法：每次都将新的结点插入到终端结点的后面。

/*
* 随机产生n个元素的值，建立带表头结点的单链线性表L(尾插法)
*/
void CreateListTail(Linst *L, int n)
{
    LinkList p, r;
    int i;
    srand(time(0));							//初始化随机数种子
    *L = (LinkList)malloc(sizeof(Node));	
    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;
}

3.10 单链表的整表删除

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

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

实现代码如下：

/*
* 初始条件：顺序线性表L已存在，操作结果：将L重置为空表
*/
Status ClearList(LinkList *L)
{
    LinkList p, q;
    p = (*L)->next;				//p指向第一个结点
    while(p)					//没到表尾
    {
        q = p->next;
        free(p);
        p = q;
    }
    (*L)->next = NULL;			//头结点指针域为空
    return OK;
}

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

链式存储和顺序存储优缺点

3.12 静态链表

静态链表：数组的元素由两个数据域组成data和cur，data存放数据元素，cur存放该数据元素后继数据元素在数组中的下标，cur叫做游标。这种用数组描述的链表叫静态链表。

/*
* 线性表的静态链表存储结构
*/
#define MAXSIZE 1000		//假设链表的最大长度为1000
typedef struct
{
    ElemType data;
    int cur;				//游标，为0时表示无指向
} Component, StaticLinkList[MAXSIZE];

链表第一个和最后一个元素作为特殊元素处理，不存数据。通常把未使用的数据元素称为备用链表。而数组第一个元素，即下标为0的元素cur存放 备用链表的第一个结点的下标。而数组最后一个元素的cur则存放第一个有数值元素的下标。

静态链表存储如下：

图3-12-1

/*
* 将一维数组space中各分量链成一条备用链。
* space[0].cur为头指针，"0"表示空指针
*/

Status InitList(StaticLinkList space)
{
    int i;
    for (i=0; i<MAXSIZE-1; i++)
        space[i].cur = i+1;
    space[MAXSIZE-1].cur = 0;			//目前静态链表为空，最后一个元素的cur为0
    return OK;
}

假设我们已将数据“甲“、”乙“、“丙”、”丁“、”戊“、”己“、庚”数据存入静态链表，则他们的状态，如下图：

图3-12-2

3.12.1 静态链表的插入操作

分配可用结点：

/*
* 若备用空间链表非空，则返回分配的结点下标，否则返回0
*/
int Malloc_SLL(StaticLinkList space)
{
	int i = space[0].cur;	//当前数组第一个元素的cur寸的值，就是要返回的第一个备用空闲的下标
	if (space[0].cur)
		space[0].cur = space[i].cur;//由于要拿出一个分量来使用了，所以就需要把下一个分量做备用。
	return i;
										
}

插入结点

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

以下图静态链表中在"乙"和"丁"之间插入"丙"：

图3-12-2

代码解释：

  • 当我们执行插入语句时，我们的目的时在“乙”和"丁"之间插入"丙"。调用代码时i=3。

  • 第4行让k=MAX_SIZE - 1 = 999。

  • 第7行，j = Malloc_SSL(L) = 7。此时下标0的cur也因为7要被占用而改备用链表值为8。

  • 第11~12行，for循环1由1到2，执行2次。

    第一次：k=L[999].cur=1

    第二次：k=L[1].cur=2。

  • 第13行，L[j].cur = L[k].cur;因为j=7，而k=2得到L[7].cur=L[2].cur=3。这就让丙的cur改为3。

  • 第14行，L[k].cur = j;意思就是L[2].cur=7。让乙的cur指向丙的下标7。

实际插入后的效果：

图3-12-3

3.12.2 静态链表的删除操作

删除元素的算法：

/*
* 删除L中第i个元素e
*/
Status ListDelete(StaticLinkList L, int i)
{
    int j, k;
    if (i < 1 || i > ListLength(L))
        return ERROR;
    k = MAX_SIZE - 1;
    for (j = 1; j <= i - 1; j++)
        k = L[k].cur;
    j = L[k].cur;
    L[k].cur = L[j].cur;
    Free_SSL(L,j);
    return OK;
}

释放空闲结点：

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

删除甲之后的静态链表：

图3-12-4

获取静态链表长度

/*
* 初始条件：静态链表L已存在。
* 操作结果：返回L中数据元素的个数。
*/
int ListLength(StaticLinkList L)
{
    int j = 0;
    int i = L[MAXSIZE - 1].cur;
    while(i)
    {
        i = L[i].cur;
        j++;
    }
    return j;
}

3.12.3 静态链表优缺点

优点 缺点
插入和删除操作时，只需要修改游标，不需要移动元素，从而改进了顺序存储结构中的插入和删除操作需要移动大量元素的缺点。 没有解决连续存储分配带来的表长难以确定的问题。
失去了顺序存储结构随机读取的特性。

3.13 循环链表

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

3.14 双向链表

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

/*
* 线性表的双向链表存储结构
*/
typedef struct DulNode
{
	ElemType data;
	struct DulNode *prior;		//指向前驱指针
	struct DulNode *next;		//指向后驱指针
} DulNode, *DuLinkList;

双向链表中元素插入

图3-14-5

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

删除结点p:

图3-14-6

p->prior->next = p->next;
p->next->prior = p->prior;
free(p);
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/spring-1991/p/11922200.html