线性表——双链表的设计思路与实现

user等级-LV9-津桥芝士平台7个月前更新
230

双链表

双链表的结构类似于单链表，但是在其结构的定义中，增加一个指向前驱节点的指针域，其定义如下：

typedef struct DulNode{
	ElemType data;
	struct DulNode *prior;    // 指向前驱节点
	struct DulNode *next;    // 指向后继节点
}DulNode, *DulLinkList;

对于ElemType ，我们假设有：

typedef int ElemType;

将int类型声明为ElemType。

双链表的初始化：

  • 对头结点进行内存分配，将头结点的前驱、后继节点指针指向空指针NULL。
  • 返回头节点指针
DulNode *InitDulList(DulLinkList L)	
{
	L = (DulNode *)malloc(sizeof(DulNode));
	if(L == NULL)
		return NULL;
		
	L->prior = NULL;    // 将前驱节点指针指向空
	L->next = NULL;    // 后继节点指针同理
	return L;
}

头插法

在链表的头部插入元素。其步骤大致为：

  • 对节点分配内存，如果分配内存失败，返回一个NULL指针。
  • 接着将元素放入数据域。
  • 将新节点的后继节点指针域指向头结点的后继指针指向的地址。
  • 如果新节点的后继节点不指向NULL，那么将新节点的后继指针指向的节点的前驱节点指针指向新节点。
  • 将新节点的前驱指针指向头节点，将头结点的后继节点指针指向新节点。

代码表述如下：

DulNode *InsertDulListHead(DulLinkList L, ElemType e)			//头插法 
{
	DulLinkList p = NULL;
	p = (DulNode *)malloc(sizeof(DulNode));
	if(p == NULL)
		return NULL;
	
	p->data = e;
	p->next = L->next;
	if(p->next != NULL)
		p->next->prior = p;
	p->prior = L;
	L->next = p;
	return p;
}

尾插法

在双链表·的尾部插入元素，其步骤大致为：

  • 先对新节点进行内存分配，如果分配内存失败返回NULL指针。
  • 接着设置一个作为缓冲节点的结点，这个结点并不作为实际的节点使用，将用作缓冲的节点指向链表尾部的节点。
  • 将数据存储进新节点的数据域。
  • 接着将新节点的后继节点指针指向缓冲节点的后继节点指针指向的地址（这个地址可能是NULL，但是不影响）。
  • 将新节点的前驱节点指针指向缓冲节点的地址。
  • 将缓冲节点的后继节点指针指向新节点的地址。

代码表述如下：

DulNode *InsertDulListTail(DulLinkList L, ElemType e)			//尾插法 
{
	DulLinkList p = NULL, q = L;
	p = (DulNode *)malloc(sizeof(DulNode));
	if(p == NULL)
		return NULL;
	
	while(q->next != NULL)
	{
		q = q->next;
	}
	p->data = e;
	p->next = q->next;
	p->prior = q;
	q->next = p;
	return p;
}

在指定位置插入元素

在指定位置插入元素，其步骤大致为：

  • 先判断待插入的位置是否正确，如果位置大于现有的元素数量，则返回一个错误标识（文中使用false）
  • 使用循环，将一个用于缓冲的指针指向插入位置的前一个节点。
  • 接着对新节点进行内存分配，如果内存分配失败，则返回错误标识。
  • 将数据存储进数据域。
  • 将新节点的后继节点指针指向缓冲节点的后继指针指向的地址。
  • 将缓冲节点的后继节点的前驱节点指针指向新节点。
  • 将新节点的前驱指针指向缓冲节点。
  • 将缓冲节点的后继指针指向新节点的地址。

代码描述大致如下：

bool InsertDulList(DulLinkList L, int pos, ElemType e)			//插入一个结点 
{
	if(pos < 1 || pos > Size(L))						//位置判断 
		return false; 
	
	int i;
	DulLinkList p = L, q = NULL;
	for(i = 1; i < pos; i++)						//将指针移动到所要插入的结点位置的前一位 
	    p = p->next;
	q = (DulNode *)malloc(sizeof(DulNode));		//分配内存
	if(q == NULL)
		return false;
	
	q->data = e;				// 将数据放入插入结点的数据域 					
    q->next = p->next;			// 将插入结点的后继指针指向插入位置原结点的地址 
	p->next->prior = q;			// 将插入位置的结点的前驱指针指向新结点的地址 
	q->prior = p;				// 将插入结点的前驱指针指向插入位置的前一个结点地址 
	p->next = q;			    // 将插入位置的前一个结点的后继指针指向新的结点 
	return true; 
}

获取元素的数量

获取元素的数量大致设计思路如下：

  • 设置一个变量用于计数，在设置一个缓冲节点，并将其指向头结点的后继指针指向的地址。
  • 如果缓冲节点为空，说明已经遍历结束了双链表。
  • 遍历双链表，每通过一个节点计数的变量自增1
  • 返回计数变量的数值。

代码描述如下：

