单链表的基本操作（必做，设计性实验）
- 实验目的
了解线性表的链式存储结构和顺序存取特性，熟练掌握线性表的链式存储结构的C语言描述方法，熟练掌握动态链表的基本操作查找、插入、定位等，能在实际应用中选择适当的链表结构。掌握用链表表示特定形式的数据的方法，并能编写出有关运算的算法。 - 实验内容
已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素）同时释放被删结点空间，并分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同） - 问题描述
对一个元素值递增有序排列的线性表，并以单链表作存储结构，删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素）同时释放被删结点空间，并分析你的算法的时间复杂度（mink和maxk是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同） - 数据结构定义
本次的存储方式是单链表，数据类型数据是int类型，此算法叶可以扩充到任意数据类型，只要可以进行比较均可以使用此算法。要进行操作主要为找到最小的元素，然后接着遍历删除，直到maxk。 - 算法思想及算法设计
算法设计思想：沿着单链表的头指针进行遍历，直到找到最小的大于mink的元素，直接把该元素的next指针赋值给上一个元素的next（具体实现的时候可以更改，此处便于描述），然后释放该空间，在次进行比较删除，直到大于maxk。
Status Delete(List &l, Elemtype mink, Elemtype maxk)
{
LNode *p = l, *q;
int flag = 1;
while (p->next)
{
while (p->next && p->next->data > mink && p->next->data < maxk)
{
q = p->next;
p->next = p->next->next;
delete (q); //删除所选空间
flag = 0;
}
if (flag)
p = p->next; //由于题目的特殊性，可以在大于maxk之后就结束循环
else
return OK;
}
return false;
}
- 实验代码
#ifndef ____2_hpp
#define ____2_hpp
#include "constant.h"
#include <stdio.h>
#include <iostream>
#define Elemtype int
#define List struct LNode *
struct LNode
{
Elemtype data;
struct LNode *next;
};
typedef struct LNode LNode;
Status Delete(List &l, Elemtype mink, Elemtype maxk);
#endif /* ____2_hpp */
#include "数据结构2.hpp"
#include "constant.h"
using namespace ::std;
int main()
{
List l;
l = new LNode;
l->next = NULL;
List node;
List p = l;
cout << "Please input the number of List" << endl;
int n;
cin >> n;
cout << "Please input the elems!" << endl;
while (n--) //构建初始化链表
{
node = new LNode;
cin >> node->data;
node->next = NULL;
p->next = node;
p = p->next;
}
p = l->next; //删除前的元素
cout << "The list is" << endl;
while (p)
{
cout << p->data << " ";
p = p->next;
}
cout << endl;
cout << "Please input mink,maxk" << endl;
int mink, maxk;
cin >> mink >> maxk;
Delete(l, mink, maxk);
p = l->next;
cout << "The changed list is" << endl;
while (p)
{
cout << p->data << " ";
p = p->next;
}
cout << endl;
return OK;
}
Status Delete(List &l, Elemtype mink, Elemtype maxk)
{
LNode *p = l, *q;
int flag = 1;
while (p->next)
{
while (p->next && p->next->data > mink && p->next->data < maxk)
{
q = p->next;
p->next = p->next->next;
delete (q); //删除所选空间
flag = 0;
}
if (flag)
p = p->next; //由于题目的特殊性，可以在大于maxk之后就结束循环
else
return OK;
}
return false;
}
- 分析与总结
（1）算法复杂度分析及优、缺点分析
时间复杂度会随着输入数据的不同而改变，但是总体来说是线性时间复杂度，比较简单，空间复杂度为O（1），比较简单。缺点是可能算法写的过程中比较复杂，思维比较难一些。
（2）实验总结
在编写程序时，考虑到如何在比较删除之后直接退出时，行到了用flag变量，比较方便，减少了大于maxk之后数据的比较。进行if判断时，注意&&与&区别，这样对于算法的完整度更好，否则可能会出现段错误（例如在delete程序中的比较操作，如果判断p->next是否为空在最后面，课鞥忽先判断p->next->data，但是这个可能不存在，就会出现段错误，影响后面的进行。
