线性表之链式存储结构_单链表相关算法

刺骨的言语ヽ痛彻心扉 2022-06-03 03:57 180阅读 0赞

在存储结构上，不需要连续的存储空间，需要上一个结点的指针域 指向下一个结点即可，找到一个结点就可以找到下一个结点。

学习教材是大话数据结构，加上自己的一些个人理解。这个算法 有点绕，需要对指针 相关内容相当熟悉。通过学习感觉单链表相关算法还是蛮考验C知识的和逻辑思维。

下面看代码：

#include <stdio.h>
    #include <stdlib.h>
    #define	ERROR 0
    #define OK 1
    typedef int EleType;
    typedef int Status;
    typedef struct Node Node;
    
    //链表元素
    struct Node
    {
    	EleType data;//数据域
    	Node * next;//指针域
    };
    typedef Node* LinkList;
    void printLinkList(const LinkList * const list) {
    	if (NULL ==list) {//链表为空
    		printf("printLinkList error \n");
    		return;
    	}
    	int i = 1;
    	LinkList li = (*list)->next;//从头结点后面第一个结点开始遍历
    	while (li)//最后一个元素没有指向，不会进行循环。
    	{
    		printf("第%d元素:%d\t", i, li->data);
    		li = li->next;
    		i++;
    	}
    	printf("\n");
    	return;
    }
    //创建拥有头结点的链表
    //头插法创建链表，往链表中添加元素，新创建的的元素始终在头结点后面类似 头指针 -> 头结点->An->An-1->An-2 ...-> A1
    //元素的数据 随机生成100以内的数字
    Status creatLinkListInHead(LinkList *list,int n) {
    	srand(time(0));//设置随机种子，为产生随机数做准备。
    	//LinkList 类型 和 Node * 类型是一样的！看最上方定义类型别名，为什么可以做呢？链表的头指针 就是指向结点Node，所有链表类型是 Node *，只是为了更好看而已。 
    	LinkList li=NULL;
    	Node *node=NULL;//可以定义为 LinkList *node = NULL;
    	int i = 0;
    	li = (LinkList)malloc(sizeof(Node));//头指针指向头结点，给头结点分配空间
    	if (NULL == li||n<0) {//分配内存空间失败或者链表元素个数非法 返回
    		return ERROR;
    	}
    	li->next = NULL;//初始头结点没有指向
    	for ( i = 0; i < n; i++)
    	{
    		node = (Node*)malloc(sizeof(Node));//给结点分配空间
    		if (NULL==node) {//给分配空间失败 
    			return ERROR;
    		}
    		node->data = rand()%100;//除以100取余的到100以内的数字，不包括100，如果含100 就需要+1
    		node->next = li->next;//新添加的元素指针域 指向头结点后面的结点
    		li->next = node;//头结点指针域 指向新增加的元素
    
    	}
    	*list = li;//通过指针 给外部链表赋值
    	return OK;
    }
    //尾插法创建链表，往链表中添加元素，先添加的元素放前面，后添加的元素放后面，遵循先来后到的道理
    Status creatLinkListInTail(LinkList *list, int n) {
    	srand(time(0));//设置随机种子
    	LinkList li = NULL ;
    	Node *node = NULL;
    	int i = 0;
    	li = (LinkList)malloc(sizeof(Node));
    	if (NULL == li || n<0) {//分配内存空间失败或元素个数非法
    		return ERROR;
    	}
    	li->next = NULL;//初始头结点指向
    	*list = li;//给通过外部链表赋值，指向头结点，此时 list 和 li 都指向头结点。
    	for ( i = 0; i < n; i++)
    	{
    		node = (Node*)malloc(sizeof(Node));//给结点分配空间
    		if (NULL == node) {//分配空间失败 
    			return ERROR;
    		}
    		node->data = rand() % 100;//除以100取余的到100以内的数字，不包括100，如果含100 就需要+1
    		li->next = node;//新结点 放到链表末尾
    		li = node;//移动链表指针指向最新链表最后一个元素，为了下次循环在链表末尾添加元素
    		//temp = node;
    	}
    	//最后表尾元素指针域 设置NULL
    	li->next = NULL;
    	//*list = li;//一定要放在for循环前面，不然头结点的内存空间没有指向！起初l指向头结点，但是进入for循环后l的指向发生改变要移动指向最新添加的结点元素。
    	return OK;
    }
    //获取链表元素数据,通过指针返回 链表第i个元素的 数据
    //i还是按国人的顺序来吧，从1开始
    Status getELement(LinkList list, int position,EleType *e) {
    	//异常情况：空指针,元素位置非法
    	if (NULL == list || position < 1) {
    		return ERROR;
    	}
    	LinkList li = list;
    	int i = 1;
    	while (li && i<position) {//在链表范围内遍历元素 直到 找到第position位置的 元素  
    		i++;
    		li = li->next;
    	}
    	if (NULL == li || position > i) {//超出链表范围，都遍历完链表还没找到元素。
    		return ERROR;
    	}
    	//通上面 while循环 当i = position 跳出循环 ，li 此时指向链表 第position位置的 前面一个结点。
    	*e = li->next->data;
    	return OK;
    }
    //往链表中第position位置 插入元素，元素数据为 e
    //元素位置从1开始数
    Status insertLinkList(LinkList *list,int position,EleType e) {
    	Node *node = (Node*)malloc(sizeof(Node));
    	//异常情况：空指针，为插入元素分配空间失败，元素位置非法，
    	if (NULL == list || NULL==node || position < 1) {
    		return ERROR;
    	}
    	LinkList li = * list;
    	int i = 1;
    	while ( li && i<position) {//在链表范围内遍历元素 直到 找到第position位置的 元素  
    		i++;
    		li = li->next;
    	}
    	if (NULL == li || position > i) {//超出链表范围
    		return ERROR;
    	}
    	//通上面 while循环 当i = position 跳出循环 ，li 此时指向链表 第position位置的 前面一个结点。
    	node->data = e;
    	node->next = li->next;//让 插入结点指针域指向 原来位置的结点
    	li->next = node;//让插入结点位置前的结点 指向插入结点
    	return OK;
    }
    //在链表第position位置 删除元素，通过指针返回 删除元素的数据内容
    Status delLinkListEle(LinkList *list, int position, EleType *e) {
    	//异常情况：空指针,元素位置非法
    	if (NULL == list || position < 1) {
    		return ERROR;
    	}
    	LinkList li = *list;
    	Node * node = NULL;
    	int i = 1;
    	while (li && i<position) {//在链表范围内遍历元素 直到 找到第position位置的 元素  
    		i++;
    		li = li->next;
    	}
    	if (NULL == li || position > i) {//超出链表范围，都遍历完链表还没找到元素。
    		return ERROR;
    	}
    	//通上面 while循环 当i = position 跳出循环 ，li 此时指向链表 第position位置的 前面一个结点。
    	node = li->next;//保存要删除元素的地址
    	li->next = node->next;//让删除元素前置结点 指向 删除元素 直接后继结点。然后就可以释放 删除结点的空间了。
    	*e = node->data;//将删除元素数据通过指针修改返回
    	free(node);//释放删除元素空间
    	return OK;
    }
    //清空整个链表，释放指针指向的内存
    Status freeLinkList(LinkList *list) {
    	if (NULL == list)//空指针
    		return ERROR;
    	//注意：头结点不要释放！只释放头结点后面的结点元素
    	//LinkList li = *list;这样将会把头结点也释放掉
    	LinkList li = (*list)->next;//将链表指针指向第一个结点元素，从这个元素开始释放
    	Node * node = NULL;//临时变量，指向还未释放的元素
    	while (li){//链表指针向移动指向结点元素，直到没有后继结点
    		node = li->next;//保存要释放结点 的直接后继结点位置。 
    		free(li);
    		li = node;//继续指向 未释放结点
    	}
    	//将头结点指针域设置为NULL
    	(*list)->next = NULL;
    	return OK;
    }
    int main(void) {
    
    	LinkList linkList;
    	EleType e;
    	printf("头插法创建链表结构：\n");
    	creatLinkListInHead(&linkList, 4);
    	printLinkList(&linkList);
    
    	//先释放 然后再用尾插法
    	freeLinkList(&linkList);
    	printf("尾插法创建链表结构：\n");
    	creatLinkListInTail(&linkList, 4);
    	printLinkList(&linkList);
    
    	printf("第%d个位置插入%d：\n",5,100);
    	//插入元素
    	insertLinkList(&linkList, 5, 100);//往链表尾结点后面插入元素
    	printLinkList(&linkList);
    	printf("第%d个位置插入%d：\n", 3, 103);
    	//插入元素
    	insertLinkList(&linkList, 3, 103);//链表中间插入元素
    	printLinkList(&linkList);
    	//获取元素
    	getELement(linkList, 4, &e);
    	printf("第%d个位置元素：%d\n", 4,e);
    
    	//删除元素
    	delLinkListEle(&linkList, 5, &e);
    	printf("第%d个位置删除：%d\n", 5, e);
    	printLinkList(&linkList);
    
    	
    	//删除元素
    	delLinkListEle(&linkList, 1, &e);
    	printf("第%d个位置删除：%d\n", 1,e);
    	printLinkList(&linkList);
    
    	//释放整个表
    	freeLinkList(&linkList);
    	system("pause");
    	return 0;
    }

结果验证截图：

![Center][]

[Center]: /images/20220603/d01bf2c3196e4bcb949ffcdd575ba1e1.png