文档章节

双链表操作

meshwon
 meshwon
发布于 2017/04/26 12:36
字数 1021
阅读 9
收藏 0

头文件


typedef  int ElemData;  
typedef struct Node* pNode;  
 
/*定义节点类型*/  
typedef struct Node  
{  
    ElemData data;      /*数据域*/  
    pNode previous; /*指向前驱*/  
    pNode next;     /*指向后继*/  
}Node;  

typedef struct{
	pNode head;
	pNode tail;
	int size;
}D_LIST;

pNode createNode();

//创建一个节点,prev与next指向NULL 
D_LIST* createList();

void initList(D_LIST* list,ElemData e);

//释放节点
void freeNode(pNode node);

//头部插入一个节点
void insertNodeFromHead(D_LIST* list,ElemData e); 

//尾部插入一个节点
void insertNodeFromTail(D_LIST* list,ElemData e); 

//指定位置插入一个节点
void insertNodeToIndex(D_LIST* list,ElemData e ,int index);

//指定data域之后插入
void insertNodeToData(D_LIST* list,ElemData data,ElemData insertData);

//修改索引节点的数据
void updateNodeDataByIndex(D_LIST* list,ElemData e,int index);

//删除索引节点,返回数据域的值,没有则返回NULL 
ElemData removeNodeByIndex(D_LIST* list,int index); 
 
//删除ElemData的节点
ElemData removeElemData(D_LIST* list,ElemData e); 

pNode get(D_LIST* list,int index); 
 
/*依次对链表中每个元素调用函数visit()*/  
void ListTraverse(D_LIST* list);  

//destroy
void destroyList(D_LIST* list); 

实现

#include <stdio.h>
#include "LinkedList.h"
#include <malloc.h>  
#include <stdlib.h>  
#include <string.h>

//创建一个节点,prev与next指向NULL 
D_LIST* createList(){
	D_LIST* node = (D_LIST*)malloc(sizeof(D_LIST));
	if(node == NULL){
		printf("内存分配失败!\n");
		return NULL;
	}
	memset(node,0,sizeof(D_LIST));
	node->size = 0 ;
	node->head = NULL;
	node->tail = NULL;
	return node;
}

pNode createNode(){
	pNode node = (pNode)malloc(sizeof(Node));
	if(node == NULL){
		printf("内存分配失败!");
		return NULL;
	}
	memset(node,0,sizeof(Node));
	node->next = NULL;
	node->previous = NULL;
}

void initList(D_LIST* list,ElemData e){
	pNode node = createNode();
	if(node == NULL){
		return ;
	}
	list->size = list->size+1;
	node->data = e;
	list->head = node;
	list->tail = node;
}

//释放节点
void freeNode(pNode node){
	free(node);
}

//头部插入一个节点
void insertNodeFromHead(D_LIST* list,ElemData e){	
	pNode node = createNode();
	if(node == NULL){
		return;
	}
	node->data = e;
	node->next = list->head;
	if(list->head != NULL)
		list->head->previous = node;
	list->head = node;
	list->size = list->size + 1;
}

//尾部插入一个节点
void insertNodeFromTail(D_LIST* list,ElemData e){
	pNode node = createNode();
	if(node == NULL){
		return;
	}
	node->data = e;
	if(list->tail != NULL){
		list->tail->next = node;
	}
	node->previous = list->tail;
	if(list->head == NULL){
		list->head = node;
	}
	list->tail = node;
	list->size = list->size + 1;
}
//
//指定位置插入一个节点,节点前比较好实现 
void insertNodeToIndex(D_LIST* list,ElemData e ,int index){
	int indexTemp = index;
	if(index < 0){
		printf("索引不能为负数!\n");
		return;
	}
	if(list->size < index){
		printf("索引超过链表的最大长度!\n");
		return;
	}
	
	pNode indexNode = list->head;
	while(indexNode != NULL && indexTemp > 0){
		indexTemp--;
		indexNode = indexNode->next;
	}
	if(indexNode == NULL){
		initList(list,e);
		return;
	}
	pNode node = createNode();
	if(node == NULL){
		return;
	}
	node->data = e;
	node->next = indexNode;
	node->previous = indexNode->previous;
	if(indexNode->previous != NULL)
		indexNode->previous->next = node;
	if(indexNode->previous)
		indexNode->previous = node;
	if(index == 0){
		list->head = node;
	}
	else if(index == list->size -1)
		list->tail = node;
	list->size = list->size + 1;
}

////指定data域之前插入
//void insertNodeToData(D_LIST* list,ElemData data,ElemData insertData){
//
//
//	
//}

//修改索引节点的数据
void updateNodeDataByIndex(D_LIST* list,ElemData e,int index){
	int indexTemp = index;
	if(index < 0){
		printf("索引不能为负数!\n");
		return;
	}
	if(list->size < index){
		printf("索引超过链表的最大长度!\n");
		return;
	}
	
	pNode indexNode = list->head;
	//可优化 (/2) 
	while(indexNode != NULL && indexTemp > 0){
		indexTemp--;
		indexNode = indexNode->next;
	}
	indexNode->data = e;
}

//删除索引节点,返回数据域的值,没有则返回NULL 
ElemData removeNodeByIndex(D_LIST* list,int index){
	int indexTemp = index;
	if(index < 0){
		printf("索引不能为负数!\n");
		return -1;
	}
	if(list->size < index){
		printf("索引超过链表的最大长度!\n");
		return -1;
	}
	pNode indexNode = list->head;
	//可优化 (/2) 
	while(indexNode != NULL && indexTemp > 0){
		indexTemp--;
		indexNode = indexNode->next;
	}
	if(index == list->size){
		list->tail = indexNode->previous;
	}
	if(index == 0)
		list->head = indexNode->next;
	if(indexNode->previous != NULL)
		indexNode->previous->next = indexNode->next;
	if(indexNode->next != NULL)
		indexNode->next->previous = indexNode->previous;
	int dat = indexNode->data;
	freeNode(indexNode);
	return dat;
}
 
