最近在重新复习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++图书管理管理程序 可以对图书和供应商两个类进行管理和统计 大学作业,可供学生参考
链表的c++实现链表的c++实现链表的c++实现
初级链表和顺序表的创建,销毁,删除,插入
其中包含了两个工程,里面有代码和比较时间的函数。
数据结构链表和顺序表实验源码,没有实验报告,需要下载。
c++链表队列的实现,c++链表队列的实现,c++链表队列的实现,c++链表队列的实现,c++链表队列的实现,c++链表队列的实现
双向循环链表 C++实现 双向循环链表 C++实现 双向循环链表 C++实现 双向循环链表 C++实现 双向循环链表 C++实现
链表类 c++ 实现的 链表类 c++ 实现的 链表类 c++ 实现的
链表 实现 c++ cpp 数据结构 作业 链表 实现 c++ cpp 数据结构 作业
数据结构顺序链表的实现数据结构顺序链表的实现数据结构顺序链表的实现数据结构顺序链表的实现数据结构顺序链表的实现数据结构顺序链表的实现
用链表与顺序表编写学生信息管理系统,用于实践vc++6.0
各种形式的链表C++实现方式 ,以及其对应的代码 1.单向链表链表 2.单向循环链表 3.双向链表 内容非常详细
C++ 链表结构实现随机森林 有解释 参数可设置 完成分类
顺序表和链表
数据结构 栈 链表实现 c++ 是模板实现的
实现的操作:有头链表; 实现的功能:增,删,改,查; 关于资源:我的文章中有部分解释,相关内容还可查看我的文章; 关于问题:有问题及时私信我,例如不能运行,运行失败等问题;
链表的实现 使用c++实现学生系统 链表的实现 使用c++实现学生系统
用链表和文件完成的C++版的学生管理系统,记录一下,希望有用!!!!!