當前位置:網站首頁>雙向鏈錶的設計

雙向鏈錶的設計

2022-01-26 23:57:01 悟空不買菜了

內存結構分析:

插入與删除分析:

 

下面看代碼實現:頭文件dlinklist.h

#ifndef _DLINKLIST_H_
#define _DLINKLIST_H_
#include <stdio.h>
#include <stdlib.h>


//數據節點
typedef struct _dlink_list_node dlink_list_node;

struct _dlink_list_node{
	int data;
	dlink_list_node *next;
	dlink_list_node *previous;
};

//頭節點
typedef struct _t_dlink_list{
	int length;
	dlink_list_node *next;
}t_dlink_list;


t_dlink_list* create();
void clear_list(t_dlink_list *t_list);
void destroy_list(dlink_list_node *p_node);
int get_len(t_dlink_list *t_list);
int insert_value(t_dlink_list *t_list,int value,int pos);
dlink_list_node *get_node(t_dlink_list *t_list,int pos);
dlink_list_node *delete_node(t_dlink_list *t_list,int pos);
void print_node(dlink_list_node *t_list);


#endif

 實現文件:dlinklist.c

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


t_dlink_list* create()
{
	t_dlink_list *t_list = (t_dlink_list*)malloc(sizeof(t_dlink_list));
	if(t_list != NULL) {
		t_list->length = 0;
		t_list->next = NULL;
	}
	return t_list;
}

void clear_list(t_dlink_list *t_list)
{
	if(t_list != NULL) {
		t_list->length = 0;
	}
}

void destroy_list(dlink_list_node *p_node)
{
	//遞歸考慮一下內存開銷,數據量特別大的時候,遞歸比較麻煩
	//直接釋放頭節點呢,數據從頭節點移動,但是malloc這片內存空間什麼時候銷毀?不會別銷毀,程序關閉
	//這樣考慮存放數據,把數據分配在棧上面,棧上面內存自動銷毀
	if(p_node != NULL) {
		return;
	} else {
		destroy_list(p_node->next);
		printf("節點進來銷毀了\n");
		free(p_node);
	}
}

int get_len(t_dlink_list *t_list)
{
	int res = -1;
	if(t_list != NULL) {
		res = t_list->length;
	}
	return res;
}

int insert_value(t_dlink_list *t_list,int value,int pos)
{
	int res = t_list != NULL && pos >= 0 && pos <= get_len(t_list);
	if(res) {
		//分配節點空間
		dlink_list_node *node = (dlink_list_node*)malloc(sizeof(dlink_list_node));
		if(node != NULL) {
			node->data = value;
			node->next = NULL;
			node->previous = NULL;
		}
		int i = 0;
		dlink_list_node *p_cur = (dlink_list_node*)t_list;
		for(;i < pos;i++) {
			p_cur = p_cur->next;
		}
		//移動到合適比特置,開始連接數據
		//找到删除節點下一個節點
		dlink_list_node *p_next = p_cur->next;
		node->next = p_next;
		p_cur->next = node;
		node->previous = p_cur;
		//如果是最後一個節點插入不用改變後面的節點的previous,沒有這個節點
		if(pos != get_len(t_list)) {
			p_next->previous = node;
		} else if(pos == 0) {
			node->previous = NULL;
		}
		t_list->length++;
	}
	return res;
} 

dlink_list_node *get_node(t_dlink_list *t_list,int pos) 
{
	dlink_list_node *res = NULL;
	if(t_list != NULL && pos >= 0 && pos < get_len(t_list)) {
		int i;
		dlink_list_node *p_cur = (dlink_list_node*)t_list;
		for(i = 0;i < pos;i++) {
			p_cur = p_cur->next;
		}
		res = p_cur->next;
	}
	return res;
}
dlink_list_node *delete_node(t_dlink_list *t_list,int pos)
{
	dlink_list_node *res = get_node(t_list,pos);
	if(t_list != NULL && pos >= 0 && pos < get_len(t_list)) {
		dlink_list_node *p_cur = (dlink_list_node *)t_list;
		int i;
		for(i = 0;i < pos;i++) {
			p_cur = p_cur->next;
		}
		dlink_list_node *p_del = p_cur->next;
		dlink_list_node *p_next = p_del->next;//改變她的previous
		p_cur->next = p_next;
		//判定第一個節點與最後一個節點的删除
		if(pos == 0) {
			p_next->previous = NULL;
		} else if(pos != get_len(t_list) - 1) {
			p_next->previous = p_cur;
		}
		t_list->length--;
	}
	return res;
}

void print_node(dlink_list_node *t_list)
{
	if(t_list != NULL) {
		dlink_list_node *p_cur = t_list->next;
		while(p_cur != NULL) {
			printf("%p %d %p\n",p_cur->previous,p_cur->data,p_cur->next);
			p_cur = p_cur->next;
		}
	}
}

測試文件:main.c

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


int main(){
	t_dlink_list *t_list = create();
	printf("before:%d\n",get_len(t_list));
	insert_value(t_list,23,get_len(t_list));
	insert_value(t_list,54,get_len(t_list));
	insert_value(t_list,89,get_len(t_list));
	insert_value(t_list,129,get_len(t_list));
	printf("after:%d\n",get_len(t_list));
	printf("\n------\n");
	dlink_list_node *p_node = (dlink_list_node*)t_list;
	print_node(p_node);
	printf("-------\n");
	delete_node(t_list,1);
	print_node(p_node);
	return 0;
}

版權聲明
本文為[悟空不買菜了]所創,轉載請帶上原文鏈接,感謝
https://cht.chowdera.com/2022/01/202201262357008877.html

隨機推薦