精华内容
下载资源
问答
  • C语言 实现一个可以保存任意类型数据的双向链表 无类型 双向链表 任意类型存储 宏语句处理 看起来很高大上是吧? 我们来看看核心结构体: typedef struct __algo_any_list_node { void * data; //指向数据的...

    C语言 实现一个可以保存任意类型数据的双向链表 无类型 双向链表 任意类型存储 宏语句处理

    看起来很高大上是吧?
    我们来看看核心结构体:

    typedef struct __algo_any_list_node
    {
    	void * data;								//指向数据的指针
    	long data_size;								//数据的大小,有时可能会用到
    	int data_type;								//数据的类型
    	struct __algo_any_list_node * previous;		//向前指针
    	struct __algo_any_list_node * next;			//向后指针
    }AlgoAnyListNode,*PAlgoAnyListNode;
    typedef AlgoAnyListNode		AlgoAnyList;
    typedef PAlgoAnyListNode	PAlgoAnyList;
    

    怎么样?是否已经知道怎么实现了?
    对,你的想法是对的就是

    • 借助void*类型
      • 可以指向任意一个地址
      • 也可以转换为任意确切的地址类型

    可能你还有点懵,我们来看下下面的语句练练手:

    int a=0x01020304;
    char * cp=(char *)(void *)&a;
    for(int i=0;i<sizeof(a);i++)
    {
    	printf("%02x",(unsigned char)cp[i]);
    }
    

    怎么样,这样,我们就能够以char * 方式去访问一个int变量,这里只是简单的演示一下,void的用法
    但是,另一个问题来了,void
    虽然可以随便指向,但是,如果我们要取数据,只有一个void*显然毫无用处,因此我们添加一个属性:

    int data_type;	//数据的类型
    

    这样,我们就可以根据我们约定的值,按照约定去取对应类型的值了
    假如:

    //定义一下类型
    #define TYPE_INT 0x01
    
    //先来赋值一下
    int a=12;
    AlgoAnyListNode node;
    node.data=(void *)&a;
    node.data_type=TYPE_INT;
    
    //下面按照约定取数据
    if(node.data_type==TYPE_INT)
    {
    	printf("%d\n",*((int *)node.data));
    }
    

    好了,上面的代码很简单,其中主要就是两句话

    node.data=(void *)&a;
    
    *((int *)node.data)
    

    我们来解决这两句话,
    第一句:
    node.data本来就是void类型,任何地址都可以隐式转换为void,因此可以写为:

    node.data=&a;
    

    第二句:
    我们知道,node.data是void类型,加上int就转换为int*类型:(int )node.data,再对这个指针取值((int *)node.data)就取到了此地址的值
    最后一个问题,为什么还要有一个data_size属性?

    long data_size;	//数据的大小,有时可能会用到
    

    对于基本数据类型来说,大小是固定的,这个属性基本是不用了,因为没有什么意义,但是如果在结构体或者其他类型中的时候,这个属性将可能会有用处,比如:现在将一个文件拆分为多个部分放入链表中,对于文件来说,他可能是二进制文件(二进制数据集),这样的话,就算知道了指针data和类型data_type,那也不知道指向的数据的大小,毕竟二进制数据,不像字符串一样可以使用’\0’来标识字符串的结束,因此只能使用长度的方式来处理(这是其中一个比较简单的方式)
    有了这些基础,我也废话不多说,直接上我的实现代码:
    我们先来看看调用代码

    #include"AlgoAnyList.hpp"
    void testAlgoAnyList()
    {
    	//直接添加一个int类型的进入链表节点
    	AlgoAnyList * list = ALGO_ANY_LIST_BASE_MAKE_NODE(12, int, ALGO_ANY_LIST_DATA_TYPE_INT);
    	//添加10个int类型数据进入链表
    	for (int i = 0; i < 10; i++)
    	{
    		AlgoAnyListNode * node = ALGO_ANY_LIST_BASE_MAKE_NODE(i,int, ALGO_ANY_LIST_DATA_TYPE_INT);
    		list = AlgoAnyList_appendList(list, node);
    	}
    	//添加10个double类型数据进入链表
    	for (int i = 0; i < 10; i++)
    	{
    		AlgoAnyListNode * node = ALGO_ANY_LIST_BASE_MAKE_NODE(i*0.5, double, ALGO_ANY_LIST_DATA_TYPE_DOUBLE);
    		list = AlgoAnyList_appendList(list, node);
    	}
    	//添加10个字符串类型数据进入链表
    	for (int i = 0; i < 10; i++)
    	{
    		AlgoAnyListNode * node = NULL;
    		ALGO_ANY_LIST_MEMORY_MAKE_NODE("hello,哈哈哈", node,15,ALGO_ANY_LIST_DATA_TYPE_LPCHAR);
    		list = AlgoAnyList_appendList(list, node);
    	}
    	//遍历链表,根据不同的类型做一个输出
    	AlgoAnyList * cur = list;
    	while (cur)
    	{
    		if (cur->data_type == ALGO_ANY_LIST_DATA_TYPE_INT)
    		{
    			printf("%d ", ALGO_ANY_LIST_GET_DATA(cur->data, int));
    			ALGO_ANY_LIST_FREE_DATA(cur->data, int);
    		}
    		else if (cur->data_type == ALGO_ANY_LIST_DATA_TYPE_DOUBLE)
    		{
    			printf("%lf ", ALGO_ANY_LIST_GET_DATA(cur->data, double));
    			ALGO_ANY_LIST_FREE_DATA(cur->data, double);
    		}
    		else if (cur->data_type == ALGO_ANY_LIST_DATA_TYPE_LPCHAR)
    		{
    			printf("%s ", ALGO_ANY_LIST_GET_DATA_MEMORY(cur->data,char *));
    			ALGO_ANY_LIST_FREE_DATA_MEMORY(cur->data, char*);
    		}
    		cur = cur->next;
    	}
    	cur = list;
    }
    int main(int argc, char * argv[])
    {
    	testAlgoAnyList();
    	system("pause");
    	return 0;
    }
    

    输出

    12 0 1 2 3 4 5 6 7 8 9 0.000000 0.500000 1.000000 1.500000 2.000000 2.500000 3.000000 3.500000 4.000000 4.500000 hello, 哈哈哈 hello,哈哈哈 hello,哈哈哈 hello,哈哈哈 hello,哈哈哈 hello,哈哈哈 hello,哈哈哈 hello,哈哈哈 hello,哈哈哈 hello,哈 哈哈 请按任意键继续. . .
    

    上面有不少的宏,为了帮助我们更简便的书写代码,为什么呢?
    我们知道,我们需要的是void*类型,也就是无论什么指针,你得给我一个指针
    那么如果我直接给一个立即数:12,这玩意儿是一个常量,地址?
    另外:

    int a=12;
    void * p=&a;
    

    这样的方式取地址不就行了吗?
    但是,是否考虑过,你这样一个临时变量,在作用域范围类,链表数据自然没有任何问题,但是,如果我把链表传递给其他函数呢?搞不好过了作用域,这个临时变量就失效了,那么这个指针就变成了一个不正确的指针,野指针,这显然会出问题
    解决方法:

    int * pa=new int;
    *pa=12;
    void * p=pa;
    

    解决办法是有了,但是每次都这样写代码,显然要骂街的
    因此我们创造一个宏,帮助我们完成这种无聊的事情

    //基本数据类型的宏构造,参数:数据,数据类型,约定类型,例如:AlgoAnyListNode* node=ALGO_ANY_LIST_BASE_MAKE_NODE(12,int,ALGO_ANY_LIST_DATA_TYPE_INT)
    //或者其他类型支持:赋值,malloc(sizeof(类型))的均可
    //因此对数组并不适用
    #define ALGO_ANY_LIST_BASE_MAKE_NODE(data,type,data_type) \
    			AlgoAnyList_makeNode(\
    			&((* (type*)malloc(sizeof(type)))  = data),\
    			data_type,\
    			sizeof(type)\
    			)
    

    好了,我们一步一步看:

    type * p=(type*)malloc(sizeof(type));
    char * p=(char *)malloc(sizeof(char));
    

    怎么样,这一步没问题了吧,也就是申请一个type类型的空间嘛

    type * p=(type*)malloc(sizeof(type));
    (*p=data)
    

    接着上面的p,这不就是赋值吗?没毛病

    AlgoAnyList_makeNode(*p,data_type,sizeof(type));
    

    没问题了吧,就是一个函数调用,对吧
    所以整体来说,我们就是申请了一个type类型的空间来保存data,并且约定类型是data_type

    下面又来了一个宏,我们来看一下

    //字符串构造宏,适用于char * 的字符串,参数:字符串地址,保存节点,例如:AlgoAnyListNode * node = NULL;ALGO_ANY_LIST_LPCHAR_MAKE_NODE("hello", node);
    #define ALGO_ANY_LIST_LPCHAR_MAKE_NODE(data,psave) \
    do\
    {\
    	int size=sizeof(char)*(strlen(data)+1);\
    	char * buf=(char *)malloc(size);\
    	strcpy(buf,data);\
    	psave = AlgoAnyList_makeNode(buf, ALGO_ANY_LIST_DATA_TYPE_LPCHAR, size);\
    } while (0)
    

    看了上一个宏,这一个宏自然也看得懂,可能有点问题的就是

    do
    {
    	//...
    }while(0)
    

    这样一个只执行一次的循环有什么用?
    这个问题很简单,C语言对于宏的处理,就是直接做了一个替换操作
    既然是替换,如果没有一个这样的包裹,就可能导致和外部变量混用,产生不可预知的编译结果,然而宏是不报错的,知道运行失败才能知道失败了
    那么,这样一个do-while(0),首先保证了运行一次,并且由于{}括号的原因,就限定了一个变量的作用域,这样就不会和外部变量交叉发生混乱
    因此,这也是一个宏应用的技巧,另外也可以用

    if(1)
    {
    	//...
    }
    

    代替do-while(0)
    也就是如此,这些宏–有的在宏内发生了临时变量的定义,在早期的纯C编译环境下是不支持的,由于传统C语言的变量需要在一开始定义,不能就地定义,所以这些宏将会出现错误

    看到这里,我相信已经被劝退了不少观众了,上实现源码
    对宏敏感的同学,就不要看宏,只需要知道怎么使用即可

    #ifndef _ALGO_ANY_LIST_HPP_
    #define _ALGO_ANY_LIST_HPP_
    
    /*
    author:ugex
    -----------------------------------
    使用C语言的方式,构造一个通用链表
    命名规则:
    宏部分:
    ALGO_ANY_LIST_开头
    其他部分:
    AlgoAnyList
    
    链表元素需要准守规则,data指向地址一定要是在堆上的
    临时变量取地址是不行的,因为这会有危险(导致野指针)
    另外,一个节点也必须是堆上的,否则如果你跨函数操作的时候,
    节点可能会发生危险,被错误的释放或者野指针
    */
    #include<stdlib.h>
    //基本数据类型定义,你也可以使用自己的定义
    #define ALGO_ANY_LIST_DATA_TYPE_NULL	 0x00
    #define ALGO_ANY_LIST_DATA_TYPE_CHAR	 0x01
    #define ALGO_ANY_LIST_DATA_TYPE_SHORT	 0x02
    #define ALGO_ANY_LIST_DATA_TYPE_INT		 0x03
    #define ALGO_ANY_LIST_DATA_TYPE_LONG	 0x04
    #define ALGO_ANY_LIST_DATA_TYPE_FLOAT	 0x05
    #define ALGO_ANY_LIST_DATA_TYPE_DOUBLE	 0x06
    #define ALGO_ANY_LIST_DATA_TYPE_LPCHAR	 0x07
    
    //用户数据类型值,开始值
    #define ALGO_ANY_LIST_DATA_TYPE_USER	 0x100
    
    //基本数据类型的宏构造,参数:数据,数据类型,约定类型,例如:AlgoAnyListNode* node=ALGO_ANY_LIST_BASE_MAKE_NODE(12,int,ALGO_ANY_LIST_DATA_TYPE_INT)
    //或者其他类型支持:赋值,malloc(sizeof(类型))的均可
    //因此对数组并不适用
    #define ALGO_ANY_LIST_BASE_MAKE_NODE(data,type,data_type) AlgoAnyList_makeNode(&((* (type*)malloc(sizeof(type)))  = data),data_type,sizeof(type))
    
    //字符串构造宏,适用于char * 的字符串,参数:字符串地址,保存节点,例如:AlgoAnyListNode * node = NULL;ALGO_ANY_LIST_LPCHAR_MAKE_NODE("hello", node);
    #define ALGO_ANY_LIST_LPCHAR_MAKE_NODE(data,psave) do{int size=sizeof(char)*(strlen(data)+1);char * buf=(char *)malloc(size);strcpy(buf,data);psave = AlgoAnyList_makeNode(buf, ALGO_ANY_LIST_DATA_TYPE_LPCHAR, size);} while (0)
    
    //内存空间构造,适用于一块内存,因此也适用于字符串构造,参数:数据源地址,数据大小,约定类型
    #define ALGO_ANY_LIST_MEMORY_MAKE_NODE(pdata,psave,data_size,data_type) do{void * buf=(void *)malloc(data_size);memcpy(buf,pdata,data_size);psave = AlgoAnyList_makeNode(buf, data_type, data_size);}while(0)
    
    //释放用于构造宏所得到的空间,适用于基本数据类型,不适用于字符串,其实就是malloc配对的free调用,参数:节点的data,数据类型,例如:ALGO_ANY_LIST_FREE_DATA(node->data,int)
    //如果要应用于字符串,第二个参数应为char,而不是char*
    #define ALGO_ANY_LIST_FREE_DATA(pdata,type) do{if(pdata){free((type *)pdata);pdata=NULL;}}while(0)
    
    //释放一块内存,参数:地址,指针类型,例如:ALGO_ANY_LIST_FREE_DATA_MEMORY(node->data,char *)
    #define ALGO_ANY_LIST_FREE_DATA_MEMORY(pdata,pointertype) do{if(pdata){free((pointertype)pdata);pdata=NULL;}}while(0)
    
    //宏取值,适用于基本数据类型,不适用于字符串,例如:ALGO_ANY_LIST_GET_DATA(cur->data, int)
    #define ALGO_ANY_LIST_GET_DATA(pdata,type) (*(type*)pdata)
    
    //宏取值,取内存数据,转换指针类型
    #define ALGO_ANY_LIST_GET_DATA_MEMORY(pdata,pointertype) ((pointertype)pdata)
    
    typedef struct __algo_any_list_node
    {
    	void * data;								//指向数据的指针
    	long data_size;								//数据的大小,有时可能会用到
    	int data_type;								//数据的类型
    	struct __algo_any_list_node * previous;		//向前指针
    	struct __algo_any_list_node * next;			//向后指针
    }AlgoAnyListNode,*PAlgoAnyListNode;
    typedef AlgoAnyListNode		AlgoAnyList;
    typedef PAlgoAnyListNode	PAlgoAnyList;
    
    //创建一个链表节点
    AlgoAnyListNode* AlgoAnyList_makeNode()
    {
    	AlgoAnyListNode* ret = (AlgoAnyListNode*)malloc(sizeof(AlgoAnyListNode));
    	ret->data = NULL;
    	ret->data_type = ALGO_ANY_LIST_DATA_TYPE_NULL;
    	ret->data_size = 0;
    	ret->previous = NULL;
    	ret->next = NULL; 
    	return ret;
    }
    //带数据创建一个链表节点
    AlgoAnyListNode* AlgoAnyList_makeNode(void * data, int data_type, long data_size/*=0*/)
    {
    	AlgoAnyListNode* ret = AlgoAnyList_makeNode();
    	ret->data = data;
    	ret->data_type = data_type;
    	ret->data_size = data_size;
    	return ret;
    }
    //删除一个节点,返回永为NULL,这样方便你进行这样的调用:
    //node=node.free(node);
    //而不是:node.free(node);node=NULL;
    AlgoAnyListNode* AlgoAnyList_freeNode(AlgoAnyListNode * node)
    {
    	if (node)
    		free(node);
    	return NULL;
    }
    //重置节点,因此,你需要提前处理data段,是否需要释放内存
    AlgoAnyListNode* AlgoAnyList_resetNode(AlgoAnyListNode * ret)
    {
    	ret->data = NULL;
    	ret->data_type = ALGO_ANY_LIST_DATA_TYPE_NULL;
    	ret->data_size = 0;
    	ret->previous = NULL;
    	ret->next = NULL;
    	return ret;
    }
    //重置一个节点的前后指针
    AlgoAnyListNode* AlgoAnyList_resetPointers(AlgoAnyListNode * node)
    {
    	if (node)
    	{
    		node->previous = NULL;
    		node->next = NULL;
    	}
    	return node;
    }
    
    //将两个完整链表连接:返回值list1=list1+list2
    //如果list2只有一个节点,那么就相当于添加一个节点
    AlgoAnyListNode* AlgoAnyList_appendList(AlgoAnyListNode * list1, AlgoAnyListNode * list2)
    {
    	AlgoAnyListNode * list1_last = list1;
    	while (list1_last->next != NULL)
    	{
    		list1_last = list1_last->next;
    	}
    	AlgoAnyListNode * list2_last = list2;
    	while (list2_last->next != NULL)
    	{
    		list2_last = list2_last->next;
    	}
    
    	list1_last->next = list2;
    
    	list2->previous = list1_last;
    
    
    	return list1;
    }
    //将完整列表list2插入到节点lstnode之后,lstnode节点原来之后的元素,被放置到list2之后,返回值lstnode0=lstnode0+list2+lstnode1+lstnode2+...
    //如果list2只有一个节点,那么就相当于插入一个节点
    AlgoAnyListNode* AlgoAnyList_insertList(AlgoAnyListNode * lstnode, AlgoAnyListNode * list2)
    {
    	AlgoAnyListNode * lstnode_next = lstnode->next;
    	AlgoAnyListNode * list2_last = list2;
    	while (list2_last->next != NULL)
    	{
    		list2_last = list2_last->next;
    	}
    
    	lstnode->next = list2;
    
    	if (lstnode_next != NULL)
    		lstnode_next->previous = list2_last;
    
    	list2->previous = lstnode;
    
    	list2_last->next = lstnode_next;
    
    	return lstnode;
    }
    //删除一个节点,至于删除的节点,你需要自己处理(因为不知道传入的是否是new出来的,还是直接临时对象)
    //返回值:lstnode->previous
    //删除节点的父节点(如果没有父节点,那么就返回它的子节点,父子节点都没有,返回NULL)
    AlgoAnyListNode* AlgoAnyList_deleteNode(AlgoAnyListNode * lstnode)
    {
    	AlgoAnyListNode * parent = lstnode->previous;
    	AlgoAnyListNode * child = lstnode->next;
    
    	lstnode->previous = NULL;
    	lstnode->next = NULL;
    
    	if (parent == NULL && child == NULL)
    	{
    		return NULL;
    	}
    
    	if (parent == NULL)
    	{
    		child->previous = parent;
    		return child;
    	}
    	if (child == NULL)
    	{
    		parent->next = child;
    		return parent;
    	}
    	child->previous = parent;
    	parent->next = child;
    	return parent;
    }
    
    //根据链表其中一个节点,找到链表最开头的节点,如果你弄成循环链表,那就不要使用此方法
    AlgoAnyListNode * AlgoAnyList_getFirstNode(AlgoAnyListNode * lstnode)
    {
    	AlgoAnyListNode * ret = lstnode;
    	while (ret->previous != NULL)
    	{
    		ret = ret->previous;
    	}
    	return ret;
    }
    //根据链表其中一个节点,找到链表最末尾的节点,如果你弄成循环链表,那就不要使用此方法
    AlgoAnyListNode * AlgoAnyList_getLastNode(AlgoAnyListNode * lstnode)
    {
    	AlgoAnyListNode * ret = lstnode;
    	while (ret->next != NULL)
    	{
    		ret = ret->next;
    	}
    	return ret;
    }
    //检查,向后指针是否构成了循环链表
    bool AlgoAnyList_isLoopNextList(AlgoAnyListNode * lstnode)
    {
    	AlgoAnyListNode * ret = lstnode;
    	while (ret->next != NULL)
    	{
    		ret = ret->next;
    		if (ret == lstnode)
    			return true;
    	}
    	return false;
    }
    //检查,向前指针是否构成了循环链表
    bool AlgoAnyList_isLoopPreviousList(AlgoAnyListNode * lstnode)
    {
    	AlgoAnyListNode * ret = lstnode;
    	while (ret->previous != NULL)
    	{
    		ret = ret->previous;
    		if (ret == lstnode)
    			return true;
    	}
    	return false;
    }
    #endif // _ALGO_ANY_LIST_HPP_
    
    

    总结一下

    • 使用void*类型的链表
    • 好处是:
      • 任意数据类型皆可存储,下到基本数据类型,上到结构,类,甚至是容器,但是如果类型只会用一种,便得到简化
    • 坏处是:
      • 不同的数据类型存储,需要依赖于约定的数据类型表示进行识别,这样就增加了代码量
    展开全文
  • 双向链表

    2019-12-26 14:34:21
    无头结点的双向链表的一般操作。 声明 本文针对的是无头结点的双链表,而下文所出现的头结点所表示的指的是双链表的第一个结点。文中可能出现语句不当的情况,但绝不会影响读者对本文的理解,请以宽容、乐观的心态...

    无头结点的双向链表的一般操作。

    声明

    本文针对的是无头结点的双链表,而下文所出现的头结点所表示的指的是双链表的第一个结点。文中可能出现语句不当的情况,但绝不会影响读者对本文的理解,请以宽容、乐观的心态阅读本文。文中可能会出现一些错误,在此提前向读者致以歉意,并欢迎在评论区留言指正!

    说在前面

    和线性链表一样,我们无论创建怎样的双向链表都不可能装得下整个世界。所以我们考虑某一元素,用整个世界去包含该元素,虽然不能包含整个世界,但我们可用该元素去窥探世界。当然,我们可以为该元素添加其他的细枝末节,以使尽可能地包含我们所需要的信息。

    马克思说世物质是世界的本源,本源,这词实在是太抽象了,不过,还是得感谢这位英明神武的伟大无产阶级主义者的创造,因为链表创造了一部分世界,那么结点是物质的代名词。
    首先,来个结点来瞧瞧:

    typedef struct node {
        int data;
        struct node * next;
    }node, list_node;
    

    没错,它就是一个结构体,里面存放了两样东西:本结点的数据data和指向下一结点的指针next。很简陋,但无比强大,如同普通的数据类型,赋予变量预设置的属性,往下看:

    node node_1;
    node node_2;
    node node_3;
    

    由结构体node类型创建的结构体对象就是我们所谓的结点,它们毋庸置疑地包含了int型的数据类型和指向下一结点的node型指针类型。这和我们使用过的int a;具有相同的形式,只不过内部存储的数据不同而已。
    铁索连环:

    node_1->next = node_2;
    node_2->next = node_3;
    node_3->next = NULL;
    

    没有存放数据信息,但是结点连起来了,很神奇。
    虽然这样纯粹的结构体类型的确已经可以包含很多东西了,但是要想适应千变万化的世界,还需要有千变万化的结点类型;如果存在某类结点,其变化足以应付世界的变化,那么这种结点的生命力相当强大。休得多言,来个例子看看:

    typedef struct lively_node {
        int data;
        string str;
        char ch;
        my_type my_data;
        node my_node;
    }lively_node, smart_node;
    

    很明显,这样的结点具有更多的信息,如此一来,我们可以创建各种存储类型的链表,虽然通常情况下只会用到其中的几个。当然,除了C语言外,还可以用C++创建链表,创建方式大致相同,但C++可以使用模板创建链表,可以根据需求自动选择存储的数据类型。
    在线性链表中,我们已经见识到了链表的风采。我们可以在链表上插入我们想要插入的数据,从头到尾去遍历,貌似轻松愉悦,但反过来遍历呢?复杂度似乎很大。不难想到,访问尾结点,需要遍历n个结点;访问倒数第二个结点,需要遍历n-1个结点;……;直到访问头结点。这样造下去,发际线又得后移了。为什么要这个样子,太蹩脚了,终于有些聪明人在已有链表的基础上又创造出一种新的链表,双向链表,铁轨两道,中国的高铁听说又提速了。
    还记得我们在用于定义结点的结构体中放了哪些东西?整形数据和node指针,完成了单向,好的,现在我们要完成双向的链表,我们需要往这个结构体里边加点东西了,对的,需要加一个指针,方向得向前了,对吧。就是这这副德行:

    typedef struct node {
        int data;
        struct node * forward;
        struct node * next;
    }node, list_node;
    

    这个结构体就比前面的多长了一条往回走的腿。如此一来,我们现在用该结构体造个人出来向前向后都比较灵活了。试试看:

    node node_1;
    node node_2;
    node node_3;
    

    对,就是这样的,每个结构体对象都具有一个int型的数据属性、一个node型向前的指针属性和一个node型向后的指针属性。走起来吧:
    往前走:

    node_1->next = node_2;
    node_2->next = node_3;
    node_3->next = NULL;
    

    往回走:

    node_3->forward = node_2;
    node_2->forward = node_1;
    

    都说到这了,就开始创建链表和增删改查吧!
    如果对线性链表的增删改查api相当熟悉的话,那双向链表的api的实现将变得相当快速,同一个妈生的。

    链表操作

    接口是否够完善,和对链表的操作是否周全有很大关系,增删改查自是不能少了,但还有一些其他的操作也是经常需要用到的。
    0、链表之前
    1、创建结点
    2、头插法
    3、尾插法
    4、按索引插入
    5、按索引获取结点
    6、打印链表
    7、删除结点
    8、清空链表
    9、销毁链表
    感觉要干的事还很多啊!

    0、链表之前

    typedef struct list {
        int data;
        struct list * forward;
        struct list * next;
    }list, link_list;
    

    1、创建结点

    list * create(int value) {
        list * node = NULL;
    
        node = (list *)malloc(sizeof(list));
        if (node == NULL) {
            return NULL;
        }
        node->data = value;
        node->forward = NULL;
        node->next = NULL;
    
        return node;
    }
    

    我们在这个函数中干了些什么事情?首先对于函数的输入和输出,形参value就是要放进data的数据,返回的是list的结构体指针,用于和其他结点连接起来形成链表;然后就申明了一个list结构体指针对象,并为该结点分配动态空间,如果空间分配失败,则返回空指针;空间分配成功,则value的值赋给data,往前、往后的指针初始化指向空,结点创建好之后根据实际需求重新调整指向;最后将创建好的结点返回。创建结点的函数就此实现。

    2、头插法

    顾名思义,从头开始插入,插在第一个结点之前。

    int head_insert_list(list * link, int value) {
        if (link == NULL) return -1;
        list * node = NULL;
    
        node = (list *)malloc(sizeof(list));
        if (node == NULL) return -2;
        node->data = value;
        node->next = link;
        link->forward = node;
    
        return 0;
    }
    

    从函数的名称就知道我们要干什么,给函数起一个通俗易懂的名称可以提高代码的可读性,利国利民。其中输入输出参数中,形参link表示待操作的双链表,形参value表示利用头插法插入的结点的数值,返回值表示函数的错误返回码,-1表示双链表为空,-2表示创建待插入双链表的新结点时分配空间出错,0表示插入成功;使用头插法,新结点node的往后(next)指向待插入双链表的开头(link), 待插入双链表的开头(link)往前(forward)指向待插入的新结点(node)。函数完成头插法。
    说这么久都没上图,来张图吧:
    头插法
    瞧见了吧,首先创建了三个结点a,b,c,结点的值分别为1,2,3,然后通过调整指针的指向创建双链表,并链表值进行打印;接着使用头插法将值4插入双链表中,则a的前一个即为双链表的头结点,插入后的链表的打印结果如图1所示。完美!明天接着写尾插法。

    3、尾插法

    我又回来啦!现在我们来看看尾插法。和头插法相反,尾插法在链表的尾巴上添加结点。多说无益,上代码:

    int tail_insert_list(list * link, int value) {
        if (link == NULL) return -1;
        list * node = NULL;
    
        node = (list *)malloc(sizeof(list));
        if (node == NULL) return -2;
        node->data = value;
        while (link->next) {
            link = link->next;
        }
        link->next = node;
        node->next = NULL;
        node->forward = link;
    
        return 0;
    }
    

    和头插法长贼像,和尾插法的差异将暴露在光天化日之下,就多了几行代码,主要用于遍历链表,使指针指向链表尾节点,然后在尾节点加入新结点,新结点成为新的尾节点,尾节点往后(next)指向NULL,往前(forward)指向原来的尾结点。函数的输入输出和头插法类似,此处不再赘述。
    给出尾插法的效果图:
    尾插法
    OK,一起正常,接下来实现按索引插入结点。

    4、按索引插入

    集头插法和尾插法于一身的插入方式,可以在链表长度以内的任何位置插入新的结点。上代码:

    int index_insert_list(list * link, int index, int value) {
        if (link == NULL) return -1;
        list * node = NULL;
    
        node = (list *)malloc(sizeof(list));
        if (node == NULL) return -2;
        if (index == 0) {
            head_insert_list(link, value);
            return 0;
        }
        node->data = value;
        while (index - 1 && link->next) {
            link = link->next;
            index--;
        }
        if (index - 1 != 0) return -3;
        else if (link->next == NULL) {
            tail_insert_list(link, value);
            return 0;
        }
        else {
            node->next = link->next;
            link->next = node;
            node->forward = link;
            node->next->forward = node;
        }
    
        return 0;
    }
    

    很明显,按索引插入的函数返回值又多出一个错误码-3,其表示的是待插入结点的位置(index)超过了双链表的长度;当插入位置为0时,即在链表的头部插入结点,直接调用头插法插入结点即可;当插入位置为链表长度时,即在链表的尾部插入结点,直接调用尾插法插入结点即可;当插入位置在头结点和尾节点之间时,先遍历链表,移动指针至插入位置,然后插入结点即可。OK,按索引插入实现完毕。但里面涉及到头插法和尾插法函数的调用,所以这两个函数需要在该函数的作用域中。
    截图来见:
    按索引插入

    5、按索引获取结点

    比起结点的插入,结点的获取要简单的多。下面就是按索引获取结点的实现,请看代码:

    int index_print_list(list * link, int index) {
        if (link == NULL) return -1;
        while (index && link->next) {
            index--;
            link = link->next;
        }
        if (index != 0) return -3;
        printf("%d", link->data);
    
        return 0;
    }
    

    与按索引插入的返回值类似,错误码-3表示的索引值(index)超过了双链表的长度,函数将不打印任何数值,一旦索引值在双链表长度的范围内,则会打印索引对应结点的数值,当然,索引是从0开始的。
    看看效果:
    按索引获取结点

    6、打印链表

    从头结点到尾结点,打印整个双链表的数值,当然首先要指定双链表的头结点,show time!

    int print_list(list * link) {
        if (link == NULL) return -1;
        while (link) {
            printf("%d\t", link->data);
            link = link->next;
        }
        printf("\n");
    
        return 0;
    }
    

    不用多说,上个效果图:
    打印链表

    7、删除结点

    删除结点,就是和插入结点对着干,什么样的插入方式,反其道而行之,上代码:

    int index_delete_list(list * link, int index) {
        if (link == NULL) return -1;
        list * node = NULL;
    
        if (index == 0) {
            node = link;
            link = link->next;
            link->next->forward = link;
            free(node);
            node->forward = NULL;
            node->next = NULL;
            node = NULL;
    
            return 0;
        }
    
        while (index && link->next) {
            index--;
            link = link->next;
        }
        if (index != 0) return -3;
        else if (link->next == NULL) {
            node = link;
            node->forward->next = NULL;
            free(node);
            node->forward = NULL;
            node->next = NULL; 
            node = NULL;
    
            return 0;
        }
        else {
            node = link;
            node->forward->next = node->next;
            node->next->forward = node->forward;
            free(node);
            node->forward = NULL;
            node->next = NULL; 
            node = NULL;
    
            return 0;
        }
    }
    

    代码量瞬间长了好多,有没有?只有三个主要部分:删头、删尾、删中间,OK,删除结点函数大功告成。看看效果:
    删除结点
    从图中可以看出,干掉了头结点后, 头结点与之后的结点断开,即原来的双链表变成了一个结点和一个双链表,而这个双链表的头结点即为原双链表的头结点的下一个,故详情请参阅上图。

    8、清空链表

    首先需要说明,清空不带表销毁链表,而是把里边的数据值置为0,还是挺简单的!

    int clean_list(list * link) {
        if (link == NULL) return -1;
        while (link) {
            link->data = 0;
            link = link->next;
        }
    
        return 0;
    }
    

    虽然很简单,但还是上个图比较踏实:
    清空链表
    全变成0了,欣喜若狂,好吧,过于简单,没有必要!

    9、销毁链表

    与清空不同,销毁链表会彻底焚毁链表包括创建链表时临时创建的动态空间,来,上代码:

    int destroy_list(list * link) {
        if (link == NULL) return -1;
        list * node = NULL;
    
        while (link) {
            node = link->next;
            free(link);
            link->forward = NULL;
            link->next = NULL;
            link = node;
        }
    
        return 0;
    }
    

    链表被毁成了这个样子,上图:
    销毁链表
    OK,一切大功告成,请读者批评指正!

    展开全文
  • 基于双向链表的双向冒泡排序法 发布时间: 2018年11月26日 10:09 时间限制: 1000ms 内存限制: 128M 习题集源码中出现了temp->next->prior = p;本人推断这里缺少预先的对temp->next==NULL这种情况的判定,...

    基于双向链表的双向冒泡排序法

    发布时间: 2018年11月26日 10:09   时间限制: 1000ms   内存限制: 128M

    习题集源码中出现了 temp->next->prior = p; 本人推断这里缺少预先的对temp->next==NULL这种情况的判定,所以需加入一个判断语句解决。

    此为非循环的双向链表,末尾空指针没有前驱,与循环双向链表有所不同。

    描述

    有n个记录存储在带头结点的双向链表中,利用双向冒泡排序法对其按上升序进行排序,请写出这种排序的算法。(注:双向冒泡排序即相邻两趟排序向相反方向冒泡)。

    输入

    多组数据,每组数据两行。第一行为序列的长度n,第二行为序列的n个元素(元素之间用空格分隔,元素都为正整数)。当n等于0时,输入结束。

    输出

    每组数据输出一行,为从小到大排序后的序列。每两个元素之间用空格隔开。

    样例输入1
    5
    4 5 3 2 9
    6
    1 3 5 7 9 2
    0
    样例输出1
    2 3 4 5 9
    1 2 3 5 7 9
     1 //双向冒泡,最大沉底,最小冒出
     2 #include<iostream>
     3 using namespace std;
     4 typedef struct node
     5 {
     6     int data;
     7     struct node *prior, *next;
     8 }node, *LinkList;
     9 void TwoWayBubbleSort(LinkList &L)
    10 //对存储在带头结点的双向链表L中的元素进行双向起泡排序。
    11 {
    12     int exchange = 1;//设标记
    13     LinkList head = L;//双向链表头,算法过程中是向下起泡的开始结点
    14     LinkList tail = NULL;//双向链表尾,算法过程中是向上起泡的开始结点
    15     while(exchange)
    16     {
    17         LinkList p = head->next;//p是工作指针,指向当前结点
    18         exchange = 0;//假定本趟无交换
    19         while (p->next != tail)//向下(右)起泡,一趟有一最大元素沉底
    20         {
    21             if (p->data > p->next->data)//交换两结点指针,涉及6条链
    22             {
    23                 LinkList temp = p->next; exchange = 1;//有交换
    24                 p->next = temp->next; 
    25                 if(temp->next)temp->next->prior = p;//先将结点从链表上摘下
    26                 //attention!存在temp->next=NULL的可能,NULL->prior无法访问
    27                 temp->next = p; p->prior->next = temp;//将temp插到p结点前
    28                 temp->prior = p->prior; p->prior = temp;
    29                 //p = p->next;
    30             }
    31             else p = p->next;//无交换,指针后移
    32         }
    33         tail = p;//准备向上起泡
    34         p = tail->prior;
    35         while (exchange&&p->prior != head)//向上(左)起泡,一趟有一最小元素冒出
    36         {
    37 
    38             if (p->data < p->prior->data)//交换两结点指针,涉及6条链
    39             {
    40                 LinkList temp = p->prior; exchange = 1;//有交换
    41                 p->prior = temp->prior; temp->prior->next = p;
    42                 //先将temp结点从链表上摘下
    43                 temp->prior = p; p->next->prior = temp;
    44                 //将temp插到p结点后(右)
    45                 temp->next = p->next; p->next = temp;
    46             }
    47             else p = p->prior;//无交换,指针前移
    48         }
    49             head = p;//准备向下起泡
    50     }
    51 }
    52 void Create(LinkList &L, int n)
    53 {
    54     LinkList p, rear;
    55     L = new node;
    56     L->next = NULL;
    57     L->prior = NULL;
    58     rear = L;
    59     while (n--)
    60     {
    61         p = new node;
    62         cin>>p->data;
    63         p->next = rear->next;
    64         rear->next = p;
    65         p->prior = rear;
    66         rear = p;
    67     }
    68 }
    69 int main()
    70 {
    71     int n;
    72     while (true)
    73     {
    74         cin >> n;
    75         if (!n)break;
    76         else 
    77         {
    78             LinkList L;
    79             Create(L, n);
    80             TwoWayBubbleSort(L);
    81             LinkList p = L->next;
    82             while (p->next)
    83             {
    84                 cout << p->data << " ";
    85                 p = p->next;
    86             }
    87             cout << p->data << endl;
    88         }
    89         
    90     }
    91     return 0;
    92 }

    转载于:https://www.cnblogs.com/wind-chaser/p/10049548.html

    展开全文
  • 双向链表的合并

    2019-10-13 11:59:55
    A 和 b 是两双向链表。其中每一个结点存放一个整数。试编函数,将链表 b 和链表 a 合并,且去除 其中整数值相同的结点,返回合并后的链表首地址。 【做错过的点】 1.在“r = r->next;”后面还加了一句“p = p-&...

    A 和 b 是两双向链表。其中每一个结点存放一个整数。试编函数,将链表 b 和链表 a 合并,且去除 其中整数值相同的结点,返回合并后的链表首地址。

    【做错过的点】

    1.在“r = r->next;”后面还加了一句“p = p->next;”,这是致命错误,会导致结果不正确,因为与r比较的不再是第一个p了

    2.冗余代码,如下写了两次p和r的赋值语句,可以归并写到一处的

    //先将A中p所指剩余结点插入新链表中
    	while (p != NULL)
    	{
    		//用q指向p的下一个结点
    		q = p->next;
    
    		//将p与新链表A中的结点比较有无相同值
    		while (r != NULL)
    		{
    			if (r->data == p->data)
    			{
    				//若相同则删除p所指结点,取链表中下一个值
    				free(p);
    
    				p = q;//冗余
    				r = A;
    
    				break;
    			}
    			r = r->next;
    
    		}
    
    		if (r == NULL)//若无相同值
    		{
    			//将p结点插入到新链表中
    			p->next = A->next;
    			p->prior = A;
    			if (A->next != NULL)
    			{
    				A->next->prior = p;
    			}
    			A->next = p;
    
    			p = q;//冗余
    			r = A;
    		}
    
    	}

    【个人理解】

    既要把A中原来相同的元素去掉一个,还要在合并时,把与B相同的元素去掉其中一个,即重复元素中只保留一个元素

    【完整代码】

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    typedef  struct DLNode
    {
    	int data;
    	struct  DLNode *prior,*next;
    } LNode;
    
    void Print(DLNode *L)///输出函数
    {
    	DLNode *p;
    	p = L;
    	while (p != NULL)
    	{
    		printf("%d ", p->data);
    		p = p->next;
    	}
    }
    
    ///建立不带头结点的双向链表及初始化
    DLNode *CreatL(int no)
    {
    	DLNode *L = (DLNode *)malloc(sizeof(DLNode));   //申请第一个结点空间
    	L->next = NULL;                  //初始化一个空链表
    	L->prior = NULL;
    
    	DLNode *r;
    	r = L;                          //r始终指向终端结点,开始时指向首元素
    	int x;                         //x为链表数据域中的数据
    	FILE *fp;
    	char str1[100] = "data";
    	char str2[100] = ".txt";
    	char str3[100];
    	_itoa(no, str3, 10);
    	strcat(str1, str3);
    	strcat(str1, str2);
    
    	fp = fopen(str1, "r");
    	
    	if (fp == NULL)
    		exit(0);
    
    	//读取首元素
    	fscanf(fp, "%d", &x);
    	L->data = x;
    	
    
    	//读取剩余元素
    	while ((fscanf(fp, "%d", &x)) != EOF)
    	{
    
    		DLNode *p;
    		p = (DLNode *)malloc(sizeof(DLNode));   //申请新的结点
    		p->data = x;                     //结点数据域赋值
    		p->next = r->next;
    		p->prior = r;
    		r->next = p;
    		r = p;                 //将结点插入到表头L-->|1|-->|2|-->NULL
    	}
    	fclose(fp);
    	r->next = NULL;
    	return L;
    }
    
    DLNode* Merge(DLNode* A, DLNode* B)
    {
    	DLNode*r, *t, *p, *q;
    	r = A;
    	p = r->next;
    	r->next = NULL;
    	p->prior = NULL;//断开连接,单独取出A的首元素
    
    	t = B;
    
    	//先将A中p所指剩余结点插入新链表中
    	while (p != NULL)
    	{
    		//用q指向p的下一个结点
    		q = p->next;
    
    		//将p与新链表A中的结点比较有无相同值
    		while (r != NULL)
    		{
    			if (r->data == p->data)
    			{
    				//若相同则删除p所指结点,取链表中下一个值
    				free(p);
    				break;
    			}
    			r = r->next;
    		}
    
    		if (r == NULL)//若无相同值
    		{
    			//将p结点插入到新链表中
    			p->next = A->next;
    			p->prior = A;
    			if (A->next != NULL)
    			{
    				A->next->prior = p;
    			}
    			A->next = p;
    		}
    
    		p = q;
    		r = A;
    	}
    
    
    	//先将B中t所指剩余结点插入新链表中
    	r = A;
    	while (t != NULL)
    	{
    		//用q指向t的下一个结点
    		q = t->next;
    
    		//将t与新链表A中的结点比较有无相同值
    		while (r != NULL)
    		{
    			if (r->data == t->data)
    			{
    				//若相同则删除t所指结点,取链表中下一个值
    				free(t);
    				break;
    			}
    			r = r->next;
    		}
    
    		if (r == NULL)//若无相同值
    		{
    			//将p结点插入到新链表中
    			t->next = A->next;
    			t->prior = A;
    			if (A->next != NULL)
    			{
    				A->next->prior = t;
    			}
    			A->next = t;
    		}
    
    		t = q;
    		r = A;
    	}
    
    	return A;
    }
    int main()
    {
    	DLNode *A;
    	DLNode *B;
    	DLNode *C;
    	A = CreatL(1);//建立链表与初始化
    	B = CreatL(2);
    	printf("A: ");
    	Print(A);
    	printf("\n");
    
    	printf("B: ");
    	Print(B);
    	printf("\n");
    
    	C = Merge(A, B);
    
    	printf("C: ");
    	Print(C);
    
    	return 0;
    }
    /*建立一个名为data1的txt文件,将此文件放在本程序所在文件夹目录下
    文件内容:
    1
    2
    3
    4
    5
    5
    */
    /*建立一个名为data2的txt文件,将此文件放在本程序所在文件夹目录下
    文件内容:
    5
    6
    7
    8
    9
    10
    */
    

    【测试结果】

    展开全文
  • 作者最近做数据结构的习题时发现了好多关于双向链表的问题,诸如双向链表非空的判定条件,双向链表插入一个结点的四条基本语句双向链表删除一个结点的两条基本语句,判断双向链表是否为回文表的算法之类的练习题。...
  • 由此可以得出,遍历循环链表指针数据域的语句是指针所指结点或指针所指结点的后继结点是否等于头结点(或指针是否等于头指针)。  除了链表结构不同以外,其余的基本操作与单链表几乎一致,包括新建元素,增加元素...
  • 分别将BST的左、右子树转换成双向链表new出一个链表节点,值等于BST根节点的值由于是BST,所以new出的节点应该位于链表的中间,所以分别连接左、右子树转换成的链表。这一步中须要找到左链表的尾节点。 对于一些...
  • 首先,L1是一个双向链表的对象,执行完这条语句后,L1中的第二个元素变成5, 大概就跟C语言里面数组的访问方式一样,不知道我解释清楚了没有。 我遇到的问题就是,具体的函数实现在下面,但是执行完这个逻辑后,L1...
  • 文章目录单选题函数题6-1 链式表操作集 (20分)各个...在h的头上插入一个新结点t的语句是: t->next=h; h=t; 2 带头结点的单链表h为空的判定条件是: h->next == NULL; 3 对于一非空的循环单链表,h和p分别
  •  List 双向链表容器介绍 List采用双向循环的链表结构组织数据元素,链表中的每个节点包括指向前去的指针、实际数据和指向后继的指针等数据域。 C++标准头文件list:宏语句“#include ” l ...
  • 使用C++实现双向链表List

    千次阅读 2016-11-29 22:29:09
    第一:自己定义的数据结构UDT如果需要使用C++11中的范围for语句,需要定义begin和end函数。如果遍历的是常量对象,则要有相应的常量对象可用的begin和end函数。 声明形式如下: iterator begin(); const_iterator...
  • 我就奇怪了 俩个一模一样的语句 ,上边的没事 下边提示有这个错误。请高手帮看一下 这是什么原因啊 ...

空空如也

空空如也

1 2 3 4 5 ... 9
收藏数 174
精华内容 69
关键字:

双向链表语句