【数据结构】单链表的基本操作

飞熊 • 2024年2月4日下午10:11 • 技术随笔 • 阅读 192

以链式结构存储的线性表称为链表；
链式存储结构是用一组任意的存储单元来存储线性表的结点；

在链式存储结构中，存储单元可以是相邻的，也可以是不相邻的
相邻的存储单元中的数据不一定是相邻的结点

单链表的结点结构：结点之间的逻辑关系是由结点中的指针指示的（如图）

单链表的优缺点

单链表(链式存储)：每个结点除了存放数据元素外，还要存储指向下一个节点的指针

优点：不要求大片连续空间，改变容量方便
缺点：不可随机存取，要耗费一定空间存放指针

单链表的基本操作—头插法

代码部分

#include<stdio.h>
//定义结点
struct Node {
	int data; //数据域
	struct Node* next; //指针域
};

//初始化
struct Node * InitList() {
	struct Node *L = (struct Node*)malloc(sizeof(struct Node));
	L->next = NULL;
	printf("--->>>初始化成功\n");
	return L;
}

//输入数据
void InputList(struct Node *L) {
	while (1) {
		int data;
		struct Node* P = (struct Node*)malloc(sizeof(struct Node));
		printf("请输入数据(输入0结束)：");
		scanf_s("%d",&data);
		if (data == 0) {
			printf("--->>>输入结束\n");
			break;
		}
		P->data = data;
		P->next = L->next;
		L->next = P;
	}

}

//输出数据
void PrintList(struct Node *L) {
	struct Node* P;
	int i = 0;
	P = L->next;
	printf("--->>>链表内数据有：");
	while (P) {
		printf(" %d ",P->data);
		P = P->next;
		i++;
	}
	printf("\n--->>>输出完毕，共有%d个数据\n",i);
}

//插入数据
void insertList(struct Node *L) {
	int i = 0,loc, data;
	struct Node* P;
	struct Node* S = (struct Node *)malloc(sizeof(struct Node));
	P = L;
	printf("--->>>请输入插入位置(从0开始)：");
	scanf_s("%d",&loc);
	printf("--->>>请输入插入数据：");
	scanf_s("%d",&data);
	while (i<loc) {
		P = P->next;
		i++;
	}
	S->data = data;
	S->next = P->next;
	P->next = S;
	PrintList(L);
}

//删除数据
void DelList(struct Node * L) {
	int i = 0, loc;
	struct Node* P,*delNode;
	PrintList(L);
	printf("\n请输入要删除数据的位置(从1开始):");
	scanf_s("%d",&loc);
	
	if (loc == 1) {//删除头结点
		P = L->next;
		L->next = P->next;
		free(P);
	}else {//删除其他结点
		P = L;
		while (i<loc - 1) {
			P = P->next;
			i++;
		}
		delNode = P->next;
		P->next = delNode->next;
		free(delNode);
		printf("--->>>删除成功\n");
	}
	PrintList(L);
}

void main() {
	struct Node * L = InitList();
	InputList(L);
	PrintList(L);
	insertList(L);
	DelList(L);
}

运行结果如下：

补充：

单链表的基本操作—尾插法
与头插法恰好相反：每次输入数据从末尾插入

//尾插法输入数据
void InputNodeList(struct NodeList *L) {
	struct NodeList* P,*Q,*S;
	Q = (struct NodeList*)malloc(sizeof(struct NodeList));
	P = L;
	while (1) {
		int data;
		S = (struct NodeList*)malloc(sizeof(struct NodeList));
		printf("--->>>请输入数据(0结束):");
		scanf_s("%d", &data);
		while (P) {
			Q = P;
			P = P->next;
		}
		if (data == 0) {
			printf("\n--->>输入完成\n");
			break;
		}
		S->data = data;
		S->next = NULL;
		Q->next = S;
		P = S;
	}
}