当前位置： 首页 > news >正文

数据结构——实验01-线性表的链式存储和操作

news 2025/8/15 21:19:22

一、实验内容

二、算法思想与算法实现

1、解题思想

（1）逆序创建链表La就是使用头插法创建一个链表，所谓头插法就是在创建链表时始终将新元素插入到头结点之后，而正序创建链表Lb就是使用尾插法创建一个链表，所谓尾插法创建一个链表就是在创建链表时始终将新元素插入到表尾

（2）合并两个升序序列，这个算法很基础，这里不做叙述，需要注意的是由于在创建La时我们是逆序创建的，也就是说此时La是降序排列，所以在做两个链表的合并操作之前我们需要先将链表La逆置

（3）删除Lc中的多余元素：这里我们可以用一个指针p表示当前链表的结点，然后用一个指针t指向第一个结点元素值不等于当前结点元素值的结点，然后让结点p的next指针域指向t即可，如下图所示

（4）逆置一个链表，可以借助头插法创建链表的思想，即扫描当前需要逆置的链表不断将当前结点插入到表头

2、算法实现

（1）定义链表结点

//定义链表节点
typedef struct LNode {int data;                          //数据域struct LNode* next;                //指针域
}LNode,*LinkList;

（2）头插法创建链表

//使用头插法创建一个带头结点的链表，当用户输入666时表示链表创建结束
bool List_HeadInsert(LinkList& L) {//对链表进行初始化操作L = (LNode*)malloc(sizeof(LNode) * 1);if (L == NULL){return false;}L->next = NULL;LNode* p = NULL;int inputs = 0;printf("请输入链表元素:\n");while (1){scanf("%d", &inputs);if (inputs == 666)break;p = (LNode*)malloc(sizeof(LNode) * 1);if (p == NULL){return false;}p->data = inputs;p->next = L->next;L->next = p;}return true;
}

 （3）尾插法创建链表


//使用尾插法创建一个带头结点的链表，当用户输入666时表示链表创建结束
bool List_TailInsert(LinkList& L)
{//对链表进行初始化操作L = (LNode*)malloc(sizeof(LNode) * 1);if (L == NULL)return false;L->next = NULL;LNode* p, * t;   //p指针用于建立新结点，t用于指向当前链表的尾结点int inputs;t = L;printf("请输入链表元素:\n");while (1){scanf("%d", &inputs);if (inputs == 666)break;p = (LNode*)malloc(sizeof(LNode) * 1);if (p == NULL)return false;p->data = inputs;p->next = NULL;t->next = p;t = p;}return true;
}

（4）合并两个升序链表

//合并两个有序链表
bool Merge_SortedLinkList(LinkList La, LinkList Lb, LinkList& Lc)
{LNode* a, * b, * c, * t;a = La->next;b = Lb->next;//初始化链表Lc；Lc = (LNode*)malloc(sizeof(LNode) * 1);if (Lc == NULL)return false;Lc->next = NULL;t = Lc;          //t指针指向Lc的尾部结点while (a != NULL && b != NULL){c = (LNode*)malloc(sizeof(LNode) * 1);if (c == NULL)return false;if (a->data <= b->data){c->data = a->data;c->next = NULL;t->next = c;t = c;a = a->next;}else{c->data = b->data;c->next = NULL;t->next = c;t = c;b = b->next;}}while (a == NULL && b != NULL){c = (LNode*)malloc(sizeof(LNode) * 1);c->data = b->data;c->next = NULL;t->next = c;t = c;b = b->next;}while (b == NULL && a != NULL){c = (LNode*)malloc(sizeof(LNode) * 1);c->data = a->data;c->next = NULL;t->next = c;t = c;a = a->next;}return true;
}

（5）删除链表中的重复元素

