C++順序表的基本操作（使用模版類(lèi)）
更新時(shí)間：2020年04月27日 17:06:02 作者：ChanJose
這篇文章主要為大家詳細(xì)介紹了C++順序表的基本操作，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
本文實(shí)例為大家分享了C++順序表的基本操作，供大家參考，具體內(nèi)容如下
一、遇到問(wèn)題：
原因：類(lèi)的函數(shù)定義不能放在SeqList.cpp中，必須放在Seqlist.h(類(lèi)的函數(shù)聲明和定義放在同一個(gè)文件下)中，否則
會(huì)出現(xiàn)以下問(wèn)題。
二、實(shí)現(xiàn)程序：
1.SeqList.h
#ifndef SeqList_h
#define SeqList_h
#include <iostream>
using namespace std;
const int defaultSize = 100;
template<class T>
class SeqList{
public:
SeqList(int sz = defaultSize); // 構(gòu)造函數(shù)
SeqList(SeqList<T>& L); // 復(fù)制構(gòu)造函數(shù)
~SeqList(); // 析構(gòu)函數(shù)
int Size(); // 重載虛函數(shù)：計(jì)算表最大可容納表項(xiàng)個(gè)數(shù)，限制權(quán)限，類(lèi)外無(wú)法直接獲取maxSize
int Length(); // 計(jì)算表長(zhǎng)度
int Search(T x); // 搜索x在表中位置，函數(shù)返回表項(xiàng)序號(hào)
int Locate(int i); // 定位第i個(gè)表項(xiàng)，函數(shù)返回表項(xiàng)序號(hào)
bool getData(int i, T& x); // 取第i個(gè)表項(xiàng)的值
void setData(int i, T x); // 用x修改第i個(gè)表項(xiàng)的值
bool Insert(int i, T x); // 在第i個(gè)表項(xiàng)后插入元素x
bool Remove(int i, T& x); // 刪除第i個(gè)表項(xiàng)，通過(guò)x返回
bool isEmpty(); // 判斷表是否為空，空則返回true;否則，返回false
bool isFull(); // 判斷表滿(mǎn)否，滿(mǎn)則返回true;否則，返回false
void Input(); // 輸入數(shù)據(jù)建立表
void Output(); // 打印表
void Sort(); // 排序
SeqList<T> operator=(SeqList<T>& L); // 表整體賦值
private:
T *data; // 存放數(shù)組
int maxSize; // 最大可容納表項(xiàng)的項(xiàng)數(shù)
int last; // 當(dāng)前已存表項(xiàng)的最后位置（從0開(kāi)始）
void reSize(int newSize); // 改變數(shù)組空間大小
};
template <class T>
SeqList<T>::SeqList(int sz) {
// 構(gòu)造函數(shù),通過(guò)指定參數(shù)sz定義數(shù)組的長(zhǎng)度
if(sz > 0) {
maxSize = sz;
last = -1; // 置表的實(shí)際長(zhǎng)度為空
data = new T[maxSize]; // 創(chuàng)建順序表存儲(chǔ)數(shù)組
if(data == NULL) {
cerr << "動(dòng)態(tài)內(nèi)存分配失敗!" << endl;
exit(1);
}
}
}
template <class T>
SeqList<T>::SeqList(SeqList<T>& L) {
// 復(fù)制構(gòu)造函數(shù)，用參數(shù)表中給出的已有順序表初始化新建的順序表
// 如果沒(méi)有定義復(fù)制構(gòu)造函數(shù)，系統(tǒng)會(huì)自動(dòng)建立一個(gè)復(fù)制構(gòu)造函數(shù)
maxSize = L.Size(); // 最大可容納的個(gè)數(shù)
last = L.Length() - 1; // 數(shù)組最后的位置
T value;
data = new T[maxSize]; // 創(chuàng)建順序表存儲(chǔ)數(shù)組
if(data == NULL) {
cerr << "動(dòng)態(tài)內(nèi)存分配失敗!" << endl;
exit(1);
}
for(int i = 1; i <= last+1; i++) {
L.getData(i, value); // 取第i個(gè)位置的值
data[i-1] = value;
}
}
template <class T>
SeqList<T>::~SeqList() {
// 析構(gòu)函數(shù)
delete []data;
}
template <class T>
void SeqList<T>::reSize(int newSize) {
// 私有函數(shù)：擴(kuò)充順序表的存儲(chǔ)數(shù)組空間大小，新數(shù)組的元素個(gè)數(shù)為newSize
if(newSize <= 0) { // 檢查參數(shù)的合理性
cerr << "無(wú)效的數(shù)組大小" << endl;
return;
}
if(newSize != maxSize) { // 修改
T *newArray = new T[newSize]; // 建立新數(shù)組
if(newArray == NULL) {
cerr << "動(dòng)態(tài)內(nèi)存分配失敗!" << endl;
exit(1);
}
int n = last + 1;
T *srcPtr = data; // 源數(shù)組首地址
T *destPtr = newArray; // 目的數(shù)組首地址
while(n--)
*destPtr++ = *srcPtr++; // 復(fù)制：只是數(shù)據(jù)
delete []data; // 刪除舊數(shù)組
data = newArray; // 復(fù)制新數(shù)組
maxSize = newSize; // 復(fù)制新數(shù)組：數(shù)據(jù)和內(nèi)存空間
}
}
template <class T>
int SeqList<T>::Size(){
// 計(jì)算表最大可容納表項(xiàng)個(gè)數(shù)
return maxSize;
}
template <class T>
int SeqList<T>::Length(){
// 計(jì)算表長(zhǎng)度
return last+1;
}
template <class T>
int SeqList<T>::Search(T x){
// 搜索x在表中位置，函數(shù)返回表項(xiàng)序號(hào):在表中的第幾個(gè)位置；搜索失?。悍祷?
for(int i = 0; i <= last; i++) // 順序搜索
if(data[i] == x)
return (i+1);
return 0;
}
template <class T>
int SeqList<T>::Locate(int i){
// 定位第i個(gè)表項(xiàng)，函數(shù)返回第i（1<= i <= last+1）個(gè)表項(xiàng)的位置，否則函數(shù)返回-1，表示定位失敗
if(i >= 1 && i <= last+1)
return i-1; // 數(shù)組下標(biāo)從0開(kāi)始
return -1;
}
template <class T>
bool SeqList<T>::getData(int i, T& x){
// 取第i個(gè)表項(xiàng)的值
if(i > 0 && i <= last+1) {
x = data[i-1];
return true;
}
return false;
}
template <class T>
void SeqList<T>::setData(int i, T x){
// 用x修改第i個(gè)表項(xiàng)的值
if(i > 0 && i <= last+1)
data[i-1] = x;
}
template <class T>
bool SeqList<T>::Insert(int i, T x) {
// 在第i個(gè)表項(xiàng)后插入元素x
if(last == maxSize-1) // 表滿(mǎn)，不能插入
return false;
if(i < 0 || i > last+2) // 參數(shù)i不合理，不能插入, last+2表示數(shù)組的最后面插入
return false;
for(int j = last; j >= i; j--)
data[j+1] = data[j]; // 依次后移，空出第i號(hào)位置
data[i] = x; // 插入
last++; // 最后位置加1
return true; // 插入成功
}
template <class T>
bool SeqList<T>::Remove(int i, T& x) {
// 刪除第i個(gè)表項(xiàng)，通過(guò)x返回
if(last == -1) // 表空，不能刪除
return false;
if(i < 0 || i > last+1) // 參數(shù)i不合理，不能插入
return false;
x = data[i-1];
for(int j = i-1; j < last; j++)
data[j] = data[j+1];
last--; // 最后位置減1
return true; // 刪除成功
}
template <class T>
bool SeqList<T>::isEmpty(){
// 判斷表是否為空，空則返回true;否則，返回false
return (last == -1 ? true : false);
}
template <class T>
bool SeqList<T>::isFull(){
// 判斷表滿(mǎn)否，滿(mǎn)則返回true;否則，返回false
return (last == maxSize-1 ? true : false);
}
template <class T>
void SeqList<T>::Input() {
// 從標(biāo)準(zhǔn)輸入（鍵盤(pán)）逐個(gè)數(shù)據(jù)輸入，建立順序表
int len;
cout << "開(kāi)始建立順序表，請(qǐng)輸入表中元素個(gè)數(shù):";
cin >> len;
if(len > maxSize) {
cout << "表元素個(gè)數(shù)輸入有誤,范圍不超過(guò)：" << maxSize << endl;
return;
}
last = len - 1; // 數(shù)組最后位置
cout << "請(qǐng)輸入建表的數(shù)據(jù):" << endl;
for(int i = 0; i <= last; i++) // 逐個(gè)輸入表元素
cin >> data[i];
}
template <class T>
void SeqList<T>::Output() {
// 將順序表全部元素輸出到屏幕上
for(int i = 0; i <= last; i++)
cout << data[i] << " ";
cout << endl;
}
template <class T>
void SeqList<T>::Sort() {
int flag;
T temp;
// 排序:從小到大
for(int i = 0; i < last; i++) { // 最后一個(gè)不用排了
flag = 0; // 標(biāo)志該輪是否有交換, 0表示沒(méi)有交換，1表示有交換
// 沒(méi)有交換，說(shuō)明已排好序，提前結(jié)束
for(int j = 0; j < (last - i); j++) { // 向后冒泡
if(data[j] > data[j + 1]) {
flag = 1;
temp = data[j+1];
data[j+1] = data[j];
data[j] = temp;
}
}
if(flag == 0) // 沒(méi)有交換，提前結(jié)束程序
break;
}
}
template <class T>
SeqList<T> SeqList<T>::operator=(SeqList<T>& L) {
int size, value;
// 表整體賦值：順序表整體賦值
size = L.Size();
if(maxSize != size) { // 表最大可容納數(shù)小于L的
reSize(size); // 該變數(shù)組大小
}
last = L.Length() - 1; // 數(shù)組的最后位置
for(int i = 1; i <= last+1; i++) {
L.getData(i, value); // 取第i個(gè)位置的值
data[i-1] = value;
}
}
#endif /* SeqList_h */
2.main.cpp
#include "SeqList.h"
using namespace std;
int main(int argc, const char * argv[]) {
int choose, len, i, x, maxSize, loc; // val存儲(chǔ)值，choose存儲(chǔ)用戶(hù)的選擇
bool finished = false;
SeqList<int> L; // 聲明SeqList對(duì)象
while(!finished) {
cout << "1:輸入數(shù)據(jù)建立順序表：" << endl;
cout << "2:順序表的最大可容納表項(xiàng)個(gè)數(shù)：" << endl;
cout << "3:順序表的長(zhǎng)度：" << endl;
cout << "4:搜索x在表中的位置：" << endl;
cout << "5:定位第i個(gè)表項(xiàng)：" << endl;
cout << "6:取第i個(gè)表項(xiàng)的值：" << endl;
cout << "7:用x修改第i個(gè)表項(xiàng)的值：" << endl;
cout << "8:在第i個(gè)表項(xiàng)后插入元素x：" << endl;
cout << "9:刪除第i個(gè)表項(xiàng)：" << endl;
cout << "10:判斷表是否為空：" << endl;
cout << "11:判斷表滿(mǎn)否：" << endl;
cout << "12:打印順序表中的數(shù)據(jù)：" << endl;
cout << "13:將順序表排序：" << endl;
cout << "14:退出：" << endl;
cout << "請(qǐng)輸入你的選擇[1-14]：" << endl;
cin >> choose;
switch(choose) {
case 1:
L.Input(); // 建立順序表
break;
case 2:
maxSize = L.Size();
cout << "順序表的最大可容納表項(xiàng)個(gè)數(shù)為：" << maxSize << endl;
break;
case 3:
len = L.Length();
cout << "順序表的長(zhǎng)度為：" << len << endl;
break;
case 4:
cout << "請(qǐng)輸入要搜索的值x:";
cin >> x;
i = L.Search(x);
if(i == 0)
cout << "沒(méi)找到" << x << endl;
else
cout << x << "在表中的第" << i << "個(gè)位置" << endl;
break;
case 5:
cout << "請(qǐng)輸入要定位的位置i：";
cin >> i;
loc = L.Locate(i);
if(loc != -1)
cout << "定位成功！在順序表中下標(biāo)為：" << loc << endl;
else
cout << "定位失敗!" << endl;
break;
case 6:
cout << "請(qǐng)輸入要取表中元素的位置i:";
cin >> i;
if(L.getData(i, x))
cout << "表中第" << i << "個(gè)表項(xiàng)的值為:" << x << endl;
else
cout << "取值失??！檢查是否超范圍取值" << endl;
break;
case 7:
cout << "請(qǐng)輸入要修改的位置i和值x:";
cin >> i >> x;
L.setData(i, x);
break;
case 8:
cout << "請(qǐng)輸入要插入的位置i和值x:";
cin >> i >> x;
if(L.Insert(i, x))
cout << "插入成功！" << endl;
else
cout << "插入失敗！" << endl;
break;
case 9:
cout << "請(qǐng)輸入要?jiǎng)h除的表項(xiàng)的位置i:";
cin >> i;
if(L.Remove(i, x))
cout << "刪除成功！刪除的值為:" << x << endl;
else
cout << "刪除失敗!" << endl;
break;
case 10:
if(L.isEmpty())
cout << "表為空！" << endl;
else
cout << "表不為空！" << endl;
break;
case 11:
if(L.isFull())
cout << "表滿(mǎn)！" << endl;
else
cout << "表未滿(mǎn)！" << endl;
break;
case 12:
cout << "表中的數(shù)據(jù)為：" << endl;
L.Output();
break;
case 13:
cout << "表中的數(shù)據(jù)排序前：" << endl;
L.Output();
L.Sort();
cout << "表中的數(shù)據(jù)排序后：" << endl;
L.Output();
break;
case 14:
finished = true;
break;
default:
cout << "輸入選擇錯(cuò)誤，請(qǐng)重新輸入!" << endl;
}
}
return 0;
}
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
在日常開(kāi)發(fā)中，我們經(jīng)常使用變量，常量，變量可以分為：全局變量、局部變量、靜態(tài)全局變量、靜態(tài)局部變量，接下來(lái)通過(guò)本文給大家介紹C++各種變量及區(qū)別，感興趣的朋友一起看看吧2022-05-05
這篇文章主要介紹了關(guān)閉所有窗口的方法,原理是枚舉所有窗口句柄，然后發(fā)送WM_CLOSE消息來(lái)關(guān)閉窗口,需要的朋友可以參考下2014-01-01
這篇文章主要為大家詳細(xì)介紹了QT實(shí)現(xiàn)簡(jiǎn)單打地鼠游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-12-12
這篇文章主要介紹了C++程序中啟動(dòng)線(xiàn)程的方法,作者針對(duì)C++11版本中的一些新特性進(jìn)行了解說(shuō),需要的朋友可以參考下2015-07-07
使用c++實(shí)現(xiàn)OpenCV繪制圓端矩形
這篇文章主要介紹了使用c++實(shí)現(xiàn)OpenCV繪制圓端矩形，其中著重的講解了OpenCV使用過(guò)程中需要注意的一些小細(xì)節(jié)，避免浪費(fèi)大家在開(kāi)發(fā)過(guò)程中浪費(fèi)多余的時(shí)間2021-08-08
C語(yǔ)言實(shí)現(xiàn)文本編輯器系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)文本編輯器系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-02-02
C++實(shí)現(xiàn)比特幣系統(tǒng)的源碼
這篇文章主要介紹了C++實(shí)現(xiàn)比特幣系統(tǒng)的源碼,本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-01-01
這篇文章主要介紹了利用C++實(shí)現(xiàn)?然連接操作算法，文章圍繞主題展開(kāi)詳細(xì)的內(nèi)容介紹，具有一定參考價(jià)值，需要的小伙伴可以參考一下2022-08-08
這篇文章主要為大家介紹了C語(yǔ)言常量的認(rèn)識(shí)和理解，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來(lái)幫助2021-12-12
C語(yǔ)言文件讀寫(xiě)操作介紹與簡(jiǎn)單示例
這篇文章主要給大家介紹了關(guān)于C語(yǔ)言文件讀寫(xiě)操作的相關(guān)資料，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2021-01-01