看了一下其他链接,真正的循序表应该支持随机索引的,也就是new的时候就将内存分配好。
这里是像链表一样申请了,当做链表看吧
参考链接:数据结构与算法——顺序表和链表的优缺点(区别、特点)详解_顺序表和链表的优缺点(区别、特点)详解-CSDN博客
代码
#include<iostream>
#include<cmath>
using namespace std;
// 具体的元素 ,这里以书本为例
struct element {element * next;int index; // 书本编号 int value; // 价格 string name; // 书本名称
};
// 代表序列整体信息
struct sequence{element * next; // 指向下一个序列的指针int size; // 当前元素树木个数int maxIndex; // 最大编号 int sum; // 寻找最后一个元素指針 element* findLast() {element* it = this->next;while(it->next) {it = it->next;
// cout<<"寻找下一个"<<endl;}return it; } // 最后一个值 int last() {element* it = this->findLast();return it->value;}// 第一个值 int front() {element* it = this->next->next;return it->value;}// 向顺序表添加末尾一个元素 void push(int price,string name ) {element* newEle = new element();
// cout<<"断点1"<<endl; newEle->index = this->maxIndex;newEle->value = price;newEle->name = name;
// cout<<"断点2"<<endl; // 将新节点加入最后 element* last = this->findLast();last->next = newEle;
// cout<<"断点3"<<endl; // 更新数据this->size ++; this->maxIndex ++; // 确保每本书的Id不一样 this->sum += newEle->value;} // 向顺序表删除第一个元素 ,返回被删除的值 ,假设一切操作合理 int pop() {
// cout<<"断点4"<<endl; element* ele = this->next->next;this->next->next = ele->next;
// cout<<"断点5"<<endl; // 更新数据 this->size --;this->sum -= ele->value;return ele->value;}// 打印順序表状态void printSate() {cout<<"序列长度:"<<this->size<<endl;cout<<"序列总和:"<<this->sum<<endl;}// 清空void reset() {// 后续加上回收 this->next = new element();this->size = 0;this->sum = 0;} // 获取第x个元素,如果超出则显示最后一个元素 int getElement(int num) {int len = min(num,this->size); element* it = this->next;for(int i=0 ;i<len;i++) {it = it->next;}return it->value;} // 按照name字段查找 返回index int findByName(string name){element* it = this->next;while(it->next) {it = it->next;if(it->name == name) {return it->index;} }return -1;// 没找到 }// 遍历元素 打印书本价格 void printELementsValue() {element* it = this->next;while(it->next) {it = it->next;cout<<it->value<<" ";}cout<<endl;} // 遍历元素 打印书本名称 void printELementsName() {element* it = this->next;while(it->next) {it = it->next;cout<<it->name<<" ";}cout<<endl;}
};
// 思考:
// 1.无效的操作如何阻止,比如在没有元素时的pop和front和last操作?
// 2. 如何将指针->引用,使用属性.引用 代替? // 初始化一个空顺序表
sequence* initSequence() {sequence* a = new sequence();a->size = 0;a->sum = 0;a->maxIndex = 0; a->next = new element(); // 确认必须会有一个element return a;
}// 测试样例 1 (Accept)只有push
void test1(sequence *seq);
// 测试样例 2 (Accept)push + pop
void test2(sequence *seq);
// 测试样例 3 (Accept)push + reset
void test3(sequence *seq);
// 测试样例 4 (Accept)push + pop + front + last
void test4(sequence *seq);
// 测试样例 5 (Accept)push + pop + printELementsValue + printELementsName
void test5(sequence *seq);signed main() {cout<<"断点start"<<endl; sequence* seq = initSequence(); test1(seq);test2(seq);test3(seq);test4(seq);test5(seq);cout<<"断点end"<<endl; return 0;
}void test1(sequence *seq) {seq->push(1,"Alice");seq->push(2,"Bob");seq->push(3,"安徒生");seq->push(2,"Alice");seq->push(7,"格林语言");seq->push(5,"中华上下五千年");seq->printSate();
}void test2(sequence *seq) {seq->push(3,"钢铁是怎样炼成的");seq->push(2,"A");seq->push(1,"B");seq->push(5,"V");seq->push(7,"D");seq->printSate();seq->pop();seq->pop();seq->printSate();
}
void test3(sequence *seq) {test1(seq);seq->reset();seq->printSate();
}
void test4(sequence *seq){test2(seq);cout<<seq->front()<<endl;cout<<seq->last()<<endl;
}
void test5(sequence *seq){test1(seq);test2(seq);seq->printELementsValue();seq->printELementsName();
}
这里的想法是,线性表是一个独立的个体,但是它又由多个元素组成
于是将线性表设计成单独的结构体,此外的元素对象单独再设计另一个结构体
// 具体的元素 ,这里以书本为例
struct element {element * next;int index; // 书本编号 int value; // 价格 string name; // 书本名称
};
// 代表序列整体信息
struct sequence{element * next; // 指向下一个序列的指针int size; // 当前元素树木个数int maxIndex; // 最大编号 int sum;
}
我们创建好结构体之后,使用 new()就可以创建一个该对象。
为了能够检测到sequence对象是否为空,我们会再第一个元素设置一个空的元素对象,当做虚拟头结点,放在初始化的时候
// 初始化一个空顺序表
sequence* initSequence() {sequence* a = new sequence();a->size = 0;a->sum = 0;a->maxIndex = 0; a->next = new element(); // 确认必须会有一个element return a;
}
在结构体下面写一些函数,使用this指代当时实例化的对象,其再运行时确定具体值,用来引用自身属性。
// 寻找最后一个元素指針 element* findLast() {element* it = this->next;while(it->next) {it = it->next;
// cout<<"寻找下一个"<<endl;}return it; } // 最后一个值 int last() {element* it = this->findLast();return it->value;}// 第一个值 int front() {element* it = this->next->next;return it->value;}// 向顺序表添加末尾一个元素 void push(int price,string name ) {element* newEle = new element();
// cout<<"断点1"<<endl; newEle->index = this->maxIndex;newEle->value = price;newEle->name = name;
// cout<<"断点2"<<endl; // 将新节点加入最后 element* last = this->findLast();last->next = newEle;
// cout<<"断点3"<<endl; // 更新数据this->size ++; this->maxIndex ++; // 确保每本书的Id不一样 this->sum += newEle->value;} // 向顺序表删除第一个元素 ,返回被删除的值 ,假设一切操作合理 int pop() {
// cout<<"断点4"<<endl; element* ele = this->next->next;this->next->next = ele->next;
// cout<<"断点5"<<endl; // 更新数据 this->size --;this->sum -= ele->value;return ele->value;}// 打印順序表状态void printSate() {cout<<"序列长度:"<<this->size<<endl;cout<<"序列总和:"<<this->sum<<endl;}// 清空void reset() {// 后续加上回收 this->next = new element();this->size = 0;this->sum = 0;} // 获取第x个元素,如果超出则显示最后一个元素 int getElement(int num) {int len = min(num,this->size); element* it = this->next;for(int i=0 ;i<len;i++) {it = it->next;}return it->value;} // 按照name字段查找 返回index int findByName(string name){element* it = this->next;while(it->next) {it = it->next;if(it->name == name) {return it->index;} }return -1;// 没找到 }// 遍历元素 打印书本价格 void printELementsValue() {element* it = this->next;while(it->next) {it = it->next;cout<<it->value<<" ";}cout<<endl;} // 遍历元素 打印书本名称 void printELementsName() {element* it = this->next;while(it->next) {it = it->next;cout<<it->name<<" ";}cout<<endl;}
测试样例使用方法进行模拟,传入具体的顺序表的实例对象,即可进行添加操作
void test1(sequence *seq) {seq->push(1,"Alice");seq->push(2,"Bob");seq->push(3,"安徒生");seq->push(2,"Alice");seq->push(7,"格林语言");seq->push(5,"中华上下五千年");seq->printSate();
}void test2(sequence *seq) {seq->push(3,"钢铁是怎样炼成的");seq->push(2,"A");seq->push(1,"B");seq->push(5,"V");seq->push(7,"D");seq->printSate();seq->pop();seq->pop();seq->printSate();
}
void test3(sequence *seq) {test1(seq);seq->reset();seq->printSate();
}
void test4(sequence *seq){test2(seq);cout<<seq->front()<<endl;cout<<seq->last()<<endl;
}
void test5(sequence *seq){test1(seq);test2(seq);seq->printELementsValue();seq->printELementsName();
}