线性表 (C语言实现一个单链表) ------- 算法笔记001

╰半夏微凉° 2023-06-30 01:51 6阅读 0赞

单链表的综合运用

实现函数：  
1.一个链表的创建  
2.链表的插入删除  
3.查看链表总数与快慢指针实现快速查找链表的中间值

链表创建过程：

第一步：定义结构

typedef struct structBody/*结构体类名*/{ 
    	ElemType data;	// 定义你的结构体数据，ElemType是你自定义的数据类型如：typedef int ElemType
    	struct structBody *next;//定义指向下一个结构体的指针
    }Alias //别名

第二步：根据输入的数据动态生成一个链表

void CreateList(Alias **list){ 
    		if(!(*list)){ 
    			(*list)=(Alias *)malloc(sizeof(Alias));	
    			//判断二级指针地址的内容是否为空。这样做的好处是传的是指针的指针地址，就不需要返回指针类型了。
    		}
    		char ch;
    		Alias *p=(*list);
    		scanf("%c",&ch);
    		while(ch!='\0'){ 
    		//下面的这几步是固定操作，尾插法创建。
    			Alias * newlist=(Alias *)malloc(sizeof(Alias));
    			newlist->data=ch;
    			newlist->next=NULL;
    			p->next=newlist;
    			p=newList;
    			scanf("%c",&ch);
    		}
    		p=(*list);
    		(*list)=(*list)->next;//删除头结点
    		free(p);
    		
    }

链表的插入和删除原理：

插入原理：

> 有好几种插入的方法这里我们的插入函数的格式是，给定要插入的位置和数据，实现一个插入过程。  
> 那么就是一个寻找到指定位置的节点，比如说第二个节点。那我们找到第二个位置前的节点，然后进行改动next指针操作。步骤是将新节点的next指针指向指定位置的节点；然后将第二个位置前的节点next指针指向新节点。

删除原理：

> 就是不停的进行迭代操作，直到指针p指向了NULL,每次操作free掉一个节点。

void InsertList(Alias **list,ElemType data,unsigned int position){ 
    		Alias *newInsert=(Alias *)malloc(sizeof(Alias));
    		Alias *p=(*list);
    		newInsert->data=data;
    		position-=2;
    		while(position){ 
    			p=p->next;
    			position--;
    		}
    		if(p==(*list)){ 
    			//在第一个元素插入
    			newInsert->next=p;
    			(*list)=newInsert;
    		}else if(p->next=NULL){ 
    			return;
    		}else{ 
    			newInsert->next=p->next;
    			p->next=newInsert;
    		}
    	}
    //代码每个人有每个人的风格特点，但是思维是不变的，要按着思维写程序，不要纠结代码，我的代码也仅做参考。

void deleteList(Alias **list){ 
    	Alias *p=(*list);
    	while(p){ 
    		Alias *dellist=p;
    		p=p->next;
    		free(dellist);
     	}
    }

快慢指针查找中间节点：

> 思路就是定义一个快指针，每次循环走两个节点，一个慢指针，每次循环走一个节点，当快指针走到末尾时由于走的步数是一样的但慢指针走的是快指针的二分之一，所以慢指针这是=时也正好处于中间位置。

void findeMiddleNode(Alias **list){ 
    		Alias *fast=(*list);
    		Alias *slow=(*list);
    		while(fast->next->next){ 
    			fast=fast->next->next;
    			slow=slow->next;
    			if(fast->next==NULL)
    				break;
    	}
    	printf("\n");
    	printf("---------------查找中间数据-------------------\n"); 
    	if(fast->next){ 
    		printf("中间的数据是:%d或者%d",slow->data,slow->next->data);
    		return;
    	}
    	printf("中间的数据是:%d\n\n",slow->data);
    	}

源程序我上传到了我的资源上，是dev c++工程 有兴趣的可以下载具体研究一下，也挺有趣的。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MzkyNzMz_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MzkyNzMz_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200113233007763.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MzkyNzMz,size_16,color_FFFFFF,t_70