链表:双链表

单链表相比于顺序表来说

能够随意插入删除元素这一点确实很方便

但是遇到需要查询一个结点的前一个结点的时候

单链表就不是很能应付这种情况了

所以双链表就出现了


相比于单链表来说,双链表之所以能双向是因为多了一个指针

就像上一节讲的那样,双链表有两个指针域

一个用作前驱,一个用作后继

两个节点间前驱和后继相互连接


所以定义的方式就变成了下面这样

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

在下面的代码里可以和类进行结合

大部分的计算和单链表是一致的,你甚至不需要修改

#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 = NULL;
    cout<<"创建成功"<<endl;
}//创建双链表 

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

void List::OutputLength(){
    int length = 0;
    Dnode *p;
    p = head;
    
    while(p->next != NULL){
        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的海滩

发表评论

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