单链表之c代码

分手后的思念是犯贱 2022-08-04 05:17 112阅读 0赞

我们知道数据结构就是数据及其相互关系，包括逻辑结构和物理结构。单链表的逻辑结构是一种一对一的线性关系，物理结构是利用节点把数据结合起来,在计算机中体现这种一对一的数据关系。单链表节点包括包含数据本身信息的数据域和体现数据一对一关系的指针域。因为单链表只有一个指向后一节点的单一指针域next 所以单链表只能从前往后遍历，而不能从后向前遍历，这就意味着一旦单链表的某一节点丢失 ，后面所有的数据信息都会丢失，并且单链表有头指针唯一确定，要想查找单链表的  
某一数据只能从头开始遍历，最坏时间复杂度为O(n)，但因为数据间是通过指针来确定数据的前后关系的，所以单链表在内存中是不一定要连续分配的内存，可以更有效的利用内存空间，同时可以快速的在一个节点后插入和删除一个数据元素。在某一节点后插入和删除一个节点的最坏时间复杂度O(1).在编写程序时，特别是面向过程的c语言程序一定牢记 程序 =数据结构+ 算法。数据在内存中有两种存储方式，一种就是连续存储的数组，另一种就是结构体。算法就是对数据的操作。同时 数据结构 和定义在数据结构上的算法 组成了抽象数据类型，注意这里是类型，类型不只是数据，还有定义在该数据的相关算法。

单链表 是n个相同节点组成的，每一个节点又包含了两个信息 ，包含数据信息的数据域，包含数据间关系的指针域所以要声明一个单链表结构体之前我们必须声明一个节点结构体单链表节点结构体ListNode。

1.头文件list.h

//单链表List.h
    #ifndef LIST_H
    #define LIST_H
    
    //单链表节点的数据结构
    typedef struct ListNode{
    	void * data;//因为 不知道单链表中存储的是何种数据 ，为了抽象所以用一个泛型指针 void* 指向数据
    	ListNode *next;//指向下一节点的指针 next
    }ListNode;
    
    //可针对单链表节点的相关操作（1）用一个数据初始化一个节点 （2）读取节点的数据信息 （3）销毁一个节点
    //init_Node
    ListNode* init_node(void *data); //初始化一个节点 最后生成的是一个节点
    void *get_data(const ListNode * list_node);
    void destroy_node(ListNode * list_node);
    
    //单链表抽象类型
    //单链表数据结构 (1)单链表的大小size （2）头节点 head （3）尾节点 tail （4）添加一个新节点 （5）销毁节点
    typedef struct List{
    	int size;//大小
    	ListNode *head;//头节点指针
    	ListNode *tail;//尾节点指针
    	ListNode* (*init_node)(void *data);//添加一个节点
    	int (*destroy_node)(ListNode *list_node);//销毁一个节点
    }List;
    
    //单链表的相关操作:(1)初始化单链表 init_list (2)在一个节点后插入一个新的节点 ins_next_list 
    //(3)在一个节点后删除一个节点rem_next_list (4)销毁单链表 dstroy_list
    //(5)单链表大小 size_list (6) 获取头节点 head_list (7)获取尾节点 tail_list (8)判断是否为头节点 is_head 
    //判断是否为尾节点 is_tail
    void init_list(List *list);
    int ins_next_list(List *list,ListNode *now_node,int(*init_node)(void *data));
    int rem_next_list(List *list,ListNode *now_node,int(*destroy_node)(ListNode *list_node));
    void destroy_list(List *list);
    int size_list(const List *list);
    ListNode* head_list(const List *list);
    ListNode* tail_list(const List *list);
    int is_head(const List *list);
    int is_tail(const List *list);
    
    #endif

2.单链表实现文件list.cpp

