数据结构:链表实现增删查改的基本功能【内含详细代码,建议收藏】

发布时间:2022-07-06 发布网站:脚本宝典
脚本宝典收集整理的这篇文章主要介绍了数据结构:链表实现增删查改的基本功能【内含详细代码,建议收藏】脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。

目录

  • 前言
  • 1. 链表的概念
  • 3. 链表的结构
  • 4. 无头单向非循环链表的实现
    • 4.1 创建工程
    • 4.2 定义结构体
    • 4.3 创建一个新节点
      • 4.3.1 SList.h 声明
      • 4.3.2 SList.c 定义
    • 4.4 头插尾插操作
      • 4.4.1 SList.h 声明
      • 4.3.2 SList.c 定义
    • 4.5 头删尾删操作
      • 4.5.1 SList.h 声明
      • 4.5.2 SList.c 定义
    • 4.6 查找操作
      • 4.6.1 SList.h 声明
      • 4.6.2 SList.c 定义
    • 4.7 修改操作
      • 4.7.1 SList.h 声明
      • 4.7.2 SList.c 定义
    • 4.8 前插后插操作
      • 4.8.1 SList.h 声明
      • 4.8.2 SList.c 定义
    • 4.9 现删后删操作
      • 4.9.1 SList.h 声明
      • 4.9.2 SList.c 定义
    • 4.10 完整代码展示及运行
      • 4.10.1 SeqList.h
      • 4.10.2 SeqList.c
      • 4.10.3 test.c
      • 4.10.4 运行测试
  • 5. 带头双向循环链表的实现
    • 5.1 创建工程
    • 5.2 定义结构体
    • 5.3 创建一个新节点和创建头节点
      • 5.3.1 DList.h声明
      • 5.3.2 DList.c定义
    • 5.4 插入操作
      • 5.4.1 DList.h声明
      • 5.4.2 DList.c定义
    • 5.5 删除操作
      • 5.5.1 DList.h声明
      • 5.5.2 DList.c定义
    • 5.6 查找操作
      • 5.6.1 DList.h声明
      • 5.6.2 DList.c定义
    • 5.7 修改操作
      • 5.7.1 DList.h声明
      • 5.7.2 DList.c定义
    • 5.8 判空求长和销毁操作
      • 5.8.1 DList.h声明
      • 5.8.2 DList.c定义
    • 5.9 完整代码展示及运行
      • 5.9.1 DList.h
      • 5.9.2 DList.c
      • 5.9.3 test.c
      • 5.9.4 运行测试
  • 6. 顺序表和链表的优缺点对比
    • 6.1 顺序表的优点
    • 6.2 顺序表缺点
    • 6.3 链表优点
    • 6.4 链表缺点
    • 6.5 总结
  • 后记

前言

hello,大家好,这期文章继续用来更新数据结构方面的知识——链表。。这期文章依旧是对之前的文章数据结构F1a;红玫瑰与白玫瑰之争的补充,希望对大家有所帮助。我们在之前的文章中已经介绍过顺序表,链表和顺序表有很大的不同,相对于顺序表,链表无疑是更加灵活的。顺序表在实现过程中头部插入数据时需要挪动数据,在增容的过程中也会消耗性能,并且以倍数的方式增容也会造成空间的浪费。链表相对于顺序表而言,也许会做的更好

1. 链表的概念

链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的

通俗理解,链表就是把数据块连接起来,还方便拆卸。可以随时将数据块加入进去,或者拿出去。

数据结构:链表实现增删查改的基本功能【内含详细代码,建议收藏】

数据结构:链表实现增删查改的基本功能【内含详细代码,建议收藏】

3. 链表的结构

数据结构:链表实现增删查改的基本功能【内含详细代码,建议收藏】

在这些链表结构的组合之中,我们最常用的是两种

数据结构:链表实现增删查改的基本功能【内含详细代码,建议收藏】

  1. 无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
  2. 带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单了

4. 无头单向非循环链表的实现

4.1 创建工程

依旧采用多文件的方式

数据结构:链表实现增删查改的基本功能【内含详细代码,建议收藏】

4.2 定义结构体

tyPEdef int SLDataType;
typedef struct SListNode
{
	int data;
	struct SListNode *next;
}SLNode;
@H_770_304@ 

4.3 创建一个新节点

4.3.1 SList.h 声明

SLNode *BuySLNode(SLDataType x);

4.3.2 SList.c 定义

SLNode *BuySLNode(SLDataType x)
{
	SLNode *node = (SLNode*)malloc(sizeof(SLNode));
	node->data = x;
	node->next = NULL;
	return node;
}

