数据结构（二）顺序表
线性表（Linear List）是n个数据元素的有限序列，有以下特点：
（1）存在唯一一个初始元素
（2）存在唯一一个最后的元素
（3）除第一个元素外，每个元素都只有一个“前驱”元素
（4）除最后一个元素外，每个元素都只有一个“后继”元素
表示形式
（a1，a2，…，an-1，an）或（D，S），其中D表示元素集合，S表示关系集合。
线性表分为顺序存储结构和链式存储结构，本文先介绍顺序存储结构。
1
顺序存储结构（顺序表）
顺序表是指按逻辑次序依次存放在一组地址连续的存储单元的数据元素。
假设线性表中每个元素占用n个存储单元，第一个元素所占位置为Loc(a1)，则第i个元素ai的位置为：
Loc(ai) = Loc(a1) + (i -1) * n
这种以元素在内存中“物理位置”相邻来表示线性表中元素之间的位置关系的方式，使得只要确定了第一个元素的位置，那么后面所有元素的位置都是可知的。
在高级程序语言中我们可以用数组来表示顺序表这种数据结构。
C语言描述：
#define MAXSIZE 100
typedef struct
{
uint8 Array[MAXSIZE]; /* Array */
uint8 Length; /* Current Length */
}ArrayList;2
顺序表算法
1.插入算法
假设在数组第i个位置处插入新元素x。
算法思想：
（1）入口判断
存储容量（n < MAXSIZE）
插入位置（（i >= 1）&& （i <= n +1））
（2）元素ai ~ an后移
（3）在线性表第i处插入新元素x
（4）数组长度加1
代码示意（这里默认Loc表示下标）：
/* Insert element */
#define MAXSIZE 100
typedef unsigned char uint8;
ArrayList ArrayToInsert;
uint8 ArrayInsertElement(uint8 Loc,uint8 x)
{
uint8 i;
uint8 Len = ArrayToInsert.Length;
if((Len > MAXSIZE) || ((Loc < 0) || (Loc > Len)))
{
return 0; /* Insert element failed. */
}
else
{
for(i = (Len - 1);i >= Loc;i --)
{
ArrayToInsert.Array[i + 1] = ArrayToInsert.Array[i];
}
ArrayToInsert.Array[Loc] = x;
ArrayToInsert.Length = Len + 1;
return 1; /* Insert element successfully. */
}
}在顺序表上做插入运算，平均要移动表长一半的元素，所以，算法的平均时间复杂度为T(n) = O(n)。
2.删除算法
删除顺序表中第i个元素，并返回其值。
算法思想：
（1）入口判断
线性表是否为空？（n != 0）
删除位置是否在范围内？（1 < i < n）
（2）将第i个元素放入temp
（3）元素ai+1~an前移
（4）表长减1
代码示意（这里默认Loc表示下标）：
/* Delete element */
ArrayList ArrayToDelete;
uint8 ArrayDeleteElement(uint8 Loc)
{
uint8 i;
uint8 x;
uint8 Len = ArrayToDelete.Length;
if((Len == 0) || ((Loc < 0) || (Loc >= Len)))
{
return 0; /* Condition not right. */
}
else
{
x = ArrayToDelete.Array[Loc];
for(i = Loc;i < Len;i ++)
{
ArrayToDelete.Array[i] = ArrayToDelete.Array[i + 1];
}
ArrayToDelete.Length = Len - 1;
return x;
}
}删除一个元素，平均移动表长一半的元素，算法的平均时间复杂度为T(n) = O(n)。
以上两种只是顺序表的比较简单的操作，还有很多操作方式读者可以自行找一些例子学习。
3
顺序表的应用——约瑟夫环问题
问题描述：
N个人围成一圈，从第一个人开始从1报数，第M个人出列，然后下一个人再从1开始报数，第M个人出列……这样依次进行下去，直到剩下最后一个人。
把上面那个问题简化一下，例如：
假设有8个人，每人拿一个牌子，上面依次写着0~7这8个数字，从第一个人开始3个3个报数，数到3的人出列，求最后剩下一个人的牌子上是数字几。
报数步骤如下图所示：
图1 报数流程
设报数的初始位置TempLoc = 0，根据上述可以看出每次出列的下标有一定规律，计算式为：
TempLoc = (TempLoc + 3 - 1) % 当前的数组长度
代码示意：
typedef unsigned char uint8;
typedef struct
{
uint8 Array[8]; /* Array */
uint8 Length; /* Current Length */
}ArrayList;
/* Josephus problem */
uint8 JosephArray(uint8 m,ArrayList Source)
{
uint8 TempLoc = 0;
uint8 ElementLeft;
uint8 i;
uint8 Len = Source.Length;
while(Len > 1)
{
TempLoc = (TempLoc + m - 1) % Len;
for(i = TempLoc;i < Len;i ++)
{
Source.Array[i] = Source.Array[i + 1];
}
Len --;
}
ElementLeft = Source.Array[0];
return ElementLeft;
}
void main(void)
{
uint8 i;
uint8 x;
uint8 m = 3;
ArrayList Source;
for(i = 0;i < 8;i ++)
{
Source.Array[i] = i;
}
Source.Length = 8;
x = JosephArray(m,Source);
}将上述代码debug一下，得出最后剩下的数字为6：
图2 debug结果
以上就是本期内容，如有疑问欢迎私信。
腾讯云开发者
