[数据结构与算法]数据结构 - 代码实现单链表的操作

首先，先建一个cpp文件，具体代码如下：

尾插法

LinkList List_TailInsert(LinkList &L) {
	int x;
	//L = (LinkList)malloc(sizeof(LNode));
	LNode *s, *r = L;
	scanf_s("%d", &x);
	while (x!=9999)	//输入9999表示结束
	{
		s = (LNode *)malloc(sizeof(LNode));
		s->data = x;
		r->next = s;
		r = s;
		scanf_s("%d", &x);
	}
	r->next = NULL;
	return L;
}

头插法

LinkList List_HeadInsert(LinkList &L) {		//与输入是逆向的
	int x;
	LNode *s;
	scanf_s("%d", &x);
	while (x!=9999)
	{
		s = (LNode *)malloc(sizeof(LNode));
		s->data = x;
		s->next = L->next;
		L->next = s;
		scanf_s("%d", &x);
	}
	return L;
}

按位查找，返回第i个元素

//按位查找，返回第i个元素
LNode * GetElem(LinkList L,int i) {
	
	LNode *p = L->next;
	int j = 1;
	if (i==0)
	{
		return L;
	}
	if (i<1)
	{
		return NULL;
	}
	while (p!=NULL && j<i)
	{
		p = p->next;
		j++;
	}
	return p;
}

在第i个位置插入新的结点

bool ListInsert(LinkList &L, int i, int e) {
	if (i<1)
	{
		return false;
	}
	LNode *p = GetElem(L, i - 1);
	if (p==NULL)
	{
		return false;
	}
	LNode *s = (LNode *)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;
}

删除第i个位置的结点

bool ListDelete(LinkList &L, int i, int &e) {
	if (i<1)
	{
		return false;
	}
	LNode *p = GetElem(L, i - 1);
	if (p == NULL) {
		return false;
	}
	if (p->next==NULL)
	{
		return false;
	}
	LNode *q = p->next;	//q指向被删除节点
	e = q->data;
	p->next = q->next;
	free(q);
	return true;
}

单链表的逆置

LinkList NiZhi(LinkList &L) {
	LinkList p, q;
	p = L->next;
	L->next = NULL;
	while (p!=NULL)
	{
		q = p;
		p = p->next;
		q->next = L->next;
		L->next = q;
	}
	return L;
}

单链表的逆置

LinkList NiZhi(LinkList &L) {
	LinkList p, q;
	p = L->next;
	L->next = NULL;
	while (p!=NULL)
	{
		q = p;
		p = p->next;
		q->next = L->next;
		L->next = q;
	}
	return L;
}

完整代码

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

typedef struct LNode {	//定义单链表结构点类型
	int data;	//每个节点存放一个数据元素
	struct LNode *next;	//指针指向下一个节点
}LNode,*LinkList;


//初始化一个单链表（带头节点）
bool InitList(LinkList &L) {
	L = (LNode *)malloc(sizeof(LNode));	//分配一个头节点
	if (L==NULL)	//内存不足，分配失败
	{
		return false;
	}
	L->next = NULL;
	return true;
}

//尾插法
LinkList List_TailInsert(LinkList &L) {
	int x;
	//L = (LinkList)malloc(sizeof(LNode));
	LNode *s, *r = L;
	scanf_s("%d", &x);
	while (x!=9999)	//输入9999表示结束
	{
		s = (LNode *)malloc(sizeof(LNode));
		s->data = x;
		r->next = s;
		r = s;
		scanf_s("%d", &x);
	}
	r->next = NULL;
	return L;
}

//头插法
LinkList List_HeadInsert(LinkList &L) {		//与输入是逆向的
	int x;
	LNode *s;
	scanf_s("%d", &x);
	while (x!=9999)
	{
		s = (LNode *)malloc(sizeof(LNode));
		s->data = x;
		s->next = L->next;
		L->next = s;
		scanf_s("%d", &x);
	}
	return L;
}

LinkList NiZhi(LinkList &L) {
	LinkList p, q;
	p = L->next;
	L->next = NULL;
	while (p!=NULL)
	{
		q = p;
		p = p->next;
		q->next = L->next;
		L->next = q;
	}
	return L;
}

//按位查找，返回第i个元素
LNode * GetElem(LinkList L,int i) {
	
	LNode *p = L->next;
	int j = 1;
	if (i==0)
	{
		return L;
	}
	if (i<1)
	{
		return NULL;
	}
	while (p!=NULL && j<i)
	{
		p = p->next;
		j++;
	}
	return p;
}

//插入
bool ListInsert(LinkList &L, int i, int e) {
	if (i<1)
	{
		return false;
	}
	LNode *p = GetElem(L, i - 1);
	if (p==NULL)
	{
		return false;
	}
	LNode *s = (LNode *)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;
}

bool ListDelete(LinkList &L, int i, int &e) {
	if (i<1)
	{
		return false;
	}
	LNode *p = GetElem(L, i - 1);
	if (p == NULL) {
		return false;
	}
	if (p->next==NULL)
	{
		return false;
	}
	LNode *q = p->next;	//q指向被删除节点
	e = q->data;
	p->next = q->next;
	free(q);
	return true;
}

//遍历打印单链表
void _printList(LinkList L) {
	while (L != NULL)
	{
		L = L->next;
		printf("%d ", L->data);
	}
}


int main() {
	LinkList L;
	InitList(L);
	//尾插法
	List_TailInsert(L);
	//头插法
	//List_HeadInsert(L);

	//逆置--类似头插法
	//NiZhi(L);

	//插入测试
	if (ListInsert(L,2,222))
	{
		printf("在2号位置插入222插入成功\n");
	}
	else
	{
		printf("插入失败\n");
	}


	//删除测试
	int temp = 0;//存放被删除数据
	if (ListDelete(L, 2, temp)) {
		printf("%d已被删除\n",temp);
	}
	else
	{
		printf("删除失败\n");
	}

	//打印
	_printList(L);

	return 0;
}