顺序表中数据元素的存储地址是其序号的线性函数,只要确定了存储顺序表的起始地址(即 基地址),计算任意一个元素的存储地址的时间是相等的,具有这一特点的存储结构称为[随机存储]。
使用的基本数据结构:数组特点:顺序存取,随机访问。
/*
Name: SeqList Copyright: 1.0 Author: Johnny Zen Date: 04/06/17 21:51 Description: 线性链表之顺序表 *//* Chinese:顺序(线性)表 English:SeqList*/#include<iostream>using namespace std;//顺序表ADT
const int MAXSIZE = 100;template<class T>class SeqList{ public: SeqList(); //无参构造函数 SeqList(T array[],int length); //有参构造函数 ~SeqList() { cout<<"\n析构成功!\n"<<endl; }; //析构函数 bool insertElement(T data,int n); //按位置插入元素 T deleteElementByLocation(int n); //按位置删除元素 int deleteElementByValue(T data); //按值删除元素 int searchElement(T data); //按值搜索元素,返回位置 T searchElement(int n); //按位置搜索元素,返回值 void print(); //输出表内元素 int getLength(); //获取当前元素个数 public: T array[MAXSIZE]; //存放元素的数组 int length; //元素个数 };//无参构造函数
template<class T> SeqList<T>::SeqList(){ length = 0; for(int i=0;i<MAXSIZE;i++){ array[i] = 0; }}//构造函数
template<class T>SeqList<T>::SeqList(T array[],int length){ this->length = length; for(int i=0;i<length;i++){ this->array[i] = array[i]; } cout<<"\n初始化成功!\n"<<endl;}//按[实际]位置插入元素
//2 8 9 0 3 7//0 1 2 3 4 5 // ↑// (n-1) //比如:插入在第3个位置上//起始: (从后往前)//array[length] = array[length-1] //array[length]:增加的1个新结点 //结束://array[n] = array[n-1];//array[n-1]:要重置新值的位置 template<class T>bool SeqList<T>::insertElement(T data,int n){ //防溢出 if(n<1||n>length){ return false; } for(int i=length;i>n-1;i--){ array[i] = array[i-1]; } array[n-1] = data; length++; return true; }//按[实际]位置删除元素
//2 8 9 0 3 7//0 1 2 3 4 5 // ↑// (n-1) //比如:插入在第3个位置上//起始: (从前往后)//array[n-1] = array[n] //array[n-1]:重置新值的位置 //结束://array[length-2] = array[length-1];//array[length-1]:要删除掉的结点 template<class T>T SeqList<T>::deleteElementByLocation(int n){ //边界检测 if(n<1||n>=length) return (T)false; T value = array[n-1]; for(int i=n-1;i<=length-2;i++){ array[i] = array[i+1]; } //减少表长度 length--; //恢复删除掉的结点的默认值(0) array[length] = 0; return value;}//按值删除结点,返回实际位置
template<class T>int SeqList<T>::deleteElementByValue(T data){ array[length] = data; int i; for(i=0;array[i]!=data;i++); if(i!=length){ //found success deleteElementByLocation(i); //按值删除 return i+1; }else{ //found fail //recover array[length]'s default value(0) array[length] = 0; return -1; }}//按值查找
//算法:顺序查找 template<class T>int SeqList<T>::searchElement(T data){ //array[length] as array's guard of border T array[length] = data; int i; for(i=0;array[i]!=data;i++); //recover array[length]'s default value(0) array[length] = 0; return i==length?(i+1):(-1); //-1 : not found }//输出表的长度
template<class T>int SeqList<T>::getLength(){ return length;}//输出数组元素
template<class T>void SeqList<T>::print(){ for(int i=0;i<length;i++){ if(i%10==0){ cout<<endl; } cout<<array[i]<<'\t'; } cout<<"\n****************print end****************\n";}int main(){
//输入数据 const int n = 10; char arr[n]; for(int i=0;i<n;i++){ cin>>arr[i]; } //测试 SeqList<char> test(arr,n); cout<<"表所有元素:"<<endl; test.print(); test.insertElement('f',3); cout<<"在第3个位置上插入元素 f "<<endl; test.print(); //按位置删除结点 cout<<test.deleteElementByLocation(3)<<endl; cout<<"删除第三个位置的元素后:"<<endl; test.print(); //获取表长度 cout<<test.getLength(); return 0;}/*
Test Data: 1 0 9 8 6 5 4 3 2 7*/