c++双链表以及循环双链表的实现以及操作

ゞ浴缸里的玫瑰 2022-03-19 08:24 197阅读 0赞

**双链表:**

#include<stdlib.h>
    #include<stdio.h>
     
    typedef struct node{
    int data;
    node* next;
    node* prior;
    }Node,*PNode;
     
    int getlen(PNode pn){
    	int i=0;
    	PNode p=pn->next;
    	while(p!=NULL){
    	i++;
    	p=p->next;
    	}
    	return i;
    }
     
    int insert(PNode p,int i,int x){
    	int j=1;
    	if(i<1||i>getlen(p)+1){
    	return 0;
    	}
    	while(j<i){
    		p=p->next;
    		j++;
    	}
    	PNode pnew=(PNode)malloc(sizeof(Node));
    	pnew->data=x;
    	pnew->next=p->next;
    	pnew->prior=p;
    	if(pnew->next!=NULL){
    		pnew->next->prior=pnew;
    	}
    	p->next=pnew;
    	return 1;
    }
     
    int deleteNode(PNode p,int i){
    	int j=1;
    	if(i<1||i>getlen(p)){
    	return 0;
    	}
    	while(j<i){
    		p=p->next;
    		j++;
    	}
    	PNode pt=p->next;
    	p->next=pt->next;
    	if(pt->next!=NULL){
    		pt->next->prior=p;
    	}
    	free(pt);
    	return 1;
    }
     
    void list(PNode List){
    	PNode P = List->next;  
        while (P != NULL)     
        {
    		printf("%d ", P->data);
            P = P->next;
        }
        printf("\n");
    }
     
    void init(PNode &p){//为了返回改变的值，使用引用型参数
    	p=(PNode)malloc(sizeof(Node));
    	p->next=NULL;
    	p->prior=NULL;
    }
    void diplist(PNode list){
    	PNode p=list->next;
    	while(p!=NULL){
    		printf("%d ",p->data);
    		p=p->next;
    	}
    	printf("\n");
    }
     
    PNode getelem(PNode p,int i){
    	int j=0;
    	if(i<1||i>getlen(p)){
    		return NULL;
    	}
    	while(j<i){
    		p=p->next;
    		j++;
    	}
    	return p;//返回第i个节点的指针
    }
     
    PNode locate(PNode sp,int x){
    	PNode p=sp->next;
    	while(p!=NULL&&p->data!=x){
    		p=p->next;
    	}
    	return p;
    }
    void main(){
    	PNode p;
    	init(p);
    	for(int i=1;i<=10;i++){
    	insert(p,i,i);
    	}
    	diplist(p);
    	deleteNode(p,5);
    	diplist(p);
    	PNode pr=getelem(p,5);
    	printf("%d\n",pr->data);
    	PNode pl=locate(p,8);
    	printf("%d\n",pl->next->data);
    	system("pause");
    }

**循环双链表:**

#include<stdlib.h>
    #include<stdio.h>
     
    typedef struct node{
    int data;
    node* next;
    node* prior;
    }Node,*PNode;
     
    int getlen(PNode pn){
    	int i=0;
    	PNode p=pn->next;
    	while(p!=pn){
    	i++;
    	p=p->next;
    	}
    	return i;
    }
     
    int insert(PNode p,int i,int x){
    	int j=1;
    	if(i<1||i>getlen(p)+1){
    	return 0;
    	}
    	while(j<i){
    		p=p->next;
    		j++;
    	}
    	PNode pnew=(PNode)malloc(sizeof(Node));
    	pnew->data=x;
    	pnew->next=p->next;
    	pnew->prior=p;
    		pnew->next->prior=pnew;
    	
    	p->next=pnew;
    	return 1;
    }
     
    int deleteNode(PNode p,int i){
    	int j=1;
    	if(i<1||i>getlen(p)){
    	return 0;
    	}
    	while(j<i){
    		p=p->next;
    		j++;
    	}
    	PNode pt=p->next;
    	p->next=pt->next;
    		pt->next->prior=p;
    	free(pt);
    	return 1;
    }
     
    void list(PNode List){
    	PNode P = List->next;  
        while (P != List)     
        {
    		printf("%d ", P->data);
            P = P->next;
        }
        printf("\n");
    }
     
    void init(PNode &p){//为了返回改变的值，使用引用型参数
    	p=(PNode)malloc(sizeof(Node));
    	p->next=p;
    	p->prior=p;
    }
    void diplist(PNode list){
    	PNode p=list->next;
    	while(p!=list){
    		printf("%d ",p->data);
    		p=p->next;
    	}
    	printf("\n");
    }
     
    PNode getelem(PNode p,int i){
    	int j=0;
    	if(i<1||i>getlen(p)){
    		return NULL;
    	}
    	while(j<i){
    		p=p->next;
    		j++;
    	}
    	return p;//返回第i个节点的指针
    }
     
    PNode locate(PNode sp,int x){
    	PNode p=sp->next;
    	while(p!=sp&&p->data!=x){
    		p=p->next;
    	}
    	return p;
    }
    void main(){
    	PNode p;
    	init(p);
    	for(int i=1;i<=10;i++){
    	insert(p,i,i);
    	}
    	diplist(p);
    	deleteNode(p,5);
    	diplist(p);
    	PNode pr=getelem(p,5);
    	printf("%d\n",pr->data);
    	PNode pl=locate(p,8);
    	printf("%d\n",pl->next->data);
    	system("pause");
    }

**1.把p！=null改为p！=自身**

**2.由于循环，所以在delete和insert不用判断是否有下一个元素**