链表:循环链表

这一节几乎不需要用什么讲解

循环单链表可以简单的理解为头尾相接

也就是说尾结点的next指针指向头节点

同时判断是否是尾结点的条件就变成了next指针是否指向的是头节点

代码基本照搬上两节

#include<iostream>

typedef char Elemtype;
using namespace std;

struct Node{
    Elemtype data;
    Node *next;
};//单链表里的最小结点

class List{
    public:
        List();
        void CreateList(Elemtype a[],int n);
        void OutputElem();
        void OutputLength();
        void Ifempty();
        void OutLocateElem(int n);
        void OutElemLocate(Elemtype e);
        void InsertInLocate(int n,Elemtype e);
        void DeleteInLocate(int n);
        void DestroyList();

    private:	
        Node *head;
    
};

List::List(){
    head = NULL;
}//初始化单链表 

void List::CreateList(Elemtype a[],int n){
    Node *p,*q;
    head = new Node;
    q = head;

    for(int i=0;i<n;i++){
        p = new Node;
        p->data = a[i];
        q->next = p;
        q = p;
    } 
    q->next = head;
    cout<<"创建成功"<<endl;
}//创建单链表 

void List::OutputElem(){
    Node *current = head->next;
    
    cout<<"该循环单链表含有元素";
    while(current != head){
        cout<<current->data<<" ";
        current = current->next;
    }
    cout<<endl;
}//输出元素 

void List::OutputLength(){
    int length = 0;
    Node *p;
    p = head;
    
    while(p->next != head){
        length++;
        p = p->next;
    }
    
    cout<<"单链表的长度为"<<length<<endl;
}//输出单链表的长度 

void List::Ifempty(){
    if(head == NULL){
        cout<<"是空表"<<endl;
    }else{
        cout<<"不是空表"<<endl;
    }
    
}//判断是否为空 

void List::OutLocateElem(int n){
    int i=0;
    Node *p = head;
    while(i<n && p!=NULL){
        i++;
        p = p->next;
    }
    if(p == NULL){
        cout<<"不存在"<<endl;
    }else{
        cout<<"第"<<n<<"个元素的值"<<p->data<<endl;
    }
}//输出指定位置的元素 

void List::OutElemLocate(Elemtype e){
    int i=1;
    Node *p = head->next;
    
    while(p!=NULL && p->data != e){
        p = p->next;
        i++;
    }
    
    if(p != NULL){
        cout<<e<<"的位置为"<<i<<endl;
    }else{
        cout<<"未找到该元素"<<endl;
    }
}//输出元素的位置

void List::InsertInLocate(int n,Elemtype e){
    int i=0;
    Node *p = head;
    Node *q;
    while(i<n-1 && p!=NULL){
        i++;
        p=p->next;
    }
    if(p!=NULL){
        q = new Node;
        q->data = e;
        q->next = p->next;
        p->next = q;
        cout<<"插入成功"<<endl;
    }else{
        cout<<"找不到可插入的结点"<<endl;
    }
}//在指定位置插入元素

void List::DeleteInLocate(int n){
    int i=0;
    Node *p = head;
    Node *q;
    while(i<n-1 && p!=NULL){
        i++;
        p = p->next;
    }
    if(p!=NULL){
        q = p->next;
        if(q != NULL){
            p->next = q->next;
            delete q;
            cout<<"删除了第"<<n<<"个元素"<<endl; 
        }
    }else{
        cout<<"该位置没有元素"<<endl;
    }
    
}//删除指定位置的元素

void List::DestroyList(){
    
}//销毁线性表

int main(){
    
    Elemtype a[5]={'a','b','c','d','e'};
    
    List h;
    h.CreateList(a,5);
    h.OutputElem();
    h.OutputLength();
    h.Ifempty();
    h.OutLocateElem(3);
    h.OutElemLocate('a');
    h.InsertInLocate(4,'f');
    h.OutputElem();
    h.DeleteInLocate(3);
    h.OutputElem();
    
    return 0;
}

循环双链表稍微复杂一点

尾结点的后继指针同样指向头节点

同时头节点的前驱指针指向尾结点

判断尾结点的条件同样变为是否后继指针指向了头节点

