C语言：循环单链表的创建，遍历，插入

秒速五厘米 2022-08-03 05:15 177阅读 0赞

/*
    	1.循环单链表的创建，由尾节点指向该链表，
    	2.循环链表遍历
    	3.求链表的长度
    	4.向链表中插入元素
    */
    
    # include <stdio.h>
    # include <malloc.h>
    
    
    typedef struct node
    {
    	int data;
    	struct node * pNext;
    }NODE, * PNODE;
    
    
    PNODE creat_list();    //创建链表
    void travese(PNODE T);   //遍历链表
    void insert(PNODE &T, int pos, int val);  //插入元素
    int length(PNODE T);  //求链表的长度
    
    int main(void)
    {
    	//返回循环链表的尾指针
    	PNODE T = creat_list();
    	travese(T);
    
    	//若在第一个有效节点前插入新节点5
    	insert(T, 4, 5);
    	travese(T);
    
    	return 0;
    }
    
    //循环单链表的创建，返回尾节点
    PNODE creat_list()
    {
    	PNODE pHead = (PNODE)malloc(sizeof(NODE));  //头结点
    	pHead->pNext = pHead;
    
    	PNODE pTail = pHead; //尾指针
    	PNODE pNew;
    
    	int len;
    	int i;
    	int val;
    
    	printf("输入此循环链表的长度 len = ");
    	scanf("%d", &len);
    
    	for(i = 0; i < len; i++)
    	{
    		printf("输入第%d个元素的值 val = ", i+1);
    		scanf("%d", &val);
    
    		pNew = (PNODE)malloc(sizeof(NODE));  //开辟新节点
    
    		pNew->data = val;
    		pNew->pNext = pHead;  //新节点的指针域始终指向头结点
    
    		pTail->pNext = pNew;
    		pTail = pNew;
    	}
    
    	return pTail;  //返回尾指针
    }
    
    //循环单链表的遍历
    void travese(PNODE T)
    {
    	PNODE pHead = T->pNext;   //pHead指向头结点
    	PNODE p = pHead->pNext;   //p指向首节点，第一个有效节点
    
    	while(p != pHead)  //循环链表的终止条件:（p != 头指针）
    	{
    		printf("%d ", p->data);
    		p = p->pNext;
    	}
    	printf("\n");
    }
    
    //向第pos个有效节点前，插入新节点
    void insert(PNODE &T, int pos, int val)  //可能会改变尾指针的位置
    {
    	PNODE pHead = T->pNext; //pHead指向头结点
    
    	PNODE pNew = (PNODE)malloc(sizeof(NODE));
    	pNew->data = val;
    
    	PNODE p = pHead->pNext;  //指向第一个有效节点
    	
    	int len = length(T);
    	int count = 0;
    
    	if(1 == pos)  //插入到第一个有效节点前
    	{
    		pNew->pNext = pHead->pNext;
    
    		pHead->pNext = pNew;
    	}
    	if(pos >1 && pos < len + 1)
    	{
    		while(p != NULL)
    		{
    			count ++;
    			if(count == pos -1)  //pos位置前一个节点
    			{
    				pNew->pNext = p->pNext;
    				p->pNext = pNew;
    				break;			
    			}
    			p = p->pNext;
    		}
    		
    	}
    	if(pos == len + 1)  //在链表尾插入一节点
    	{	
    		pNew->pNext = T->pNext;
    		T->pNext = pNew;
    		T = pNew;
    	}
    	if(pos > len + 1)
    	{
    		printf("插入位置错误！");
    		return;
    	}
    
    }
    
    //求链表的长度
    int length(PNODE T)
    {
    	PNODE pHead = T->pNext;
    	PNODE p = pHead->pNext;
    
    	int len = 0;
    
    	while(p != pHead)
    	{
    		len ++;
    		p = p->pNext;
    	}
    	return len;
    }

![Center][]

[Center]: /images/20220731/88fdf45aa64d4dfd82c5ca1422452e19.png