ps: 滴~
打卡第二天，好困啊~~~~~~

数据结构实验二——单链表的基本操作

一、实验目的

了解线性表的链式存储结构和顺序存取特性，熟练掌握线性表的链式存储结构的C语言描述方法，熟练掌握动态链表的基本操作查找、插入、定位等，能在实际应用中选择适当的链表结构。掌握用链表表示特定形式的数据的方法，并能编写出有关运算的算法。

二、实验内容（选其中之一写实验报告）

(1) 已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素）同时释放被删结点空间，并分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同）。

(2) 完成单链表上的如下操作：
a. 逆序建立单链表；
b. 遍历单链表 (输出单链表每个元素的值)；
c. 在单链表第5个元素前插入一个值为 999 的元素；
d. 删除单链表第 5 个元素。

三、问题描述

上述题目概况：

    1. 删除线性表中一个开区间内的所有元素；
    1. 单链表的逆序建立、遍历、插入、删除操作。

四、数据结构定义

两部分均采用链式存储结构，数据元素类型整型。

五、算法思想及算法设计

（实验代码部分没有中文注释，在此部分给出）

5.1 实验内容（1）

题目：已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试 写一高效算法，删除表中所有值大于mink且小于maxk的元素（若表中存在这样 的元素）同时释放被删结点空间，并分析你的算法的时间复杂度（注意：mink和 maxk是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同）

思考：
大致分为以下两步：
<1> 建立一个单链表，用来存储线性表元素；
<2> 找到（mink,maxk）区间内的元素并删除，同时链接起剩余的部分以免链表断开。

5.1.1 理论实现和代码实现

<1> 建立单链表：应用结构体表示链表节点，每个节点有数据域和指针域：数 据域存放元素值，指针域指向后继节点。此处只应用了 malloc函数开辟空间，同 时还要考虑节点的指向问题。

//建立单链表
typedef struct Node
{
    int data;
    struct Node* next;
}*node, Link;

void InitLink(node& L) // main 函数中应用此函数
{
    L = (node)malloc(sizeof(Link));
    L->next = NULL;
    L->data = -1;
}

void CreatLink(node& L)
{
    int length, x;
    printf("Please input the length of this List: ");
    scanf("%d", &length);
    node NewNode;
    node p = (node)malloc(sizeof(Link));
    p = L;
    printf("Please input its content: \n");
    for (int i = 0; i < length; ++i)
    {
        NewNode = (node)malloc(sizeof(Link));
        scanf("%d", &x);
        NewNode->data = x;
        NewNode->next = NULL;
        p->next = NewNode;
        p = NewNode;
    }
}

<2> 查找、删除和链接：在单链表中找满足大小关系条件的节点，只能从头结点开始往后一一遍历。利用 p指针往后寻找，由于这个表递增，如果存在满足条件的节点，当 p->data > mink 时退出循环，另设一个 pre 保存每次循环的上一个p 指针。将此 p 指针继续往后遍历，p->data >= maxk 时退出，链接 pre 和此时的 p，另设 q 完成 free。

void Delete(node& L, int mink, int maxk) {
    if (mink > maxk) { 
        printf("Error!"); 
        return; 
    }
    
    node p = L->next, pre, q, s;
    
    if (p == NULL)
        return;
    
    q = pre = (node)malloc(sizeof(Link));
    
    while (p->data <= mink) {
        pre = p;
        p = p->next;
    }
    
    if (p) {
        while (p && p->data < maxk) {
            p = p->next;
        }
        
        q = pre->next;
        pre->next = p;
        
        while (q != p) {
            s = q->next;
            free(q);
            q = s;
        }
    }
}
/*最坏的情况是从头遍历到尾，中间元素全部删除；
最好的情况是第一个元素就遍历结束；
而在各种情况下，比较多少次最终是由 maxk 决定，凡是小于 maxk 的元素，都要遍历一次；
查找到位置之后，便开始遍历删除————整个过程没有循环的嵌套，是 x 次循环的简单相加；
所以时间复杂度为 O(n).*/

5.2 实验内容（2）

题目：完成单链表上的如下操作：
a. 逆序建立单链表 ；
b. 遍历单链表 (输出单链表每个元素的值) ；
c. 在单链表第5个元素前插入一个值为 999 的元素.；
d. 删除单链表第 5 个元素。

思考：
任务a头插法即可完成逆序建立单链表；
任务b从头结点开始循环遍历即可；
任务c 和 d 注意指针指向即可。

5.2.1 代码实现

  • a. 头插法逆序建立：
void CreatLink2(node& L) {
    int length, x;
    printf("Please input the length of this List: ");
    scanf("%d", &length);
    
    node NewNode;
    printf("Please input its content: \n");
    
    for (int i = 0; i < length; ++i) {
        NewNode = (node)malloc(sizeof(Link));
        scanf("%d", &x);
        NewNode->data = x;
        // 以下两行是关键语句
        NewNode->next = L->next; 
        L->next = NewNode;
    }
}
//任务b,c,d 在“七、实验代码”部分

六、运行示例

  • 区间删除操作示例：
    在这里插入图片描述

  • 实验内容（2）关于单链表操作较为简单，这里不再给出图示。

七、实验代码

  1. 实验内容（1）：
//FileName: code2.1.cpp

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

typedef struct Node
{
	int data;
	struct Node* next;
}*node,Link;

void InitLink(node& L)
{
	L = (node)malloc(sizeof(Link));
	L ->next=NULL;
	L->data = -1;
}

