【数据结构】双向链表

喜欢ヅ旅行 2022-05-16 09:46 293阅读 0赞

**1.LinkedList.h**

#ifndef LINKED_LIST_H
    #define LINKED_LIST_H
    #include <stdlib.h>
    #include <stdio.h>
    #include <string.h>
    //首先定义一个链表节点结构体
    typedef struct LINKNODE{
    	void* data;//表示节点中存储任意类型的数据
    	struct LINKNODE* pre;//注意这种定义的方式啊
    	struct LINKNODE* next;//注意这种定义的方式啊，前面是struct 后面是LINKNODE是最开始定义的结构体名称，LinkNode是另外定义的名称
    }LinkNode;
    
    //再定义链表结构体
    typedef struct {
            //注意，下面的LinkNode可以不是指针就是LinkNode head,改成不是指针后可能还方便点，
            //如果head不是指针至少在初始化list的时候不用新开辟一片内存，同样也是作为头节点， 
            //而不是数据存储的第一个点，读者可以自行尝试把下面的指针改为不是指针
    	LinkNode* head;//给链表定义一个头
    	int size;//记录当前list存储的元素数量
    }LinkList;
    
    //打印函数指针
    typedef void(*PRINTLINKNODE)(void*);
    
    //初始化链表
    LinkList* initLinkList();
    //指定位置插入
    void insertLinkList(LinkList* list, int pos, void* data);
    //删除指定位置的值
    void removeByPosLinkList(LinkList* list, int pos);
    //获得链表的长度
    int getLinkListSize(LinkList* list);
    //查找
    int findPosByData(LinkList* list, void* data);
    //返回第一个结点
    void* frontLinkList(LinkList* list);
    //返回最后一个结点
    void* backLinkList(LinkList* list);
    //打印链表结点
    void printLinkList(LinkList* list, PRINTLINKNODE print);
    //释放链表内存
    void freeSpaceLinkList(LinkList* list);
    //从后面加入
    void pushBack(LinkList* list, void* data);
    //从后面弹出
    void popBack(LinkList* list);
    //从前面加入
    void pushFront(LinkList* list, void* data);
    //从前面弹出
    void popFront(LinkList* list);
    #endif // !LINKED_LIST_H

**2.LinkedList.c**

