1. Toy模板网首页
  2. > Toy博客

第 2 章 线性表 （线性表的单链表存储结构实现）

10月前 作者：moyebai 分类：Toy博客 阅读(28) 违法举报

这篇具有很好参考价值的文章主要介绍了第 2 章 线性表 （线性表的单链表存储结构实现）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1. 背景说明

第 2 章 线性表 （线性表的单链表存储结构实现）,# 数据结构（C语言版）,算法,c语言,数据结构第 2 章 线性表 （线性表的单链表存储结构实现）,# 数据结构（C语言版）,算法,c语言,数据结构

 第 2 章 线性表 （线性表的单链表存储结构实现）,# 数据结构（C语言版）,算法,c语言,数据结构

2. 示例代码 

1) status.h

/* DataStructure 预定义常量和类型头文件 */
#include <string.h>

#ifndef STATUS_H
#define STATUS_H

#define NONE ""

#define FILE_NAME(X) strrchr(X, '\\') ? strrchr(X,'\\') + 1 : X

#define DEBUG

#ifdef DEBUG
#define CHECK_NULL(pointer) if (!(pointer)) { \
		printf("\nFileName: %-25s FuncName: %-20s Line: %-10d ErrorCode: %-3d\n", FILE_NAME(__FILE__), __func__, __LINE__, ERR_NULL_PTR); \
		return NULL; \
	}
#else
#define CHECK_NULL(pointer)
#endif

#ifdef DEBUG
#define CHECK_VALUE(value, ERR_CODE) if (!(value)) { \
		printf("\nFileName: %-25s FuncName: %-20s Line: %-10d ErrorCode: %-3d\n", FILE_NAME(__FILE__), __func__, __LINE__, ERR_CODE); \
		return FALSE; \
	}
#else
#define CHECK_VALUE(value, ERR_CODE)
#endif

#ifdef DEBUG
#define CHECK_RET(ret, FORMAT, ...) if (ret != RET_OK) { \
		printf("\nFileName: %-25s FuncName: %-20s Line: %-10d ErrorCode: %-3d" FORMAT "\n", FILE_NAME(__FILE__), __func__, __LINE__, ret, ##__VA_ARGS__); \
		return ret; \
	}
#else
#define CHECK_RET(ret, FORMAT, ...)
#endif

#ifdef DEBUG
#define CHECK_CONDITION(condition, ERR_CODE, FORMAT, ...) if (condition) { \
		printf("\nFileName: %-25s FuncName: %-20s Line: %-10d ErrorCode: %-3d" FORMAT "\n", FILE_NAME(__FILE__), __func__, __LINE__, ERR_CODE, ##__VA_ARGS__); \
		return ERR_CODE; \
	}
#else
#define CHECK_CONDITION(condition, ERR_CODE, FORMAT, ...)
#endif

/* 函数结果状态码 */
#define TRUE 					1			/* 返回值为真 */
#define FALSE 					0			/* 返回值为假 */
#define RET_OK 					0			/* 返回值正确 */
#define ERR_NULL_PTR   			2			/* 空指针错误 */
#define ERR_MEMORY_ACCESS		3			/* 访问内存错 */
#define ERR_MEMORY_ALLOCATE		4			/* 内存分配错 */
#define ERR_NULL_STACK			5			/* 栈元素为空 */
#define ERR_PARA				6			/* 函数参数错 */
#define ERR_OPEN_FILE			7			/* 打开文件错 */
#define ERR_NULL_QUEUE			8			/* 队列为空错 */
#define ERR_FULL_QUEUE			9			/* 队列为满错 */
#define ERR_NOT_FOUND			10			/* 表项不存在 */
typedef int Status;							/* Status 是函数的类型,其值是函数结果状态代码，如 RET_OK 等 */
typedef int Bollean;						/* Boolean 是布尔类型,其值是 TRUE 或 FALSE */

#endif // !STATUS_H

2) singleLinkList.h

/* 线性表的单链表存储结构头文件 */

#ifndef SINGLELINKLIST_H
#define SINGLELINKLIST_H

#include "status.h"

typedef int ElemType;

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

