#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
int over_flag=0;
typedef int ElemType;
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LNode,*LinkList;
void Traverse(LinkList L);
void CreateList(LinkList &L);
void exchange(LinkList &L);
void Deleteou(LinkList &L);
void Deletechong(LinkList &L);
void Insert_Sort(LinkList &L,ElemType e);
void Create_Sort(LinkList &L);
void Hebing(LinkList La,LinkList Lb,LinkList &Lc);
void Fenjie(LinkList &L);
//用头插法建立无序链表
void CreateList(LinkList &L)
{
int e;
printf("请输入链表元素数值(以0结束):
");
L = (LinkList)malloc(sizeof(LNode));
L->next = NULL;
LinkList q=L;
scanf("%d",&e);
while(e!=0)
{
LinkList p;
p = (LinkList)malloc(sizeof(LNode));
p->data = e;
p->next = NULL;
q->next = p;
q = q->next;
scanf("%d",&e);
}
Traverse(L);
}
//遍历单向链表
void Traverse(LinkList L)
{
LinkList i=L->next;
printf("链表的元素遍历为：");
while(i)
{
printf("%d ",i->data);
i=i->next;
}
printf("
");
}
//把单向链表中的元素逆置
void exchange(LinkList &L)
{
LinkList pa,pb;
pa=L->next;
L->next=NULL;
while(pa)
{
pb=pa;
pa=pa->next;
pb->next=L->next;
L->next=pb;
}
}
//在单向链表中删除所有偶数元素结点
void Deleteou(LinkList &L)
{
printf("删除偶数结点后的链表为:
");
LinkList q=L;
LinkList p=L->next;
while(p)
{
if(p->data%2==0)
{
LinkList r=p;
q->next=p->next;
p=p->next;
free(r);
}
else
{
p=p->next;
q=q->next;
}
}
Traverse(L);
}
//直接插入排序算法
void Insert_Sort(LinkList &L,ElemType e)
{
LinkList p,s;
s=(LinkList)malloc(sizeof(LNode));
s->data=e;
p=L;
while(p->next&&p->next->data<=e)
p=p->next;
s->next=p->next;
p->next=s;
}
//建立递增有序的单向链表
void Create_Sort(LinkList &L)
{
ElemType e;
L=(LinkList)malloc(sizeof(LNode));
L->next=NULL;
printf("请输入单向链表的元素数值，以0结束
");
scanf("%d",&e);
while(e)
{
Insert_Sort(L,e);
scanf("%d",&e);
}
}
//删除链表中的重复元素
void Deletechong(LinkList &L)
{
LinkList p,q,temp1,temp2;
p=L->next;
q=p->next;
while(p->next)
{
temp1=p;
while(q)
{
if(p->data!=q->data)
{
q=q->next;
temp1=temp1->next;
}
else
{
temp2=q;
q=q->next;
temp1->next=q;
free(temp2);
}
}
p=p->next;
q=p->next;
}
Traverse(L);
}
//利用算法5建立两个非递减有序单向链表，然后合并成一个非递减链表
void Hebing(LinkList La,LinkList Lb,LinkList &Lc)
{
LinkList p,q,s,rear;
p=La->next;
q=Lb->next;
Lc=rear=La;
free(Lb);
while(p&&q)
{
if(p->data<q->data)
{
s=p;
p=p->next;
}
else
{
s=q;
q=q->next;
}
rear->next=s;
rear=rear->next;
}
if(p)
rear->next=p;
else
rear->next=q;
}
//利用算法1建立的链表，实现将其分解成两个链表，其中一个全部为奇数，另一个全部为偶数
void Fenjie(LinkList &L)
{
printf("分解成两个链表：
");
LinkList A=L;
LinkList B=(LinkList)malloc(sizeof(LNode));
B->next=NULL;
LinkList Lb=B;
int i=1;
LinkList La=L;
LinkList p=L->next;
while(p)
{
if(i++%2==0)
{
La->next=p->next;
p->next=NULL;
Lb->next=p;
Lb=Lb->next;
p=La->next;
}
else
{
p=p->next;
La=La->next;
}
}
printf("链表A:");
Traverse(A);
printf("链表B:");
Traverse(B);
}
//主函数
void main()
{
LinkList La,Lb,Lc;
int select;
do
{
printf("************************************************
");
printf("*****************链表的应用*******************
");
printf("************************************************
");
printf("
1 键盘输入一组元素，建立一个无头结点的单向链表（无序）,遍历（打印）单向链表
");
printf("2 把单向链表中元素逆置（不允许申请新的结点空间）
");
printf("3 删除所有偶数元素的结点
");
printf("4 对链表排序，排序后链表元素按照非递减方式排列
");
printf("5 利用算法1建立的链表，实现将其分解成两个链表，其中一个全部为奇数，另一个全部为偶数（尽量利用已知的存储空间）
");
printf("6 利用算法5建立两个非递减有序单向链表，然后合并成一个非递减链表
");
printf("7 删除链表中的重复元素
");
printf("8 选作11
");
printf("0 退出
");
scanf("%d",&select);
switch(select)
{
case 0:
break;
case 1:
CreateList(La);
break;
case 2:
printf("原链表为：
");
Traverse(La);
exchange(La);
printf("逆置后的链表为：
");
Traverse(La);
break;
case 3:
Traverse(La);
printf("该链表变为:");
Deleteou(La);
break;
case 4:
Create_Sort(La);
printf("按非递减方式排列后的链表链表为：
");
Traverse(La);
break;
case 5:
printf("分解前的链表为:");
Traverse(La);
printf("分解后的链表为:");
Fenjie(La);
break;
case 6:
printf("建立两个非递减有序单向链表，然后合并成一个非递减链表
");
printf("输入第一个链表的元素数值：
");
Create_Sort(La);
Traverse(La);
printf("输入第二个链表的元素数值：
");
Create_Sort(Lb);
Traverse(Lb);
Hebing(La,Lb,Lc);
printf("合并后的非递减链表:
");
Traverse(Lc);
break;
case 7:
printf("算法1生成的链表为：
");
Traverse(La);
printf("删除重复元素后的链表为：
");
Deletechong(La);
break;
case 8:
printf("建立两个非递减有序单向链表，然后合并成一个非递增链表
");
printf("输入第一个链表的元素数值：
");
Create_Sort(La);
Traverse(La);
printf("输入第二个链表的元素数值：
");
Create_Sort(Lb);
Traverse(Lb);
Hebing(La,Lb,Lc);
exchange(Lc);
printf("合并后的非递增链表:
");
Traverse(Lc);
break;
default:
printf("输入错误，请重新输入!
");
}
}while(select);
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/bian-cheng-ri-ji/67994.html