顺序表的基本操作实现及其应⽤（实验1）
顺序表是⽤⼀段地址连续的存储单元依次存储线性表的数据元素。由于线性表中每个数据元素的类型相同，通常⽤⼀维数组来实现顺序表。下⾯我么就⽤C++来做⼀个⼩demo，实现顺序表的基本功能。
由于线性表的数据元素类型不确定，所以采⽤C++的模板机制，下⾯是顺序表模板的代码
// SequenList.h
#ifndef SequenList_h
#define SequenList_h
#include <iostream>
using namespace std;
const int MaxSize = 50;
template <class T>
class SeqList
{
private:
T data[MaxSize];
int length;
define的基本用法
public:
SeqList() {length = 0;}
SeqList(T a[], int n);
~SeqList() {}
int Length() {return length;}
T Get(int i);
int Locate(T x);
void Insert(int i, T x);
T Delete(int i);
void clearList();
void PrintList();
};
#endif /* SequenList_h */
// SequenList.cpp
#include "SequenList.h"
/**
* 先判断是否合法否则抛出异常
*/
template <class T>
SeqList<T> :: SeqList(T a[], int n)
{
if (n > MaxSize) throw"error : 超出数组最⼤范围"; for (int i = 0; i < n; i++)
data[i] = a[i];
length = n;
}
template <class T>
T SeqList<T> :: Get(int i)
{
if (i < 1 && i > length) throw"查位置⾮法";
else return data[i-1];
}
template <class T>
int SeqList<T> :: Locate(T x)
{
for (int i = 0; i < length; i++)
if (data[i] == x) return i+1;
return0;
}
template <class T>
void SeqList<T> :: Insert(int i, T x)
{
if (length >= MaxSize) throw"上溢错误";
if (i < 1 || i > length + 1) throw"位置错误";
for (int j = length; j >= i; j--)
data[j] = data[j - 1];
data[i-1] = x;
length++;
}
template <class T>
T SeqList<T> :: Delete(int i)
{
if (length == 0) throw"下溢";
if (i < 1 || i > length) throw"位置错误";
T x = data[i - 1];
for (int j = i; j < length; j++)
data[j-1] = data[j];
length--;
return x;
}
template <class T>
void SeqList<T> :: clearList() {
length = 0;
}
template <class T>
void SeqList<T> :: PrintList()
{
for (int i = 0; i < length; i++)
cout << data[i] <<" ";
}
再利⽤上⾯的模板，使⽤顺序表来实现约瑟环问题。 // main.cpp
#include <iostream>
using namespace std;
#include "SequenList.cpp"
#define kCount 10
int main(int argc, const char * argv[]) {
char a[kCount];
int k = 97;
for (int i = 0; i < kCount; i++) {
a[i] = k++;
}
SeqList<char> list(a,kCount);
int n = 6; // 报到6就删除
int count = kCount; // 总数
int i = 0; // 初始化
while (count > 0) {
for (int j = 1; j <= n; j++) {
if (i == count) {
i = 1;
} else {
i++;
}
}
cout << "删除:" << list.Delete(i) << endl;
cout << "剩下:";
list.PrintList();
cout << endl;
count--;
if (i >= 1) {
i--;
} else {
i = count;
}
}
return0;
}
对查操作的分析：上述模板中的按位查算法的时间复杂度为O(1)，按值查算法的平均时间性能是O(n)。
使⽤顺序表之后，体会到顺序表拥有存储密度⾼、可随机存储结点的优点。但是上述顺序表始终是⽤简单数组实现的，长度为定值，在中途⽆法进⾏扩充。在插⼊和删除时，需要移动结点，效率低。
在算法上并没有什么新颖的地⽅，在解决约瑟环问题的main函数中的代码有待优化。若发现有何错漏，望读者指出。(··)و✧