#include<stdio.h>
#include<malloc.h>
typedef struct LNode
{
int data;
struct LNode *next;
}LNode,*LinkList;
void CreateList(LinkList &L); //创建链表
void Locate(LinkList L); //查询数值
void InsertList(LinkList &L); //插入数值
void DeleteList(LinkList &L); //选择删除
void Deleterepeat(LinkList &L); //删除重复结点
void DeleteEven(LinkList &L); //删除数值为偶数的结点
void Rotate(LinkList &L); //变为循环链表
void Divide(LinkList &L); //分解成两个链表
int LengthList(LinkList L); //求链表长度
void PrintList(LinkList L); //输出链表
/**********************************************************************
主函数
**********************************************************************/
void main(void)
{
char operate;
LinkList L;
int n;
for( n=0;n<40;n++)
{
printf("\n输入字符选择链表操作类型\nA:创建 B:查询 C:插入 D:选择删除 E:删除重复 F:删除偶数 \nG:变为循环链表 H:分解为两个链表\n");
label:scanf("%c",&operate);
switch (operate)
{
case 'a':
case 'A': CreateList(L);break;
case 'b':
case 'B': Locate(L);break;
case 'c':
case 'C': InsertList(L); break;
case 'd':
case 'D': DeleteList(L);break;
case 'e':
case 'E': Deleterepeat(L);break;
case 'f':
case 'F': DeleteEven(L);break;
case 'g':
case 'G': Rotate(L);break;
case 'h':
case 'H': Divide(L);break;
case '\n':goto label; //排除换行键的影响
default: printf("输入有误,请重新输入!");break;
}
}
}
/**********************************************************************
创建链表
**********************************************************************/
void CreateList(LinkList &L)
{
int temp;
printf("创建链表:\n请输入创建链表所需的整数值(以-1结束):\n");
L = (LinkList)malloc(sizeof(LNode));
L->next = NULL;
LinkList q=L;
scanf("%d",&temp);
while(temp!=-1)
{
LinkList p;
p = (LinkList)malloc(sizeof(LNode));
p->data = temp;
p->next = NULL;
q->next = p;
q = q->next;
scanf("%d",&temp);
}
L->data = LengthList(L);
PrintList(L);
}
/**********************************************************************
查询元素
**********************************************************************/
void Locate(LinkList L)
{ if(!L)printf("错误:链表未创建!");
int element;
printf("查询数值:\n输入要查询的数值:");
scanf("%d",&element);
LinkList p=L->next;
int i =1;
while(p->data!=NULL)
{
if(p->data==element)
{
printf("找到了,它是链表的第%d个元素。\n",i);
return ;
}
p=p->next;
i++;
}
printf("找不到。\n");
}
/**********************************************************************
插入数值
**********************************************************************/
void InsertList(LinkList &L)
{
int x,i;
printf("插入数值:\n输入要插入的数值和插入的位置:");
scanf("%d",&x);
scanf("%d",&i);
LinkList p = L;
int j = 0;
while (p && j < i-1)
{
p = p->next;
++j;
}
if (!p || j > i-1)
{
printf("输入位置错误!") ;
return;
}
LinkList s = (LinkList)malloc(sizeof(LNode));
s->data = x;
s->next = p->next;
p->next = s;
L->data = LengthList(L);
PrintList(L);
}
/**********************************************************************
选择位置删除节点
**********************************************************************/
void DeleteList(LinkList &L)
{
int i;
LinkList p = L;
printf("选择位置删除结点:\n输入要删除数值的位置:");
scanf("%d",&i);
int j = 0;
while (p->next && j < i-1)
{
p = p->next;
++j;
}
if (!(p->next) || j > i-1)
{
printf("输入位置错误!") ;
return;
}
LinkList q = p->next;
p->next = q->next;
free(q);
L->data = LengthList(L);
PrintList(L);
}
/**********************************************************************
删除重复结点
**********************************************************************/
void Deleterepeat(LinkList &L)
{
printf("删除重复结点后的链表为:\n");
int n=1;
int a[20];
LinkList q=L->next;
LinkList p=q->next;
a[0]=q->data;
while(p)
{
for(int i=0;i<n;i++)
{
if(p->data==a[i])
{
LinkList r=p;
q->next=p->next;
p=p->next;
free(r);
break;
}
}
if(i==n)
{
a[n++]=p->data;
p=p->next;
q=q->next;
}
}
L->data = LengthList(L);
PrintList(L);
}
/**********************************************************************
删除数值为偶数的结点
**********************************************************************/
void DeleteEven(LinkList &L)
{
printf("删除偶数结点后的链表为:\n");
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;
}
}
L->data = LengthList(L);
PrintList(L);
}
/**********************************************************************
变为循环链表
**********************************************************************/
void Rotate(LinkList &L)
{
printf("变为循环链表:\n");
LinkList p=L;
while(p->next)p=p->next;
p->next=L;
LinkList t=L->next;
printf("长度:%d\t",L->data);
printf("各个结点数值为:");
while(t!=L)
{
printf("%d\t",t->data);
t=t->next;
}
printf("\n");
printf("已经变为循环链表,其他操作将受影响,程序结束!\n");
}
/**********************************************************************
分解成两个链表
**********************************************************************/
void Divide(LinkList &L)
{
printf("分解成两个链表:\n");
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;
}
}
A->data = LengthList(A);
printf("链表A:");
PrintList(A);
B->data = LengthList(B);
printf("链表B:");
PrintList(B);
printf("已经分解成两个链表,其他操作将受影响,程序结束!\n");
}
/**********************************************************************
求链表长度
**********************************************************************/
int LengthList(LinkList L)
{
int i=0;
LinkList p=L->next;
while(p)
{
p=p->next;
i++;
}
return i;
}
/**********************************************************************
输出链表
**********************************************************************/
void PrintList(LinkList L)
{
LinkList t=L->next;
printf("长度:%d\t",L->data);
printf("结点数值:");
while(t)
{
printf("%d ",t->data);
t=t->next;
}
printf("\n");
}
评论0