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

超、凢脫俗 2022-03-19 07:52 264阅读 0赞

**单链表:**

#include<stdlib.h>
    #include<stdio.h>
    
    typedef struct node{
    int data;
    node* next;
    }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;
    	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;
    	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;
    }
    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 p,int x){
    	p=p->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,*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;
    	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;
    	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;
    }
    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.init,头结点的next域不为空，而是指向自身。**

**2.getlen,p！=null改为p！=sq**

**3.locate，p！=null改为p！=sq**

**4.insert和delete没有改动**

**5.list把p！=null改为p！=sq**

**总之判断条件从null改为到自身。**