数据结构03-双向链表

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

// 定义双向链表的节点结构体
typedef struct DoubleLinkedNode {
	char data; // 节点存储的数据
	struct DoubleLinkedNode *previous; // 指向前一个节点的指针
	struct DoubleLinkedNode *next; // 指向下一个节点的指针
} DLNode, *DLNodePtr;

// 初始化双向链表，创建一个头节点
DLNodePtr initLinkList() {
	DLNodePtr tempHeader = (DLNodePtr)malloc(sizeof(struct DoubleLinkedNode));
	tempHeader->data = '\0'; // 头节点数据为空
	tempHeader->next = NULL; // 头节点的next指针为空
	tempHeader->previous = NULL; // 头节点的previous指针为空
	return tempHeader; // 返回头节点
}

// 打印双向链表的内容
void printList(DLNodePtr paraHeader) {
	DLNodePtr p = paraHeader->next; // 从头节点的下一个节点开始遍历
	while (p != NULL) {
		printf("%c", p->data); // 打印当前节点的数据
		p = p->next; // 移动到下一个节点
	}
	printf("\r\n"); // 打印换行
}

// 在双向链表的指定位置插入元素
void insertElement(DLNodePtr paraHeader, char paraChar, int paraPosition) {
	DLNodePtr p, q, r;
	p = paraHeader;
	for (int i = 0; i < paraPosition; i++) {
		p = p->next;
		if (p == NULL) {
			printf("The position %d is beyond the scope of the list.", paraPosition);
			return;
		}
	}
	q = (DLNodePtr)malloc(sizeof(struct DoubleLinkedNode)); // 创建新节点
	q->data = paraChar; // 设置新节点的数据
	r = p->next; // r指向p当前指向的节点的下一个节点
	q->next = p->next; // 新节点的next指针指向p的next节点
	q->previous = p; // 新节点的previous指针指向p
	p->next = q; // p的next指针指向新节点
	if (r != NULL) {
		r->previous = q; // 如果r不为空，设置r的previous指针指向新节点
	}
}

// 删除双向链表中的指定元素
void deleteElement(DLNodePtr paraHeader, char paraChar) {
	DLNodePtr p, q, r;
	p = paraHeader;
	while ((p->next != NULL) && (p->next->data != paraChar)) {
		p = p->next;
	}
	if (p->next == NULL) {
		printf("The char '%c' does not exist.\r\n", paraChar);
		return;
	}
	q = p->next; // q指向要删除的节点
	r = q->next; // r指向q的下一个节点
	p->next = r; // p的next指针指向r
	if (r != NULL) {
		r->previous = p; // 如果r不为空，设置r的previous指针指向p
	}
	free(q); // 释放q节点占用的内存
}

// 测试插入和删除功能
void insertDeleteTest() {
	DLNodePtr tempList = initLinkList(); // 初始化链表
	printList(tempList); // 打印链表
	// 插入元素
	insertElement(tempList, 'H', 0);
	insertElement(tempList, 'e', 1);
	insertElement(tempList, 'l', 2);
	insertElement(tempList, 'l', 3);
	insertElement(tempList, 'o', 4);
	insertElement(tempList, '!', 5);
	printList(tempList); // 打印链表
	// 删除元素
	deleteElement(tempList, 'e');
	deleteElement(tempList, 'a'); // 该元素不存在
	deleteElement(tempList, 'o');
	printList(tempList); // 打印链表
	insertElement(tempList, 'o', 1); // 再次插入元素
	printList(tempList); // 打印链表
}

// 测试节点地址
void basicAddressTest() {
	DLNode tempNode1, tempNode2;

	tempNode1.data = 4; // 设置节点1的数据
	tempNode1.next = NULL; // 节点1的next指针为空

	tempNode2.data = 6; // 设置节点2的数据
	tempNode2.next = NULL; // 节点2的next指针为空

	// 打印节点地址信息
	printf("The first node: %p, %p, %p\r\n",
		&tempNode1, &tempNode1.data, &tempNode1.next);
	printf("The second node: %p, %p, %p\r\n",
		&tempNode2, &tempNode2.data, &tempNode2.next);

	tempNode1.next = &tempNode2; // 设置节点1的next指针指向节点2
}

int main() {
	insertDeleteTest(); // 运行插入和删除测试
	basicAddressTest(); // 运行地址测试
	return 0;
}

运行结果