单链表的基本功能C实现(各个功能:初始化,插入,删除,遍历,查询等)

2021年9月30日 16点热度 0条评论 来源: qqcoming

1. 什么是链表?相比数组有哪些好处?

	单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。结点由数据和指针构成。
	单链表的结点的结构如下图:


同时单链表又分为带头结点和不带头结点的单链表,一般使用带头结点的单链表有利于各种操作:

2.单链表有哪些优点呢?

  1. 采用链式存储,逻辑相邻的元素不用保证物理存储也相邻,没有长度的限制。
  2. 插入和删除元素更方便,不需要移动大量元素。

3.单链表的基本操作
1.头插法建立链表

示例代码如下:

//头插法建立链表
LinkList  list_HeadInsert(LinkList& L,int arr[],int len) { 
	LNode* s; int x;
	L = (LinkList)malloc(sizeof(LNode));//创建头结点
	L->next = NULL; //初始为空链表
	int i = 0;
	while (i<len)
	{ 
		s = (LNode*)malloc(sizeof(LNode));//创建新结点
		s->data = arr[i++];
		s->next = L->next;
		L->next = s;	//将新节点插入表中,L为头指针;
	}
	arrayList(L);	// 利用指针遍历输出各结点的值
	return L;
}

2.尾插法建立单链表

代码如下:

//尾插法建立单链表
LinkList list_RailInsert(LinkList& L,int arr[],int len) { //正向建立单链表
	int i=0;
	L = (LinkList)malloc(sizeof(LNOde));//创建头结点
	LNOde* s, * r = L;//r表示尾指针
	L->next = NULL;
	
	while (i<len) { 
		s = (LNOde*)malloc(sizeof(LNOde));//建立一个新的节点
		s->data = arr[i++];
		r->next = s;
		r = s;
	}
	r->next = NULL;//尾指针置空;
	arrayList(L);
	return L;
}

3.按序号查找节点值

LNOde* getElem(LinkList L, int i) { 
	int k = 1;//用于记录节点数;
	LNOde* head = L->next;
	if (i == 0) { 	//i等于0,返回头结点;
		return L;
	}
	if (i < 1) { 
		return NULL;	//i无效则返回NULL;
	}
	while (head && k < i) { 
		head = head->next;
		k++;
	}
	return head;
}

4.按值查找节点

// 按值查找节点
LNOde* locateElem(LinkList L, int value) { 
	LNOde* first = L->next;
	while (first != NULL && first->data != value) { 
		first = first->next;
	}
	return first;
}

5.在指定位置插入节点

