数据结构02-单链表

单链表表作业2024.4.9 丁致宇 202331060205

老师讲课讲的真好！生动有趣！

代码展示

#include <stdio.h>
#include <malloc.h>

/**
 * 字符链表结点结构。关键数据为data。
 */
typedef struct LinkNode{
	char data;
	struct LinkNode *next;
} LNode, *LinkList, *NodePtr;

/**
 * 初始化链表并创建一个头结点。
 * @return 指向头结点的指针。
 */
LinkList initLinkList(){
	NodePtr tempHeader = (NodePtr)malloc(sizeof(LNode));
	tempHeader->data = '\0';
	tempHeader->next = NULL;
	return tempHeader;
}// initLinkList 结束

/**
 * 打印链表。
 * @param paraHeader 链表的头结点。
 */
void printList(NodePtr paraHeader){
	NodePtr p = paraHeader->next;
	while (p != NULL) {
		printf("%c", p->data);
		p = p->next;
	}// 循环结束
	printf("\r\n");
}// printList 结束

/**
 * 打印链表及其内存信息。
 * @param paraHeader 链表的头结点。
 */
void printListMemory(NodePtr paraHeader){
	NodePtr p = paraHeader;
	while (p != NULL) {
	    printf("At address %ld, data = %c, next = %ld \r\n", p, p->data, p->next);
		p = p->next;
	}// 循环结束
	printf("\r\n");
}// printListMemory 结束


/**
 * 在链表尾部添加一个元素。
 * @param paraHeader 链表的头结点。
 * @param paraChar 要添加的字符。
 */
void appendElement(NodePtr paraHeader, char paraChar){
	NodePtr p, q;

	// 第1步：构造一个新结点。
	q = (NodePtr)malloc(sizeof(LNode));
	q->data = paraChar;
	q->next = NULL;

	// 第2步：搜索到尾部。
	p = paraHeader;
	while (p->next != NULL) {
		p = p->next;
	}// 循环结束

	// 第3步：链接新结点。
	p->next = q;
}// appendElement 结束

/**
 * 在指定位置插入一个元素。
 * @param paraHeader 链表的头结点。
 * @param paraChar 要插入的字符。
 * @param paraPosition 指定的位置。
 */
void insertElement(NodePtr paraHeader, char paraChar, int paraPosition){
	NodePtr p, q;

	// 第1步：搜索到指定位置。
	p = paraHeader;
	for (int i = 0; i < paraPosition; i ++) {
		p = p->next;
		if (p == NULL) {
			printf("位置 %d 超出了链表范围。", paraPosition);
			return;
		}// 如果为空，则返回
	} // for 循环结束

	// 第2步：构造一个新结点。
	q = (NodePtr)malloc(sizeof(LNode));
	q->data = paraChar;

	// 第3步：插入新结点。
	printf("正在链接\r\n");
	q->next = p->next;
	p->next = q;
}// insertElement 结束

/**
 * 从链表中删除一个元素。
 * @param paraHeader 链表的头结点。
 * @param paraChar 要删除的字符。
 */
void deleteElement(NodePtr paraHeader, char paraChar){
	NodePtr p, q;
	p = paraHeader;
	while ((p->next != NULL) && (p->next->data != paraChar)){
		p = p->next;
	}// 循环结束

	if (p->next == NULL) {
		printf("无法删除字符 %c\r\n", paraChar);
		return;
	}// 如果为空，则返回

	q = p->next;
	p->next = p->next->next;
	free(q);
}// deleteElement 结束

/**
 * 单元测试。
 */
void appendInsertDeleteTest(){
	// 第1步：初始化一个空链表。
	LinkList tempList = initLinkList();
	printList(tempList);

	// 第2步：添加一些字符。
	appendElement(tempList, 'H');
	appendElement(tempList, 'e');
	appendElement(tempList, 'l');
	appendElement(tempList, 'l');
	appendElement(tempList, 'o');
	appendElement(tempList, '!');
	printf("添加元素后");
	printList(tempList);
	printListMemory(tempList);

	// 第3步：删除一些字符（第一次出现的）。
	deleteElement(tempList, 'e');
	deleteElement(tempList, 'a');
	deleteElement(tempList, 'o');
	printf("删除元素后");
	printList(tempList);
	printListMemory(tempList);

	// 第4步：插入到指定位置。
	insertElement(tempList, 'o', 1);
	printf("插入元素后");
	printList(tempList);
	printListMemory(tempList);
}// appendInsertDeleteTest 结束

/**
 * 地址测试：超出书本内容的测试。
 */
void basicAddressTest(){
	LNode tempNode1, tempNode2;

	tempNode1.data = 4;
	tempNode1.next = NULL;

	tempNode2.data = 6;
	tempNode2.next = NULL;

	printf("第一个结点: %d, %d, %d\r\n",
		&tempNode1, &tempNode1.data, &tempNode1.next);
	printf("第二个结点: %d, %d, %d\r\n",
		&tempNode2, &tempNode2.data, &tempNode2.next);

	tempNode1.next = &tempNode2;
}// basicAddressTest 结束

/**
 * 主函数入口。
 */
int main(){
	appendInsertDeleteTest();
	return 0;
}// main 结束

运行结果