顺序表 #数据结构

线性结构是数据结构中最基础、最简单的一种数据结构类型，其中最典型的就是线性表

线性表的定义

具有相同特性的数据元素的有限序列。

相同特性	所有元素属于同一数据类型
有限	数据元素个数是有限的
序列	数据元素由逻辑序号唯一确定

用逻辑序号来确定的特性使得线性表中可以有多个相同值的元素

线性表中所含元素的个数叫做线性表的长度，用n表示（ n >= 0）。当n = 0时，表示线性表是一个空表，即表中不包含任何元素

线性表的逻辑表示

线性表的逻辑表示为：

(

)

≤

表

示

第

个

元

素

为

逻

辑

位

序

\begin{aligned} &(a_1,a_2,...,a_i,a_{i+1},...,a_n)\\ &a_i(1\le i \le n )表示第i个元素(i为逻辑位序) \end{aligned}

(a1,a2,...,ai,ai+1,...,an)ai(1≤i≤n)表示第i个元素(i为逻辑位序)

线性表的基本运算

初始化线性表

构造一个空的线性表
l
建立线性表
销毁线性表

释放线性表
l 占用的内存空间
判线性表是否为空表

若为空返回
1 ，不为空返回
求线性表的长度

返回元素个数
n
输出线性表

当线性表
l 不为空时，顺序输出 l 的每一个元素
求线性表 l
中指定位置的某个数据元素

用
e 返回 l 中第 i 个元素的值
定位查找

返回
l 中第一个与 e 相等的逻辑位序
插入一个数据元素

在
l 的第 i 个元素之前插入新的元素 e ， l 的长度 +1
删除数据元素

删除
l i 个元素，并用 e 返回其值， l -1

线性表的顺序存储结构

把线性表中所有的元素按照顺序的方法进行存储。所有元素按逻辑顺序依次存储到存储器中一片连续的存储空间中

顺序表类型定义

#define MAXSIZE 100
typedef int ElemType;
typedef struct {
    ElemType data[MAXSIZE];
    int length;
}SqList;

顺序表运算的实现

void initList(SqList** l) {
    (*l) = (SqList*)malloc(sizeof(SqList));
    (*l)->length = 0;
}

void createList(SqList* l, ElemType a[], int n) {
    int i;
    for (i = 0; i < n; i++) {
        l->data[i] = a[i];
    }
    l->length = n;
}

void destroyList(SqList* l) {
    free(l);
}

判断是否为空表

int listEmpty(SqList* l) {
    return (l->length == 0);
}

int listlength(SqList* l) {
    return (l->length);
}

当线性表不为空时，顺序显示L中各元素的值

void dispList(SqList* l) {
    int i;
    if (listEmpty(l)) {
        printf("线性表为空\n");
        return;
    }
    for (i = 0; i < l->length; i++) {
        printf("%d ", l->data[i]);
    }
    printf("\n");
}

求某个数据元素值

int getElem(SqList* l, int i, ElemType* e) {
    if (i < 1 || i > l->length) {
        return FALSE;
    }
    *e = l->data[i - 1];
    /*
    **物理位序 = 逻辑位序 + 1
    */
    return TRUE;
}

getElem() 的时间复杂度为 O(1) 。体现了顺序表的随机存取特性

按元素值查找

int locateElem(SqList* l, ElemType e) {
    int i = 0;
    while (i < l->length && l->data[i] != e) {
        i++;
    }
    if (i >= l->length) {
        return 0;
    }
    else {
        return i + 1;
        /*
        ** 返回的是逻辑位序
        */
    }
}

插入数据元素

在插入之前，已有的元素要给新来的元素腾出空间，后面的元素都要向表尾移动一位。最后表的长度

+1

int listInsert(SqList* l, int i, ElemType e) {
    int j;
    if (i < 1 || i > l->length + 1) {		/*判断给出的下标是否合法*/
        return FALSE;
    }
    i--;
    for (j = l->length; j > i; j--) {
        l->data[j] = l->data[j - 1];
    }
    l->data[i] = e;
    l->length++;
    return TRUE;
}

当

i = n + 1

时，元素移动次数为

，最好时间复杂度为

O(1)

i = 1

时，元素移动

次，最坏时间复杂度为

O(n)

线性表中有

n+1

个可以插入元素的地方，在插入元素

ai

时，若为等概率情况，则

p_i = \frac 1 {n+1}

pi=n+11

此时需要将

ai

到

an

的元素均向后移动一个位置，共移动

n-i+1

个元素

所以在长度为

的线性表中插入一个元素时所需移动元素的平均次数为

∑

(

−

)

\begin{aligned} A(n) &= \displaystyle\sum^{n+1}_{i=1} \frac 1 {n+1} \times ( n - i + 1)\\ &= \frac 1 {n+1}\displaystyle\sum^n_{i=0} n-i+1\\ &= \frac n 2 \end{aligned}

A(n)=i=1∑n+1n+11×(n−i+1)=n+11i=0∑nn−i+1=2n

因为插入算法主要花的时间就在移动元素上，因此插入算法的平均时间复杂度为

O(n)

删除元素

用后面的元素覆盖被删除元素，同时都向表头移动。最后表的长度-1

int listDelete(SqList* l, int i, ElemType* e)
{
    int j;
    if (i < 1 || i > l->length) {	/*判断给出的下标是否合法*/
        return FALSE;
    }
    i--;
    *e = l->data[i];
    for (j = i; j < l->length - 1; j++) {
        l->data[j] = l->data[j + 1];
    }
    l->length--;
    return TRUE;
}

