单链表的操作

桃扇骨 2024-04-17 20:49 57阅读 0赞

## 创建单链表 ##

typedef struct Node
    {
    	int elem;
    	struct Node * next;
    }linklist, *plinklist;

## 生成单链表 ##

*  函数声明

plinklist linklist_create(int size);

*  函数实现

plinklist linklist_create(int size)
    {
        
    	plinklist node, head;
    	head = (plinklist)malloc(sizeof(linklist));
    
    	// 头结点 elem 表示链表大小，头结点 next 指向第一个元素
    	head->elem = size;
    	head->next = NULL;
    
    	node = head;
    
    	for (int i = 0; i < size; i++)
    	{
        
    		node->next = (plinklist)malloc(sizeof(linklist));
    		node = node->next;
    		node->elem = rand() % 100;
    		node->next = NULL;
    	}
    
    	return head;
    }

## 插入 ##

*  函数声明

void linklist_insert(plinklist list, int locate, int elem);

*  函数实现

void linklist_insert(plinklist plist, int location, int elem)
    {
    	plinklist head = plist;
    	plinklist inode = NULL;
    	int size = linklist_size(plist);
    
    	if (location < 0 || location > size)
    		return;
    
    	inode = (plinklist)malloc(sizeof(linklist));
    	inode->elem = elem;
    
    	if (location == 0)
    	{
    		inode->next = head->next;
    		head->next = inode;
    	}
    	else
    	{
    		plinklist node = linklist_find(plist, location - 1);
    		plinklist next = node->next;
    		node->next = inode;
    		inode->next = next;
    	}
    	linklist_update_head(head);
    }

## 删除 ##

*  函数声明

void linklist_delete(plinklist list, int locate);

*  函数实现

void linklist_delete(plinklist plist, int location)
    {
    	plinklist head = plist;
    	int size = linklist_size(plist);
    
    	if (location < 0 || location >= size)
    		return;
    
    	if (location == 0)
    	{
    		plinklist dnode = head->next;
    		head->next = dnode->next;
    		free(dnode);
    	}
    	else
    	{
    		plinklist node = linklist_find(plist, location - 1);
    		plinklist dnode = node->next;
    		node->next = dnode->next;
    		free(dnode);
    	}
    	linklist_update_head(head);
    }

## 遍历 ##

*  函数声明

void linklist_display(plinklist list);

*  函数实现

void linklist_display(plinklist plist)
    {
        
    	plinklist head = plist;
    	plinklist node = head->next;
    	while (node != NULL)
    	{
        
    		printf("%d\t", node->elem);
    		node = node->next;
    	}
    	printf("\n");
    }

## 查找 ##

*  函数声明

plinklist linklist_find(plinklist list, int location);

*  函数实现

plinklist linklist_find(plinklist list, int location)
    {
        
    	plinklist head = list;
    	plinklist node = head->next;
    
    	if (location == 0)
    		return node;
    	else
    	{
        
    		while (location != 0)
    		{
        
    			if (linklist_is_tail(node)) break;
    
    			node = node->next;
    			location--;
    		}
    
    		if (location != 0)
    			return NULL;
    
    		return node;
    	}
    }

## 完整实例 ##

*  头文件 `linklist.h`

#ifndef LINKLIST_H
    #define LINKLIST_H
    
    typedef struct Node
    {
        
    	int elem;
    	struct Node * next;
    }linklist, *plinklist;
    
    plinklist linklist_create(int size);
    void linklist_insert(plinklist list, int locate, int elem);
    void linklist_delete(plinklist list, int locate);
    void linklist_display(plinklist list);
    plinklist linklist_find(plinklist list, int location);
    int linklist_is_tail(plinklist list);
    int linklist_size(plinklist list);
    void linklist_update_head(plinklist list);
    
    #endif

*  源文件 `linklist.c`

