【数据结构 李春葆】第二章 线性表 上机实验题2【单链表】

实验题2：实现单链表的各种基本运算

编写一个程序linklist.h和linklist.cpp，实现单链表的各种基本运算和整体建表算法(元素类型ElemType为char)。在此基础上面设计一个exp2-2.cpp完成下面的功能。

1. 初始化单链表h。
2. 依次采用尾插法插入a,b,c,d,e元素。
3. 输出单链表h。
4. 输出单链表的长度。
5. 判断单链表是否为空。
6. 输出单链表的第3个元素。
7. 输出元素a的位置。
8. 在第4个元素位置上插入f元素。
9. 输出单链表h。
10. 删除单链表h的第3个元素。
11. 输出单链表h。
12. 释放单链表h。

Linklist.h：

#pragma once
#include <cstdio>
#include <cstdlib>
typedef char ElemType;

typedef struct LNode { // 定义单链表结点类型
	ElemType data;
	struct LNode* next;
} Linklist;

void InitList(Linklist*& L);						 // 初始化单链表
void DestroyList(Linklist*& L);						 // 销毁单链表
bool ListEmpty(Linklist* L);						 // 判断单链表是否为空表
bool ListLength(Linklist* L);						 // 返回单链表长度
void PrintList(Linklist* L);						 // 打印整个单链表
bool GetElem(Linklist* L, int i, ElemType& e);		 // 获取单链表中第i个数据元素
int LocateElem(Linklist* L, ElemType e);			 // 按元素值查找元素e的位置
bool ListInsert(Linklist*& L, int i, ElemType e);	 // 插入数据元素
bool ListDelete(Linklist*& L, int i, ElemType &e);	 // 删除数据元素

Linklist.cpp

#include "Linklist.h"

void InitList(Linklist*& L) {						  // 初始化单链表
	L = (Linklist*)malloc(sizeof(LNode));
	L->next = NULL; // nullptr
}
void DestroyList(Linklist*& L) {					  // 销毁单链表
	Linklist* p = L, *q = L->next;
	while (q) {
		free(p);
		p = q;
		q = p->next;
	}
	free(p);
}
bool ListEmpty(Linklist* L) {						  // 判断单链表是否为空表
	return (L->next == NULL);
}
int ListLength(Linklist* L) {						  // 返回单链表长度
	Linklist* p = L;
	int i = 0; 
	while (p->next != NULL) {
		++i;
		p = p->next;
	}
	return i;
}
void PrintList(Linklist* L) {						  // 打印整个单链表
	Linklist* p = L->next;
	while (p) {
		printf("%c ", p->data);
		p = p->next;
	}
	printf("\n");
}

bool GetElem(Linklist* L, int i, ElemType& e) {	      // 获取单链表中第i个数据元素
	int j = 0;
	Linklist* p = L;
	while (j < i && p != NULL) {
		++j;
		p = p->next;
	}
	if (p == NULL) return false; // 不存在第i个数据结点
	else {
		e = p->data;
		return true;
	}
}
int LocateElem(Linklist* L, ElemType e) {			 // 按元素值查找元素e的位置
	int i = 1;  // 逻辑序号
	Linklist* p = L->next;
	while (p != NULL && p->data != e) {
		p = p->next;
		++i;
	}
	if (p == NULL) return 0;  // 不存在元素值为e的结点
	else return i;                     // 存在，返回其逻辑序号
}

bool ListInsert(Linklist*& L, int i, ElemType e) {	 // 插入数据元素
	int j = 0;
	Linklist* pre = L, * s; // p执行头结点，逻辑序号为0
	while (j < i - 1 && pre != NULL) {
		++j;
		pre = p->next;
	}
	if (pre == NULL) return false; // 未找到第i-1个结点
	else { // 找到第i-1个结点
		s = (Linklist*)malloc(sizeof(LNode));   
		s->data = e;
		s->next = pre->next;
		pre->next = s;
		return true;
	}
}
bool ListDelete(Linklist*& L, int i, ElemType& e) { // 删除数据元素
	int j = 0;
	Linklist* pre = L, * q;
	while (j < i - 1 && pre != NULL) {
		++j;
		pre = pre->next;
	}
	if (pre == NULL) return false;  // 未找到第i-1个结点
	else {
		q = pre->next; // 指向要删除的第i个结点
		if (q == NULL) return false;  // 不存在第i个结点
		e = q->data;
		pre->next = q->next;
		free(q);
		return true;     // 返回true表示成功删除第i个结点
	}
}

exp2-2.cpp

#include "Linklist.h"

int main() {
	Linklist* h;
	ElemType e;
	printf("单链表的基本运算如下:\n");
	printf("	1. 初始化单链表h\n");
	InitList(h);
	printf("	2. 依次采用尾插法插入a,b,c,d,e元素\n");
	ListInsert(h, 1, 'a');
	ListInsert(h, 2, 'b');
	ListInsert(h, 3, 'c');
	ListInsert(h, 4, 'd');
	ListInsert(h, 5, 'e');
	printf("	3. 输出单链表h\n");
	PrintList(h);
	printf("	4. 输出单链表的长度：%d\n", ListLength(h));
	printf("	5. 判断单链表是否为空，%s\n", ListEmpty(h) ? "空" : "非空");
	GetElem(h, 3, e);
	printf("	6. 输出单链表的第3个元素：%c\n", e); 
	printf("	7. 输出元素a的位置：%d\n", LocateElem(h, 'a'));
	printf("	8. 在第4个元素位置上插入f元素\n");
	ListInsert(h, 4, 'f');
	printf("	9. 输出单链表h\n");
	PrintList(h);
	printf("	10. 删除单链表h的第3个元素\n");
	ListDelete(h, 3, e);
	printf("	11. 输出单链表h\n");
	PrintList(h);
	printf("	12. 释放单链表h\n");
	DestroyList(h);
	return 0;
}

效果：