数据结构:链表实现增删查改的基本功能【内含详细代码,建议收藏】

创建一个新节点会在增加操作中频繁使用,所以我们单独定义出一个函数来。创建新节点的思路就是开辟一块空间,空间里存放想要存放的数据,并使这块空间指向NULL。

4.4 头插尾插操作

注意,在头插尾插操作中,我们传递的都是二级指针。因为节点本身就是指针,我们知道按地址传参才可以改变原值,由于plist本身就是指针,要想改变它,所以我们需要传二级指针**pplist。

4.4.1 SList.h 声明

void SListPushFront(SLNode **pplist, SLDataType x);
void SListPushBack(SLNode **pplist, SLDataType x)

4.3.2 SList.c 定义

void SListPushFront(SLNode **pplist, SLDataType x)
{
	SLNode*newnode = BuySLNode(x);
	newnode->next = *pplist;
	*pplist = newnode;
}
void SListPushBack(SLNode **pplist, SLDataType x)
{
	SLNode*newnode = BuySLNode(x);
	//空和非空
	if (*pplist == NULL)
	{
		*pplist = newnode;
	}
	else
	{
		//先遍历找尾
		SLNode *tail = *pplist;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		SLNode *newnode = BuySLNode(x);
		tail->next = newnode;
	}
}

头插相对于尾插更好实现,只需要在头节点前链接上新节点就好。但是尾插则需要考虑的更多一些,实现我们要判断链表此时是否为空,如果是空则不需尾插,如果非空,我们则需要首先找到链表的尾,在尾上插入新的节点。尾插动画演示如下:

数据结构:链表实现增删查改的基本功能【内含详细代码,建议收藏】

4.5 头删尾删操作

4.5.1 SList.h 声明

void SListPopFront(SLNode **pplist);
void SListPopBack(SLNode **pplist);

4.5.2 SList.c 定义

void SListPopFront(SLNode **pplist)
{
	if (*pplist == NULL)
	{
		return;
	}
	else
	{
		SLNode *next= (*pplist)->next;
		free(*pplist);
		*pplist = next;
	}
}
void SListPopBack(SLNode **pplist)
{
	if (*pplist == NULL)
	{
		return;
	}
	else if ((*pplist)->next == NULL)
	{
		free(*pplist);
		*pplist = NULL;
	}
	else
	{
		SLNode *prev = NULL;
		SLNode *tail = *pplist;
		while (tail->next != NULL)
		{
			PRev = tail;
			tail = tail->next;
		}
		free(tail);
		tail = NULL;
		prev->next = NULL;
	}
}

头删只需要去除第一个节点,注意判断如果链表为空则不需要操作。对于尾删,依旧是要先找到尾部,还要找到尾部节点的前一个节点prev,将尾部节点释放,然后将prev置为新的尾节点。尾删动画演示如下:

数据结构:链表实现增删查改的基本功能【内含详细代码,建议收藏】

4.6 查找操作

查找操作要返回该节点的指针,注意考虑空链表的情况。

4.6.1 SList.h 声明

SLNode*SListFind(SLNode **pplist, SLDataType x);

4.6.2 SList.c 定义

