单链表基本操作代码实现【数据结构笔记】

本程序实现的单链表是带头结点的单链表，头结点相当于一个全局变量。
本程序利用了C++的模板功能。

1、指定位序插入
2、清空线性表
3、查询元素
4、指定位序删除
5、遍历
6、指定位序元素获取
7、线性表长度获取

LinkList.h

#define _CRT_SECURE_NO_WARNINGS

#include 
#include 
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
typedef int Status;

//模板
template
struct LinkNode 
{
	DataType data;
	struct LinkNode* next;
};

//线性表的头结点定义，不同于一般的数据节点，相当于是一个全局变量
template
struct LinkList
{
	LinkNode* head;	//L是头结点，head是头指针？
	int length;
};

//线性表的初始化操作
template
void InitList(LinkList &L)
{
	L.length = 0;
	L.head = NULL;
}

//线性表指定位序插入
template
Status ListInsert(LinkList &L,int i,DataType e)
{
	//合法性检验
	if (i > L.length + 1 || i < 0)
		return FALSE;

	//申请一个结点，并进行初始化设置
	LinkNode* p = new LinkNode;

	//内存分配失败
	if (!p) return FALSE;

	//初始化新结点
	p->next = NULL;
	p->data = e;

	if (i == 1)	//1位置进行特殊处理，即插入头结点之后
	{
		p->next = L.head;		//p指向首结点
		L.head = p;
	}
	else
	{
		//先找到第i-1个结点，然后再该位置插入
		LinkNode* q = L.head;
		for (int k = 0; k < i - 1; k++)
		{
			q = q->next;
		}
		p->next = q->next;
		q->next = p;
	}

	L.length++;
	return OK;
}

//线性表头位置插入，相当于在第一个位置插入
template
Status InsFirst(LinkList& L,DataType e)
{
	return ListInsert(L,1,e);
}

//线性表尾位置插入，相当于在最后一个位置插入
template
Status InsLast(LinkList& L,DataType e)
{
	return ListInsert(L,L.length+1,e);
}

//清空线性表
template
Status ClearList(LinkList& L)
{
	LinkNode* p = L.head;		//p指向头结点
	while (p)
	{
		L.head = p->next;
		delete p;				//释放结点空间
		p = L.head;
	}
	return OK;
}

//查询元素, compare为查询操作所用的比较操作
template
int LocateElem(LinkList& L, DataType e, 
						bool(*compare)(DataType, DataType))
{
	LinkNode* p = L.head;
	int k = 1;
	while (p)
	{
		if (*compare(p->data, e)) return k;
		k++;
		p = p->next;
	}
	return FALSE;
}

//删除指定位序元素
template
Status ListDelete(LinkList& L, int i, DataType& e)
{
	//i的合法性检验
	if (i < 0 || i > L.length)
		return FALSE;

	LinkNode* p = L.head;		//p指向第几个结点

	//第一个结点特殊处理
	if (i == 1)
	{
		L.head = p->next;
		e = p->data;		
		delete p;			//释放p指向的空间
	}
	else
	{
		//先找到要删除第i-1个结点
		for (int k = 0; k < i - 1; k++)
		{
			p = p->next;
		}//p指向第i - 1个结点

		LinkNode* q = p->next;	//q指向第i个结点
		p->next = q->next;
		delete q;
	}
	return OK;
}

//遍历线性表
template
void ListTraverse(LinkListL,void(*visit)(DataType e))
{
	LinkNode* p = L.head;
	while (p)
	{
		(*visit)(p->data);
		p = p->next;
	}
}

//获取指定位序元素
template
Status GetElem(LinkListL,int i,DataType &e)
{
	if (i < 1 || i > L.length)
		return FALSE;

	LinkNode* p = L.head;

	for (int k = 1; k < i; k++)
	{
		p = p->next;
	}

	e = p->data;
	
	return OK;
}


//获取线性表长度
template
int ListLength(LinkList L)
{
	return L.length;
}

main.cpp

//编程环境: vs 2019
#include "LinkList.h"
typedef struct Student 
{
	char sno[20];
	int G;
}Student;

char fileName[] = "stu.txt";

//定义学生信息结构体的比较函数
bool compare(Student e1, Student e2)
{
	if (e1.G == e2.G && strcmp(e1.sno, e2.sno))
		return true;
	return false;
}

//定义学生结构体的遍历操作，本实例程序中定义为简单的打印
void visit(Student e)
{
	printf("学号%s，成绩%d n",e.sno,e.G);
}

//从控制台中输入一个学生信息
bool readStudent(Student &e)
{
	printf("输入学生的学号和成绩信息，用空格隔开n");
	scanf("%s %d",e.sno,&e.G);
	getchar();
	return true;
}

//把学生信息存储到文件的操作
void savetoFile(LinkListL)
{
	Student e;
	FILE* f = fopen(fileName,"w");
	for (int k = 0; k < L.length; k++)
	{
		GetElem(L,k + 1,e);
		fprintf(f,"%s %dn",e.sno,e.G);
	}
	fclose(f);
}


int main()
{
	LinkList L;
	InitList(L);
	char command = 'n';
	bool out = false;
	char tmp[256];
	Student e;
	while (!out)
	{
		printf("save to file(s)n");
		printf("insert into List(i)n");
		printf("delete from List(d)n");
		printf("clear List(c)n");
		printf("print List(p)n");
		printf("exit system(e)n");
		gets_s(tmp);
		command = tmp[0];
		switch (command)
		{
		case 's':savetoFile(L); break;
		case 'i':readStudent(e);InsFirst(L,e); break;
		case 'd':ClearList(L); break;
		case 'c':ListDelete(L, 2, e); break;
		case 'p':ListTraverse(L,visit); break;
		case 'e':out = true; break;
		default:
			printf("error commandn");
			break;
		}
	}
	ClearList(L);

	return 0;
}