双链表的实现 - c++编程基础

跟单链表有点像，主要区别就在建表，插入元素，删除元素这里。

双链表数据结构为:

typedef struct  DNode{
	ElemType data;        //节点数据 
	struct DNode* prior;   //指向前一节点指针 
	struct DNode* next;    //指向后一节点指针 
}DLinkList;

实现下列函数:

void CreateListF(DLinkList *&L,ElemType a[],int n);  //头插法建表
void CreateListR(DLinkList *&L,ElemType a[],int n); //尾插法建表
void InitList(DLinkList *&L);  //初始化链表
void DestroyList(DLinkList *&L);  //销毁链表
int ListEmpty(DLinkList *L);  //判断链表是否为空
int ListLength(DLinkList *L);  //求链表长度
void DispList(DLinkList *L);  //输出链表
int GetElem(DLinkList *L,int i,ElemType &e);  //求链表里第i个节点的值，并赋值给e 
int LocateElem(DLinkList *L,ElemType e); //求与e值相等的第一个元素的序号 
int InsertElem(DLinkList *&L,int i,ElemType e); //插入元素
int DeleteElem(DLinkList *&L,int i,ElemType &e); //删除元素

具体实现代码:

#include
  
   
#include
   
     #include
    
      #define ElemType float #define GET_ARRAY_LEN(array) (sizeof(array)/sizeof(array[0])) using namespace std; typedef struct DNode{ ElemType data; //节点数据 struct DNode* prior; //指向前一节点指针 struct DNode* next; //指向后一节点指针 }DLinkList; void CreateListF(DLinkList *&L,ElemType a[],int n); //头插法建表 void CreateListR(DLinkList *&L,ElemType a[],int n); //尾插法建表 void InitList(DLinkList *&L); //初始化链表 void DestroyList(DLinkList *&L); //销毁链表 int ListEmpty(DLinkList *L); //判断链表是否为空 int ListLength(DLinkList *L); //求链表长度 void DispList(DLinkList *L); //输出链表 int GetElem(DLinkList *L,int i,ElemType &e); //求链表里第i个节点的值，并赋值给e int LocateElem(DLinkList *L,ElemType e); //求与e值相等的第一个元素的序号 int InsertElem(DLinkList *&L,int i,ElemType e); //插入元素 int DeleteElem(DLinkList *&L,int i,ElemType &e); //删除元素 void CreateListF(DLinkList* &L,ElemType a[],int n){ L=(DLinkList *)malloc(sizeof(DLinkList)); L->prior=L->next=NULL; DLinkList *p=L; for(int i=0;i
     
      data=a[i]; if(p->next!=NULL){ addNumber->prior=p->next->prior; addNumber->next=p->next; p->next->prior=addNumber; p->next=addNumber; } else { addNumber->prior=p; addNumber->next=NULL; p->next=addNumber; } } } void CreateListR(DLinkList* &L,ElemType a[],int n){ L=(DLinkList *)malloc(sizeof(DLinkList)); L->prior=L->next=NULL; DLinkList *p=L; for(int i=0;i
      
       data=a[i]; addNumber->prior=p; addNumber->next=NULL; p->next=addNumber; p=p->next; } } void InitList(DLinkList* &L){ L=(DLinkList *)malloc(sizeof(DLinkList)); L->prior=L->next=NULL; } void DestroyList(DLinkList* &L){ DLinkList* p=L; DLinkList* q=L->next; while(q!=NULL){ free(p); p=q; q=q->next; } free(p); } int ListEmpty(DLinkList* L){ return(L->next==NULL); } int ListLength(DLinkList* L){ int count=0; DLinkList* p=L->next; while(p!=NULL){ count++; p=p->next; } return count; } void DispList(DLinkList* L){ DLinkList* p=L->next; while(p!=NULL){ cout<
       
        data<<" "; p=p->next; } cout<
        
         next; j++; } if(i<1||p==NULL)return -1; else{ e=p->data; return 1; } } int LocateElem(DLinkList* L,ElemType e){ DLinkList* p=L->next; int i=1; while((!(-1e-9
         
          data-e&&p->data-e<1e-9))&&p!=NULL){ p=p->next; i++; } if(p==NULL)return -1; else return i; } int InsertElem(DLinkList* &L,int i,ElemType e){ DLinkList* p=L->next; int j=1; while(j
          
           next; } if((p==NULL&&i>j+1)||i<1)return -1; else{ DLinkList* addNumber=(DLinkList *)malloc(sizeof(DLinkList)); addNumber->data=e; addNumber->prior=p->prior; addNumber->next=p; p->prior->next=addNumber; p->prior=addNumber; return 1; } } int DeleteElem(DLinkList* &L,int i,ElemType &e){ DLinkList* p=L->next; int j=1; while(j
           
            next; } if(i<1||p==NULL)return -1; else{ e=p->data; if(p->next!=NULL){ p->next->prior=p->prior; p->prior->next=p->next; free(p); } else{ p->prior->next=NULL; free(p); } return 1; } } int main(){ DLinkList *L=N

双链表的实现(一)