Status InitList(LinkList *list);
Status DestroyList(LinkList *list);
Status ClearList(const LinkList list);
Status ListEmpty(const LinkList list, Bollean *isEmpty);
Status ListLength(const LinkList list, int *num);
Status GetElem(int i, const LinkList list, ElemType *e);
Status LocateElem(ElemType e, Bollean(*compare)(ElemType, ElemType), const LinkList list, int *pos);
Status PriorElem(ElemType cur_e, Bollean(*equal)(ElemType, ElemType), const LinkList list, ElemType *pre_e);
Status NextElem(ElemType cur_e, Bollean(*equal)(ElemType, ElemType), const LinkList list, ElemType *next_e);
Status ListInsert(int i, ElemType e, LinkList list);
Status ListDelete(int i, ElemType *e, LinkList list);
Status ListTraverse(void(*vi)(ElemType), LinkList list);
Status InsertAscend(ElemType e, int(*compare)(ElemType, ElemType), const LinkList list);
Status InsertDescend(ElemType e, int(*compare)(ElemType, ElemType), const LinkList list);
Status HeadInsert(ElemType e, const LinkList list);
Status EndInsert(ElemType e, LinkList list);
Status DeleteFirst(ElemType *e, const LinkList list);
Status DeleteTail(ElemType *e, const LinkList list);
Status DeleteElem(ElemType e, Bollean *isDeleted, const LinkList list);
Status RePlaceElem(int i, ElemType e, LinkList list);
Status CreateSingleLinkList(int n, int(*compare)(ElemType, ElemType), Bollean isAscend, LinkList *list);
Status GetFirstElem(const LinkList list, ElemType *e);

#endif

3) singleLinkList.c

/* 线性表的单链表（带头结点）存储结构源文件实现 */

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

/*
	前置条件：无
	操作结果：辅助函数，创建一个新的节点
*/
static LinkList MakeNewLNode(ElemType e)
{
	LinkList newLNode = (LinkList)malloc(sizeof(struct LNode));
	CHECK_NULL(newLNode);
	newLNode->data = e;
	newLNode->next = NULL;

	return newLNode;
}

/*
	前置条件：list 非空
	操作结果：构造一个空的线性表 *list
*/
Status InitList(LinkList *list)
{
	CHECK_CONDITION(!list, ERR_NULL_PTR, NONE);
	*list = (LinkList)malloc(sizeof(struct LNode));
	CHECK_CONDITION(!(*list), ERR_MEMORY_ALLOCATE, NONE);
	(*list)->next = NULL;

	return RET_OK;
}

/*
	前置条件：线性表 *list 已存在
	操作结果：销毁线性表 *list
*/
Status DestroyList(LinkList *list)
{
	CHECK_CONDITION(!list, ERR_NULL_PTR, NONE);
	LinkList p;
	while (*list) {
		p = (*list)->next;
		free(*list);
		*list = p;
	}

	return RET_OK;
}

/*
	前置条件：线性表 list 已存在
	操作结果：将 list 重置为空表
*/
Status ClearList(const LinkList list)
{
	CHECK_CONDITION(!list, ERR_NULL_PTR, NONE);
	LinkList p, q;
	p = list->next;
	while (p) {
		q = p->next;
		free(p);
		p = q;
	}

	list->next = NULL;

	return RET_OK;
}

/*
	前置条件：线性表 list 已存在
	操作结果：若 list 为空表，则用 *isEmpty 返回 TRUE，否则用 *isEmpty 返回 FALSE
*/
Status ListEmpty(const LinkList list, Bollean *isEmpty)
{
	CHECK_CONDITION(!list || !isEmpty, ERR_NULL_PTR, "list = %p, isEmpty = %p",
		list, isEmpty);
	*isEmpty = (list->next == NULL) ? TRUE : FALSE;

	return RET_OK;
}

/*
	前置条件：线性表 list 已存在
	操作结果：用 *num 返回 list 中数据元素个数
*/
Status ListLength(const LinkList list, int *num)
{
	CHECK_CONDITION(!list || !num, ERR_NULL_PTR, "list = %p, num = %p", list, num);
	*num = 0;
	LinkList p = list->next;
	while (p) {
		++(*num);
		p = p->next;
	}

	return RET_OK;
}

/*
	算法 2.8
	前置条件：list 为带头结点的单链表的头指针
	操作结果：当第 i 个元素存在时, 其值赋给 *e 并返回 RET_OK,否则返回 ERROR
*/
Status GetElem(int i, const LinkList list, ElemType *e)
{
	CHECK_CONDITION(!list || !e, ERR_NULL_PTR, "list = %p, e = %p", list, e);
	int j = 1;
	LinkList p = list->next;
	while (p && (j < i)) {
		p = p->next;
		++j;
	}

	/* j > i 适用于 i < 1 时，如 i = 0 */
	CHECK_CONDITION(!p || (j > i), ERR_PARA, "p = %p, j = %d, i = %d", p, j, i);
	*e = p->data;

	return RET_OK;
}

/*
	前置条件：线性表 list 已存在, compare() 是数据元素判定函数(满足为 1,否则为 0)
	操作结果：用 *pos 返回 list 中第 1 个与 e 满足关系 compare() 的数据元素的位序,
	若这样的数据元素不存在,则用 *pos 返回值为 0
*/
Status LocateElem(ElemType e, Bollean(*compare)(ElemType, ElemType), const LinkList list, int *pos)
{
	CHECK_CONDITION(!compare || !list || !pos, ERR_NULL_PTR, "compare = %p, list = %p, post = %p",
		compare, list, pos);
	int i = 1;
	LinkList p = list->next;
	while (p) {
		if (compare(p->data, e)) {
			*pos = i;
			return RET_OK;
		}

		p = p->next;
		++i;
	}

	*pos = 0;

	return RET_OK;
}