int Size(DulLinkList L)			//查询双链表中的元素数量 
{
	int count = 0;				//用于计数 
	DulLinkList p = L->next;
	while(p != NULL)
	{
		++count;
		p = p->next;
	}
	return count;
}

查询双链表是否为空

如果头结点的后继节点指针指向了NULL，说明双链表为空。

代码描述如下：

bool EmptyDulList(DulLinkList L)			//判断双链表是否为空 
{
	if(L->next == NULL)						//判断头结点的后继指针是否指空 
	    return true;
	return false;
}

查询某个位置的值

按位置查找，大致流程如下：

  • 先判断查找位置是否合法，如果位置小于1或者是大于现有的元素数量，则返回错误标识。
  • 设置一个缓冲节点，将节点指向头结点的后继节点地址，设置一个用于计数的变量。
  • 遍历链表，当计数的变量数值（从1开始计数）达到了指定数值，遍历结束。
  • 此时的缓冲节点指向的就是目标位置的结点，访问数据域即可。

代码的设计思路如下：

bool GetElem(DulLinkList L, int pos, ElemType *data)			//按位置查找
{
	if(pos < 1 || pos > Size(L))		//判断位置是否正确 
	{
		data = NULL;
		return false;
	}
	int i;
	DulLinkList p = L->next;
	for(i = 1; i < pos; i++)
	    p = p->next;
	*data = p->data;
	return true;
}

查找双链表中第一个指定的值

对于查询，设计思路大致如下：

  • 设置一个用于记录位置的变量，设置一个缓冲节点并指向头结点的后继节点指针指向的地址。
  • 遍历整个双链表，如果缓冲节点指向了空或者是缓冲节点的数据域与待查找的值相等，则返回计数变量或者是其他标识。
  • 当遍历结束了还未能找到，返回失败/错误标识。

代码实现如下：

int FindFirst(DulLinkList L, ElemType e)			//按值查找 
{
    int i = 0;
	DulLinkList p = L->next;
	while(p != NULL)
	{
		++i;
		if(p->data == e)
			return i;
		
		p = p->next;
	}
	return -1;
}

打印双链表的数据

打印双链表中的数据域，本例数据域以int为例

  • 设置一个缓冲节点，将节点指向头结点，
  • 遍历整个双链表，如果缓冲节点的后继节点指针指向空，则说明遍历到最后一个元素。

代码实现如下：

void DisplayDulList(DulLinkList L)			//打印双链表元素 
{
	DulLinkList p = L;
	while(p->next != NULL)
	{   
	    p = p->next;
		printf("%5d\n", p->data);
	}
	return;
}

修改某个位置的元素的数据域

修改节点中的数据域步骤大致如下：

  • 先判断待修改的位置是否合法，如果位置合法则进行下一步
  • 设置一个缓冲节点，并将其指向头节点的后一个节点。
  • 通过循环，将缓冲节点指向待修改的位置。
  • 修改数据域。

代码实现如下：

bool ChangeElem(DulLinkList L, int pos, ElemType e)			//将某个位置的元素的值修改 
{
	if(pos < 1 || pos > Size(L))						//位置判断 
	{
		return false;
	}
	int i;
	DulLinkList p = L->next;
	for(i = 1; i < pos; i++)
	    p = p->next;
	p->data = e;
	return true;
}

删除一个指定位置的节点

删除一个节点的大致步骤如下：

  • 先判断待删除的位置是否合法，不合法则返回错误标识。
  • 设置一个缓冲节点并将其指向头结点。
  • 通过循环遍历到指定位置。
  • 将缓冲节点的前驱节点的后继节点指针指向缓冲节点后继指针指向的地址。
  • 如果缓冲节点的后继节点指针不指向空，则将缓冲节点后继节点的前驱节点指针指向缓冲节点前驱节点指针指向的地址。
  • 释放缓冲节点的内存。、

实现代码大致如下：

bool DeleteElem(DulLinkList L, int pos)			//按位删除 
{
	if(pos < 1 || pos > Size(L))
		return false;
	
	int i; 
    DulLinkList p = L;
	for(i = 1; i <= pos; i++)				// 将指针移动到所删除的结点的前驱结点
	    p = p->next;
	
	p->prior->next = p->next;
	if(p->next != NULL)
	    p->next->prior = p->prior;
    free(p);
    return true;
}

销毁双链表

销毁双联办的步骤大致如下：

  • 先设置两个缓冲节点。
  • 其中一个节点指向头节点，我们将这个节点视为缓冲节点1，另外一个则指向NULL，我们将其标识为缓冲节点2。
  • 将节点1的地址赋值给节点2，将节点1指向其后继节点指针指向的地址，释放掉节点2的内存。
  • 通过循环重复上一步，直到节点1指向NULL.

代码实现如下：

void DestoryDulList(DulLinkList L)			//销毁双链表 
{
	DulLinkList p = L, q;
	while(p != NULL)
	{
		q = p;
		p = p->next;				//移动指针 
		free(q);
	}
	L = NULL;
}

总体代码

