数据结构-单链表（C语言）

1.函数的声明和自定义

#pragma once
#include<stdio.h>
#include<stdlib.h>

typedef int ElemType;

typedef struct LNode {
	ElemType data;
	struct LNode* next;
}LinkNode;

#ifndef __LINKNODE_H__
#define __LINKNODE_H__
//菜单
void menu();

//整体创建链表头插法
void CreateListF(LinkNode*& L, ElemType a[], int n);

//整体创建链表尾插法
void CreateListR(LinkNode*& L, ElemType a[], int n);

//初始化
void InitList(LinkNode*& L);

//销毁
void DestroyList(LinkNode*& L);

//判断是否为空
bool ListEmpty(LinkNode* L);

//求链表长度
int ListLength(LinkNode* L);

//输出链表
void DispList(LinkNode* L);

//索引查找
bool GetElem(LinkNode* L, ElemType &e, int i);

//元素查找
int LocateElem(LinkNode* L, ElemType e);

//插入
bool ListInsert(LinkNode*& L, ElemType e, int i);

//删除
bool ListDelete(LinkNode*& L, ElemType& e, int i);
#endif // !__LINKNODE_H__

2.单链表的各函数操作

#define _CRT_SECURE_NO_WARNINGS 1
#include "linknode.h"

//菜单
void menu() {
	printf("*********************************************************\n");
	printf("*********1.插入                        2.删除************\n");
	printf("*********3.索引搜索                    4.元素搜索********\n");
	printf("*********5.输出表                      6.表长************\n");
	printf("*********0.退出                              ************\n");
	printf("*********************************************************\n");
}

//整体创建链表头插法
void CreateListF(LinkNode*& L, ElemType a[], int n) {
	LinkNode* s;
	L = (LinkNode*)malloc(sizeof(LinkNode));					//创建头结点
	L->next = NULL;
	for (int i = 0; i < n; i++) {
		s = (LinkNode*)malloc(sizeof(LinkNode));				//创建表中节点
		s->data = a[i];
		s->next = L->next;										//这一句就说明了是头插法
		L->next = s;											//头结点一直指向首节点
	}
}

//整体创建链表尾插法
void CreateListR(LinkNode*& L, ElemType a[], int n) {
	LinkNode* s;
	LinkNode* r;												//创建指针r一直指向尾节点（尾插法）
	L = (LinkNode*)malloc(sizeof(LinkNode));
	L->next = NULL;
	r = L;														//还未有元素时，尾节点就是头结点
	for (int i = 0; i < n; i++) {
		s = (LinkNode*)malloc(sizeof(LinkNode));				//创建表中节点
		s->data = a[i];
		r->next = s;
		r = s;													//指针r一直往后移指向新进来的尾节点
	}
	r->next = NULL;												//最后一个节点的next指针赋空
}

//初始化
void InitList(LinkNode*& L) {
	L = (LinkNode*)malloc(sizeof(LinkNode));					//开辟头结点空间
	L->next = NULL;
}

//销毁
void DestroyList(LinkNode*& L) {
	LinkNode* pre = L;								//从头结点逐一释放即可
	LinkNode* p = L->next;
	while (p != NULL) {
		free(pre);
		pre = p;
		p = pre->next;
	}
	free(pre);
}

//判断是否为空
bool ListEmpty(LinkNode* L) {
	return(L->next == NULL);
}

//求链表长度
int ListLength(LinkNode* L) {
	int count = 0;
	LinkNode* p = L;
	while (p->next != NULL) {						//为什么这里判断条件是p->!=NULL,销毁则是p!=NULL,因为这里指针p是从L开始，头结点是不算表的长度的，如要判断条件也为p!=NULL，那么指针p开始赋值为L->next即可
		count++;
		p = p->next;
	}
	return(count);
}