/*
	前置条件：线性表 list 已存在
	操作结果：若 cur_e 是 list 的数据元素,且不是第一个,则用 *pre_e 返回它的前驱,
	函数返回 RET_OK; 否则操作失败, *pre_e 无定义
*/
Status PriorElem(ElemType cur_e, Bollean(*equal)(ElemType, ElemType), const LinkList list, ElemType *pre_e)
{
	CHECK_CONDITION(!list || !pre_e, ERR_NULL_PTR, "list = %p, pre_e = %p", list, pre_e);
	LinkList p = list->next;
	while (p->next) {
		if (equal(p->next->data, cur_e)) {
			*pre_e = p->data;
			return RET_OK;
		}

		p = p->next;
	}

	return ERR_NOT_FOUND;
}

/*
	前置条件：线性表 list 已存在
	操作结果：若 cur_e 是 list 的数据元素，且不是最后一个，则用 next_e 返回它的后继，
	函数返回 RET_OK; 否则操作失败，next_e无定义，返回 INFEASIBLE
*/
Status NextElem(ElemType cur_e, Bollean(*equal)(ElemType, ElemType), const LinkList list, ElemType *next_e)
{
	CHECK_CONDITION(!list || !next_e, ERR_NULL_PTR, "list = %p, next_e = %p", list, next_e);
	LinkList p = list->next;
	while (p->next) {
		if (equal(p->data, cur_e)) {
			*next_e = p->next->data;
			return RET_OK;
		}

		p = p->next;
	}

	return ERR_NOT_FOUND;
}

/*
	算法 2.9
	前置条件：线性表 list 已存在
	操作结果：在带头结点的单链线性表 list 中第 i 个位置之前插入元素 e
*/
Status ListInsert(int i, ElemType e, LinkList list)
{
	CHECK_CONDITION(!list, ERR_NULL_PTR, NONE);
	int j = 0;
	while (list && (j < i - 1)) {
		++j;
		list = list->next;
	}

	CHECK_CONDITION((!list || (j > i - 1)), ERR_PARA, "list = %p, j = %d, i - 1 = %d",
		list, j, i - 1);
	LinkList newLNode = MakeNewLNode(e);
	CHECK_CONDITION(!newLNode, ERR_MEMORY_ALLOCATE, NONE);
	newLNode->next = list->next;
	list->next = newLNode;

	return RET_OK;
}

/*
	算法 2.10
	前置条件：线性表 list 已存在
	操作结果：在带头结点的单链线性表 list 中，删除第 i 个元素,并由 *e 返回其值
*/
Status ListDelete(int i, ElemType *e, LinkList list)
{
	CHECK_CONDITION(!e || !list, ERR_NULL_PTR, "e = %p, list = %p", e, list);
	int j = 0;
	while ((list->next) && (j < i - 1)) {
		++j;
		list = list->next;
	}

	CHECK_CONDITION((!(list->next) || (j > i - 1)), ERR_PARA, "list->next = %p, j = %d, i - 1 = %d",
		list->next, j, i - 1);
	LinkList p = list->next;
	*e = p->data;
	list->next = p->next;
	free(p);

	return RET_OK;
}

/*
	前置条件：线性表 list 已存在
	操作结果：依次对 list 的每个数据元素调用函数 vi()。一旦 vi() 失败,则操作失败
*/
Status ListTraverse(void(*vi)(ElemType), LinkList list)
{
	CHECK_CONDITION(!vi || !list, ERR_NULL_PTR, "vi = %p, list = %p", vi, list);
	while (list->next) {
		vi(list->next->data);
		list = list->next;
	}

	return RET_OK;
}

/*
	前置条件：线性表 list 已存在
	操作结果：按照升序或者降序获取元素插入位置
*/
static LinkList GetInsertPos(Bollean isAscend, int(*compare)(ElemType, ElemType), ElemType e, const LinkList list)
{
	LinkList q = list, p = list->next;
	if (isAscend) {
		while ((p) && (compare(e, p->data) > 0)) {
			q = p;
			p = p->next;
		}

		return q;
	}

	while ((p) && (compare(e, p->data) < 0)) {
		q = p;
		p = p->next;
	}
	
	return q;
}

/*
	前置条件：按非降序排列的线性表 list 已存在
	操作结果：在 list 中按非降序插入新的数据元素 e
*/
Status InsertAscend(ElemType e, int(*compare)(ElemType, ElemType), const LinkList list)
{
	CHECK_CONDITION(!list, ERR_NULL_PTR, NONE);
	LinkList q = GetInsertPos(TRUE, compare, e, list);
	LinkList s = MakeNewLNode(e);
	CHECK_CONDITION(!s, ERR_MEMORY_ALLOCATE, NONE);
	LinkList p = q->next;
	q->next = s;
	s->next = p;

	return RET_OK;
}