注：因作者精力有限，代码仅通过编译运行，但并未通过实际的函数调用测试，故可能存在未知的bug。

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

typedef int ElemType;

typedef struct DulNode{
	ElemType data;
	struct DulNode *prior;
	struct DulNode *next;
}DulNode, *DulLinkList;

int Size(DulLinkList L)			//查询双链表中的元素数量 
{
	int count = 0;				//用于计数 
	DulLinkList p = L->next;
	while(p != NULL)
	{
		++count;
		p = p->next;
	}
	return count;
}

DulNode *InitDulList(DulLinkList L)			//初始化头结点 
{
	L = (DulNode *)malloc(sizeof(DulNode));
	if(L == NULL)
		return NULL;
		
	L->prior = NULL;
	L->next = NULL;
	return L;
}

DulNode *InsertDulListHead(DulLinkList L, ElemType e)			//头插法 
{
	DulLinkList p = NULL;
	p = (DulNode *)malloc(sizeof(DulNode));
	if(p == NULL)
		return NULL;
	p->data = e;
	p->next = L->next;
	if(p->next != NULL)
		p->next->prior = p;
	p->prior = L;
	L->next = p;
	return p;
} 

DulNode *InsertDulListTail(DulLinkList L, ElemType e)			//尾插法 
{
	DulLinkList p = NULL, q = L;
	p = (DulNode *)malloc(sizeof(DulNode));
	if(p == NULL)
		return NULL;
	
	while(q->next != NULL)
	{
		q = q->next;
	}
	p->data = e;
	p->next = q->next;
	p->prior = q;
	q->next = p;
	return p;
}

bool InsertDulList(DulLinkList L, int pos, ElemType e)			//插入一个结点 
{
	if(pos < 1 || pos > Size(L))						//位置判断 
		return false; 
	
	int i;
	DulLinkList p = L, q = NULL;
	for(i = 1; i < pos; i++)						//将指针移动到所要插入的结点位置的前一位 
	    p = p->next;
	q = (DulNode *)malloc(sizeof(DulNode));		//分配内存
	if(q == NULL)
		return false;
	
	q->data = e;				// 将数据放入插入结点的数据域 					
    q->next = p->next;			// 将插入结点的后继指针指向插入位置原结点的地址 
	p->next->prior = q;			// 将插入位置的结点的前驱指针指向新结点的地址 
	q->prior = p;				// 将插入结点的前驱指针指向插入位置的前一个结点地址 
	p->next = q;			    // 将插入位置的前一个结点的后继指针指向新的结点 
	return true; 
}

void DestoryDulList(DulLinkList L)			//销毁双链表 
{
	DulLinkList p = L, q;
	while(p != NULL)
	{
		q = p;
		p = p->next;				//移动指针 
		free(q);
	}
	L = NULL;
}

bool DeleteElem(DulLinkList L, int pos)			//按位删除 
{
	if(pos < 1 || pos > Size(L))
		return false;
	
	int i; 
    DulLinkList p = L;
	for(i = 1; i <= pos; i++)				// 将指针移动到所删除的结点的前驱结点
	    p = p->next;
	
	p->prior->next = p->next;
	if(p->next != NULL)
	    p->next->prior = p->prior;
    free(p);
    return true;
}

bool ChangeElem(DulLinkList L, int pos, ElemType e)			//将某个位置的元素的值修改 
{
	if(pos < 1 || pos > Size(L))						//位置判断 
	{
		return false;
	}
	int i;
	DulLinkList p = L->next;
	for(i = 1; i < pos; i++)
	    p = p->next;
	p->data = e;
	return true;
}

bool EmptyDulList(DulLinkList L)			//判断双链表是否为空 
{
	if(L->next == NULL)						//判断头结点的后继指针是否指空 
	    return true;
	return false;
}

bool GetElem(DulLinkList L, int pos, ElemType *data)			//按位置查找
{
	if(pos < 1 || pos > Size(L))		//判断位置是否正确 
	{
		data = NULL;
		return false;
	}
	int i;
	DulLinkList p = L->next;
	for(i = 1; i < pos; i++)
	    p = p->next;
	*data = p->data;
	return true;
} 

int FindFirst(DulLinkList L, ElemType e)			//按值查找 
{
    int i = 0;
	DulLinkList p = L->next;
	while(p != NULL)
	{
		++i;
		if(p->data == e)
			return i;
		
		p = p->next;
	}
	return -1;
}

void DisplayDulList(DulLinkList L)			//打印双链表元素 
{
	DulLinkList p = L;
	while(p->next != NULL)
	{   
	    p = p->next;
		printf("%5d\n", p->data);
	}
	return;
}

int main()
{
	return 0;
}
评分
欢迎为Ta评分
赞赏
分享
请登录后发表评论

    没有回复内容

发布文章发布帖子
在手机上浏览此页面
工作时间
全周无休：9:00-23:00
欢迎大家骚扰
zibll子比主题
本站同款主题模板
zibll子比主题是一款漂亮优雅的网站主题模板，功能强大，配置简单。
查看详情