之前大一的时候开过数据结构这门课，不过学过之后也不知道学这个是用来做什么的，现在大三下半年了要为找实习找工作做准备，又拿起数据结构狂啃，不过已经不是当初那种挺迷惑的不知道所以然的心情了，我想这就是在实践中渐渐领悟到有些东西的缘故吧。作为一名IT专业的学生，只有理论知识，不实践，是没有前途的，因为有些东西你只有在动手的过程中，才能更好更深层的去理解它，在发现问题时运用所学的知识去解决问题，在这个过程中你会不断地成长，接受技术知识的能力也会不断地提升。
?
说说现在我对数据结构的理解吧，首先，从概念上来说数据结构是一种类型和定义在该类型上的一组操作，其次，我们学数据结构到底是用来干什么的呢？我觉得数据结构是一种能够优化我们程序性能和效率的东东，就我们要解决的具体问题所要求的资源限制（运行时间和存储空间）和达到的性能需求来说，如果我们能够选择合适的数据结构来存储数据，那么在编写程序的过程中，我们对数据的一些操作将会便于实现，实现操作的时间复杂度也会降低，这样程序的效率会提高。例如，散列表和B+树这两种数据结构都支持高效的记录插入和caozuo.html" target="_blank">删除操作及精确匹配，但是在匹配查询方面，散列表更为有效，而在范围查询方面，B+树更加有效，所以在选择数据结构时，应该视具体问题的具体需求来选择合适的，更为有效的数据结构。
?
看到书上说，水平不高的程序设计人员往往忽视了分析问题的过程，直接选用一种惯用的，熟悉的但与问题不相称的数据结构，结果设计出一个低效率的程序。确实是这样，平时我们（编程水平还不太高的这一类人）在编程的时候，可能不会想那么多，一想自己熟悉的会用的数据结构能够解决当前问题，便会拿它来存储数据，比如最常用的数组，线性表等。我想也许是现有问题中的数据量还并不是很大，所以数据结构选择的合适不合适没有在程序运行时间或占有的存储空间上很明显的反映出程序性能的好坏，我们也不会觉察或意识到我们错误的设计。不过，如果简单的设计就能达到性能目标时，选用复杂的数据结构也是没有道理的。
要想在问题中选择合适的数据结构，就必须对每一种数据结构都透彻的掌握（理论，实现），加上自己在编程中积累的经验，才能达到目的。以数据为中心，首先确定问题中数据和对数据的操作，然后确定数据的表示方法，最后实现数据表示（我们可以自己定义自己想要实现的数据结构）。
?
下面谈一下几种常用的数据结构：
一.线性表
1.线性表的概念：由称为元素的数据项组成的一种有限有序（有序指线性表中的每一个元素都有自己的位置）的序列。
注：线性表中的第一个位置是用0来表示。
线性表的C++抽象类声明：
（抽象类：成员函数都被声明为"纯虚的"，即在函数方法声明的最后有"=0"的符号。）
???????? template<class Elem> class List{
??????????????????? public:
???????????????????????????????? virtual void clear()=0;
???????????????????????????????? virtual void insert(const Elem& )=0;
???????????????????????????????? virtual void append(const Elem& )=0;
???????????????????????????????? virtual void prev()=0; //求前驱。
???????????????????????????????? virtual void next()=0; //求后继。
???????????????????????????????? virtual bool setPos(int pos)=0;
???????????????????????????????? virtual bool getValue(Elem& )?const=0;
???????????????????????????????? virtual void?print() const=0;
????????????};
2.线性表的两种实现方法：顺序表和链表。
1>顺序表的c++实现
顺序表中有一个数据成员fence，用来存储栅栏（当前位置）的位置，栅栏将表分为左右两个部分。
顺序表AList类继承了线性表抽象类List。
???template<class Elem>class AList:public List<Elem>{
??????? private:
??????????????????? int maxSize;//顺序表的最大长度。
??????????????????? int fence;//存储栅栏的位置（即当前位置）的值。
??????????????????? int listSize;//顺序表当前的长度。
??????????????????? Elem*? listArray;
??????? public:
??????????????????? AList(int size=defaultListSize){
??????????????????????????? maxSize=size;
??????????????????????????? listSize=fence=0;
??????????????????????????? listArray=new Elem[maxSize];
??????????????????? }
???????????????????~AList(){ delete[] listArray;}
?????????????????? void clear(){
????????????????????????????delete[] listArray;
??????????????????????????? listSize=fence=0;
??????????????????????????? listArray=new Elem[maxSize];
??????????????????? }
?????????????????? bool getValue(Elem& it) const{
??????????????????????????? if(rightLength()==0)? return false;
??????????????????????????? else{? it=listArray[fence]; return true;}
?????????????????? }
?????????????????? bool find(Elem& k){
??????????????????????????? int it;
??????????????????????????? for(listArray.setStart();listArray.getValue(it);ListArray.next())
??????????????????????????????????????? if(k==it) return true;
????????????????????????????return false;
?????????????????? }
?????????????????? ...
???????? };
在顺序表中插入和删除平均要移动一半数据，即需要O(n)时间。
?
2>链表：利用指针实现线性表。
链表由一系列称为表的结点类（结点类中包括数据域和指针域）的对象组成。可以按照需要为表中新的元素分配存储空间。（动态的）
?一个链表实现的关键设计是怎样表现栅栏(fence)，最合理的选择是用指向左边部分的最后一个元素或者是指向右边部分的第一个元素。一般选择指向左边部分的最后一个元素。
链表依据有没有前驱指针又分为单链表和双链表。
a.单链表：每个结点只有一个指向表中下一结点的指针。
单链表的Link类（结点类）的对象包含一个存储元素值的element域和一个存储表中下一个结点指针的next域。
单链表结点类的定义：
?????????? template<class Elem> class Link{
?????????????????? public:
????????????????????????????? Elem element;
????????????????????????????? Link? *next;
????????????????????????????? Link(const Elem& elemval , Link* nextval=null){
??????????????????????????????????????? element=elemval;
??????????????????????????????????????? next=nextval;
????????????????????????????? }
??????????????????????????????Link(Link *nextval=null){
??????????????????????????????????????? next=nextval;
????????????????????????????? }
?????????? };
单链表的实现声明：
??????????template<class Elem> class LList:public?List<Elem>{
???????????????????private:
?????????????????????????????? Link<Elem> *head;? ?//头指针，指向链表中的第一个结点。
????????????????????????????? ?Link<Elem> *tail;? //尾指针，指向链表中的最后一个结点。
???????????????????????????????Link<Elem> *fence; //指向"栅栏"的位置。 栅栏将链表分为左右两部分。
?????????????????????????????? int?leftLength;? ?//fence指针指向结点左边的链表结点的个数。
?????????????????????????????? int rightLength;?? //fence指针指向结点右边的链表结点的个数。
????????????????? ?public:?
???????????????????????????????void init(){
?????????????????????????????????? fence=tail=head=new Link<Elem>;
?????????????????????????????????? leftLenght=rightLength=0;
????????????????????????????? ?}
?????????????????????????????? void setStart(){
???????????????????????????????????fence=head;? rightLenght+=leftLength;?? leftLength=0;
???????????????????????????????}
???????????????????????????????void setEnd(){
?????????????????????????????????? fence=tail;? leftLength+=rightLength;? rightLength=0;
?????????????????????????????? }
?????????????????????????????? void next(){
????????????????????????????????? if(tail !=null){? fence=fence->next; ?rightLength++;? leftLength--; }
?????????????????????????????? }
?????????????????????????????? bool getvalue(Elem& it) const{
??????????????????????????????????if(rightLenght()==0)? return false;
??????????????????????????????????it=fence->next->element;? return true;
?????????????????????????????? }
??????????????????????????????//向栅栏位置（fence指向的地方，即链表的右部分）插入一个元素。
?????????????????????????????? bool insert(const Elem& item){
??????????????????????????????????fence->next=new Link<Elem>( item, fence->next);
??????????????????????????????????if(tail==fence)? tail=tail->next;?? rightLength++;? return true;
?????????????????????????????? }
????????????????????????????? ?//向链表的末尾插入一个结点。
???????????????????????????????bool append(const Elem& item){
????????????????????????????????? tail=tail->next=new Link<Elem>( item,null);
??????????????????????????????????rightLength++;? return true;
???????????????????????????????}
??????????????????????????????//删除右部分的第一个元素。
????????????????????????????? bool remove(Elem& it){
????????????????????????????????? if(fence->next==null)? return false;
??????????????????????????????????it=fence->next->element;?
??????????????????????????????????Link<Elem> * Itemp=fence->next;
????????????????????????????????? fence->next=Itemp->next;
????????????????????????????????? if(tail==Itemp)? tail=fence;
??????????????????????????????????delete Itemp;
????????????????????????????????? rightLenght--;
????????????????????????????????? return true;
????????????????????????????????}
?????????????????????????????? //向左移动fence指针一个位置。
?????????????????????????????? /*在单链表中，没有指向前驱结点的指针，所以要实现prev()方法，需要从表头沿链表移
???????????????????????????????? 动，直到找到当前结点。
??????????????????????????????? void prev(){
???????????????????????????????????Link<Elem>? *temp=head;
?????????????????????????????????? if(fence==head)? return;
?????????????????????????????????? while(temp->next!=fence) temp=temp->next;
?????????????????????????????????? fence=temp;
???????????????????????????????????leftLength--;?
?????????????????????????????????? rightLength++;
????????????????????????????????}
??????????????????????????????? .....
????????????????? };??????????????????????????????????????
?双链表，可利用空间表，栈，递归，队列，字典，hashu.html" target="_blank">二叉树，查找二叉树，堆，Huffman树，待续。。。
相关文章