//输出链表
void DispList(LinkNode* L) {
	LinkNode* p = L->next;								//指向首节点
	printf("链表中的元素有：");
	while (p!= NULL) {									//遍历链表输出元素
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}

//索引查找
bool GetElem(LinkNode* L, ElemType& e, int i) {
	LinkNode* p = L;
	int j = 0;
	if (i < 1) {
		return false;
	}
	while (j < i && p != NULL) {
		j++;										//刚好j++到i-1的位置，完成逻辑-1
		p = p->next;								//此时指针p指向的就是第i个位置
	}
	if (p == NULL) {								//判断第i个位置是否有元素
		return false;
	}
	else {
		e = p->data;
		return true;
	}
}

//元素查找
int LocateElem(LinkNode* L, ElemType e) {
	LinkNode* p = L;
	int i = 0;
	while (p->data != e && p != NULL) {				//根据元素遍历链表，找出该元素的位置
		p = p->next;
		i++;
	}
	if (p == NULL) {								//遍历完都没找到就返回0
		return 0;
	}
	else {
		return (i);									//否则返回该元素位置
	}
}

//插入
bool ListInsert(LinkNode*& L, ElemType e, int i) {
	LinkNode* p;
	LinkNode* s;
	int j = 0;
	p = L;
	if (i <= 0) {
		return false;
	}
	while (j < i - 1 && p != NULL) {					//找到逻辑上第i-1位置的节点
		j++;
		p = p->next;
	}
	if (p == NULL) {									//判断第i-1位置的节点是否为空，空就错误(因为表是具备索引且按顺序的，没有i-1的节点，就无法插入第i个节点）
		return false;
	}
	else {
		s = (LinkNode*)malloc(sizeof(LinkNode));
		s->data = e;
		s->next = p->next;								//这是使用尾插法插入
		p->next = s;
		return true;
	}

}

//删除
bool ListDelete(LinkNode*& L, ElemType& e, int i) {
	int j = 0;
	LinkNode* p = L;
	LinkNode* s;
	if (i <= 0) {
		return false;
	}
	while (j < i - 1 && p != NULL) {					//同插入一样先找到逻辑上i-1位置上的节点
		j++;
		p = p->next;
	}
	if (p == NULL) {									//不存在i-1也就不存在i，返回错误
		return false;
	}
	else {
		s = p->next;									//让指针s指向p->next，也就是s指向第i个元素
		if (s == NULL) {								//判断是否存在第i个元素，不存在就返回错误
			return false;
		}
		e = s->data;									//这行操作可以用来告诉用户删除的元素值为多少
		p->next = s->next;								//让第i-1位置的节点指向第i+1位置的节点，将第i个节点从表中独立出来
		free(s);										//释放掉第i个节点空间
		return true;									//删除成功
	}
}

3.运行

#define _CRT_SECURE_NO_WARNINGS 1
#include "linknode.h"


int main() {
	LinkNode* L;
	ElemType e;
	int input = 0;
	int i = 0;
	int n = 0;

	InitList(L);

	do {
		menu();
		printf("请选择模式：");
		scanf("%d",&input);
		switch (input)
		{
		case 0:
			DestroyList(L);
			break;
		case 1:
			printf("请输入要插入的元素：");
			scanf("%d",&e);
			printf("请输入要插入的位置：");
			scanf("%d", &i);
			if (ListInsert(L, e, i)) {
				printf("插入成功\n");
			}
			else {
				printf("插入失败\n");
			}
			break;
		case 2:
			printf("请输入要删除元素的位置：");
			scanf("%d", &e);
			if (ListDelete(L, e, i)) {
				printf("删除成功,删除元素为：%d\n",e);
			}
			else {
				printf("删除失败\n");
			}
			break;
		case 3:
			printf("请输入要查找哪个位置的元素：");
			scanf("%d", &i);
			GetElem(L, e, i);
			printf("该位置的元素为：%d\n",e);
			break;
		case 4:
			printf("请输入要查找哪个元素的位置：");
			scanf("%d", &e);
			n = LocateElem(L, e);
			printf("该元素的位置为：%d\n", n);
			break;
		case 5:
			DispList(L);
			break;
		case  6:
			printf("该表表长为：%d\n", ListLength(L));
			break;
		default:
			break;
		}
	} while (input);
	return 0;
}

4.结果

插入

搜索

删除

退出