# define TRUE 1
# define FALSE 0
# define OK 1
# define ERROR 0
# define INFEASIBLE -1
# define OVERFLOW -2
typedef int status;
typedef int ElemType;
#include<stdio.h>
#include<stdlib.h> //不要这行关系不大
#include<malloc.h>
typedef struct LNode
{
ElemType data;
struct LNode * next;
}LNode,*LinkList;
void CreateList_L1(LinkList & L) //创建一个链表,用这个建立链表输出时为顺序输出
{
int elem;
LinkList p,q;
L=(LinkList)malloc(sizeof(LNode));
L->next=NULL;
p=L;
printf("(Input a data,0 to end):\n"); printf(" ");
scanf("%d",&elem);
while(elem)
{
q=(LinkList)malloc(sizeof(LNode));
q->data=elem;
q->next=p->next;
p->next=q;
p=q;
scanf("%d",&elem);
}
}
void CreateList_L(LinkList & L) //创建一个链表,用这个建立链表输出时为逆序输出
{
int elem ;
LinkList P;
L=(LinkList)malloc(sizeof(LNode));
L->next=NULL;
printf("(Input data, 0 to end)\n");
scanf("%d",&elem);
while(elem)
{
P=(LinkList)malloc(sizeof(LNode));
P->data=elem;
P->next=L->next;
L->next=P;
scanf("%d",&elem);
}
}
void Print_L(LinkList head) //输出链表
{
LinkList p;
p=head;
if(p->next==NULL)
printf("Please attention!This list is empty!\n");
else
while(p->next)
{
printf("%d ",p->next->data);
p=p->next;
}
printf("\n");
}
void reverse(LinkList &L) //让链表头指针指向尾节点
{
LinkList p,q,r;
int n=1;
p=L; q=L->next;
while(q->next)
{
r=q->next;
if(n)
{
q->next=NULL;
n=0;
}
else
q->next=p;
p=q; q=r;
}
q->next=p; //注意要将头节点的指针域指向最后一个节点,并将第一个
//节点的指针域设为NULL
//L->next=NULL; L->data=0;L=q;
L->next=q;
}
status Locate(LinkList L,int & i,ElemType e) //找出数据的位置
{
LinkList p;
i=0;
p=L;
while(p->next!=NULL&&p->data!=e)
{
p=p->next; i++;
}
if(p->data!=e)
return ERROR;
else
return OK;
}
status Found(LinkList L,int i,ElemType & e) //看第X位置上是什么数
{
LinkList p; p=L;
int j=0;
while(p->next!=NULL&&j<i)
{
p=p->next;j++;
}
if(j<i)
return ERROR;
else
e=p->data;
return OK;
}
status ListInsert_L(LinkList &L,int i,ElemType e) //插入节点
{
int j;
LinkList p,s;
p=L;
j=0;
while(p&&j<i-1)
{
p=p->next;
++j;
}
if(!p||j>i-1)
return ERROR;
s=(LinkList)malloc(sizeof(LNode));
s->data=e;
s->next=p->next;
p->next=s;
return OK;
}
status ListDelete_L(LinkList &L,int i, ElemType &e) //删除一个节点
{
int j;LinkList p,q;
p=L;
j=0;
while(p->next&&j<i-1)
{
p=p->next;++j;
}
if(!(p->next)||j>i-1) return ERROR;
q=p->next; p->next=q->next;
e=q->data; free(q);
return OK;
}
void Combine_L(LinkList &La,LinkList &Lb,LinkList &Lc)//将两个有序链表合并成一个有序链表Lc
{
LinkList pa,pb,pc,p;
p=(LinkList)malloc(sizeof(LNode)); p->next=NULL;
pa=La->next; pb=Lb->next; pc=Lc;
while(pa&&pb)
{
if(pa->data<pb->data)
{
pc->next=p; pc=p; pc->data=pa->data; pa=pa->next;
p=(LinkList)malloc(sizeof(LNode)); p->next=NULL;
}
else if(pa->data>pb->data)
{
pc->next=p; pc=p; pc->data=pb->data; pb=pb->next;
p=(LinkList)malloc(sizeof(LNode)); p->next=NULL;
}
else if(pa->data=pb->data)
{
pc->next=p; pc=p; pc->data=pa->data; pb=pb->next; pa=pa->next;
p=(LinkList)malloc(sizeof(LNode));
}
}
if(pa==NULL)
while(pb)
{
pc->next=p; pc=p; pc->data=pb->data; pb=pb->next;
p=(LinkList)malloc(sizeof(LNode)); p->next=NULL;
}
else if(pb==NULL)
while(pa)
{
pc->next=p; pc=p; pc->data=pa->data; pa=pa->next;
p=(LinkList)malloc(sizeof(LNode)); p->next=NULL;
}
}
int LenList(LinkList L) //求链表中节点的个数,即链表的长度
{
LinkList p; p=L;
int n=0;
if(!L->next)
return n;
while(p->next)
{
n++; p=p->next;
}
return n;
}
status paixu(LinkList &L) //排序
{
LinkList p1,p2; int t;
p1=L; p2=L;
if(L->next==0)
return 0;
else if(!L->next->next)
return 1;
else
{
for(p1=L->next;p1->next!=NULL;p1=p1->next)
{
for(p2=p1->next;p2!=NULL;p2=p2->next)
{
if(p1->data>p2->data)
{
t=p1->data; p1->data=p2->data; p2->data=t;
}//if
}//for
}//for
}//else
return 2;
}//status
void ClearList(LinkList &L) //将一个链表清空,即只留一个头节点
{
LinkList p,q; int n=1;
p=L->next;
while(p)
{
q=p;
if(n==1)
{
L->next=NULL; n=0;
}
p=p->next;
free(q);
}
}
void Divide(LinkList &Lc,LinkList &La,LinkList &Lb) //将一个带头节点的单链表La分解成两个同样结构的单链表Lb,Lc,使得Lb中只
{ //含La中表中的奇数节点,Lc中含有La表的偶数结点
LinkList pa,pb,pc,p1,p2;
pa=La; pb=Lb; pc=Lc;
p1=(LinkList)malloc(sizeof(LNode));p1->next=NULL; p2=(LinkList)malloc(sizeof(LNode));p2->next=NULL;
while(pc->next)
{
pc=pc->next;
if(pc->data%2==1)
{
pa->next=p1; pa=p1;
pa->data=pc->data;
p1=(LinkList)malloc(sizeof(LNode)); p1->next=NULL;
}
else if(pc->data%2==0)
{
pb->next=p2; pb=p2;
pb->data=pc->data;
p2=(LinkList)malloc(sizeof(LNode)); p2->next=NULL;
}
}
}
void main() //主函数
{
int sele,e,i,num,j=0,k,m,n=1;
LinkList head,La,Lb,Lc;
printf("Now,you can set up three lists----La,Lb,Lc.假如让Lc为空即Lc只输0进去\n");
printf("La: ");
CreateList_L1(La); printf("La: ");
Print_L(La);
printf("Lb: ");
CreateList_L1(Lb); printf("Lb: ");
Print_L(Lb);
printf("Lc: ");
CreateList_L1(Lc); printf("Lc: ");
Print_L(Lc); //建立一个空表,只有头节点
while(1)
{
//if(j%2==0)
printf("********************************************************************************");//每完成一个函数就输出星号
printf("Now:");
printf(" La: "); Print_L(La);
printf(" Lb: "); Print_L(Lb);
printf(" Lc: "); Print_L(Lc); //printf("\nLa,Lb,Lc现在分别如下:\n");//Print_L(La); Print_L(Lb); Print_L(Lc);
if(j++%2==0) //每完成两个函数功能就输出函数表
{
printf("Functions are as follows:\n");
printf("_______________________________________________________________________________ ");
printf("1,insert element | ");
printf("2,delete element | ");
printf("3,locate a data\n");
printf("_______________________________________________________________________________ ");
printf("4,find a data | ");
printf("5,reverse the list | ");
printf("6,combine the two lists\n");
printf("_______________________________________________________________________________ ");
printf("7,get the length of the list | ");
printf("8,paixu | ");
printf("9,clear the list\n");
printf("_______________________________________________________________________________ ");
printf("10,divide one list to two ones| ");
printf("11,print the list |\n");
printf("_______________________________________________________________________________ ");
printf("Do you want to konw the exact meaning of some function in Chinese.Yes: 1,No: 0, end the program: 2 k="); //可直接输入函数的号,不一定要输入1,反正只要不是0就可以了
scanf("%d",&k);
if(k==2)
break;
while(k)
{
printf("Please input the number in front of the function you don't kown(Input 0 to skip the circle).k=");
scanf("%d",&k);
if(k==0)
break;
else
switch(k)
{
case 1:printf("插入节点,先要输入插入的数值再输入插入的位置。\n"); break;
case 2:printf("删除一个节点,你只须输入要删除的数的位置即可,那个数就一定会被删的。\n"); break;
case 3:printf("定位一个节点,你只须输入一个数,就在链表中查找该数并能返回其位