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

桃扇骨 2022-05-18 02:41 234阅读 0赞

**创建:**

pNode create(){
    	int len;
    	int value;
     pNode pHead=(pNode)malloc(sizeof(Node));
     pHead->pNext=pHead;
     pHead->pPre=pHead;
     pNode pTail=pHead;
     printf("请输入节点个数:");
     scanf_s("%d",&len);
     for(int i=0;i<len;i++){
      pNode pNew=(pNode)malloc(sizeof(Node));
       printf("第%d个节点的值为:",i+1);
       scanf_s("%d",&value);
      pNew->data=value;
      pNew->pPre=pTail;
      pNew->pNext=pHead;
      pTail->pNext=pNew;
      pHead->pPre=pNew;
      pTail=pNew;
     }
     return pHead;
    }

注意:(1).pHead->pNext=pHead; pHead->pPre=pHead; pNode pTail=pHead;一开始没创建新节点，为空表，头指针前后指向自身，一开始头指针也相当于头指针。

**遍历:**

void TraverseDbCcLinkList(pNode pHead){
    	pNode p=pHead->pNext;
    	printf("遍历链表的值为:");
    	while(p!=pHead){
    		printf("%d ",p->data);
    		p=p->pNext;
    	}
    	printf("\n");
    }

注意:(1).当p等于头指针，也就循环了一圈了。

**插入:**

void insert(pNode pHead,int pos,int value){
    	pNode p=pHead->pNext;
    	int i=0;
    	while(p!=pHead){
    		i++;
    		if(i==pos)
    			break;
    		p=p->pNext;
    	}
    	if(p!=pHead){
    	pNode pNew=(pNode)malloc(sizeof(Node));
    	pNew->data=value;
    	pNew->pPre=p->pPre;
    	p->pPre->pNext=pNew;
    	pNew->pNext=p;
    	p->pPre=pNew;
    	printf("插入成功");
    	}else{
    	printf("插入失败");
    	}
    }

注意:(1).先找到第pos个节点(不用pos-1),因为该链表是双向的，可以指向前一个节点。

**删除:**

void DeleteByPos(pNode pHead,int pos){
    	pNode p=pHead->pNext;
    	int i=0;
    	while(p!=pHead){
    		i++;
    		if(i==pos)
    			break;
    		p=p->pNext;
    	}
    	if(p!=pHead){
    		p->pPre->pNext=p->pNext;
    		p->pNext->pPre=p->pPre;
    		free(p);
    	printf("删除成功");
    	}else{
    	printf("删除失败");
    	}
    }

注意:(1).改变指针连接后，记得free(p)；