#include<iostream>

typedef char Elemtype;
using namespace std;

struct Dnode{
    Elemtype data;
    Dnode *prior;
    Dnode *next;
};

class List{
    public:
        List();
        void CreateList(Elemtype a[],int n);
        void OutputElem();
        void OutputLength();
        void Ifempty();
        void OutLocateElem(int n);
        void OutElemLocate(Elemtype e);
        void InsertInLocate(int n,Elemtype e);
        void DeleteInLocate(int n);
        void DestroyList();

    private:	
        Dnode *head;
};

List::List(){
    head = NULL;
}//初始化双链表

void List::CreateList(Elemtype a[],int n){
    Dnode *p,*q;
    head = new Dnode;
    q = head;
    for(int i=0;i<n;i++){
        p = new Dnode;
        p->data = a[i];
        q->next = p;
        p->prior = q;
        q = p;
    }
    q->next = head;
    head->prior = q;
    cout<<"创建成功"<<endl;
}//创建双链表 

void List::OutputElem(){
    Dnode *current = head->next;
    cout<<"该循环双链表中含有元素"<<endl;
    
    while(current != head){
        cout<<current->data<<" ";
        current = current->next;
    }
    cout<<endl;
}

void List::OutputLength(){
    int length = 0;
    Dnode *p;
    p = head;
    
    while(p->next != head){
        length++;
        p = p->next;
    }
    
    cout<<"单链表的长度为"<<length<<endl;
}//输出单链表的长度 

void List::Ifempty(){
    if(head == NULL){
        cout<<"是空表"<<endl;
    }else{
        cout<<"不是空表"<<endl;
    }
    
}//判断是否为空 

void List::OutLocateElem(int n){
    int i=0;
    Dnode *p = head;
    while(i<n && p!=NULL){
        i++;
        p = p->next;
    }
    if(p == NULL){
        cout<<"不存在"<<endl;
    }else{
        cout<<"第"<<n<<"个元素的值"<<p->data<<endl;
    }
}//输出指定位置的元素 

void List::OutElemLocate(Elemtype e){
    int i=1;
    Dnode *p = head->next;
    
    while(p!=NULL && p->data != e){
        p = p->next;
        i++;
    }
    
    if(p != NULL){
        cout<<"元素的位置为"<<i<<endl;
    }else{
        cout<<"未找到该元素"<<endl;
    }
}//输出元素的位置

void List::InsertInLocate(int n,Elemtype e){
    int i=0;
    Dnode *p = head;
    Dnode *q;
    while(i<n-1 && p!=NULL){
        i++;
        p=p->next;
    }
    if(p!=NULL){
        q = new Dnode;
        q->data = e;
        q->next = p->next;
        if(p->next!=NULL){
            p->next->prior = q;
        }
        q->prior = p;
        p->next = q;
        cout<<"插入成功"<<endl;
    }else{
        cout<<"找不到可插入的结点"<<endl;
    }
}//在指定位置插入元素

void List::DeleteInLocate(int n){
    int i=0;
    Dnode *p = head;
    Dnode *q;
    while(i<n-1 && p!=NULL){
        i++;
        p = p->next;
    }
    if(p!=NULL){
        q = p->next;
        if(q != NULL){
            p->next = q->next;
            if(p->next != NULL){
                p->next->prior = q;
            }
            delete q;
            cout<<"删除了第"<<n<<"个元素"<<endl; 
        }
    }else{
        cout<<"该位置没有元素"<<endl;
    }
    
}//删除指定位置的元素

void List::DestroyList(){
    
}//销毁线性表

int main(){
    
    Elemtype a[5]={'a','b','c','d','e'};
    
    List h;
    h.CreateList(a,5);	
    h.OutputElem();
    h.OutputLength();
    h.Ifempty();
    h.OutLocateElem(3);
    h.OutElemLocate('a');
    h.InsertInLocate(4,'f');
    h.OutputElem();
    h.DeleteInLocate(3);
    h.OutputElem();
    
    return 0;
}

《链表:循环链表》有1个想法

  1. Pingback: 数据结构第五版——第二章课后实验题 – 海星peter的海滩

发表评论

您的电子邮箱地址不会被公开。