C语言：链表的创建、增、删、查

偏执的太偏执、 2022-08-03 11:42 150阅读 0赞

/*
    	链表的创建、增、删、查
    	增删：需要获取前一个节点的指针
    	查：获取当前节点的指针
    */
    
    # include <stdio.h>
    # include <malloc.h>
    
    //节点类型
    typedef struct node
    {
    	int data;
    	struct node * pNext;
    }NODE, * PNODE;
    
    PNODE creat_list(); //创建链表
    void traverse(PNODE pHead);  //链表遍历
    void insret(PNODE pHead, int pos, int val);  //在第pos位置插入元素
    int Length(PNODE pHead);  //链表的长度
    void dele(PNODE pHead, int pos);  //删除第pos位置的元素
    int getEle(PNODE pHead, int pos);  //获取第pos位置的元素
    
    int main(void)
    {
    	PNODE pHead = creat_list();  //创建链表
    	traverse(pHead);
    
    	//在链表的第pos位置前插入1元素
    	printf("在链表的第1个位置前插入7:");
    	insret(pHead, 1, 7);
    	traverse(pHead);
    
    	printf("删除第5个元素：");
    	dele(pHead, 5);
    	traverse(pHead);
    
    	printf("获取第3个元素：");
    	int val = getEle(pHead, 3);
    	printf("val = %d\n", val);
    
    	return 0;	
    }
    
    //创建链表
    PNODE creat_list()
    {
    	int i;
    	int len, val;
    
    	printf("输入创建链表的长度：");
    	scanf("%d", &len);
    	PNODE pHead = (PNODE)malloc(sizeof(NODE));  //创建头结点
    	pHead->pNext = NULL;
    	PNODE pTail = pHead;
    
    	PNODE pNew;
    
    	for(i = 0; i < len; i++)
    	{
    		printf("输入插入的第%d个元素 val:", i+1);
    		scanf("%d", &val);
    
    		pNew = (PNODE)malloc(sizeof(NODE));  //新节点
    		pNew->data = val;
    		pNew->pNext = NULL;
    
    		pTail->pNext = pNew;
    		pTail = pNew;
    	}
    
    	return pHead;
    }
    
    //遍历链表
    void traverse(PNODE pHead)
    {
    	PNODE p = pHead->pNext;  //指向首节点
    
    	while(p)
    	{
    		printf("%d ", p->data);
    		p = p->pNext;
    	}
    	printf("\n");
    }
    
    //在第pos位置前插入一元素val
    void insret(PNODE pHead, int pos, int val)
    {
    	PNODE p = pHead->pNext; //指向首节点
    
    	PNODE pNew = (PNODE)malloc(sizeof(NODE)); //创建新节点
    	pNew->data = val;
    	pNew->pNext = NULL;
    
    	int count = 0;
    	int len = Length(pHead);
    
    	//首先要知道第pos位置前节点的指针
    	//1.如果插入到第一个节点前
    	if(1 == pos)
    	{
    		pNew->pNext = p;
    		pHead->pNext = pNew;
    	}
    
    	//2.非第一个节点
    	else if(pos > 1 && pos < len + 2)
    	{
    		while(p)
    		{
    			count ++;
    			if(count == pos - 1)
    			{
    				pNew->pNext = p->pNext;
    				p->pNext = pNew;
    				break;
    			}
    			p = p->pNext;
    		}
    	}
    	else
    	{
    		printf("插入位置不对\n");
    		return;
    	}
    }
    
    //删除第pos位置元素
    void dele(PNODE pHead, int pos)
    {
    	PNODE p = pHead->pNext;  //指向首节点
    	int count = 0;
    	int len = Length(pHead);
    
    	if(1 == pos)  //头结点
    	{
    		pHead->pNext = p->pNext;
    	}
    	else if(pos > 1 && pos < len + 1)  //其他节点
    	{
    		while(p)
    		{
    			count ++;
    			if(count == pos - 1)
    			{
    				p->pNext = p->pNext->pNext;
    				break;
    			}
    			p = p->pNext;
    		}
    	}
    	else
    	{
    		printf("删除位置错误\n");
    		return;
    	}
    }
    
    //返回第pos个元素
    int getEle(PNODE pHead, int pos)
    {
    	PNODE p = pHead->pNext;  //指向首节点
    
    	int len = Length(pHead);
    	int count = 0;
    
        if(pos >= 1 && pos <= len)
    	{
    		while(p)  //获取该位置的节点指针
    		{
    			count ++;
    			if(count == pos)
    			{
    				return p->data;
    			}
    			p = p->pNext;
    		}
    	}
    	else
    	{
    		printf("元素不存在");
    		return -1;
    	}
    }
    
    //链表的长度
    int Length(PNODE pHead)
    {
    	int len = 0;
    	PNODE p = pHead->pNext;
    
    	while(p)
    	{
    		len ++;
    		p = p->pNext;
    	}
    
    	return len;
    }

![Center][]

[Center]: /images/20220731/673981047be24a879a8ac9c0c6d7f109.png