#include <stdio.h>
    #include <stdlib.h>
    #include "linklist.h"
    
    int main() {
        
    	int size;
    	int index = 0;
    	plinklist list;
    
    	printf("输入此单链表的大小：");
    	scanf_s("%d", &size);
    
    	list = linklist_create(size);
    	linklist_display(list);
    
    	for (index = 0; index < size; index++)
    	{
        
    		plinklist node = linklist_find(list, index);
    		printf("位置 %d 的值为：%d \n", index, node->elem);
    	}
    
    	printf("\n在位置5插入元素2后\n");
    	linklist_insert(list, 5, 2);
    	linklist_display(list);
    
    	printf("\n在最后一个位置插入元素-1后\n");
    	linklist_insert(list, linklist_size(list), -1);
    	linklist_display(list);
    
    	printf("\n删除位置3元素后\n");
    	linklist_delete(list, 2);
    	linklist_display(list);
    
    	printf("\n删除位置1元素后\n");
    	linklist_delete(list, 0);
    	linklist_display(list);
    
    	printf("\n删除位置最后的元素后\n");
    	linklist_delete(list, linklist_size(list) - 1);
    	linklist_display(list);
    
    	return 0;
    }
    
    plinklist linklist_create(int size)
    {
        
    	plinklist node, head;
    	head = (plinklist)malloc(sizeof(linklist));
    
    	// 头结点 elem 表示链表大小，头结点 next 指向第一个元素
    	head->elem = size;
    	head->next = NULL;
    
    	node = head;
    
    	for (int i = 0; i < size; i++)
    	{
        
    		node->next = (plinklist)malloc(sizeof(linklist));
    		node = node->next;
    		node->elem = rand() % 100;
    		node->next = NULL;
    	}
    
    	return head;
    }
    
    void linklist_display(plinklist plist)
    {
        
    	plinklist head = plist;
    	plinklist node = head->next;
    	while (node != NULL)
    	{
        
    		printf("%d\t", node->elem);
    		node = node->next;
    	}
    	printf("\n");
    }
    
    void linklist_insert(plinklist plist, int location, int elem)
    {
        
    	plinklist head = plist;
    	plinklist inode = NULL;
    	int size = linklist_size(plist);
    
    	if (location < 0 || location > size)
    		return;
    
    	inode = (plinklist)malloc(sizeof(linklist));
    	inode->elem = elem;
    
    	if (location == 0)
    	{
        
    		inode->next = head->next;
    		head->next = inode;
    	}
    	else
    	{
        
    		plinklist node = linklist_find(plist, location - 1);
    		plinklist next = node->next;
    		node->next = inode;
    		inode->next = next;
    	}
    	linklist_update_head(head);
    }
    
    void linklist_delete(plinklist plist, int location)
    {
        
    	plinklist head = plist;
    	int size = linklist_size(plist);
    
    	if (location < 0 || location >= size)
    		return;
    
    	if (location == 0)
    	{
        
    		plinklist dnode = head->next;
    		head->next = dnode->next;
    		free(dnode);
    	}
    	else
    	{
        
    		plinklist node = linklist_find(plist, location - 1);
    		plinklist dnode = node->next;
    		node->next = dnode->next;
    		free(dnode);
    	}
    	linklist_update_head(head);
    }
    
    plinklist linklist_find(plinklist list, int location)
    {
        
    	plinklist head = list;
    	plinklist node = head->next;
    
    	if (location == 0)
    		return node;
    	else
    	{
        
    		while (location != 0)
    		{
        
    			if (linklist_is_tail(node)) break;
    
    			node = node->next;
    			location--;
    		}
    
    		if (location != 0)
    			return NULL;
    
    		return node;
    	}
    }
    
    int linklist_is_tail(plinklist list)
    {
        
    	return list->next == NULL ? 1 : 0;
    }
    
    int linklist_size(plinklist list)
    {
        
    	return list->elem;
    }
    
    void linklist_update_head(plinklist list)
    {
        
    	plinklist head = list;
    	plinklist node = head->next;
    	int size = 0;
    	while (node != NULL)
    	{
        
    		size++;
    		node = node->next;
    	}
    	head->elem = size;
    }