#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
//定义节点结构体
typedef struct _node{
int value; //定义链表一个节点的数据域
struct _node *next; //定义链表一个节点的指针域
}Node,Date; //两个链表的名字
//函数声明
void ShowMenu();
Node *choosen();
Date *choosed();
Node *nadd();
Node *nsort(Node *phead);
Node *nprint(Node *phead);
Node *ndelet1(Node *phead);
Node *ninsert(Node *phead);
Node *ndelet0(Node *phead);
Date *dadd();
Date *dsort(Date *phead);
Date *dprint(Date *phead);
Date *ddelet1(Date *phead);
Date *dinsert(Date *phead);
Date *ddelet0(Date *phead);
Node *ndconnect(Node *pnhead,Date *pdhead);
int main()
{
printf("***********************************************
");
printf("19级电科一班刘子琦、陈辉、徐超杰，李新玖共同制作
");
printf("***********************************************
");
ShowMenu(); //调用函数
return 0;
}
void ShowMenu() //菜单
{
Node *nhead,*ndhead,*p;
Date *dhead;
char i;
printf("选择链表，输入‘n’或者‘d’
输入‘L’为两个链表连接并输出（警告：需要先创建链表）
输入‘H’退出：");
while( i != 'H' )
{
scanf("%c",&i);
switch(i) //调用函数
{
case('n'):nhead = choosen();break;
case('d'):dhead = choosed();break;
case('L'):ndhead = ndconnect(nhead,dhead);
for( p=ndhead ; p ; p=p->next ) //遍历链表并输出
{
printf("%d
", p->value );
}
printf("
"); break;
case('H'):break;
}
}
}
Node *choosen()
{
Node *head,*phead;
char i;
printf("输入I为输入数据。
输入R为链表排序。
输入O为输出数据。
输入S为查找和删除数据。
输入E为插入数据。
输入D为删除链表。
输入G为退出
");
while(i != 'G')
{
scanf("%c",&i);
switch(i) //调用函数
{
case('I'):head = phead = nadd();break;
case('R'):head = nsort(phead);break;
case('O'):head = nprint(phead);break;
case('S'):head = ndelet1(phead);break;
case('E'):head = ninsert(phead);break;
case('D'):head = ndelet0(phead);break;
case('G'):printf("已退出。
");break;
}
}
return phead;
}
Date *choosed()
{
Date *head,*phead;
char i;
printf("输入I为输入数据。
输入R为链表排序。
输入O为输出数据。
输入S为查找和删除数据。
输入E为插入数据。
输入D为删除链表。
输入G为退出
");
while(i != 'G')
{
scanf("%c",&i);
switch(i) //调用函数
{
case('I'):head = phead = dadd();break;
case('R'):head = dsort(phead);break;
case('O'):head = dprint(phead);break;
case('S'):head = ddelet1(phead);break;
case('E'):head = dinsert(phead);break;
case('D'):head = ddelet0(phead);break;
case('G'):printf("已退出。
");break;
}
}
return phead;
}
Node *nadd()
{
int number;
Node *phead = NULL; //初始化
do{
printf("输入数据,输入-1结束："); //输入数据
scanf("%d",&number);
if(number != -1)
{
Node *p=(Node*)malloc(sizeof(Node)); //申请内存空间
p -> value = number; //将刚输入的数据存入新建节点的数据域中
p -> next = NULL; //新建节点指针域初始化
Node *last = phead; //定义并初始化指向下一个节点的指针
if(last) //判断该指针是否为空
{
while(last -> next) //判断该指针指向的节点的指针域是否为空
{
last = last -> next; //使该指针指向下一个节点
}
last -> next = p; //将指针p的值赋给last指针
}else
{
phead = p; //使头指针指向第一个节点
}
}
}while(number != -1); //判断输入的数据是否为-1
return phead;
}
Node *nsort( Node *phead )
{
Node *p,*tail,*q; //定义结点指针
p = q = tail = NULL; //初始化
if(phead == NULL || phead->next == NULL) //排除空链表和单节链表
{
printf("无需排序。
");
return;
}
while(phead != tail) //外循环
{
int Ischange = 0; //定义判断变量
p = phead; //使p指针指向头节点
q = p->next; //使q指针指向第二节节点
while(q != tail) //内循环
{
if(p->value > q->value) //比较
{
int number = q->value; //将两个节点调换
q->value = p->value;
p->value = number;
Ischange = 1;
}
p = p->next; //向后移动
q = q->next; //向后移动
}
if(!Ischange)
{
printf("排序完成！
");
return;
}
tail = p; //尾节点指针向前移动
}
printf("排序完成！
"); //提示
return phead;
}
Node *nprint( Node *phead )
{
Node *p = NULL; //定义结点指针并初始化
for( p=phead ; p ; p=p->next ) //循环遍历链表
{
printf("%d
", p->value );
}
printf("
");
return phead;
}
Node *ndelet1( Node *phead )
{
int number,sam;
printf("输入要查找的值：");
scanf("%d", &number );
int isFound = 0; //定义判断变量
Node *p,*q; //定义结点指针
for( q=NULL , p=phead ; p ; q=p , p=p->next)
{
if(p->value == number) //判断是否符合要找的数据
{
printf("找到了。
"); //遍历链表查找
isFound = 1;
break;
}
}
if( !isFound )
{
printf("没找到。
");
}
if( isFound == 1 )
{
printf("是否删除？删除输入1，否则输入0.
");
scanf("%d",&sam);
switch(sam)
{
case(1):for( q=NULL , p=phead ; p ; q=p , p=p->next)
{
if(p->value == number)
{
if( q )
{
q->next = p->next; //删除一个节点并连接剩下的节点
}else{
phead = p->next;
}
free(p);
printf("删除完成！
");
break;
}
}
break;
case(0):break;
default:printf("无效！
");
}
}
return phead;
}
Node *ninsert( Node *phead ) //插入节点函数
{
int number,a;
printf("输入要插入的值：");
scanf("%d",&number);
Node *p=(Node*)malloc(sizeof(Node)); //申请新节点空间
p->value = number; //将输入的数据存入新节点数据域
p->next = NULL; //初始化新节点指针域
Node *q,*i; //定义结点指针
printf("输入想要插入的到节点后面的节点的值：");
scanf("%d",&a);
for( q=NULL , i=phead ; i ; q=i , i=i->next) //遍历链表查找
{
if(i->value == a)
{
p->next = i->next; //将新节点指针域存入下一个节点指针值
i->next = p; //将找到的节点的指针域存入新节点指针值
break;
}
}
printf("插入完成！
");
return phead;
}
Node *ndelet0( Node *phead )
{
Node *q,*p; //定义结点指针
for( p = phead ; p ; p=q ) //遍历链表
{
q = p -> next; //全部删除
free(p);
}
printf("删除完成！
");
return phead;
}
Date *dadd()
{
int number;
Date *phead = NULL; //初始化
do{
printf("输入数据,输入-1结束："); //输入数据
scanf("%d",&number);
if(number != -1)
{
Date *p=(Date*)malloc(sizeof(Date)); //申请内存空间
p -> value = number; //将刚输入的数据存入新建节点的数据域中
p -> next = NULL; //新建节点指针域初始化
Date *last = phead; //定义并初始化指向下一个节点的指针
if(last) //判断该指针是否为空
{
while(last -> next) //判断该指针指向的节点的指针域是否为空
{
last = last -> next; //使该指针指向下一个节点
}
last -> next = p; //将指针p的值赋给last指针
}else
{
phead = p; //使头指针指向第一个节点
}
}
}while(number != -1); //判断输入的数据是否为-1
return phead;
}
Date *dsort( Date *phead )
{
Date *p,*tail,*q; //定义结点指针
p = q = tail = NULL; //初始化
if(phead == NULL || phead->next == NULL) //排除空链表和单节链表
{
printf("无需排序。
");
return;
}
while(phead != tail) //外循环
{
int Ischange = 0; //定义判断变量
p = phead; //使p指针指向头节点
q = p->next; //使q指针指向第二个节点
while(q != tail) //内循环
{
if(p->value > q->value) //比较
{
int number = q->value; //将两个节点调换
q->value = p->value;
p->value = number;
Ischange = 1;
}
p = p->next; //向后移动
q = q->next; //向后移动
}
if(!Ischange)
{
printf("排序完成！
");
return;
}
tail = p; //尾结点指针向前移动
}
printf("排序完成！
"); //提示
return phead;
}
Date *dprint( Date *phead )
{
Date *p = NULL; //定义结点指针并初始化
for( p=phead ; p ; p=p->next ) //循环遍历链表
{
printf("%d
", p->value );
}
printf("
");
return phead;
}
Date *ddelet1( Date *phead )
{
int number,sam;
printf("输入要查找的值：");
scanf("%d", &number );
int isFound = 0; //定义判断变量
Date *p,*q; //定义结点指针
for( q=NULL , p=phead ; p ; q=p , p=p->next)
{
if(p->value == number) //判断是否符合要找的数据
{
printf("找到了。
"); //遍历链表查找
isFound = 1;
break;
}
}
if( !isFound )
{
printf("没找到。
");
}
if( isFound == 1 )
{
printf("是否删除？删除输入1，否则输入0.
");
scanf("%d",&sam);
switch(sam)
{
case(1):for( q=NULL , p=phead ; p ; q=p , p=p->next)
{
if(p->value == number)
{
if( q )
{
q->next = p->next; //删除一个节点并连接剩下的节点
}else{
phead = p->next;
}
free(p);
printf("删除完成！
");
break;
}
}
break;
case(0):break;
default:printf("无效！
");
}
}
return phead;
}
Date *dinsert( Date *phead ) //插入节点函数
{
int number,a;
printf("输入要插入的值：");
scanf("%d",&number);
Date *p=(Date*)malloc(sizeof(Date)); //申请新节点空间
p->value = number; //将输入的数据存入新节点数据域
p->next = NULL; //初始化新节点指针域
Date *q,*i; //定义结点指针
printf("输入想要插入的到节点后面的节点的值：");
scanf("%d",&a);
for( q=NULL , i=phead ; i ; q=i , i=i->next) //遍历链表查找
{
if(i->value == a)
{
p->next = i->next; //将新节点指针域存入下一个节点指针值
i->next = p; //将找到的节点的指针域存入新节点指针值
break;
}
}
printf("插入完成！
");
return phead;
}
Date *ddelet0( Date *phead )
{
Date *q,*p; //定义结点指针
for( p = phead ; p ; p=q ) //遍历链表
{
q = p -> next; //全部删除
free(p);
}
printf("删除完成！
");
return phead;
}
Node *ndconnect( Node *pnhead,Date *pdhead ) //链表连接函数
{
Node *p,*tail,*q; //定义结点指针
if(pnhead == NULL) //排除链表为空情况
{
return pdhead; //返回头节点
}
if(pdhead == NULL) //排除链表为空情况
{
return pnhead; //返回头节点
}
p = pnhead; //读取头节点
while( p->next ) //循环找到尾节点
{
p = p->next;
}
p->next = pdhead; //连接
p = q = tail = NULL; //初始化
if(pnhead == NULL || pnhead->next == NULL) //排除空链表和单节链表
{
return pnhead; //返回头节点
}
while(pnhead != tail) //外循环
{
int Ischange = 0; //定义判断变量
p = pnhead; //使p指针指向头节点
q = p->next; //使q指针指向第二节节点
while(q != tail) //内循环
{
if(p->value > q->value) //比较
{
int number = q->value; //将两个节点调换
q->value = p->value;
p->value = number;
Ischange = 1;
}
p = p->next; //向后移动
q = q->next; //向后移动
}
if(!Ischange)
{
return pnhead; //返回头节点
}
tail = p; //尾节点指针向前移动
}
return pnhead; //返回头节点
}
