非连续内存线性表,C++ list 单链表 简单实现 同时也是栈结构的实现
#includeusing namespace std; template class lifo{//先实现一个简单的list public: lifo() { this->data = 0; this->next = nullptr; } void in(T value) { lifo *insert = new lifo ; //首先先进行初始化,作为首地址 insert->data = value; //进行值的插入 insert->next = this->end; this->end = insert; } void printList(void) { while (this->end != nullptr) { //需要使用一个临时变量,替换替代一下 cout << "index: " << this->end->data<< endl; this->end = this->end->next; } } private: T data; lifo * end; //必须多出一个尾指针进行使用, 记录线性表开始遍历的地址; lifo * next; }; int main(void) { lifo test; test.in(1); test.in(2); test.in(3); test.in(4); test.printList(); }
C++ 中 无法修改 this 指针的地址（仔细想想也应该）所以不能像C中使用的那样 可移动初始地址,作为数据遍历的头部 上面的代码是头插法
templateclass fifo { public: fifo() { this->data = 0; this->next = nullptr; } void in(T value) { fifo * node = new fifo ; node->data = value; if (this->ptr == nullptr) { this->ptr = node; } else { this->tmp->next = node; } this->tmp = node; node->next = nullptr; } void printList(void) { //fifo * tmp = this; while (ptr != nullptr) { //需要使用一个临时变量,替换替代一下 cout << "index: " << ptr->data << endl; ptr = ptr->next; } } private: T data; fifo * ptr; //线性表的头部, 实际常说的迭代器 fifo * tmp; //需要迭代移动的指针 fifo * next; //链接地址使用 }; int main(void) { fifo test; test.in(1); test.in(2); test.in(3); test.in(4); test.printList(); }
这里面的new 和 delete 操作可以受用 auto_ptr 替代，会更加省心
C++ 中有现成的算法容器.以上只为熟悉类的内存分布和使用
// Cplus数据结构阶段复习three.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。 // #include//循环列表约瑟夫问题 // using namespace std; //双向结构的好处在与,在任何一个地址下,都可以进行遍历 template class circle { public: circle() { //无参构造方法 // cout << "no para init" << endl; this->data = 0; this->next = nullptr; } circle(T v) :data(v) { //有参构造方法 // cout << "one para init" << endl; this->in(this->data); } void in(T value) { circle * node = new circle ; node->data = value; if (this->ptr == nullptr) { this->ptr = node; //确立第一个节点的位置 this->begin = node; } else { this->tmp->next = node; node->pre = this->tmp; } this->tmp = node; this->end = this->tmp; //完成首尾循环建立 this->end->next = this->begin; this->begin->pre = this->end; size++; } void printList(void) { //fifo * tmp = this; while (size--) { // 循环建立表成功; 设置退出条件 cout << "index: " << end->data << endl; end = end->pre; } } T get_begin_data(void) { return this->begin->data; } T get_end_value(void) { return this->end->data; } private: T data; int size=0; circle * begin; //循环时需要用到的头部指针 circle * end; //循环时需要用到的尾部指针 circle * ptr; //线性表的头部, 实际常说的迭代器 circle * tmp; //需要迭代移动的指针 circle * pre; //前驱链接地址 circle * next; //后继链接地址使用 }; int main(void) { circle test(19); //需要实现一个构造时初始值的复制, 初始化的第一个值,一个list基类基本可以使用 test.in(1); test.in(2); test.in(3); test.in(4); test.printList(); }
FIXME 概述一下约瑟夫环的问题:
按照约定的规则删除，环形表中的数据, （能不能并发删除,这是一个好的问题,单步删除倒是很容易想到?）
最后只剩下一个数据元素（我用 bitmap 直接删除会不会更爽?）
使用栈实现就近匹配原则: 简单的匹配左右括号
// Cplus数据结构阶段复习three.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。 // #include//循环列表约瑟夫问题 // using namespace std; //双向结构的好处在与,在任何一个地址下,都可以进行遍历 template class circle { public: circle() { //无参构造方法 // cout << "no para init" << endl; this->data = 0; this->next = nullptr; } circle(T v) :data(v) { //有参构造方法 // cout << "one para init" << endl; this->in(this->data); } void in(T value) { circle * node = new circle ; node->data = value; if (this->ptr == nullptr) { this->ptr = node; //确立第一个节点的位置 this->begin = node; } else { this->tmp->next = node; node->pre = this->tmp; } this->tmp = node; this->end = this->tmp; //完成首尾循环建立 this->end->next = this->begin; this->begin->pre = this->end; size++; } void printList(void) { //fifo * tmp = this; while (size--) { //需要使用一个临时变量,替换替代一下; 循环建立表成功 cout << "index: " << end->data << endl; end = end->pre; } } T get_begin_data(void) { return this->begin->data; } T get_end_value(void) { return this->end->data; } private: T data; int size=0; circle * begin; //循环时需要用到的头部指针 circle * end; //循环时需要用到的尾部指针 circle * ptr; //线性表的头部, 实际常说的迭代器 circle * tmp; //需要迭代移动的指针 circle * pre; //前驱链接地址 circle * next; //后继链接地址使用 }; template class lifo {//先实现一个简单的list public: lifo() { this->data = 0; this->next = nullptr; } void in(T value) { lifo * insert = new lifo ; //首先先进行初始化,作为首地址 insert->data = value; //进行值的插入 insert->next = this->end; this->end = insert; size++; } void out(void) { if (size == 0) { return; } lifo * tmp = this->end; this->end = this->end->next; //移动到最新的栈顶 delete[] tmp; //释放弹出的栈顶内存空间 tmp = nullptr; size--; } T stack_top(void) { if (this->end != nullptr) return this->end->data; return 0; //返回一个空顶,用以判断栈顶不存在该元素 } void printList(void) { while (this->end != nullptr) { //需要使用一个临时变量,替换替代一下 cout << "index: " << this->end->data << endl; this->end = this->end->next; } } private: int size=0; T data; lifo * end; //必须多出一个尾指针进行使用, 记录线性表开始遍历的地址; lifo * next; }; int main(void) { //circle test(19); //需要实现一个构造时初始值的复制, 初始化的第一个值,一个list基类基本可以使用 //test.in(1); //test.in(2); //test.in(3); //test.in(4); //test.printList(); char text[] = "hello world))"; //栈的使用就近匹配原则; int len = strlen(text); lifo check; int check_sym = 0; try { for (int i = 0; i < len; i++) { //常见的括号匹配 if (text[i] == '(') { check.in(text[i]); //入栈 check_sym++; } else if (text[i] == ')') { if (check.stack_top() == '(') { check.out(); //左括号出栈； 如果匹配就说明没有任何问题 } else { cout << "括号不匹配" << endl; throw i; } } } } catch(int error){ cout << "右括号不匹配: " << text << endl; text[error] = ' '; cout << "右括号不匹配: " << text << endl; } if (check_sym == 0) { cout << "缺少左括号" << endl; } }
