C++数据结构--单向循环链表（实现头插法，尾插法）

迈不过友情╰ 2021-12-05 16:41 399阅读 0赞

**单向循环链表核心代码图解：  
  
  
\*插入到非空链表的表尾  
![Center][]  
  
  
\*删除非空链表元素  
![Center 1][]  
  
  
  
  
  
  
  
实现代码：并未包括异常类处理  
  
template<typename T>  
class sinCirLink  
\{  
private:  
class node //节点类型   
\{   
public:  
  
node():val(T()),next(nullptr)\{\}  
node(T v):val(v),next(nullptr)\{\}  
node(T v,node\* pt):val(v),next(pt)\{\}  
T val; //存储数据   
node \*next; //保存下一节点的指针   
\};  
node \*front; //保存表头指针   
node \*back; //保存表尾指针  
  
void findPointer(node \*&p,int pos) //在链表寻找pos位置的指针的工具函数,pos从0开始   
\{   
node\* tem=front->next; //指向链表的第一个节点   
for(int i=0;i<pos;i++)  
\{   
tem=tem->next;   
\}  
p=tem;  
\}   
public:  
sinCirLink() //构建只有一个头节点的空链表  
\{   
front=back=new node;  
back->next=front;  
front->next=back;   
\}   
  
void push\_back(T val) //尾插法   
\{   
if(front==back) //处理空链表的情况   
\{   
node \*tem=new node(val,front); //令新节点的next指向头节点   
  
front->next=tem;//更新头指针的next  
back=tem; //更新尾指针   
  
\}  
else //处理非空链表的情况   
\{   
node \*tem=new node(val,front);  
back->next=tem;  
back=tem; //更新尾指针   
  
\}  
  
\}  
  
void push\_front(T val)  
\{   
if(front==back) //处理空链表的情况   
\{   
node \*tem=new node(val,front); //令新节点的next指向头节点   
front->next=tem;//更新头指针的next  
back=tem; //更新尾指针   
  
\}  
else //处理非空链表的情况   
\{   
node \*tem=new node(val,front->next);//令新节点的next指向指向的节点   
front->next=tem; //更新front的next节点   
  
\}  
\}   
  
void insert(int pos,T val) //在pos位置(下标从0开始）插入val   
\{   
node\* des=new node(val);  
node\* pre; //插入目标的前一节点   
if(pos==0)  
\{   
push\_front(val);  
\}  
else  
\{   
findPointer(pre,pos-1);  
des->next=pre->next;  
pre->next=des;  
  
\}  
  
  
\}   
  
void erase(int pos) //在pos位置(下标从0开始）删除节点  
\{   
  
  
if(pos==0)  
\{   
 node\* tem=front->next;  
 front->next=tem->next;  
 delete tem;  
\}  
else  
\{   
node\* pre;  
node\* tem;  
findPointer(pre,pos-1) ;  
tem=pre->next;  
pre->next=tem->next;  
delete tem;  
  
\}  
  
\}  
  
void toString() //打印循环链表   
\{   
node\* tem=front->next;  
while(tem!=front)   
\{   
cout<<tem->val<<ends;  
tem=tem->next;  
\}  
\}   
  
  
\};  
  
  
  
  
int main()  
\{   
sinCirLink<int> scl;  
scl.push\_back(3);  
scl.push\_back(4);  
scl.push\_front(2);  
scl.insert(0,1);  
scl.insert(4,5);  
scl.toString(); //1 2 3 4 5  
cout<<endl;  
scl.erase(1);  
scl.erase(3);  
scl.erase(0);  
scl.toString();// 3 4  
return 0;  
\}**

[Center]: /images/20211205/e07569f88c21436bb3207b6044bd09b1.png
[Center 1]: /images/20211205/b29b50cb05c5466dace7e7b800ae8b79.png