对于本算法来说，元素移动的次数也与表长

length

和删除元素的位置

有关：

i = n 时，移动次数为 O(1)
i = 1 n-1 ，最坏时间复杂度为 O(n)

在线性表

中共有

个可以删除元素的地方，在删除元素

ai

p_i = \frac1 n

pi=n1

a(i+1)

和

an

的元素均前移一个位置，共移动

n-(i+1)+1

n-i

−

\begin{aligned} A(n) &= \displaystyle\sum^{n}_{i=1} \frac 1 {n+1} \times ( n - i )\\ &= \frac 1 {n+1}\displaystyle\sum^n_{i=0} n-i\\ &= \frac {n-1} 2 \end{aligned}

A(n)=i=1∑nn+11×(n−i)=n+11i=0∑nn−i=2n−1

平均时间复杂度为

O(n)

顺序表算法设计应用

例题1

已知长度为

的线性表

采用顺序存储结构。设计一个删除线性表中所有值为

的数据元素。要求：

T(n) = O(n)
S(n) = O(1)

方案一

删除一个就把后面的元素往前移动，T(n) = O(n2)，S(n) = O(1)，时间复杂度不符合要求

方案二

创建一个新的顺序表，存放A中所有不为x的元素，T(n) = O(n)，S(n) = O(n)，空间复杂度不符合要求

解法一

设删除

中所有值等于

元素后的顺序表为

A1

，显然

A1

是A的一个子集，所以

A1

可以复用

的空间。

用

记录不为

的元素的位置，遍历线性表

找到一个不等于

的元素就把它移动到下标为

的位置，同时

k+1

最后

的值即为所有不等于

的元素的个数，即删除后的线性表的长度。这个算法的思路类似于重新建表

void delnode1(SqList* l, ElemType x) {
    int i, k = 0;
    for (i = 0; i < l->length; i++) {
        if (l->data[i] != x) {
            l->data[k] = l->data[i];
            k++;
        }
    }
    l->length = k;
}

解法二

记录顺序表

中等于

的元素个数，一边扫描

一边统计等于

的元素的个数，将不为

的元素前移

个位置，最后修改

void delnode2(SqList* l, char x) {
    int i = 0, k = 0;
    while (i < l->length) {
        if (l->data[i] == x) {
            k++;
        }
        else {
            l->data[i - k] = l->data[i];
        }
        i++;
    }
    l->length -= k;
}

例题2

设顺序表

。设计一个算法，以第一个元素为分界线（基准），将所有小于等于它的元素移到该元素的前面，将所有大于它的元素移到该元素的后面

设置

pivot

等于表头元素的值

j 从后向前找 ≤ pivot 的元素
i 从前向后找 > pivot

顺序表

void move1(SqList* l) {
	int i = 0, j = l->length - 1;
	ElemType pivot = l->data[0];
	while (i < j) {
		while (i < j && l->data[j] > pivot) {
			j--;
		}
		while (i < j && l->data[i] <= pivot) {
			i++;
		}
		if (i < j) {
			swap(&l->data[i], &l->data[j]);
		}
	}
	swap(&l->data[0], &l->data[j]);
}

j pivot 的元素，找到前移
i pivot 的元素，找到后移

void move2(SqList* l) {
	int i = 0, j = l->length - 1;
	ElemType pivot = l->data[0];
	while (i < j) {
		while (j > i && l->data[j] > pivot) {
			j--;
		}
		l->data[i] = l->data[j];
		while (i < j && l->data[i] <= pivot) {
			i++;
		}
		l->data[j] = l->data[i];
	}
	l->data[i] = pivot;
}

荷兰国旗问题

红色	白色	蓝色

void flag(SqList* l) {
	int i = -1, j = 0, k = l->length;
	while (j < k) {
		if (l->data[j] == 0) {
			i++;
			swap(&l->data[i], &l->data[j]);
			j++;
		}
		else  if (l->data[j] == 2) {
			k--;
			swap(&l->data[k], &l->data[j]);
		}
		else {
			j++;
		}
	}
}

顺序表的优劣

优点	缺点
存储密度大	插入和删除需要移动大量元素
具有随机存取性	初始空间大小分配难以掌握

顺序表

线性表的定义

线性表的逻辑表示

线性表的基本运算

线性表的顺序存储结构

顺序表类型定义

顺序表运算的实现

判断是否为空表

当线性表不为空时，顺序显示L中各元素的值

求某个数据元素值

按元素值查找

插入数据元素

删除元素

顺序表算法设计应用

例题1

解法一

解法二

例题2

荷兰国旗问题

顺序表的优劣

参考链接

继续阅读

树的基本概念(定义、基本术语、性质)

GSL--GNU Scientific Library

D5|哈希表，善用数据结构

如何成为一名.net 工程师?

BMP文件结构及图像每行字节计算方法

D. Ehab the Xorcist(构造+思维)

查找算法之二分查找查找算法之二分查找

JAVA高效编程指南

CQ V1.0分词bates(基于双数组tire树)—应该是目前最快的中文分词算法

【数据结构】医院选址

[转]ISUP信令的IAM消息详细内容

笔试面试题目：滑动窗口(二)

交通/城市相关的公开的数据集上学时整理的Xie et al., 2020收集的

数据结构与算法（27）——排序（二）

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

Linux设备模型（中）之上层容器