/*
	前置条件：按非升序排列的线性表 list 已存在
	操作结果：在 list 中按非升序插入新的数据元素 e
*/
Status InsertDescend(ElemType e, int(*compare)(ElemType, ElemType), const LinkList list)
{
	CHECK_CONDITION(!list, ERR_NULL_PTR, NONE);
	LinkList q = GetInsertPos(FALSE, compare, e, list);
	LinkList newLNode = MakeNewLNode(e);
	CHECK_CONDITION(!newLNode, ERR_MEMORY_ALLOCATE, NONE);
	LinkList p = q->next;
	q->next = newLNode;
	newLNode->next = p;

	return RET_OK;
}

/*
	前置条件：线性表 list 已存在
	操作结果：在 list 的头部插入新的数据元素 e, 作为链表的第一个元素
*/
Status HeadInsert(ElemType e, const LinkList list)
{
	CHECK_CONDITION(!list, ERR_NULL_PTR, NONE);
	LinkList newLNode = MakeNewLNode(e);
	CHECK_CONDITION(!newLNode, ERR_MEMORY_ALLOCATE, NONE);
	newLNode->next = list->next;
	list->next = newLNode;

	return RET_OK;
}

/*
	前置条件：线性表 list 已存在
	操作结果：在 list 的尾部插入新的数据元素 e, 作为链表的最后一个元素
*/
Status EndInsert(ElemType e, LinkList list)
{
	CHECK_CONDITION(!list, ERR_NULL_PTR, NONE);
	while (list->next) {
		list = list->next;
	}

	LinkList newLNode = MakeNewLNode(e);
	CHECK_CONDITION(!newLNode, ERR_MEMORY_ALLOCATE, NONE);
	list->next = newLNode;

	return RET_OK;
}

/*
	前置条件：线性表 list 已存在，且有不少于 1 个元素
	操作结果：删除 list 的第一个数据元素，并由 *e 返回其值
*/
Status DeleteFirst(ElemType *e, const LinkList list)
{
	CHECK_CONDITION(!e || !list, ERR_NULL_PTR, "e = %p, list = %p", e, list);
	CHECK_CONDITION(!(list->next), ERR_NOT_FOUND, NONE);
	*e = list->next->data;
	LinkList p = list->next;
	list->next = p->next;
	free(p);

	return RET_OK;
}

/*
	前置条件：线性表 list 已存在，且有不少于 1 个元素
	操作结果：删除 list 的最后一个数据元素，并用 *e 返回其值
*/
Status DeleteTail(ElemType *e, const LinkList list)
{
	CHECK_CONDITION(!e || !list, ERR_NULL_PTR, "e = %p, list = %p", e, list);
	CHECK_CONDITION(!(list->next), ERR_NOT_FOUND, NONE);
	LinkList p = list, q = NULL;
	while (p->next) {
		q = p;
		p = p->next;
	}

	q->next = NULL;
	*e = p->data;
	free(p);

	return RET_OK;
}

/*
	前置条件：线性表 list 已存在
	操作结果：删除表中值为 e 的元素，并用 *isDeleted 返回 TRUE；如无此元素，则用 *isDeleted 返回 FALSE
*/
Status DeleteElem(ElemType e, Bollean *isDeleted, const LinkList list)
{
	CHECK_CONDITION(!isDeleted || !list, ERR_NULL_PTR, "isDeleted = %p, list = %p",
		isDeleted, list);
	LinkList p = list, q = NULL;
	*isDeleted = FALSE;
	while (p) {
		q = p->next;
		if ((q) && (q->data == e)) {
			p->next = q->next;
			free(q);
			*isDeleted = TRUE;
			break;
		}

		p = q;
	}

	return RET_OK;
}

/*
	前置条件：线性表 list 已存在
	操作结果：用 e 取代表 list 中第 i 个元素的值
*/
Status RePlaceElem(int i, ElemType e, LinkList list)
{
	CHECK_CONDITION(!list, ERR_NULL_PTR, NONE);
	int j = 0;
	while ((list->next) && (j < i)) {
		++j;
		list = list->next;
	}

	CHECK_CONDITION(j != i, ERR_NOT_FOUND, "j = %d, i = %d", j, i);
	list->data = e;
	
	return RET_OK;
}

/*
	前置条件：list 非空
	操作结果：根据 isAscend 是否为 TRUE 建立 n 个元素的非降序（非升序）线性表
*/
Status CreateSingleLinkList(int n, int(*compare)(ElemType, ElemType), Bollean isAscend, LinkList *list)
{
	CHECK_CONDITION(!list, ERR_NULL_PTR, NONE);
	CHECK_CONDITION(n < 1, ERR_PARA, "n = %d", n);
	Status ret = InitList(list);
	CHECK_RET(ret, NONE);
	printf("Please input %d elements: ", n);
	ElemType e;
	scanf_s("%d", &e);
	LinkList newLNode = MakeNewLNode(e);
	CHECK_CONDITION(!newLNode, ERR_MEMORY_ALLOCATE, NONE);
	(*list)->next = newLNode;
	if (isAscend) {
		for (int i = 0; i < n - 1; ++i) {
			scanf_s("%d", &e);
			ret = InsertAscend(e, compare, *list);
			CHECK_RET(ret, NONE);
		}

		return RET_OK;
	}

	for (int i = 0; i < n - 1; ++i) {
		scanf_s("%d", &e);
		ret = InsertDescend(e, compare, *list);
		CHECK_RET(ret, NONE);
	}

	return RET_OK;
}

