实现单链表的各种基本运算，要求用菜单组织所有功能。设单链表中存储的数据元素为int型，要实现的功能包括：
（1）输出单链表中的所有元素，若单链表为空，则给出提示信息；
（2）按序号查找指定元素，即输出单链表中的第i个元素；
（3）按值查找指定元素，即输出单链表中值为x的元素的序号；
（4）在指定位置插入元素，即在第i个元素前面插入值为x的元素；
（5）删除指定元素，即删除第i个元素；
（6）求单链表的长度，即数据结点的个数；
（7）返回单链表中最后一个最小结点（最小结点可能有多个）的逻辑序号；
（8）将单链表中的结点排列为递增有序的序列；
（9）删除递增有序的单链表中所有值在[x,y]范围内的元素，删除前先对单链表排序；
（10）销毁单链表并退出。
#include
#define overflow -2
#define ok 1
#define error 0
using namespace std;
typedef int status;
typedef int ElemType;
//定义
typedef struct LNode
{
ElemType data; //数据域
struct LNode *next; //指针域
}LNode , *LinkList;
//函数声明
status InitList(LinkList &L);
status Empty(LinkList L);
int Length(LinkList L);
status CreatList_R(LinkList &L, int n);
LNode *GetElem(LinkList L, int i);
int LocateList(LinkList L, int x);
status InsertList(LinkList &L, int i, ElemType e);
status DeleteList(LinkList &L, int i, ElemType e);
status deletex_y(LinkList &L, int min, int max);
status up_List(LinkList &L);
status MinList(LinkList L);
int DispList(LinkList L);
status DestoryList(LinkList &L);
void menu()
{
cout << endl ;
cout << "**************单链表操作****************" << endl;
cout << endl ;
cout << "P-输出 G-取值" << endl;
cout << "L-查找 I-插入" << endl;
cout << "D-删除 C-求表长" << endl ;
cout << "M-求最小结点 S-排序" << endl ;
cout << "N-删除区间 Q-退出" << endl ;
cout << endl;
cout << "****************************************" << endl;
cout << endl ;
}
//主函数
int main()
{
int n , i , m , x;
int min, max;
LNode *s;
ElemType e;
char choice;
LinkList L;
InitList(L);
cout << "线性表中元素的个数？" << endl;
cin >> n ;
cout << "请输入元素：" << endl;
CreatList_R(L, n);
while (1)
{
menu();
cin >> choice;
choice = toupper(choice); //小写转大写
switch (choice)
{
case 'P':
if (Empty(L))
cout << "线性表为空" << endl ;
else
{
cout << "线性表中的元素为：" << endl ;
DispList(L);
}
cout << endl;
break;
case 'G':
cout << "要取第几个元素？" << endl ;
cin >> i;
s = GetElem(L, i); //用一个结点类型的指针s，接收调用的GetElemType()函数的返回结点值
cout << "要查找的" << "第" << i << "个元素是：" << s->data << endl;
cout << endl;
break;
case 'L':
cout << "要查找的元素是：" << endl ;
cin >> x;
LocateList( L, x);
cout << endl;
break;
case 'I':
cout << "在第几个元素前面插入 ？" << endl ;
cin >> i ;
cout << "插入的值为：" << endl ;
cin >> x ;
m = InsertList(L, i, x);
if (!m)
cout << "插入失败!" << endl ;
else
cout << "在第" << i << "个元素前面插入" << x << "后的线性表为：" << endl ;
DispList(L);
cout << endl ;
cout << endl;
break;
case 'D':
cout << "删除第几个元素？" << endl ;
cin >> i ;
m = DeleteList(L, i, e);
if (!m)
cout << "删除失败！" << endl ;
else
cout << "删除成功，删除后的线性表元素为：" << endl ;
DispList (L);
cout << endl;
break;
case 'C':
cout << "线性表的长度为：" << Length(L) - 1<< endl ;
cout << endl;
break;
case 'M':
cout << "最小结点位置为：" ;
MinList(L) ;
cout << endl;
break;
case 'S':
cout << "原线性表为：" << endl ;
DispList(L);
cout << endl ;
cout << "排序后的线性表为：" << endl ;
up_List(L);
DispList(L);
cout << endl;
break;
case 'N':
cout << "要删除的最小区间是：" << endl ;
cin >> min;
cout << "要删除的最大区间是：" << endl ;
cin >> max;
m = deletex_y(L, min, max);
if (min > max)
cout << "区间错误，删除失败！" << endl ;
else
{
cout << "删除成功，删除后的线性表为：" << endl ;
DispList(L);
}
cout << endl;
break;
case 'Q':
DestoryList(L);
exit(overflow);
cout << endl;
default:
cout << "NULL" ;
break;
}
}
}
//初始化
status InitList(LinkList &L)
{
L = new LNode; //生成一个新结点
L->next = NULL; //结点指针域置空
return ok;
}
//判空
status Empty(LinkList L)
{
return (L->next == NULL);
}
//表长
int Length(LinkList L)
{
int len = 0;
LNode *p = L; //p初始化，指向头结点
while (p)
{
p = p->next; //p指向首元结点
len++; //长度加一
}
return len;
}
//创建一个长度为n的单链表
status CreatList_R(LinkList &L, int n)
{
LNode *r = L; //尾指针初始化指向头结点
for (int i = 0; i < n; i++)
{
LNode *p = new LNode; //生成新结点
cin >> p->data; //输入的数据存放在新结点的数据域
r->next = p;
p->next = NULL;
r = p;
}
return ok;
}
//按序号查找，查找第i个结点的元素
LNode *GetElem(LinkList L, int i)
{
LNode *p = L->next; //p指向首元结点
int j = 1; //初始化j为1
if (i == 0) //如果i等于0，返回头结点（头结点第0个元素，一般不存放数据）
return L;
if (i < 1) //位置不合法
return NULL;
while (p && j < i) //如果p不为空，且 还没找到第i个结点
{
p = p->next; //p顺着链域继续向下找，直至p空，或者j=i
j++;
}
return p; //找到了就返回第i个结点的值
}
//按值查找，查找单链表中，值为x的元素，并返回其位序
int LocateList(LinkList L, int x)
{
LNode *p = L->next; //p指向首元结点
int num = 1;
if (p == NULL)
cout << "NULL" << endl ;
while (p != NULL)
{
if (p->data == x) //如果p不为空，p所指结点的数据域等于x，就输出结点值，和位序
{
cout << x << "元素是链表中的第" << num << "个元素" << endl ;
return num;
}
p = p->next; //如果p所指结点的数据域不等于x，P就继续向下找， num ++ (记录位序)
num++;
}
cout << "未找到该元素！" << endl ;
return -1;
}
//插入
status InsertList(LinkList &L, int i, ElemType e)
{
LNode *p = L;
int j = 0;
while (p && j < i - 1) //找第 i - 1个元素
{
p = p->next;
j++;
}
if (!p || j > i - 1)
return error;
LNode *s = new LNode; //生成新结点，指向要插入的结点位置
s->data = e; //将要插入的元素存放在新结点的数据域
s->next = p->next; //插入 *** 作
p->next = s;
return ok;
}
//删除
status DeleteList(LinkList &L, int i, ElemType e)
{
LNode *p = L;
int j = 0;
while (p->next && j < i - 1) //找第 i - 1个元素
{
p = p->next;
j++;
}
if (!p->next || j > i - 1)
return error;
LNode *q = new LNode;
q = p->next;
//删除 *** 作
p->next = q->next;
e = q->data;
delete q;
return ok;
}
//删除有序递增单链表中值大于min且小于max的所有元素(含端点值)
status deletex_y(LinkList &L, int min, int max)
{
LNode *p ,*pre , *q;
p = L->next; //p初始化指向首元结点
pre = L; //pre初始化指向头结点（可以理解为此时是p的前驱结点）
while (p)
{
if (p->data >= min && p->data <= max) //如果p不为空，p所指结点的值在区间范围之类的
{
q = p->next; //删除范围之内的所有结点 ， 指针q保存p的后继结点
pre->next = p->next; //p的前驱结点pre指向p的后继结点
delete p; //删除当前结点p
p = q;
}
else
{ //不在区间范围内
pre = p;
p = p->next;
}
}
}
//排序
status up_List(LinkList &L)
{
// LNode *p, *pre, *q ;
// p = L->next->next;
// L->next->next = NULL; //将链表断成两个链表
// while (p != NULL)
// {
// q = p->next;
// pre = L;
// while (pre->next != NULL && pre->next->data < p->data)
// pre = pre->next; //搜索前驱
// p->next = pre->next;
// pre->next = p;
// p = q;
// }
/*************简单排序（这个比较好理解）**************/
LNode *p, *q;
p = L->next; //p初始化指针首元结点
while (p) //p不为空，一重循环
{
q = p->next; //q初始化指向p的下一结点
while (q)
{ //q不为空， 二重循环
if (p->data > q->data) //比较p, q所指结点的数据大小， p结点的值大，就交换顺序
{
int temp;
temp = p->data;
p->data = q->data;
q->data = temp;
}
q = q->next; //否则，q就继续向后移动
}
p = p->next; //一轮内层循环结束后，执行外侧循环，p后移
}
}
//最小结点
status MinList(LinkList L)
{
int j = 1;
int i = 1;
LNode *p, *q ;
p = L->next ;
q = p->next ;
if (L->next == NULL)
return error;
while (q)
{
i++;
if (p->data < q->data)
{
q = q->next; //p结点值小， q后移
}
else if(p->data >= q->data) //p结点值大于等于q，p指向q, q指向下一结点
{
p = q;
q = q->next;
j = i;
}
}
cout << j;
return ok;
}
//输出
int DispList(LinkList L)
{
LNode *p = L->next;
while (p)
{
cout << p->data << ' ';
p = p->next;
}
return ok;
}
//销毁
status DestoryList(LinkList &L)
{
LNode *p;
while (L)
{
p = L;
L = L->next;
delete p;
}
return ok;
} 欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）