Categories: 算法相关

线性表之“顺序表”

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

1. 顺序表的定义

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

2. 结点ai 的存储地址

不失一般性,设线性表中所有结点的类型相同,则每个结点所占用存储空间大小亦相同。假设表中每个结点占用c个存储单元,其中第一个单元的存储地址则是该结点的存储地址,并设表中开始结点a1的存储地址(简称为基地址)是LOC(a1),那么结点ai的存储地址LOC(ai)可通过下式计算:
       LOC(ai)= LOC(a1)+(i-1)*c   1≤i≤n
注意:
 在顺序表中,每个结点ai的存储地址是该结点在表中的位置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类型的顺序表,则线性表的开始结点a1和终端结点an分别存储在L.list[0]和L.List[L.length-1]中。
④ 若L是SeqList类型的指针变量,则a1和an分别存储在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]

龚杰洪

Share
Published by
龚杰洪

Recent Posts

GOLANG面试八股文-并发控制

背景 协程A执行过程中需要创建…

1 年 ago

MYSQL面试八股文-常见面试问题和答案整理二

索引B+树的理解和坑 MYSQ…

1 年 ago

MYSQL面试八股文-InnoDB的MVCC实现机制

背景 什么是MVCC? MVC…

1 年 ago

MYSQL面试八股文-索引类型和使用相关总结

什么是索引? 索引是一种用于加…

1 年 ago

MYSQL面试八股文-索引优化之全文索引(解决文本搜索问题)

背景:为什么要有全文索引 在当…

1 年 ago