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 leftcnt; //栅栏结点左边结点的数目
int rightcnt; //栅栏结点右边结点的数目
void init(){
fence = tail = head = new Link<Elem>;
leftcnt = rightcnt = 0;
}
void removeall(){
while (head != NULL){
fence = head;
head = head->next;
delete fence;
}
}
public:
LList(int size = 0){ init(); }
~LList(){ removeall(); }
void clear(){ removeall(); init(); }
bool insert(const Elem&);
bool append(const Elem&);
bool remove(Elem&);
void setStart(){
fence = head;
rightcnt += leftcnt;
leftcnt = 0;
}
void setEnd(){
fence = tail;
leftcnt += rightcnt;
rightcnt = 0;
}
void prev();
void next(){
if (fence!=tail){
fence = fence->next;
rightcnt--;
leftcnt++;
}
}
int leftLength()const{return leftcnt;}
int rightLength()const{return rightcnt;}
bool setPos(int pos);
bool getValue(Elem& it)const{
if(rightLength()==0)return false;
it = fence->next->element;
return true;
}
void print()const;
bool turn(); //单链表逆序,反转
Link<Elem> quickloc();//快速定位到中间位置
void getBackN(int N){//寻找单链表倒数第N个数
this->setStart();
while(rightcnt!=N-1){
fence=fence->next;
rightcnt--;
leftcnt++;
}
cout<<fence->element;
}
};
template<class Elem>
bool LList<Elem>::insert(const Elem& item){//在栅栏结点后插入结点
fence->next = new Link<Elem>(item, fence->next);
if(tail == fence) tail = fence->next;
rightcnt++;
return true;
}
template<class Elem>
bool LList<Elem>::turn(){//链表就地逆转
Link<Elem> *current=head->next,*p;
if (head == NULL) {
return false;
}
while (current->next != NULL){
p = current->next;
current->next = p->next;
p->next = head->next;
head->next = p;
}
return true;
}
template<class Elem>
bool LList<Elem>::append(const Elem& item){//在尾节点后增加结点
tail = tail->next = new Link<Elem>(item,NULL);
rightcnt++;
return true;
}
template<class Elem>
bool LList<Elem>::remove(Elem& it){
if(fence->next == NULL)return false;
it = fence->next->element;
Link<Elem>* ltemp = fence->next;
fence->next = ltemp->next;
if(tail == ltemp) tail =fence;
delete ltemp;
rightcnt--;
return true;
}
template<class Elem>
void LList<Elem>::prev(){//访问前结点
Link<Elem>* temp= head;
if(fence == head)return ;
while(temp->next!=fence)temp=temp->next;
fence=temp;
leftcnt--;
rightcnt++;
}
template<class Elem>
bool LList<Elem>::setPos(int pos){//把栅栏设在pos处
if((pos>0)||(pos>rightcnt+leftcnt))return false;
fence = head;
for(int i=0;i<pos;i++)fence = fence->next;
return true;
}
template<class Elem>
void LList<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>
Link<Elem> LList<Elem>::quickloc(){//快速定位
Link<Elem> *search=head,*mid=head;
while(true){
if(search==tail){
cout<<mid->element;
return mid;
}
search=search->next;
mid=mid->next;
if(search==tail){
cout<<mid->element;
return mid;
}
search=search->next;
}
}
分享到:
相关推荐
c++链表队列的实现,c++链表队列的实现,c++链表队列的实现,c++链表队列的实现,c++链表队列的实现,c++链表队列的实现
c++,算法链表实现一元多项式相加,通过链表实现,非常好的一个程序
各种形式的链表C++实现方式 ,以及其对应的代码 1.单向链表链表 2.单向循环链表 3.双向链表 内容非常详细
c++ 链表实现 以及一个很简单的学生管理系统实现增删查学生信息作为例子,怎样运用链表。
C++实现的链表
C++链表基于类实现多项式的加法和乘法; C ++ list class-based polynomial addition and multiplication.
c++链表实现
使用链表来实现多项式的加法,用C++编程
C++链表的具体实现,包含链表的正向和逆向创建,节点的插入与删除,节点的查找
采用c++链表实现电话薄 实现增删改查等功能
用c++实现链表的建立、插入和删除操作。希望能对刚学数据结构的同学有点帮助。
c++链表的实现及链表的合并,自写链表的两个链表的合并函数
链表类 c++ 实现的 链表类 c++ 实现的 链表类 c++ 实现的
用随机数生成密钥,通过循环单链表存储序号及密钥,递归输出出列顺序
C++链表通讯录系统,适合新手学习,可以实现添加,修改,删除,查询,文件保存文件打开功能,拿来学习还不错
链表的c++实现链表的c++实现链表的c++实现
C++链表实现的多项式乘法 需要逐项输入
C++链表的实现,包含链表的创建,删除 ,插入等,有很详细的注释!!
学习尝试,代码不完美,请多包涵
c++ 链表应用 链表类源代码,实现了链表的插入、删除、查找、长度、显示、比较两个链表是否相等、翻转、连个链表的链接、迭代、链表的拷贝、赋值等操作。