Question

数据结构 实验题~ （高手请进）

问题描述：
某项比赛中，评委们给某参赛者的评分信息储存在一个带头结点的单向链表中，编写程序：
（1） 显示在评分中给出的最高分和最低分的有关信息（姓名、年龄、所给分数）
（2） 在链表中删除一个最高分和一个最低分的节点
（3） 计算该参赛者去掉一个最高分和一个最低分后的平均成绩
基本要求：
（1） 建立一个评委打分的单向链表
（2） 显示删除相关节点后的链表的信息
（3） 显示要求的结果
实现提示：
（1） 节点用结构变量储存，至少包含三个成员项，即姓名、评分、年龄
（2） 用头插法或尾插法建立链表
（3） 用扫描链表并逐次比较求最高分和最低分

Answer 1

单链表的操作，我已经写得差不多了，你只要改一下数据结构，应该可以满足你的要求！
#include<stdio.h>
#include <stdlib.h>
#include <math.h>

/************************************************************************/
/* 常量定义 */
/************************************************************************/
#define ElemType int
#define Status int
#define TRUE 1
#define OK 1
#define FALSE 0
#define ERROR -1

/************************************************************************/
/* 线性表的单链表存储结构*/
/************************************************************************/
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LNode, *LinkList;

//////////////////////////////////////////////////////////////////////////
//
// 带有头结点的单链表的基本操作(13个)
//
//////////////////////////////////////////////////////////////////////////

/************************************************************************/
/* 操作结果：构造一个空的线性表L */
/************************************************************************/
void InitList(LinkList *L)
{
*L = (LinkList)malloc(sizeof(struct LNode)); /* 产生头结点，并使L指向此头结点 */
if( !*L ) /* 存储分配失败 */
exit(OVERFLOW);
(*L)->next = NULL; /* 指针域为空 */
}

/************************************************************************/
/* 初始条件：线性表L已存在。*/
/* 操作结果：销毁线性表L */
/************************************************************************/
void DestroyList(LinkList *L)
{
LinkList q;
while(*L)
{
q = (*L)->next;
free(*L);
*L=q;
}
}
/************************************************************************/
/* 初始条件：线性表L已存在。*/
/* 操作结果：将L重置为空表 */
/************************************************************************/
void ClearList(LinkList L) /* 不改变L */
{
LinkList p, q;
p = L->next; /* p指向第一个结点 */
while(p) /* 没到表尾 */
{
q = p->next;
free(p);
p = q;
}
L->next = NULL; /* 头结点指针域为空 */
}

/************************************************************************/
/* 初始条件：线性表L已存在。*/
/* 操作结果：若L为空表，则返回TRUE，否则返回FALSE */
/************************************************************************/
Status ListEmpty(LinkList L)
{
/* 非空 */
return (L->next) ? FALSE : TRUE;
}

/************************************************************************/
/* 初始条件：线性表L已存在。操作结果：返回L中数据元素个数 */
/************************************************************************/
int ListLength(LinkList L)
{
int i = 0;
LinkList p = L->next; /* p指向第一个结点 */
while(p) /* 没到表尾 */
{
i++;
p = p->next;
}
return i;
}

/************************************************************************/
/* L为带头结点的单链表的头指针。*/
/* 当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR */
/************************************************************************/
Status GetElem(LinkList L, int i, ElemType *e) /* 算法2.8 */
{
int j = 1; /* j为计数器 */
LinkList p = L->next; /* p指向第一个结点 */
while(p && j < i) /* 顺指针向后查找，直到p指向第i个元素或p为空 */
{
p = p->next;
j++;
}
if( !p || j > i) /* 第i个元素不存在 */
return ERROR;
*e = p->data; /* 取第i个元素 */
return OK;
}

/************************************************************************/
/* 初始条件: 线性表L已存在，compare()是数据元素判定函数(满足为1，否则为0)*/
/* 操作结果: 返回L中第1个与e满足关系compare()的数据元素的位序。 */
/* 若这样的数据元素不存在，则返回值为0 */
/************************************************************************/
int LocateElem(LinkList L, ElemType e, Status(*compare)(ElemType, ElemType))
{
int i = 0;
LinkList p = L->next;
while(p)
{
i++;
if(compare(p->data,e)) /* 找到这样的数据元素 */
return i;
p=p->next;
}
return 0;
}

/************************************************************************/
/* 初始条件: 线性表L已存在 */
/* 操作结果: 若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱 */
/* 返回OK；否则操作失败，pre_e无定义，返回INFEASIBLE */
/************************************************************************/
Status PriorElem(LinkList L, ElemType cur_e, ElemType *pre_e)
{
LinkList q, p = L->next; /* p指向第一个结点 */
while(p->next) /* p所指结点有后继 */
{
q = p->next; /* q为p的后继 */
if(q->data == cur_e)
{
*pre_e = p->data;
return OK;
}
p = q; /* p向后移 */
}
return ERROR;
}

