...有序链表的插入,删除结点基本操作,及两个有序链表的归并代码_百度知 ...
发布网友
发布时间：2024-10-18 14:18
共1个回答
热心网友
时间：2024-11-17 12:17
//动态单向链表结构
//单文件版
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <string.h>
#include <malloc.h>
#define LEN sizeof(S_MESSAGE)
#define N 10
typedef struct songer //定义选手信息链表结构
{
long num; //选手编号
char name[20]; //选手姓名
float grades[N]; //选手成绩
double ave; //平均成绩
struct songer * next; //链表的结点，next是指针变量，指向结构体变量
}S_MESSAGE;
S_MESSAGE * head; //定义链表的头指针
S_MESSAGE * tail; //定义链表的尾指针
int n=0; // n为全局变量，用于统计结点的个数
void creat(); //建立单向动态链表。此函数带回一个指向链表头的指针,用于参赛选手的录入
void del(); //用于删除结点，用于参赛选手的删除
void search(); //参赛选手成绩的查询
void print(); //用于输出链表
void rank(); //按个人平均成绩从高到低的顺序进行排序
void update(); //参赛选手的修改
void menu(); //操作系统菜单界面
void menu_select(); //菜单选择界面
void browse(); //选手信息浏览
void save(); //选手信息保存
void quit(); //退出系统界面
/*------------------------------------ rank函数 -----------------------------------------*/
void rank()
{
S_MESSAGE *p1,*p2,*endpt,*p; // *endpt/*控制循环比较*/ *p/*临时指针变量*/
n=0;
p1=head;
if(head == NULL && tail == NULL)
{
printf("\n--------当前信息记录为空--------\n");
}
else
{
p1 = (S_MESSAGE *)malloc(LEN);
p1->next = head; /*注意理解：我们增加一个节点，放在第一个节点的前面，主要是为了便于比较。因为第一个节点没有前驱，我们不能交换地址。*/
head = p1; /*让head指向p1节点，排序完成后，我们再把p1节点释放掉*/
for(endpt=NULL; endpt!=head; endpt=p) /*结合第6点理解*/
{
for(p=p1=head; p1->next->next!=endpt; p1=p1->next)
{
if(p1->next->ave < p1->next->next->ave) /*如果前面的节点键值比后面节点的键值小，则交换*/
{
p2 = p1->next->next; //1、排序后q节点指向p节点，在调整指向之前，我们要保存原p的指向节点地址，即：p2=p1->next->next
p1->next->next = p2->next; //2、顺着这一步一步往下推,排序后p1->next->next要指的是p2->next,所以p1->next->next=p2->next
p2->next = p1->next; //3、p2->next原是q发出来的指向，排序后q的指向要变为指向p的，而原来p1->next是指向p的，所以p2->next=p1->next
p1->next = p2; //4、p1->next原是指向p的，排序后图16中p1->next要指向q,原来p1->next->next（即p2)是指向q的，所以p1->next=p2
p = p1->next->next; //5、至此，完成了相邻两节点的顺序交换
}
}
}
p1 = head; /*把p1的信息去掉*/
head = head->next; /*让head指向排序后的第一个节点*/
free(p1); /*释放p1*/
printf("\n-----------选手成绩排名信息如下---------\n");
printf("--------|--------|--------|--------\n");
printf(" 编号 | 姓名 |平均成绩| 名次 \n");
p1=head;
while(p1 != NULL)
{
printf("--------|--------|--------|--------\n");
printf(" %-9d%-9s%-9.1lf%-5d\n",p1->num,p1->name,p1->ave,n+1);
n++;
p1=p1->next;
}
printf("--------|--------|--------|--------\n");
}
getchar();
}
/*------------------------------------ print函数 -----------------------------------------*/
void print()
{
S_MESSAGE * p1=(S_MESSAGE *)malloc(LEN);
int check=0,i;
long seeknum;
printf("\n请输入要查找的选手编号：");
scanf("%d",&seeknum);
if(head == NULL && tail == NULL )
{
printf("\n对不起，当前记录为空!\n");
}
else
{
p1=head;
printf("\n-----------你要找的选手的成绩如下---------\n");//在这里找到了要查找的选手成绩
printf("------|------|------|----|----|----|----|----|----|----|----|----|----|--------\n");
printf(" 编号 | 姓名 | 成绩 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |平均成绩\n");
printf("------|------|------|----|----|----|----|----|----|----|----|----|----|--------\n");
while(p1 != NULL)
{
if(p1->num == seeknum)
{
printf(" %-7d%-6s",p1->num,p1->name);
printf(" ");
for(i=0;i<N;i++)
{
printf(" %.1f ",p1->grades[i]);
}
printf(" %-6.2lf\n",p1->ave);
check=1;
getchar();
return;
}
else
{
p1=p1->next;
}
}
}
if(head != NULL && check == 0)
{
printf("\n对不起，你查看的选手成绩不存在!\n");
}
getchar();
}
/*----------------------------------- search函数 -----------------------------------------*/
void search()
{
int c;
printf("\n请选择查询内容：\n");
printf("1.选手详细成绩查询 2.选手排名查询\n请输入您的选择：");
scanf("%d",&c);
switch(c)
{
case 1:system("cls");print();break;
case 2:system("cls");rank();break;
}
}
/*------------------------------------ save函数 ------------------------------------------*/
void save()//将数据保存到文件
{
FILE *fp;
S_MESSAGE *p1;//=(S_MESSAGE *)malloc(LEN);
p1=head;
fp=fopen("参赛选手名单.txt","w");
fprintf(fp,"--------|--------\n");
fprintf(fp," 编号 | 姓名 \n");
while(p1 != NULL)
{
fprintf(fp,"--------|--------\n");
fprintf(fp," %-9d%-6s\n",p1->num,p1->name);
p1=p1->next;
}
fprintf(fp,"--------|--------\n");
fclose(fp);
printf("\n\t文件已将保存到\"参赛选手名单.txt\"");
}
/*----------------------------------- update函数 -----------------------------------------*/
void update()
{
S_MESSAGE *p1;//=(S_MESSAGE *)malloc(LEN);
int check=0; //用来进行判断，是否找到了要修改的信息
long updatenum;
printf("\n请输入要修改的选手编号:");
scanf("%d",&updatenum);//查找到要修改的选手
if(head == NULL && tail == NULL)
{
printf("\n--------当前信息记录为空--------\n");
}
else
{
p1=head;
while(p1 != NULL)
{
if(p1->num == updatenum)
{
printf("\n-----------你要修改的选手信息如下---------\n");
printf("--------|--------\n");
printf(" 编号 | 姓名 \n");
printf("--------|--------\n");
printf(" %-9d%-6s\n",p1->num,p1->name);
printf("--------|--------\n");
printf("\n-----------请重新写入此选手信息:---------\n");
check=1;//从新写入修改项目
printf("\n修改选手编号为：");
scanf("%d",&p1->num);
printf("\n修改选手姓名为：");
scanf("%s",p1->name);
return;
}
else
{
p1=p1->next;
}
}
}
if(head != NULL && check == 0)
{
printf("\n对不起，你要修改的选手信息不存在!\n");
}
getchar();
}
/*----------------------------------- browse函数 -----------------------------------------*/
void browse()
{
S_MESSAGE *p1;
if(head == NULL && tail == NULL)
{
printf("\n--------当前信息记录为空--------\n");
}
else
{
printf("\n-----------你要浏览的选手信息如下---------\n");
printf("--------|--------\n");
printf(" 编号 | 姓名 \n");
p1=head;
while(p1 != NULL)
{
printf("--------|--------\n");
printf(" %-9d%-6s\n",p1->num,p1->name);
p1=p1->next;
}
printf("--------|--------\n");
}
}
/*------------------------------------- del函数 ------------------------------------------*/
void del()
{
S_MESSAGE *node;//=(S_MESSAGE *)malloc(LEN);
S_MESSAGE *p1;
int check=0; //用来进行判断，是否找到了要删除的信息
long del_num;
printf("\n请输入要删除的选手的编号：");
scanf("%d",&del_num);
if(head == NULL && tail ==NULL)
{
printf("\n当前信息记录为空，删除失败！\n");
}
else
{
node=head;
p1=head;
while(node != NULL)
{
if(node->num == del_num)
{
printf("\n--------要删除的选手信息--------\n");
printf("--------|--------\n");
printf(" 编号 | 姓名 \n");
printf("--------|--------\n");
printf(" %-9d%-6s\n",node->num,node->name); //在这里找到了要删除的选手信息
printf("--------|--------\n");
check=1; //找到要删除的信息，赋为真
if(node == head && head->next == NULL) //是头结点，并且只有一个结点
{
head=NULL;
tail=head;
free(node);
printf("\n--------删除信息成功--------\n"); //删除唯一的节点
}
else if(node == head && head->next != NULL) //删除头节点
{
node=head;
head=head->next;
free(node);
printf("\n--------删除信息成功--------\n"); //头节点删除成功
n=n-1;
}
else if(node ->next != NULL) //删除中间节点
{
p1->next=node->next;
free(node);
printf("\n--------删除信息成功--------\n"); //中间节点删除成功
n=n-1;
}
else if(node->next == NULL) //删除尾节点
{
p1->next=NULL;
tail=p1;
free(node);
printf("\n--------删除信息成功--------\n"); //尾节点删除成功
n=n-1;
}
getchar();
return;
}
else
{
p1=node;
node=node->next;
}
}
}
if(head != NULL && check == 0)
{
printf("\n对不起，你要删除的选手信息不存在!\n");
}
getchar();
}
/*------------------------------------ creat函数 -----------------------------------------*/
void creat()
{
int i,j;
float t;
char c='y';
while(c == 'y' || c == 'Y')
{
S_MESSAGE *p1=(S_MESSAGE *)malloc(LEN);
printf("\n请输入要录入的选手信息：\n");
printf("\n选手编号：");
scanf("%d",&p1->num);
printf("\n选手姓名：");
scanf("%s",p1->name);
printf("\n请输入10位评委点评成绩：");
p1->ave = 0;
for(i=0;i<N;i++)
{
scanf("%f",&(p1->grades[i])); //runtime error
p1->ave += p1->grades[i];
}
for(i=0;i<N-1;i++) //冒泡排序法让那个成绩从小到大排列，然后选出最大值是最后一个，最小值是第一个
for(j=0;j<N-1-i;j++)
if(p1->grades[j]>p1->grades[j+1])
{
t=p1->grades[j];
p1->grades[j]=p1->grades[j+1];
p1->grades[j+1]=t;
}
p1->ave=(p1->ave-(p1->grades[0]+p1->grades[9]))/8;//去掉一个最高分，去掉一个这一低分，得出最后的平均分
p1->next=NULL;
if(p1==NULL)
{
printf("\n内存分配失败\n");
n=n-1;
}
if(head == NULL && tail == NULL) //当前没有结点，创建第一个结点
{
head=p1;
head->next=NULL;
tail=head;
printf("\n------选手信息录入成功------\n");
}
else //如果当前还有节点则插入到尾部
{
tail->next=p1;
tail=p1;
tail->next=NULL;
printf("\n------选手信息录入成功------\n");
}
printf("是否继续(Y/N):");
getchar();
scanf("%c",&c);
}
}
/*------------------------------------- quit函数 -----------------------------------------*/
void quit()
{
printf("\n\n\t==========》感谢您使用歌唱比赛评分系统《==========\n\n");
}
/*------------------------------------- menu函数 -----------------------------------------*/
void menu()
{
printf("\n\n\t*************** 歌唱比赛评分系统 ***************\n\n");
printf("\t1.选手信息浏览 2.选手信息录入\n");
printf("\t3.选手信息保存 4.选手成绩查询\n");
printf("\t5.选手信息修改 6.选手信息删除\n");
printf("\t 7.退出系统\n");
printf("\n\t*************** 系统菜单选择界面 ***************\n");
printf("\t>> 请根据您想执行的命令，输入对应功能的数字键 <<\n");
printf("请输入您的选择：");
}
/*--------------------------------- menu_select函数 --------------------------------------*/
void menu_select()
{
char s[100];
int c;
gets(s); //不管用户输入的是数字键或是字母键使用gets都能将输入作为字符串接收
while(1) //限定用户输入的数值必须在1-7之间才有效，否则要求重新输入
{
c = atoi(s); //利用atoi()函数将所接收的字符串转换成数值，提供给if语句判断
if(c < 1 || c >7)
{
printf("您的输入有误，请重新输入：");
gets(s);
}
else break;
}
switch(c)
{
case 1:
system("cls"); //清屏
browse();
break;
case 2:
system("cls");
creat();
break;
case 3:
system("cls");
save();
break;
case 4:
system("cls");
search();
break;
case 5:
system("cls");
update();
break;
case 6:
system("cls");
del();
break;
case 7:
system("cls");
quit();
return;
break;
default:
break;
}
getchar();
system("cls");
menu();
menu_select();
}
/*------------------------------------- main函数 -----------------------------------------*/
int main()
{
menu();
menu_select();
return 0;
}
这是我以前写过的一个程序，里面包含了单向链表的各种操作，你可以看一看。至于你说的归并，实在不好意思，还没有学数据结构，那个帮不了你。悬赏我也不要，没有解决问题。
