请问各位大佬这个怎么改为双链表

Question

#include"stdafx.h"
#include<stdio.h>
#include <iostream>
using namespace std; 
#define OK 1;
#define ERROR 0;

typedef int Status;
typedef int ElemType;

typedef struct LNode{                //存储结构 
 ElemType data;                        //数据域 
 struct LNode *next;                //指针域 
}LNode,*LinkList;                    /*LinkList是指向LNode结构体的指针类型，可以通过这个指针类型定义LNode这个结构体的表 */ 

Status InitList(LinkList &L);        //初始化
void CreateList_H(LinkList &L,int n);//头插法创建单链表
void CreateList_R(LinkList &L,int n);//后插法创建单链表 
void TraverseList(LinkList L);        //显示单链表 
Status GetElem(LinkList L,int i,ElemType &e);//按位置查找值 
LNode *LocateElem(LinkList L,ElemType);//按值查找地址 
Status ListInsert(LinkList &L,int i,ElemType e);//单个数据插入 
Status ListDelete(LinkList &L,int i);//删除第i个数据 

int main(int argc, char** argv) {
 LinkList L;
 int n,i,op=1;
 ElemType e,value;
 InitList(L);
 cout<<"<1>.前插法创建单链表"<<endl
  <<"<2>.后插法创建单链表"<<endl
  <<"<3>.显示"<<endl
  <<"<4>.按位查询"<<endl
  <<"<5>.按值查询"<<endl
  <<"<6>.插入第i个数据"<<endl 
  <<"<7>.删除第i个数据"<<endl
  <<"<0>.退出"<<endl
  <<"--------------------"<<endl; 
 while(op){
  cout<<"请输入你要进行的操作:\t"; 
  cin>>op;
  if(op>7)cout<<"对不起输入错误！"<<endl;
  switch(op){
   
 case 1://前插法创建单链表 
 cout<<"你想创建单链表的表长为：";
 cin>>n;
 CreateList_H(L,n);
 break;
 
 case 2://后插法创建单链表 
 cout<<"你想创建单链表的表长为：";
 cin>>n;
 CreateList_R(L,n);
 break;
 
 case 3://显示
 if(!L->next){
 cout<<"还未创建单链表，查询失败！"<<endl;
 break;
 }
 TraverseList(L);
 break;
 
 case 4://按位查询 
 if(!L->next){
 cout<<"还未创建单链表，查询失败！"<<endl;
 break;
 }
 cout<<"你想查询的位置i是：";
 cin>>i;
 if(GetElem(L,i,e)) cout<<"该位置的值是:"<<e<<endl;
 else cout<<"查询失败！";
 break;
 
 case 5://按值查询 
 if(!L->next){
 cout<<"还未创建单链表，查询失败！"<<endl;
 break;
 }
 cout<<"你想查询的值value为：";
 cin>>value;
 cout<<"该值的位置是:"<<LocateElem(L,value)<<endl;
 break;
 
 case 6://插入 
 if(!L->next){
 cout<<"还未创建单链表，查询失败！"<<endl;
 break;
 }
 cout<<"你想插入的位置和数字是：";
 cin>>i>>e;
 if(ListInsert(L,i,e))cout<<"插入成功！";
 else cout<<"输入位置不合法！" ;
 break;
 
 case 7://删除
 if(!L->next){
 cout<<"还未创建单链表，查询失败！"<<endl;
 break;
 }
 cout<<"你想删除的位置i是：";
 cin>>i;
 if(ListDelete(L,i))cout<<"删除成功!"<<endl; 
 else cout<<"删除失败，删除位置不合法！"; 
 break;
 
 case 0:
  cout<<"退出单链表！"<<endl; 
  return 0;
 }
 }
 return 0;
}

Status InitList(LinkList &L){
 L=new LNode;
 L->next=NULL;
 return 1;
}

void CreateList_H(LinkList &L,int n){
 
 L=new LNode;
 L->next=NULL;
 for(int i=0;i<n;i++){
  LinkList p;
  p=new LNode;
  cout<<"请输入第"<<n-i<<"个数为:";
  cin>>p->data;
  p->next=L->next;
  L->next=p;
 }
 cout<<"前插法创建成功！"<<endl; 
}

void CreateList_R(LinkList &L,int n){
 L=new LNode;
 L->next=NULL;
 LinkList p,r;
 r=L;
 for(int i=0;i<n;i++){
  p=new LNode;
  cout<<"请输入第"<<i+1<<"个数为:";
  cin>>p->data;
  p->next=NULL;
  r->next=p;
  r=p;
 }
 cout<<"后插法创建成功！"<<endl; 
} 

void TraverseList(LinkList L){
 LinkList p;
 p=L;
 cout<<"显示结果：";
 while(p->next!=NULL){
  p=p->next;
  cout<<p->data<<"  ";
 }
 cout<<endl; 
 
}

Status GetElem(LinkList L,int i,ElemType &e){
 LinkList p;
 p=L; 
 int j;
 for(j=0;j<i&&p;j++)//防止系统停止运行 
  p=p->next;
 if(!p||i<1)return ERROR;
 e=p->data; 
 return OK;
} 

