单向动态链表

╰半橙微兮° 2022-02-13 09:43 278阅读 0赞

## 单向动态链表 ##

**什么是链表**

*链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)*

**单向动态链表实现**

**①头文件代码**

#pragma once
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    typedef struct LinkNode { 
    	struct LinkNode* Next;
    	int Value;
    }LinkNode;
    typedef struct LinkList { 
    	struct LinkNode* head;
    	int size;
    }LinkList;
    //初始化链表
    LinkList* Init_LinkList();
    //在指定位置插入结点
    void Insert_LinkList(LinkList* list, int pos,int Value);
    //删除指定位置的结点
    void Remove_LinkList(LinkList* list, int pos);
    //获得链表的长度
    void Size_LinkList(LinkList* list);
    //查找链表位置
    void Find_LinkList(LinkList* list, int Value);
    //打印链表
    void Printf_LinkList(LinkList* list);
    //返回第一个结点位置
    void* Frist_LinkList(LinkList* list);
    //释放链表内存
    void Free_LinkList(LinkList* list);

**②函数文件代码**

#include "Linklist.h"
    //初始化
    LinkList* Init_LinkList() { 
    	LinkList* list = (LinkList*)malloc(sizeof(LinkList));
    	list->head = (LinkNode*)malloc(sizeof(LinkNode));
    	list->head->Value =0;
    	list->head->Next = NULL;
    	list->size = 0;
    	return list;
    }
    //在指定位置插入结点
    void Insert_LinkList(LinkList* list, int pos, int Value) { 
    	if (list == NULL) { 
    		return;
    	}
    	if (pos<0 || pos>list->size) { 
    		pos = list->size;
    	}
    	//创建新结点
    	LinkNode* NewNode = (LinkNode*)malloc(sizeof(LinkNode));
    	NewNode->Value = Value;
    	NewNode->Next = NULL;
    	//找结点
    	//辅助指针变量
    	LinkNode* Pcur = list->head;
    	for (int i = 0; i < pos; ++i) { 
    		Pcur = Pcur->Next;
    	}
    	//插入结点
    	NewNode->Next = Pcur->Next;
    	Pcur->Next = NewNode;
    	++list->size;
    }
    //删除指定位置的结点
    void Remove_LinkList(LinkList* list, int pos) { 
    	if (list == NULL) { 
    		return;
    	}
    	if (pos < 0 || pos >= list->size) { 
    		printf("您输入的位置不合法\n");
    	}
    	//创建辅助指针,需要两个辅助指针
    	LinkNode* Pcur=list->head;
    	LinkNode* Ppre = Pcur;//用来保存上一个结点的位置
    	for (int i = 0; i < pos; ++i) { 
    		Ppre = Pcur;
    		Pcur = Pcur->Next;
    	}
    	Ppre->Next = Pcur->Next;
    	free(Pcur);
    	--list->size;
    }
    //获得链表的长度
    void Size_LinkList(LinkList* list) { 
    	if (list == NULL) { 
    		return;
    	}
    	printf("这个链表现在有%d个结点", list->size - 1);
    }
    //查找链表位置
    void Find_LinkList(LinkList* list, int Value) { 
    	if (list == NULL) { 
    		return;
    	}
    	LinkNode* Pcur = list->head;
    	Pcur = Pcur->Next;
    	for (int i = 0; i < list->size; ++i) { 
    		if (Pcur->Value == Value) { 
    			printf("这个值在第%d个结点上\n", i);
    			break;
    		}
    		Pcur = Pcur->Next;
    	}
    }
    //打印链表
    void Printf_LinkList(LinkList* list) { 
    	if (list == NULL) { 
    		return;
    	}
    	LinkNode* Pcur = list->head;
    	for (int i = 0; i < list->size; ++i) { 
    		Pcur = Pcur->Next;
    		printf("%d--->", Pcur->Value);
    	}
    	printf("NULL\n");
    }
    //返回第一个结点位置
    void* Frist_LinkList(LinkList* list) { 
    	return list->head->Next;
    }
    //释放链表内存
    void Free_LinkList(LinkList* list) { 
    	if (list == NULL) { 
    		return;
    	}
    
    	//辅助指针
    	LinkNode* Pcur = list->head;
    	while (Pcur != NULL) { 
    		LinkNode* Ppre = Pcur->Next;
    		free(Pcur);
    		Pcur = Ppre;
    	}
    	free(list);
    }

**③测试文件代码**

#include <stdio.h>
    #include <stdlib.h>
    #include "Linklist.h"
    
    void test01() { 
    	//初始化
    	LinkList* list = Init_LinkList();
    	//插入新结点
    	for (int i = 0; i < 15; ++i) { 
    		Insert_LinkList(list, i, 2 * i);
    	}
    	//打印结点
    	Printf_LinkList(list);
    	//删除结点
    	Remove_LinkList(list, 5);
    	Printf_LinkList(list);
    	//查找
    	Find_LinkList(list, 10);
    	//释放内存
    	Free_LinkList(list);
    }
    int main() { 
    
    	test01();
    	system("pause");
    	return 0;
    }