#include "LinkedList.h"
    //初始化链表
    LinkList* initLinkList() {
    	LinkList* linkList = (LinkList*)malloc(sizeof(LinkList));
    	//新建个数据节点,让list指向这个节点，这个节点作为list的头节点，不存储数据，只用next记录下真实的存储的第一个位置
    	//这样做的目的是为了便于遍历
    	linkList->head= (LinkNode*)malloc(sizeof(LinkNode));
    	linkList->head->data = NULL;
    	linkList->head->pre = NULL;
    	linkList->head->next = NULL;
    	linkList->size = 0;
    	return linkList;
    }
    //指定位置插入
    void insertLinkList(LinkList* list, int pos, void* data) {
    	if (list == NULL) {
    		return;
    	}
    	if (data == NULL) {
    		return;
    	}
    	if (pos < 0 || pos >= list->size) {
    		pos = list->size;
    	}
    	//创建新的结点
    	LinkNode* newNode = (LinkNode*)malloc(sizeof(LinkNode));
    	newNode->data = data;
    	newNode->next = NULL;
    	//辅助指针
    	LinkNode* pCurrent = list->head;
    	for (int i = 0; i < pos; i++) {
    		pCurrent = pCurrent->next;
    	}
    
    	//将新节点加入链表
    	newNode->pre = pCurrent;
    	newNode->next = pCurrent->next;
    	pCurrent->next = newNode;
    
    	list->size++;
    }
    //删除指定位置的值
    void removeByPosLinkList(LinkList* list, int pos) {
    	if (list == NULL) {
    		return;
    	}
    	if (pos < 0 || pos >= list->size) {
    		return;
    	}
    	//辅助指针
    	LinkNode* pCurrent = list->head;
    	for (int i = 0; i < pos; i++) {
    		pCurrent = pCurrent->next;
    	}
    	//缓存删除的节点
    	LinkNode* pDel = pCurrent->next;
    	pCurrent->next = pDel->next;
    	//释放删除节点的内存
    	free(pDel);
    	list->size--;
    }
    //获得链表的长度
    int getLinkListSize(LinkList* list) {
    	return list->size;
    }
    //查找
    int findPosByData(LinkList* list, void* data) {
    	if (list == NULL) return -10086;
    	if (data == NULL) return -10086;
    	LinkNode* firstNode = list->head->next;
    	int pos = 0;
    	while (firstNode!= NULL) {
    		if (firstNode->data == data) {
    			return pos;
    		}
    		firstNode = firstNode->next;
    		pos++;
    	}
    	return -10086;//表示没有找到
    }
    //返回第一个结点
    void* frontLinkList(LinkList* list) {
    	if (list == NULL) return NULL;
    	return list->head->next->data;
    }
    //返回最后一个结点
    void* backLinkList(LinkList* list) {
    	if (list == NULL) return NULL;
    	LinkNode* pCurrent = list->head;
    	for (int i = 0; i < list->size; i++) {
    		pCurrent = pCurrent->next;
    	}
    	return pCurrent->data;
    }
    //打印链表结点
    void printLinkList(LinkList* list, PRINTLINKNODE print) {
    	if (list == NULL) return;
    	//辅助指针变量
    	LinkNode* pCurrent = list->head->next;
    	while (pCurrent != NULL) {
    		print(pCurrent->data);
    		pCurrent = pCurrent->next;
    	}
    }
    //释放链表内存
    void freeSpaceLinkList(LinkList* list){
    	if (list == NULL) {
    		return;
    	}
    	//辅助指针变量
    	LinkNode* pCurrent = list->head;
    	while (pCurrent != NULL) {
    		//缓存下一个结点
    		LinkNode* pNext = pCurrent->next;
    		free(pCurrent);
    		pCurrent = pNext;
    	}
    
    	//释放链表内存
    	list->size = 0;
    	free(list);
    }
    //从后面加入
    void pushBack(LinkList* list, void* data) {
    	if (list == NULL) {
    		return;
    	}
    	if (data == NULL) {
    		return;
    	}
    	insertLinkList(list, list->size, data);
    }
    //从后面弹出
    void popBack(LinkList* list) {
    	if (list == NULL) return;
    	//获得最后一个指针
    	LinkNode* pCurrent = list->head;
    	while (pCurrent->next != NULL) {
    		pCurrent = pCurrent->next;
    	}
    	//把最后一个的前一个的指针的next指向NULL
    	pCurrent->pre->next = NULL;
    	//释放掉最后一个指针
    	free(pCurrent);
    	list->size--;
    }
    //从前面加入
    void pushFront(LinkList* list, void* data) {
    	if (list == NULL) {
    		return;
    	}
    	if (data == NULL) {
    		return;
    	}
    	insertLinkList(list, 0, data);
    }
    //从前面弹出
    void popFront(LinkList* list) {
    	if (list == NULL) return;
    	if (list->size == 0) return;
    	//先保存第一个阶段的的指针
    	LinkNode* firstNode = list->head->next;
    	//再将头指针的下一个指针指向第一个的下一个
    	list->head->next = firstNode->next;
    	//再将第二个的pre设置为头指针
    	firstNode->next->pre = list->head;
    	//最后释放第一个指针
    	free(firstNode);
    	//size减小一个
    	list->size--;
    }

**3.测试**

#include "LinkedList.h"
    //自定义数据类型
    typedef struct PERSON {
    	char name[64];
    	int age;
    	int score;
    }Person;
    //打印函数
    void MyPrint(void* data) {
    	Person* p = (Person*)data;
    	printf("Name:%s Age:%d Score:%d\n", p->name, p->age, p->score);
    }
    void test01() {
    	LinkList* list = initLinkList();
    	Person p1 = { "xiaodong",20,56 };
    	Person p2 = { "xiaoxiao",30,78 };
    	Person p3 = { "dogndong",20,22 };
    	Person p4 = { "kankan",46,13 };
    	Person p5 = { "hehe",62,34 };
    	Person p6 = { "lishang",67,55 };
    	printf("size:%d\n", getLinkListSize(list));
    	pushBack(list, &p1);
    	printf("size:%d\n", getLinkListSize(list));
    	pushBack(list, &p2);
    	pushBack(list, &p3);
    	pushBack(list, &p4);
    	pushBack(list, &p5);
    	pushFront(list, &p6);
    	printLinkList(list, MyPrint);
    	printf("size:%d\n", getLinkListSize(list));
    	printf("-----------从后面弹出----------\n");
    	popBack(list);
    	printLinkList(list, MyPrint);
    	printf("size:%d\n", getLinkListSize(list));
    	printf("-----------从前面弹出----------\n");
    	popFront(list);
    	printLinkList(list, MyPrint);
    	printf("size:%d\n", getLinkListSize(list));
    	printf("-----------返回第一个节点数据----------\n");
    	MyPrint(frontLinkList(list));
    	printf("-----------返回最后一个节点数据----------\n");
    	MyPrint(backLinkList(list));
    
    }
    int main(void) {
    	test01();
    	system("pause");
    	return 0;
    }