线性表单链表实现基础操作和效果图

Myth丶恋晨 2022-11-25 10:11 185阅读 0赞

前言：

单链表这个结构，一定要理解链的意思，就是找到第一个才能找到第二个，不像数组，想知道哪个数据，直接用下标就出来了，链表不允许这样。强制性的必须知道第一个才能知道第二个，依次类推，这个想法要贯穿链表始终。

另外一个就是引入了指针这个概念，还有就是定义结构体的时候，看着代码会有点像递归，我写完后，试了试，其实就是递归，可以一直点下去；我上网搜索了一下，大概意思是有的编译器会处理这个问题，这个其实不要太在意，就当是指向下一个数据元素的地址就行了，不要钻牛角尖。

有什么不对的可以直接说出来，我会修改

代码是C语言写的，可以直接运行，效果就是下面的效果图，代码可以单独注释，然后看单独的效果，我是直接全部运行了。

代码看了一遍懂了，其实不算自己的，只有自己写出来了，经过自己思考了，才是自己的，并且写的过程中也会加深理解概念。

效果图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MjM0NDEw_size_16_color_FFFFFF_t_70][]

#include <stdio.h>
    #include <malloc.h>
    
    #define OK 1
    #define ERROR 0
    
    typedef int ElemType;
    
    typedef struct Link			//定义链表结点类型 
    {
    	ElemType data;			//数据域 
    	struct Link *next;		//指针域 
    }Link,*LinkList;
    
    /*头插法创建一个单链表*/
    LinkList HeadInitLink(Link *Lk)
    {
    	Link *link;
    	Lk = (LinkList)malloc(sizeof(Link));	//创建头结点
    	Lk->next=NULL;
    	int i = 1;
    	while(i<=10)
    	{
    		link = (LinkList)malloc(sizeof(Link));
    		link->data=i;
    		link->next=Lk->next;
    		Lk->next=link;
    		i++;
    	}
    	return Lk;
    } 
    
    /*采用尾插法创建单链表*/
    LinkList TailInitLink(Link *Lk)
    {
    	Lk = (LinkList)malloc(sizeof(Link));
    	Link *link,*Tail=Lk;
    	int i = 1;
    	while(i<=10)
    	{
    		link = (LinkList)malloc(sizeof(Link));
    		link->data=i;
    		Tail->next=link;			//link是一个地址 
    		Tail=link;					//link的地址给了Tail，然后就接着往下了，值并没改变 
    		i++;
    	}
    	Tail->next=NULL;
    	return Lk;
    }
    
    /*按序号查找结点*/
    LinkList GetLinkNode(Link *Lk,int i)
    {
    	Link *p = Lk->next;			//给头节点的指针，也就是给个地址，开始顺着地址查
    	if(i==0)
    		return Lk;
    	if(i<1)
    		return NULL;
    	int j = 1;
    	while(p && j<i)
    	{
    		p = p->next;
    		j++;	
    	}
    	return p;	
    } 
    
    /*按值查找表结点*/
    LinkList ValueElemType(Link *Lk,ElemType e)
    {
    	Link *p = Lk->next;				//取头结点指针域，开始查找
    	while(p!=NULL && p->data!=e)	//指针域不为空，且数据域的值和要找的值不一样，一样的话就找到了 
    		p=p->next;
    	return p;				 
    }
    
    /*求链表长度*/
    int LenghtLink(Link *Lk)
    {
    	Link *p=Lk->next;
    	int lenght = 0;
    	while(p)
    	{
    		p = p->next;
    		lenght++;
    	}
    	return lenght;
    }
    
    /*结点插入操作*/
    LinkList InsertLink(Link *Lk,int i,ElemType e)
    {
    	int lenght = LenghtLink(Lk);
    	if(i<1||i>lenght)						//判断插入位置是否合法 
    		return NULL;
    	Link *pl,*p=Lk;
    	pl = (LinkList)malloc(sizeof(Link));	//生成新结点
    	int j = 1;
    	while(j<i)
    	{
    		p = p->next;						//在要插入新结点之前；根据指针域地址不断地找 
    		j++;
    	}
    	pl->data=e;
    	pl->next=p->next;
    	p->next=pl;
    	return Lk; 
    }
    
    
    
    /*结点删除操作*/
    LinkList DeleteLink(Link *Lk,int i)
    {
    	int lenght = LenghtLink(Lk);
    	if(i<1||i>lenght)				//判断删除位置是否合法 
    		return NULL;
    	Link *dp,*p = Lk;
    	int j = 1;
    	while(j < i)
    	{
    		p = p->next;
    		j++;
    	}
    	dp = p->next;					//p->next就是要删除结点的后继结点，很重要 
    	p->next=dp->next;
    	free(dp);						//free(C语言标准函数库)
    	return Lk;
    }
    
    int main(void)
    {
    	Link *Headlink,*Taillink,*Insertlink,*Deletelink,HeadLk,TailLk,InsertLk,DeleteLk;
    	Headlink = HeadInitLink(&HeadLk);
    	Headlink = Headlink->next;
    	printf("头插法实现单链表\n");
    	while(Headlink)
    	{
    		printf("链表数据域的值为：%d 链表指针域的值为：%p\n",Headlink->data,Headlink->next);
    		Headlink=Headlink->next;
    	}
    	printf("\n");
    	
    	Taillink = TailInitLink(&TailLk);
    	//按序号查找结点值
    	printf("按序号查找结点值\n");
    	int address = 6; 
    	LinkList p = GetLinkNode(Taillink,address);
    	printf("第 %d 个结点数据域的值为：%d；指针域的值为：%p\n",address,p->data,p->next);
    	printf("\n");
    	
    	printf("尾插法实现单链表\n");
    	Taillink = Taillink->next;
    	while(Taillink)
    	{
    		printf("链表数据域的值为：%d 链表指针域的值为：%p\n",Taillink->data,Taillink->next);
    		Taillink=Taillink->next;
    	}
    	printf("\n");
    	
    	
    	//在第6个结点位置插入一个新结点
    	printf("在第6个结点位置插入一个新结点\n\n");
    	int No = 666;
    	Insertlink = TailInitLink(&InsertLk);
    	Insertlink = InsertLink(Insertlink,address,No);
    	Insertlink = Insertlink->next;
    	while(Insertlink)
    	{
    		printf("新插入结点的链表数据域的值为：%d 指针域的值为：%p\n",Insertlink->data,Insertlink->next);
    		Insertlink=Insertlink->next;
    	}
    	printf("\n");
    	
    	//删除第6个结点
    	printf("删除第6个结点\n\n");
    	Deletelink = TailInitLink(&DeleteLk);
    	int DeleteBefore = LenghtLink(Deletelink);
    	printf("删除结点前链表长度：%d\n",DeleteBefore);
    	Deletelink = DeleteLink(Deletelink,address);
    	int DeleteAfter = LenghtLink(Deletelink);
    	printf("删除结点后链表长度：%d\n",DeleteAfter);
    	Deletelink = Deletelink->next;
    	while(Deletelink)
    	{
    		printf("删除结点后的链表数据域的值为：%d 指针域的值为：%p\n",Deletelink->data,Deletelink->next);
    		Deletelink=Deletelink->next;
    	}
    	printf("\n");
    
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MjM0NDEw_size_16_color_FFFFFF_t_70]: /images/20221124/e18f2960de3e43a8a73bc49ce71a0eca.png