Question

c++链表栈问题

以前感觉自己的c++还行，现在学到链表，学到面对对象程序设计，感觉自己就是个渣，特别是要加入什么头文件，还有几个cpp格式的文件要组合起来，完全不知道要怎么写起？望高人指点。万分感谢！





Answer 1

在要求上是说要模拟stl stack的话，这个就比较麻烦了，咱先说一下怎么建立一个普通栈。
业界惯例的抿了一口咖啡之后，我们拿起笔来：
1.建立抽象模型，说起来这件事得追溯到C++本身的结构上：从广义上看，类是一个数据操作集合体，即使数据结构也不外乎如是。那么我们必须知道栈需要什么——这是一切问题的起点。数据结构是数据模型的实现，围绕数据为中心，操作为主要手段的语义模型。真正具体化到C++的类中，我们就是要确定储存结构（系统结构）和与之关联的操作方式。按照题目的要求：我们需要一个存储区域（大小、位置、访问性等先不确定）、一组操作：Pop 、Push、IsEmpty、GetTop、operator=。如此这般，我们确定了属性和方法的最小集。
2.将方法和属性绑定到一起，就比如手长在你身上你却不知道怎么用就糗大了。首先要考察的是操作的性质，这会影响到我们选择的存储区，很明显的使用顺序存储会非常之方便，毕竟操作永远都是指向一个位置的顺序操作，采用顺序存储会非常省事。随机操作就适合于使用链式存储了。顺序存储通常的实现是数组，有个小问题就是这货是有限连续分配，不适合变长栈。
3.我们要增加隐含的辅助方法：存储区管理相关——初始化存储区、清理存储区等方法。必要时还应加入错误处理方法。
4.方法访问存储区的实现：用什么方式在方法中获得存储区中特定位置的数据。比如顺序存储区：加上一个指向栈顶指针（？或者标志索引，反正任何方式你能直接访问到才行），一般我们选整数索引，pop、push这两个操作只要按照其语义处理（强烈建议你注意栈底的判断和栈满的判断，无论是顺序还是链式存储都必须注意这些）比如push: topptr++，stackmem[top]=custdata;
5.简单栈就此完结。
stl的stack的话，这个类是一个适配器类型，就是他完全不是一个数据类型实现，而是把某种数据结构直接作为存储结构，然后包装一下直接搞过来了。想要完全模仿的话需要理解STL的设计思想，建议参考Generic programming and the stl （中文版）p.505页，这里有stack的详细描述。当然你也直接按照concept直接构造一个stack。

追问

谢谢！！！多讲一下思路可以吗？万分感谢！

追答

如果初学数据结构的话，不建议去读STL，STL不是一个数据结构的模范实现，它是一个泛型编程库，更准确地说是一个通用算法泛型库。模仿STL这件事基本上不用想了，基本上是做不来的。
唯一能做的是按照抽象模型来写代码，即使题目说去模仿stl，这件事对于一个一流本科毕业生仍然是非常难的一件事。推荐的实现是：数据结构-C++实现（作者：缪淮扣/顾训穰/沈俊 出版社：科学出版社 出版日期：2009-02 ISBN：7030104579），代码虽然有错误，但是思路很清晰。

刚刚我看到标题了，你这题目是链栈类啊，这个需要一个链表作为内部存储区，反正就是你得先写一个双向链表（单向也是可以的，不过时间复杂度会提高）。然后封装一下方法就好了。

Answer 2

#include<iostream>using namespace std;template<class E,class K>class SortedList{public: SortedList(int MaxListSize=10); ~SortedList(){delete []element;} bool IsEmpty()const {return length==0;} bool Search(const K&k,E&e)const; SortedList<E,K>& Delete(const K& k, E& e); SortedList<E,K>& Insert(const E& e); SortedList<E,K>& DistinctInsert(const E& e); void Output() const; private: int length; int MaxSize; E *element; // dynamic 1D array};template<class E,class K>SortedList<E,K>::SortedList<E,K>(int MaxListSize){ MaxSize=MaxListSize; element=new E[2*MaxSize]; cout<<"input MaxSize number:"<<endl; for(int i=0;i<MaxSize;i++) { int k; cin>>k; element[i]=k; } length=MaxSize;}template<class E,class K>bool SortedList<E,K>::Search(const K&k,E&e)const{ int i=0; while(i<length&&k>element[i]) i++; if(i>=length||k!=element[i]) return false; e=element[i]; return true;}template<class E,class K>SortedList<E,K>&SortedList<E,K>::Delete(const K& k, E& e){ int i=0; while(i<length&&k>element[i]) i++; e=element[i]; for(int j=i+1;j<length;j++) element[j-1]=element[j]; length--; return *this;}template<class E,class K>SortedList<E,K>&SortedList<E,K>::Insert(const E&e){ int i=0; while(i<length&&e>element[i]) i++; element[i]=e; for(int j=length-1;j>=i;j--) element[j+1]=element[j]; length++; return *this;}template<class E,class K>SortedList<E,K>&SortedList<E,K>::DistinctInsert(const E& e){ int i=0; while(i<length&&e) i++; //if(e=element[i]) //throw BadInput(); element[i]=e; for(int j=length-1;j>=i;j--) element[j+1]=element[j]; length++; return *this;}template<class E,class K>void SortedList<E,K>::Output()const{ for(int i=0;i<length;i++) cout<<element[i]<<" "; cout<<endl;}int main(){ int e; SortedList<int,int> C(10); C.Output(); C.Insert(12).Insert(12).Insert(10); C.Output(); C.Delete(1,e); C.Output();}给你个我的程序吧，你对照改就是了

追问

关键是看不懂。。怎么改？？

Answer 3

先定义一个结构体，然后建立一个类，构造函数中创建链表，析构函数中删除链表，在编写push,pop,IsLinkListNull函数，在main函数中建立该类的两个实例，调用之，有空可以帮你写。