`
香煎马鲛鱼
  • 浏览: 109403 次
  • 性别: Icon_minigender_2
社区版块
存档分类
最新评论

链表和顺序表的实现c++版(绝对能用)

    博客分类:
  • C++
阅读更多

最近在重新复习C++基础知识点,复习到链表和顺序表,把之前的代码整理出来给大家参考;

 

我的注释算是比较详细的,所以就不做过多解释了;

 

贴代码的话只把具体实现贴出来,如果想要完整代码的我已经提供下载链接了哦,希望对大家有帮助:

 

首先是纯虚函数,两个表都继承此函数:headlist.h

#ifndef LISTHEAD_H

#defineLISTHEAD_H

 

#include<iostream>

usingnamespace std;

template <classElem> classlisthead{

public:

      virtualvoidclear() = 0;

      virtualboolinsert(Elem&,int i) = 0;

      virtualboolappend(Elem&) = 0;

      virtualboolremove(Elem&) = 0;

      virtualvoidsetStart() = 0;

      virtualvoidsetEnd() = 0;

      virtualvoidprev() = 0;

      virtualvoidnext() = 0;

      virtualintleftLength() const = 0;

      virtualintrightLength() const = 0;

      virtualboolsetPos(int pos) = 0;

      virtualboolgetValue(Elem&) const = 0;

      virtualvoidprint() const = 0;

};

#endif

 

顺序表实现:

//顺序表:

#ifndef ALIST_H

#defineALIST_H

#include"listhead.h"

#include"Link.h"

template <classElem> classAlist : publiclisthead<Elem>

{

private:

      int maxSize;

      int listSize;

      int fence;

      Elem* listArray;

 

public:

      Alist(int size);

      ~Alist();

      boolchangeMaxSize(int newMaxsize);//改变顺序表最大长度

      boolinsert(Elem& it, int num);//插入元素

      boolappend(Elem& item);//在末端添加元素

      boolremove(Elem& item);//删除元素

      voidsetStart();//将栅栏放置在开始处

      voidsetEnd();//将栅栏放置在末端

      voidprev();//栅栏前移

      voidnext();//栅栏后移

      voidclear();//清空队列

      intleftLength() const;

      intrightLength() const;

      boolsetPos(int pos);

      boolgetValue(Elem& it) const;

      voidprint() const;//打印

      voidreverlist();//逆置

};

 

      template<classElem>

      Alist<Elem>::Alist(intsize){

           maxSize = size;

           listSize = fence = 0;

           listArray = newElem[maxSize];

      }

      template<classElem>

      Alist<Elem>::~Alist(){

           delete[] listArray;

           listSize = fence = 0;

           listArray = newElem[maxSize];

      }

      template<classElem>

      boolAlist<Elem>::changeMaxSize(intnewMaxsize){

           Elem* newlistArray;

           newlistArray = new  Elem[newMaxsize];

           for (int i = 0; i < newMaxsize; i++){

                 newlistArray[i] = listArray[i];

           }

           listArray = newlistArray;

           if (listSize>newMaxsize){

                 listSize = newMaxsize;

 

            }

           if (fence > listSize){

                 fence = listSize;

           }

           maxSize = newMaxsize;

//         delete[] newlistArray;

           returntrue;

      }

      template<classElem>

      boolAlist<Elem>::insert(Elem& it, intnum){

           if (listSize == maxSize || num<0 || num > listSize){

                 returnfalse;

           }

           else

           {

                 for (int i = listSize; i > num; i--){

                      listArray[i] = listArray[i - 1];

                 }

                 listArray[num] = it;

                 listSize++;

                 fence = num;

                 returntrue;

           }

      }

      template<classElem>

      boolAlist<Elem>::append(Elem& item){

           if (listSize == maxSize){

                 returnfalse;

           }

           listArray[listSize++] = item;

           returntrue;

      }

 

      template<classElem>

      boolAlist<Elem>::remove(Elem& item){

           if (rightLength() == 0){

                 returnfalse;

           }

           for (int i = 0; i < listSize; i++){

                 if (listArray[i] == item){

                      fence = i;

                      break;

                 }

           }

           item = listArray[fence];

           for (int i = fence; i<listSize - 1; i++){

                 listArray[i] = listArray[i + 1];

           }

           listSize--;

           returntrue;

      }

      template<classElem>

      voidAlist<Elem>::setStart(){

           fence = 0;

      }

      template<classElem>

      voidAlist<Elem>::setEnd(){

           fence = listSize;

      }

      template<classElem>

      voidAlist<Elem>::prev(){

           if (fence != 0)

                 fence--;

      }

      template<classElem>

      voidAlist<Elem>::next(){

           if (fence <= listSize - 1)

                 fence++;

      }

      template<classElem>

      intAlist<Elem>::leftLength() const{

           return fence;

      }

      template<classElem>

      intAlist<Elem>::rightLength() const{

           return listSize - fence;

      }

      template<classElem>

      boolAlist<Elem>::setPos(intpos){

           if ((pos >= 0) && (pos <= listSize)){

                 fence = pos;

           }

           return (pos >= 0) && (pos <= listSize);

      }

      template<classElem>

      boolAlist<Elem>::getValue(Elem& it) const{

           if (rightLength() == 0) returnfalse;

           else

           {

                 it = listArray[fence]; returntrue;

           }

      }

      template<classElem>

      voidAlist<Elem>::print() const

      {

           int temp = 0;

           cout << "<";

           while (temp<fence){ cout << listArray[temp++] << " "; }

           cout << " | ";

          

           while (temp<listSize){ cout << listArray[temp++] << " "; }

           cout << " \n";

           cout << listSize << " "<<fence<<endl;

      }

      template<classElem>

      voidAlist<Elem>::reverlist(){

           int i;

           for (i = 0; i<listSize / 2; i++){

                 listArray[listSize + 1] = listArray[i];

                 listArray[i] = listArray[listSize - i - 1];

                 listArray[listSize - i - 1] = listArray[listSize + 1];

           }

      }

      //删除列表中的数据

      template<classElem>

      void  Alist<Elem>::clear(){

      }

#endif

 

链表实现:

//节点

#ifndef LINK_H

#defineLINK_H

#include"listhead.h"

template <classElem> classLink{

public:

      Elem element;//节点元素

      Link *next;//指向下一个元素

      Link(constElem& elemval,Link* nextval =NULL){

      element = elemval;next = nextval;

      }

    Link(Link* nextval =NULL){

      next = nextval;

      }

};

#endif

 

#ifndef ALIST_L

#defineALIS_L

#include"listhead.h"

template<classElem> classLList:publiclisthead<Elem>{

private:

      Link<Elem> *head;//头节点(不存数据)

      Link<Elem> *tail;//尾节点

      Link<Elem> *fence;//栅栏

      int leftcnt;

      int rightcnt;

      int size;//链表长度

      voidinit(){//初始化

           fence = tail = head = newLink<Elem>;

           leftcnt = rightcnt = 0;

           size = 1;

      }

      voidremoveall(){//清空所有

           while (head != NULL)

           {

                 fence = head;

                 head = head->next;

                 delete fence;

           }

      }

public:

      LList( intsize = DefaultListSize){

           init();

      }

      ~LList(){

           removeall();

      }

      voidclear(){

           removeall();init();

      }

      boolinsert(Elem&,int i);

      boolappend(Elem&);

      boolremove(Elem&);

      voidsetStart(){

           fence = head;

           rightcnt +=leftcnt;

           leftcnt = 0;

      }

      voidsetEnd(){

           fence = tail;

           leftcnt += rightcnt;

           rightcnt = 0;

      }

      voidprev();//前驱

      voidnext(){//后继

           if(fence!=tail){

                 fence =fence ->next;rightcnt--;leftcnt++;

           }

      }

      intleftLength() const{return leftcnt;}

      intrightLength() const{return rightcnt;}

      boolsetPos(int pos);

      boolgetValue(Elem& it) const{

           if(rightLength()==0)returnfalse;

           it = fence->next->element;

           returntrue;

      }

      voidprint() const;

    voidreverlist();//逆置

};

template<classElem>

boolLList<Elem>::insert(Elem& item, inti){//插入操作

      if (i<1||i>size){

           returnfalse;

      }

      else{

           int n = 0;

           Link<Elem>*  temp = head;

           while(n<i-1){

                 temp = temp->next;

                 n++;

           }

           temp->next = newLink<Elem>(item, temp->next);

           size++;

           returntrue;

      }

 

}

template<classElem>

boolLList<Elem>::append(Elem& item){//添加在末端

      tail = tail ->next = newLink<Elem>(item,NULL);

      rightcnt++;

      size++;

      returntrue;

}

template<classElem>

boolLList<Elem>::remove(Elem& it){//删除某元素

      bool del = false;

      Link<Elem>*  temp = head;

      while(temp->next!=NULL){

           if (temp->next->element == it){

                 temp->next = temp->next->next;

                 del = true;

                 leftcnt--;

                 size--;

           }

           else{

                 temp = temp->next;

           }

 

      }

      return del;

}

template<classElem>

voidLList<Elem>::prev(){

      Link<Elem>*  temp = head;

      if(fence == head) return;

      while (temp->next!=fence) temp = temp->next;

      fence = temp;

      leftcnt--; rightcnt++;

}

template<classElem> boolLList<Elem>::setPos(intpos){

      if((pos<0)||(pos>rightcnt+leftcnt)) returnfalse;

      fence = head;

      for(int i=0;i<pos;i++){

           fence = fence->next;

      }

      returntrue;

}

template<classElem>

voidLList<Elem>::print() const{

      Link<Elem>* temp = head;

      cout<<"<";

      while (temp!=fence)

      {

           cout<<temp->next->element<<" ";

           temp = temp->next;

      }

      cout<<" | ";

      while (temp->next!=NULL){

           cout <<temp->next->element <<"  ";

           temp = temp->next;

      }

      cout<<" >\n ";

}

template <class  Elem>

voidLList<Elem>::reverlist()

{

Link<Elem>* p,*q;

p=head->next;

head->next=NULL;//链式线性表分为两部分

while(p!=NULL){

q=p;

p=p->next;

q->next=head->next;

head->next=q;

}

}

#endif

 

0
0
分享到:
评论

相关推荐

    调度算法中的经典-LRU算法的实现(绝对值得收藏)

    一个常见的方法是使用链表,每个节点代表一个页面,链表的顺序表示页面的访问顺序。每当有新的页面被访问,如果已经在链表中,则移动到链表头部;如果不在链表中,添加到链表头部,同时保持链表长度不超过设定的最大...

    力扣刷题总结c++ 解题报告(持续更新中)(csdn)————程序.pdf

    这些题目展示了C++在解决算法问题时的灵活性和效率,涉及了数据结构(如数组、链表、哈希表、栈和队列)、基本操作(如字符串处理、整数转换、位运算)以及多种算法思想(如暴力求解、动态规划、双指针、滑动窗口、...

    深入浅出,C++新手绝对教科书,PPT,WORD

    C++课程安排目录 第一课内容:整个网络游戏课程的概述,熟悉VS.2005.net编译器,并理解简单的程序。...第十六课内容:链表和链表的基本操作 第十七课内容:栈与对列 第十八课内容:树的结构 第十九课内容:模板机制

    c++笔记,自己对比赛的知识点总结

    C++笔记总结 本资源摘要信息涵盖了C++语言的基础知识点,包括环境配置、语言结构、数据类型、变量、常量、修饰符、存储类、运算符、循环、判断、函数、数组、字符串...动态内存可以用来实现动态数组和链表等数据结构。

    数据结构课件(绝对经典)

    它可以抽象为顺序表(数组实现)或链表(链式存储)。顺序表的优点是访问速度快,但插入和删除操作可能涉及大量元素的移动;链表则在插入和删除时更为灵活,但访问速度较慢。 2. **数组与广义表**(第五章):数组...

    数据结构源代码绝对详尽!

    查找算法如顺序查找、二分查找和哈希查找分别对应线性、对数和常数时间复杂度。 通过学习和分析这些源代码,不仅可以提升编程技能,还能深入理解数据结构的内在逻辑,为解决实际问题打下坚实基础。无论是初学者还是...

    2021年软件开发应知应会-84分之欧阳学文创编.docx

    1. **数据结构**:研究数据结构实际上涵盖了数据的逻辑结构(如数组、链表、树、图等)、存储结构(如顺序存储、链式存储、索引存储等)以及在这些结构上的运算实现。数据结构的选择直接影响到算法的效率和程序的...

    编程新手真言绝对实用

    1. **C与C++是两种不同的语言**:尽管两者之间存在联系,但它们的设计理念和使用场景有很大区别。 2. **C的数组、指针、字符串**:C语言中的数组、指针和字符串是其基础数据类型,了解它们的用法对于编写高效的C...

    软件开发应知应会-84分.pdf

    4. **线性表**:线性表是基本的数据结构,包括数组、单链表、双链表和循环链表等形式,它们可以实现顺序存取或动态增删元素。 5. **哈希函数**:哈希函数用于将任意大小的输入转换为固定大小的输出,常用于哈希表的...

    反调试源代码,10多种方式

    9. **代码混淆**:通过随机化指令顺序、使用自定义编码或混淆技术,使得逆向工程变得更加困难,间接实现反调试。 10. **动态库注入检测**:调试器可能通过注入DLL来监视程序。程序可以检查所有已加载模块,寻找非...

    CacheTalk

    在C++中,可以使用双向链表和哈希表来实现LRU缓存,链表用于维护数据的顺序,哈希表用于快速查找。 2. **LFU (Least Frequently Used) 算法**:另一种常见的策略是LFU,它淘汰最不常使用的数据。LFU需要记录每个项...

    程序员面试宝典

    而对于C++,推荐使用`inline`关键字来实现。 #### 18. 直接链接两个信令点的一组链路 - PPP(Point-to-Point Protocol,点对点协议)用于直接链接两个信令点的一组链路。 以上是对给定文档中的知识点进行了详细的...

    嵌入式软件工程师笔试题华为 (2).pdf

    19. **跳转到绝对地址执行**:在特定的硬件平台上,可以使用跳转指令如`jmp`或`call`配合绝对地址来实现。但在现代操作系统中,这样做通常是不允许的,需要通过系统调用来切换执行上下文。 这些知识点是嵌入式软件...

    2021-2022计算机二级等级考试试题及答案No.17572.docx

    9. 链表:链表允许动态地添加和删除元素,不需要移动元素,这使得插入和删除操作比顺序存储结构更高效,但随机访问不如顺序存储快。 10. C语言标识符:标识符可以由字母、数字和下划线组成,且不能以数字开头。选项...

    《链接器和加载器》(中文版)

    ### 《链接器和加载器》(中文版)—— 关键知识点详解 #### 第1章 链接和加载 **链接器和加载器的作用**: - **链接器**负责将多个目标文件(通常是由编译器产生的)链接成一个可执行文件或库。 - **加载器**则是在...

    你必须知道的495个C语言问题

    8. **控制结构体域的对齐**:大多数编译器提供了`#pragma pack`指令来控制结构体域的对齐,从而优化内存使用和性能。 9. **结构体成员的字节偏移**:通过`offsetof`宏可以获取结构体成员相对于结构体起点的偏移量,...

    经典的问题

    - 类初始化顺序涉及静态块、静态字段、非静态块、非静态字段和构造函数的执行顺序。 **15. 普通代码块、静态代码块、构造代码块区别** - **静态代码块**: 在类加载时只执行一次。 - **构造代码块**: 在每次创建...

Global site tag (gtag.js) - Google Analytics