线性表
2016-08-16 本文已影响11人
Houzhuo
线性表是n个相同数据类型的元素组成的有限序列。
线性表按照存储结构可分为顺序表和链表。
顺序表都是内存地址连续的元素组成的！
顺序表的构建
- 定义元素个数和顺序表最大容量，初始化指针
- 在构造函数中传参来确定size；length设为0；初始化指针地址。
#include <iostream>
#include <cstring>
using namespace std;
class Vector {
private:
int size, length;
int *data;
public:
Vector(int input_size) {
size = input_size;
length = 0;
data = new int[size];
}
~Vector() {
delete[] data; // 析构函数中进行删除
}
};
int main() {
Vector a(2);
return 0;
}
顺序表的插入:
在insert方法中定义了参数loc，value。loc为插入的位置，value代表插入的数值。每次插入都要将序列loc之后的元素向后移动一位，并且长度length增加1。成功返回true，否则false。
-
判断loc位置是否合法。位于0到length之间（包括length），有元素在序列上才可以进行插入，所以开始为空时要顺序插入。并且元素左右两边都可插入（所以位置为length时依然合法）。 -
判断元素个数是否超出最大容量（长度相等时就不能插入了，再插溢出）。 - 将loc（包括loc）之后的元素
右移。 - 插入
赋值。 - 元素
个数加1。
在构造函数中添加insert方法
bool insert(int loc, int value) {
if(loc < 0 || loc > length){
return false;
}
if (length >= size){
return false;
}
for (int i = length; i > loc; i--){
data[i] = data[i-1];
}
data[loc] = value;
length += 1;
return true;
}
顺序表的扩容：
通产来说，扩容通常是将容量修改为以前的两倍；扩容时要重新开辟一块空间并把原有数据 依次 拷贝过去，再将原来的 空间 释放
- 保存原始数据到
旧指针。 - 容量
加倍。 - 指针指向新size
开辟的新空间。 - 数据
拷贝。 - 在insert中
调用 回收
bool insert(int loc, int value) {
if (loc < 0 || loc > length) {
return false;
}
if (length >= size) {
//return false;
expand();
}
for (int i = length; i > loc; --i) {
data[i] = data[i - 1];
}
data[loc] = value;
length++;
return true;
}
void expand(){
int *old_data = data
size = size * 2;
data = new int[size] ;
for(int i = 0; i <length;i ++){
data[i] = old_data[i];
}
delete[] old_data;
}
顺序表的查找
接收一个int类型的value，返回该值对应的下表，没有返回－1
从零循环到小于length，枚举匹配：
int search(int value) {
for(int i=0; i < length; i++){
if (data[i] == value){
return i
}
}
return -1;
}
顺序表的删除：index之后的元素向前移动一位。
-
判断index是否在元素中 - index之后的元素向
前移动 - 元素个素
减1，返回true
bool remove(int index) {
if(index < 0 || index >= length){
return false
}
for(int i = index + 1; i < length; i++){
data[i-1] = data[i];
}
length -= 1;
return true;
}
顺序表的遍历
把顺序表的所有元素输出到一行，并用空格分开。
- 判断第一个元素，不要输出空格
- 循坏遍历输出
void print() {
for(int i = 0; i<length; i++){
if(i > 0){
cout << " ";
}
cout << data[i];
}
cout << endl; //输出空行
}
完整代码：
#include <iostream>
#include <cstring>
using namespace std;
class Vector {
private:
int size, length;
int *data;
public:
Vector(int input_size) {
size = input_size;
length = 0;
data = new int[size];
}
~Vector() {
delete[] data;
}
bool insert(int loc, int value) {
if (loc < 0 || loc > length) {
return false;
}
if (length >= size) {
return false;
}
for (int i = length; i > loc; --i) {
data[i] = data[i - 1];
}
data[loc] = value;
length++;
return true;
}
int search(int value) {
for (int i = 0; i < length; ++i) {
if (data[i] == value) {
return i;
}
}
return -1;
}
bool remove(int index) {
if (index < 0 || index >= length) {
return false;
}
for (int i = index + 1; i < length; ++i) {
data[i - 1] = data[i];
}
length = length - 1;
return true;
}
void print() {
for(int i = 0; i<length; i++){
if(i > 0){
cout << " ";
}
cout << data[i];
}
cout << endl
}
};
int main() {
Vector a(2);
cout << a.insert(0, 1) << endl;
cout << a.insert(0, 2) << endl;
a.print();
cout << a.remove(1) << endl;
a.print();
cout << a.search(0) << endl;
cout << a.search(1) << endl;
return 0;
}
引用：计蒜客
