/*
设计一个算法,删除递增有序链表中值大于mink且小于maxk的所有元素
(mink和maxk是给定的两个参数,其值可以和表中元素相同,也可以不同)。
*/
#include<iostream>
using namespace std;
//结点、链表的定义
struct LNode
{
int data;
LNode *next;
};
typedef LNode *LinkList;
//基本操作函数
//1.初始化
int InitList(LinkList &L)//创建一个只有头结点的空链表
{
L = new LNode;//生成新节点作为头结点,用指针L指向头结点
L->next = NULL;//头结点的指针域置空
return 1;
}
//2.取值
int GetElem(LinkList L, int i, int &e)
{
LNode *p = L->next;
int j = 1;
while (j < i && p)//直到p为空或者p指向第i个元素
{
p = p->next;
j++;
}
e = p->data;
if (!p || j > i)
return 0;
return 1;
}
//3.按值查找
LNode *LocateElem(LinkList L, int e)
{
LNode *p = L->next;
while (p->data != e && p)//外加p非空
p = p->next;
return p;
}
//4.插入
int ListInsert(LinkList &L, int i, int e)//插入元素的类型可以更改,可以是LNode
{
LNode *q = new LNode;
q->data = e;
q->next = NULL;
LNode *p = L;
int j = 0;
while (j < i-1&&p)
{
p = p->next;
j++;
}//找到第i-1个结点
if (!p || j > i - 1)
return 0;
q->next = p->next;
p->next = q;
return 1;
}
//5.删除
int ListDelete(LinkList &L, int i)
{
LNode *p = L;
int j = 0;
while (j < i - 1 && p)
{
p = p->next;
j++;
}
if (!(p->next) || (j > i - 1))
return 0;
LNode *q = p ->next;
p->next = q->next;
delete q;
return 1;
}
//6.前插法创建单链表
void CreateList_H(LinkList &L, int n)//逆序创建含有n个结点的链表
{
//先初始化
L = new LNode;
L->next = NULL;
for (int i = 0; i < n; i++)
{
LNode *p = new LNode;
cout << "请输入第" <<n-i<< "个结点的值:";
cin >> p->data;
p->next = L->next;
L->next = p;
}
}
//7.尾插法创建单链表
void CreateList_R(LinkList &L, int n)//正序创建含有n个结点的链表
{
//初始化
L = new LNode;
L->next = NULL;
LNode *r = L;//r为尾指针
for (int i = 0; i < n; i++)
{
LNode *p = new LNode;
cout << "请输入第" << i+1 << "个结点的值:";
cin >> p->data;
p->next = NULL;
r->next = p;
r = p;
}
}
//8.<补充>遍历
void PrintList(LinkList L)
{
LNode *p = L->next;
cout << "遍历结果为:";
while (p)
{
cout << p->data << " ";
p = p->next;
}
}
//功能函数
int fun(LinkList &L, int mink, int maxk)
{
LNode *p = L;
while (p->next->data < mink)
{
p = p->next;
}
LNode *q = p->next;
LNode *r = q->next;
while (q->data <= maxk)
{
delete q;
q = r;
r = r->next;
}
p->next = q;
return 1;
}
int main()
{
LinkList L;
CreateList_R(L, 8);
PrintList(L);
fun(L,1,13);
PrintList(L);
system("pause");
return 0;
}