SLNode*SListFind(SLNode **pplist, SLDataType x)
{
	SLNode *cur = *pplist;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

4.7 修改操作

修改操作时在查找的基础上进行的,找到要修改的值的节点,然后进行修改。注意要考虑找不到要修改的数据的情况。

4.7.1 SList.h 声明

void SListModify(SLNode *plist, SLDataType x, SLDataType y);

4.7.2 SList.c 定义

void SListModify(SLNode *plist, SLDataType x, SLDataType y)
{
	SLNode *pos = SListFind(&plist, x);
	if (pos)
	{
		pos->data = y;
	}
	else
	{
		printf("没有该数字,无法修改n");
	}
}

4.8 前插后插操作

前插后插比头插尾插更复杂一些。尤其是前插操作,需要考虑的东西会多一点。后插我们只需要在位置后加入一个新的节点,而前插则需要考虑该位置是不是头节点。如果不是头节点,还需要找到该位置并且需要找到该位置的前一个节点,将新节点插入其中。下面通过动画演示非首元素前插的情况:

数据结构:链表实现增删查改的基本功能【内含详细代码,建议收藏】

4.8.1 SList.h 声明

void SListInsertAfter(SLNode *pos, SLDataType x);
void SListInsertBefore(SLNode **pplist,SLNode *pos, SLDataType x);

4.8.2 SList.c 定义

void SListInsertAfter(SLNode *pos, SLDataType x)
{
	assert(pos);
	SLNode *newnode = BuySLNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
void SListInsertBefore(SLNode **pplist, SLNode *pos, SLDataType x)
{
	assert(pos);
	SLNode *newnode = BuySLNode(x);
	if (pos == *pplist)
	{
		newnode->next = pos;
		*pplist = newnode;
	}

	else
	{
		SLNode *prev = NULL;
		SLNode *cur = *pplist;
		while (cur != pos)
		{
			prev = cur;
			cur = cur->next;
		}
		prev->next = newnode;
		newnode->next = pos;
	}
}

4.9 现删后删操作

对于删除操作,我们再这里实现删除指定位置后的节点和指定位置的节点,因为删除指定位置之前的节点实现起来非常麻烦且意义不大。因为我们可以通过改变指定位置来实现删除前一个节点。删除指定位置后一个节点需要考虑是否为空链表。删除当前位置节点则需要考虑当前位置是否为首节点。我们在这里用动画演示删除非首节点当前节点的操作:

数据结构:链表实现增删查改的基本功能【内含详细代码,建议收藏】

4.9.1 SList.h 声明

void SListEraseAfter(SLNode*pos);
void SListEraseCur(SLNode **pplist,SLNode*pos);

4.9.2 SList.c 定义

void SListEraseAfter(SLNode*pos)
{
	assert(pos);
	if (pos->next == NULL)
	{
		return;
	}
	else
	{
		SLNode*next = pos->next;
		pos->next = next->next;
		free(next);
		next = NULL;
	}
}
void SListEraseCur(SLNode **pplist,SLNode*pos)
{
	if (pos == *pplist)
	{
		return;
	}
	else
	{
		SLNode *prev = NULL;
		SLNode *cur = *pplist;
		while (cur != pos)
		{
			prev = cur;
			cur = cur->next;
		}
		prev->next = pos->next;
		free(cur);
		cur = NULL;
	}
}

4.10 完整代码展示及运行

4.10.1 SeqList.h

#include<stdio.h>
#include<;malloc.h>
#include<assert.h>

typedef int SLDataType;
typedef struct SListNode
{
	int data;
	struct SListNode *next;
}SLNode;

//单向+带头+不循环
void SListPrint(SLNode *plist);

SLNode *BuySLNode(SLDataType x);

//二级指针
void SListPushFront(SLNode **pplist, SLDataType x);
void SListPushBack(SLNode **pplist, SLDataType x);
void SListInsertAfter(SLNode *pos, SLDataType x);
void SListInsertBefore(SLNode **pplist,SLNode *pos, SLDataType x);


void SListPopFront(SLNode **pplist);
void SListPopBack(SLNode **pplist);
void SListEraseAfter(SLNode*pos);
void SListEraseCur(SLNode **pplist,SLNode*pos);

SLNode*SListFind(SLNode **pplist, SLDataType x);
void SListModify(SLNode *plist, SLDataType x, SLDataType y);

4.10.2 SeqList.c

#include"SList.h"

void SListPrint(SLNode *plist)
{
	SLNode *cur = plist;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULLn");
}

SLNode *BuySLNode(SLDataType x)
{
	SLNode *node = (SLNode*)malloc(sizeof(SLNode));
	node->data = x;
	node->next = NULL;
	return node;
}

void SListPushFront(SLNode **pplist, SLDataType x)
{
	SLNode*newnode = BuySLNode(x);
	newnode->next = *pplist;
	*pplist = newnode;
}
void SListPushBack(SLNode **pplist, SLDataType x)
{
	SLNode*newnode = BuySLNode(x);
	//空和非空
	if (*pplist == NULL)
	{
		*pplist = newnode;
	}
	else
	{
		//先遍历找尾
		SLNode *tail = *pplist;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		SLNode *newnode = BuySLNode(x);
		tail->next = newnode;
	}
}

void SListPopFront(SLNode **pplist)
{
	if (*pplist == NULL)
	{
		return;
	}
	else
	{
		SLNode *next= (*pplist)->next;
		free(*pplist);
		*pplist = next;
	}
}
void SListPopBack(SLNode **pplist)
{
	if (*pplist == NULL)
	{
		return;
	}
	else if ((*pplist)->next == NULL)
	{
		free(*pplist);
		*pplist = NULL;
	}
	else
	{
		SLNode *prev = NULL;
		SLNode *tail = *pplist;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		tail = NULL;
		prev->next = NULL;
	}
}


SLNode*SListFind(SLNode **pplist, SLDataType x)
{
	SLNode *cur = *pplist;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}


void SListModify(SLNode *plist, SLDataType x, SLDataType y)
{
	SLNode *pos = SListFind(&plist, x);
	if (pos)
	{
		pos->data = y;
	}
	else
	{
		printf("没有该数字,无法修改n");
	}
}


void SListInsertAfter(SLNode *pos, SLDataType x)
{
	assert(pos);
	SLNode *newnode = BuySLNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
void SListInsertBefore(SLNode **pplist, SLNode *pos, SLDataType x)
{
	assert(pos);
	SLNode *newnode = BuySLNode(x);
	if (pos == *pplist)
	{
		newnode->next = pos;
		*pplist = newnode;
	}

	else
	{
		SLNode *prev = NULL;
		SLNode *cur = *pplist;
		while (cur != pos)
		{
			prev = cur;
			cur = cur->next;
		}
		prev->next = newnode;
		newnode->next = pos;
	}
}


void SListEraseAfter(SLNode*pos)
{
	assert(pos);
	if (pos->next == NULL)
	{
		return;
	}
	else
	{
		SLNode*next = pos->next;
		pos->next = next->next;
		free(next);
		next = NULL;
	}
}
void SListEraseCur(SLNode **pplist,SLNode*pos)
{
	if (pos == *pplist)
	{
		return;
	}
	else
	{
		SLNode *prev = NULL;
		SLNode *cur = *pplist;
		while (cur != pos)
		{
			prev = cur;
			cur = cur->next;
		}
		prev->next = pos->next;
		free(cur);
		cur = NULL;
	}
}

4.10.3 test.c

#include"SList.h"

void TestOne()
{
	SLNode *plist = NULL;
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPrint(plist);
	SListPushFront(&plist, 5);
	SListPushFront(&plist, 6);
	SListPrint(plist);
	SListPopBack(&plist);
	SListPrint(plist);
	SListPopFront(&plist);
	SListPrint(plist);
	SLNode *pos = SListFind(&plist, 3);
	if (pos)
	{
		printf("找到了n");
	}
	else
	{
		printf("没有找到n");
	}
	SListInsertBefore(&plist, pos, 0);
	SListInsertAfter(pos, 9);
	SListPrint(plist);
	SListEraseAfter(pos);
	SListPrint(plist);
	SListEraseCur(&plist,pos);
	SListPrint(plist);
}

int main()
{
	TestOne();
	return 0;
}

4.10.4 运行测试

数据结构:链表实现增删查改的基本功能【内含详细代码,建议收藏】

5. 带头双向循环链表的实现

5.1 创建工程

依旧采用多文件形式

数据结构:链表实现增删查改的基本功能【内含详细代码,建议收藏】

5.2 定义结构体

typedef int LDataType;
typedef struct ListNode
{
	struct ListNode*next;
	struct ListNode*prev;
	LDataType data;
}ListNode;

5.3 创建一个新节点和创建头节点

5.3.1 DList.h声明

ListNode *BuyListNode(LDataType x);
ListNode * ListCreate();

5.3.2 DList.c定义

ListNode *BuyListNode(LDataType x)
{
	ListNode*node = (ListNode*)malloc(sizeof(ListNode));
	node->next = NULL;
	node->prev = NULL;
	node->data = x;
	return node;
}
ListNode * ListCreate()
{
	ListNode*phead = BuyListNode(0);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

创建的新节点:

数据结构:链表实现增删查改的基本功能【内含详细代码,建议收藏】

创建的头节点:

数据结构:链表实现增删查改的基本功能【内含详细代码,建议收藏】

5.4 插入操作

插入操作我们要实现的有头插尾插和指定位置的插入。

5.4.1 DList.h声明

void ListPushFront(ListNode *phead, LDataType x);
void ListPushBack(ListNode *phead, LDataType x);

void ListInsert(ListNode * pos, LDataType x);

5.4.2 DList.c定义

void ListPushFront(ListNode *phead, LDataType x)
{
	assert(phead);
	ListNode*First = phead->next;
	ListNode*newnode = BuyListNode(x);
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = first;
	first->prev = newnode;
}

void ListPushBack(ListNode *phead, LDataType x)
{
	assert(phead);
	ListNode *tail = phead->prev;
	ListNode *newnode = BuyListNode(x);

	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}


void ListInsert(ListNode * pos, LDataType x)
{
	assert(pos);
	ListNode*prev = pos->prev;
	ListNode*newnode = BuyListNode(x);
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}

头插:

数据结构:链表实现增删查改的基本功能【内含详细代码,建议收藏】

尾插:

数据结构:链表实现增删查改的基本功能【内含详细代码,建议收藏】

指定位置插入:

数据结构:链表实现增删查改的基本功能【内含详细代码,建议收藏】

5.5 删除操作

删除操作我们来实现头删尾删和指定位置的删除。删除操作要考虑空链表的情况,我们用断言来判断。assert((phead->next) != phead);。如果头节点的next指向头节点,则证明链表为空。

5.5.1 DList.h声明

void ListPopFront(ListNode *phead);
void ListPopBack(ListNode *phead);

void ListErase(ListNode * pos);

5.5.2 DList.c定义

void ListPopFront(ListNode *phead)
{
	assert(phead);
	assert((phead->next) != phead);
	ListNode*first = phead->next;
	ListNode*second = first->next;
	free(first);
	first = NULL;
	phead->next = second;
	second->prev = phead;

}
void ListPopBack(ListNode *phead)
{
	assert(phead);
	assert((phead->next)!= phead);
	ListNode*tail = phead->prev;
	ListNode*tailprev = tail->prev;
	free(tail);
	tail = NULL;
	tailprev->next = phead;
	phead->prev = tailprev;
}


void ListErase(ListNode * pos)
{
	assert(pos);
	ListNode *prev = pos->prev;
	ListNode *next = pos->next;
	prev->next = next;
	next->prev = prev;
	free(pos);
	pos = NULL;

}

头删:

数据结构:链表实现增删查改的基本功能【内含详细代码,建议收藏】

尾删:

数据结构:链表实现增删查改的基本功能【内含详细代码,建议收藏】

指定位置的删除:

数据结构:链表实现增删查改的基本功能【内含详细代码,建议收藏】

5.6 查找操作

5.6.1 DList.h声明

ListNode *ListFind(ListNode *phead,LDataType x);

5.6.2 DList.c定义

ListNode *ListFind(ListNode *phead, LDataType x)
{
	assert(phead);
	ListNode*cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

5.7 修改操作

5.7.1 DList.h声明

void ListModify(ListNode*pos,LDataType x);

5.7.2 DList.c定义

void ListModify(ListNode*pos, LDataType x)
{
	assert(pos);
	pos->data = x;
}

5.8 判空求长和销毁操作

注意在进行销毁操作时,要逐个释放。并且在调用销毁操作后,将头节点置为NULL。

5.8.1 DList.h声明

int ListEmpty(ListNode *phead);
int ListSize(ListNode *phead);
void ListDestory(ListNode *phead);

5.8.2 DList.c定义

int ListEmpty(ListNode *phead)
{
	return phead->next == phead ? 1 : 0;
}
int ListSize(ListNode *phead)
{
	assert(phead);
	int size = 0;
	ListNode*cur = phead->next;
	while (cur != phead)
	{
		++size;
		cur = cur->next;
	}
	return size;
}
void ListDestory(ListNode *phead)
{
	assert(phead);
	ListNode*cur = phead->next;
	while (cur != phead)
	{
		ListNode*next = cur->next;
		free(cur);

		cur = next;
	}
	free(phead);
}

5.9 完整代码展示及运行

5.9.1 DList.h

#include<stdio.h>
#include<malloc.h>
#include<assert.h>

typedef int LDataType;
typedef struct ListNode
{
	struct ListNode*next;
	struct ListNode*prev;
	LDataType data;
}ListNode;

void ListPrint(ListNode*phead);
ListNode *BuyListNode(LDataType x);
ListNode * ListCreate();
void ListPushFront(ListNode *phead, LDataType x);
void ListPushBack(ListNode *phead, LDataType x);
void ListPopFront(ListNode *phead);
void ListPopBack(ListNode *phead);
ListNode *ListFind(ListNode *phead,LDataType x);
void ListModify(ListNode*pos,LDataType x);
void ListInsert(ListNode * pos, LDataType x);
void ListErase(ListNode * pos);
int ListEmpty(ListNode *phead);
int ListSize(ListNode *phead);
void ListDestory(ListNode *phead);

5.9.2 DList.c

#include"DList.h"


void ListPrint(ListNode*phead)
{
	ListNode *cur = phead->next;
	while (cur != phead)
	{
		printf("%d  ", cur->data);
		cur = cur->next;
	}
	printf("n");
}
ListNode *BuyListNode(LDataType x)
{
	ListNode*node = (ListNode*)malloc(sizeof(ListNode));
	node->next = NULL;
	node->prev = NULL;
	node->data = x;
	return node;
}

ListNode * ListCreate()
{
	ListNode*phead = BuyListNode(0);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

void ListPushFront(ListNode *phead, LDataType x)
{
	assert(phead);
	ListNode*first = phead->next;
	ListNode*newnode = BuyListNode(x);
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = first;
	first->prev = newnode;
}

void ListPushBack(ListNode *phead, LDataType x)
{
	assert(phead);
	ListNode *tail = phead->prev;
	ListNode *newnode = BuyListNode(x);

	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}

void ListPopFront(ListNode *phead)
{
	assert(phead);
	assert((phead->next) != phead);
	ListNode*first = phead->next;
	ListNode*second = first->next;
	free(first);
	first = NULL;
	phead->next = second;
	second->prev = phead;

}
void ListPopBack(ListNode *phead)
{
	assert(phead);
	assert((phead->next)!= phead);
	ListNode*tail = phead->prev;
	ListNode*tailprev = tail->prev;
	free(tail);
	tail = NULL;
	tailprev->next = phead;
	phead->prev = tailprev;
}


ListNode *ListFind(ListNode *phead, LDataType x)
{
	assert(phead);
	ListNode*cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
void ListModify(ListNode*pos, LDataType x)
{
	assert(pos);
	pos->data = x;
}
void ListInsert(ListNode * pos, LDataType x)
{
	assert(pos);
	ListNode*prev = pos->prev;
	ListNode*newnode = BuyListNode(x);
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}
void ListErase(ListNode * pos)
{
	assert(pos);
	ListNode *prev = pos->prev;
	ListNode *next = pos->next;
	prev->next = next;
	next->prev = prev;
	free(pos);
	pos = NULL;

}

int ListEmpty(ListNode *phead)
{
	return phead->next == phead ? 1 : 0;
}
int ListSize(ListNode *phead)
{
	assert(phead);
	int size = 0;
	ListNode*cur = phead->next;
	while (cur != phead)
	{
		++size;
		cur = cur->next;
	}
	return size;
}
void ListDestory(ListNode *phead)
{
	assert(phead);
	ListNode*cur = phead->next;
	while (cur != phead)
	{
		ListNode*next = cur->next;
		free(cur);

		cur = next;
	}
	free(phead);
}

5.9.3 test.c

#include"DList.h"

void TestOne()
{
	ListNode*plist = ListCreate();
	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);

	ListPrint(plist);

	ListPushFront(plist, 1);
	ListPushFront(plist, 2);
	ListPushFront(plist, 3);
	ListPushFront(plist, 4);

	ListPrint(plist);

	ListPopBack(plist);
	ListPopBack(plist);

	ListPrint(plist);
	ListNode*pos = ListFind(plist, 1);
	if (pos)
	{
		printf("找到了n");
	}
	else
	{
		printf("没找到n");
	}
	ListInsert(pos, 0);
	ListPrint(plist);
	ListModify(pos, 9);
	ListPrint(plist);
	ListErase(pos);
	ListPrint(plist);
	printf("%dn", ListEmpty(plist));
	printf("%dn", ListSize(plist));
	ListDestory(plist);
	plist = NULL;
}

int main()
{
	TestOne();
	return 0;
}

5.9.4 运行测试

数据结构:链表实现增删查改的基本功能【内含详细代码,建议收藏】

6. 顺序表和链表的优缺点对比

链表以带头双向循环链表为例

6.1 顺序表的优点

支持按下标访问

6.2 顺序表缺点

空间不够需要增容,有性能消耗,可能会造成空间浪费。 头部或中间插入数据需要挪动数据,效率较低。

6.3 链表优点

按需申请内存,不存在空间浪费。 在时间复杂度O(1)的时间内插入删除数据。

6.4 链表缺点

不支持下标随机访问

6.5 总结

链表和顺序表各有优缺,根据具体场景选择使用。

后记

好的,这期诚意满满干货满满的文章就先分享到这里啦。希望对大家有所帮助,也欢迎大家批评指正。

脚本宝典总结

以上是脚本宝典为你收集整理的数据结构:链表实现增删查改的基本功能【内含详细代码,建议收藏】全部内容,希望文章能够帮你解决数据结构:链表实现增删查改的基本功能【内含详细代码,建议收藏】所遇到的问题。

如果觉得脚本宝典网站内容还不错,欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。