数据结构的C++实现之线性表之顺序存储结构

数据结构的C++实现之线性表之顺序存储结构2013-08-17 csdn Simba888888线性表的数据对象集合为 {a1,a2,....an}，每个元素的类型均为Datatype。其中，除第一个元素a1外，每一个元素有且只有一个直接前驱元素，除了最后一个元素an外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。

线性表的顺序存储结构的优缺点：

优点：无须为表示表中元素之间的逻辑关系而增加额外的存储空间；可以快速地存取表中任一位置的元素O（1）

缺点：插入和删除操作需要移动大量元素O（n）；当线性表长度变化较大时，难以确定存储空间的容量；造成存储空间的“碎片 ”

示例程序如下（改编自《大话数据结构》）：

#include<iostream>using namespace std;#define MAXSIZE 20typedef int ElemType;typedef struct{ElemType data[MAXSIZE];int length;} SqList;/* 初始化顺序线性表 */bool InitList（SqList *ptr）{for （int i = 0 ; i < MAXSIZE; i++）ptr->data[i] = 0;ptr->length = 0;return true;}bool ListEmpty（SqList Sq）{if （Sq.length == 0）return true;elsereturn false;}bool ClearList（SqList *ptr）{for （int i = 0 ; i < ptr->length; i++）ptr->data[i] = 0;ptr->length = 0;return true;}/*用ptr返回Sq中第pos个数据元素的值,注意pos是指位置，第1个位置的数组是从0开始 */bool GetElem（SqList Sq, int pos, ElemType *ptr）{if （Sq.length == 0 || pos < 1 || pos > Sq.length）return false;*ptr = Sq.data[pos - 1];return true;}/*返回Sq中第1个与Elem满足关系的数据元素的位序,若这样的数据元素不存在，则返回值为0 */int Locate（SqList Sq, ElemType Elem）{for （int i = 0; i < Sq.length; i++）{if （Sq.data[i] == Elem）return i + 1;}return 0;}/*在Sq中第pos个位置之前插入新的数据元素Elem，L的长度加1*/bool ListInsert（SqList *ptr, int pos, ElemType Elem）{if （ptr->length == MAXSIZE）/* 顺序线性表已经满 */return false;if （pos < 1 || pos > ptr->length + 1）return false;if （pos <= ptr->length）{/* 将要插入位置之后的数据元素向后移动一位 */for （int i = ptr->length - 1; i >= pos - 1; i--）{ptr->data[i + 1] = ptr->data[i];}}ptr->data[pos - 1] = Elem; /* 将新元素插入 */ptr->length++;return true;}/*删除ps的第pos个数据元素，并用pe返回其值，ps的长度减1*/bool ListDelete（SqList *ps, int pos, ElemType *pe）{if （pos < 1 || pos > ps->length）return false;*pe = ps->data[pos - 1];/* 将删除位置后继元素前移 */for （int i = pos; i < ps->length; i++）ps->data[i - 1] = ps->data[i];ps->length--;return true;}int ListLength（SqList Sq）{return Sq.length;}/*将所有在线性表pb中但不在pa中的元素都插入到pa中*/void UnionList（SqList *pa, SqList *pb）{int lena = pa->length;int lenb = pb->length;int item;for （int i = 0; i < lenb; i++）{if （GetElem（*pb, i + 1, &item））{if （Locate（*pa, item） == 0）ListInsert（pa, ++lena, item）;}}}int main（void）{SqList Sq;InitList（&Sq）;for （int i = 1 ; i < 5; i++）ListInsert（&Sq, i, i）;if （！ListEmpty（Sq））{cout << "Sq: " << endl;for （int i = 0 ; i < ListLength（Sq）; i++）cout << Sq.data[i] << " ";}cout << endl;int pos = Locate（Sq, 2）;if （pos ！= 0）{int result;ListDelete（&Sq, pos, &result）;cout << "delete: " << result << endl;}if （！ListEmpty（Sq））{cout << "Sq: " << endl;for （int i = 0 ; i < ListLength（Sq）; i++）cout << Sq.data[i] << " ";}cout << endl;SqList Sq2;InitList（&Sq2）;for （int i = 1 ; i < 4; i++）ListInsert（&Sq2, i, 6）;ListInsert（&Sq2, 4, 7）;if （！ListEmpty（Sq2））{cout << "Sq2: " << endl;for （int i = 0 ; i < ListLength（Sq2）; i++）cout << Sq2.data[i] << " ";}cout << endl;UnionList（&Sq, &Sq2）;if （！ListEmpty（Sq））{cout << "Sq: " << endl;for （int i = 0 ; i < ListLength（Sq）; i++）cout << Sq.data[i] << " ";}cout << endl;return 0;}

输出为：

注意：

1、程序中所说的位置pos应是序号加1，如第一个元素序号为0，位置为1。

2、程序中所举的函数是最基本的操作，涉及更复杂的操作可以使用基本操作的组合来完成，如上面的UnionList即求两个线性表集合A和B的并集。

3、初学者易混淆的点是：插入或删除并没有真正进行内存的操作，只是进行了元素的移动，覆盖等，由length成员来记录现在线性表的长度，但总长度是确定的即MAXSIZE，线性表的内存在栈上，函数返回时会被释放。