//删除有序链表中的重复元素
bool DeleteRpeatElem(LinkList& L)
{//判断是否是空表if (L->next == NULL)return false;LNode* p, * e = NULL;   //p指针用于记录当前结点，e指针用于表示值等于当前结点的最后一个结点p = L->next;while (p != NULL){e = p->next;if (e == NULL)break;while (p->data == e->data){LNode* temp = e;e = e->next;free(temp);}p->next = e;p = p->next;	}return true;
}

（6）逆置一个链表

//逆置一个链表，从头开始扫描一个链表，不断将当前结点插入到链表的开始位置
bool ReverseLinkList(LinkList& L)
{if (L->next == NULL)return false;LNode* end = L->next;  //指向逆置以后的表尾元素LNode* p = end->next;  //指向当前元素while (p != NULL){LNode* temp = p->next;p->next = L->next;L->next = p;p = temp;}end->next = NULL;return true;
}

三、代码测试

完整测试代码：

//用C语言编写程序，其中Lb={2,4,6,8,10} La={1,2,3,4,5,6,8},
//(1)逆序创建链表La, 正序创建链表Lb; .
//(2)将La与Lb有序合并，得到有序链表Lc：Lc = { 1,2,2,3,4,4,5,6,6,8,8,10 }
//(3)删除Lc中多余的重复元素，使得所有元素只保留一个;
//(4)将链表Lc倒置，并输出其内容。#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
using namespace std;//定义链表节点
typedef struct LNode {int data;                          //数据域struct LNode* next;                //指针域
}LNode,*LinkList;//使用头插法创建一个带头结点的链表，当用户输入666时表示链表创建结束
bool List_HeadInsert(LinkList& L) {//对链表进行初始化操作L = (LNode*)malloc(sizeof(LNode) * 1);if (L == NULL){return false;}L->next = NULL;LNode* p = NULL;int inputs = 0;printf("请输入链表元素:\n");while (1){scanf("%d", &inputs);if (inputs == 666)break;p = (LNode*)malloc(sizeof(LNode) * 1);if (p == NULL){return false;}p->data = inputs;p->next = L->next;L->next = p;}return true;
}//使用尾插法创建一个带头结点的链表，当用户输入666时表示链表创建结束
bool List_TailInsert(LinkList& L)
{//对链表进行初始化操作L = (LNode*)malloc(sizeof(LNode) * 1);if (L == NULL)return false;L->next = NULL;LNode* p, * t;   //p指针用于建立新结点，t用于指向当前链表的尾结点int inputs;t = L;printf("请输入链表元素:\n");while (1){scanf("%d", &inputs);if (inputs == 666)break;p = (LNode*)malloc(sizeof(LNode) * 1);if (p == NULL)return false;p->data = inputs;p->next = NULL;t->next = p;t = p;}return true;
}//合并两个有序链表
bool Merge_SortedLinkList(LinkList La, LinkList Lb, LinkList& Lc)
{LNode* a, * b, * c, * t;a = La->next;b = Lb->next;//初始化链表Lc；Lc = (LNode*)malloc(sizeof(LNode) * 1);if (Lc == NULL)return false;Lc->next = NULL;t = Lc;          //t指针指向Lc的尾部结点while (a != NULL && b != NULL){c = (LNode*)malloc(sizeof(LNode) * 1);if (c == NULL)return false;if (a->data <= b->data){c->data = a->data;c->next = NULL;t->next = c;t = c;a = a->next;}else{c->data = b->data;c->next = NULL;t->next = c;t = c;b = b->next;}}while (a == NULL && b != NULL){c = (LNode*)malloc(sizeof(LNode) * 1);c->data = b->data;c->next = NULL;t->next = c;t = c;b = b->next;}while (b == NULL && a != NULL){c = (LNode*)malloc(sizeof(LNode) * 1);c->data = a->data;c->next = NULL;t->next = c;t = c;a = a->next;}return true;
}//删除有序链表中的重复元素
bool DeleteRpeatElem(LinkList& L)
{//判断是否是空表if (L->next == NULL)return false;LNode* p, * e = NULL;   //p指针用于记录当前结点，e指针用于表示值等于当前结点的最后一个结点p = L->next;while (p != NULL){e = p->next;if (e == NULL)break;while (p->data == e->data){LNode* temp = e;e = e->next;free(temp);}p->next = e;p = p->next;	}return true;
}//逆置一个链表，从头开始扫描一个链表，不断将当前结点插入到链表的开始位置
bool ReverseLinkList(LinkList& L)
{if (L->next == NULL)return false;LNode* end = L->next;  //指向逆置以后的表尾元素LNode* p = end->next;  //指向当前元素while (p != NULL){LNode* temp = p->next;p->next = L->next;L->next = p;p = temp;}end->next = NULL;return true;
}//顺序打印一个链表中的所有元素
bool PrintLinkList(LinkList L)
{if (L->next == NULL)return false;LNode* p = L->next;while (p != NULL){printf("%d\t", p->data);p = p->next;}printf("\n");return true;
}//测试程序
int main()
{LinkList La, Lb, Lc;//逆序创建链表La,即使用头插法创建链表LaList_HeadInsert(La);printf("链表La：\n");PrintLinkList(La);//正序创建链表Lb，即使用尾插法创建链表LbList_TailInsert(Lb);printf("链表Lb：\n");PrintLinkList(Lb);//合并La和Lb//先逆序LaReverseLinkList(La);printf("逆序后的链表La：\n");PrintLinkList(La);//调用函数合并La和LbMerge_SortedLinkList(La, Lb, Lc);printf("合并链表La和链表Lb得到的链表Lc：\n");PrintLinkList(Lc);//删除Lc中的重复元素DeleteRpeatElem(Lc);printf("删除链表Lc中的重复元素的结果：\n");PrintLinkList(Lc);//将Lc逆序ReverseLinkList(Lc);printf("将链表Lc逆序之后的结果：\n");PrintLinkList(Lc);return 0;}

测试结果截图：

http://www.lryc.cn/news/293037.html

相关文章：

  • 十分钟上手vue！
  • day37WEB攻防-通用漏洞XSS跨站权限维持钓鱼捆绑浏览器漏洞
  • 【Java程序设计】【C00215】基于SSM的勤工助学管理系统（论文+PPT）
  • c#的反汇编对抗
  • 设计模式之框架源码剖析（实战+图解）
  • SQL注入：sqli-labs靶场通关（1-37关）
  • 浙政钉（专有钉钉）
  • 【lesson2】定长内存池的实现
  • C++迷宫游戏详解
  • java下载网络文件
  • 大数据信用报告查询费用一般要多少钱?
  • 【操作宝典】IntelliJ IDEA新建maven项目详细教程
  • 【Java程序设计】【C00196】基于（JavaWeb+SSM）的旅游管理系统（论文+PPT）
  • pdmodel从动态模型转成静态onnx
  • git 如何修改仓库地址
  • 基于springboot篮球论坛系统源码和论文
  • 【三维重建】运动恢复结构（SfM）
  • Android Studio非UI线程修改控件——定时器软件
  • canvas的一些基础
  • C++（10）——类与对象（最终篇）
  • NetApp FAS2750 和 FAS2820 简化分布式企业的存储
  • Geogebra设置函数定义域
  • 代码随想录刷题笔记 DAY 18 | 找树左下角的值 No.513 | 路经总和 No.112 | 从中序与后序遍历序列构造二叉树 No.106
  • 【algorithm】一个简单的PID工程 base 用于手生时候快速复习 用于设计模式 cpp语法八股 快速复习校验
  • Python处理图片生成天际线（2024.1.29）
  • jsp服装穿搭推荐系统Myeclipse开发mysql数据库web结构java编程计算机网页项目
  • Opencv(C++)学习 之RV1126平台的OPENCV交叉编译
  • http和https区别
  • 富文本编辑器CKEditor4简单使用-05（开发自定义插件入门）
  • chisel之scala 语法