【数据结构与算法】单链表的查找和建立

喜欢ヅ旅行 2024-04-26 02:18 39阅读 0赞

> ? 本文由 [程序喵正在路上][Link 1] 原创，CSDN首发！  
> ? 系列专栏：[数据结构与算法][Link 2]  
> ? 首发时间：2022年9月22日  
> ? 欢迎关注?点赞?收藏?留言?  
> ? 一以贯之的努力 不得懈怠的人生

#### 阅读指南 ####

*  单链表的查找
 *   *  按位查找
     *  按值查找
 *  单链表的建立
 *   *  尾插法
     *  头插法建立单链表

## 单链表的查找 ##

其实在单链表的插入和删除中，我们已经使用过单链表的查找方法，因为插入和删除的前提都是先找到对应的结点，所以这里就不再多解释

### 按位查找 ###

`GetElem(L, i)`：按位查找操作。获取表 **L** 中第 **i** 个位置的元素的值

//按位查找
    LNode * GetElem(LinkList L, int i) {
        
    	if (i < 0) return false;
    
    	LNode *p;		//指针p指向当前扫描到的结点
    	int j = 0;		//当前p指向的是第几个结点
    	p = L;			//L指向头结点，头结点是第 0 个结点
    
    	//循环找到第 i-1 个结点
    	while (p != NULL && j < i) {
        
    		p = p->next;
    		j++;
    	}
    	return p;
    }

### 按值查找 ###

`LocateElem(L, e)`：按值查找操作。在表 **L** 中查找具有给定关键字值的元素

//按值查找
    LNode * LocateElem(LinkList L, ElemType e) {
        
    	LNode *p = L->next;
    	//从第1个结点开始查找数据域为e的结点
    	while (p && p->data != e) {
        
    		p = p->next;
    	}
    	return p;

## 单链表的建立 ##

如果给你很多个数据元素（**ElemType**），要把它们存到一个单链表里面，怎么操作呢？

第一步：初始化一个单链表  
第二步：每次取一个数据元素，插入到表尾/表头

### 尾插法 ###

算法步骤：

1.  创建一个只有头结点的空链表
2.  尾指针 r 初始化，指向头结点
3.  接收用户输入的值，判断是否结束插入，不结束则插入表中  
    创建新结点 \*s  
    将用户输入的值赋给新节点 \*s 的数据域  
    将新节点 \*s 插入到尾结点 \*r 之后  
    尾指针 r 指向新的尾结点 \*s  
    用户继续输入

//尾插法建立单链表
    LinkList List_TailInsert(LinkList &L) {
        
    	int x;		//假设ElemType为整型		
    	L = (LinkList)malloc(sizeof(LNode));	//建立头结点
    	LNode *s, *r = L;		//r为表尾指针
    	scanf("%d", &x);		//输入结点的值
    	while (x != 9999) {
        		//输入9999表示结束
    		s = (LNode *)malloc(sizeof(LNode));
    		s->data = x;
    		r->next = s;
    		r = s;				//r指向新的表尾结点
    		scanf("%d", &x);
    	}
    	r->next = NULL;		//尾结点指针置空
    	return L;
    }

### 头插法建立单链表 ###

算法步骤：

1.  创建一个只有头结点的空链表
2.  接收用户输入的值，判断是否结束插入，不结束则插入表中  
    创建新结点 \*s  
    将用户输入的值赋给新节点 \*s 的数据域  
    将新节点 \*s 插入到头结点之后  
    用户继续输入

//头插法建立单链表
    LinkList List_HeadInsert(LinkList &L) {
        
    	LNode *s;
    	int x;		//假设ElemType为整型		
    	L = (LinkList)malloc(sizeof(LNode));	//建立头结点
    	L->next = NULL;
    	scanf("%d", &x);		//输入结点的值
    	while (x != 9999) {
        		//输入9999表示结束
    		s = (LNode *)malloc(sizeof(LNode));
    		s->data = x;
    		s->next = L->next;
    		L->next = s;
    		scanf("%d", &x);
    	}
    	return L;
    }

记得 `L->next = NULL;` 这一句不能漏了，不然会出问题

[Link 1]: https://blog.csdn.net/weixin_62511863?spm=1011.2421.3001.5343
[Link 2]: https://blog.csdn.net/weixin_62511863/category_11984530.html?spm=1001.2014.3001.5482