/*
	前置条件：线性表 list 已存在
	操作结果：返回表头元素的值
*/
Status GetFirstElem(const LinkList list, ElemType *e)
{
	CHECK_CONDITION(!list || !e, ERR_NULL_PTR, "list = %p, e = %p", list, e);
	CHECK_CONDITION(!(list->next), ERR_NOT_FOUND, "list->next = %p", list->next);
	*e = list->next->data;

	return RET_OK;
}

4) algorithm.h

/* 算法定义头文件 */
#ifndef ALGORITHM_H
#define ALGORITHM_H

#include "singleLinkList.h"

Status CreateListHead(int n, LinkList *list);
Status CreateListTail(int n, LinkList *list);
Status MergeList(const LinkList listA, int(*compare)(ElemType, ElemType), LinkList *listB, LinkList *listC);
Status Union(const LinkList listB, const LinkList listA);
Status MergeList2(const LinkList listA, const LinkList listB, int(*compare)(ElemType, ElemType), LinkList *listC);

#endif // !ALGORITHM_H

5) algorithm.c

/* 算法实现源文件 */
#include "algorithm.h"
#include "auxiliary.h"
#include <stdlib.h>
#include <stdio.h>

/*
	前置条件：list 非空
	操作结果：创建具有 n 个节点的线性表
*/
static Status CreateList(int n, Status (*Insert)(ElemType, LinkList), LinkList *list)
{
	Status ret = InitList(list);
	CHECK_RET(ret, NONE);
	printf("Please input %d integers: ", n);
	ElemType e;
	for (int i = 0; i < n; ++i) {
		scanf_s("%d", &e);
		ret = Insert(e, *list);
		CHECK_RET(ret, NONE);
	}

	return RET_OK;
}

/*
	算法 2.11
	前置条件：list 非空
	操作结果：逆位序(插在表头)输入 n 个元素的值，建立带表头结构的单链线性表 *list
*/
Status CreateListHead(int n, LinkList *list)
{
	CHECK_CONDITION(!list, ERR_NULL_PTR, NONE);
	CHECK_CONDITION(n < 1, ERR_PARA, "n = %d", n);
	Status ret = CreateList(n, HeadInsert, list);
	CHECK_RET(ret, "n = %d", n);

	return RET_OK;
}

/*
	前置条件：list 非空
	操作结果：正位序(插在表尾)输入 n 个元素的值，建立带表头结构的单链线性表 *list
*/
Status CreateListTail(int n, LinkList *list)
{
	CHECK_CONDITION(!list, ERR_NULL_PTR, NONE);
	CHECK_CONDITION(n < 1, ERR_PARA, "n = %d", n);
	Status ret = CreateList(n, EndInsert, list);
	CHECK_RET(ret, "n = %d", n);

	return RET_OK;
}

/*
	算法 2.12
	前置条件：已知单链线性表 listA 和 *listB 的元素按值非递减排列
	操作结果：归并 listA 和 *listB 得到新的单链线性表 *listC，*listC 的元素也按值非递减排列,
	此处需要将 *listB 头节点指针置空故需要传入 listB 指针变量
*/
Status MergeList(const LinkList listA, int(*compare)(ElemType, ElemType), LinkList *listB, LinkList *listC)
{
	CHECK_CONDITION(!listA || !compare || !listB || !listC, ERR_NULL_PTR, "listA = %p, compare = %p, listB = %p, listC = %p",
		listA, compare, listB, listC);
	LinkList pa = listA->next, pb = (*listB)->next, pc = NULL;
	*listC = pc = listA;
	while (pa && pb) {
		if (compare(pa->data, pb->data) <= 0) {
			pc->next = pa;
			pc = pa;
			pa = pa->next;
			continue;
		}

		pc->next = pb;
		pc = pb;
		pb = pb->next;
	}

	pc->next = pa ? pa : pb;
	free(*listB);
	*listB = NULL;

	return RET_OK;
}