void CreatLink(node& L)
{
	int length, x;
	printf("Please input the length of this List: ");
	scanf("%d", &length);
	node NewNode;
	node p = (node)malloc(sizeof(Link));
	p = L;
	printf("Please input its content: \n");
	for (int i = 0; i < length; ++i)
	{
		NewNode = (node)malloc(sizeof(Link));
		scanf("%d", &x);
		NewNode->data = x;
		NewNode->next = NULL;
		p->next = NewNode;
		p = NewNode;
	}
}

void Delete(node& L, int mink, int maxk) {
	if (mink > maxk) { printf("Error!"); return; }
	node p = L->next,pre,q,s;
	if (p == NULL)return;
	q = pre = (node)malloc(sizeof(Link));
	while (p->data <= mink)
	{
		pre = p;
		p = p->next;
	}
	if (p)
	{
		while (p && p->data < maxk)
		{
			p = p->next;
		}
		q = pre->next;
		pre->next = p;
		while (q != p)
		{
			s = q->next;
			free(q);
			q = s;
		}
	}
}

void DisplayLink(node L)
{
	while (L->next != NULL)
	{
		printf("%d ", L->next->data);
		L = L->next;
	}
}
int main()
{
	node L;
	InitLink(L);
	CreatLink(L);
	int mink,maxk;
	printf("Please input the range you want DELETE: ");
	scanf("%d %d", &mink, &maxk);
	Delete(L, mink, maxk);
	DisplayLink(L);


}
  1. 实验内容（2）：
//FileName: code2.2.cpp

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

typedef struct Node
{
	int data;
	struct Node* next;
}*node, Link;

void InitLink(node& L)
{
	L = (node)malloc(sizeof(Link));
	L->next = NULL;
	L->data = -1;
}

void CreatLink2(node& L)
{
	int length, x;
	printf("Please input the length of this List: ");
	scanf("%d", &length);
	node NewNode;
	printf("Please input its content: \n");
	for (int i = 0; i < length; ++i)
	{
		NewNode = (node)malloc(sizeof(Link));
		scanf("%d", &x);
		NewNode->data = x;
		NewNode->next = L->next;
		L->next = NewNode;
	}
}

void DisplayLink(node L)
{
	while (L->next != NULL)
	{
		printf("%d ", L->next->data);
		L = L->next;
	}
}
int main()
{
	node L;
	InitLink(L);
	CreatLink2(L);
	printf("This List has: ");
	DisplayLink(L);
	printf("\n");
	printf("We will input 999 in the fifth room.....");
	int cnt = 0; node NewNode,p = L;
	NewNode = (node)malloc(sizeof(Link));
	NewNode->data = 999;
	while (p != NULL)
	{
		p = p->next;
		cnt++;
		if (cnt == 4)break;
	}
	if (p == NULL) { printf("List's length is NOT enough! !"); return 0; }
	NewNode->next = p->next;
	p->next = NewNode;
	printf("Now, this List has: \n");
	DisplayLink(L);
	printf("\nDelete the fifth data, then List has: ");
	node q = L->next, s = L; cnt = 0;
	while (q != NULL)
	{
		s = q;
		q = q->next;
		cnt++;
		if (cnt == 4)break;
	}
	s->next = q->next;
	free(q); q = NULL;
	DisplayLink(L);
}

八、算法测试结果

输入线性表：1、5、9、12、54、66 —–> 输入 mink=5, 输入 maxk=18 —–> 删除后：1、5、54、66

示例：
在这里插入图片描述

输入线性表：1、3、5、7、9、11、13、15
—–> 逆置：15、13、11、9、7、5、3、1
——> 第五个位置插入999: 15、13、11、9、999、7、5、3、1
——> 删除第五个位置元素： 15、13、11、9、7、5、3、1

示例：
在这里插入图片描述

九、分析与总结

9.1 算法复杂度分析及优、缺点分析

实验内容（1）：最坏的情况是从头遍历到尾，中间元素全部删除；最好的情况是第一个元素就遍历结束；而在各种情况下，比较多少次最终是由 maxk决定，凡是小于 maxk 的元素，都要遍历一次；查找到位置之后，便开始遍历删除———— 整个过程没有循环的嵌套，x次循环的简单相加，所以时间复杂度为 O(n)。采用链式存储，删除链接操作效率高，但是存储密度低，空间利用率低。

实验内容（2）：每有一个结点就要操作一次，时间复杂度O(n)。同样采用链式存储，删除链接操作效率高，但是存储密度低，空间利用率低。

9.2 实验总结

<1> 系统性地练习了单链表的建立插入删除操作，在一些特定问题 (如删除一个区间内的元素) 上予以探讨，学会利用辅助指针解决问题；
<2> 初步理解链表思想，理解结构体、指针在链表中的作用，体会到链表在插入、删除操作上的快速便捷；
<3> 引发了初步的思考，每个节点可以增添一个指向前驱节点的指针，方便解决问题。

ps: 溜了溜了~~~

# 数据结构 # c语言 # visual studio code # visual studio # 算法
Logo
魔乐社区

魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。

更多推荐

cover

【计算机视觉】Pixel逐像素分类&Mask掩码分类理解摘要

avatar 魔乐社区

计算机视觉（opencv）实战三十二——CascadeClassifier 人脸微笑检测（摄像头）

本文从原理到实现，详细介绍了基于 OpenCV Haar 分类器的人脸与微笑检测：讲解了 Haar 特征和级联检测原理。对代码逐行拆解并解释参数含义。画出完整流程图，帮助理解执行过程。给出了常见问题和优化建议，甚至扩展到深度学习方法。这种方法简单、轻量、实时性好，非常适合入门和小型应用项目。但如果需要更高准确率和更强鲁棒性，建议使用深度学习检测器替代 Haar 分类器。

avatar 魔乐社区
cover

小杰机器学习（seven）——贝叶斯分类

avatar 魔乐社区