//list.cpp
    #include<stdlib.h>
    #include<stdio.h>
    
    #include"list.h"
    
    //生成一个单链表节点:init_node
    //功能：动态分配内存，生成一个单链表节点，数据域中的数据为 data, 指针域为NULL 为单链表的插入做准备
    //返回值：内存中动态分配的单链表节点指针 ListNode
    //时间复杂度：O(1)
    ListNode* init_node(void *data){ 
    
    	ListNode* new_node ;//声明一个单链表节点类型的指针
    
    		//在堆中为新的节点分配内存空间
    	if( ( new_node = (ListNode*)malloc( sizeof(ListNode) ) ) == NULL )
    		return NULL;//分配失败
    
    	//分配成功
    	//将数据封装为节点
    	new_node->data = data;
    	new_node->next = NULL;
    
    	//将指向该节点的指针返回
    	return new_node;
    
    }
    
    //destroy_node:释放节点list_node 持有的内存空间
    //返回值 ：void
    //参数; list_node 为单链表节点
    //时间复杂度：O(1)
    void destroy_node(ListNode * list_node){
    	free(list_node);
    	return;
    }
    
    //初始化单链表 init_list
    // 功能：对链表的其余操作都是在此初始化之后,如果不调用init_list,编译器会报错：list 未被初始化。
    //返回值 void
    //时间复杂度O(1)
    void init_list(List *list){
    	list->size = 0;
    	list->head = NULL;
    	list->tail = NULL;
    }
    
    //在链表中插入一个新的节点：ins_next_list
    //功能：在一个节点now_node后插入一个数据项为data的新的节点，如果now_node为 NULL 则在链表的头部插入
    //返回值：当插入成功返回0，插入失败 返回-1
    //时间复杂度：O(1)
    //参数：list 为空， list 只有一个节点，list有多个节点 ， now_node 为空， now_node 为中间节点
    //now_node 为尾部节点
    //测试用例 {list == NULL , now_node == NULL , [1,2,3,4,5],now_node->next == NULL}
    int ins_next_list(List *list,ListNode *now_node, void *data){
    	//把数据封装为一个新的节点，这里需要动态分配内存空间，已经在 int(*init_node)(void *data) 
    	//中封装好了
    	if( list == NULL )
    		return -1;
    	
    	else
    	{
    	ListNode *new_node = (*init_node)(data);//封装好的节点类型
    	
    	//将节点插入到相应位置
    	//查看链表list 中有哪些元素发生了改变
    	//size自增
    	if(now_node == NULL)//新节点 作为头节点进行插入
    	{
    		if(list->size == 0)//当链表为空时
    		{ 
    
    			list->head = new_node;
    			list->tail = new_node;
    			++list->size;
    		}
    		else//链表非空时，
    		{
    			new_node->next = list->head;
    			list->head = new_node;
    			++list->size;
    		}
    		//这里可以把共有的代码提取出来
    		//list->head = new_node;
    		//++list->size;
    	}
    
    	//新节点 非头节点（now_node 为中间节点，now_node 为链表中最后第二个节点，now_node 为最后的一个节点）
    	else
    	{
    		if(now_node == list->tail)//当前节点为尾节点
    		{
    			new_node->next = now_node->next;
    			now_node->next = new_node;
    			list->tail = new_node;
    			++list->size;
    		}
    		else//当前节点为中间节点
    		{
    			new_node->next = now_node->next;
    			now_node->next = new_node;
    			++list->size;
    		}
    		//这里可以把插入节点的共有代码提取出来：
    		// new_node->next = now_node->next;
    		// now_node->next = new_node;
    
    		
    	}
    	//插入都有链表长度加1
    	// ++list->szie
    
    	return 0;
    
    }
    
    }
    
    
    
    //rem_next_list:从单链表list当前节点 now_node  后删除一个节点，list必须已经初始化，当传入实参now_node 
    //为NULL时 ，删除头节点
    //函数返回值： 当删除成功返回0，当删除失败 返回 -1
    //参数说明：list 必须已经初始化，list 不能为空，now_node == NULL 删除头节点，now_node 为尾节点时，返回-1,
    //int(*destroy_node)(ListNode *list_node);为函数指针，指向节点的析构函数，也就是说在堆中动态释放该节点所占有的内存空间。
    //时间复杂度：O(1)
    //测试用例说明：1.list 未初始化(return -1)，2.list 为空2.list 只有一个节点(now_node == NULL(删除头节点，head =tail = NULL,size =0) ,now_node == head (删除失败，return-1))
    //3.list 有多个节点(now_node == NULL（删除头节点，head =head->next）, now_node == head, now_node == 中间节点(pnode),(正常删除，1.保存原有信息2.释放节点内存空间，3.size-1)
    //now_node =倒数第二个节点（删除尾节点， 正常删除外， tail ，size 需要改变），now_node =tail（删除失败 ，return -1）)
    
    int rem_next_list(List *list,ListNode *now_node,void (*destroy_node) (ListNode *list_node)){
    	ListNode * old_node;//将要删除的节点
    	ListNode *pnode ;//保存的中间节点
    
    	if(list == NULL)//链表不存在
    		return -1;
    
    	if(list->size == 0)//链表为空
    		return -1;
    
    	if(list->size == 1)//链表只有一个节点
    	{
    		if(now_node == NULL)//删除头节点
    		{
    			old_node = list->head;
    			destroy_node(old_node);//销毁节点，释放节点所占的内存空间
    			
    			list->head = list->tail = NULL;//链表为空
    			--list->size ;
    
    			return 0;
    
    		}
    
    		else //删除失败
    			return -1;
    	}
    
    	else if (list->size == 2)//链表由两个节点
    	{
    
    		if(now_node == NULL)//删除头节点
    		{  
    			pnode = list->head->next;
    			old_node = list->head;
    			destroy_node( old_node );//销毁节点
    			list->head = list->tail = pnode;//删除后剩下的唯一节点，即是头节点，又是尾节点
    			--list->size;
    			return 0;
    		}
    
    		/*else if( now_node->next = list->tail )*/
    		else if( now_node->next == list->tail )//删除尾节点
    		{ 
    		    now_node -> next = list->tail->next;//删除尾节点，必须使尾节点的前一节点 的next 指向 NULL;
    			old_node = now_node->next;//要删除的节点，也就是尾节点
    			//pnode = old_node->next;
    			destroy_node( old_node );
    			list->tail = list->head;//删除后只剩下一个节点了，尾节点和头节点是同一个节点，都是原来的头节点
    			--list->size;
    			return 0;
    		}
    
    		else//删除不存在的节点，失败
    		{
    
    			return -1;
    		}
    	}
    	else //链表有n（n>2）个节点
    	{
    		if(now_node == NULL)//删除头节点
    		{
    			old_node = list->head;
    			pnode = old_node->next;
    			destroy_node( old_node );//销毁节点
    			list->head = pnode;
    			--list->size;
    			return (0);
    		}
    		else//删除其他节点
    		{
    			old_node = now_node->next;
    
    			if( old_node == NULL )//删除不存在的节点
    			{
    				return -1;
    			}
    
    			else if( old_node == list->tail )//删除尾节点
    			{
    				//now_node -> next = NULL;//如果删除的是尾节点 注意一定要将尾节点的前一节点的指针域 next 指向NULL
    				now_node -> next = old_node -> next;
    				//pnode = old_node->next;
    				pnode = now_node;
    				destroy_node( old_node );
    				list->tail = pnode;
    				--list->size;
    
    				return 0;
    			}
    
    			else//删除中间节点
    			{
    				pnode = old_node->next;
    				now_node->next = pnode;//将要删除的节点从链表中移除
    				destroy_node(old_node);//释放节点所占的内存
    				--list->size;//链表的节点数 -1
    				return 0;
    
    			}
    
    
    		}
    	}
    
    }
    
    
    //destroy_list:销毁单链表，从头到尾 将链表的节点销毁
    //返回值：销毁成功 返回 0，销毁失败 返回-1；
    //参数：已经初始化了的单链表
    //时间复杂度：O（n）相当于遍历了整个单链表
    void destroy_list(List *list){
    	while (list->size > 0 )//如果链表不为空，调用已经定义好的函数从头到尾删除链表的节点
    		rem_next_list(list,NULL,destroy_node);
    	
    }
    
    
    int main(void){
    	List list;//声明一个单链表
    	List *plist = &list;
    
    	//测试初始化链表：init_list(&list)
    	init_list(plist);//初始化单链表 此时 
    	printf("list_size:%d\n",plist->size);
    	printf("list_head:%p\n",plist->head);
    	printf("list_tail:%p\n",plist->tail);
    
    	//测试在链表中插入一个节点：int ins_next_list(List *list,ListNode *now_node, void *data)
    	//测试数据集data{1,2,3,4,5}
    	//测试用例[list,now_node,data]=[NULL,NULL,1];[list,NULL,1];[list,head,2];[list,中间节点,3]
    	//[list,NULL,0];[list,tail,5]
    	int data[5] ={1,2,3,4,5};
    	
    	int True = ins_next_list(NULL,NULL,&data[1]);//返回值为 -1插入失败
    	printf("ins_next_list:%d\n",True);
    
    	True = ins_next_list(plist,NULL,&data[1]);//添加头节点 数据项 data =2 ，list_size = 1链表中的数据元素：{2}
    	printf("ins_next_list:%d\n",True);
    	printf("List_size:%d\n",plist->size);
    	printf("*data:%d\n",*(int*)(plist->head->data));
    
    	True = ins_next_list(plist,plist->head,&data[2]);//在头节点后添加一个节点 数据项 data=3 ，list_size =2 链表中数据元素{2，3}
    	printf("ins_next_list:%d\n",True);
    	printf("List_size:%d\n",plist->size);
    	printf("*data:%d\n",*(int*)(plist->head->next->data));
    
    	True = ins_next_list(plist,plist->head->next,&data[3]);//在第二个节点后添加一个节点 数据项 data =4 ，list_size = 3 ,链表中的数据元素{2，3，4}
    	printf("ins_next_list:%d\n",True);
    	printf("List_size:%d\n",plist->size);
    	printf("*data:%d\n",*(int*)(plist->head->next->next->data));
    
    	True = ins_next_list(plist,NULL,&data[0]);//在链表头节点前插入一个节点 作为新的头节点，数据项 data = 1，链表中的数据元素 {1，2，3，4}
    	printf("ins_next_list:%d\n",True);
    	printf("List_size:%d\n",plist->size);
    	printf("*data:%d\n",*(int*)(plist->head->data));
    
    	True = ins_next_list(plist,plist->tail,&data[4]);//在尾节点后添加一个节点 作为新的尾节点，数据项 data = 5, 链表中的数据元素{1，2，3，4，5}
    	printf("ins_next_list:%d\n",True);
    	printf("List_size:%d\n",plist->size);
    	printf("*data:%d\n",*(int*)(plist->tail->data));
    
    	//输出链表中的所有数据元素（遍历）{1，2，3，4，5}
    	ListNode* pNode = plist->head;
    	while( pNode != NULL ){
    		
    		printf("%d ",*(int*)pNode->data );
    		pNode = pNode->next;
    	}
    	printf("\n");
    
    	测试销毁链表 现在链表的数据元素为{1，2，3，4，5}，
    
     //   destroy_list(plist);
    	//printf("plist->size:%d\n",plist->size);//如果为 0 链表成功销毁
    	//
    
    	//测试在一个链表中删除节点
    //现在链表中总共有5个数据 从头至尾遍历 结果为{1，2，3，4，5}
    //测试用例为{链表未初始化，链表为空， 链表有n（n=5）个节点（删除头节点，删除尾节点，删除中间节点）链表只有两个节点，链表只有一个节点}
    
    	ListNode* qnode;//测试用的节点
    	List qlist;
    	List *pqlist = &qlist;//测试用的链表
    	int result; //用来判断是否删除节点失败的结果，result = 0，删除成功，result = -1,删除失败
    
    	//1.链表未初始化，通不过编译器的语法检查
    	//qnode = NULL;
    	//	result = rem_next_list(pqlist,qnode,destroy_node);//
    	//printf("rem_next_list: %d",result);
    
    	//1.链表为空,删除失败返回-1
    	init_list(pqlist);
    	qnode = NULL;
    		result = rem_next_list(pqlist,qnode,destroy_node);//
    	printf("rem_next_list: %d\n",result);
    
    	//2.链表有5个节点，{1,2,3,4,5}删除头节点{2,3,4,5}
    	pqlist = plist;
    	qnode = NULL;
    	result = rem_next_list(pqlist,qnode,destroy_node );
    	printf("rem_next_list: %d\n",result);
    
        pNode = pqlist->head;
    	while( pNode != NULL ){
    		
    		printf("%d ",*(int*)pNode->data );
    		pNode = pNode->next;
    	}
    	printf("\n");
    
    
    	//删除链表中的尾节点，删除后链表中元素为{2，3，4}；
    
    	pqlist = plist;
    
    	//找到尾节点前一节点
    	qnode = pqlist->head;
    	while(qnode->next != pqlist->tail )
    		qnode = qnode->next;
    	//此时删除的是尾节点5
    	result = rem_next_list(pqlist,qnode,destroy_node );
    	printf("rem_next_list: %d\n",result);
    
        pNode = pqlist->head;
    	while( pNode != NULL ){
    		printf("%d ",*(int*)pNode->data );
    		pNode = pNode->next;
    	}
    	printf("\n");
    
    	//此时链表数据{2，3，4}，删除中间节点3后链表数据域{2，4}
    	pqlist = plist;
    
       //找到尾节点前一节点
    	qnode = pqlist->head;
    	
    	//此时删除的是尾节点3
    	result = rem_next_list(pqlist,qnode,destroy_node );
    	printf("rem_next_list: %d\n",result);
    
        pNode = pqlist->head;
    	while( pNode != NULL ){
    		printf("%d ",*(int*)pNode->data );
    		pNode = pNode->next;
    	}
    	printf("\n");
    
    	//只有两个节点{2，4}删除头节点2 后，链表数据为{4}
    	pqlist = plist;
    
    	//要删除的节点
    	qnode = NULL;
    	//此时删除的是2各数据的头节点；
    	result = rem_next_list(pqlist,qnode,destroy_node );
    	printf("rem_next_list: %d\n",result);
    
        pNode = pqlist->head;
    	while( pNode != NULL ){
    		printf("%d ",*(int*)pNode->data );
    		pNode = pNode->next;
    	}
    	printf("\n");
    
    	只有两个节点{2，4}删除尾节点4 后，链表数据为{2}
    	//pqlist = plist;
    
    	要删除的节点前一节点
    	//qnode = pqlist->head;
    	此时删除的是2各数据的头节点；
    	//result = rem_next_list(pqlist,qnode,destroy_node );
    	//printf("rem_next_list: %d\n",result);
    
     //   pNode = pqlist->head;
    	//while( pNode != NULL ){
    	//	printf("%d ",*(int*)pNode->data );
    	//	pNode = pNode->next;
    	//}
    	//printf("\n");
    
    	//只有两个节点{2，4},当前节点 为 尾节点时
    	//pqlist = plist;
    	//printf("size: %d\n",pqlist->size);
    
    	当前的节点 为尾节点 删除失败 返回-1；删除后数据不变还是{2，4}
    	//qnode = pqlist->tail;
    	//
    
    	//result = rem_next_list(pqlist,qnode,destroy_node );
    	//printf("rem_next_list: %d\n",result);
    
     //   pNode = pqlist->head;
    	//while( pNode != NULL ){
    	//	printf("%d ",*(int*)pNode->data );
    	//	pNode = pNode->next;
    	//}
    	//printf("\n");
    
    
    	
    
    	//此时 链表中只剩一个节点数据{4}，
    	pqlist = plist;
    
    	//要删除的前一节点 为head，删除失败 返回-1； 操作结束后链表中还是{4}
    	qnode = pqlist->head;
    	result = rem_next_list(pqlist,qnode,destroy_node );
    
    
    	printf("rem_next_list: %d\n",result);
    
        pNode = pqlist->head;
    	while( pNode != NULL ){
    		printf("%d ",*(int*)pNode->data );
    		pNode = pNode->next;
    	}
    
    	printf("\n");
    
    
    	//此时 链表中只剩一个节点数据{4}，
    	pqlist = plist;
    
    	//传入参数 为 NULL，删除成功返回 0； 操作结束后链表为 空；
    	qnode = NULL;
    	result = rem_next_list(pqlist,qnode,destroy_node );
    	printf("rem_next_list: %d\n",result);
    	printf("链表已经为 空啦，啦啦啦");
    
        pNode = pqlist->head;
    	while( pNode != NULL ){
    		printf("%d ",*(int*)pNode->data );
    		pNode = pNode->next;
    	}
    	printf("\n");
    	
    	
    	
    
    	return 0;
    }

3.测试结果： ![20150818182843519][]

[20150818182843519]: /images/20220731/a19f105a43f34856b3e0b41d44db663f.png