/*
	算法 2.1
	前置条件：已知单链线性表 listA 和 *listB 的元素按值非递减排列
	操作结果：单链表实现，将所有在线性表 listB 中但不在 listA 中的数据元素插入到 listA 中
*/
Status Union(const LinkList listB, const LinkList listA)
{
	CHECK_CONDITION(!listB || !listA, ERR_NULL_PTR, "listB = %p, listA = %p",
		listB, listA);
	int listALength, listBLength;
	Status ret = ListLength(listA, &listALength);
	CHECK_RET(ret, NONE);
	ret = ListLength(listB, &listBLength);
	CHECK_RET(ret, NONE);
	ElemType e;
	int pos;
	for (int i = 1; i <= listBLength; ++i) {
		ret = GetElem(i, listB, &e);
		CHECK_RET(ret, "] = %d", i);
		ret = LocateElem(e, Equal, listA, &pos);
		CHECK_RET(ret, NONE);
		if (pos) {
			continue;
		}

		ret = ListInsert(++listALength, e, listA);
		CHECK_RET(ret, "listALength = %d", listALength);
	}

	return RET_OK;
}

/*
	算法 2.2
	前置条件：单链表实现，已知线性表 listA 和listB 中的数据元素按值非递减排列
	操作结果：归并 listA 和listB 得到新的线性表 listC, listC 的数据元素也按值非递减排列
*/
Status MergeList2(const LinkList listA, const LinkList listB, int(*compare)(ElemType, ElemType), LinkList *listC)
{
	CHECK_CONDITION(!listA || !listB || !compare || !listC, ERR_NULL_PTR, "listA = %p, listB = %p, compare = %p, listC = %p",
		listA, listB, compare, listC);
	Status ret = InitList(listC);
	CHECK_RET(ret, NONE);
	int listALength, listBLength;
	ret = ListLength(listA, &listALength);
	CHECK_RET(ret, NONE);
	ret = ListLength(listB, &listBLength);
	CHECK_RET(ret, NONE);
	int i = 1, j = 1, k = 0;
	ElemType ai, bj;
	while ((i <= listALength) && (j <= listBLength)) {
		ret = GetElem(i, listA, &ai);
		CHECK_RET(ret, "i = %d", i);
		ret = GetElem(j, listB, &bj);
		CHECK_RET(ret, "j = %d", j);
		if (compare(ai, bj) <= 0) {
			ret = ListInsert(++k, ai, *listC);
			CHECK_RET(ret, "k = %d, ai = %d", k, ai);
			++i;
			continue;
		}

		ret = ListInsert(++k, bj, *listC);
		CHECK_RET(ret, "k = %d, bj = %d", k, bj);
		++j;
	}

	while (i <= listALength) {
		ret = GetElem(i++, listA, &ai);
		CHECK_RET(ret, "i = %d", i);
		ret = ListInsert(++k, ai, *listC);
		CHECK_RET(ret, "k = %d, ai = %d", k, ai);
	}

	while (j <= listBLength) {
		ret = GetElem(j++, listB, &bj);
		CHECK_RET(ret, "j = %d", j);
		ret = ListInsert(++k, bj, *listC);
		CHECK_RET(ret, "k = %d, bj = %d", k, bj);
	}

	return RET_OK;
}

6) auxiliary.h

/* 辅助函数定义头文件 */

#ifndef AUXILIARY_H
#define AUXILIARY_H

#include "singleLinkList.h"

void Visit(ElemType e);
Bollean Equal(ElemType e1, ElemType e2);
int Compare(ElemType e1, ElemType e2);
Status ShowList(char str[], LinkList L);

#endif // !AUXILIARY_H

7) auxiliary.c

/* 辅助函数实现源文件 */

#include "auxiliary.h"
#include <stdio.h>

/*
	前置条件：无
	操作结果：辅助函数，打印整形元素值 e
*/
void Visit(ElemType e)
{
	printf("%d ", e);
}

/*
	前置条件：无
	操作结果：辅助函数，判断元素 e1 和 e2 是否相等
*/
Bollean Equal(ElemType e1, ElemType e2)
{
	return (e1 == e2) ? TRUE : FALSE;
}

/*
	前置条件：无
	操作结果：辅助函数，判断元素 e1 和 e2 大小
*/
int Compare(ElemType e1, ElemType e2)
{
	return e1 - e2;
}

/*
	前置条件：无
	操作结果：辅助函数，格式化打印 list 中的元素
*/
Status ShowList(char str[], LinkList list)
{
	printf("%s", str);
	Status ret = ListTraverse(Visit, list);
	CHECK_RET(ret, NONE);
	putchar('\n');

	return RET_OK;
}

8) main.c

/* 主函数入口源文件 */
#include "singleLinkList.h"
#include "algorithm.h"
#include "auxiliary.h"
#include <stdio.h>

