数据结构（C语言版）代码实现（三）——单链表部分代码实现

目录

格式

头文件

宏定义

线性表的单链表存储结构

按位查找

插入元素

删除元素

头插法建立单链表

合并非递减单链表

其他基本操作

完整版

测试代码（主函数）

测试结果

---

格式

参考 2.3节 线性表的链式表示和实现

头文件

宏定义

#pragma once
#include <cstdio>
#include <cstdlib>
#include <cstring>

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;//Status是函数的类型，其值是函数结果状态代码
typedef int ElemType;

线性表的单链表存储结构

//-----线性表的单链表存储结构-----
typedef struct LNode {
	ElemType data;
	struct LNode* next;
}LNode,*LinkList;

按位查找

//算法2.8 函数GetElem在单链表中的实现。
Status GetElem_L(LinkList L, int i, ElemType& e) {
	//L为带头结点的单链表的头指针。
	//当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR
	LinkList p = L->next;int j = 1;//初始化，p指向第一个结点，j为计数器
	while (p && j < i) {//顺指针向后查找，直到p指向第i个元素或p为空
		p = p->next;
		++j;
	}
	if (!p || j > i)
		return ERROR;//第i个元素不存在
	e = p->data;//取第i个元素
	return OK;
}

插入元素

//算法2.9 函数ListInsert在单链表中的实现
Status ListInsert_L(LinkList& L, int i, ElemType e) {
	//在带头结点的单链线性表L中第i个位置之前插入元素e
	LinkList p = L;int j = 0;
	while (p && j < i - 1) {
		p = p->next;
		++j;//寻找第i-1个结点
	}
	if (!p || j > i - 1)
		return ERROR;//i小于1或者大于表长+1
	LinkList s = (LinkList)malloc(sizeof(LNode));//生成新结点
	s->data = e;s->next = p->next;//插入L中
	p->next = s;
}

删除元素

//算法2.10 函数ListDelete在单链表中的实现
Status ListDelete_L(LinkList& L, int i, ElemType& e) {
	//在带头结点的单链线性表L中，删除第i个元素，并由e返回其值
	LinkList p = L;int j = 0;
	while (p && j < i - 1) {
		p = p->next;
		++j;//寻找第i个结点,p->next所在的位置
	}
	if (!(p->next) || j > i - 1)
		return ERROR;//删除位置不合理
	LinkList q = p->next;p->next = q->next;//删除并释放结点
	e = q->data;free(q);
	return OK;
}

头插法建立单链表

//算法2.11 头插法建立单链表
void CreateList_L(LinkList& L, int n) {
	//逆位序输入n个元素的值，建立带表头结点的单链线性表L。
	L = (LinkList)malloc(sizeof(LNode));
	L->next = NULL;//先建立一个带头结点的单链表
	LinkList p;
	for (int i = n;i > 0;i--) {
		p = (LinkList)malloc(sizeof(LNode));
		scanf_s("%d", &p->data);//输入元素值
		p->next = L->next;//插入到表头
		L->next = p;
		//插入到表尾
		// LinkList T=L;
		// for循环，用下面三行替换插入表头两行
		//p->next=NULL;
		//T->next=p;
		//T=p;
	}
}

合并非递减单链表

//算法2.12 合并非递减单链表
void MergeList_L(LinkList& La, LinkList& Lb, LinkList& Lc) {
	//已知顺序线性表La和Lb的元素按值非递减排列
	//归并La和Lb得到的新的顺序线性表Lc,Lc的元素也按值非递减排列
	LinkList pa = La->next;LinkList pb = Lb->next;
	LinkList pc = Lc = La;//用La的头结点作为Lc的头结点
	while (pa && pb) {
		if (pa->data <= pb->data) {
			pc->next = pa;
			pc = pa;
			pa = pa->next;
		}
		else {
			pc->next = pb;
			pc = pb;
			pb = pb->next;
		}
	}
	pc->next = pa ? pa : pb;//插入剩余段
	free(Lb);//释放Lb的头结点
}

free函数不能放在while循环内，否则会出现以下情况。

警告信息：使用未初始化的内存"Lb"。

看不懂，但这个问题解决了。

其他基本操作