LNode *LocateElem(LinkList L,ElemType e){
 LinkList p=L->next;//初始化指向首元结点
 while(p&&p->data!=e){
  p=p->next;
 } 
 return p;//1.p为NULL 2.p->data==e 
  
} 

Status ListInsert(LinkList &L,int i,ElemType e){
 //带有头结点 在第i个位置插入新结点（计数时不包含头结点）。
 LinkList p,q;
 p=L;
 int j=0;
 
 q=new LNode;
 q->next=NULL;
 q->data=e;
 while(p&&j<i-1)//找第i-1个结点 
 {
  p=p->next;
  j++; 
 } 
 if(!p&&i<1)return ERROR;/*p为空说明未找到第i-1个结点 或者说i-1个结点是n+1 */ 
 q->next=p->next;
 p->next=q;
 return OK;
} 

Status ListDelete(LinkList &L,int i){
 //找到第i-1个结点
 
 LinkList p,q;
 p=L;
 int j=0;
 while(p->next&&j<i-1)//找第i-1个结点 
 {
  p=p->next;
  j++; 
 } 
 if(!p->next||i<1)return ERROR;/*p->next为空则证明第i-1个结点是最后一个结点n 第i个不存在 无法删除 */
 q=p->next;
 p->next=q->next;//用q过渡一下第i-1个和第i+1个
 delete q;//将过渡的这个辅助q删除掉 
 return OK;

} 

Answer 1

要将单链表改为双向链表，需要在原有的单链表结构体LNode中增加一个指向前驱节点的指针prev，然后在相关操作中进行相应的修改。

修改后的LNode结构体定义如下：

typedef struct LNode{
    ElemType data;         //数据域 
    struct LNode *next;    //指向后继节点的指针
    struct LNode *prev;    //指向前驱节点的指针
}LNode,*LinkList;

接下来需要对相关操作进行修改：

1. 初始化操作不需要修改，仍然是创建一个头节点，并将其next和prev指针都指向NULL。

2. 在前插法创建双向链表时，需要保证新插入的节点的prev指针指向其前面的节点，而不是头节点。修改如下：

void CreateList_H(LinkList &L, int n) {
    L = new LNode;
    L->next = NULL;
    L->prev = NULL;
    LinkList p;
    p = L;
    for (int i = 0; i < n; i++) {
        LinkList q;
        q = new LNode;
        cout << "请输入第" << n - i << "个数为:";
        cin >> q->data;
        q->next = p->next;
        if (p->next) {
            p->next->prev = q;  //将新节点的prev指针指向前面的节点
        }
        p->next = q;
        q->prev = p;
    }
    cout << "前插法创建成功！" << endl;
}

1. 后插法创建双向链表的操作同样需要进行修改，保证新插入节点的prev指针指向前面的节点，而不是头节点。修改如下：

void CreateList_R(LinkList &L, int n) {
    L = new LNode;
    L->next = NULL;
    L->prev = NULL;
    LinkList p, q;
    p = L;
    for (int i = 0; i < n; i++) {
        q = new LNode;
        cout << "请输入第" << i + 1 << "个数为:";
        cin >> q->data;
        p->next = q;
        q->prev = p;
        p = q;
    }
    p->next = NULL;
    cout << "后插法创建成功！" << endl;
}

1. 在遍历双向链表时，需要额外遍历prev指针。修改如下：

void TraverseList(LinkList L) {
    LinkList p;
    p = L;
    cout << "正向显示结果：";
    while (p->next != NULL) {
        p = p->next;
        cout << p->data << "  ";
    }
    cout << endl;

    cout << "反向显示结果：";
    while (p != L) {
        cout << p->data << "  ";
        p = p->prev;
    }
    cout << endl;
}

1. 在插入节点和删除节点时，需要修改新节点的prev指针和前一个节点的next指针。修改如下：

Status ListInsert(LinkList& L, int i, ElemType e) {
    //带有头结点 在第i个位置插入新结点（计数时不包含头结点）。
    LinkList p, q;
    p = L;
    int j = 0;

    q = new LNode;
    q->next = NULL;
    q->data = e;
    while (p && j < i - 1)//找第i-1个结点 
    {
        p = p->next;
        j++;
    }
    if (!p && i < 1) return ERROR;/*p为空说明未找到第i-1个结点 或者说i-1个结点是n+1 */
    q->next = p->next;
    if (p->next) {
        p->next->prev = q;  //将新节点的prev指针指向前面的节点
    }
    p->next = q;
    q->prev = p;
    return OK;
}

Status ListDelete(LinkList& L, int i) {
    //找到第i-1个结点

    LinkList p, q，r;
    p = L;
    int j = 0;
    while (p->next && j < i - 1) {
        p = p->next;
        j++;
    }
    if (!(p->next) || j > i - 1) return ERROR; //删除位置不合理
    q = p->next;
    r = q->next;
    p->next = r;
    if (r) {
        r->prev = p;  //将前一个节点的next指针指向后面的节点
    }
    delete q;
    return OK;
}

这样就可以将单链表改为双向链表了。需要注意的是，双向链表相比单链表需要额外的空间存储前驱节点的指针，因此会占用更多的内存。同时，由于双向链表支持双向遍历，因此在一些场景下可以提高效率，但在其他场景下可能会带来额外的开销。需要根据具体的应用场景进行选择。