最近在重新复习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
相关推荐
一个常见的方法是使用链表,每个节点代表一个页面,链表的顺序表示页面的访问顺序。每当有新的页面被访问,如果已经在链表中,则移动到链表头部;如果不在链表中,添加到链表头部,同时保持链表长度不超过设定的最大...
这些题目展示了C++在解决算法问题时的灵活性和效率,涉及了数据结构(如数组、链表、哈希表、栈和队列)、基本操作(如字符串处理、整数转换、位运算)以及多种算法思想(如暴力求解、动态规划、双指针、滑动窗口、...
C++课程安排目录 第一课内容:整个网络游戏课程的概述,熟悉VS.2005.net编译器,并理解简单的程序。...第十六课内容:链表和链表的基本操作 第十七课内容:栈与对列 第十八课内容:树的结构 第十九课内容:模板机制
C++笔记总结 本资源摘要信息涵盖了C++语言的基础知识点,包括环境配置、语言结构、数据类型、变量、常量、修饰符、存储类、运算符、循环、判断、函数、数组、字符串...动态内存可以用来实现动态数组和链表等数据结构。
它可以抽象为顺序表(数组实现)或链表(链式存储)。顺序表的优点是访问速度快,但插入和删除操作可能涉及大量元素的移动;链表则在插入和删除时更为灵活,但访问速度较慢。 2. **数组与广义表**(第五章):数组...
查找算法如顺序查找、二分查找和哈希查找分别对应线性、对数和常数时间复杂度。 通过学习和分析这些源代码,不仅可以提升编程技能,还能深入理解数据结构的内在逻辑,为解决实际问题打下坚实基础。无论是初学者还是...
1. **数据结构**:研究数据结构实际上涵盖了数据的逻辑结构(如数组、链表、树、图等)、存储结构(如顺序存储、链式存储、索引存储等)以及在这些结构上的运算实现。数据结构的选择直接影响到算法的效率和程序的...
1. **C与C++是两种不同的语言**:尽管两者之间存在联系,但它们的设计理念和使用场景有很大区别。 2. **C的数组、指针、字符串**:C语言中的数组、指针和字符串是其基础数据类型,了解它们的用法对于编写高效的C...
4. **线性表**:线性表是基本的数据结构,包括数组、单链表、双链表和循环链表等形式,它们可以实现顺序存取或动态增删元素。 5. **哈希函数**:哈希函数用于将任意大小的输入转换为固定大小的输出,常用于哈希表的...
9. **代码混淆**:通过随机化指令顺序、使用自定义编码或混淆技术,使得逆向工程变得更加困难,间接实现反调试。 10. **动态库注入检测**:调试器可能通过注入DLL来监视程序。程序可以检查所有已加载模块,寻找非...
在C++中,可以使用双向链表和哈希表来实现LRU缓存,链表用于维护数据的顺序,哈希表用于快速查找。 2. **LFU (Least Frequently Used) 算法**:另一种常见的策略是LFU,它淘汰最不常使用的数据。LFU需要记录每个项...
而对于C++,推荐使用`inline`关键字来实现。 #### 18. 直接链接两个信令点的一组链路 - PPP(Point-to-Point Protocol,点对点协议)用于直接链接两个信令点的一组链路。 以上是对给定文档中的知识点进行了详细的...
19. **跳转到绝对地址执行**:在特定的硬件平台上,可以使用跳转指令如`jmp`或`call`配合绝对地址来实现。但在现代操作系统中,这样做通常是不允许的,需要通过系统调用来切换执行上下文。 这些知识点是嵌入式软件...
9. 链表:链表允许动态地添加和删除元素,不需要移动元素,这使得插入和删除操作比顺序存储结构更高效,但随机访问不如顺序存储快。 10. C语言标识符:标识符可以由字母、数字和下划线组成,且不能以数字开头。选项...
### 《链接器和加载器》(中文版)—— 关键知识点详解 #### 第1章 链接和加载 **链接器和加载器的作用**: - **链接器**负责将多个目标文件(通常是由编译器产生的)链接成一个可执行文件或库。 - **加载器**则是在...
8. **控制结构体域的对齐**:大多数编译器提供了`#pragma pack`指令来控制结构体域的对齐,从而优化内存使用和性能。 9. **结构体成员的字节偏移**:通过`offsetof`宏可以获取结构体成员相对于结构体起点的偏移量,...
- 类初始化顺序涉及静态块、静态字段、非静态块、非静态字段和构造函数的执行顺序。 **15. 普通代码块、静态代码块、构造代码块区别** - **静态代码块**: 在类加载时只执行一次。 - **构造代码块**: 在每次创建...