心得技巧
html5HTML/XhtmlCSSXML/XSLTDreamweaver教程Frontpage教程心得技巧

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

发布时间：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 @R_126_2187@.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. 链表的概念

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

@H_360_228@

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

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

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

3. 链表的结构

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

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

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

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

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

4.1 创建工程

依旧采用多文件的方式

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

4.2 定义结构体

tyPEdef int SLDataType;
typedef struct SListNode
{
	int data;
	struct SListNode *next;
}SLNode;
@H_256_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，请注明来意。
标签：capjavalistmacphppythonStringwhilewhile查找查找程序员程序员遍历遍历面试面试
猜你在找的心得技巧相关文章
其他相关热搜词更多
phpjavapython程序员loadpost-format-gallerydivString参数开发ListcapMapClass工具安装SQL数据库资源this
全站导航更多
html5HTML/XhtmlCSSXML/XSLTDreamweaver教程Frontpage教程心得技巧JavaScriptASP.NETPHP编程正则表达式AJAX相关ASP编程JSP编程编程10000问CSS/HTMLFlexvbsDOS/BAThtahtcpythonperl游戏相关VBA远程脚本ColdFusionMsSqlMysqlmariadboracleDB2mssql2008mssql2005SQLitePostgreSQLMongoDB星外虚拟主机华众虚拟主机Linuxwin服务器FTP服务器DNS服务器Tomcatnginxzabbix云和虚拟化bios系统安装系统系统进程Windows系列LINUXRedHat/CentosUbuntu/DebianFedoraSolaris红旗Linux建站经验微信营销网站优化网站策划网络赚钱网络创业站长故事alexa域名photoshop教程摄影教程Fireworks教程CorelDraw教程Illustrator教程Painter教程Freehand教程IndesignSketch笔记本主板内存CPU存储显卡显示器光存储鼠标键盘平板电脑安全教程杀毒防毒安全设置病毒查杀脚本攻防入侵防御工具使用业界动态Exploit漏洞分析
最新心得技巧教程
热门心得技巧教程