int main(void)
{
	int n = 5;
	LinkList listA, listB, listC;
	Status ret = CreateListHead(n, &listA);
	ret = ShowList("listA is: ", listA);
	CHECK_RET(ret, NONE);
	ret = CreateListTail(n, &listB);
	CHECK_RET(ret, NONE);
	ret = ShowList("listB is: ", listB);
	CHECK_RET(ret, NONE);
	ret = MergeList(listA, Compare, &listB, &listC);
	CHECK_RET(ret, NONE);
	ret = ShowList("listC is: ", listC);
	CHECK_RET(ret, NONE);
	ret = DestroyList(&listC);
	CHECK_RET(ret, NONE);
	/* free() 的作用：仅仅是释放堆内存，不将指针置空 */
	printf("After Destroy list listC, listC is %p\n", listC);

	/* 算法 2.1 单链表实现测试 */
	ret = CreateListTail(n, &listA);
	CHECK_RET(ret, NONE);
	ret = ShowList("listA is: ", listA);
	CHECK_RET(ret, NONE);
	ret = CreateListTail(n, &listB);
	CHECK_RET(ret, NONE);
	ret = ShowList("listB is: ", listB);
	CHECK_RET(ret, NONE);
	ret = Union(listB, listA);
	ret = ShowList("listA is: ", listA);
	CHECK_RET(ret, NONE);
	ret = ShowList("listB is: ", listB);
	CHECK_RET(ret, NONE);
	ret = DestroyList(&listA);
	CHECK_RET(ret, NONE);
	ret = DestroyList(&listB);
	CHECK_RET(ret, NONE);

	/* 算法 2.2 单链表实现测试 */
	ret = CreateListTail(n, &listA);
	CHECK_RET(ret, NONE);
	ret = ShowList("listA is: ", listA);
	CHECK_RET(ret, NONE);
	ret = CreateListTail(n, &listB);
	CHECK_RET(ret, NONE);
	ret = ShowList("listB is: ", listB);
	CHECK_RET(ret, NONE);
	ret = MergeList2(listA, listB, Compare, &listC);
	CHECK_RET(ret, NONE);
	ret = ShowList("listC is: ", listC);
	CHECK_RET(ret, NONE);
	ret = DestroyList(&listA);
	CHECK_RET(ret, NONE);
	ret = DestroyList(&listB);
	CHECK_RET(ret, NONE);
	ret = DestroyList(&listC);
	CHECK_RET(ret, NONE);

	/* 测试其他 */
	LinkList list;
	printf("Please input the element num of list for create ascend: ");
	int num;
	scanf_s("%d", &num);
	ret = CreateSingleLinkList(num, Compare, TRUE, &list);
	CHECK_RET(ret, NONE);
	ret = ShowList("list is: ", list);
	CHECK_RET(ret, NONE);
	ret = InsertAscend(10, Compare, list);
	CHECK_RET(ret, NONE);
	printf("After insert 10 for ascend, ");
	ret = ShowList("list is: ", list);
	CHECK_RET(ret, NONE);
	ret = HeadInsert(12, list);
	CHECK_RET(ret, NONE);
	ret = EndInsert(9, list);
	CHECK_RET(ret, NONE);
	printf("After insert 12 in the head of list, insert 9 in the tail of list, ");
	ret = ShowList("list is: ", list);
	CHECK_RET(ret, NONE);
	ElemType e;
	printf("Please input the element to be delete: ");
	scanf_s("%d", &e);
	Bollean isDeleted = FALSE;
	ret = DeleteElem(e, &isDeleted, list);
	CHECK_RET(ret, NONE);
	printf("delete %d %s\n", e, (isDeleted == TRUE) ? "success" : "failed");
	ret = ShowList("list is: ", list);
	CHECK_RET(ret, NONE);
	printf("Please input the order of the element to be replace and the new value: ");
	scanf_s("%d%d", &num, &e);
	ret = RePlaceElem(num, e, list);
	CHECK_RET(ret, NONE);
	ret = ShowList("list is: ", list);
	CHECK_RET(ret, NONE);
	ret = DestroyList(&list);
	CHECK_RET(ret, NONE);
	printf("Create list for descend, please input the num of list: ");
	scanf_s("%d", &num);
	ret = CreateSingleLinkList(num, Compare, FALSE, &list);
	CHECK_RET(ret, NONE);
	ret = ShowList("list is: ", list);
	CHECK_RET(ret, NONE);
	ret = InsertDescend(10, Compare, list);
	CHECK_RET(ret, NONE);
	printf("After insert 10 in list for descend, ");
	ret = ShowList("list is: ", list);
	CHECK_RET(ret, NONE);
	printf("Please input the element to be delete: ");
	scanf_s("%d", &e);
	isDeleted = FALSE;
	ret = DeleteElem(e, &isDeleted, list);
	CHECK_RET(ret, NONE);
	printf("delete %d %s\n", e, (isDeleted == TRUE) ? "success" : "failed");
	ret = ShowList("list is: ", list);
	CHECK_RET(ret, NONE);
	ElemType e2;
	ret = DeleteFirst(&e, list);
	CHECK_RET(ret, NONE);
	ret = DeleteTail(&e2, list);
	CHECK_RET(ret, NONE);
	printf("After delete head element %d and tail element %d, ", e, e2);
	ret = ShowList("list is: ", list);
	CHECK_RET(ret, NONE);
	ret = DestroyList(&list);
	CHECK_RET(ret, NONE);

	return 0;
}