void PrintList_L(LinkList L) {//打印链表
	LinkList p = L->next;
	while (p) {//while(p=p->next)这样写行吗？
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}

Status DestroyList_L(LinkList& L) {//销毁链表
	LinkList p;
	while (L) {
		p = L;
		L = L->next;
		free(p);//free函数的释放是只释放一个结点，还是释放后面相关的所有结点？--已解决，只释放一个结点。
	}
	return OK;
}

完整版

#pragma once
#include <cstdio>
#include <cstdlib>
#include <cstring>

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;//Status是函数的类型，其值是函数结果状态代码
typedef int ElemType;

//-----线性表的单链表存储结构-----
typedef struct LNode {
	ElemType data;
	struct LNode* next;
}LNode,*LinkList;

//算法2.11 头插法建立单链表
void CreateList_L(LinkList& L, int n) {
	//逆位序输入n个元素的值，建立带表头结点的单链线性表L。
	L = (LinkList)malloc(sizeof(LNode));
	L->next = NULL;//先建立一个带头结点的单链表
	LinkList p;
	for (int i = n;i > 0;i--) {
		p = (LinkList)malloc(sizeof(LNode));
		scanf_s("%d", &p->data);//输入元素值
		p->next = L->next;//插入到表头
		L->next = p;
		//插入到表尾
		// LinkList T=L;
		// for循环，用下面三行替换插入表头两行
		//p->next=NULL;
		//T->next=p;
		//T=p;
	}
}

//算法2.8 函数GetElem在单链表中的实现。
Status GetElem_L(LinkList L, int i, ElemType& e) {
	//L为带头结点的单链表的头指针。
	//当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR
	LinkList p = L->next;int j = 1;//初始化，p指向第一个结点，j为计数器
	while (p && j < i) {//顺指针向后查找，直到p指向第i个元素或p为空
		p = p->next;
		++j;
	}
	if (!p || j > i)
		return ERROR;//第i个元素不存在
	e = p->data;//取第i个元素
	return OK;
}

//算法2.9 函数ListInsert在单链表中的实现
Status ListInsert_L(LinkList& L, int i, ElemType e) {
	//在带头结点的单链线性表L中第i个位置之前插入元素e
	LinkList p = L;int j = 0;
	while (p && j < i - 1) {
		p = p->next;
		++j;//寻找第i-1个结点
	}
	if (!p || j > i - 1)
		return ERROR;//i小于1或者大于表长+1
	LinkList s = (LinkList)malloc(sizeof(LNode));//生成新结点
	s->data = e;s->next = p->next;//插入L中
	p->next = s;
}

//算法2.10 函数ListDelete在单链表中的实现
Status ListDelete_L(LinkList& L, int i, ElemType& e) {
	//在带头结点的单链线性表L中，删除第i个元素，并由e返回其值
	LinkList p = L;int j = 0;
	while (p && j < i - 1) {
		p = p->next;
		++j;//寻找第i个结点,p->next所在的位置
	}
	if (!(p->next) || j > i - 1)
		return ERROR;//删除位置不合理
	LinkList q = p->next;p->next = q->next;//删除并释放结点
	e = q->data;free(q);
	return OK;
}

//算法2.12 合并非递减单链表
void MergeList_L(LinkList& La, LinkList& Lb, LinkList& Lc) {
	//已知顺序线性表La和Lb的元素按值非递减排列
	//归并La和Lb得到的新的顺序线性表Lc,Lc的元素也按值非递减排列
	LinkList pa = La->next;LinkList pb = Lb->next;
	LinkList pc = Lc = La;//用La的头结点作为Lc的头结点
	while (pa && pb) {
		if (pa->data <= pb->data) {
			pc->next = pa;
			pc = pa;
			pa = pa->next;
		}
		else {
			pc->next = pb;
			pc = pb;
			pb = pb->next;
		}
	}
	pc->next = pa ? pa : pb;//插入剩余段
	free(Lb);//释放Lb的头结点
}

void PrintList_L(LinkList L) {//打印链表
	LinkList p = L->next;
	while (p) {//while(p=p->next)这样写行吗？
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}

Status DestroyList_L(LinkList& L) {//销毁链表
	LinkList p;
	while (L) {
		p = L;
		L = L->next;
		free(p);//free函数的释放是只释放一个结点，还是释放后面相关的所有结点？--已解决，只释放一个结点。
	}
	return OK;
}

测试代码（主函数）

#include "LinkList.h"

int main()
{
	LinkList La = NULL,Lb = NULL,Lc = NULL;
	int n1,n2;
	Status i = 0;
	ElemType e;//变量声明

	//测试算法2.11
	printf("请输入元素个数：");//构建单链表La
	scanf_s("%d", &n1);
	printf("请输入元素：");
	CreateList_L(La, n1);
	printf("\n");
	printf("头插法得到的元素逆序：");
	PrintList_L(La);

	//测试算法2.8
	i = GetElem_L(La, 3, e);
	if (i)
		printf("第3个元素为%d\n", e);
	else
		printf("第3个元素不存在\n");
	//测试算法2.9,2.10.
	i = ListInsert_L(La, 3, 3);
	if (i)
		printf("插入成功\n");
	else
		printf("插入失败\n");
	i = ListDelete_L(La, 5, e);
	if (i)
		printf("删除成功\n");
	else
		printf("删除失败\n");

	//测试算法2.12
	printf("请输入元素个数：");//构建单链表Lb
	scanf_s("%d", &n2);
	printf("请输入元素：");
	CreateList_L(Lb, n2);
	printf("\n");
	printf("头插法得到的元素逆序：");
	PrintList_L(Lb);

	MergeList_L(La, Lb, Lc);
	printf("新链表的元素：");
	PrintList_L(Lc);

	DestroyList_L(Lc);//因为Lc实质是La和Lb的合并，而且Lb的头结点已经被释放了。
	return 0;
}

测试结果