编写一个完整的程序，实现单链表的建立、插入、删除、输出等基本操作。1）建立一个带头结点的单链表。（2）计算单链表的长度，然后输出单链表。（3）查找值为x的直接前驱结点q。（4

Question

编写一个完整的程序，实现单链表的建立、插入、删除、输出等基本操作。
1）建立一个带头结点的单链表。
（2）计算单链表的长度，然后输出单链表。
（3）查找值为x的直接前驱结点q。
（4）删除值为x的结点。
（5）把单向链表中元素逆置（不允许申请新的结点空间）。
（6）利用（1）建立的链表，实现将其分解成两个链表，其中一个全部为奇数，另一个全部为偶数（尽量利用已知的存储空间）。
（7）在主函数中设计一个简单的菜单，分别测试上述算法

Answer 1

typedef int Elemtype;
typedef int status;
#define OVERFLOW -2
#define OK 1
#define ERROR -1
#include "stdio.h"
#include "stdlib.h"
typedef struct LNode {
Elemtype data;
struct LNode *next;
}*linklist;
//构造链表
void Create_Linklist(linklist &L)
{
linklist p;
p=(linklist)malloc(sizeof(LNode));
if(!p)
exit(OVERFLOW);
L=p;
L->next =NULL;
}
//节点插入
void Insert_Linklist(linklist &L)
{
linklist p;
int n,i;
printf("请输入插入节点的个数n: ");
scanf("%d",&n);
getchar();
for(i=n;i>0;i--)
{
p=(linklist )malloc(sizeof(LNode));
scanf("%d",&p->data);
p->next=L->next ;
L->next =p;
}
}
//遍历输出并输出长度
status Visit_linklist(linklist &L)
{
linklist p;
int i=1;
p=L->next ;
if(L->next==NULL)
return ERROR;
while(p->next !=NULL)
{
printf("%d ",p->data );
p=p->next ;
i++;
}
printf("%d\n",p->data );
printf("长度为：%d\n",i);
return OK;
}
//查找值为x的直接前驱结点q并输出
void Search_linklist(linklist &L)
{
int x,k=0;
linklist p=L,q;
printf("输入x: ");
scanf("%d",&x);
getchar();
if(L->next ==NULL)
printf("该表为空 ！\n");
while(p->next!=NULL)
{
q=p;
if(p->next ->data ==x)
{
printf("%d ",q->data );
k=1;
}
p=p->next ;
}
if(p->next &&p->data ==x)
{
printf("%d ",p->data );
k=1;
}
if(k==0)
printf("未找到值为%d的结点\n",&x);
printf("\n");
}
//删除节点
status Delete_linklist(linklist &L)
{
linklist p,q;
int k=0,x;
printf("请输入删除节点的值x: ");
scanf("%d",&x);
getchar();
if(L->next ==NULL)
return ERROR;
p=L;
q=L->next ;
while(q!=NULL)
if(q->data ==x)
{
k=1;
p=q ;
p->next =q->next ;
free(q);
q=p->next ;
}
else
{
p=q ;
q=p->next ;
}
if(k==0)
printf("表中没有值为%d的结点！\n",&x);
return OK;
}

//链表逆置
void ListInverse_linkliast(linklist &L)
{
linklist k,p,q;
p=L;
while (p->next !=NULL)
{
p=p->next ;
}
k=p;
while (L->next !=p)
{
q=L->next ;
L->next = q->next ;
k->next =q;
}
}
//链表奇偶分解
void Break_linklist (linklist &La,linklist &Lb)
{
linklist p,q;
p=La->next;
q=Lb;
while(p->next!=NULL)
{
if(p->data %2==0)
{
q->next =p;
q=q->next ;
}
p=p->next ;
}
if(p->data %2==0)
{
q->next =p;
q=q->next ;
}
}

//主菜单
void main()
{
linklist L1,L2;
printf(" （1） 建立带头节点的单链表\n");
printf(" （2） 插入节点\n");
printf(" （3） 计算链表长度并输出单链表\n");
printf(" （4） 查找值为x的直接前驱结点并输出其值\n");
printf(" （5） 删除节点值为x的结点\n");
printf(" （6） 逆置单链表结点\n");
printf(" （7） 单链表奇偶分解\n");
int choice;
printf(" 请输入选择：");
while(scanf("%d",&choice))
{
getchar();
printf("\n\n");
switch(choice)
{
case 1:
Create_Linklist(L1);
break;
case 2:
Insert_Linklist(L1);
break;
case 3:
Visit_linklist(L1);
break;
case 4:
Search_linklist(L1);
break;
case 5:
Delete_linklist(L1);
break;
case 6:
ListInverse_linkliast(L1);
break;
case 7:
Create_Linklist(L2);
Break_linklist (L1,L2);
break;
default:
printf(" 输入有误！");
break;
}
}
}