3. 运行示例

第 2 章 线性表 （线性表的单链表存储结构实现）,# 数据结构（C语言版）,算法,c语言,数据结构文章来源地址https://www.toymoban.com/news/detail-704561.html

到了这里，关于第 2 章 线性表 （线性表的单链表存储结构实现）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 数据结构（王道）——线性表的存储结构之循环表

    数据结构（王道）——线性表的存储结构之循环表

      创建并初始化、判断循环单链表是否为空、判断结点p是否为循环单链表的表尾结点的代码操作。           创建并初始化、判断循环双链表是否为空、判断结点p是否为循环双链表的表尾结点的代码操作。     普通双链表用以下代码实现插入的时候，如果插入的结点是最后

    2024年02月16日
    浏览(39)
  • 【（数据结构）— 单链表的实现】

    【（数据结构）— 单链表的实现】

    概念： 链表是⼀种 物理存储结构上非连续、 非顺序的存储结构，数据元素的 逻辑顺序 是通过链表中的 指针链接 次序实现的 。 链表的结构跟⽕⻋⻋厢相似，淡季时⻋次的⻋厢会相应减少，旺季时⻋次的⻋厢会额外增加⼏节。只需要将⽕⻋⾥的某节⻋厢去掉/加上，不会影响

    2024年02月08日
    浏览(52)
  • 【数据结构—单链表的实现】

    【数据结构—单链表的实现】

    提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档 目录 前言 1. 链表的概念及结构 2. 单链表的实现 2.1单链表头文件——功能函数的定义 2.2单链表源文件——功能函数的实现 2.3 单链表源文件——功能的测试 3.具体的理解操作图 4. 链表的分类 总结 世上

    2024年02月05日
    浏览(66)
  • 【数据结构】单链表的实现

    【数据结构】单链表的实现

    🌇个人主页：平凡的小苏 📚学习格言：别人可以拷贝我的模式，但不能拷贝我不断往前的激情 🛸C语言专栏：https://blog.csdn.net/vhhhbb/category_12174730.html 🚀数据结构专栏：https://blog.csdn.net/vhhhbb/category_12211053.html         家人们更新不易，你们的👍点赞👍和⭐关注⭐真的对我

    2023年04月09日
    浏览(65)
  • 【数据结构】-- 单链表的实现

    【数据结构】-- 单链表的实现

    在前面我们学习了顺序表，顺序表在数组的基础上提供了很多现成的方法，方便了我们对数据的管理，但是我们也发现顺序表有着许多不足： 在处理大型的数据时，需要频繁的增容且在中间删除或插入数据时需要遍历顺序表，这些性质导致了顺序表的 效率较低 。这时我们就

    2024年04月27日
    浏览(52)
  • 【数据结构】单链表的简单实现

    【数据结构】单链表的简单实现

    提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档 单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元

    2024年02月04日
    浏览(57)
  • 【数据结构】单链表的层层实现！! !

    【数据结构】单链表的层层实现！! !

    关注小庄 顿顿解馋(●’◡’●) 上篇回顾 我们上篇学习了本质为数组的数据结构—顺序表，顺序表支持下标随机访问而且高速缓存命中率高，然而可能造成空间的浪费，同时增加数据时多次移动会造成效率低下，那有什么解决之法呢？这就得引入我们链表这种数据结构 概念

    2024年03月12日
    浏览(169)
  • 【数据结构】实现单链表的增删查

    【数据结构】实现单链表的增删查

    链表类和节点类的定义： 图解： 从中间位置插入： 图解：假定index=2 尾插： 删除当前线性表中索引为index的元素，返回删除的元素值： 图解： 删除当前线性表中第一个值为element的元素： 删除当前线性表中所有值为element的元素： 将当前线性表中index位置的元素替换为eleme

    2024年02月14日
    浏览(172)
  • 数据结构：单链表的实现(C语言)

    数据结构：单链表的实现(C语言)

    个人主页 ： 水月梦镜花 个人专栏 ： 《C语言》 《数据结构》 本博客将要实现的无头单向不循环链表。 我们将节点定义为如下结构： 其成员变量有data，next。 将int重命名为STLDataType，方便我们以后修改数据域的内容。 动态申明一个空间，来放置数据。如下： 将data的内容置

    2024年02月14日
    浏览(59)
  • 数据结构——单链表的实现(c语言版）

    数据结构——单链表的实现(c语言版）

    前言           单链表作为顺序表的一种，了解并且熟悉它的结构对于我们学习更加复杂的数据结构是有一定意义的。虽然单链表有一定的缺陷，但是单链表也有它存在的价值， 它也是作为其他数据结构的一部分出现的，比如在图，哈希表中。 目录 1.链表节点的结构 2.头插

    2024年02月13日
    浏览(60)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包