一、程序代码
#include<tchar.h>
#include <stdio.h>
#include "stdlib.h"
#include <conio.h>
#include <string.h>
#define MaxSize 100 //线性表最大元素个数，可调。
typedef struct {
long cno; // 学号
float mark;// 学生成绩
float cflag;
} ElemType; //自定义数据类型，可调。
typedef struct {
ElemType* list; // 存储空间基址指针
int size; // 当前元素个数
int maxsize; // 存储空间长度
} SqList;
void init_sq(SqList& L);
int find(SqList L, long cardnumber);
int addnew(SqList& L, long& cardnumber);
void actnew(SqList& L);
void display(SqList L);
void SelectSort(SqList& L);
void displayall(SqList L);
void exitout();
int _tmain(int argc, _TCHAR* argv[]) {
long cardnumber;
long cnum;
int flag;
SqList student;
char choose = '\0';
//cnum = FValue;
init_sq(student);
while (1) {
system("cls");
fflush(stdin);
printf("\n\n\n\n");
printf("\n\t||---------------------------------------------------------||");
printf("\n\t| 1. 记录学生成绩 |");
printf("\n\t| 2. 求平均分 |");
printf("\n\t| 3. 成绩汇总 |");
printf("\n\t| 4. 学生信息查询 |");
printf("\n\t| 5. 信息显示(按成绩递减排序) |");
printf("\n\t| 0. 退 出 |");
printf("\n\t|---------------------------------------------------------- |");
printf("\n\t请选择(0-5)：");
choose = getchar();
switch (choose) {
case '1': flag = addnew(student, cnum);
if (flag == -1) {
printf("内存分配错误，无法增加新卡！\n");
_getch();
}
else {
printf("学生信息录入成功！\n");
printf("请按任意键继续…");
_getch();
}
break;
case '2': actnew(student);
printf("请按任意键继续…");
_getch();
break;
case '3': displayall(student);
printf("请按任意键继续…");
break;
case '4': display(student);
break;
case '5': SelectSort(student);
displayall(student);
break;
case 'e': break;
case '0': exitout();
break;
default: printf("\n\t输入错误，请重新选择！");
_getch();
}
}
}
void init_sq(SqList& L) { //顺序表初始化
L.list = (ElemType*)malloc(MaxSize * sizeof(ElemType));
L.size = 0;
L.maxsize = MaxSize;
}
int againMalloc(SqList& L) {//存储空间再分配
ElemType* newbase = (ElemType*)realloc(L.list, (L.maxsize * 2) * sizeof(ElemType));
if (!newbase) {
printf("存储空间分配失败！");
return 0;
}
L.list = newbase;
L.maxsize = 2 * L.maxsize;
return 1;
}
int find(SqList L, long cardnumber) {//按值查找元素，返回元素所在位置；失败时返回。
int i;
L.list[0].cno = cardnumber; //监视哨存放在list[0]
//从尾至头递减查找
for (i = L.size; cardnumber != L.list[i].cno; i--);
return i; //查找成功：返回找到记录的下标；
//查找失败：返回
}
int addnew(SqList & L, long& cardnumber) {
int f;
float b;
long a;
printf("请输入学号");
scanf_s("%ld", &a);
printf("请输入成绩");
scanf_s("%f", &b);
L.list[L.size].cno = a;
L.list[L.size].mark = b;
L.size++;
if (L.size >= L.maxsize) {
f = againMalloc(L);
if (!f) return -1;
}
return 1;
}
void actnew(SqList & L)
{
float z = 0;
int i;
for (i = 0; i < L.size; i++)
{
z = z + L.list[i].mark;
}
z = z / L.size;
printf("%f", z);
}
void display(SqList L) {
int i = 0;
int j = 0;
long x;
printf("请输入要查找的学号");
scanf_s("%ld", &x);
for (i = 0; i < L.size; i++)
{
if (L.list[i].cno == x)
{
j = 1;
break;
}
}
if (j == 1)
printf("\n\t学号：%ld 成绩：%7.2f ", L.list[i].cno, L.list[i].mark);
else
printf("学号不存在");
printf("\n按任意键继续...\n");
_getch();
}
void SelectSort(SqList & L) { //简单选择排序--按卡内余额递减排序
int i, k, j;
float x;
long y;
for (i = 0; i <= L.size; i++) {
k = i;
for (j = i + 1; j <= L.size; j++)
if (L.list[j].mark > L.list[k].mark)
k = j;
if (k != i) {
x = L.list[i].mark;
y = L.list[i].cno;
L.list[i].mark = L.list[k].mark; L.list[k].mark = x;
L.list[i].cno = L.list[k].cno; L.list[k].cno = y;
}
}
}
void displayall(SqList L) {
int i;
system("cls");
printf("\n\t|----------------------------------------------------|");
printf("\n\t| 学号 | 成绩 | ");
for (i = 0; i < L.size; i++) {
if (L.list[i].cflag == 0) continue;
else {
printf("\n\t|----------------------------------------------------|");
printf("\n\t| %10d | %8.2f | ", L.list[i].cno, L.list[i].mark);
if ((i + 1) % 20 == 0) {
printf("\n按任意键继续...\n");
_getch();
}
}
}
printf("\n\t|----------------------------------------------------|");
printf("\n\n按任意键继续...\n");
_getch();
}
void exitout() {
char choose = '\0';
do {
fflush(stdin);
system("cls");
printf("\n\t确定退出吗(y/n)?");
scanf_s("%c", &choose, sizeof(choose));
} while (choose != 'Y' && choose != 'y' && choose != 'N' && choose != 'n');
if (choose == 'Y' || choose == 'y') exit(0);
}
#include <stdio.h>
#include "stdlib.h"
#include <conio.h>
#include <string.h>
#include <conio.h>
#include "ctype.h"
#define Null 0
#define False 0
#define True 1
typedef int KeyType;
typedef struct {
char name[20];
KeyType key;
int otherterm;
} ElemType;
typedef struct bnode {
ElemType data;
struct bnode* lchild, * rchild;
} BiTree;
BiTree* f = Null, * p = Null, * root = Null; /* f,p 为BiTree 类型的全局变量*/
BiTree* InsertBst(BiTree* tr, BiTree* s) {
/* 将新结点s插入到由tr所指的二叉搜索树中*/
BiTree* f, * p;
p = tr;
while (p != Null) {
f = p;
if (s->data.key == p->data.key) return tr;
if (s->data.key < p->data.key) p = p->lchild;
else p = p->rchild;
}
if (tr == Null) return(s);
if (s->data.key < f->data.key) f->lchild = s;
else f->rchild = s;
return(tr);
}
BiTree* creatord() { /* 建立二叉搜索树*/
BiTree* tr, * s;
int x;
char myname[20];
tr = Null;
printf("请输入数据记录的关键字值[值为-1时结束输入！]: ");
scanf("%d", &x);
while (x != -1) {
printf("输入该记录的名称: ");
scanf("%s", &myname[0]);
s = (BiTree*)malloc(sizeof(BiTree));
s->data.key = x;
strcpy(s->data.name, myname);
s->data.otherterm = 0;
s->lchild = Null;
s->rchild = Null;
tr = InsertBst(tr, s);
printf("请输入下一个数据记录的关键字值[值为-1时结束输入！]: ");
scanf("%d", &x);
}
return(tr);
}
BiTree* SearchBST(BiTree * T, KeyType key) { //二叉搜索树递归查找
if (T == NULL) return Null; // 查找失败
else if (key == T->data.key) return T; //查找成功
else if (key < T->data.key)
return SearchBST(T->lchild, key); //查找左子树
else return SearchBST(T->rchild, key);//查找右子树
}
BiTree * SearchBSTWithoutRecursion(BiTree * T, KeyType key) {//二叉搜索树非递归查找
p = T;
while (p) {
if (key == p->data.key) return p; //查找成功
if (key < p->data.key) p = p->lchild; //查找左子树
else p = p->rchild; //查找右子树
}
return NULL; //查找失败
}
int ModiSearchBST(BiTree * T, KeyType key) { //用于插入的查找
p = T;
while (p) {
if (key == p->data.key) return 1;
else if (key < p->data.key) {
f = p; p = p->lchild;
}
else {
f = p; p = p->rchild;
}
}
return 0;
}
int InsertBST(BiTree * T, ElemType e) {//二叉搜索树的插入算法
BiTree* s;
if (!ModiSearchBST(T, e.key)) {
printf("结点不存在，插入新结点!\n");
s = (BiTree*)malloc(sizeof(BiTree));
s->data = e;
s->lchild = NULL; s->rchild = NULL;
if (!f) T = s;
else if (e.key < f->data.key) f->lchild = s;
else f->rchild = s;
return 1;
}
printf("结点存在!\n");
return 0;
}
void bst_delete(BiTree * T, KeyType key) {//二叉搜索树的删除算法
BiTree* parent, * p, * q, * child;
parent = NULL; p = T;
while (p) {
if (p->data.key == key) break;
parent = p;
p = (key < p->data.key) ? p->lchild : p->rchild;
}
if (!p) return;
q = p;
if (q->lchild && q->rchild)
for (parent = q, p = q->lchild; p->rchild; parent = p, p = p->rchild);
child = (p->lchild) ? p->lchild : p->rchild;
if (!parent) T = child;
else {
if (p == parent->lchild) parent->lchild = child;
else parent->rchild = child;
if (p != q) q->data.key = p->data.key;
}
free(p);
}
void InOrder(BiTree * tr) { /* 中序遍历二叉树*/
if (tr != Null) {
InOrder(tr->lchild);
printf("%-4d;", tr->data.key);
printf("%-10s;", tr->data.name);
printf("%-4d\n", tr->data.otherterm);
InOrder(tr->rchild);
}
}/* InOrder */
void DestOrder(BiTree* tr) { /*从右子树开始遍历二叉排序树*/
if (tr != NULL) {
DestOrder(tr->rchild);
printf("%4d", tr->data.key);
DestOrder(tr->lchild);
}
}
void main() {
int key;
ElemType e;
char cmd;
do {
do {
system("cls");
printf("\n\tc,C......创建二叉搜索树");
printf("\n\ti,I .....中序遍历结果");
printf("\n\td,D......查找关键字");
printf("\n\ts,S......关键字插入结点");
printf("\n\ts,B......删除结点的关键字");
printf("\n\ts,E......数据递减输出结果");
printf("\n\tq,Q......退出\n\t请选择:");
cmd = getchar();
} while ((toupper(cmd) != 'D') && (toupper(cmd) != 'Q') && (toupper(cmd) != 'I') && (toupper(cmd) != 'C') && (toupper(cmd) != 'S'));
switch (cmd) {
case 'c':
case 'C':
root = creatord();
break;
case 'i':
case 'I':
InOrder(root);
_getch();
break;
case 'd':
case 'D':
printf("输入要查找的关键字");
scanf("%d", &key);
printf("输出二叉搜索树递归查找的结果：\n");
p = SearchBST(root, key);
if (p)
printf("查找成功!\n");
else
printf("查找失败!\n");
printf("输出二叉搜索树非递归查找的结果：\n");
p = SearchBSTWithoutRecursion(root, key);
if (p)
printf("查找成功!\n");
else
printf("查找失败!\n");
_getch();
break;
case 's':
case 'S':
printf("输入关键字插入的节点");
scanf("%d", &e.key);
printf("输入该记录的名称: ");
scanf("%s", e.name);
e.otherterm = 0;
InsertBST(root, e);
_getch();
break;
case 'b':
case 'B':
printf("输入删除结点的关键字");
scanf("%d", &key);
bst_delete(root, key);
_getch();
break;
case 'e':
case 'E':
DestOrder(root);
_getch();
break;
}
} while ((cmd != 'q') && (cmd != 'Q'));
system("pause");
}
二、实验数据
| 学号 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 成绩 | 90 | 80 | 85 | 95 | 100 |
三、运行截图
三、思考题
思考题
如何在“查找算法程序”中针对查找成功的关键字统计并输出关键字的比较次数和数据移动次数的总和？
答：将原程序中的折半查找函数改为
int Search_Bin(SSTable ST,KeyType key) //折半查找
{
int low=1,high=ST.length, mid; //下界从开始
int m;
while(low<=high)//查找范围非空时才能进行查找
{
mid=(low+high)/2; //上下界之和整除以
if(key==ST.elem[mid].key)
{
return mid; //查找成功，返回找到记录的下标
m=m+1；
}
else if(key<ST.elem[mid].key)
{
high=mid-1; //给定值小，在左侧，上界改为mid-1
m=m+1；
}
else
{
low=mid+1; //给定值大，在右侧，下界改为mid+1
m=m+1；
}
}
return 0; //low>high查找范围为空，查找失败，返回
return m;
}
在主函数中定义int m; 并且在输出时输出m即是关键字的比较次数。
在直接插入程序中int k；并改成以下程序
void InsertSort(SSTable &ST)//直接插入排序
{
int i,j;
int k;
for(i=2;i<=ST.length;i++)
{
ST.elem[0]=ST.elem[i]; //将待排序记录存入监视哨
j=i-1; //j指向有序序列的最后一个元素
while(ST.elem[0].key<ST.elem[j].key)
{
ST.elem[j+1]=ST.elem[j]; //记录后移
j--;
k=k+1;
}
ST.elem[j+1]=ST.elem[0]; // 插入第i个元素至恰当位置
return k;
}
}
在输出时输出k，即数据移动次数。
如何在“二叉搜索树查找算法程序”中输出按层次遍历的结果？
答：
void LevelOrder（BiTree *bt）
｛
BiTree *queue [MAXNODE］；
int front， rear;
if （bt = NULL） return；
front=-1
rear=0；
queue［rear］=bt；
while（front！=rear） front++;
Visit (queue[front]->data);
if（queue［ front］->lchild！=NULL） rear++;
queue［rear］= queue［front］->lchild；
if（queue front］->rchild！=NULL） rear++;
queue［ rear］= queue［ front］->rchild；
}
如何修改“一卡通程序”，增加一选项：显示未激活卡片的信息清单？
答：在初始页面中加入
printf("\n\t| 8.显示未激活卡片的清单 |");
写一个新函数：
judge(SqList &L, long &cardnumber);
{
int i;
for(i=0;i<L.size; i++)
{
if(L.list[i].cflag==0)
{
printf("\n\t卡号：%-10d 最后一笔消费金额：%7.2f 当前余额：%7.2f",L.list[num].cno,L.list[num].cmoney,L.list[num].cbalance);
}
}
}
四、心得体会
通过本次实验了解了线性表的各种功能及应用。增长了这种算法相关程序的编写。