LinkList assignInsert(LinkList& L, int i, int x) { //i表示第i个位置
	LNOde* s; // 定义一个待插入的节点;
	LNOde* p = getElem(L, i - 1);//找到对应的i前驱节点;
	s = (LNOde*)malloc(sizeof(LNOde));
	s->data = x;![在这里插入图片描述](https://img-blog.csdnimg.cn/20200823192422675.png#pic_center)

	s->next = p->next;
	p->next = s;
	arrayList(L);
	return L;
}

6.删除指定的节点

LinkList deleteNode(LinkList& L, int i) { //i表示删除的第几个节点
	LNOde* s;
	LNOde* p = getElem(L, i - 1);//查找第i-1的节点;
	s = p->next;//表示要删除的当前节点;
	p->next = s->next;
	free(s);
	arrayList(L);
	return L;
}

7.指针显示输出链表

//指针显示输出链表
void arrayList(LinkList L) { 
	LNOde* first = L->next;//表示第一个元素
	while (first) { //直到链表为空结束
		printf("%d ", first->data);
		first = first->next;
	}
	printf("\n\n");
}

4.代码汇总,测试结果
当我们C实现单链表的基本操作,可以利用工程更方便的书写代码,把方法的声明和实现测试分别放在不同的文件里,提高写代码的效率,附上代码:
方法的声明:link.h

link.h		//link.h文件,主要用于声明数据类型,结构体类型,以及方法的定义等
#pragma once
typedef int ElemType;//定义数据的类型,方便更改
typedef struct LNOde//定义结点
{ 
	ElemType data;
	struct LNOde* next;
}LNode, * LinkList;//结点的重命名

LinkList  list_HeadInsert(LinkList& L,int arr[], int len);//头插法建立链表
LinkList list_RailInsert(LinkList& L, int arr[], int len);//尾插法建立单链表
LNOde* getElem(LinkList L, int i);//按序号查找节点值
LNOde* locateElem(LinkList L, int value);// 按值查找节点
LinkList assignInsert(LinkList& L, int i ,int x);//在指定位置插入节点 
LinkList deleteNode(LinkList& L, int i);//删除指定的节点
void arrayList(LinkList L);//指针显示输出链表

方法的具体实现:link.cpp

#include<stdlib.h>
#include<stdio.h>
#include"link.h"

//头插法建立链表
LinkList  list_HeadInsert(LinkList& L,int arr[],int len) { 
	LNode* s; int x;
	L = (LinkList)malloc(sizeof(LNode));//创建头结点
	L->next = NULL; //初始为空链表
	int i = 0;
	while (i<len)
	{ 
		s = (LNode*)malloc(sizeof(LNode));//创建新结点
		s->data = arr[i++];
		s->next = L->next;
		L->next = s;	//将新节点插入表中,L为头指针;
	}
	arrayList(L);
	return L;
}

//尾插法建立单链表
LinkList list_RailInsert(LinkList& L,int arr[],int len) { //正向建立单链表
	int i=0;
	L = (LinkList)malloc(sizeof(LNOde));//创建头结点
	LNOde* s, * r = L;//r表示尾指针
	L->next = NULL;
	
	while (i<len) { 
		s = (LNOde*)malloc(sizeof(LNOde));//建立一个新的节点
		s->data = arr[i++];
		r->next = s;
		r = s;
	}
	r->next = NULL;//尾指针置空;
	arrayList(L);
	return L;
}

//按序号查找节点值
LNOde* getElem(LinkList L, int i) { 
	int k = 1;//用于记录节点数;
	LNOde* head = L->next;
	if (i == 0) { 	//i等于0,返回头结点;
		return L;
	}
	if (i < 1) { 
		return NULL;	//i无效则返回NULL;
	}
	while (head && k < i) { 
		head = head->next;
		k++;
	}
	return head;
}

// 按值查找节点
LNOde* locateElem(LinkList L, int value) { 
	LNOde* first = L->next;
	while (first != NULL && first->data != value) { 
		first = first->next;
	}
	return first;
}

//在指定位置插入节点 
LinkList assignInsert(LinkList& L, int i, int x) { //i表示第i个位置
	LNOde* s; // 定义一个待插入的节点;
	LNOde* p = getElem(L, i - 1);//找到对应的i前驱节点;
	s = (LNOde*)malloc(sizeof(LNOde));
	s->data = x;
	s->next = p->next;
	p->next = s;
	arrayList(L);
	return L;
}

//删除指定的节点
LinkList deleteNode(LinkList& L, int i) { //i表示删除的第几个节点
	LNOde* s;
	LNOde* p = getElem(L, i - 1);//查找第i-1的节点;
	s = p->next;//表示要删除的当前节点;
	p->next = s->next;
	free(s);
	arrayList(L);
	return L;
}

//指针显示输出链表
void arrayList(LinkList L) { 
	LNOde* first = L->next;
	while (first) { 
		printf("%d ", first->data);
		first = first->next;
	}
	printf("\n\n");
}

测试代码:linkTest.cpp:

#include<stdio.h>
#include "link.h"
int main() { 
	LinkList link, link2, link3, link4;
	printf("输出头插法建立的单链表为: ");//显示输出链表
	int arr[] = { 1,2,3,4,5};
	int len = sizeof(arr) / sizeof(int);
	list_HeadInsert(link, arr, len);//头插法建立链表
	printf("输出尾插法建立的单链表为: ");//显示输出链表
	list_RailInsert(link2,arr,len);//尾插法建立单链表
	printf("输出查找序号为2的结点为:");
	printf("%d\n\n", getElem(link2, 2)->data);//按序号查找节点值
	locateElem(link2, 5);// 按值查找节点
	printf("在指定位置3插入元素6后的单链表为:");
	link3 = assignInsert(link2, 3,6);
	printf("输出删除指定位置3的结点元素后的单链表为:");
	link4 = deleteNode(link2, 3);//删除指定的节点
	
}

附上一张测试的结果:

    原文作者:qqcoming
    原文地址: https://blog.csdn.net/qq_45784913/article/details/108186308
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。