线性表之“顺序表”

demo 下载地址http://git.cxylg.com/gongjiehong/AlgorithmsDemos.git

1． 顺序表的定义

(1) 顺序存储方法
即把线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里的方法。
(2) 顺序表
用顺序存储方法存储的线性表简称为顺序表。

2． 结点a_i 的存储地址

不失一般性，设线性表中所有结点的类型相同，则每个结点所占用存储空间大小亦相同。假设表中每个结点占用c个存储单元，其中第一个单元的存储地址则是该结点的存储地址，并设表中开始结点a₁的存储地址（简称为基地址）是LOC（a₁），那么结点a_i的存储地址LOC（a_i）可通过下式计算：
       LOC（a_i）= LOC（a₁）+（i-1）*c   1≤i≤n
注意：
　在顺序表中，每个结点a_i的存储地址是该结点在表中的位置i的线性函数。只要知道基地址和每个结点的大小，就可在相同时间内求出任一结点的存储地址。是一种随机存取结构。

3．顺序表类型定义

[code lang=”CPP”]

#define ListSize 100 // 定义存储空间大小
typedef int DataType; // 定义类型

typedef struct
{
DataType list[ListSize]; // 线性表的存储空间
int length; // 线性表的长度

}SequenceList;

[/code]

注意：
    ① 用向量这种顺序存储的数组类型存储线性表的元素外，顺序表还应该用一个变量来表示线性表的长度属性，因此用结构类型来定义顺序表类型。
② 存放线性表结点的向量空间的大小ListSize应仔细选值，使其既能满足表结点的数目动态增加的需求，又不致于预先定义过大而浪费存储空间。
③ 由于C语言中向量的下标从0开始，所以若L是SeqList类型的顺序表，则线性表的开始结点a₁和终端结点a_n分别存储在L.list[0]和L.List[L.length-1]中。
④ 若L是SeqList类型的指针变量，则a₁和a_n分别存储在L-＞list[0]和L-＞list[L-＞length-1]中。

4．顺序表的特点
顺序表是用向量实现的线性表，向量的下标可以看作结点的相对地址。因此顺序表的的特点是逻辑上相邻的结点其物理位置亦相邻。

顺序表的基本运算：

[code lang=”CPP”]
void init_list(SequenceList *seq_list);
bool list_is_empty(SequenceList seq_list);
int locate_element(SequenceList seq_list, DataType element);
bool get_element(SequenceList seq_list, int index, DataType *element);
bool insert_list(SequenceList *seq_list, int index, DataType element);
bool delete_list(SequenceList *seq_list, int index, DataType *element);
int list_length(SequenceList seq_list);
void clear_list(SequenceList *seq_list);

void init_list(SequenceList *seq_list)
{
seq_list -> length = 0; //线性表的长度，初始化为0
}

bool list_is_empty(SequenceList seq_list)
{
if (seq_list.length == 0)
{
return false;
}
return true;
}

int locate_element(SequenceList seq_list, DataType element)
{
for (int i = 0; i < seq_list.length; i++)
{
if (seq_list.list[i] == element)
{
return i+1;
}
}
return 0;
}

bool get_element(SequenceList seq_list, int index, DataType *element)
{
if (index < 1 || index > seq_list.length)
{
printf("越界了");
return false;
}
*element = seq_list.list[index – 1];
return true;
}

bool delete_list(SequenceList *seq_list, int index, DataType *element)
{
// 判断位置是否是空表
if (seq_list->length == 0)
{
printf("空表不能删除\n");
return false;
}
else if(index < 1 || index > seq_list->length)
{
printf("位置不合法\n");
return false;
}
else
{
*element = seq_list->list[index – 1];
for (int j = index; j < seq_list->length; j++)
{
seq_list->list[j] = seq_list->list[j + 1]; ///移动元素
}
seq_list->length = seq_list->length -1; ///表长减少
return true;
}
}

bool delete_list(SequenceList *seq_list, int index, DataType *element)
{
// 判断位置是否是空表
if (seq_list->length == 0)
{
printf("空表不能删除\n");
return false;
}
else if(index < 1 || index > seq_list->length)
{
printf("位置不合法\n");
return false;
}
else
{
*element = seq_list->list[index – 1];
for (int j = index; j < seq_list->length – 1; j++)
{
seq_list->list[j – 1] = seq_list->list[j]; ///移动元素
}
seq_list->length = seq_list->length -1; ///表长减少
return true;
}
}

int list_length(SequenceList seq_list)
{
return seq_list.length;
}

void clear_list(SequenceList *seq_list)
{
seq_list->length = 0;
}
[/code]

测试顺序表

[code lang=”CPP”]#include <iostream>
#include "SequenceList.h"

using namespace std;
int main(int argc, const char * argv[]) {
// insert code here…
std::cout << "Hello, World!\n";

SequenceList testList;
DataType element;

init_list(&testList);

int size = sizeof(testList);

if (list_is_empty(testList))
{
std::cout << "表是空表\n";
}

for (int i = 0; i < 101; i++)
{
if (insert_list(&testList, i + 1, i))
{
std::cout << "插入成功\n";
}
else
{
std::cout << "插入失败\n";
}
}

for (int i = 0; i < 110; i++)
{
if (get_element(testList, i + 1, &element))
{
std::cout << "第" << i << "个元素是" << element << endl;
}
else
{
std::cout << "error" << endl;
}
}

int t = locate_element(testList, 101);
if (t == 0)
{
std::cout << "没找到";
}
else
{
std::cout << "找到了 元素在第" << t << "个";
}

int length = list_length(testList);
std::cout << "现在长度： " << length;

size = sizeof(testList);

clear_list(&testList);

length = list_length(testList);

std::cout << "清空后长度： " << length;

size = sizeof(testList);

return 0;
}
[/code]