//删除ElemData的节点
ElemData removeElemData(D_LIST* list,ElemData e){
	if(list->head == NULL){
		printf("查找元素不存在,链表为空!");
		return -1; 
	}
	pNode node = list->head;
	while(node->data != e){
		node = node->next;
	}
	if(node == NULL){
		printf("未找到对应元素的节点!");
		return -1; 
	} 
	
	if(&node == &(list->head)){
		list->tail = node->previous;
	}
	if(&node == &(list->tail)){
		list->head = node->next;
	}
		
	if(node->previous != NULL)
		node->previous->next = node->next;
	if(node->next != NULL)
		node->next->previous = node->previous;
	int dat = node->data;
	freeNode(node);
	return dat;
}


void ListTraverse(D_LIST* list){
	if(list == NULL){
		printf("链表还未创建!\n");
		return;
	}
	pNode node = list->head;
	if(node == NULL){
		printf("链表为空\n");
		return;
	}
	printf("链表长度:%d\n",list->size);
	while(node != NULL){
		printf("%d\t",node->data);
		node = node->next;
	}
}

//destroy
void destroyList(D_LIST** list){
	pNode fNode = NULL;
	pNode head = (*list)->head;
	int i = 1;
	while(head != NULL){
		printf("%d\n",i++);
		fNode = head;
		head = fNode->next;
		freeNode(fNode);
	} 
	free(*list);
	*list = NULL;
}

int main(){
	D_LIST* list = createList();
	initList(list,50);
	insertNodeFromHead(list,10);
	insertNodeFromTail(list,1000);
	insertNodeToIndex(list,100,2);
	updateNodeDataByIndex(list,200,2);
	//removeNodeByIndex(list,2);
	//ListTraverse(list);
	removeElemData(list,200);
	destroyList(&list);
	ListTraverse(list);
	//initList(&list,100);
	//insertNodeFromHead(&list,50);
	//insertNodeFromTail(&list,200);
	//insertNodeToIndex(&list,5,0);
	//insertNodeToData(&list,50,10);
	//ListTraverse(list);
	return 1;
}

 

© 著作权归作者所有

下一篇: 链表基本操作
meshwon
粉丝 1
博文 29
码字总数 19085
作品 0
哈尔滨
程序员
私信 提问
数组和链表结构(python)_2

本文内容目录如下,会分拆为两篇笔记,另一则笔记是 "数组和链表结构(python)_1"。 3. 链表结构 Linked Structures 在数组之后,链表结构可能使程序中最常用的数据结构。 3.1 单链表结构和双...

曾翔翔
2018/07/28
0
0
单双链表练习题

本文是关于链表的一些操作(包括单链表和双向循环链表) 1、单链表,双链表的创建。 2、单链表和双链表的打印。 3、单链表的插入,删除。 4、双链表的插入和删除。 5、单链表的逆置。 6、单链...

qq_38646470
2018/01/27
0
0
[game]十字链表的AOI算法实现

AOI主要有九宫格、灯塔和十字链表的算法实现。本文阐述十字链表的实现和尝试。 1. 基本原理 根据二维地图,将其分成x轴和y轴两个链表。如果是三维地图,则还需要维护多一个z轴的链表。将对象...

技术小牛人
2017/11/08
0
0
数据结构——基于java的链表实现(真正理解链表这种数据结构)

原创不易,如需转载,请注明出处https://www.cnblogs.com/baixianlong/p/10759599.html,否则将追究法律责任!!! 一、链表介绍 1、什么是链表? 链表是一种物理存储结构上非连续、非顺序的...

会炼钢的小白龙
前天
0
0
Java基础知识——数组与链表的区别

1、数组与链表的区别。 数组是具有相同的数据类型且按一定次序排列的一组变量的集合体,数组在内存中的地址是连续的(链表内存地址是散列、不连续的)。数组是一种引用数据类型,数组元素类似...

小八路2222
03/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

REST接口

文章来源 https://zhuanlan.zhihu.com/p/28674721?group_id=886181549958119424 http://www.ruanyifeng.com/blog/2014/05/restful_api.html REST 对请求的约定 REST 用来规范应用如何在 HTTP......

Airship
昨天
0
0
Spring Cloud Config 统一配置中心

Spring Cloud Config 统一配置中心 一、统一配置中心 统一管理配置 通常,我们会使用配置文件来管理应用的配置。如一个 Spring Boot 的应用,可以将配置信息放在 application.yml 文件中,如...

非摩尔根
昨天
0
0
android ------ AAPT2 error: check logs for details解决方法

AAPT 是全称是 Android Asset Packaging Tool,它是构建 App,甚至是构建 Android 系统都必不可少的一个工具。它的作用是将所有资源文件压缩打包到Android APK 当中。我们在 Android SDK 目录...

切切歆语
昨天
1
0
今天的学习

今天学到了<select></select>标签: <label for="unittype">Select unit type: </label><select id="unittype" name="unittype" autofocus > <option value="1"> Miner </option> ......

墨冥
昨天
1
0
程序员随想-关于分享

最早的时候,文字是贵族这些上层人士才会学习的,底层人士没有资格和渠道去学习,同样用文字、图像等其他载体承载的知识大部分也只有贵族阶层才能享受的。后来有了造纸术、印刷术,成本降低,...

Lubby
昨天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部