本科课程【数据结构与算法】实验2——单链表与双向循环链表的插入、删除操作(C++实现）

2022-11-16 09:47:08

大家好，我是【1+1=王】，热爱java的计算机（人工智能）渣硕研究生在读。
如果你也对java、人工智能等技术感兴趣，欢迎关注，抱团交流进大厂！！！
Good better best, never let it rest, until good is better, and better best.

近期会把自己本科阶段的一些课程设计、实验报告等分享出来，供大家参考，希望对大家有帮助。

博客更新至专栏【课程设计实验报告】：https://blog.csdn.net/weixin_43598687/category_11640051.html

一、实验目的

掌握线性表的链表表示；
实现单链表的插入操作
实现单链表的删除操作
实现双向链表的插入操作
实现双向链表的删除操作

二、实验内容

1. 实验任务

a. 完成单链表的建立、插入和删除
b. 完成双向链表的建立、插入和删除

2. 程序设计

1）数据输入（输入哪些数据、个数、类型、来源、输入方式）
节点个数：count；
节点元素值：temp；
要插入节点的位置和数值：num1、Data；
要删除节点的位置：num2；
2）数据存储（输入数据在内存中的存储）
动态分配内存（pNode pNew = (pNode)malloc(sizeof(Node));）
3）数据处理（说明处理步骤。若不是非常简单，需要绘制流程图）

4）数据输出（贴图：程序运行结果截图。图幅大小适当，不能太大）

三、实验环境

操作系统：WINDOWS 10
开发工具：VC++ 2013
实验设备：PC

四、源代码

1. 单链表的插入删除操作

pNode CreatList(); //创建链表函数
void TravelseList(pNode); //遍历链表函数
bool Insert_Node(pNode, int, int); //插入节点
int Del_Node(pNode, int); //删除节点

#include<iostream>
using namespace std;

typedef struct node
{
	int data;
	struct node *pNext;
}Node, *pNode;

pNode CreatList();                                       //创建链表函数
void TravelseList(pNode);                              //遍历链表函数
bool Insert_Node(pNode, int, int);                      //插入节点
int Del_Node(pNode, int);                               //删除节点

int main()
{
	pNode pHead = NULL;        //struct Node *pHead=NULL
	int Data;
	int num;

	pHead = CreatList();

	TravelseList(pHead);
	cout << "输入要插入的位置和数据：";
	cin >> num >> Data;
	Insert_Node(pHead, num, Data);
	TravelseList(pHead);
	cout << "输入要删除的位置：";
	cin >> num;
	Del_Node(pHead, num);
	TravelseList(pHead);
	system("pause");
	return 0;
}


//创建链表
pNode CreatList()
{
	int count;                                           //节点个数
	int temp;                                            //临时存储用户输入的节点的数据
	pNode pHead = (pNode)malloc(sizeof(Node));            //不存放有效数据的头结点
	pNode pTail = pHead;                                   //链表的最后一个节点
	pTail->pNext = NULL;                                  //最后一个节点指针置为空

	cout << "输入节点个数" << endl;
	cin >> count;
	for (int i = 0; i < count; i++)
	{
		cout << "输入第" << i + 1 << "个节点的数值" << endl;
		cin >> temp;
		pNode pNew = (pNode)malloc(sizeof(Node));         //给新节点分配空间
		pNew->data = temp;
		pTail->pNext = pNew;
		pNew->pNext = NULL;
		pTail = pNew;
	}
	return pHead;
}

void TravelseList(pNode pHead)
{
	cout << "链表的数据如下：";
	pNode p = pHead->pNext;
	while (p != NULL)
	{
		cout << p->data << " ";
		p = p->pNext;
	}
	cout << endl;
	return;
}

//插入
bool Insert_Node(pNode pHead, int front, int Data)
{
	int i = 0;
	pNode _node = pHead;
	pNode pSwap;                                   //交换指针
	if ((front < 1) && (_node != NULL))
	{
		return false;
	}
	while (i < front - 1)
	{
		_node = _node->pNext;
		++i;
	}
	pNode pNew = (pNode)malloc(sizeof(Node));
	pNew->data = Data;
	pSwap = _node->pNext;
	pNew = _node->pNext;
	pSwap = pNew->pNext;
	return true;
}

//删除
int Del_Node(pNode pHead, int back)
{
	int i = 0;
	int Data;
	pNode _node = pHead;
	pNode pSwap;
	if ((back < 1) && (NULL == _node->pNext))
	{
		printf("删除失败！\n");
		return 0;
	}
	while (i < back - 1)
	{
		_node = _node->pNext;
		++i;
	}
	pSwap = _node->pNext;
	Data = pSwap->data;
	_node->pNext = _node->pNext->pNext;
	free(pSwap);
	return Data;
}

2. 双向循环链表的插入删除操作

头文件

#ifndef _DOUBLELINKLIST_H_
#define _DOUBLELINKLIST_H_


//
// 在此处包含 C 标准库头文件
//

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


//
// 在此处包含其他头文件
//




//
// 在此处定义数据结构
//

typedef int ElemType;	// 链表中元素的类型

typedef struct DuLNode {
	ElemType data;			// 数据域
	struct DuLNode* prior;	// 前趋指针
	struct DuLNode* next;	// 后继指针
}DuLinkList;


//
// 在此处声明函数
//

int InsertBefore(DuLinkList* pListHead, int i, ElemType Elem);
int Delete(DuLinkList* pListHead, int i, ElemType* pElem);


#endif /* _DOUBLELINKLIST_H_ */

cpp文件

#include "DoubleLinkList.h"
#include<iostream>

using namespace std;


int main(int argc, char* argv[])
{
	int i;
	ElemType Elem;
	DuLinkList* pListHead;	// 双向循环链表的表头指针，指向表头节点
	DuLinkList* pListNode;	// 双向循环链表节点指针

	//
	// 初始化双向循环链表的表头节点
	//
	pListHead = (DuLinkList*)malloc(sizeof(DuLinkList));
	pListHead->prior = pListHead;
	pListHead->next = pListHead;

	//
	// 初始化双向循环链表的节点
	//
	for (i = 8; i>0; i--)
	{
		pListNode = (DuLinkList*)malloc(sizeof(DuLinkList));
		pListNode->data = i;

		pListNode->next = pListHead->next;
		pListNode->prior = pListHead;
		pListHead->next->prior = pListNode;
		pListHead->next = pListNode;
	}

	//
	// 在第 i 个节点之前插入一个节点
	//
	InsertBefore(pListHead, 3, 88);
	InsertBefore(pListHead, 20, 15);		// 插入位置非法。插入失败。

	//
	// 删除第 i 个节点
	//
	Delete(pListHead, 3, &Elem);
	Delete(pListHead, 20, &Elem);		// 删除位置非法。删除失败。


	//
	// 销毁双向循环链表
	//
	while (pListHead->next != pListHead)
	{
		pListNode = pListHead->next;
		pListHead->next = pListNode->next;
		pListNode->next->prior = pListHead;

		free(pListNode);
	}
	free(pListHead);

	return 0;
}

/*
功能：
在第 i 个节点之前插入一个节点。

参数：
pListHead -- 双向循环链表的表头指针
i -- 插入节点的位置。从 1 开始计数。
Elem -- 插入节点的值。

返回值：
如果插入成功返回 1
如果插入失败返回 0
*/
int InsertBefore(DuLinkList* pListHead, int i, ElemType Elem)
{
	DuLinkList* pListNode=NULL;			// 节点指针

	//
	// TODO: 在此添加代码
	//
	if (i <= 0 && i > 8)
		cout << "插入非法" << endl;
	else
	{
		DuLinkList* s = (DuLinkList*)malloc(sizeof(DuLNode));
		s->data = Elem;
		s->prior = pListNode->prior;
		pListNode->prior->next = s;
		s->next = pListNode;
		pListNode->prior = s;
	}

	return 0;
}

/*
功能：
删除第 i 个节点。

参数：
pListHead -- 双向循环链表的表头指针
i -- 删除节点的位置。从 1 开始计数。
pElem -- 返回被删除节点的值。

返回值：
如果删除成功返回 1
如果删除失败返回 0
*/
int Delete(DuLinkList* pListHead, int i, ElemType* pElem)
{
	DuLinkList* pListNode;			// 节点指针

	//
	// TODO: 在此添加代码
	//	

	if (i <= 0 && i > 8)
		cout << "插入非法" << endl;
	else
	{
		pElem = pListNode->data;
		pListNode->prior->next = pListNode->next;
		pListNode->next->prior = pListNode->prior;
		free(pListNode);
	}
	return 0;
}

博客更新至专栏【课程设计实验报告】：https://blog.csdn.net/weixin_43598687/category_11640051.html

码农公寓

一、 实验目的

二、 实验内容