最近阅读《数据结构、算法及应用》这本书，书中的习题汇总，用自己的方法来实现这些问题。可能效率。等方面存在着非常多的问题，也可能是错误的实现。假设大家在看这本书的时候有更优更好的方法来实现，还请大家多多留言交流多多指正，谢谢
9. C++实现的线性表--顺序表
//
// LinearList.h
// LinearList
//
// Created by cc on 14-8-21.
// Copyright (c) 2014年 cc. All rights reserved.
// 顺序表
#ifndef __LinearList__LinearList__
#define __LinearList__LinearList__
#include <iostream>
#include <stdlib.h>
using namespace std;
template <class T>
class LinearList {
private:
//顺序表长度
int m_length;
//顺序表最大的长度
int m_maxSize;
//元素数组
T* m_element;
public:
LinearList(int maxListSize);
virtual ~LinearList();
/**
* @brief 顺序表是否为空
*
* @return true: 空 false: 非空
*/
bool isEmpty() const;
/**
* @brief 获取顺序表的长度
*
* @return 顺序表的长度
*/
int length() const;
/**
* @brief 获取顺序表最大容量
*
* @return 顺序表的最大容量
*/
int maxSize() const;
/**
* @brief 在顺序表中查找第k个元素。并返回第k个元素至x中
*
* @param k 第k个元素
* @param x 保存第k个元素
*
* @return true: 找到了第k个元素 false: 没找到第k个元素
*/
bool find(int k, T& x) const;
/**
* @brief 查找顺序表中的元素x, 而且返回x所在位置
*
* @param x 元素x
*
* @return 元素x的在顺序表中的位置
*/
int search(const T& x) const;
/**
* @brief 删除第k个元素并将它返回至x中
*
* @param k 第k个元素
* @param x 保存第k个元素
*
* @return 改动后的顺序表
*/
LinearList<T>& deleteElement(int k, T& x);
/**
* @brief 在第k个元素之后插入x元素
*
* @param k 第k个元素
* @param x 元素x
*
* @return 改动后的顺序表
*/
LinearList<T>& insertElement(int k, const T& x);
/**
* @brief 输出信息
*
* @param out 输出流
*/
void output(ostream& out) const;
};
template <class T>
LinearList<T>::LinearList(int maxListSize):m_length(0), m_element(NULL) {
this->m_maxSize = maxListSize;
this->m_element = new T[this->m_maxSize];
}
template <class T>
LinearList<T>::~LinearList() {
delete [] this->m_element;
this->m_element = NULL;
}
/**
* @brief 顺序表是否为空
*
* @return true: 空 false: 非空
*/
template <class T>
bool LinearList<T>::isEmpty() const {
return this->m_length == 0;
}
/**
* @brief 获取顺序表的长度
*
* @return 顺序表的长度
*/
template <class T>
int LinearList<T>::length() const {
return this->m_length;
}
/**
* @brief 获取顺序表最大容量
*
* @return 顺序表的最大容量
*/
template <class T>
int LinearList<T>::maxSize() const {
return this->m_maxSize;
}
/**
* @brief 在顺序表中查找第k个元素，并返回第k个元素至x中
*
* @param k 第k个元素
* @param x 保存第k个元素
*
* @return true: 找到了第k个元素 false: 没找到第k个元素
*/
template <class T>
bool LinearList<T>::find(int k, T& x) const {
if (k > this->m_length - 1
|| k < 0) {
cout << "在顺序表中为找到第" << k << "个位置上的元素";
return false;
}
x = m_element[k];
return true;
}
/**
* @brief 查找顺序表中的元素x, 而且返回x所在位置(位置是下标+1)
*
* @param x 元素x
*
* @return 元素x的在顺序表中的位置
*/
template <class T>
int LinearList<T>::search(const T& x) const {
for (int i = 0; i < this->m_length; i++) {
if (this->m_element[i] == x) {
return i;
}
}
return 0;
}
/**
* @brief 删除第k个元素并将它返回至x中
*
* @param k 第k个元素
* @param x 保存第k个元素
*
* @return 改动后的顺序表
*/
template <class T>
LinearList<T>& LinearList<T>::deleteElement(int k, T& x) {
if (find(k, x)) {
//找到了第k个元素
for (int i = k; i < this->m_length - 1; i++) {
this->m_element[i] = this->m_element[i + 1];
}
this->m_length--;
} else {
// throws exception
cout << "未找到第" << k << "个元素";
}
return *this;
}
/**
* @brief 在第k个元素之后插入x元素
*
* @param k 第k个元素
* @param x 元素x
*
* @return 改动后的顺序表
*/
template <class T>
LinearList<T>& LinearList<T>::insertElement(int k, const T& x) {
if (k > m_maxSize - 1
|| k < 0) {
cout << "数组下标越界!" << endl;
// throws OutOfBoundsException
} else if (this->m_length == this->m_maxSize) {
cout << "已达到数组最大容量。申请内存后再加入!" << endl;
// throws NoMemException
} else {
//找到了第k个元素
for (int i = this->m_length - 1; i > k; i--) {
this->m_element[i] = this->m_element[i - 1];
}
this->m_length++;
this->m_element[k] = x;
}
return *this;
}
template<class T>
void LinearList<T>::output(ostream& out) const {
for (int i = 0; i < this->m_length; i++)
out << this->m_element[i] << " ";
}
// overload
template <class T>
ostream& operator<<(ostream& out, const LinearList<T>& x){
x.output(out); return out;
}
#endif /* defined(__LinearList__LinearList__) */
//
// main.cpp
// LinnerList
//
// Created by ChengChao on 14-8-29.
// Copyright (c) 2014年 cc. All rights reserved.
//
#include <iostream>
#include <stdlib.h>
#include "LinearList.h"
int main(int argc, const char * argv[]) {
LinearList<int> list(10);
list.insertElement(0, 1000).insertElement(1, 312).insertElement(2, 134);
cout << "The list is" << endl;
cout << list << endl;
//顺序表是否为空
cout << "顺序表是否为空：" << boolalpha << list.isEmpty() << endl;
cout << "顺序表的最大容量：" << list.maxSize() << endl;
int res = 0;
int res2 = 0;
//查找99
cout << "查找第0个元素输入到res变量中。是否找到: " << boolalpha << list.find(0, res) << "。res=" << res << endl;
//查找312
cout << "查找第5个元素输入到res变量中。是否找到: " << boolalpha << list.find(5, res2) << "，res=" << res2 << endl;
//删除第1个位置上的元素元素
list.deleteElement(1, res);
cout << list << endl;
//查找元素134
cout << "搜索元素134，位置为：" << list.search(134) << endl;
return 0;
}
输出结果例如以下图：
注意C++中的模板不支持编译分离，须要把模板类的声明和实现放到.h文件中面
本文转自mfrbuaa博客园博客，原文链接：http://www.cnblogs.com/mfrbuaa/p/4869177.html，如需转载请自行联系原作者