/*************************************************************************/
/* 初始条件：线性表L已存在 */
/* 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继*/
/* 返回OK; 否则操作失败，next_e无定义，返回INFEASIBLE */
/*************************************************************************/
Status NextElem(LinkList L, ElemType cur_e, ElemType *next_e)
{
LinkList p = L->next; /* p指向第一个结点 */
while(p->next) /* p所指结点有后继 */
{
if(p->data == cur_e)
{
*next_e = p->next->data;
return OK;
}
p = p->next;
}
return ERROR;
}

/************************************************************************/
/* 在带头结点的单链线性表L中第i个位置之前插入元素e */
/************************************************************************/
Status ListInsert(LinkList L, int i, ElemType e)
{
int j = 0;
LinkList p = L, s;
while( p && j < i-1) /* 寻找第i-1个结点 */
{
p = p->next;
j++;
}
if( !p|| j > i-1) /* i小于1或者大于表长 */
return ERROR;
s = (LinkList)malloc(sizeof(struct LNode)); /* 生成新结点 */
s->data = e; /* 插入L中 */
s->next = p->next;
p->next = s;
return OK;
}

/************************************************************************/
/* 在带头结点的单链线性表L中，删除第i个元素，并由e返回其值 */
/************************************************************************/
Status ListDelete(LinkList L, int i, ElemType *e)
{
int j = 0;
LinkList p = L, q;
while(p->next && j < i-1) /* 寻找第i个结点，并令p指向其前岖 */
{
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;
}

/************************************************************************/
/* 初始条件：线性表L已存在。操作结果：依次对L的每个数据元素调用函数vi() */
/************************************************************************/
void ListTraverse(LinkList L, void(*vi)(ElemType))
{
LinkList p = L->next;
while(p)
{
vi(p->data);
p = p->next;
}
printf("\n");
}

/************************************************************************/
/* 初始条件：线性表L已存在。打印链表的data域 */
/************************************************************************/
void ListPrint(LinkList L)
{
LinkList p = L->next;
while(p)
{
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}

void printInt(int data)
{
printf("%d ", data);
}

/************************************************************************/
/* 插入排序 */
/************************************************************************/
void ListSort(LinkList L)
{
LinkList first, p, q; //为原链表剩下用于直接插入排序的节点头指针
LinkList t; //临时指针变量：插入节点

//原链表剩下用于直接插入排序的节点链表
first = L->next;

//只含有一个节点的链表的有序链表
L->next = NULL;

//遍历剩下无序的链表
while (first != NULL)
{
//无序节点在有序链表中找插入的位置
for (t = first, q = L; ((q != NULL) && (q->data < t->data)); p = q, q = q->next);

//退出for循环，就是找到了插入的位置
first = first->next;

p->next = t;

//完成插入动作
t->next = q;
}
}

//排序，指针交换法
void ListSort1(LinkList L)
{
LinkList head = L->next;//head指向除头结点以外的链表
LinkList pre_p; //p的前驱结点
LinkList pre_q; //q的前驱结点
LinkList min; //最小的结点
LinkList p, q, temp;

for(p = head; p->next; pre_p = min, p = min->next)
{
//找出最小的结点
for(min = p, q = p; q->next; q = q->next)
{
if(q->next->data < min->data)
{
pre_q = q;
min = q->next;
}
}

//如果最小是自己 就不需要交换
if(min == p) continue;

//如果p是指向head的结点，则链表直接指向min
if(p == head)
L->next = min;
else
pre_p->next = min;

temp = min->next;
if(p->next == min)
{
min->next = p;
p->next = temp;
}
else
{
min->next = p->next;
pre_q->next = p;
p->next = temp;
}
}
}

//排序，数据选择法排序
void ListSort2(LinkList L)
{
LinkList head = L->next;//head指向除头结点以外的链表
LinkList min; //最小的结点
LinkList p, q; //遍历链表指针
int temp;
for (p = head; p->next; p = p->next)
{
//在p指针后的链表选取最小的结点
for (min = p, q = p->next; q; q = q->next)
{
if (q->data < min->data)
min = q;
}

//两者结点值不相等，数据交换
if (min->data != p->data)
{
temp = min->data;
min->data = p->data;
p->data = temp;
}
}
}

void main()
{
LinkList L;
InitList(&L);
ListInsert(L, 1, 6);
ListInsert(L, 1, 3);
ListInsert(L, 1, 67);
ListInsert(L, 1, 2);
ListInsert(L, 1, 15);
ListInsert(L, 1, 13);
ListInsert(L, 1, 10);

ListSort2(L);
ListTraverse(L, printInt);
}

Answer 2

指南针的始祖——司南