线性表之顺序表C++实现

  1 //顺序线性表的头文件
  2 #include<iostream>
  3 
  4 const int MaxSize = 100;
  5 //定义顺序表SeqList的模板类
  6 template<class DataType>
  7 class SeqList{
  8 public:
  9 　　//顺序表无参构造器（创建一个空的顺序表）
 10 　　SeqList(){ length = 0 }
 11 　　//顺序表有参构造器（创建一个长度为n的顺序表）
 12 　　SeqList(DataType array[], int n);
 13 　　//顺序表析构函数
 14 　　~SeqList(){}
 15 　　//求顺序表的长度
 16 　　int GetLength(){ return length; }
 17 　　//顺序表按位查找，返回i位置的元素
 18 　　DataType GetElement(int i);
 19 　　//顺序表按值查找，返回该元素所在的位置
 20 　　int GetLocal(DataType x);
 21 　　//顺序表在指定的位置插入指定的元素
 22 　　void Insert(int i, DataType x);
 23 　　//顺序表删除元素，返回删除的元素
 24 　　DataType Delete(int i);
 25 　　//输出顺序表中的元素
 26 　　void PrintSeqList();
 27 private:
 28 　　//一维数组，存放数据元素
 29 　　DataType data[MaxSize];
 30 　　//顺序表的长度
 31 　　int length;
 32 };
 33 
 34 //实现顺序表有参构造器
 35 template<class DataType>
 36 SeqList<DataType>::SeqList(DataType array[], int n)
 37 {
 38 　　if (n > MaxSize)
 39 　　{
 40 　　　　throw "传入的顺序表长度过长";
 41 　　}
 42 　　//给顺序表的存储元素的数组赋值
 43 　　for (int i = 0; i < n; i++)
 44 　　{
 45 　　　　data[i] = array[i];
 46 　　}
 47 　　//给顺序表的长度赋值
 48 　　length = n;
 49 }
 50 
 51 //实现顺序表按位查找
 52 template<class DataType>
 53 DataType SeqList<DataType>::GetElement(int i)
 54 {
 55 　　//判断是定的位置是否合理
 56 　　if (i < 1 || i >length)
 57 　　{
 58 　　　　throw "位置有误";
 59 　　}
 60 　　else
 61 　　{
 62 　　　　//返回指定位置的元素
 63 　　　　return data[i - 1];
 64 　　}
 65 }
 66 
 67 //实现顺序表按值查找,返回该元素所在的位置
 68 template<class DataType>
 69 int SeqList<DataType>::GetLocal(DataType x)
 70 {
 71 　　//遍历顺序表的元素
 72 　　for (int i = 0; i < length; i++)
 73 　　{
 74 　　　　//判断指定的元素是否在顺序表中
 75 　　　　if (data[i] == x)
 76 　　　　{
 77 　　　　　　//返回指定元素在顺序表中的位置
 78 　　　　　　return (i + 1);
 79 　　　　}
 80 　　}
 81 　　//如果指定的元素不在顺序表中，则返回位置为0
 82 　　return 0;
 83 }
 84 
 85 //实现顺序表插入元素
 86 template<class DataType>
 87 void SeqList<DataType>::Insert(int index, DataType x)
 88 {
 89 　　//判断插入的位置是否合理
 90 　　if (length >= MaxSize)
 91 　　{
 92 　　　　throw "顺序表已存放满";
 93 　　}
 94 　　if (index<1 || index>length + 1)
 95 　　{
 96 　　　　throw "插入元素的位置有误";
 97 　　}
 98 　　//如何插入的位置合理，则把顺序表中从最后位置到指定插位置的元素整体向后移动一个位置
 99 　　for (int j = length; j >= index; j--)
100 　　{
101 　　　　data[j] = data[j - 1];
102 　　}
103 　　//给插入的位置放入指定的元素
104 　　data[index - 1] = x;
105 　　length++;
106 }
107 
108 //实现顺序表删除指定位置的元素
109 template<class DataType>
110 DataType SeqList<DataType>::Delete(int index)
111 {
112 　　//声明要取出的元素
113 　　DataType x;
114 　　//判断要删除的位置是否合理
115 　　if (index<1 || index>length)
116 　　{
117 　　　　throw "删除的位置有误";
118 　　}
119 　　else
120 　　{
121 　　　　//取出指定位置的元素
122 　　　　x = data[index-1];
123 　　　　//将指定位置后的元素全部都向前移动一个位置
124 　　　　for (int i = index; i < length; i++)
125 　　　　{
126 　　　　　　data[i - 1] = data[i];
127 　　　　}
128 　　　　//删除顺序表中的元素后，其长度减1
129 　　　　length--;
130 　　}
131 　　return x;
132 }
133 
134 //顺序输出顺序表中的元素
135 template<class DataType>
136 void SeqList<DataType>::PrintSeqList()
137 {
138 　　if (length < 1)
139 　　{
140 　　　　throw "顺序表中没有元素";
141 　　}
142 　　else
143 　　{
144 　　　　//顺序输出顺序表元素
145 　　　　for (int i = 0; i < length; i++)
146 　　　　{
147 　　　　　　　cout << data[i] << " ";
148 　　　　}
149 　　　　cout << endl;
150 　　}
151 }

 1 #include<iostream>
 2 #include"SeqList.h"
 3 using namespace std;
 4 void show()
 5 {
 6 　　cout << "---------------------------------------" << endl;
 7 }
 8 int main()
 9 {
10 　　int array[10] = {1,3,4,2,5,6,8,7,9,10};
11 　　SeqList<int> seqList = SeqList<int>(array,10);
12 　　cout << "顺序表为：" << endl;
13 　　seqList.PrintSeqList();
14 　　show();
15 　　cout << "顺序表的长度为：" << seqList.GetLength()<< endl;
16 　　cout << "第三个位置的元素是：" << seqList.GetElement(3) << endl;
17 　　cout << "元素3的位置是：" << seqList.GetLocal(3) << endl;
18 　　show();
19 　　cout << "在第5个位置插入元素22" << endl;
20 　　seqList.Insert(5, 22);
21 　　cout << "顺序表为：" << endl;
22 　　seqList.PrintSeqList();
23 　　cout << "顺序表的长度为：" << seqList.GetLength() << endl;
24 　　show();
25 　　cout << "删除第5个位置的元素" << endl;
26 　　seqList.Delete(5);
27 　　cout << "顺序表为：" << endl;
28 　　seqList.PrintSeqList();
29 　　cout << "顺序表的长度为：" << seqList.GetLength() << endl;
30 　　show();
31 　　return 0;
32 }