Turbo C程序开发环境简介
Turbo C是一个集程序编辑、编译、连接、调试为一体的C语言程序开发软件，具有速度快、效率高、功能强等特点，使用非常方便，C语言程序员可在Turbo C环境下进行全屏幕编辑，利用窗口功能进行编译、连接、调试、运行、环境设置等工作。
要求的配置
Turbo C 可以在IBM PC在系列机上运行（包括XT、AT、PS/2、286、386等及其兼容机），要求2.0或更高版本的DOS以及至少448KB的 RAM，监视器应为80系列。
2、安装
Turbo C系统有一安装程序INISTALL，其运行过程如下：
将标签为INSTALLATION DISK 的软盘插入A盘驱动器：
键入A,<br>
键入INSTALL <br>
这时只要遵循INSTALL显示在屏幕上的指示进行操作即可。INSTALL运行以后，就可使用Turbo C了。
3、使用
（1）、进入 Turbo C
如果使用INSTALL安装程序安装好了Turbo C,那么Turbo C以存在TC主目录下，可以用：
CD/TC <br> 或 CD TC <br>
进入该目录。然后在DOS命令行上键入“TC”并按回车键。这时就进入Turbo C，屏幕上将显示出如下的Turbo C主菜单窗口。
File Edit Run Complie Project Options Debug Break/Watch
如果不是在TC主目录内调用Turbo C，而是在另一个目录下想使用Turbo C，则应该指出目录路径，在DOS 3。0以上版本中，可以在命令行中使用包括目录路径的文件全名。如：用户希望将文件存于\USER目录后，则在进入USER目录后在命令行上输入\CD\TC，即可进入TC目录并调用Turbo C，用户编辑的源文件将存在于USER下。
（2）、工作目录工作目录指用户文件所在的目录。用户进入TC目录后，可以在这个目录下再建立一个用户专用的子目录。用户可以在此目录下进入文件的编辑工作，编译生成的目标文件也存放在此子目录中。这个工作目录可由用户自己建立，再由Change dir命令来告诉Turbo C你所选定的工作目录，方法见下述。
前以述及，在进入Turbo C后，屏幕上显示出一个Turbo C主菜单窗口。这时可以用F10键和光标移动键来从主菜单中选择所需的功能。步骤如下：先按下F10键，可看到屏幕上部的某一位置会出现亮块，如果亮块不在FILE处，表示准备选择,FILE”类 操作，即文件操作，也可不用F10键，而直接按ALT键和”f”键（同时），使亮块位于“FILE”处。亮块移动到“FILE”处后，按以下回车键，在“FILE”下方会出现一个子窗口如下图。
File edit run compile project options debug break/watch
Load F3
Pick ALT-F3
New
Save F2
Write to
Directory
Change dir
Os shell
Quit ALT-X
子窗口也有一个亮块，可以用“↑”、“↓”键，将此亮块移动到Change dir 处，或者直接按下“C”键，来选择change dir操作;输入键“↙”后，将会出现一目录提示框，提示用户输入所选择的目录名，用户输入后，再按下“↙”键即可。
如：屏幕显示输入提示：
newdirectory
C:\tc
用户输入“\usr”。
Newdirectory
C:\tc\usr
如果当前不存在此目录，则显示错误信息，可再次输入合法目录名。
（3）、建立工作环境即告诉TC:包括文件和库文件在什么地方：输出文件存在于何出。可用主菜单上“option项”来进行。步骤如下：
File edit run complie project option debug break/watch
在“option”位置上以后，按回车键。此时在位置下面出现一个子窗口，如下：
File edit run compile project options debug break/watch
Compiler
Linker
Environment
Directores
Arguments
Save options
Retrieve options
用光标移动健将亮条移动到“Directories”处，按回车键后，又将出现一个子窗口，如下图：
Include directories:c:\Turbo C\include
Licrary directories:c:\Turbo C\lib
Output directory,
Turbo C directory:
Pick file name,
Current pick file:
将亮条移至“include directories”出并按回车键，然后输入包括文件所在的盘符和路径。如输入：
c:\Turbo C\include ; c;\Turbo C\include \sys
表示：包含文件放在C盘上的\Turbo C\include 子目录和\Turbo C \include \sys子目录中。
包含文件的所在目录输入后，再将亮条移到“library directories”处，按回车键。输入库函数的盘符和目录名
c:\Turbo C \lib
这就告诉Turbo C:库函数的目录
（4）、编辑源文件在主菜单状态下，将亮块移到左上角“FILE”处，按回车，选择“load”出现：
load file name
用户可在输入要编辑的文件名，按回车即可。
如果记不清所编辑的源文件名，想看一下当前目录中有哪些源文件，可以在子窗口出现上述“*.C”时直接按回车键。Turbo C就回显示出当前目录下的所有后缀为“.C”的文件名，利用光标键时将亮度条移到需要编辑的文件名处，按回车键，该输入文件内容即显示在屏幕上，供用户编辑、修改。
如果用户用“load”输入的文件名是已存在的文件，则这时屏幕上将显示出文件内容，可供修改；否则屏幕上是一片空白，表示文件无内容（是新文件），用户可以从键盘输入文件内容。在编辑过程中除用到个字符键外还可以用到“Ins”键和“Del”键，“Ins”键是一个切换键，用来控制工作状态是否处于“插入状态”。按下,Ins”键后，可以看到在屏幕编辑窗口的上方状态行上有一个英文单词“INSERT”，这时从键盘输入的字符（包括控制字符，如“回车”）会插入到屏幕当前光标处，光标后的字符会自动顺序后移。如果再按一下“Ins”键，则取消插入状态，状态行上的“INSERT”单词消失。此后键入的字符将覆盖（而不是插入）光标处的字符，Turbo C设置的初始状态是“插入状态”，第一次按“Ins”键改成“覆盖状态”，再按“Ins”键，则又改成“插入状态”，如此反复切换。“Del”键是删除光标所在的字符。“Ctrl”键和“Y”键同时按下可删除光标所在的一行，“Ctrl”键盘和“N”键盘可用来插入一行。
编辑完成后，可从“File”菜单中选择“save”命令（即将亮条移至Save处后，再按回车键）将文件存盘，也可直接按下F2键，将文件存盘。
（5）、编译、连接加工程序时，先编译源代码，生成目标文件（扩展名为。OBJ），然后将目标文件进行连接生成可执行文件（扩展名为。EXE）。
对单文件程序的编译、连接的方法是在将文件存盘后，按F10键，将亮条移至Compile处按回车键，也可直接按Alt-C即可产生一个子窗口如下图：
File edit run compile project options debug break/watch
表示编译后生成 a.obj 文件，连接后生成 a.exe 文件，源文件名设定为 a.c 将亮条移至Make EXE File处（也可以直接按住F9键），则TC将对文件进行编译、链结并生成运行文件。
若文件有错，则在屏幕底部的“Message”窗口显示出错及警告信息。这时可进行修改。该完后在重复进行编译、链结。
另外，TC的最显著特点之一是能进行分别编译，可以把一个长的文件分别编辑在多个文件中，分别编译。Turbo C提供了一个工具，可直接将这些文件编译连接后生成一个完整的运行程序，而不必由用户显示在分别编译连接。这个工具就是Project菜单项，使用步骤如下：
假设有两个文件组成一个程序，首先要生成两个源文件（如File1.c和File2.c）。
构造Project文件，在编辑状态下，编辑一个后缀名为PRJ的文件（文件名可由用户选择，如：MYPROJECT.PRJ）此文件内容如下,
file1
file2
后缀.C可要可不要，而且File1、File2顺序无所谓。当File1.c，File2.c不在一个目录中时，可在project文件MYPROJECT.PRJ中给出各自的路径，例如文件内容可为：
\Turbo C\USER\File1
\ Turbo C\File2
在主菜单窗口中选择project功能项，即将亮条移至project处回车（也可按Alt+P键得到），此时得到如下子窗口。
File edit run compile project options debug break/watch
Project name
Break make on Errors
Auto depentlents off
Clear project
Remove messages
将亮条移到“Project name”处，按回车键输入后，输入project文件名（如MYPROG.PRJ）并回车。然后按F9键即产生相应的可执行文件。此时运行文件名及为用户给出的project文件名（如MYPROG.EXE），运行时可用下述的RUN命令，也可在操作命令状态下直接输入运行文件名（如MYPROG）。
停止编辑的方式。如果同时编辑的几个程序中有错，就须停止编译，由用户进行修改。用户可以指定两种方式停止编译。
A、用户希望同时编译的几个文件中同时出现一个错误时，就停止编译，可用如下方法：将Project菜单中的亮条移到“Break Make On”处，回车后可出现一个子窗口，如下图：
Warnings
Errors
Fatal errors
Link
将亮条移至Errors或Warnings处，回车后，在Break Make On 右边及出现此选项，如图：
Break Make On Errors
这时，当编译的几个文件只要出现一个错误时，就立即停止编辑，亮条停在出错处，指示用户进行修改。
望所有文件的所有错误都找出以后，在修改错误，可用以下方法：
在”break make on”子窗口中，将亮条移至fatal errors或link处，此时:break make on右边出现的是fatal errors 或link。这样，在编译出现错误后，才停止编译，用户这时在修改源文件。
（6）、运行编译链结完成一个文件后，可利用主菜单的“run”命令或直接使用ctrl +F9来运行程序。其实当用户认为自己的源程序不会有编译，链结错误时，在源程序编译完成后，可以直接用“run”命令或直接按crtl+F9键，这时它会一次完成编译链结到运行的全过程。
程序运行后，仍回到tc屏，这时若想看运行结果，可以用“run”菜单的“user screen”命令，也可直接按alt+F5键，转到用户屏。
File edit run compile project options debug break/watch
Run ctrl+F9
Program reset ctrl+f2
Go to cursor f4
Trace into f7
Step over f8
User screen alt+F5
看完后，按任意键回到TC屏。
关于Turbo C的更详细的信息，请参阅Turbo C手册，或使用F1帮助联机系统。
实验一 线性表一、实验目的
1、掌握用C语言上机调试线性表的基本方法。
2、掌握线性表基本操作，插入、删除、查找，以及线性表合并等运算在顺序存储结构和链接存储结构上的运算。
二、实验内容题目一 线性表基本操作的实现
[问题描述]
当我们要在线性表的顺序存储结构上的第i个位置上插入一个元素时，必须先将线性表中第i个元素之后的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到该位置。若欲删除第i个元素时，也必须把第i元素之后的所以元素前移一个位置。
[基本要求]
要求生成线性表时，可以键盘输入读取元素，用顺序存储结构和链式存储结构实现存储。
[实现提示]
要实现基本操作可用已实现的基本操作，也可设计简单的算法实现
[算法实现]
typedef null 0;
typedef int datatype;
#define maxsize 1024;
typedef struct
{ datatype data[maxsize]; /*定义线性表是向量，第一结点是data[0]*/
int last;
}sequenlist;
/*插入函数*/
int insert(L,x,i) /*将新结点x插入到顺序表l第i个位置
sequenlist *L; /*l是sequenlist类型的指针变量
int i;
{ int j;
if （（*l）.last==maxsize-1）
{ printif(“overflow”);
return null;}
else
if((i<1)||(i>(*l).last+1)
{ printf(“error”);
return null;}
else
{ for(j=（*l）.last;j>=i-1;j--)
(*l).data[j+1](*l).data[j]; /*结点后移
(*l).data[i-1]=x; /*?插入x
(*l).last+1; } /*表长加一
return (1);
}
/*删除运算
int delete(L,i)/*删除第i个结点
sequenlist *L;
int i;
{ int j;
if((i<1)||(i>(*L).last+1)
{ printf(“error”);
return null; }
else
{ for (j=i;j<=(*L).last;j++)
(*l).data[j-1]=(*L).data[j];
(*L).last--; }
return (1);
}
/*生成线性表
void ceatlist()
{ sequentlist *L;
int n,i,j;
printf(“请输入n个数据\n”)；
scanf(“%d”,&n);
for(i=0,i<n,i+);
{ printf(“data[%d]=”,i);
scanf(“%d”&(*L).&data[i]);
}
(*L).last=n-1;
printf(“”\n”);
}
/*输出线性表
printout(L)
sequenlist *L;
{ int i;
for(i=0;i<(*L).last;i++)
{ printf(“data[%d]=”,i);
printf(“%d”,(*L).data[i]);
}
}
/*主程序开始
main()
{ sequenlist *L;
char cmd’
int i,t;
clscr();
printf(“i I ： 插入元素\n”);
printf(“d D ： 删除元素\n”);
printf(“q Q, 退出元素\n”);
do
{ do
{ do{cmd=getchar();
}while((cmd!=’d’)||(cmd!=’D’)||(cmd!=’q’)||(cmd!=’Q’)||(cmd!=’i’)||(cmd!=I));
switch(cmd)
{ case ‘i’,’I’,scanf(&i);
insert(L,i);
printout(L);
break;
case ‘d’,’D’,scanf(&i);
delete(L,i);
printout(L);
break;
}
}while((cmd!=’q’||(cmd!=’D’));
}
题目二 约瑟夫问题求解
[问题描述]
设有n个人围坐一圈，现从某个人开始报数，数到m的人出列，接着从出列的下一个人开始重新报数，数到的M人又出列，如此下去，直到所有的人出列为止，试设计确定他们的出列次序序列的程序。
[基本要求]
选择单向循环链表作为存储结构模拟整个过程，并依次输出出列的各人的编号。
[实现提示]
程序运行之后，首先要求用户指定初始报数的上限值，可以n<=30，此题中循环链表可不设头结点，而且必须注意空表和非空表的界限。如：n=8，m=4时，若从第一个人开始，设每个人的编号依次1、2、3、4…开始报数，则得到的出列次序为4 8 5 2 1 3 7 6。
[程序实现]：
struct node
{ int num;
struct node *next;
} linklist;
/*建立链表
linklist *creat(head,n)/使n个人围成一圈,并给每个人标志号数
linklist *head
int n;
{ linklist *s,*p;
int i;
s=malloc(sizeof(linklist));
head=s;
s->num=1;
p=s;
for(i=2;i<=n;i++);
{ s=malloc(sizeof(linklist));
s->num=i;
p->next=s;
p=s;
}
p->next=head;
return head;
}
linklist *select(head,m)
linklist *head;
int m;
{ linklist *p,*q;
int i,t;
p=head;t=1;
p=q; /*q为p的前驱指针
do{
p=q->next; /*指向当前报数的人
t=t+1;
if(t%m==0)
{
printf(“%4d”,p->num);
q->next=p->next;
free(p);
p=q;
}
else
p=q;
} while(p==q);
head=p;
}
/*主程序
main()
{ int n,m;
linklist *head;
scanf(&n);
scanf(&m);
creat(head,n);
select(head,m);
printf(“the last one:is%d”,head-num);
}
题目三 一元多项式简单计算
[问题描述]
设计一个一元多项式的简单计算器
[基本要求]
一元多项式简单计算器的基本功能为：
输入并建立多项式输出多项式两个多项式相加减，相乘除，建立并输出多项式
[实现提示]
可选择带头结点的单向循环链表或单链表存储多项式，头结点可以存储多项式的参数如项数等。
[程序实现]
这里利用单链表作为存储多项式的结构：单链表定义如下,#define null 0
#define true 1
#define false 0
struct mulpoly
{ int coef ;/*系数
int exp; /*指数
struct mulpoly next; }
假设输入一组多项式的系数和指数，以输入实数0为结束标记，这里建立多项式时，总是按指数从大到小排列。
/*产生多项式链表，设头指针为head
struct mulpoly creatpoly()
{ struct mulpoly *head,*r,*s;
int m,n;
head =(struct mulpoly *)malloc(sizeof(struct mulpoly));
scanf(“%d,%d”&n,&m)；
r=head;
while(n) /*n不等于0时建立多项式链表
{ s=(struct mulpoly )malloc(sizeof(struct mulpoly));
/*建立一个新结点
s->coef=n;
s->exp=m;
r->next=s; /*把*S链接到*R后面
r=s;
printf(“input coef and exp:\n”);
scanf(“%d,%d”,&n,&m);
}
r->next=null;
head=head->next;
return (head);
}
/*a+b实现多项式相加：
/*两多项式相加运算ha hb 分别是A、B链表的头指针,相加后存放到多项式C，头指针为hc
struct mulpoly polyadd(ha,hb)
struct mulpoly *ha,*hb;
{ struct mulpoly *hc,*p,*q,*s,*r;
int x;
p=ha;
q=hb;
hc=(struct mulpoly *)malloc(sizeof(struct *mulpoly));
s=hc;
while((p!=null)&&(q!=null))
{if(p->ext==q->ext) /*两个结点指数相等
{ x=p->coef+q->coef; /*系数相加
if(x!=0)
{r=(struct mulpoly *)malloc(sizeof(struct *mulpoly));
r->exp=p->exp;
r->coef=x;
s->next=r;
s=r; }
p=p->next;
q=q->next;
}
else/*两结点指数不相等
if(p->next<q->next)
{ r=(struct mulpoly *)malloc(sizeof(struct *mulpoly));
r->exp=p->exp;
r->coef=p->coef;
s->next=r;
s=r;
p=p->next;
}
else /* p->next>q->next时
{ r=(struct mulpoly *)malloc(sizeof(struct *mulpoly));
r->exp=q->exp;
r->coef=q->coef;
s->next=r;
s=r;
q=q->next;
}
}
while(p) /* p!=NULL复制A的剩余部分
{ r=(struct mulpoly *)malloc(sizeof(struct *mulpoly));
r->exp=p->exp;
r->coef=p->coef;
s->next=r;
s=r;
p=p->next;
}
while(q) /* q!=NULL复制B的剩余部分
{ r=(struct mulpoly *)malloc(sizeof(struct *mulpoly));
r->exp=q->exp;
r->coef=q->coef;
s->next=r;
s=r;
q=q->next;
}
s->next=null; /*链成单链表
r=hc;
hc=hc->next;
free ( r );
return(hc);
}
相减运算，实际上也是多项式相加的运算，无非是各项的系数符号不等而已。而多项式的乘法运算可说明如下。
/*多项式相乘
struct mulpoly * polymulti(f,g)
struct mulpoly *f,*g;
{ mulpoly *fp,*gp,*q,*h;
int maxp,p,r,x;
extern reverse(mulpoly *p);
maxp=f->exp+q->exp;
h=(struct mulpoly *)malloc(sizeof(struct *mulpoly));
hp=h;
reverse(g);
for(r=maxp;r>=0;r--)
{ x=0;fp=f;gp=g;
while((fq!=null)&&(gp!=null))
{ p=fp->exp=gp->exp;
if(p>r)
fp=fp->next;
else
if(p<r)
gp=gp->next;
else
{ x+=fp->coef*gp->coef;
fp=fp->next;
gp=gp->next; }
} /* end of while
if (abs(x)>le-6)
{ p=(struct mulpoly *)malloc(sizeof(struct *mulpoly));
q->exp=r;
q->coef=x;
q(next=null;
hp->next=q;
hp=q;
}
} /* end of for
hp=h;
h=h->next;
free(hp);
return h;
}
其中的reverse函数说明如下
reverse(q)
mulpoly *q;
{ mulpoly *p1,*p2;
if(q!=null)
{ p1=q->next;
q->next=null;
while(p1!=null)
{ p2=p1->next;
p1->next=q;
q=p1;
p1=p2;
}
}
多项式的输出的输出，实际上就是单链表的输出，只是该单链表的数据域含有系数和指示两部分而已。
/*多项式的输出
ployout(head)
mulpoly *head;
{ mulploy *p,*q ;
p=head->next;
while(p!=NULL)
{ printf(“%d,%d”,p->coef,p->exp);
p=p->next;
}
}
整个实现的主程序如下：
void main()
{ mulpoly *ha,*hb,*hc,*p,*q,*h;
ha=creatpoly();
polyout(ha);
hb=creatpoly();
polyout(hb);
hc=polyadd(ha,hb)’;
polyout(hc);
h=polymulti(ha,hb);
polyout(hc);
}
实验二 栈和队列一,实验目的
1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际背景下灵活运用。
握栈和队列的特点，即先进后出与先进先出的原则。
3、栈和队列的基本运算，如入栈和出栈、入队与出队等运算在顺序存储结构和链式存储结构上的实现。
二、实验内容题目一 表达式求值算法
[问题描述]
表达式求值是程序设计语言编译中的一个基本算法。他的实现是栈应用的一个典型例子。这里采用较为流行的“算符优先法”来实现对表达式的求值。要把一个表达式翻译成正确求值的一个机器指令序列，或者是直接对表达式求值，首先要能够正确解释表达式。那么就要了解算术四则运算的基本规则：
1）先乘除，后加减；
2）从左算到右；
4）先括号内，后括号外。
例如表达式：4+2*3-10/5的计算顺序为：
4+2*3–10/5=4+6–10/5=10–10/5=10–2=8
算符优先法就是根据这个运算优先关系的规则来实现对表达式的编译或解释执行的。
[基本要求]
要求能根据算符优先法则对所输入的四则运算表达进行求值。
[实现提示]
任何表达式都由操作数、运算符、定界符组成，我们把运算符和定界符统称为算符。它们构成的集合命名为OP，根据运算法则在每一步中，任意两个算符优先级关系可以由下表来描述:
其中， Q1<Q2 Q1的优先级低于Q2
Q1=Q2 Q1的优先级等于Q2
Q1>Q2 Q1的优先级高于Q2
“#”号表示表达式的开始与结束。
该表可以采用二维表表示，由先后两算符的序号做下标定位两者的优先级，如“*”的序号为2，“+”的序号为1，则“*”与“+”相遇OP[2，1]得到“>”所以“*”的优先级高。
[程序实现]
算法思想为了实现算符优先算法，可以使用两个工作栈，一个是操作数栈OPDS，另一个是运算符栈OPS，分别存放操作数与算符。首先将标志“#”进运算符栈OPS的底，按照栈后进先出的原则进行：
遇到操作数，进操作数栈，计算机继续扫描下一符号；
遇到运算符时，需要将此算符的优先级与OPS栈顶算符优先级比较。
若优先级比站顶元素高，则进OPS栈，继续扫描下一符号；
若优先级比站顶元素低，则运算符优先级比站顶元素OPS栈顶元素退栈形成一个操作码Q；同时，操作数栈OPDS两次退栈，形成两个操作数a,b.计算机对操作数与操作码完成一次运算操作，即aQb.其运算结果存放在操作数OPDS栈，作为一次运算的中间结果进OPDS栈。
若与栈OPS栈顶元素优先级相等，则栈顶元素退栈。当遇到栈顶元素是“#”时，表示整个运算结果，否则，继续扫描下一个符号。
程序实现
/* 初始化*/
#define FALSE 0
#define TRUE 1
#define MAX 10
#include <stdio.h>
#include <stdlib.h>
void push_opds(); /*push opds stack.*/
float pop_opds(); /*pop opds stack.*/
void push_ops(); /*push ops stack.*/
float pop_ops(); /*pop ops stack.*/
char relation(); /*>,<,=*/
float operate(); /*+,-,*,/*/
float opds[MAX]; /*operand's stack */
int ops[MAX]; /*operator's stack */
int topd=0; /*opds's top*/
int top=0; /*opd's top*/
char symb;
/*主函数，表达式求值
void main()
{
char sy;
char ch;
float a,b;
printf("\n Please input expression(# end):\n");
push_ops('#');
symb=getchar();
while ((symb!='#')||((char)(ops[top])!='#'))
{
if((symb!='+')&&(symb!='-')&&(symb!='*')&&(symb!='/')&&(symb!='(')&&(symb!=')')&&(symb!='#')&&(symb!=' '))
{ /*不是算符，则是操作数进OPDS栈
push_opds(symb);
symb=getchar();
}
else
{ /*是算符，先比较优先级，在分情况处理
ch=relation((char)(ops[top]),symb);
switch(ch)
{
case '<':
push_ops(symb);
symb=getchar();
break;
case '=':
sy=pop_ops();
symb=getchar();
break;
case '>':
sy=pop_ops();
b=pop_opds();
a=pop_opds();
topd=topd+1; /*push_opds stack*/
opds[topd]=operate(a,sy,b);
break;
case ' ':
printf("error\n");
break;
}
}
}
printf("\nThe result=%1.2f\n",opds[topd]);
getch();
}
/*操作数压栈
void push_opds(ch)
char ch;
{
int ch_i;
if (topd==MAX-1)
printf("the opds stack is overflow.\n");
else
{
ch_i=ch-'0'; /*将字符转化为“值”：“3”转为3
topd++;
opds[topd]=ch_i;
}
}
/*操作数弹栈
float pop_opds()
{
topd=topd-1;
return(opds[topd+1]);
}
/*操作符压栈
void push_ops(ch)
char ch;
{ if (top==MAX-1)
printf("the ops stack is overflow.\n");
else
{
top++;
ops[top]=(int)(ch);
}
}
/*操作符弹栈
float pop_ops()
{
top=top-1;
return((char)(ops[top+1]));
}
/*比较两个算符sym1,sym2的优先关系
char relation(sym1,sym2)
char sym1,sym2;
{
int i;
char chl[2];
int ind[2];
char re[7][7]={ {'>','>','<','<','<','>','>'},
{'>','>','<','<','<','>','>'},
{'>','>','>','>','<','>','>'},
{'>','>','>','>','<','>','>'},
{'<','<','<','<','<','=',' '},
{'>','>','>','>',' ','>','>'},
{'<','<','<','<','<',' ','='}};
chl[0]=sym1;
chl[1]=sym2;
for (i=0;i<=1;i++)
{
switch(chl[i])
{
case '+',ind[i]=0;break;
case '-',ind[i]=1;break;
case '*',ind[i]=2;break;
case '/',ind[i]=3;break;
case '(',ind[i]=4;break;
case ')',ind[i]=5;break;
case '#',ind[i]=6;break;
default:printf("error\n");return('0');
}
}
return(re[ind[0]][ind[1]]); /*取优先符>、=、<
}
/*执行操作运算
float operate(a,sym,b)
float a,b;
char sym;
{
float re;
switch(sym)
{
case '+':re=a+b;break;
case '-':re=a-b;break;
case '*':re=a*b;break;
case '/':re=a/b;break;
default:printf("error\n");return(0);
}
return(re);
}
题目二 迷宫路径问题
[问题描述]
迷宫实验是取自心理学的一个古典实验。在该实验中，把一只老鼠从一个无顶大盒子的门放入，在盒中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有一个出口，在出口处放一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验，一直到老鼠从入口到出口，而不走错一步。老鼠经多次实验终于得到他学习走通迷宫的路线。设计一个计算机程序对任意设定的迷宫，求出一条入口到出口的通路，或得出没有通路的结论。
[基本要求]
要求程序输出：
（1）、一条通路的二元组（i,j）数据序列，（i,j）表示同路上某一点的坐标。
（2）、用一种标志（如数字8）在二维数组中标出该条通路，并在屏幕上输出二维数组。
[实现提示]
可以利用一个二维数组maze[i][j]表示迷宫，其中1≤i≤m,1≤j≤n。数组元素值为1表示该位置是墙壁，不能通行；元素值为0表示该位置是通路。假定从maze[1][1]出发，出口位于maze[m][n],移动方向可以是8个方向（东，东南，南，西南，西，西北，北和东北）。一个构造的迷宫如下页图：
[算法实现]
设计思想当迷宫采用二维数组表示时，老鼠在迷宫中任一时刻的位置可由数组的行列序号i,j来表示。而从[i][j]位置出发，可能的行进方向见下图1。如果[i][j]周围位置均为0值，则老鼠可以选择这8个维之中的任一个作为它的下一个位置。将这八个方向分别记作：E（东）、SE（东南）、S（南）、SW（西南）、W（西）、NW（西北）、N（北）和NE（东北）。但是并非每一个位置都有8个相邻位置。如果[i][j]位于边界上，即i=1,或i=m,或j=n,则相邻位置可能是5个或3个。为了避免检查边界条件，将数组四周围用值为1的边框包围起来，这样二维数组maze应该声明为maze[m+2][n+2]。
在迷宫中行进时，可能有多个行进方向可供选择，我们可以规定方向搜索的次序是从东（E）沿顺时针方向进行。为了简化问题，规定[i][j]的下一步位置坐标是[x][y]，并将这8个方向上的x和y坐标的增量预先放在一个结构数组move[8]中（见图2）。该数组的每个分量有两个域dx和dy。例如要向东走，只要在j值上加dy,就可以得到下一步位置的[x][y]的值为[i][j+dy]。于是搜索方向的变化只是要令方向值dir从0增加到7，便可以从move数组中得到从[i][j]点出发搜索到的每一个相邻点[x][y]。
x=i+move[dir].dx
y=j+move[dir].dy
为了防止重走原路，我们规定对已经走到过的位置，将原值0改为-1，这既可以区别该位置是否已经走到过，又可以与边界值1相区别。当整个搜索过程结束后，可以将所有的-1该回到0，从而恢复迷宫的原样。
这个计算机走迷宫的算法是：采取一步一步试探的方法。每一步都从东（E）开始，按顺时针方向对8个方向进行探测，如某个方向上的maze[x][y]=0,表示可以通行，则走一步；如maze[x][y]=1,表示此方向上不可通行，须换方向再试，直至8个方向都试过，maze[x][y]均为1，说明此步已无路可走，须退回一步，再上一步的下一个方向上重新探测。为此须设置一个栈，用来记录所走过的位置和方向（i,j,dir）。当退回一步时，就从栈中退回一个元素，以便在上一个位置的下一个方向上探测，如果有找到一个进行方向，这把但前位置核心的方向重新进栈，并走到新的位置。如果有探测到x=m,y=n,则已达到迷宫得出口，可以停止检测，输出存在栈中的路径；若在某一个位置的8个方向上都堵塞，则退回1步，继续探测，如果以退出到迷宫的入口（栈中无元素），则表示此迷宫无路径可通行。
（2）程序实现这里用到一个栈，栈的元素是一个结构。为了方便采用顺序栈。由于数组maze的每一个位置最多被访问一次，所以至多有m*n个元素放入栈中，因此m*n作为栈的容量大小是个安全的值，但也是一个保守的值。一般取m*n/2即可。
# define M2 12 /*M2*N2为实际使用迷宫数组的大小*/
# define N2 11
# define MAXLEN M2 /*栈的长度*/
# define True 1
# define False 0
# define,stdio.h”
int M=M2-w,N=N2-2; /*M*N为迷宫的大小*/
typedef struct /*定义栈元素的类型*/
{int x,y,dir;
}elemtype;
typedef struct /*定义顺序栈*/
{elemtype stack[MAXLEN];
int top;
}sqstktp;
/*定义方向位移数组对于存储坐标增量的方向位移数组move */
struct moved
{int dx,dy;
};
/*初始化迷宫*/
void inimaze(int maze[][N2])
{int i,j,num;
for(i;i<=M;i++)
{ for(j=1;i<=n;j++)
{ num=(800*(j+i)+1500)%327; /*根据M和N值产生迷宫
if((num<150)&&(i!=M||j!=N))
maze[i][j]=1;
else
maze[i][j]=0;
printf(maze[i][j]); /*显示迷宫
}
printf(“\n”);
}
printf(“\n”);
for(i=0,j=0;i<=<M+1;i++) /*设置迷宫的边界
maze[i][j]=1;
for(i=0,j=N+1;i<=M;i++)
maze[i][j]=1;
for(i=0,j=0;j<=N+1;j++)
maze[i][j]=1;
for(i=M+1,j=0;j<=N+1;)
maze[i][j]=1;
}
/*初始化方向位移数组*/
void inmove(struct moved move[])
/*依次为E,SE,S,SW,W,NW,N,NE*/
{ move[0].dx=0;move[0].dy=1;
move[1].dx=1;move[1].dy=1;
move[2].dx=1;move[2].dy=0;
move[3].dx=1;move[3].dy=-1;
move[4].dx=0;move[4].dy=-1;
move[5].dx=-1;move[5].dy=-1;
move[6].dx=-1;move[6].dy=0;
move[7].dx=-1;move[7].dy=1;
} /*inimove*/
/*初始化栈*/
void inistack(sqstktp *s)
{ s->top=-1;
}/*inistack*/
/*数据元素x入指针s所指的栈*/
int push(sqstktp *s,elemtype x)
{ if (s->top= =MAXLEN-1) /*栈满，返回False */
return(False);
else
{ s->stack[++s->top]=x; /*栈不满，执行入栈操作*/
return(Ture); }
} /*push*/
/*栈顶元素出栈*/
elemtype pop(sqstktp *s)
{ elemtype elem;
if (s->top<0) /*如果栈空，返回空值*/
{ elem.x =Null;
elem.y =Null;
elem.dir =Null;
return(elem); }
else
{ s->top- -;
return(s->stack[s->top+1]); /*返回栈顶元素*/
}
}/*pop*/
/*寻找迷宫中的一条通路*/
void path(int maze[ ][N2],struct moved move[],sqstktp s*)
{ int i,j,dir,x,y,f;
elemtype elem;
i=1;j=1;dir=0;
maze[1][1]=-1; /*设[1][1]为入口处*/
/*循环，直到入口处或出口处为止*/
do
{ x=i+move[dir].dx; /*求下一步可行的到达点的坐标*/
y=j+move[dir].dy;
if (maze[x][y]= =0)
{ elem.x=i;elem.y=j;elem.dir=dir;
f=push(s,elem); /*如果可行，将此点数据入栈*/
if (f= =False) /*如果入栈操作返回假，说明栈容量不够*/
printf(“栈长度太短\n”);
i=x;j=y;dir=0;maze[x][y]=-1; }
else
if (dir <7) /*如果当前方向不可行，就转到下一个方向*/
dir + +;
else
{ elem=pop(s); /*8个方向都不可行，就退回一步*/
if (elem.x!=Null)
{ i=elem.x;
j=elem.y;
dir=elem.dir+1; }
}
}while (!((s->top= =-1)&&(dir>=7)||(x= =M)&&(y= =N)&&(maze[x][y]==-1)));
/*如果是入口处，则迷宫无通路*/
if (s->top= =-1)
printf(“此迷宫无通路\n”);
else
{ elem.x=x;elem.y=y;elem.dir=dir; /*最后出口的坐标入栈*/
f=push(s,elem);
printf(“迷宫通路是：\n”);
i=0;
/*显示迷宫通道*/
while (i<=s->top)
{ printf(“%d,%d”,s->stack[i].x,s->stack[i].y;
if(i!=s->top)
printf(“-->”);
if((i+1)%4= =0)
printf(“\n”);
i++;
}
printf(“\n”);
}
} /*path*/
/*在迷宫中绘制出通路*/
void draw(int maze[][N2],sqstktp *s)
{ int i,j;
elemtype elem;
for(i=1;i<=M;i++) /*将迷宫中全部的-1值恢复为0值*/
for(j=1;j<=N;j++)
if (maze[i][j]= =-1)
maze [i][j]=0;
/*根据栈中元素的坐标，将通路的各个点的值改为8*/
while (s->top>-1)
{ elem=pop(s);
i=elem.x;j=elem.y;
maze[i][j]=8;
}
for(i=1;it=M;i++)
{ for(j=1;j<=N;j++)
printf(“%3d”,maze[i][j]); /*显示已标记通路的迷宫*/
printf(“\n”);
}
printf(“\n”);
} /*draw*/
/*寻找迷宫通路程序*/
void main( )
{ sqstktp *s;
int maze[M2][N2];
struct moved move[8];
inimaze(maze); /*初始化迷宫数组*/
s=(sqstktp )malloc(sizeof(sqstktp));
inistack(s); /*初始化栈*/
inimove(move); /*初始化方向位移数组*/
path(maze,move,s); /*绘制作出通路标记的迷宫*/
}/*main*/
题目三 迷宫最短路径问题
[问题描述]
在第2题给出的条件基础上，要求设计一个算法，寻找一条从迷宫入口到出口的最短路径。输出信息的要求同第2题。
[设计思想]
一般走迷宫的方法是只要找出一条通路即可，至于这条通路是怎样形成的，并没有关系。由于走迷宫的方法是采用试探法，因此第一步试探的方法非常重要，它决定了通路的可能走向。例如第一步向东走与向东南走，最终形成的通路一般是不一样的。本题是在一般走迷宫的方法上，更进一步要求找出一条最短的路径，而不论起始试探的方位为何。
算法的基本思想是：从迷宫的入口[1][1]出发，向四周搜索，记下所有一步能到达的坐标点p11,p12,……，p1k1(0≤k1≤3);然后依次从p11,……,p1k1出发向四周搜索，几下所有从入口点出发，经过两部可以到达的坐标点p21,……，p2k2(0≤K2≤5);依次进行下去，一直到达迷宫的出口处[m][n]。然后从出口出演搜索路径回溯直至入口点，这样就找到了从入口到出口的一条最短路径。
在本算法中，搜索[i][j]点周围8个方向的坐标点，以决定那些坐标点是可以到达的，方法同上机实习题2。这里只是需要解决搜索路径的保存问题。
在搜索过程中必须记下每一个可到达的坐标点，以便从这些点出发继续向四周搜索。由于先到达的点将作为新的起点先进新搜索，故须采用一个先进先出的队列来保存已到达的坐标点。对于每一个记录下来的坐标点，还需同时保存是从哪一个坐标点出发到达的（该坐标点肯定已在队列中了）。另外搜索结束后，还需从出口向入口回溯，以寻找一条通路，因此尽管采用队列形式，但每一个出发点并不真正离开队列（或者说并不真正从队列中将其删除），只是取其值作为搜索的出发点。这样我们采用一个结构数组queue[]来做该队列的存储空间。因为迷宫中的每一个点至多被访问一次，因此queue[]的容量最大为m*n。queue的每一个元素有三个域：x,y,pre。其中x和y分别记下每一个到达点的行、列坐标，pre则是一个静态链域，他保存到达该点的出发点在queue中的下标。该队列的头尾指针front和rear分别指向实际的队头和队尾元素。例如开始时，队列中只有一个元素，即入口点[1][1]，它的pre域值为0，因为不是从其它出发点到达[1][1]的。front和rear同时指向该元素。此后搜索时，均以front所指的元素作为搜索的出发点，当找到一个可到达点时，将该点的坐标及出发点的下标一起入队。而rear始终指向当前入队列的可到达点元素。假如front所指的点出发搜索完毕，则使front指向下一个新的出发点，继续搜索。一直到找到出口点，或者当前队列为空结束。前者表示成功找到通路，而后者则表示迷宫无通路。
在输出通路时，由于是从队列的队尾（出口）向队头（入口）回溯，得到的结果序列就是从出口到入口。为了保证输出通路是从入口到出口，需将队列中回溯得到的结果先入栈，然后再从栈中输出。
[算法实现]
#define M2 12 /*M2×N2为实际使用的迷宫数组的大小*/
#define N2 11
#define MAXLEN M2*N2/2 /*队列和栈的长度*/
#define Ture 1
#define False 0
#include,stido.h”
int M=M2-2,N=N2-2; /* M×N为迷宫大小*/
typedef struct /*定义栈元素的类型*/
{int x,y;
}elemtype;
typedef struct /*定义顺序栈*/
{elemtype stack[MAXLEN];
int top;
}sqstktp;
typedef struct /*定义队列元素的类型*/
{int x,y,pre;
}queeletp;
typedef struct /*定义顺序队列*/
{queeletp queue[MAXLEN];
int front,rear;
}queuetp;
struct moved /*定义方向位移数组元素的类型*/
{int dx;dy;
};
/*初始化迷宫*/
void inimaze(int maze[ ][N2])
{ int i,j,num;
for(i=1;i<=M;i++) /*根据M和N的值产生迷宫*/
{ for(j=1;j<=N;j++)
{ num=(800*(i+j)+1500) &327;
if (num<150 &&(i!=M ||j!=N))
maze[i][j]=1;
else
maze[i][j]=0;
printf(“%3d”,maze[i][j]); /*显示迷宫*/
}
printf(“\n”);
}
printf(“\n”);
for(i=0,j=0;i<=M+1;i++) /*设置迷宫的边界值*/
maze[i][j]=1;
for(i=0,j=N+1;i<=M+1;i++)
maze[i][j]=1;
for (i=0,j=0;j<=N+1;j++)
maze[i][j]=1;
for(i=M+1,j=0;j<=N+1;j++)
maze[i][j]=1;
} /*inimaze*/
/*初始化方向位移数组*/
void inimove(struct moved move[])
{ move[0].dx=0;move[0].dy=1; /*依次为 E,SE,S,SW,W,NW,N,NE*/
move[1].dx=1;move[1].dy=1;
move[2].dx=1;move[2].dy=0;
move[3].dx=1;move[3].dy=-1;
move[4].dx=0;move[4].dy=-1;
move[5].dx=-1;move[5].dy=-1;
move[6].dx=-1;move[6].dy=0;
move[7].dx=-1;move[7].dy=1;
}/*inimove*/
/*初始化栈*/
void inistack(sqstktp *s)
{s->top=-1;
} /*inistack*/
/*压栈，数据元素x入指针s所指的栈*/
int push(sqstktp *s,elemtype x)
{ if (s->top= =MAXLEN-1) /*栈满，返回False*/
return(False);
else
{ s->stack[++s->top] =x; /*栈不满，执行入栈操作*/
return(Ture);}
} /*push*/
/*栈顶元素出栈*/
elemtype pop(sqstktp *s)
{ elemtype elem;
if (s->top<0) /*如果栈空，返回空值*/
{ elem.x=Null;
elem.y=Null;
elem.dir=Null;
return(elem);
}
else
{ s->top- -;
return(s->stack[s->top+1]); /*栈不空，返回栈顶元素*/
}
}/*pop*/
/*初始化队列*/
void iniqueue(queuetp *s)
{ s->fornt=1; /*为直观，设置队头在数组下标为1处*/
s->rear=1;
} /*iniqueue*/
/*寻找迷宫中最短路径
int shortpath(int maze[][N2],struct moved move[],queuetp *p)
{ int i,j,dir,x,y;
p->queue[1].x=1;//入口点坐标入队列
p->queue[1].y=1;
p->queue[1].pre=0;
maze[1][1]=-1;//设置入口点以到达
while(p->front<=p->rear)//当队列不空时循环
{ i=p->queue[p->front].x;//j,i为出发点
j->p->queue[p->fornt].y;
for(dir=0;dir<8;dir++)
{ x=i+move[dir].dx;
y=j+move[dir].dy;
if(maze[x][y]==0)//如有可到达点，将此点坐标入对列
{ p->rear++:
p->queue[p->rear].x=x;
p->queue[p->rear].y=y;
p->queue[p->rear].pre=p->front;
maze[x][y]=-1;//设置已达到标志
}
if(((x==M)&&(y==N))//如到达出口，返回true
return（true）;
}
p->front++;//对头指针指向下一个队列元素
}
return (false);//迷宫无通路
}
/*显示迷宫通路
void printpath(queuetp*p,sqstktp *s)
{ int i,f;
elemtype elem;
i=p->rear;
Do /*从队列中取出最短路径放入栈中
{ elem.x=p->queue[i].x;
elem.x=p->queue[i].y;
f=push(s,elem);
if(f==false) /*如果f为假，则栈长度太短
printf(“栈长太短“)；
i=p->queue[i].pre;
}while(i>0);
i=s->top;
While(i>-1)
{ printf(s->stack[i].x,s->stack[i].y);/*显示迷宫最短的通路
if(i>0)
printf(“(”);
if((s->top-i+1)%4==0)
printf(“\n”);
i—;
}
printf(“\n”);
}
/*在迷宫中绘出最短路径
void draw(int maze[][n2],sqstktp*s)
{ int i,j;
elemtype elem;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
if(maze[i][j]==-1)
maze[i][j]=0;
while(s->top=-1) /*根据栈中元素的坐标，将最短路径各点的值该为8
{ elem=pop(s);
i=elem.x;j=elem.y;
Maze[i][j]=8;
}
for(i=1;i<=m;i++) /*显示已标记最短通路的迷宫
{ for(j=1;j<=n;j++)
printf(maze[i][j]);
printf(“\n”);
}
printf(“\n”);
}
/*寻找迷宫最短通路路径程序
Void main()
{ sqstktp *s;
queuetp *p;
int maze[m2][n2],f;
struct moved move[8];
inimaze(maze);/*初始化迷宫
s=(sqstktp*)malloc(sizeof(sqstktp));
inistack(s);/*初始化栈
p=(queuetp*)malloc(sizeof(queuetp));
iniqueue(p);/*初始化队列
inimove(move);/*初始化方向为一数组
f=shortpath(maze,move,p)/* 寻找迷宫最短通路路径程序
if(f==true)
{ printpath(p,s);/*如果找到，显示通路和绘制出通路标记的迷宫
draw(maze,s);
}
else
printf(“此迷宫无通路\n”);/*如果没找到显示无通路
}
题目四 停车场管理算法
[问题描述]
设有一个可以停放n辆汽车的狭长停车场，它只有一个大门可以供车辆进出。车辆按到达停车场时间的早晚依次从停车场最里面向大门口处停放（最先到达的第一辆车放在停车场的最里面）。如果停车场已停放满n辆车，则后来的车辆只能在停车场大门外的便道上等候，一旦停车场内有车开走，则排在便道上的第一辆车就进入停车场。停车场内如果有某辆车要开走，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车再按原来的次序进场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费。如果停留在便道上的车未进入停车场就要离去，允许其离去，不收停车费，并仍然保持在便道上等待的车辆的次序。编制一个程序模拟该停车场的管理。
[实现要求]
要求程序输出每辆车到达后的停车位置（停车场或便道上），以及某辆车离开停车场是应交纳的费用和它在停车场内停留的时间。
[实现提示]
汽车的模拟输入信息格式可以是：（到达/离去，汽车牌照号码，到达/离去的时刻）。例如，（‘A’，1，5）表示1号牌照车在5这个时刻到达，而（‘D’，5，20）表示5号牌照车在20这个时刻离去。整个过程可以在输入信息为（‘E’，0，0）时结束。本题可以用栈和队列来实现。
[程序实现]
设计思想根据题目要求，停车场只有一个门，因此可用一个栈来模拟；而当栈满后，继续来到的车辆只能停在便道上，根据便道停车的特点，可知这可以用一个队列来模拟，先排队的车辆先离开便道，进入停车场。由于停在停车场中间的车辆可以提出离开停车场，并且要求在离开到停车场到停车场大门之间的车辆都必须先离开停车场，让此车离去，然后再让这些车辆按原来的次序进入停车场，因此在一个栈和队列的基础上，还需要有一个地方（车辆规避所）保存为了让路而离开停车场的车辆，很显然这也应该用一个栈来模拟。因此本题中用到两个栈和一个队列对于停车场和车辆规避所，有车辆进入和车辆离去两个动作，这就是栈的进栈和出栈操作，只是还允许排在中间的车辆先离开停车场，因此在栈中需要进行查找。而对于便道，也有如队列和入队列的操作，同样允许排在中间的车辆先离开队列。这样基本动作只需利用栈和队列的基本操作即可实现。
整个操作过程是：当输入数据表示有车辆到达，则判断栈是否满，若未满就将新数据进栈（表示新到达的车辆进入停车场的里面），数据应包括车牌号和到达时间；若已满，就将数据放在队尾，表示车辆在便道上等待进入停车场。
当输入数据表示有车辆要离去，就在栈中寻找是否有该车牌号的车辆，如有就让此车辆离开停车场，并根据停车时间计费；如没有找到，就到队列中（便道上）去寻找此车牌号的车辆，如有就允许此车辆离开队列，但不收费；如没有就显示出错信息。
当离开停车场的车辆位于栈的中间时，必须先将此位置到栈顶之间的所有数据倒到另一个栈中去（车辆规避所），然后安排车辆出栈，最后将另一个栈中的数据倒回到停车场栈中来。
在模拟停车场管理时，还应注意，如果停车场栈中已没有车辆停放时，输入数据仍然要求车辆退出，则显示出错信息；程序中停车场的停车数量为n，但对便道没有规定，因此认为便道上可以听任意多的车辆。
程序实现根据题目分析的结果，停车场和车辆规避所的栈可以采用顺序栈，而便道可用链队列来模拟。
#define N 2 /*定义停车场栈长度*/
#define M 5 /*M为单元时间的收费值*/
#define True 1
#define False 0
#include,stdio.h”
/*存储结构*/
typedef struct /*定义栈元素的类型*/
{int num;
int arrtime;
}elemtype;
typedef struct /*定义栈*/
{elemtype stack[N];
int top;
}sqstktp;
typedef struct node /*定义队列结点的类型*/
{int num;
struct node *next;
}queueptr;
typedef struct /*定义队列*/
{queueptr *front,*rear;
}linkedquetp;
/*初始化栈*/
void inistack(sqstktp s)
{ s->top= -1;
}
/*压栈，将数据元素x压入指针s所指的栈*/
int push(sqstktp s,elemtype x)
{ if (s->top= =N-1)
return (False); /*如果栈满，返回False*/
else
{ s->stack[++s->top]=x; /*栈不满，x入栈。*/
return (True);
}
}/*push*/
/*弹栈，将栈顶元素出栈*/
elemtype pop (sqstktp *s)
{ elemtype x ;
if (s->top<0)
{ x.num=Null;
x.arrtime=Null;
return (x); /*如果栈空，返回空值*/
}
else
{ s->top - -;
return (s->stack[s->top+1]); /*返回栈顶元素*/
}
}/*pop*/
/*初始化队列*/
void inilinkedque (linkedquetp s)
{ s->fornt= (queueptr )malloc (sizeof (queueptr)); /产生一个新结点，作头结点*/
s->rear= s->fornt;
s->front->next =Null;
s->front->num =0; /*头结点的num保存队列元素的个数*/
}/* nilinkedque */
/*数据入队列*/
void enlinkedque (linkedquetp s,int numl)
{ queueptr *p;
p= (queueptr)malloc (sizeof (queueptr));/*产生一个新结点*/
p->num =numl;
p->next =Null;
s->rear->next=p; /*新结点入队列*/
s->rear=p;
s->front->num++; /*队列元素个数加1*/
}/*enlinkedque*/
/*数据出队列*/
int dllinkedque(linkedquetp s)
{ queueptr *p;
int n;
if (s->front ==s->rear)
return (Null); /*如果队列空，返回空值*/
else
{ p=s->front->next=p->next; /*返回队头元素值*/
if (p->next==Null)
s->rear=s->front;
n=p->num;
free(p);
s->front->num - -; /*队列元素的个数减1*/
return (n);
}
}/*dllinkedque*/
/*处理车辆到达的情况*/
void arrive(sqstktp *sl,linkedquetp *p,elemtype x)
{ int f;
f=push (s1,x); /*新到达的车辆入停车场栈*/
if (f==False)
{ enlinkedque(p,x.num); /*如停车场满，入便道队列*/
printf(“第%d号车停在便道第%d号车位上 \n”,x.num,p->front->num);
}
else /*新到车辆进入停车场*/
printf(“第%d号车停在停车场第%d号车位上\n”,x.num,sl->top+1);
}/*arrive*/
/*处理车辆离去的情况*/
void delive(sqstktp *sl,sqstktp *s2,linkedquetp *p,elemtype x)
{ int n,f=False;
elemtype y;
queueptr *q;
/*在停车场中寻找要离开的车辆*/
while ((sl->top>-1)&&(f!=Ture))
{ y=pop(sl);
if (y.num!=x.num) /*如果栈顶元素不是要离开的车辆，就将其放入车辆规避所*/
n=push(s2,y);
else
f=Ture;
}/*end of while
if (y.num= =x.num) /*在停车场中找到要离开的车辆*/
{ printf(“第%d号车应收费%d元\n”,y.num,(x.arrtime-y.arrtime)*M);
/*车辆规避所不空，将其全部放回停车场*/
while (s2->top>-1)
{ y=pop(s2);
f=push(s1,y); }
n=dllinkedque(p);
/*如便道上有车辆，将第一辆车放入停车场*/
if (n!=Null)
{ y.num=n;
y.arrtime=x.arrtime; /*计费时间为刚离开车辆的离去时间*/
f=push(s1,y);
printf(“第%d号车停在停车场第%d号车位上\n”,y.num,s1->top+1);
}
}/*end the pat one of if
else /*在停车场中没有找到要离开的车辆*/
{ while (s2->top>-1) /*将车辆规避所中的所有车辆放入停车场*/
{ y=pop(s2);
f=push(s1,y);
}
q=p->front;
f=False;
/*在便道上寻找要离开的车辆*/
while (f= =False &&q->next!=Null)
if (q->next->num!=x.num)
q=q->next;
else
/*在便道上找到该车辆*/
{ q->next=q->next->next;
p->fornt->num - -;
if (q->next= =Null)
p->rear=p->front;
printf(“第%d号车离开便道\n”,x.num); /*该车离开便道，但不收费*/
f=Ture;
}
/*在便道上也没找到要离开的车辆，输入数据错误*/
if (f= =False)
printf(“输入数据错误,停车场和便道上均无第%d号车\n”,x.num);
}
}/*delive*/
/*停车场模拟管理程序*/
void main( )
{ char ch1,ch2;
sqstktp *s1,*s2;
linkedquetp *p;
elemtype x;
int flag;
s1=(sqstktp *)malloc(sizeof(sqstktp));
s2=(sqstktp *)malloc(sizeof(sqstktp));
p=(linkedquetp *)malloc(sizeof(linkedquetp));
inistack(s1); /*初始化停车场栈*/
inistack(s2); /*初始化便道队列*/
flag= true;
for(;;)
{printf(“输入数据：‘A’/ ‘D’,车牌号，到达/离开时间\n”);
scanf(“%c %d %d”,&ch1,&x.num,x.arrtime);
ch2=getchar( );
switch (ch1)
{ case ‘A’, arrive(s1,p,x); /*车辆到达*/
break;
case ‘D’, delive(s1,s2,p,x); /*车辆离去*/
break;
case ‘E’,flag=False; /*结束程序运行*/
printf(“程序正常结束\n”);
break;
default,printf(“输入数据错误，重新输入\n”);
}
if (flag = =False) break;
}
}/*main*/
实验三 数组与广义表一、实验目的
1、了解数组的两种存储表示方法，掌握数组在作为运行的存储结构中的地址的计算方法。
2、了解稀疏矩阵的两种压缩方法的特点和适用范围，领会稀疏矩阵运算采用的处理方法。
掌握广义结构的特点及其存储表示方法。
二、实验内容题目一 鞍点问题
[问题描述]
若矩阵中的某个元素A[i,j]是第一行中的最小值，而又是第j列中的最大值，则称A[i,j]为矩阵A中的第一个鞍点。请写一个可确定此鞍点位置的算法（如果这鞍点存在），并给出此算法的时间复杂度。
[基本要求]
要求算法要考虑某行中具有多个相同的且又是该行中最小的元素的情况。
[实现提示]
可以用一位数组保存R[0..n-1]每一行中最小的元素，用一位数组C[0..n-1]来保存每一行中最大元素。如果R[i]=C[j]，则A[i,j] 即为鞍点。
[程序实现]
基本思想可先求出每行的最小值元素，放入一个一维数组min[m]中，在求出每列的最大元素，放入max[n]中，若某个元素既在min[i]中，又在max[j]中，则该R[i,j]元素便是鞍点元素，找出这样的鞍点元素，即找到此处有鞍点。
(2)程序实现
#include <stdio.h>
#define m 4
#define n 5
/*鞍点定位
void point（R）
int R[m][n];
{ int i,j;
int flag;
int min[m],max[n];
flag=0;
/*找每行最小值放入min[i]中
for(i=0;i<m;i++)
{ min[i]=R[i][0];
for(j=1;j<n;j++)
if(R[i][j]<min[i])
min[i]=R[i][j];
}
/*找每行最大值放入max[j]中
for(j=0;j<n;j++)
{ max[j]=R[0][j];
for(i=1;i<m;i++)
if(R[i][j]>max[j])
max[j]=R[i][j];
}
for(i=0;i<m;i++)
for(j=0;j<n;j++)
if(min[i]==max[j])
{ prinft(“(%d,%d):%d\n”,i,j,R[i][j]); /*输出鞍点
flag=1; /*置标志
}
if (!flag)
printf(“找不到鞍点\n”);
}
/*主函数
main()
{ int R[m]}[n];
int i,j;
for(i=0;i<m;i++)
for(j=0;j<n;j++)
scanf(&R[i][j]);
point(r);
}
题目二 N阶魔阵问题
[问题描述]
给定一奇数n，构造一个n阶魔阵，n阶魔阵是一个n阶方阵，其元素由自然数1，2，3……n2组成，魔阵的每行元素之和，每列元素之和以及主、副对角线元素之和均相等。即对于给定的奇整数n以及i=1…..n,魔阵a满足条件：
∑aik (k=1~ n)=∑aki(k=1~ n)=∑akk(k=1~ n)=∑ak,n-k+1(k=1~ n)
[基本要求]
要求输出结果的格式要具有n阶方阵的形式。
[实现提示]
依次将自然数填入方阵中，共填n轮，每轮填n次。第一轮的第一次将1填入方阵的中间一行的最后一列位置。设前一次填入的位置是aij:
（1）每轮中第2至第n次将数填入ai+1,j+1,若遇到下列两种情况之一，则填写位置按以下规则调整。
aij是最后一列（即j=n）位置，则将下一个数填入ai+1,1;
aij是最后一行（即i=n）位置，则将下一个数填入a1,j+1.
(2) 新一轮的第一次填入a1,j-1.
[程序实现]
/*N阶魔阵问题主函数
main()
{ int r[m][n]; /*设数组下标均从1开始
int n,j,i,k;
scanf(&n);
i=(n+1)%n; /*相除
J=n+1;
For(k=1,k<=(n*n);k++)
{ if(k%n==1)
j--;
else
{ i=i%n+1;
j=j%j+1;
}
r[i][j]=k;
}
for(i=1;i<=n;i++)
{ for(j=1;j<=n;j++)
printf(r[i][j]);
}
}
也可按下列方法给出n魔阵，其算法思想为：
由魔方阵知其排列规律如下：
将1放第一行中间一列；
从“2”开始直到n*n止，各数一次按下列规则存放：每一个数存放的行比前一个数的行数减1，列数加1；
如果上一数行数为1，则下一个数行数为n（指向最下一行）；
当上一数的列数为n时，下一个数的列数应为1，行数减1；
如果按上面规则确定位置上的已有数，或上一个数是第1行第 n列时，则把下一个数放在上一个数的下面。
算法程序如下：
#define n 15
main()
{ int r[m][n];
int r,c,k,i,j;
k=0;
scanf(&k);
for(i=1;i<=k;i++)
for(j=1;j<=k;j++)
r[i][j]=0;
i=1;
t=1;
m=k*k;
J=(k+1)%2;
R[i,j]=t;
T++;
While(t<=m)
{ x=i-1;
y=j+1;
if((x<1)&&(y<k))
{ i=x+2;
J=-y-1;
}
else
if(y<k)
{ i=x;
j=1;
}
else
if(i<1)
{ i=k;
j=y;
}
else
if(r[x][y]!=0)
{ i=x+2;
J=y-1;
}
else
{ i=x;
j=y;
}
r[i][j]=t;
}
for(i=1;j<=k;i++)
{ for(j=1;j<=k;j++)
printf(r[i][j]);
printf(“\n”);
}
}
实验四 树一、实验目的进一步掌握指针变量，动态变量的含义。
掌握二叉树的结构特性，以及各种存储结构的特点及使用范围掌握用指针类型描述、访问和处理二叉树的运算二、试验内容题目一 二叉树子树交换算法
[基本要求]
编写交换以二叉树链表作存储结构的二叉树中所有结点的左、右子树的算法。
[基本思想]
设二叉树的根指针为t，且以二叉链表表示，可利用一个类型为seqstack的指针来实现，且设栈单元包含两个域，一个为data，一个为top，整个栈容量为maxsize，当树非空时，将当前的树根结点入栈，同时将当前栈顶元素出栈当作根结点，然后依据当前的根结点是否具有孩子结点来判断是否将其左、右指针进行交换；再将交换后的左指针或右指针入栈，这样反复进行，直到栈为空为止。
[算法实现]
#define null o
typedef struct node
{ int data;
struct node lchild,rchild;
}bitree;
typedef int datatype ; /*栈元素的数据类型
#define maxsize 64 /*栈可能达到的最大容量
typedef struct {
datatype data[maxsize];
int top;
} seqstack； /*顺序栈类型定义
seqstack s; /* s顺序栈类型指针
/*建立二叉树
bitree *creat()
{ bitree *t;
int x;
scanf(“&x);
if(x==0)
t=null;
else
{ t=malloc(sizeof(bitree));
t->data=x;
t->lchild=creat();
t->rchild=creat();
}
return t;
}
/*中序遍历二叉树
void inorder(t)
bitree *t;
{ if(t!=null)
{ inorder(t->lchild);
prinrf(t->data);
inorder(t->rchild);
}
}
/*对二叉树t所有结点左右子树进行交换
exchange(t)
bitree *t
{ bitree *p;
seqstack s; /*为一指针栈，类型为seqstack
if(t)
{ s->top=1;
s->data[s->top]=t; /*跟指针t进栈
do
{ t=s->data[s->top]; /*栈顶元素退栈
s->top--;
if((t->lchild!=null)||(t->rchild!=null))
{ p=t->lchild; /*结点的左右指针交换
t->lchild=t->rchild;
t->rchild=p;
}
if(t->lchild!=null) /*交换后的左孩子指针入栈
{ s->top++;
s->data[s->top]=t->lchild;
}
if(t->rchild!=null) /*交换后的右孩子指针入栈
{ s->top++;
s->data[s->top]=t->rchild;
}
}while(s->top==0) /*栈空结束
}
}
/*交换算法主函数
main()
{ bitree *root;
root=creat();
inorder(root);
exchange(root);
inorder(root);
}
对于exchange算法也可以利用以下的递归算法
void exchange(t)
bitree *t;
{ bitree *p;
if(t!=null)
{ p=t->lchild;
t->lchild=t->rchild;
t->rchild=p;
exchange(t->lchild);
exchange(t->rchild);
}
}/*exchange*/
题目二 按层次顺序遍历二叉树
[基本要求]
已知以二叉链表作存储结构，试编写按层次顺序遍历二叉树的算法。
[算法思想]
本算法要采用一个队列q，先将二叉树根结点入队列，然后退队列，输出该结点，若它有左子树，便将左子树根结点入队列，若它有右子树，边将右子树根结点入队列，如此直到队列为空为止，因为队列的特点是先进先出，从而达到按层次顺序遍历二叉树的目的。
[算法实现]
#define m 100
#define null 0
typedef struct node
{ int data;
struct node lchild,rchild;
} bitree;
bitree *que[m];
int front=0,rear=0;
/*建立二叉树
bitree *creat()
{ bitree *t;
int x;
scanf(&x);
if(x==0)
t=null;
else
{ t=malloc(sizeof(bitree));
t->data=x;
t->lchild=creat();
t->rchild=creat();
}
return t;
}/*create*/
/*中序遍历二叉树
void inorder(t)
bitree *t;
{ if(t!=null)
{ inorder(t->lchild);
printf(t->data);
inorder(t->rchild);
}
}
/*入队列
void enqueue(t)
bitree *t;
{ if(front!=(rear+1)%m)
{ rear=(rear+1)%m;
que[rear]=t;
}
}
/*出队列
bitree *delqueue()
{ if(front==rear)
return null;
front=(front+1)%m;
return (que[front]);
}
/*按层次遍历二叉树
void levorder(t)
bitree *t;
{ bitree *p;
if(t!=null)
{ enqueue(t);
while(front!=rear)
{ p=delqueue();
printf(p->data);
if(p->lchild!=null)
enqueue(p->lchild);
if(p->rchild!=null)
enqueue(p->rchild);
}
}
}
/*主调函数
main()
{ bitree *root;
printf(“\n”);
root=creat();
inorder(root);
printf(“\n”);
levorder(root);
}
也可以用非递归方式写出levorder算法。可利用一个队列que来保存遍历过程中的各个结点。由于二叉树以二叉链表存储，所以设que为一个指向数据类型为 bitree的指针数组，最大容量为maxsize,下标从1开始，同层结点从左到右存放。其中front为队头指针，rear为尾指针
/*按层次遍历二叉树t
levlorder(t)
bitree t; /*二叉树t为类型bitree
{ /*队列que为一个指向类型指针数组，下标从1开始
bitree *que[maxsize]
int rear,front;
if(t)
{ front=0; /*置空队列
rear=1;
que[1]=t;
do
{ front=front%maxsize+1; /*出队列
t=que[front];
printf(t->data);
if (t->rchild!=null) /*左子树的根结点入队
{ rear=rear%maxsize+1;
que[rear]=t->lchild;
}
if (t->rchild!=null) /*右子树的根结点入队
{ rear=rear%maxsize+1;
que[rear]=t->rchild;
}
} while(rear==front);
}
}/*levorder*/
题目三 二叉排序树遍历算法
[基本要求]
已知二叉排序树以二叉链表作为存储结构，试编写按从大到小的顺序输出二叉排序树的各结点的算法。
[算法思想]
可以先建立一棵二叉排序树，以二叉链表表示，由于按中序遍历二叉排序树即为按递增次序遍历，所以要按从大到小的顺序输出二叉排序树的各结点的值，可以对二叉排序树从树根结点右子树中最右下结点开始进行遍历，先遍历右子树，在访问根结点，最后遍历左子树，这样就可以得到一个结点从大到小的顺序输出的序列。
[算法实现]
#define m 100
#define null 0
typedef struct node /*二叉树链表类型定义
{ int data;
struct node *lchild,*rchild;
} bitree;
/*从右子树开始遍历二叉排序树
void destorder(t)
bitree *t;
{ if(t!=null)
{ destorder(t->rchild);
printf(t->data);
destorder(t->lchild);
}
}
/*将新结点*s插入到t所指的二叉排序树中
bitree *insertbst(t,s)
bitree *s,*t;
{ bitree *f,*p;
p=t;
while(p!=null)
{ f=p;
if(s->data==p->data)
return t;
if(s->data<p->data)
p=p->lchild;
else
p=p->rchild;
}
if(t==null) return s;
if (s->key<f->key)
f->lchild=s;
else
f->rchild=s;
return t;
}
/*返回二叉排序树
bitree *creatord()
{ bitree *t,*s;
int x;
t=null;
scanf(&x);
while(x!=0)
{ s=malloc(sizeof(bitree));
s->data=x;
s->lchild=null;
s->rchild=null;
t=insertbst(t,s);
scanf(&x);
}
return t;
}
/*主函数
main()
{ bitree *root;
printf(“\n”);
root=creatord();
destorder(root);
printf(“\n”);
}
实验五 图一、实验目的
1、掌握图的基本存储方法。
2、掌握有关图的操作算法并用高级语言实现。
3、熟悉图的各种存储结构及其构造算法，了解实际问题的求解效率与采用何种存储结构以及算法有着密切的联系。
4、熟练掌握图的两种搜索路径的遍历方法。
二、实验内容题目一 优化通信网的设计算法
[基本要求]
如果以无向网表示n个城市之间的通信网络的建设计划，顶点表示城市，边上的权表示该线路的造价，设计一个方案，使这个通信网的总造价最低。
[实现提示]
这是一个求连通的带权无向图（及网络）的最小代价生成树的问题。建立图的邻接矩阵，然后以prime算法来求最小生成树。
[算法实现]
这里给出由R.C.Prim提出的求最小代价生成树的算法。设图的顶点集合V有n个顶点，prim算法粗略的描述如下：
（1）一个顶点的集合S1和一个边的集合TE，S1和TE的初始状态皆为空集。
（2）选中图中的一个顶点k（从此顶点开始求最小代价生成树），将k加入集合S1。
（3）重复下列步骤，直至选取了n-1条边：
①选取一条权值最小的边（x,y）；
②将顶点y加入集合S1，边（x,y）加入集合TE。
下面是用邻接表做为数据结构实现prim算法的程序。
#ingclude <stdio.h>
#define n 5 /* n为顶点数*/
#define max 1000.0
typedef struct node
{ int no;
float wgt;
struct node *next;
} edgenode
typedef struct
{ char vtx;
edgenode *link
} vexnode;
float gali[n][n]={{0,2,12,10,max},{2,0,8,max,9},
{12,8,0,6,3,},{10,max,6,0,7},{max,9,3,7,0}};
typedef vesnode Graph[n];
Grapg G;
/*用邻接表实现prim算法*/
Void prim(vexnode Gp [ ],int k)
{ int v2link[n],vset[n],parent[n],w[n];
edgenode *ptr;
int x,s,ecount，i，y，z，f;
s=-1;
v2link[n]=-1;
ecount=0;
for(i=0;i<n;i++)
if(i!=k)
vset[i]=3;
while(ecount <n-1)
{ ptr=G[x].link;
while(ptr!=Null)
{ y=ptr->no;
if((vset[y]==2)&&(ptr->wgt<w[y])) /*y在集合v2*/
{ parent[y]=x;
w[y]=ptr->wgt;
}
if (vset[y]==3) /*y在集合v3*/
{ vset[y]=2;
v2link[y]=s;
s=y;
parent[y]=x;
w[y]=ptr->wgt;
}
ptr=ptr->next;
}
if(s==-1)
break; /*无最小代价生成树*/
z=x=s;
y=v2link[x];
f=-1;
while(y!=-1)
{ if (w[y]<w[x])
{ x=y;
f=z;
}
z=y;
y=v2link[y];
}
if(f==-1)
s=v2link[x];
else
v2link[f]=v2link[x];
vset[x]=1;
ecount ++; /*边数记数*/
}
printf(“\nroot%c:\t”,G[k].vtx); /*输出结点*/
for(i=0;i<n;i++)
{ if(i!=k)
{ printf(G[i].vtx);
f=parent[i];
printf(“G[f].vtx);
}
}
/*建立邻接表
void creatlist(vexnode ga[])
{ int i,j,k,e,w;
edgenode *se;
for(i=0;i<n;i++)
{ ga[i].vtx=’a’+i;
for(j=0;j<n;j++)
{ if((gali[i][j]<max)&&(gali[i][j]!=0))
{ se=(edgenode*)malloc(sizeof(*se));
se->no=j;
se->next=ga[i].link;
se->wgt=gali[i][j];
ga[i].link=se;
}
}
}
}
/*主程序*/
main()
{ int i;
edgenode *ve;
creatlist(G);
for(i=0;i<n;i++)
{ printf(G[i].vtx);
ve=G[i].link;
while(ve!=null)
{ printf(ve->no,ve->wgt);
ve=ve->next;
}
}
prim(G,4);
return 0;
}/*main*/
题目二 最优选课序列算法设计
[基本要求]
软件专业的学生要学习一系列的课程，其中有些课程必须在其先修课程之后才能学习，具体关系见下表：
课程编码
课程名称
先决条件
C1
程序设计基础
无
C2
离散数学
C1
C3
数据结构
C1，C2
C4
汇编语言
C1
C5
语言的设计和分析
C3，C4
C6
计算机原理
C11
C7
编译原理
C3，C5
C8
操作系统
C3，C6
C9
高等数学
无
C10
线性代数
C9
C11
普通物理
C9
C12
数值分析
C1，C9，C10
假使每门课程的学习时间为一学期，试为该专业的学生设计教学计划，使他们能在最短的时间内修完这些课程。
[实现提示]
以顶点代表课程，弧代表课程的先后修关系，按表中条件建立有向无环图的邻接表结构并统计得到初始化的入度为0的顶点，利用拓扑排序算法来进行课程安排。假定一个进修班的学生必须完成所列的全部课程。在这里，课程代表活动，学习每门课程的先决条件是学完它的全部先修课，如“编译技术”课程就必须先修它的两门先修课程“数据结构”和“算法语言”之后,“高等数学”课程则可以在后修课程之前随时安排，因为它是基础课程。
通常我们把这种顶点代表活动，边代表活动间先后关系的有向图称为顶点活动网，简称阿Aov网。一个Aov网应该是一个有向无环图，即不应该带有回路，因为若带有回路，则回路的所有活动都无法进行。
在Avo网中，若不存在回路，则所有活动可排列成一个线性序列，使每个活动的所有前驱活动都排列在该活动的前面，我们称为拓扑序列（Topological orde），由Aov网构造拓扑序列的过程叫做拓扑排序。Aov网的拓扑序列不是唯一的，满足上述定义的任一线性序列都称作它的拓扑序列。
由Aov网构造拓扑序列的实际意义是：如果按照拓扑序列中的顶点次序进行每一项活动，就能够保证在开始每一项活动时，他的所有前驱活动都已完成，从而使得整个工程结点顺序进行。
由构造拓扑序列的拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止。
选择一个入度为0的顶点并输出之；
从网中删除该顶点及所有从该顶点出发的边。
循环结束时，若输出的顶点数小于网中的顶点数，则输出“有回路”错误信息，否则输出的顶点序列就是一种拓扑序列。
为了在计算机上实现拓扑排序算法，Aov网采用邻接表表示较方便，不过要在表头结点结构中增加一个保存顶点入度的域（indegree）。在进行拓扑排序中，为了把拓扑排序都保存起来，而且又便于插入、删除和节省存储，最好的方法是把它们链接成一个栈。另一方面，当一个顶点入度为0时，邻接表中的对应表结点中的入度域(indegree)就没有用了，可正好利用它作为链栈单元使用，用来保存下一个入度为0的顶点序号，通过所有入度为0的表头结点中的入度域就可以把 入度为0的顶点（对应表头结点）都静态链接起来。在这个链栈中，栈顶指针top指向第一个入度为0的顶点vi(对应表头向量中的第i个分量，即vi的表头结点)，vi的表头结点的入度域指向第二个入度为0的顶点vj，以此类推，最后一个入度为0的表头结点的如度域应置为0（即空指针），表示栈底。
采用邻接表作为实现上述算法的数据结构。算法首先扫描邻接表，求出图中每一个顶点的入度存于数组IN中，然后将所有入度为0的顶点组成一个链表并作为链接存储的栈进行操作，top指向栈顶。
[算法实现]
typedef struct node
{ int no;
float wgt;
struct node *next;
} edgennode;
typedef struct
{ char vtx;
edgenode *link;
} vexnode;
typedef vexnode Graph [n];
Graph G;
/*拓扑排序
void topolo(Graph g)
{ int top,count,i,j;
char k;
edgenode *p;
int IN[n];
for(i=0;i<n;i++); /*数组IN初始化
IN[i]=0;
for(i=0;i<n;i++) /*求图中个顶点的入度
{ p=g[i].link;
while(p!=null)
{ j=p->no;
IN[j]++;
P=p->next;
}
}
top=-1;
for(i=0;i<n;i++) /*将入度为0的顶点组成一个栈
if(IN[i]==0)
{ IN[i]=top;
Top=i;
}
count=0;
while(top>=0)
{ k=g[top].vtx;
printf(k); /*输出顶点
p=g[top].link;
top=IN[top];
count++;
while(p!=null)
{ j=p->no;
IN[j]--;
if (IN[j]==0) /*将入度为0的顶点插入栈中
{ IN[j]=top;
Top=j;
}
p=p->next;
}
}
if(count<n)
printf(“\n the network has a cycle”);
}/*topolo
题目三 交通购票指南系统算法
[基本要求]
假设以一个带权有向图表示某一区域的公交线路网，图中顶点代表一些区域中的重要场所，弧代表以有的公交线路，弧上的权代表该线路上的票价（或搭乘所要的时间）。试设计一个交通指南系统，直到来咨询者以最低的票价或最少的时间从区域中的某一场所到达另一场所。
[实现提示]
该问题可以归结为一个求带权有向图中顶点间最短路径的问题。分别建立以票价为权或以搭乘时间为权的邻结矩阵，以FLOYD算法来求最短路径及其路径长度。
设图G=(V，E)的顶点集合V={0,1,…., n-1}，图用邻接矩阵表示。一开始，若弧<i,j>∈E(G)，则认为i到j的最短路径为（i，j），长度为弧<i,j>的权。算法使用一个n*n的矩阵A进行n次迭代来计算每对顶点间的最短路径，迭代过程中得到的一个矩阵序列A0,A1,…..,An，矩阵元素An[i,j]的值即为从顶点i到顶点j的最短路径长度。首先在路径（i，j）中插入顶点0，考虑路径（i,0,j），若该路径存在，即图中有弧<i,0>和<0,j>，比较路径（i,j）和路径（i,0,j）的长度，取长度最短者作为当前求得的从顶点i到顶点j且中间顶点编号不大于0的最短路径，记为（i,…..j）,其长度存于A1[i,j]中，然后再考虑路径（i,…,1,…j）,由于（i,…..j）和（i,…,1,…j）是从顶点i到顶点1及从顶点1到顶点j中间顶点编号不大于1的最短路径，比较路径(i,…,1)和路径 （i,…,1,…j）的长度，若后者较短，则路径（i,…,1,…j）即为当前求得的从顶点i到顶点j中间顶点编号不大于1的最短路径,其长度存于A2[i,j]中，………，依次类推，逐个插入图的每个顶点，最后必将求得顶点i到顶点j且中间顶点编号不大于n-1的最短路径。在k+1次迭代时，矩阵Ak+1[i,j]的值为： Ak[i,j]
A k+1[i,j]=min (0 ( k ( n-1)
Ak[i,k]+ Ak[k,j]
其中Ak+1[i,j]表示经过k+1次迭代后得到的值，他等于从i到j中间顶点编号不大于k的最短路径长度。
下面是R.W.FLOYD求每对顶点之间最短路径算法的C语言程序，程序中矩阵A用来进行n次迭代，矩阵P用来记录路径。P[i,j]为迭代过程中当前得到的从顶点i到顶点j的最短路径上最后被插入的那个顶点。
[算法实现]
typedef struct node
{ int no;
float wgt;
struct node *next;
} edgenode;
typedef struct
{ char vtx;
edgenode*link;
} vexnode;
typedef vexnode Graph[n];
/*floyd算法，求最短路径
void floyd(Graph G,float A[n][n],int p[n][n])
{ int i,j,k;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{ A[i][j]=G[i][j];
P[i][j]=-1;
}
for(k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(A[i][k]+A[k][j])
{ p[i][j]=A[i][k]+A[k][j];
}
}/*floyd*/
实验六 查找一、实验目的
1、掌握查找的不同方法，并能用高级语言实现查找算法。
2、熟练掌握顺序表和有序表的查找方法以及静态查找树的构造方法和查找算法，理解静态查找树的折半查找方的法。
3、熟练掌握二叉树的构造和查找方法。
二、实验内容题目一 二叉树的构成算法
[基本要求]
设计一个读入一串整数构成一棵二叉排序树的算法。
[实现提示]
二叉排序树的构成，可从空的二叉树开始，每输入一个结点数据，就建立一个新结点、插入到当前已生成的二叉排序树中，所以，它的主要操作是二叉排序树的插入运算。在二叉排序树中插入新结点，只要保证插入后仍符合二叉排序树的定义即可。插入是这样进行的：若二叉排序树为空，则待插入结点*s作为根结点插入到空树中；当二叉排序树非空，将待插结点的关键字s->key与树根的关键字t->key比较，若s->key=t->key,则说明树中已有此结点，无需插入；若s->key<t->key,则将待插结点*s插入到根的左子树中，否则将*s插入到根的右子树中。而子树的插入过程又和在树中的插入过程相同，如此进行下去，直到把结点*s作为一个新的树叶插入到二叉排序树中，或则直到发现树中已有*s结点为止.
[算法实现]
typedef struct node
{ int key; /*关键字项
int other; /*其他数据项
struct node *lchild,*rchild;
} bstnode;
/*中序遍历二叉树
void inorder (t)
bstnode *t;
{ if(t!=null)
{ inorder(t->lchild);
printf(“%4d”,t->key);
inorder(t->rchild);
}
}
/*将新结点*s插入到t所指的二叉排序树中
bstnode insertbst(t,s)
bstnode *s,*t;
{ bstnode *f,*p;
p=t;
while(p!=null)
{ f=p;
if(s->key==p->key)
return t;
if(s->key<p->key)
p=p->lchild;
else
p=p->rchild;
}
if(t==null)
return s;
if(s->key<f->key)
f->lchild=s;
else
f->rchild=s;
return t;
}
/*返回二叉排序树
bstnode *creatord()
{ bstnode *t,*s;
int key;
t=null;
scanf(“&d”,&key);
while(key!=0)
{ s=malloc(sizeof(bitree));
s->key=key;
s->lchild=null;
s->rchild=null;
scanf(“%d”,&data);
s->other=data;
t=insertbst(t,s);
scanf(“%d”,&key);
}
return t;
}
/*主函数
main()
{ bstnode *root;
root=creatord();
inorder(root);
}
题目二 二叉树结点删除算法
[基本要求]
写出从二叉排序树中删除一个结点，使该二叉排序树仍为二叉排序树的算法。
[实现提示]
本题要注意的是，删除二叉排序树中的结点与删除一棵树中的结点不同，二叉排序树的结点对应的是一条记录，只要在删除它后仍使它为二叉排序即可；而要将一棵树中的结点删除，是将该结点同他的左右子树一并删除。
要将二叉排序树的结点删除，必须建立一棵二叉排序树，以二叉链表方式表示，然后再进行二叉排序树结点删除，依据被删除结点位置又可分为根和非跟结点两种情况，可将算法思想描述为：
（1）若被删除结点k是二叉排序树的根结点，则:
若k有左子树L，而无右子树，则将仅需将L作为根结点即可若k有右子树r，而无左子树，则将仅需将r作为根结点即可若k既有左子树L又有右子树r,则可将L作为根结点。此时，若L无右子树，需将的L右孩子指针指向r；若L有右子树，则需沿着L右分支一直往下检索，直到找到最右的、且没有右子树的结点为止（即最右下的一个结点），然后把该结点的右孩子指针指向r。
（2）若被删除的结点k不是二叉排序树的根结点，此时可设*p为k的双亲结点，k是*p的左子树（或右子树），则可按以下情况进行处理：
若k有左子树L，而无右子树，则应将*p结点的左指针（或右指针）改指向L;
若k无左子树L，而有右子树，则应将*p结点的左指针（或右指针）改指向r
若k既有左子树又有右子树，则应将*p结点的左指针（或右指针）改向L；若L无右子树，需将的L右孩子指针指向r；若L有右子树，则需沿着L右分支一直往下检索，直到找到最右的、且没有右子树的结点为止，然后把该结点的右孩子指针指向r。
设t为二叉排序树的根指针，二叉排序树以二叉链表储存，k为待删除结点的关键字，则可的程序如下：
[算法实现]
首先建立一个二叉排序树，以二叉链表方式表示
typedef struct node
{ int key; /*关键字项
struct node * lchild,*rchild;
} bitree;
/*中序遍历二叉树
void inorder(t)
bitree *t;
{ if(t!=null)
{ inorder(t->lchild);
printf(t->key);
inorder(t->rchild);
}
}
/*将新结点*s插入到t所指的二叉排序树中
bitree *inserbst(t,s)
bitree *s,*t;
{ bitree *f,*p;
p=t;
while(p!=null)
{ f=p;
if(s->key==p->key)
return t;
if(s->key<p->key)
p=p->lchild;
else
p=p->rchild;
}
if(t==null)
return s;
if(s->key<f->key)
f->lchild=s;
else
f->rchild=s;
return t;
}
/*返回二叉排序树
bitree *creatord()
{ bitree *s,*t
int key;
t=null;
scanf(“&d”,&key);
while(key!=0)
{ s=malloc(sizeof(bitree));
s->key=key;
s->lchild=null;
s->rchild=null;
scanf(“%d”,&data);
s->other=data;
t=insertbst(t,s);
scanf(“%d”,&key);
}
return t;
}
再给出检索算法描述如下：
将p,q作为全程量看待，则有
/*在一个儿叉树t中间所关键字为k的结点
/* t为二叉排序树的根指针，二叉排序树以二叉链表存储
bstsrch (t,k)
bitree t;
int k;
{ int flag;
p=null; /*p,q为全程量
q=t;
flag=false;
while((q!=null)&&(flag==false))
if(k==q->key)
flag=true;
else
{ p=q;
if(k<q->key)
q=q->lchild;
else
q=q->rchild;
}
}
然后给出删除算法如下：
bittree *p,*q; /* p,q为bitree类型全局变量
/*从二叉排序树中删除一个结点
bintreedele(t,k)
bitree *t;
int k;
{ bitree *r;
bstsrch(t,k); /*检索过程，设待删除结点在树中
if(q!=null) /*若被删除结点在树中
if(p==null) /*若被删除结点是根结点
if(q->lchild==null) /*若被删除结点无左子树
t=q->lchild;
else /*若被删除得结点无右子树
if(q->rchild==null)
t=q->lchild;
else /*被删除结点儿女双全
{ r=q->lchild;
while(r->lchild!=null)
r=r->rchild; /*检索中序前趋
r->rchild=q->rchild;
t=q->lchild;
}
else /*被删除结点不是根结点
if(q->lchild==null) /*若被删除得结点无左子树
if(q==p->lchild)
p->lchild=q->rchild;
else
{ r=r->rchild;
while(r->rchild!=null) /*查找中序前趋
r=r->rchild;
r->rchild=q->rchild;
if(q==p->lchild)
p->lchild=q->lchild;
else
p->rchild=q->lchild;
}
free(q);
}
/*主程序
main()
{ bitree *root,*p,*q;
int k;
root=creatord();
inorder(root);
scanf(“%d”,&k);
bintreedele(root,k);
inorder(root);
}
题目三 斐波那契（Fibonacci）检索算法
[实现提示]
斐波那契检索是利用数列Fibonacci进行的一种检索的方法首先给出数列如下：
f0=0 n=0
f1=1 n=1
……,
fn=fn-1+fn-2 n>=2;
从而可得斐波那契序列为：0，1，2，3，5，8，13，21，…..假设利用一个数组r来存放斐波那契数列，且r数组中的元素按关键字从小到大的顺序排列，并且假定元素个数n比某个Fibonacci数fm小1，即n=Fm- 1，第一次，用要检索的关键字key与r[fm-1].key进行比较，其算法思想为：
（1）若key=r[fm-1].key，则检索成功，r[fm-1]为key所在记录
（2）若key<r[fm-1].key，则下一次检索时再从1到fm-1 -1的范围内进行，此时序列长度为fm-1;
（3）key>r[fm-1].key，则下一次检索在从下标从fm-1 +1到fm -1的范围内进行，此时该序列的长度为(fm –1)-(fm-1 +1)+1=fm-fm-1 –1=fm-2 -1，从而可得到：
设r为顺序存储的线性表，则：
r[1].key ( r[2].key (……,( r[n].key
key为已知的关键字，在r中检索关键字为key的记录，若找到，则返回其下标，否则返回0。假定m为Fibonacci数列的序号，则有fm+i=n+1(i ( 0,fm+1>i+1,n为记录元素个数)。
[算法实现]
首先可定义一个递归函数，求Fibonacci数列的函数
int Fibonacci(n)
int n;
{ if(n==0)
return(0);
else
if(n==1)
return(1);
else
return (Fibonacci(n-1)+Fibonacci(n-2));
}
然后再给出Fibonacci数列检索的算法：
#define keytype int;
#define datatype int;
type struct
{ keytype key;
datatype other;
} rectype;
Fibonaccisrch(r,k,n)
rectype r[ ];
keytype k;
int n;
{ int i,p,q,t,m,flag;
i=Fibonacci(m-1); /*设m为 Fibonacci数列序号
P=Fibonacci(m-2)；
Q=Fibonacci(m-3);
S=n+1-(i+p);
if(k>r[i].key
i=i+s;
Flag=false;
While((i))&&(!flag))
Switch
{ case k==r[i].key,flag=ture;
break; /*检索成功
case k<r[i].key,if(q==0) /*检索失败
i=0;
else
{ i=i-q;
t=p;
p=q;
q=t-q;
}
break;
case k>r[i].key,if(p==1)
i=0; /*检索失败
else
{ i=i+q;
P=p-q;
q=q-p;
}
break;
default: }
return (i);
}
实验七 排序一、实验目的掌握常用的排序方法，并掌握用高级语言实现排序算法的方法。
深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用。
3、了解各种方法的排序过程及其依据的原则，并掌握各种排序方法的时间复杂度的分析方法。
二、实验内容题目一 成绩统计算法
[问题描述]
给出n个学生的考试成绩表，每条信息由姓名和分数组成，试设计一个算法：
（1）、按分数高低次序，打印出每个学生在考试中获得的名次，分数相等的为同一名次；
（2）、按名次列出每一个学生的姓名和分数。
[基本要求]
学生的考试成绩表必须通过键盘输入数据而建立，同时要对输出进行格式控制。
[算法实现]
下面给出的是用直接选择排序算法实现的C语言程序。在此基础上还可以尝试用直接插入、shell排序、冒泡排序、快续排序、归并排序等算法实现对本问题的求解
#define n 30
typedef struct student
{ char name[8];
int score;
} student r[n];
/*用直接选择排序算法统计学生成绩排名
main()
{ int num,i,j,max,temp;
printf(“\n请输入学生成绩\n”);
for(i=0;i<n;i++)
{ printf(“姓名：“)；
scanf(“%c”,stu[i].name);
scanf(“%4d”,&stu[i].score);
}
num=1;
for(i=0;i<n;i++)
{ max=i;
for(j=i+1;j<n;j++)
if(r[j].score>r[max].score)
max=j;
if(max!=i)
{ temp=r[max];
r[max]=r[i];
r[i]=temp;
}
if((i>0)&&(r[i].score<r[i-1].score))
num=num+1;
printf(num,r[i].name,r[i].score);
}
}
题目二 最小意义关键字优先的基数排序法
[基本要求]
采用最小意义关键字优先的基数排序法，实现对数列的排序，数列中的每个数据由d位数字组成，不足 d位的数据高位补0。
[算法提示]
设待排序数据序列为r1,r2,r3…..rn,他们各自的关键字为k1,k2….kn;其中每个关键字由d个分量组成，kid,kid-1…ki1,其中ki1位最大意义关键字分量，kid为最小意义关键字分量，从而将数据按关键字分量kid,kid-1…ki1的顺序对数据排序。
设待排序的数据均由3位数组成，即d=3;显然，每个数据由分量ki3,ki2,ki1组成，ki1表示第一位，ki2 表示第二位,ki3表示第三位。
由于待排序数据为数列，则每位上的数据由0-9种的某个数组成，故可设置10个队列，用数组f和e的元素fi,ei 分别表示队列的开头和结尾（i=0~9）,只要每一次排序前先将各队列置空，然后按ki3,ki2,ki1的顺序对其排序即可。
为了使排序过程尽可能地不进行数列中数据的移动，可设计结点为一个含关键字域key和指针域next的结构体。于是，第i个队列由fi和ei分别存放该队列中的第一个数据和最后一个数据在数列中的位置的下标值。数列在进行排序前、之后及排序过程中，各队列中各个数据的先后顺序通过指针域next的链域来实现，可由变量p来指示排序后这个有序数列的第一个元素的位置。
[算法实现]
#define d 3 /*关键字位数为3
#define m 10 /*基数10
typedef struct
{ int key[d]; /*关键字由d个分量组成
int next; /*静态指针域next
datatype other; /*其他域
} rectype;
typedef struct
{ int f,e; /*n个队列的首指针，和尾指针
} queue;
queue b[m]; /*用队列表示
/*对r[0]到r[n-1]进行基数排序，返回收集用的链头指针
int basesort（r）
rectype r[ ];
{ int i,j,k,t,p;
for(i=0;i<n;i++) /*将 r[0]到r[n-1]链成一个静态表
r[i].next=i+1;
r[n-1].next= -1; /*将初始链表的终端结点指针置空
p=0; /*p指针指向静态链表的第一个结点
for(j=d-1;j>=0;j--) /*进行d趟排序
for(i=0;i<m;i++) /*清空队列
{ b[i].f=-1;
b[i].e=-1;
}
while(p!=-1) /*按关键字第j个分量进行分配
{ k=r[p].key[j];
if(b[k].f==-1)
b[k].p; /*对列为空时，将 r[p]链到队列头部
else
r[b[k].e].next=p; /*否则对列非空将r[p]链到队尾
b[k].e=p; /*修改对列的尾指针
p=r[p].next; /*扫描下一个记录
}
i=0;
While(b[i].f== -1) /*检索第一个非空队列
i++;
t=b[i].e;
p=b[i].f /p为收集链表的头指针
while(i<m-1) /*检索下一个队列
{ i++;
if(b[i].f!=-1) /*队列非空时,链接
{ r[t].next=b[i].f;
t=b[i].e;
r[t].next=-1; /*本趟收集完毕,将链表的终端结点指针置空 }
return p;
}
题目三 堆排序算法
[基本要求]
写出在含有n个元素的堆中增加一个元素，且调整为堆的算法程序。
[算法提示]
由于堆可看成一棵完全二叉树，所以可以用一个数组r[1]至r[n+1]表示一个堆。其中r[1]到r[n]表示原始堆中的各个元素，r[n+1]用于存放新插入的元素。由于原来的n个元素已经构成堆，则当插入一个元素时，有可能破坏堆的结构，所以需依据情况进行调整，此时仅需要从r[n+1]出发，走一条从叶子结点r[n+1]到根结点r[1]的路径（设为小根堆）。每次就该结点r[j]和其双亲结点r[i]进行比较，若r[j].key>r[i].key，此时算法结束，不需要进行调整；此时r[1]到r[n+1]即成为堆，否则，将r[i]与r[j]进行交换，继续和上一层结点比较，直到根结点为止。
[算法实现]
#define n 15
#define datatype int
typedef struct
{ int key; /*关键字域
datatype other; /*其它域
} rectlype;
rectype r[n];
/*在堆r[1]到r[n]中插入一个新元素
heapinsert(r,x)
rectype r[ ];
datatype x;
{ int i,j;
j=n+1;
while(j>1)
{ i=j/2; /*求结点kj的双亲结点ki
if(r[i].key<x.key) /*若此时为堆跳出循环
j=1;
else
{ r[j]=r[i];
j=i;
} /*不为堆，再调整
}
r[i]=x; /*x插入正确的插入位置
}
/*主程序
main()
{ int n,i;
datatype x;
for(i=1;i<=n;i++)
{ scanf(“%d”,r[i]);
printf(“%d”,r[i]);
}
scanf(“%d”,&x);
heapinsert(r,x);
for(i=1;i<=n+1;i++)
printf(“&d”,r[i]);
}
题目四 字符串排序算法
[基本要求]
输入若干国家名称，按字典顺序将这些国家进行排序（设所有的名称均用大写或小写表示）。
[算法提示]
本题实质是对一些字符串进行排序，可以用直接选择排序或shell排序等，这里shell采用排序。Shell排序又称“缩小增量排序”。它的做法是：先取一个小于n的整数d１作为第一个增量，把文件的全部记录分成d1个组，所有距离为d1倍数的记录放在同一个组中，在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述分组和排序，直至所取得增量dt=1(dt<dt-1…<d1)，即所有记录放在同一组中进行直接插入排序为止。
[算法实现]
/*按字典顺序将这些国家进行排序
main()
{ string r[ ];
string temp;
int i,h,n,change;
scanf(“%d”,&n);
printf(“input country name\n”);
for(i=0;i<n;i++)
scanf (r[i]);
h=n;
while(h>0)
{ h=h/2; /*取增量h/2
do
{ change=false;
for(i=0;i<n-h;i++)
if(r[i]>r[i+h]) /*比较r[i]与r[i+h]
｛ temp=r[i]; /*交换
r[i]=r[i+h];
r[i+h]=temp;
change=true; /*置已交换标志
}
} while(!change);
}
printf(“output country name\n”);
for(i=0;i<n;i++)
printf(r[i]);
}
综合实验题目一 索引文件系统的使用操作
[基本要求]
假定一个以ElemType为记录类型的主文件存于D：盘LL子目录的test1.data文件中，他的索引文件存于同一目录下的test1.idx中。索引文件中的每个索引项对应主文件中的一个记录，每个记录项包含两个域：一是索引值域，又称关键字域（key），用来存储对应记录的关键字；二是记录位置域（next），用来存储对应记录在主文件的位置编号，若若主文件中包含n个记录，则next域的取值范围在0 ~ n-1之间。另外，主文件中记录的排列次序可以任意排列，即不强求按关键字有序，而索引文件是按关键字从小到大排列的有序文件。在这种带有主文件和索引文件的整个文件系统中当向主文件的末尾插入一条记录后，还要把它的索引项插入到索引文件中；当删除一条记录时，首先从索引文件中删除掉对应的索引项，然后把主文件中的被删除的记录的关键字域置为特定的值以作为删除标记即可，而不需要真正从物理上删除它；当查找一条记录时，是先查找索引文件得到对应的索引项，然后根据索引项中所含的记录位置从主文件中取出记录。由此可知，对这种文件系统的操作主要开销在对索引文件的操作上。试按照下列每一项功能编写出相应的算法程序：
向索引文件中插入一条记录的索引项（在文件系统中插入记录）；
从索引文件中删除一条记录的索引项（在文件系统中删除记录）；
从索引文件中二分查找一条记录的索引项（在文件系统中查找记录）；
[算法提示]
有题意可知，索引文件是有序文件，对索引文件的插入和删除操作都是在有序文件上进行的，操作后仍是有序文件。按二进制方式使用的文件，每次存取一个数据块的信息，一个数据块可以包含一个或若干个记录。一个数据块通常小于等于外存上的一个物理块，而一个物理块的大小通常为210即1024个字节，他是进行一次外存访问操作的信息交换单位。当从有序文件中顺序查找一个记录的插入或删除位置时，不是使每个记录的关键字同给定关键字进行比较，而是使每个数据块中的最大关键字（即该块中最后一个记录的关键字）同给定关键字进行比较，若前者小于后者，则继续访问下一个数据块并比较，否则。待插入或删除的位置必然落在本块中。
假定主文件test1.dat中记录的类型ElemType可定义为：
struct ElemType { //主文件中的记录类型
KeyType key; //关键字域
int rest; //其它域，假设用整形rest表示
}
索引文件test1.idx中类型可定义为：
struct IndexItem { //索引文件中的记录类型
KeyType key; //关键字域
int next; //保存对应记录的存储位置域
}
而关键字的类型KeyType可事先通过typedef语句定义为整形：
typedef int KeyType;
一个数据块中所含的索引项个数m和每个索引项的大小b可分别用下面语句定义为全局变量：
const int m=100; //m可定义为大于等于1的任意整数
const int b=sizeof(IndexItem); //保存索引文件中的记录长度以上定义仅供参考，其它算法（略）
题目二 散列文件的使用操作
[基本要求]
在外存磁盘上建立一个散列文件，按照下列功能编写出相应算法：
初始化散列文件；
向散列文件中插入一个元素；
向散列文件中一次插入n个元素；
从散列文件中删除一个元素；
从散列文件中查找一个元素。
[算法提示]
散列存储方式不仅适用与内存，也同样适用于外存，即文件也可以采用散列方式存储，以散列方式存储的文件称为散列文件。散列文件通常采用链接法处理冲突，并且把保存每个单链表表头指针的表头向量用一个文件单独存储起来，称此为散列表文件，把所有单链表中的结点用一个文件单独存储起来，称此为散列主文件。散列主文件中每个结点的类型可定义为：
struct FLNode { //散列主文件中的结点类型
ElemType data; //值域
int next; 指向下一个结点的指针域
}
其中data域用来存储待散列的元素，next域用来存储下一个同义词元素在散列主文件中的存储位置，即所在结点的位置序号。散列主文件中第一个结点的位置序号为0，字节地址为0，第二个结点的位置序号为1，字节地址为sizeof (FLNode)，第三个结点的位置序号为2，字节地址为2* sizeof (FLNode)，依次类推。当一个结点为同义词单链表中的最后一个结点时，则next域为空，假定用数值-1表示。
散列表文件中、每一个结点的类型为整形int，每个结点的值为指定对应单链表的第一个结点的位置序号。若相应的单链表不存在，则该结点的值为空，同样用数值-1表示。散列表文件中每个结点的初始值均为-1。
初始化散列表文件时，首先按输出方式打开并建立散列表文件和散列主文件，接着动态分配一个具有m+1个整数位置的数组空间A，然后把A中的每个元素君置为-1，表示空指针，最后把数组内容写入散列表文件即可。
向散列文件中插入一个元素x时，首先根据元素的关键字x.key，散列表长度m和所选择的任一散列函数计算出散列地址d，接着为x生成一个内存结点，并使该结点的next域为散列表文件中位置d的元素值（即表头指针），然后把该内存结点的值写入到散列主文件的一个空闲结点中，若不存在空闲结点则写入到该文件的末尾，最后把该结点在散列主文件中的序列赋给散列表文件中位置d的元素中，使得新插入的结点被链接到散列地址为d的单链表的表头。
向散列文件中一次插入n个元素的操作，是上述插入一个元素过程的重复，当然算法开始时的打开文件和结束时的关闭文件是不需要重复的。
从散列文件中删除一个关键字为x.key的元素时，首先是计算出散列地址d，接着从散列表文件中下标为d的位置取出对应单链表的表头指针，然后遍历该单链表从中查找出关键字为x.key的结点，并从单链表中删除该结点，其元素值由x带回，最后把被删除的结点链接到空闲结点表的表头。假定空闲结点表的表头指针保存在散列表文件中下标为m的位置，若该位置为-1，则表明散列主文件中不存在空闲结点。
从散列文件中查找一个关键字为x.key的元素时，同样是首先计算出散列地址d，接着从散列表文件中下标为d的位置取出对应单链表的表头指针，然后从单链表中顺序查找出对应的元素并由x带回。
主要全局类型和常量说明：
const int m=13; //定义散列表长度，其值取决于待散列的元素数量和选取的装填因子(的大小。
Typedef int KeyType; //定义关键字类型
Struct ElemType { //元素类型
KeyType key; //关键字域
int rest; //其它域
}；
Struct FLNode; { //索引主文件中的结点类型
ElemType data; //值域
int next; //指向下一个结点的指针域
}；
const int b1=sizeof(int); //保存索引表文件中的记录长度
const int b2=sizeof(FLNode);//保存索引主文件中的记录长度以上定义仅供参考，其它算法（略）
Turbo C是一个集程序编辑、编译、连接、调试为一体的C语言程序开发软件，具有速度快、效率高、功能强等特点，使用非常方便，C语言程序员可在Turbo C环境下进行全屏幕编辑，利用窗口功能进行编译、连接、调试、运行、环境设置等工作。
要求的配置
Turbo C 可以在IBM PC在系列机上运行（包括XT、AT、PS/2、286、386等及其兼容机），要求2.0或更高版本的DOS以及至少448KB的 RAM，监视器应为80系列。
2、安装
Turbo C系统有一安装程序INISTALL，其运行过程如下：
将标签为INSTALLATION DISK 的软盘插入A盘驱动器：
键入A,<br>
键入INSTALL <br>
这时只要遵循INSTALL显示在屏幕上的指示进行操作即可。INSTALL运行以后，就可使用Turbo C了。
3、使用
（1）、进入 Turbo C
如果使用INSTALL安装程序安装好了Turbo C,那么Turbo C以存在TC主目录下，可以用：
CD/TC <br> 或 CD TC <br>
进入该目录。然后在DOS命令行上键入“TC”并按回车键。这时就进入Turbo C，屏幕上将显示出如下的Turbo C主菜单窗口。
File Edit Run Complie Project Options Debug Break/Watch
如果不是在TC主目录内调用Turbo C，而是在另一个目录下想使用Turbo C，则应该指出目录路径，在DOS 3。0以上版本中，可以在命令行中使用包括目录路径的文件全名。如：用户希望将文件存于\USER目录后，则在进入USER目录后在命令行上输入\CD\TC，即可进入TC目录并调用Turbo C，用户编辑的源文件将存在于USER下。
（2）、工作目录工作目录指用户文件所在的目录。用户进入TC目录后，可以在这个目录下再建立一个用户专用的子目录。用户可以在此目录下进入文件的编辑工作，编译生成的目标文件也存放在此子目录中。这个工作目录可由用户自己建立，再由Change dir命令来告诉Turbo C你所选定的工作目录，方法见下述。
前以述及，在进入Turbo C后，屏幕上显示出一个Turbo C主菜单窗口。这时可以用F10键和光标移动键来从主菜单中选择所需的功能。步骤如下：先按下F10键，可看到屏幕上部的某一位置会出现亮块，如果亮块不在FILE处，表示准备选择,FILE”类 操作，即文件操作，也可不用F10键，而直接按ALT键和”f”键（同时），使亮块位于“FILE”处。亮块移动到“FILE”处后，按以下回车键，在“FILE”下方会出现一个子窗口如下图。
File edit run compile project options debug break/watch
Load F3
Pick ALT-F3
New
Save F2
Write to
Directory
Change dir
Os shell
Quit ALT-X
子窗口也有一个亮块，可以用“↑”、“↓”键，将此亮块移动到Change dir 处，或者直接按下“C”键，来选择change dir操作;输入键“↙”后，将会出现一目录提示框，提示用户输入所选择的目录名，用户输入后，再按下“↙”键即可。
如：屏幕显示输入提示：
newdirectory
C:\tc
用户输入“\usr”。
Newdirectory
C:\tc\usr
如果当前不存在此目录，则显示错误信息，可再次输入合法目录名。
（3）、建立工作环境即告诉TC:包括文件和库文件在什么地方：输出文件存在于何出。可用主菜单上“option项”来进行。步骤如下：
File edit run complie project option debug break/watch
在“option”位置上以后，按回车键。此时在位置下面出现一个子窗口，如下：
File edit run compile project options debug break/watch
Compiler
Linker
Environment
Directores
Arguments
Save options
Retrieve options
用光标移动健将亮条移动到“Directories”处，按回车键后，又将出现一个子窗口，如下图：
Include directories:c:\Turbo C\include
Licrary directories:c:\Turbo C\lib
Output directory,
Turbo C directory:
Pick file name,
Current pick file:
将亮条移至“include directories”出并按回车键，然后输入包括文件所在的盘符和路径。如输入：
c:\Turbo C\include ; c;\Turbo C\include \sys
表示：包含文件放在C盘上的\Turbo C\include 子目录和\Turbo C \include \sys子目录中。
包含文件的所在目录输入后，再将亮条移到“library directories”处，按回车键。输入库函数的盘符和目录名
c:\Turbo C \lib
这就告诉Turbo C:库函数的目录
（4）、编辑源文件在主菜单状态下，将亮块移到左上角“FILE”处，按回车，选择“load”出现：
load file name
用户可在输入要编辑的文件名，按回车即可。
如果记不清所编辑的源文件名，想看一下当前目录中有哪些源文件，可以在子窗口出现上述“*.C”时直接按回车键。Turbo C就回显示出当前目录下的所有后缀为“.C”的文件名，利用光标键时将亮度条移到需要编辑的文件名处，按回车键，该输入文件内容即显示在屏幕上，供用户编辑、修改。
如果用户用“load”输入的文件名是已存在的文件，则这时屏幕上将显示出文件内容，可供修改；否则屏幕上是一片空白，表示文件无内容（是新文件），用户可以从键盘输入文件内容。在编辑过程中除用到个字符键外还可以用到“Ins”键和“Del”键，“Ins”键是一个切换键，用来控制工作状态是否处于“插入状态”。按下,Ins”键后，可以看到在屏幕编辑窗口的上方状态行上有一个英文单词“INSERT”，这时从键盘输入的字符（包括控制字符，如“回车”）会插入到屏幕当前光标处，光标后的字符会自动顺序后移。如果再按一下“Ins”键，则取消插入状态，状态行上的“INSERT”单词消失。此后键入的字符将覆盖（而不是插入）光标处的字符，Turbo C设置的初始状态是“插入状态”，第一次按“Ins”键改成“覆盖状态”，再按“Ins”键，则又改成“插入状态”，如此反复切换。“Del”键是删除光标所在的字符。“Ctrl”键和“Y”键同时按下可删除光标所在的一行，“Ctrl”键盘和“N”键盘可用来插入一行。
编辑完成后，可从“File”菜单中选择“save”命令（即将亮条移至Save处后，再按回车键）将文件存盘，也可直接按下F2键，将文件存盘。
（5）、编译、连接加工程序时，先编译源代码，生成目标文件（扩展名为。OBJ），然后将目标文件进行连接生成可执行文件（扩展名为。EXE）。
对单文件程序的编译、连接的方法是在将文件存盘后，按F10键，将亮条移至Compile处按回车键，也可直接按Alt-C即可产生一个子窗口如下图：
File edit run compile project options debug break/watch
表示编译后生成 a.obj 文件，连接后生成 a.exe 文件，源文件名设定为 a.c 将亮条移至Make EXE File处（也可以直接按住F9键），则TC将对文件进行编译、链结并生成运行文件。
若文件有错，则在屏幕底部的“Message”窗口显示出错及警告信息。这时可进行修改。该完后在重复进行编译、链结。
另外，TC的最显著特点之一是能进行分别编译，可以把一个长的文件分别编辑在多个文件中，分别编译。Turbo C提供了一个工具，可直接将这些文件编译连接后生成一个完整的运行程序，而不必由用户显示在分别编译连接。这个工具就是Project菜单项，使用步骤如下：
假设有两个文件组成一个程序，首先要生成两个源文件（如File1.c和File2.c）。
构造Project文件，在编辑状态下，编辑一个后缀名为PRJ的文件（文件名可由用户选择，如：MYPROJECT.PRJ）此文件内容如下,
file1
file2
后缀.C可要可不要，而且File1、File2顺序无所谓。当File1.c，File2.c不在一个目录中时，可在project文件MYPROJECT.PRJ中给出各自的路径，例如文件内容可为：
\Turbo C\USER\File1
\ Turbo C\File2
在主菜单窗口中选择project功能项，即将亮条移至project处回车（也可按Alt+P键得到），此时得到如下子窗口。
File edit run compile project options debug break/watch
Project name
Break make on Errors
Auto depentlents off
Clear project
Remove messages
将亮条移到“Project name”处，按回车键输入后，输入project文件名（如MYPROG.PRJ）并回车。然后按F9键即产生相应的可执行文件。此时运行文件名及为用户给出的project文件名（如MYPROG.EXE），运行时可用下述的RUN命令，也可在操作命令状态下直接输入运行文件名（如MYPROG）。
停止编辑的方式。如果同时编辑的几个程序中有错，就须停止编译，由用户进行修改。用户可以指定两种方式停止编译。
A、用户希望同时编译的几个文件中同时出现一个错误时，就停止编译，可用如下方法：将Project菜单中的亮条移到“Break Make On”处，回车后可出现一个子窗口，如下图：
Warnings
Errors
Fatal errors
Link
将亮条移至Errors或Warnings处，回车后，在Break Make On 右边及出现此选项，如图：
Break Make On Errors
这时，当编译的几个文件只要出现一个错误时，就立即停止编辑，亮条停在出错处，指示用户进行修改。
望所有文件的所有错误都找出以后，在修改错误，可用以下方法：
在”break make on”子窗口中，将亮条移至fatal errors或link处，此时:break make on右边出现的是fatal errors 或link。这样，在编译出现错误后，才停止编译，用户这时在修改源文件。
（6）、运行编译链结完成一个文件后，可利用主菜单的“run”命令或直接使用ctrl +F9来运行程序。其实当用户认为自己的源程序不会有编译，链结错误时，在源程序编译完成后，可以直接用“run”命令或直接按crtl+F9键，这时它会一次完成编译链结到运行的全过程。
程序运行后，仍回到tc屏，这时若想看运行结果，可以用“run”菜单的“user screen”命令，也可直接按alt+F5键，转到用户屏。
File edit run compile project options debug break/watch
Run ctrl+F9
Program reset ctrl+f2
Go to cursor f4
Trace into f7
Step over f8
User screen alt+F5
看完后，按任意键回到TC屏。
关于Turbo C的更详细的信息，请参阅Turbo C手册，或使用F1帮助联机系统。
实验一 线性表一、实验目的
1、掌握用C语言上机调试线性表的基本方法。
2、掌握线性表基本操作，插入、删除、查找，以及线性表合并等运算在顺序存储结构和链接存储结构上的运算。
二、实验内容题目一 线性表基本操作的实现
[问题描述]
当我们要在线性表的顺序存储结构上的第i个位置上插入一个元素时，必须先将线性表中第i个元素之后的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到该位置。若欲删除第i个元素时，也必须把第i元素之后的所以元素前移一个位置。
[基本要求]
要求生成线性表时，可以键盘输入读取元素，用顺序存储结构和链式存储结构实现存储。
[实现提示]
要实现基本操作可用已实现的基本操作，也可设计简单的算法实现
[算法实现]
typedef null 0;
typedef int datatype;
#define maxsize 1024;
typedef struct
{ datatype data[maxsize]; /*定义线性表是向量，第一结点是data[0]*/
int last;
}sequenlist;
/*插入函数*/
int insert(L,x,i) /*将新结点x插入到顺序表l第i个位置
sequenlist *L; /*l是sequenlist类型的指针变量
int i;
{ int j;
if （（*l）.last==maxsize-1）
{ printif(“overflow”);
return null;}
else
if((i<1)||(i>(*l).last+1)
{ printf(“error”);
return null;}
else
{ for(j=（*l）.last;j>=i-1;j--)
(*l).data[j+1](*l).data[j]; /*结点后移
(*l).data[i-1]=x; /*?插入x
(*l).last+1; } /*表长加一
return (1);
}
/*删除运算
int delete(L,i)/*删除第i个结点
sequenlist *L;
int i;
{ int j;
if((i<1)||(i>(*L).last+1)
{ printf(“error”);
return null; }
else
{ for (j=i;j<=(*L).last;j++)
(*l).data[j-1]=(*L).data[j];
(*L).last--; }
return (1);
}
/*生成线性表
void ceatlist()
{ sequentlist *L;
int n,i,j;
printf(“请输入n个数据\n”)；
scanf(“%d”,&n);
for(i=0,i<n,i+);
{ printf(“data[%d]=”,i);
scanf(“%d”&(*L).&data[i]);
}
(*L).last=n-1;
printf(“”\n”);
}
/*输出线性表
printout(L)
sequenlist *L;
{ int i;
for(i=0;i<(*L).last;i++)
{ printf(“data[%d]=”,i);
printf(“%d”,(*L).data[i]);
}
}
/*主程序开始
main()
{ sequenlist *L;
char cmd’
int i,t;
clscr();
printf(“i I ： 插入元素\n”);
printf(“d D ： 删除元素\n”);
printf(“q Q, 退出元素\n”);
do
{ do
{ do{cmd=getchar();
}while((cmd!=’d’)||(cmd!=’D’)||(cmd!=’q’)||(cmd!=’Q’)||(cmd!=’i’)||(cmd!=I));
switch(cmd)
{ case ‘i’,’I’,scanf(&i);
insert(L,i);
printout(L);
break;
case ‘d’,’D’,scanf(&i);
delete(L,i);
printout(L);
break;
}
}while((cmd!=’q’||(cmd!=’D’));
}
题目二 约瑟夫问题求解
[问题描述]
设有n个人围坐一圈，现从某个人开始报数，数到m的人出列，接着从出列的下一个人开始重新报数，数到的M人又出列，如此下去，直到所有的人出列为止，试设计确定他们的出列次序序列的程序。
[基本要求]
选择单向循环链表作为存储结构模拟整个过程，并依次输出出列的各人的编号。
[实现提示]
程序运行之后，首先要求用户指定初始报数的上限值，可以n<=30，此题中循环链表可不设头结点，而且必须注意空表和非空表的界限。如：n=8，m=4时，若从第一个人开始，设每个人的编号依次1、2、3、4…开始报数，则得到的出列次序为4 8 5 2 1 3 7 6。
[程序实现]：
struct node
{ int num;
struct node *next;
} linklist;
/*建立链表
linklist *creat(head,n)/使n个人围成一圈,并给每个人标志号数
linklist *head
int n;
{ linklist *s,*p;
int i;
s=malloc(sizeof(linklist));
head=s;
s->num=1;
p=s;
for(i=2;i<=n;i++);
{ s=malloc(sizeof(linklist));
s->num=i;
p->next=s;
p=s;
}
p->next=head;
return head;
}
linklist *select(head,m)
linklist *head;
int m;
{ linklist *p,*q;
int i,t;
p=head;t=1;
p=q; /*q为p的前驱指针
do{
p=q->next; /*指向当前报数的人
t=t+1;
if(t%m==0)
{
printf(“%4d”,p->num);
q->next=p->next;
free(p);
p=q;
}
else
p=q;
} while(p==q);
head=p;
}
/*主程序
main()
{ int n,m;
linklist *head;
scanf(&n);
scanf(&m);
creat(head,n);
select(head,m);
printf(“the last one:is%d”,head-num);
}
题目三 一元多项式简单计算
[问题描述]
设计一个一元多项式的简单计算器
[基本要求]
一元多项式简单计算器的基本功能为：
输入并建立多项式输出多项式两个多项式相加减，相乘除，建立并输出多项式
[实现提示]
可选择带头结点的单向循环链表或单链表存储多项式，头结点可以存储多项式的参数如项数等。
[程序实现]
这里利用单链表作为存储多项式的结构：单链表定义如下,#define null 0
#define true 1
#define false 0
struct mulpoly
{ int coef ;/*系数
int exp; /*指数
struct mulpoly next; }
假设输入一组多项式的系数和指数，以输入实数0为结束标记，这里建立多项式时，总是按指数从大到小排列。
/*产生多项式链表，设头指针为head
struct mulpoly creatpoly()
{ struct mulpoly *head,*r,*s;
int m,n;
head =(struct mulpoly *)malloc(sizeof(struct mulpoly));
scanf(“%d,%d”&n,&m)；
r=head;
while(n) /*n不等于0时建立多项式链表
{ s=(struct mulpoly )malloc(sizeof(struct mulpoly));
/*建立一个新结点
s->coef=n;
s->exp=m;
r->next=s; /*把*S链接到*R后面
r=s;
printf(“input coef and exp:\n”);
scanf(“%d,%d”,&n,&m);
}
r->next=null;
head=head->next;
return (head);
}
/*a+b实现多项式相加：
/*两多项式相加运算ha hb 分别是A、B链表的头指针,相加后存放到多项式C，头指针为hc
struct mulpoly polyadd(ha,hb)
struct mulpoly *ha,*hb;
{ struct mulpoly *hc,*p,*q,*s,*r;
int x;
p=ha;
q=hb;
hc=(struct mulpoly *)malloc(sizeof(struct *mulpoly));
s=hc;
while((p!=null)&&(q!=null))
{if(p->ext==q->ext) /*两个结点指数相等
{ x=p->coef+q->coef; /*系数相加
if(x!=0)
{r=(struct mulpoly *)malloc(sizeof(struct *mulpoly));
r->exp=p->exp;
r->coef=x;
s->next=r;
s=r; }
p=p->next;
q=q->next;
}
else/*两结点指数不相等
if(p->next<q->next)
{ r=(struct mulpoly *)malloc(sizeof(struct *mulpoly));
r->exp=p->exp;
r->coef=p->coef;
s->next=r;
s=r;
p=p->next;
}
else /* p->next>q->next时
{ r=(struct mulpoly *)malloc(sizeof(struct *mulpoly));
r->exp=q->exp;
r->coef=q->coef;
s->next=r;
s=r;
q=q->next;
}
}
while(p) /* p!=NULL复制A的剩余部分
{ r=(struct mulpoly *)malloc(sizeof(struct *mulpoly));
r->exp=p->exp;
r->coef=p->coef;
s->next=r;
s=r;
p=p->next;
}
while(q) /* q!=NULL复制B的剩余部分
{ r=(struct mulpoly *)malloc(sizeof(struct *mulpoly));
r->exp=q->exp;
r->coef=q->coef;
s->next=r;
s=r;
q=q->next;
}
s->next=null; /*链成单链表
r=hc;
hc=hc->next;
free ( r );
return(hc);
}
相减运算，实际上也是多项式相加的运算，无非是各项的系数符号不等而已。而多项式的乘法运算可说明如下。
/*多项式相乘
struct mulpoly * polymulti(f,g)
struct mulpoly *f,*g;
{ mulpoly *fp,*gp,*q,*h;
int maxp,p,r,x;
extern reverse(mulpoly *p);
maxp=f->exp+q->exp;
h=(struct mulpoly *)malloc(sizeof(struct *mulpoly));
hp=h;
reverse(g);
for(r=maxp;r>=0;r--)
{ x=0;fp=f;gp=g;
while((fq!=null)&&(gp!=null))
{ p=fp->exp=gp->exp;
if(p>r)
fp=fp->next;
else
if(p<r)
gp=gp->next;
else
{ x+=fp->coef*gp->coef;
fp=fp->next;
gp=gp->next; }
} /* end of while
if (abs(x)>le-6)
{ p=(struct mulpoly *)malloc(sizeof(struct *mulpoly));
q->exp=r;
q->coef=x;
q(next=null;
hp->next=q;
hp=q;
}
} /* end of for
hp=h;
h=h->next;
free(hp);
return h;
}
其中的reverse函数说明如下
reverse(q)
mulpoly *q;
{ mulpoly *p1,*p2;
if(q!=null)
{ p1=q->next;
q->next=null;
while(p1!=null)
{ p2=p1->next;
p1->next=q;
q=p1;
p1=p2;
}
}
多项式的输出的输出，实际上就是单链表的输出，只是该单链表的数据域含有系数和指示两部分而已。
/*多项式的输出
ployout(head)
mulpoly *head;
{ mulploy *p,*q ;
p=head->next;
while(p!=NULL)
{ printf(“%d,%d”,p->coef,p->exp);
p=p->next;
}
}
整个实现的主程序如下：
void main()
{ mulpoly *ha,*hb,*hc,*p,*q,*h;
ha=creatpoly();
polyout(ha);
hb=creatpoly();
polyout(hb);
hc=polyadd(ha,hb)’;
polyout(hc);
h=polymulti(ha,hb);
polyout(hc);
}
实验二 栈和队列一,实验目的
1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际背景下灵活运用。
握栈和队列的特点，即先进后出与先进先出的原则。
3、栈和队列的基本运算，如入栈和出栈、入队与出队等运算在顺序存储结构和链式存储结构上的实现。
二、实验内容题目一 表达式求值算法
[问题描述]
表达式求值是程序设计语言编译中的一个基本算法。他的实现是栈应用的一个典型例子。这里采用较为流行的“算符优先法”来实现对表达式的求值。要把一个表达式翻译成正确求值的一个机器指令序列，或者是直接对表达式求值，首先要能够正确解释表达式。那么就要了解算术四则运算的基本规则：
1）先乘除，后加减；
2）从左算到右；
4）先括号内，后括号外。
例如表达式：4+2*3-10/5的计算顺序为：
4+2*3–10/5=4+6–10/5=10–10/5=10–2=8
算符优先法就是根据这个运算优先关系的规则来实现对表达式的编译或解释执行的。
[基本要求]
要求能根据算符优先法则对所输入的四则运算表达进行求值。
[实现提示]
任何表达式都由操作数、运算符、定界符组成，我们把运算符和定界符统称为算符。它们构成的集合命名为OP，根据运算法则在每一步中，任意两个算符优先级关系可以由下表来描述:
其中， Q1<Q2 Q1的优先级低于Q2
Q1=Q2 Q1的优先级等于Q2
Q1>Q2 Q1的优先级高于Q2
“#”号表示表达式的开始与结束。
该表可以采用二维表表示，由先后两算符的序号做下标定位两者的优先级，如“*”的序号为2，“+”的序号为1，则“*”与“+”相遇OP[2，1]得到“>”所以“*”的优先级高。
[程序实现]
算法思想为了实现算符优先算法，可以使用两个工作栈，一个是操作数栈OPDS，另一个是运算符栈OPS，分别存放操作数与算符。首先将标志“#”进运算符栈OPS的底，按照栈后进先出的原则进行：
遇到操作数，进操作数栈，计算机继续扫描下一符号；
遇到运算符时，需要将此算符的优先级与OPS栈顶算符优先级比较。
若优先级比站顶元素高，则进OPS栈，继续扫描下一符号；
若优先级比站顶元素低，则运算符优先级比站顶元素OPS栈顶元素退栈形成一个操作码Q；同时，操作数栈OPDS两次退栈，形成两个操作数a,b.计算机对操作数与操作码完成一次运算操作，即aQb.其运算结果存放在操作数OPDS栈，作为一次运算的中间结果进OPDS栈。
若与栈OPS栈顶元素优先级相等，则栈顶元素退栈。当遇到栈顶元素是“#”时，表示整个运算结果，否则，继续扫描下一个符号。
程序实现
/* 初始化*/
#define FALSE 0
#define TRUE 1
#define MAX 10
#include <stdio.h>
#include <stdlib.h>
void push_opds(); /*push opds stack.*/
float pop_opds(); /*pop opds stack.*/
void push_ops(); /*push ops stack.*/
float pop_ops(); /*pop ops stack.*/
char relation(); /*>,<,=*/
float operate(); /*+,-,*,/*/
float opds[MAX]; /*operand's stack */
int ops[MAX]; /*operator's stack */
int topd=0; /*opds's top*/
int top=0; /*opd's top*/
char symb;
/*主函数，表达式求值
void main()
{
char sy;
char ch;
float a,b;
printf("\n Please input expression(# end):\n");
push_ops('#');
symb=getchar();
while ((symb!='#')||((char)(ops[top])!='#'))
{
if((symb!='+')&&(symb!='-')&&(symb!='*')&&(symb!='/')&&(symb!='(')&&(symb!=')')&&(symb!='#')&&(symb!=' '))
{ /*不是算符，则是操作数进OPDS栈
push_opds(symb);
symb=getchar();
}
else
{ /*是算符，先比较优先级，在分情况处理
ch=relation((char)(ops[top]),symb);
switch(ch)
{
case '<':
push_ops(symb);
symb=getchar();
break;
case '=':
sy=pop_ops();
symb=getchar();
break;
case '>':
sy=pop_ops();
b=pop_opds();
a=pop_opds();
topd=topd+1; /*push_opds stack*/
opds[topd]=operate(a,sy,b);
break;
case ' ':
printf("error\n");
break;
}
}
}
printf("\nThe result=%1.2f\n",opds[topd]);
getch();
}
/*操作数压栈
void push_opds(ch)
char ch;
{
int ch_i;
if (topd==MAX-1)
printf("the opds stack is overflow.\n");
else
{
ch_i=ch-'0'; /*将字符转化为“值”：“3”转为3
topd++;
opds[topd]=ch_i;
}
}
/*操作数弹栈
float pop_opds()
{
topd=topd-1;
return(opds[topd+1]);
}
/*操作符压栈
void push_ops(ch)
char ch;
{ if (top==MAX-1)
printf("the ops stack is overflow.\n");
else
{
top++;
ops[top]=(int)(ch);
}
}
/*操作符弹栈
float pop_ops()
{
top=top-1;
return((char)(ops[top+1]));
}
/*比较两个算符sym1,sym2的优先关系
char relation(sym1,sym2)
char sym1,sym2;
{
int i;
char chl[2];
int ind[2];
char re[7][7]={ {'>','>','<','<','<','>','>'},
{'>','>','<','<','<','>','>'},
{'>','>','>','>','<','>','>'},
{'>','>','>','>','<','>','>'},
{'<','<','<','<','<','=',' '},
{'>','>','>','>',' ','>','>'},
{'<','<','<','<','<',' ','='}};
chl[0]=sym1;
chl[1]=sym2;
for (i=0;i<=1;i++)
{
switch(chl[i])
{
case '+',ind[i]=0;break;
case '-',ind[i]=1;break;
case '*',ind[i]=2;break;
case '/',ind[i]=3;break;
case '(',ind[i]=4;break;
case ')',ind[i]=5;break;
case '#',ind[i]=6;break;
default:printf("error\n");return('0');
}
}
return(re[ind[0]][ind[1]]); /*取优先符>、=、<
}
/*执行操作运算
float operate(a,sym,b)
float a,b;
char sym;
{
float re;
switch(sym)
{
case '+':re=a+b;break;
case '-':re=a-b;break;
case '*':re=a*b;break;
case '/':re=a/b;break;
default:printf("error\n");return(0);
}
return(re);
}
题目二 迷宫路径问题
[问题描述]
迷宫实验是取自心理学的一个古典实验。在该实验中，把一只老鼠从一个无顶大盒子的门放入，在盒中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有一个出口，在出口处放一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验，一直到老鼠从入口到出口，而不走错一步。老鼠经多次实验终于得到他学习走通迷宫的路线。设计一个计算机程序对任意设定的迷宫，求出一条入口到出口的通路，或得出没有通路的结论。
[基本要求]
要求程序输出：
（1）、一条通路的二元组（i,j）数据序列，（i,j）表示同路上某一点的坐标。
（2）、用一种标志（如数字8）在二维数组中标出该条通路，并在屏幕上输出二维数组。
[实现提示]
可以利用一个二维数组maze[i][j]表示迷宫，其中1≤i≤m,1≤j≤n。数组元素值为1表示该位置是墙壁，不能通行；元素值为0表示该位置是通路。假定从maze[1][1]出发，出口位于maze[m][n],移动方向可以是8个方向（东，东南，南，西南，西，西北，北和东北）。一个构造的迷宫如下页图：
[算法实现]
设计思想当迷宫采用二维数组表示时，老鼠在迷宫中任一时刻的位置可由数组的行列序号i,j来表示。而从[i][j]位置出发，可能的行进方向见下图1。如果[i][j]周围位置均为0值，则老鼠可以选择这8个维之中的任一个作为它的下一个位置。将这八个方向分别记作：E（东）、SE（东南）、S（南）、SW（西南）、W（西）、NW（西北）、N（北）和NE（东北）。但是并非每一个位置都有8个相邻位置。如果[i][j]位于边界上，即i=1,或i=m,或j=n,则相邻位置可能是5个或3个。为了避免检查边界条件，将数组四周围用值为1的边框包围起来，这样二维数组maze应该声明为maze[m+2][n+2]。
在迷宫中行进时，可能有多个行进方向可供选择，我们可以规定方向搜索的次序是从东（E）沿顺时针方向进行。为了简化问题，规定[i][j]的下一步位置坐标是[x][y]，并将这8个方向上的x和y坐标的增量预先放在一个结构数组move[8]中（见图2）。该数组的每个分量有两个域dx和dy。例如要向东走，只要在j值上加dy,就可以得到下一步位置的[x][y]的值为[i][j+dy]。于是搜索方向的变化只是要令方向值dir从0增加到7，便可以从move数组中得到从[i][j]点出发搜索到的每一个相邻点[x][y]。
x=i+move[dir].dx
y=j+move[dir].dy
为了防止重走原路，我们规定对已经走到过的位置，将原值0改为-1，这既可以区别该位置是否已经走到过，又可以与边界值1相区别。当整个搜索过程结束后，可以将所有的-1该回到0，从而恢复迷宫的原样。
这个计算机走迷宫的算法是：采取一步一步试探的方法。每一步都从东（E）开始，按顺时针方向对8个方向进行探测，如某个方向上的maze[x][y]=0,表示可以通行，则走一步；如maze[x][y]=1,表示此方向上不可通行，须换方向再试，直至8个方向都试过，maze[x][y]均为1，说明此步已无路可走，须退回一步，再上一步的下一个方向上重新探测。为此须设置一个栈，用来记录所走过的位置和方向（i,j,dir）。当退回一步时，就从栈中退回一个元素，以便在上一个位置的下一个方向上探测，如果有找到一个进行方向，这把但前位置核心的方向重新进栈，并走到新的位置。如果有探测到x=m,y=n,则已达到迷宫得出口，可以停止检测，输出存在栈中的路径；若在某一个位置的8个方向上都堵塞，则退回1步，继续探测，如果以退出到迷宫的入口（栈中无元素），则表示此迷宫无路径可通行。
（2）程序实现这里用到一个栈，栈的元素是一个结构。为了方便采用顺序栈。由于数组maze的每一个位置最多被访问一次，所以至多有m*n个元素放入栈中，因此m*n作为栈的容量大小是个安全的值，但也是一个保守的值。一般取m*n/2即可。
# define M2 12 /*M2*N2为实际使用迷宫数组的大小*/
# define N2 11
# define MAXLEN M2 /*栈的长度*/
# define True 1
# define False 0
# define,stdio.h”
int M=M2-w,N=N2-2; /*M*N为迷宫的大小*/
typedef struct /*定义栈元素的类型*/
{int x,y,dir;
}elemtype;
typedef struct /*定义顺序栈*/
{elemtype stack[MAXLEN];
int top;
}sqstktp;
/*定义方向位移数组对于存储坐标增量的方向位移数组move */
struct moved
{int dx,dy;
};
/*初始化迷宫*/
void inimaze(int maze[][N2])
{int i,j,num;
for(i;i<=M;i++)
{ for(j=1;i<=n;j++)
{ num=(800*(j+i)+1500)%327; /*根据M和N值产生迷宫
if((num<150)&&(i!=M||j!=N))
maze[i][j]=1;
else
maze[i][j]=0;
printf(maze[i][j]); /*显示迷宫
}
printf(“\n”);
}
printf(“\n”);
for(i=0,j=0;i<=<M+1;i++) /*设置迷宫的边界
maze[i][j]=1;
for(i=0,j=N+1;i<=M;i++)
maze[i][j]=1;
for(i=0,j=0;j<=N+1;j++)
maze[i][j]=1;
for(i=M+1,j=0;j<=N+1;)
maze[i][j]=1;
}
/*初始化方向位移数组*/
void inmove(struct moved move[])
/*依次为E,SE,S,SW,W,NW,N,NE*/
{ move[0].dx=0;move[0].dy=1;
move[1].dx=1;move[1].dy=1;
move[2].dx=1;move[2].dy=0;
move[3].dx=1;move[3].dy=-1;
move[4].dx=0;move[4].dy=-1;
move[5].dx=-1;move[5].dy=-1;
move[6].dx=-1;move[6].dy=0;
move[7].dx=-1;move[7].dy=1;
} /*inimove*/
/*初始化栈*/
void inistack(sqstktp *s)
{ s->top=-1;
}/*inistack*/
/*数据元素x入指针s所指的栈*/
int push(sqstktp *s,elemtype x)
{ if (s->top= =MAXLEN-1) /*栈满，返回False */
return(False);
else
{ s->stack[++s->top]=x; /*栈不满，执行入栈操作*/
return(Ture); }
} /*push*/
/*栈顶元素出栈*/
elemtype pop(sqstktp *s)
{ elemtype elem;
if (s->top<0) /*如果栈空，返回空值*/
{ elem.x =Null;
elem.y =Null;
elem.dir =Null;
return(elem); }
else
{ s->top- -;
return(s->stack[s->top+1]); /*返回栈顶元素*/
}
}/*pop*/
/*寻找迷宫中的一条通路*/
void path(int maze[ ][N2],struct moved move[],sqstktp s*)
{ int i,j,dir,x,y,f;
elemtype elem;
i=1;j=1;dir=0;
maze[1][1]=-1; /*设[1][1]为入口处*/
/*循环，直到入口处或出口处为止*/
do
{ x=i+move[dir].dx; /*求下一步可行的到达点的坐标*/
y=j+move[dir].dy;
if (maze[x][y]= =0)
{ elem.x=i;elem.y=j;elem.dir=dir;
f=push(s,elem); /*如果可行，将此点数据入栈*/
if (f= =False) /*如果入栈操作返回假，说明栈容量不够*/
printf(“栈长度太短\n”);
i=x;j=y;dir=0;maze[x][y]=-1; }
else
if (dir <7) /*如果当前方向不可行，就转到下一个方向*/
dir + +;
else
{ elem=pop(s); /*8个方向都不可行，就退回一步*/
if (elem.x!=Null)
{ i=elem.x;
j=elem.y;
dir=elem.dir+1; }
}
}while (!((s->top= =-1)&&(dir>=7)||(x= =M)&&(y= =N)&&(maze[x][y]==-1)));
/*如果是入口处，则迷宫无通路*/
if (s->top= =-1)
printf(“此迷宫无通路\n”);
else
{ elem.x=x;elem.y=y;elem.dir=dir; /*最后出口的坐标入栈*/
f=push(s,elem);
printf(“迷宫通路是：\n”);
i=0;
/*显示迷宫通道*/
while (i<=s->top)
{ printf(“%d,%d”,s->stack[i].x,s->stack[i].y;
if(i!=s->top)
printf(“-->”);
if((i+1)%4= =0)
printf(“\n”);
i++;
}
printf(“\n”);
}
} /*path*/
/*在迷宫中绘制出通路*/
void draw(int maze[][N2],sqstktp *s)
{ int i,j;
elemtype elem;
for(i=1;i<=M;i++) /*将迷宫中全部的-1值恢复为0值*/
for(j=1;j<=N;j++)
if (maze[i][j]= =-1)
maze [i][j]=0;
/*根据栈中元素的坐标，将通路的各个点的值改为8*/
while (s->top>-1)
{ elem=pop(s);
i=elem.x;j=elem.y;
maze[i][j]=8;
}
for(i=1;it=M;i++)
{ for(j=1;j<=N;j++)
printf(“%3d”,maze[i][j]); /*显示已标记通路的迷宫*/
printf(“\n”);
}
printf(“\n”);
} /*draw*/
/*寻找迷宫通路程序*/
void main( )
{ sqstktp *s;
int maze[M2][N2];
struct moved move[8];
inimaze(maze); /*初始化迷宫数组*/
s=(sqstktp )malloc(sizeof(sqstktp));
inistack(s); /*初始化栈*/
inimove(move); /*初始化方向位移数组*/
path(maze,move,s); /*绘制作出通路标记的迷宫*/
}/*main*/
题目三 迷宫最短路径问题
[问题描述]
在第2题给出的条件基础上，要求设计一个算法，寻找一条从迷宫入口到出口的最短路径。输出信息的要求同第2题。
[设计思想]
一般走迷宫的方法是只要找出一条通路即可，至于这条通路是怎样形成的，并没有关系。由于走迷宫的方法是采用试探法，因此第一步试探的方法非常重要，它决定了通路的可能走向。例如第一步向东走与向东南走，最终形成的通路一般是不一样的。本题是在一般走迷宫的方法上，更进一步要求找出一条最短的路径，而不论起始试探的方位为何。
算法的基本思想是：从迷宫的入口[1][1]出发，向四周搜索，记下所有一步能到达的坐标点p11,p12,……，p1k1(0≤k1≤3);然后依次从p11,……,p1k1出发向四周搜索，几下所有从入口点出发，经过两部可以到达的坐标点p21,……，p2k2(0≤K2≤5);依次进行下去，一直到达迷宫的出口处[m][n]。然后从出口出演搜索路径回溯直至入口点，这样就找到了从入口到出口的一条最短路径。
在本算法中，搜索[i][j]点周围8个方向的坐标点，以决定那些坐标点是可以到达的，方法同上机实习题2。这里只是需要解决搜索路径的保存问题。
在搜索过程中必须记下每一个可到达的坐标点，以便从这些点出发继续向四周搜索。由于先到达的点将作为新的起点先进新搜索，故须采用一个先进先出的队列来保存已到达的坐标点。对于每一个记录下来的坐标点，还需同时保存是从哪一个坐标点出发到达的（该坐标点肯定已在队列中了）。另外搜索结束后，还需从出口向入口回溯，以寻找一条通路，因此尽管采用队列形式，但每一个出发点并不真正离开队列（或者说并不真正从队列中将其删除），只是取其值作为搜索的出发点。这样我们采用一个结构数组queue[]来做该队列的存储空间。因为迷宫中的每一个点至多被访问一次，因此queue[]的容量最大为m*n。queue的每一个元素有三个域：x,y,pre。其中x和y分别记下每一个到达点的行、列坐标，pre则是一个静态链域，他保存到达该点的出发点在queue中的下标。该队列的头尾指针front和rear分别指向实际的队头和队尾元素。例如开始时，队列中只有一个元素，即入口点[1][1]，它的pre域值为0，因为不是从其它出发点到达[1][1]的。front和rear同时指向该元素。此后搜索时，均以front所指的元素作为搜索的出发点，当找到一个可到达点时，将该点的坐标及出发点的下标一起入队。而rear始终指向当前入队列的可到达点元素。假如front所指的点出发搜索完毕，则使front指向下一个新的出发点，继续搜索。一直到找到出口点，或者当前队列为空结束。前者表示成功找到通路，而后者则表示迷宫无通路。
在输出通路时，由于是从队列的队尾（出口）向队头（入口）回溯，得到的结果序列就是从出口到入口。为了保证输出通路是从入口到出口，需将队列中回溯得到的结果先入栈，然后再从栈中输出。
[算法实现]
#define M2 12 /*M2×N2为实际使用的迷宫数组的大小*/
#define N2 11
#define MAXLEN M2*N2/2 /*队列和栈的长度*/
#define Ture 1
#define False 0
#include,stido.h”
int M=M2-2,N=N2-2; /* M×N为迷宫大小*/
typedef struct /*定义栈元素的类型*/
{int x,y;
}elemtype;
typedef struct /*定义顺序栈*/
{elemtype stack[MAXLEN];
int top;
}sqstktp;
typedef struct /*定义队列元素的类型*/
{int x,y,pre;
}queeletp;
typedef struct /*定义顺序队列*/
{queeletp queue[MAXLEN];
int front,rear;
}queuetp;
struct moved /*定义方向位移数组元素的类型*/
{int dx;dy;
};
/*初始化迷宫*/
void inimaze(int maze[ ][N2])
{ int i,j,num;
for(i=1;i<=M;i++) /*根据M和N的值产生迷宫*/
{ for(j=1;j<=N;j++)
{ num=(800*(i+j)+1500) &327;
if (num<150 &&(i!=M ||j!=N))
maze[i][j]=1;
else
maze[i][j]=0;
printf(“%3d”,maze[i][j]); /*显示迷宫*/
}
printf(“\n”);
}
printf(“\n”);
for(i=0,j=0;i<=M+1;i++) /*设置迷宫的边界值*/
maze[i][j]=1;
for(i=0,j=N+1;i<=M+1;i++)
maze[i][j]=1;
for (i=0,j=0;j<=N+1;j++)
maze[i][j]=1;
for(i=M+1,j=0;j<=N+1;j++)
maze[i][j]=1;
} /*inimaze*/
/*初始化方向位移数组*/
void inimove(struct moved move[])
{ move[0].dx=0;move[0].dy=1; /*依次为 E,SE,S,SW,W,NW,N,NE*/
move[1].dx=1;move[1].dy=1;
move[2].dx=1;move[2].dy=0;
move[3].dx=1;move[3].dy=-1;
move[4].dx=0;move[4].dy=-1;
move[5].dx=-1;move[5].dy=-1;
move[6].dx=-1;move[6].dy=0;
move[7].dx=-1;move[7].dy=1;
}/*inimove*/
/*初始化栈*/
void inistack(sqstktp *s)
{s->top=-1;
} /*inistack*/
/*压栈，数据元素x入指针s所指的栈*/
int push(sqstktp *s,elemtype x)
{ if (s->top= =MAXLEN-1) /*栈满，返回False*/
return(False);
else
{ s->stack[++s->top] =x; /*栈不满，执行入栈操作*/
return(Ture);}
} /*push*/
/*栈顶元素出栈*/
elemtype pop(sqstktp *s)
{ elemtype elem;
if (s->top<0) /*如果栈空，返回空值*/
{ elem.x=Null;
elem.y=Null;
elem.dir=Null;
return(elem);
}
else
{ s->top- -;
return(s->stack[s->top+1]); /*栈不空，返回栈顶元素*/
}
}/*pop*/
/*初始化队列*/
void iniqueue(queuetp *s)
{ s->fornt=1; /*为直观，设置队头在数组下标为1处*/
s->rear=1;
} /*iniqueue*/
/*寻找迷宫中最短路径
int shortpath(int maze[][N2],struct moved move[],queuetp *p)
{ int i,j,dir,x,y;
p->queue[1].x=1;//入口点坐标入队列
p->queue[1].y=1;
p->queue[1].pre=0;
maze[1][1]=-1;//设置入口点以到达
while(p->front<=p->rear)//当队列不空时循环
{ i=p->queue[p->front].x;//j,i为出发点
j->p->queue[p->fornt].y;
for(dir=0;dir<8;dir++)
{ x=i+move[dir].dx;
y=j+move[dir].dy;
if(maze[x][y]==0)//如有可到达点，将此点坐标入对列
{ p->rear++:
p->queue[p->rear].x=x;
p->queue[p->rear].y=y;
p->queue[p->rear].pre=p->front;
maze[x][y]=-1;//设置已达到标志
}
if(((x==M)&&(y==N))//如到达出口，返回true
return（true）;
}
p->front++;//对头指针指向下一个队列元素
}
return (false);//迷宫无通路
}
/*显示迷宫通路
void printpath(queuetp*p,sqstktp *s)
{ int i,f;
elemtype elem;
i=p->rear;
Do /*从队列中取出最短路径放入栈中
{ elem.x=p->queue[i].x;
elem.x=p->queue[i].y;
f=push(s,elem);
if(f==false) /*如果f为假，则栈长度太短
printf(“栈长太短“)；
i=p->queue[i].pre;
}while(i>0);
i=s->top;
While(i>-1)
{ printf(s->stack[i].x,s->stack[i].y);/*显示迷宫最短的通路
if(i>0)
printf(“(”);
if((s->top-i+1)%4==0)
printf(“\n”);
i—;
}
printf(“\n”);
}
/*在迷宫中绘出最短路径
void draw(int maze[][n2],sqstktp*s)
{ int i,j;
elemtype elem;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
if(maze[i][j]==-1)
maze[i][j]=0;
while(s->top=-1) /*根据栈中元素的坐标，将最短路径各点的值该为8
{ elem=pop(s);
i=elem.x;j=elem.y;
Maze[i][j]=8;
}
for(i=1;i<=m;i++) /*显示已标记最短通路的迷宫
{ for(j=1;j<=n;j++)
printf(maze[i][j]);
printf(“\n”);
}
printf(“\n”);
}
/*寻找迷宫最短通路路径程序
Void main()
{ sqstktp *s;
queuetp *p;
int maze[m2][n2],f;
struct moved move[8];
inimaze(maze);/*初始化迷宫
s=(sqstktp*)malloc(sizeof(sqstktp));
inistack(s);/*初始化栈
p=(queuetp*)malloc(sizeof(queuetp));
iniqueue(p);/*初始化队列
inimove(move);/*初始化方向为一数组
f=shortpath(maze,move,p)/* 寻找迷宫最短通路路径程序
if(f==true)
{ printpath(p,s);/*如果找到，显示通路和绘制出通路标记的迷宫
draw(maze,s);
}
else
printf(“此迷宫无通路\n”);/*如果没找到显示无通路
}
题目四 停车场管理算法
[问题描述]
设有一个可以停放n辆汽车的狭长停车场，它只有一个大门可以供车辆进出。车辆按到达停车场时间的早晚依次从停车场最里面向大门口处停放（最先到达的第一辆车放在停车场的最里面）。如果停车场已停放满n辆车，则后来的车辆只能在停车场大门外的便道上等候，一旦停车场内有车开走，则排在便道上的第一辆车就进入停车场。停车场内如果有某辆车要开走，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车再按原来的次序进场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费。如果停留在便道上的车未进入停车场就要离去，允许其离去，不收停车费，并仍然保持在便道上等待的车辆的次序。编制一个程序模拟该停车场的管理。
[实现要求]
要求程序输出每辆车到达后的停车位置（停车场或便道上），以及某辆车离开停车场是应交纳的费用和它在停车场内停留的时间。
[实现提示]
汽车的模拟输入信息格式可以是：（到达/离去，汽车牌照号码，到达/离去的时刻）。例如，（‘A’，1，5）表示1号牌照车在5这个时刻到达，而（‘D’，5，20）表示5号牌照车在20这个时刻离去。整个过程可以在输入信息为（‘E’，0，0）时结束。本题可以用栈和队列来实现。
[程序实现]
设计思想根据题目要求，停车场只有一个门，因此可用一个栈来模拟；而当栈满后，继续来到的车辆只能停在便道上，根据便道停车的特点，可知这可以用一个队列来模拟，先排队的车辆先离开便道，进入停车场。由于停在停车场中间的车辆可以提出离开停车场，并且要求在离开到停车场到停车场大门之间的车辆都必须先离开停车场，让此车离去，然后再让这些车辆按原来的次序进入停车场，因此在一个栈和队列的基础上，还需要有一个地方（车辆规避所）保存为了让路而离开停车场的车辆，很显然这也应该用一个栈来模拟。因此本题中用到两个栈和一个队列对于停车场和车辆规避所，有车辆进入和车辆离去两个动作，这就是栈的进栈和出栈操作，只是还允许排在中间的车辆先离开停车场，因此在栈中需要进行查找。而对于便道，也有如队列和入队列的操作，同样允许排在中间的车辆先离开队列。这样基本动作只需利用栈和队列的基本操作即可实现。
整个操作过程是：当输入数据表示有车辆到达，则判断栈是否满，若未满就将新数据进栈（表示新到达的车辆进入停车场的里面），数据应包括车牌号和到达时间；若已满，就将数据放在队尾，表示车辆在便道上等待进入停车场。
当输入数据表示有车辆要离去，就在栈中寻找是否有该车牌号的车辆，如有就让此车辆离开停车场，并根据停车时间计费；如没有找到，就到队列中（便道上）去寻找此车牌号的车辆，如有就允许此车辆离开队列，但不收费；如没有就显示出错信息。
当离开停车场的车辆位于栈的中间时，必须先将此位置到栈顶之间的所有数据倒到另一个栈中去（车辆规避所），然后安排车辆出栈，最后将另一个栈中的数据倒回到停车场栈中来。
在模拟停车场管理时，还应注意，如果停车场栈中已没有车辆停放时，输入数据仍然要求车辆退出，则显示出错信息；程序中停车场的停车数量为n，但对便道没有规定，因此认为便道上可以听任意多的车辆。
程序实现根据题目分析的结果，停车场和车辆规避所的栈可以采用顺序栈，而便道可用链队列来模拟。
#define N 2 /*定义停车场栈长度*/
#define M 5 /*M为单元时间的收费值*/
#define True 1
#define False 0
#include,stdio.h”
/*存储结构*/
typedef struct /*定义栈元素的类型*/
{int num;
int arrtime;
}elemtype;
typedef struct /*定义栈*/
{elemtype stack[N];
int top;
}sqstktp;
typedef struct node /*定义队列结点的类型*/
{int num;
struct node *next;
}queueptr;
typedef struct /*定义队列*/
{queueptr *front,*rear;
}linkedquetp;
/*初始化栈*/
void inistack(sqstktp s)
{ s->top= -1;
}
/*压栈，将数据元素x压入指针s所指的栈*/
int push(sqstktp s,elemtype x)
{ if (s->top= =N-1)
return (False); /*如果栈满，返回False*/
else
{ s->stack[++s->top]=x; /*栈不满，x入栈。*/
return (True);
}
}/*push*/
/*弹栈，将栈顶元素出栈*/
elemtype pop (sqstktp *s)
{ elemtype x ;
if (s->top<0)
{ x.num=Null;
x.arrtime=Null;
return (x); /*如果栈空，返回空值*/
}
else
{ s->top - -;
return (s->stack[s->top+1]); /*返回栈顶元素*/
}
}/*pop*/
/*初始化队列*/
void inilinkedque (linkedquetp s)
{ s->fornt= (queueptr )malloc (sizeof (queueptr)); /产生一个新结点，作头结点*/
s->rear= s->fornt;
s->front->next =Null;
s->front->num =0; /*头结点的num保存队列元素的个数*/
}/* nilinkedque */
/*数据入队列*/
void enlinkedque (linkedquetp s,int numl)
{ queueptr *p;
p= (queueptr)malloc (sizeof (queueptr));/*产生一个新结点*/
p->num =numl;
p->next =Null;
s->rear->next=p; /*新结点入队列*/
s->rear=p;
s->front->num++; /*队列元素个数加1*/
}/*enlinkedque*/
/*数据出队列*/
int dllinkedque(linkedquetp s)
{ queueptr *p;
int n;
if (s->front ==s->rear)
return (Null); /*如果队列空，返回空值*/
else
{ p=s->front->next=p->next; /*返回队头元素值*/
if (p->next==Null)
s->rear=s->front;
n=p->num;
free(p);
s->front->num - -; /*队列元素的个数减1*/
return (n);
}
}/*dllinkedque*/
/*处理车辆到达的情况*/
void arrive(sqstktp *sl,linkedquetp *p,elemtype x)
{ int f;
f=push (s1,x); /*新到达的车辆入停车场栈*/
if (f==False)
{ enlinkedque(p,x.num); /*如停车场满，入便道队列*/
printf(“第%d号车停在便道第%d号车位上 \n”,x.num,p->front->num);
}
else /*新到车辆进入停车场*/
printf(“第%d号车停在停车场第%d号车位上\n”,x.num,sl->top+1);
}/*arrive*/
/*处理车辆离去的情况*/
void delive(sqstktp *sl,sqstktp *s2,linkedquetp *p,elemtype x)
{ int n,f=False;
elemtype y;
queueptr *q;
/*在停车场中寻找要离开的车辆*/
while ((sl->top>-1)&&(f!=Ture))
{ y=pop(sl);
if (y.num!=x.num) /*如果栈顶元素不是要离开的车辆，就将其放入车辆规避所*/
n=push(s2,y);
else
f=Ture;
}/*end of while
if (y.num= =x.num) /*在停车场中找到要离开的车辆*/
{ printf(“第%d号车应收费%d元\n”,y.num,(x.arrtime-y.arrtime)*M);
/*车辆规避所不空，将其全部放回停车场*/
while (s2->top>-1)
{ y=pop(s2);
f=push(s1,y); }
n=dllinkedque(p);
/*如便道上有车辆，将第一辆车放入停车场*/
if (n!=Null)
{ y.num=n;
y.arrtime=x.arrtime; /*计费时间为刚离开车辆的离去时间*/
f=push(s1,y);
printf(“第%d号车停在停车场第%d号车位上\n”,y.num,s1->top+1);
}
}/*end the pat one of if
else /*在停车场中没有找到要离开的车辆*/
{ while (s2->top>-1) /*将车辆规避所中的所有车辆放入停车场*/
{ y=pop(s2);
f=push(s1,y);
}
q=p->front;
f=False;
/*在便道上寻找要离开的车辆*/
while (f= =False &&q->next!=Null)
if (q->next->num!=x.num)
q=q->next;
else
/*在便道上找到该车辆*/
{ q->next=q->next->next;
p->fornt->num - -;
if (q->next= =Null)
p->rear=p->front;
printf(“第%d号车离开便道\n”,x.num); /*该车离开便道，但不收费*/
f=Ture;
}
/*在便道上也没找到要离开的车辆，输入数据错误*/
if (f= =False)
printf(“输入数据错误,停车场和便道上均无第%d号车\n”,x.num);
}
}/*delive*/
/*停车场模拟管理程序*/
void main( )
{ char ch1,ch2;
sqstktp *s1,*s2;
linkedquetp *p;
elemtype x;
int flag;
s1=(sqstktp *)malloc(sizeof(sqstktp));
s2=(sqstktp *)malloc(sizeof(sqstktp));
p=(linkedquetp *)malloc(sizeof(linkedquetp));
inistack(s1); /*初始化停车场栈*/
inistack(s2); /*初始化便道队列*/
flag= true;
for(;;)
{printf(“输入数据：‘A’/ ‘D’,车牌号，到达/离开时间\n”);
scanf(“%c %d %d”,&ch1,&x.num,x.arrtime);
ch2=getchar( );
switch (ch1)
{ case ‘A’, arrive(s1,p,x); /*车辆到达*/
break;
case ‘D’, delive(s1,s2,p,x); /*车辆离去*/
break;
case ‘E’,flag=False; /*结束程序运行*/
printf(“程序正常结束\n”);
break;
default,printf(“输入数据错误，重新输入\n”);
}
if (flag = =False) break;
}
}/*main*/
实验三 数组与广义表一、实验目的
1、了解数组的两种存储表示方法，掌握数组在作为运行的存储结构中的地址的计算方法。
2、了解稀疏矩阵的两种压缩方法的特点和适用范围，领会稀疏矩阵运算采用的处理方法。
掌握广义结构的特点及其存储表示方法。
二、实验内容题目一 鞍点问题
[问题描述]
若矩阵中的某个元素A[i,j]是第一行中的最小值，而又是第j列中的最大值，则称A[i,j]为矩阵A中的第一个鞍点。请写一个可确定此鞍点位置的算法（如果这鞍点存在），并给出此算法的时间复杂度。
[基本要求]
要求算法要考虑某行中具有多个相同的且又是该行中最小的元素的情况。
[实现提示]
可以用一位数组保存R[0..n-1]每一行中最小的元素，用一位数组C[0..n-1]来保存每一行中最大元素。如果R[i]=C[j]，则A[i,j] 即为鞍点。
[程序实现]
基本思想可先求出每行的最小值元素，放入一个一维数组min[m]中，在求出每列的最大元素，放入max[n]中，若某个元素既在min[i]中，又在max[j]中，则该R[i,j]元素便是鞍点元素，找出这样的鞍点元素，即找到此处有鞍点。
(2)程序实现
#include <stdio.h>
#define m 4
#define n 5
/*鞍点定位
void point（R）
int R[m][n];
{ int i,j;
int flag;
int min[m],max[n];
flag=0;
/*找每行最小值放入min[i]中
for(i=0;i<m;i++)
{ min[i]=R[i][0];
for(j=1;j<n;j++)
if(R[i][j]<min[i])
min[i]=R[i][j];
}
/*找每行最大值放入max[j]中
for(j=0;j<n;j++)
{ max[j]=R[0][j];
for(i=1;i<m;i++)
if(R[i][j]>max[j])
max[j]=R[i][j];
}
for(i=0;i<m;i++)
for(j=0;j<n;j++)
if(min[i]==max[j])
{ prinft(“(%d,%d):%d\n”,i,j,R[i][j]); /*输出鞍点
flag=1; /*置标志
}
if (!flag)
printf(“找不到鞍点\n”);
}
/*主函数
main()
{ int R[m]}[n];
int i,j;
for(i=0;i<m;i++)
for(j=0;j<n;j++)
scanf(&R[i][j]);
point(r);
}
题目二 N阶魔阵问题
[问题描述]
给定一奇数n，构造一个n阶魔阵，n阶魔阵是一个n阶方阵，其元素由自然数1，2，3……n2组成，魔阵的每行元素之和，每列元素之和以及主、副对角线元素之和均相等。即对于给定的奇整数n以及i=1…..n,魔阵a满足条件：
∑aik (k=1~ n)=∑aki(k=1~ n)=∑akk(k=1~ n)=∑ak,n-k+1(k=1~ n)
[基本要求]
要求输出结果的格式要具有n阶方阵的形式。
[实现提示]
依次将自然数填入方阵中，共填n轮，每轮填n次。第一轮的第一次将1填入方阵的中间一行的最后一列位置。设前一次填入的位置是aij:
（1）每轮中第2至第n次将数填入ai+1,j+1,若遇到下列两种情况之一，则填写位置按以下规则调整。
aij是最后一列（即j=n）位置，则将下一个数填入ai+1,1;
aij是最后一行（即i=n）位置，则将下一个数填入a1,j+1.
(2) 新一轮的第一次填入a1,j-1.
[程序实现]
/*N阶魔阵问题主函数
main()
{ int r[m][n]; /*设数组下标均从1开始
int n,j,i,k;
scanf(&n);
i=(n+1)%n; /*相除
J=n+1;
For(k=1,k<=(n*n);k++)
{ if(k%n==1)
j--;
else
{ i=i%n+1;
j=j%j+1;
}
r[i][j]=k;
}
for(i=1;i<=n;i++)
{ for(j=1;j<=n;j++)
printf(r[i][j]);
}
}
也可按下列方法给出n魔阵，其算法思想为：
由魔方阵知其排列规律如下：
将1放第一行中间一列；
从“2”开始直到n*n止，各数一次按下列规则存放：每一个数存放的行比前一个数的行数减1，列数加1；
如果上一数行数为1，则下一个数行数为n（指向最下一行）；
当上一数的列数为n时，下一个数的列数应为1，行数减1；
如果按上面规则确定位置上的已有数，或上一个数是第1行第 n列时，则把下一个数放在上一个数的下面。
算法程序如下：
#define n 15
main()
{ int r[m][n];
int r,c,k,i,j;
k=0;
scanf(&k);
for(i=1;i<=k;i++)
for(j=1;j<=k;j++)
r[i][j]=0;
i=1;
t=1;
m=k*k;
J=(k+1)%2;
R[i,j]=t;
T++;
While(t<=m)
{ x=i-1;
y=j+1;
if((x<1)&&(y<k))
{ i=x+2;
J=-y-1;
}
else
if(y<k)
{ i=x;
j=1;
}
else
if(i<1)
{ i=k;
j=y;
}
else
if(r[x][y]!=0)
{ i=x+2;
J=y-1;
}
else
{ i=x;
j=y;
}
r[i][j]=t;
}
for(i=1;j<=k;i++)
{ for(j=1;j<=k;j++)
printf(r[i][j]);
printf(“\n”);
}
}
实验四 树一、实验目的进一步掌握指针变量，动态变量的含义。
掌握二叉树的结构特性，以及各种存储结构的特点及使用范围掌握用指针类型描述、访问和处理二叉树的运算二、试验内容题目一 二叉树子树交换算法
[基本要求]
编写交换以二叉树链表作存储结构的二叉树中所有结点的左、右子树的算法。
[基本思想]
设二叉树的根指针为t，且以二叉链表表示，可利用一个类型为seqstack的指针来实现，且设栈单元包含两个域，一个为data，一个为top，整个栈容量为maxsize，当树非空时，将当前的树根结点入栈，同时将当前栈顶元素出栈当作根结点，然后依据当前的根结点是否具有孩子结点来判断是否将其左、右指针进行交换；再将交换后的左指针或右指针入栈，这样反复进行，直到栈为空为止。
[算法实现]
#define null o
typedef struct node
{ int data;
struct node lchild,rchild;
}bitree;
typedef int datatype ; /*栈元素的数据类型
#define maxsize 64 /*栈可能达到的最大容量
typedef struct {
datatype data[maxsize];
int top;
} seqstack； /*顺序栈类型定义
seqstack s; /* s顺序栈类型指针
/*建立二叉树
bitree *creat()
{ bitree *t;
int x;
scanf(“&x);
if(x==0)
t=null;
else
{ t=malloc(sizeof(bitree));
t->data=x;
t->lchild=creat();
t->rchild=creat();
}
return t;
}
/*中序遍历二叉树
void inorder(t)
bitree *t;
{ if(t!=null)
{ inorder(t->lchild);
prinrf(t->data);
inorder(t->rchild);
}
}
/*对二叉树t所有结点左右子树进行交换
exchange(t)
bitree *t
{ bitree *p;
seqstack s; /*为一指针栈，类型为seqstack
if(t)
{ s->top=1;
s->data[s->top]=t; /*跟指针t进栈
do
{ t=s->data[s->top]; /*栈顶元素退栈
s->top--;
if((t->lchild!=null)||(t->rchild!=null))
{ p=t->lchild; /*结点的左右指针交换
t->lchild=t->rchild;
t->rchild=p;
}
if(t->lchild!=null) /*交换后的左孩子指针入栈
{ s->top++;
s->data[s->top]=t->lchild;
}
if(t->rchild!=null) /*交换后的右孩子指针入栈
{ s->top++;
s->data[s->top]=t->rchild;
}
}while(s->top==0) /*栈空结束
}
}
/*交换算法主函数
main()
{ bitree *root;
root=creat();
inorder(root);
exchange(root);
inorder(root);
}
对于exchange算法也可以利用以下的递归算法
void exchange(t)
bitree *t;
{ bitree *p;
if(t!=null)
{ p=t->lchild;
t->lchild=t->rchild;
t->rchild=p;
exchange(t->lchild);
exchange(t->rchild);
}
}/*exchange*/
题目二 按层次顺序遍历二叉树
[基本要求]
已知以二叉链表作存储结构，试编写按层次顺序遍历二叉树的算法。
[算法思想]
本算法要采用一个队列q，先将二叉树根结点入队列，然后退队列，输出该结点，若它有左子树，便将左子树根结点入队列，若它有右子树，边将右子树根结点入队列，如此直到队列为空为止，因为队列的特点是先进先出，从而达到按层次顺序遍历二叉树的目的。
[算法实现]
#define m 100
#define null 0
typedef struct node
{ int data;
struct node lchild,rchild;
} bitree;
bitree *que[m];
int front=0,rear=0;
/*建立二叉树
bitree *creat()
{ bitree *t;
int x;
scanf(&x);
if(x==0)
t=null;
else
{ t=malloc(sizeof(bitree));
t->data=x;
t->lchild=creat();
t->rchild=creat();
}
return t;
}/*create*/
/*中序遍历二叉树
void inorder(t)
bitree *t;
{ if(t!=null)
{ inorder(t->lchild);
printf(t->data);
inorder(t->rchild);
}
}
/*入队列
void enqueue(t)
bitree *t;
{ if(front!=(rear+1)%m)
{ rear=(rear+1)%m;
que[rear]=t;
}
}
/*出队列
bitree *delqueue()
{ if(front==rear)
return null;
front=(front+1)%m;
return (que[front]);
}
/*按层次遍历二叉树
void levorder(t)
bitree *t;
{ bitree *p;
if(t!=null)
{ enqueue(t);
while(front!=rear)
{ p=delqueue();
printf(p->data);
if(p->lchild!=null)
enqueue(p->lchild);
if(p->rchild!=null)
enqueue(p->rchild);
}
}
}
/*主调函数
main()
{ bitree *root;
printf(“\n”);
root=creat();
inorder(root);
printf(“\n”);
levorder(root);
}
也可以用非递归方式写出levorder算法。可利用一个队列que来保存遍历过程中的各个结点。由于二叉树以二叉链表存储，所以设que为一个指向数据类型为 bitree的指针数组，最大容量为maxsize,下标从1开始，同层结点从左到右存放。其中front为队头指针，rear为尾指针
/*按层次遍历二叉树t
levlorder(t)
bitree t; /*二叉树t为类型bitree
{ /*队列que为一个指向类型指针数组，下标从1开始
bitree *que[maxsize]
int rear,front;
if(t)
{ front=0; /*置空队列
rear=1;
que[1]=t;
do
{ front=front%maxsize+1; /*出队列
t=que[front];
printf(t->data);
if (t->rchild!=null) /*左子树的根结点入队
{ rear=rear%maxsize+1;
que[rear]=t->lchild;
}
if (t->rchild!=null) /*右子树的根结点入队
{ rear=rear%maxsize+1;
que[rear]=t->rchild;
}
} while(rear==front);
}
}/*levorder*/
题目三 二叉排序树遍历算法
[基本要求]
已知二叉排序树以二叉链表作为存储结构，试编写按从大到小的顺序输出二叉排序树的各结点的算法。
[算法思想]
可以先建立一棵二叉排序树，以二叉链表表示，由于按中序遍历二叉排序树即为按递增次序遍历，所以要按从大到小的顺序输出二叉排序树的各结点的值，可以对二叉排序树从树根结点右子树中最右下结点开始进行遍历，先遍历右子树，在访问根结点，最后遍历左子树，这样就可以得到一个结点从大到小的顺序输出的序列。
[算法实现]
#define m 100
#define null 0
typedef struct node /*二叉树链表类型定义
{ int data;
struct node *lchild,*rchild;
} bitree;
/*从右子树开始遍历二叉排序树
void destorder(t)
bitree *t;
{ if(t!=null)
{ destorder(t->rchild);
printf(t->data);
destorder(t->lchild);
}
}
/*将新结点*s插入到t所指的二叉排序树中
bitree *insertbst(t,s)
bitree *s,*t;
{ bitree *f,*p;
p=t;
while(p!=null)
{ f=p;
if(s->data==p->data)
return t;
if(s->data<p->data)
p=p->lchild;
else
p=p->rchild;
}
if(t==null) return s;
if (s->key<f->key)
f->lchild=s;
else
f->rchild=s;
return t;
}
/*返回二叉排序树
bitree *creatord()
{ bitree *t,*s;
int x;
t=null;
scanf(&x);
while(x!=0)
{ s=malloc(sizeof(bitree));
s->data=x;
s->lchild=null;
s->rchild=null;
t=insertbst(t,s);
scanf(&x);
}
return t;
}
/*主函数
main()
{ bitree *root;
printf(“\n”);
root=creatord();
destorder(root);
printf(“\n”);
}
实验五 图一、实验目的
1、掌握图的基本存储方法。
2、掌握有关图的操作算法并用高级语言实现。
3、熟悉图的各种存储结构及其构造算法，了解实际问题的求解效率与采用何种存储结构以及算法有着密切的联系。
4、熟练掌握图的两种搜索路径的遍历方法。
二、实验内容题目一 优化通信网的设计算法
[基本要求]
如果以无向网表示n个城市之间的通信网络的建设计划，顶点表示城市，边上的权表示该线路的造价，设计一个方案，使这个通信网的总造价最低。
[实现提示]
这是一个求连通的带权无向图（及网络）的最小代价生成树的问题。建立图的邻接矩阵，然后以prime算法来求最小生成树。
[算法实现]
这里给出由R.C.Prim提出的求最小代价生成树的算法。设图的顶点集合V有n个顶点，prim算法粗略的描述如下：
（1）一个顶点的集合S1和一个边的集合TE，S1和TE的初始状态皆为空集。
（2）选中图中的一个顶点k（从此顶点开始求最小代价生成树），将k加入集合S1。
（3）重复下列步骤，直至选取了n-1条边：
①选取一条权值最小的边（x,y）；
②将顶点y加入集合S1，边（x,y）加入集合TE。
下面是用邻接表做为数据结构实现prim算法的程序。
#ingclude <stdio.h>
#define n 5 /* n为顶点数*/
#define max 1000.0
typedef struct node
{ int no;
float wgt;
struct node *next;
} edgenode
typedef struct
{ char vtx;
edgenode *link
} vexnode;
float gali[n][n]={{0,2,12,10,max},{2,0,8,max,9},
{12,8,0,6,3,},{10,max,6,0,7},{max,9,3,7,0}};
typedef vesnode Graph[n];
Grapg G;
/*用邻接表实现prim算法*/
Void prim(vexnode Gp [ ],int k)
{ int v2link[n],vset[n],parent[n],w[n];
edgenode *ptr;
int x,s,ecount，i，y，z，f;
s=-1;
v2link[n]=-1;
ecount=0;
for(i=0;i<n;i++)
if(i!=k)
vset[i]=3;
while(ecount <n-1)
{ ptr=G[x].link;
while(ptr!=Null)
{ y=ptr->no;
if((vset[y]==2)&&(ptr->wgt<w[y])) /*y在集合v2*/
{ parent[y]=x;
w[y]=ptr->wgt;
}
if (vset[y]==3) /*y在集合v3*/
{ vset[y]=2;
v2link[y]=s;
s=y;
parent[y]=x;
w[y]=ptr->wgt;
}
ptr=ptr->next;
}
if(s==-1)
break; /*无最小代价生成树*/
z=x=s;
y=v2link[x];
f=-1;
while(y!=-1)
{ if (w[y]<w[x])
{ x=y;
f=z;
}
z=y;
y=v2link[y];
}
if(f==-1)
s=v2link[x];
else
v2link[f]=v2link[x];
vset[x]=1;
ecount ++; /*边数记数*/
}
printf(“\nroot%c:\t”,G[k].vtx); /*输出结点*/
for(i=0;i<n;i++)
{ if(i!=k)
{ printf(G[i].vtx);
f=parent[i];
printf(“G[f].vtx);
}
}
/*建立邻接表
void creatlist(vexnode ga[])
{ int i,j,k,e,w;
edgenode *se;
for(i=0;i<n;i++)
{ ga[i].vtx=’a’+i;
for(j=0;j<n;j++)
{ if((gali[i][j]<max)&&(gali[i][j]!=0))
{ se=(edgenode*)malloc(sizeof(*se));
se->no=j;
se->next=ga[i].link;
se->wgt=gali[i][j];
ga[i].link=se;
}
}
}
}
/*主程序*/
main()
{ int i;
edgenode *ve;
creatlist(G);
for(i=0;i<n;i++)
{ printf(G[i].vtx);
ve=G[i].link;
while(ve!=null)
{ printf(ve->no,ve->wgt);
ve=ve->next;
}
}
prim(G,4);
return 0;
}/*main*/
题目二 最优选课序列算法设计
[基本要求]
软件专业的学生要学习一系列的课程，其中有些课程必须在其先修课程之后才能学习，具体关系见下表：
课程编码
课程名称
先决条件
C1
程序设计基础
无
C2
离散数学
C1
C3
数据结构
C1，C2
C4
汇编语言
C1
C5
语言的设计和分析
C3，C4
C6
计算机原理
C11
C7
编译原理
C3，C5
C8
操作系统
C3，C6
C9
高等数学
无
C10
线性代数
C9
C11
普通物理
C9
C12
数值分析
C1，C9，C10
假使每门课程的学习时间为一学期，试为该专业的学生设计教学计划，使他们能在最短的时间内修完这些课程。
[实现提示]
以顶点代表课程，弧代表课程的先后修关系，按表中条件建立有向无环图的邻接表结构并统计得到初始化的入度为0的顶点，利用拓扑排序算法来进行课程安排。假定一个进修班的学生必须完成所列的全部课程。在这里，课程代表活动，学习每门课程的先决条件是学完它的全部先修课，如“编译技术”课程就必须先修它的两门先修课程“数据结构”和“算法语言”之后,“高等数学”课程则可以在后修课程之前随时安排，因为它是基础课程。
通常我们把这种顶点代表活动，边代表活动间先后关系的有向图称为顶点活动网，简称阿Aov网。一个Aov网应该是一个有向无环图，即不应该带有回路，因为若带有回路，则回路的所有活动都无法进行。
在Avo网中，若不存在回路，则所有活动可排列成一个线性序列，使每个活动的所有前驱活动都排列在该活动的前面，我们称为拓扑序列（Topological orde），由Aov网构造拓扑序列的过程叫做拓扑排序。Aov网的拓扑序列不是唯一的，满足上述定义的任一线性序列都称作它的拓扑序列。
由Aov网构造拓扑序列的实际意义是：如果按照拓扑序列中的顶点次序进行每一项活动，就能够保证在开始每一项活动时，他的所有前驱活动都已完成，从而使得整个工程结点顺序进行。
由构造拓扑序列的拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止。
选择一个入度为0的顶点并输出之；
从网中删除该顶点及所有从该顶点出发的边。
循环结束时，若输出的顶点数小于网中的顶点数，则输出“有回路”错误信息，否则输出的顶点序列就是一种拓扑序列。
为了在计算机上实现拓扑排序算法，Aov网采用邻接表表示较方便，不过要在表头结点结构中增加一个保存顶点入度的域（indegree）。在进行拓扑排序中，为了把拓扑排序都保存起来，而且又便于插入、删除和节省存储，最好的方法是把它们链接成一个栈。另一方面，当一个顶点入度为0时，邻接表中的对应表结点中的入度域(indegree)就没有用了，可正好利用它作为链栈单元使用，用来保存下一个入度为0的顶点序号，通过所有入度为0的表头结点中的入度域就可以把 入度为0的顶点（对应表头结点）都静态链接起来。在这个链栈中，栈顶指针top指向第一个入度为0的顶点vi(对应表头向量中的第i个分量，即vi的表头结点)，vi的表头结点的入度域指向第二个入度为0的顶点vj，以此类推，最后一个入度为0的表头结点的如度域应置为0（即空指针），表示栈底。
采用邻接表作为实现上述算法的数据结构。算法首先扫描邻接表，求出图中每一个顶点的入度存于数组IN中，然后将所有入度为0的顶点组成一个链表并作为链接存储的栈进行操作，top指向栈顶。
[算法实现]
typedef struct node
{ int no;
float wgt;
struct node *next;
} edgennode;
typedef struct
{ char vtx;
edgenode *link;
} vexnode;
typedef vexnode Graph [n];
Graph G;
/*拓扑排序
void topolo(Graph g)
{ int top,count,i,j;
char k;
edgenode *p;
int IN[n];
for(i=0;i<n;i++); /*数组IN初始化
IN[i]=0;
for(i=0;i<n;i++) /*求图中个顶点的入度
{ p=g[i].link;
while(p!=null)
{ j=p->no;
IN[j]++;
P=p->next;
}
}
top=-1;
for(i=0;i<n;i++) /*将入度为0的顶点组成一个栈
if(IN[i]==0)
{ IN[i]=top;
Top=i;
}
count=0;
while(top>=0)
{ k=g[top].vtx;
printf(k); /*输出顶点
p=g[top].link;
top=IN[top];
count++;
while(p!=null)
{ j=p->no;
IN[j]--;
if (IN[j]==0) /*将入度为0的顶点插入栈中
{ IN[j]=top;
Top=j;
}
p=p->next;
}
}
if(count<n)
printf(“\n the network has a cycle”);
}/*topolo
题目三 交通购票指南系统算法
[基本要求]
假设以一个带权有向图表示某一区域的公交线路网，图中顶点代表一些区域中的重要场所，弧代表以有的公交线路，弧上的权代表该线路上的票价（或搭乘所要的时间）。试设计一个交通指南系统，直到来咨询者以最低的票价或最少的时间从区域中的某一场所到达另一场所。
[实现提示]
该问题可以归结为一个求带权有向图中顶点间最短路径的问题。分别建立以票价为权或以搭乘时间为权的邻结矩阵，以FLOYD算法来求最短路径及其路径长度。
设图G=(V，E)的顶点集合V={0,1,…., n-1}，图用邻接矩阵表示。一开始，若弧<i,j>∈E(G)，则认为i到j的最短路径为（i，j），长度为弧<i,j>的权。算法使用一个n*n的矩阵A进行n次迭代来计算每对顶点间的最短路径，迭代过程中得到的一个矩阵序列A0,A1,…..,An，矩阵元素An[i,j]的值即为从顶点i到顶点j的最短路径长度。首先在路径（i，j）中插入顶点0，考虑路径（i,0,j），若该路径存在，即图中有弧<i,0>和<0,j>，比较路径（i,j）和路径（i,0,j）的长度，取长度最短者作为当前求得的从顶点i到顶点j且中间顶点编号不大于0的最短路径，记为（i,…..j）,其长度存于A1[i,j]中，然后再考虑路径（i,…,1,…j）,由于（i,…..j）和（i,…,1,…j）是从顶点i到顶点1及从顶点1到顶点j中间顶点编号不大于1的最短路径，比较路径(i,…,1)和路径 （i,…,1,…j）的长度，若后者较短，则路径（i,…,1,…j）即为当前求得的从顶点i到顶点j中间顶点编号不大于1的最短路径,其长度存于A2[i,j]中，………，依次类推，逐个插入图的每个顶点，最后必将求得顶点i到顶点j且中间顶点编号不大于n-1的最短路径。在k+1次迭代时，矩阵Ak+1[i,j]的值为： Ak[i,j]
A k+1[i,j]=min (0 ( k ( n-1)
Ak[i,k]+ Ak[k,j]
其中Ak+1[i,j]表示经过k+1次迭代后得到的值，他等于从i到j中间顶点编号不大于k的最短路径长度。
下面是R.W.FLOYD求每对顶点之间最短路径算法的C语言程序，程序中矩阵A用来进行n次迭代，矩阵P用来记录路径。P[i,j]为迭代过程中当前得到的从顶点i到顶点j的最短路径上最后被插入的那个顶点。
[算法实现]
typedef struct node
{ int no;
float wgt;
struct node *next;
} edgenode;
typedef struct
{ char vtx;
edgenode*link;
} vexnode;
typedef vexnode Graph[n];
/*floyd算法，求最短路径
void floyd(Graph G,float A[n][n],int p[n][n])
{ int i,j,k;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{ A[i][j]=G[i][j];
P[i][j]=-1;
}
for(k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(A[i][k]+A[k][j])
{ p[i][j]=A[i][k]+A[k][j];
}
}/*floyd*/
实验六 查找一、实验目的
1、掌握查找的不同方法，并能用高级语言实现查找算法。
2、熟练掌握顺序表和有序表的查找方法以及静态查找树的构造方法和查找算法，理解静态查找树的折半查找方的法。
3、熟练掌握二叉树的构造和查找方法。
二、实验内容题目一 二叉树的构成算法
[基本要求]
设计一个读入一串整数构成一棵二叉排序树的算法。
[实现提示]
二叉排序树的构成，可从空的二叉树开始，每输入一个结点数据，就建立一个新结点、插入到当前已生成的二叉排序树中，所以，它的主要操作是二叉排序树的插入运算。在二叉排序树中插入新结点，只要保证插入后仍符合二叉排序树的定义即可。插入是这样进行的：若二叉排序树为空，则待插入结点*s作为根结点插入到空树中；当二叉排序树非空，将待插结点的关键字s->key与树根的关键字t->key比较，若s->key=t->key,则说明树中已有此结点，无需插入；若s->key<t->key,则将待插结点*s插入到根的左子树中，否则将*s插入到根的右子树中。而子树的插入过程又和在树中的插入过程相同，如此进行下去，直到把结点*s作为一个新的树叶插入到二叉排序树中，或则直到发现树中已有*s结点为止.
[算法实现]
typedef struct node
{ int key; /*关键字项
int other; /*其他数据项
struct node *lchild,*rchild;
} bstnode;
/*中序遍历二叉树
void inorder (t)
bstnode *t;
{ if(t!=null)
{ inorder(t->lchild);
printf(“%4d”,t->key);
inorder(t->rchild);
}
}
/*将新结点*s插入到t所指的二叉排序树中
bstnode insertbst(t,s)
bstnode *s,*t;
{ bstnode *f,*p;
p=t;
while(p!=null)
{ f=p;
if(s->key==p->key)
return t;
if(s->key<p->key)
p=p->lchild;
else
p=p->rchild;
}
if(t==null)
return s;
if(s->key<f->key)
f->lchild=s;
else
f->rchild=s;
return t;
}
/*返回二叉排序树
bstnode *creatord()
{ bstnode *t,*s;
int key;
t=null;
scanf(“&d”,&key);
while(key!=0)
{ s=malloc(sizeof(bitree));
s->key=key;
s->lchild=null;
s->rchild=null;
scanf(“%d”,&data);
s->other=data;
t=insertbst(t,s);
scanf(“%d”,&key);
}
return t;
}
/*主函数
main()
{ bstnode *root;
root=creatord();
inorder(root);
}
题目二 二叉树结点删除算法
[基本要求]
写出从二叉排序树中删除一个结点，使该二叉排序树仍为二叉排序树的算法。
[实现提示]
本题要注意的是，删除二叉排序树中的结点与删除一棵树中的结点不同，二叉排序树的结点对应的是一条记录，只要在删除它后仍使它为二叉排序即可；而要将一棵树中的结点删除，是将该结点同他的左右子树一并删除。
要将二叉排序树的结点删除，必须建立一棵二叉排序树，以二叉链表方式表示，然后再进行二叉排序树结点删除，依据被删除结点位置又可分为根和非跟结点两种情况，可将算法思想描述为：
（1）若被删除结点k是二叉排序树的根结点，则:
若k有左子树L，而无右子树，则将仅需将L作为根结点即可若k有右子树r，而无左子树，则将仅需将r作为根结点即可若k既有左子树L又有右子树r,则可将L作为根结点。此时，若L无右子树，需将的L右孩子指针指向r；若L有右子树，则需沿着L右分支一直往下检索，直到找到最右的、且没有右子树的结点为止（即最右下的一个结点），然后把该结点的右孩子指针指向r。
（2）若被删除的结点k不是二叉排序树的根结点，此时可设*p为k的双亲结点，k是*p的左子树（或右子树），则可按以下情况进行处理：
若k有左子树L，而无右子树，则应将*p结点的左指针（或右指针）改指向L;
若k无左子树L，而有右子树，则应将*p结点的左指针（或右指针）改指向r
若k既有左子树又有右子树，则应将*p结点的左指针（或右指针）改向L；若L无右子树，需将的L右孩子指针指向r；若L有右子树，则需沿着L右分支一直往下检索，直到找到最右的、且没有右子树的结点为止，然后把该结点的右孩子指针指向r。
设t为二叉排序树的根指针，二叉排序树以二叉链表储存，k为待删除结点的关键字，则可的程序如下：
[算法实现]
首先建立一个二叉排序树，以二叉链表方式表示
typedef struct node
{ int key; /*关键字项
struct node * lchild,*rchild;
} bitree;
/*中序遍历二叉树
void inorder(t)
bitree *t;
{ if(t!=null)
{ inorder(t->lchild);
printf(t->key);
inorder(t->rchild);
}
}
/*将新结点*s插入到t所指的二叉排序树中
bitree *inserbst(t,s)
bitree *s,*t;
{ bitree *f,*p;
p=t;
while(p!=null)
{ f=p;
if(s->key==p->key)
return t;
if(s->key<p->key)
p=p->lchild;
else
p=p->rchild;
}
if(t==null)
return s;
if(s->key<f->key)
f->lchild=s;
else
f->rchild=s;
return t;
}
/*返回二叉排序树
bitree *creatord()
{ bitree *s,*t
int key;
t=null;
scanf(“&d”,&key);
while(key!=0)
{ s=malloc(sizeof(bitree));
s->key=key;
s->lchild=null;
s->rchild=null;
scanf(“%d”,&data);
s->other=data;
t=insertbst(t,s);
scanf(“%d”,&key);
}
return t;
}
再给出检索算法描述如下：
将p,q作为全程量看待，则有
/*在一个儿叉树t中间所关键字为k的结点
/* t为二叉排序树的根指针，二叉排序树以二叉链表存储
bstsrch (t,k)
bitree t;
int k;
{ int flag;
p=null; /*p,q为全程量
q=t;
flag=false;
while((q!=null)&&(flag==false))
if(k==q->key)
flag=true;
else
{ p=q;
if(k<q->key)
q=q->lchild;
else
q=q->rchild;
}
}
然后给出删除算法如下：
bittree *p,*q; /* p,q为bitree类型全局变量
/*从二叉排序树中删除一个结点
bintreedele(t,k)
bitree *t;
int k;
{ bitree *r;
bstsrch(t,k); /*检索过程，设待删除结点在树中
if(q!=null) /*若被删除结点在树中
if(p==null) /*若被删除结点是根结点
if(q->lchild==null) /*若被删除结点无左子树
t=q->lchild;
else /*若被删除得结点无右子树
if(q->rchild==null)
t=q->lchild;
else /*被删除结点儿女双全
{ r=q->lchild;
while(r->lchild!=null)
r=r->rchild; /*检索中序前趋
r->rchild=q->rchild;
t=q->lchild;
}
else /*被删除结点不是根结点
if(q->lchild==null) /*若被删除得结点无左子树
if(q==p->lchild)
p->lchild=q->rchild;
else
{ r=r->rchild;
while(r->rchild!=null) /*查找中序前趋
r=r->rchild;
r->rchild=q->rchild;
if(q==p->lchild)
p->lchild=q->lchild;
else
p->rchild=q->lchild;
}
free(q);
}
/*主程序
main()
{ bitree *root,*p,*q;
int k;
root=creatord();
inorder(root);
scanf(“%d”,&k);
bintreedele(root,k);
inorder(root);
}
题目三 斐波那契（Fibonacci）检索算法
[实现提示]
斐波那契检索是利用数列Fibonacci进行的一种检索的方法首先给出数列如下：
f0=0 n=0
f1=1 n=1
……,
fn=fn-1+fn-2 n>=2;
从而可得斐波那契序列为：0，1，2，3，5，8，13，21，…..假设利用一个数组r来存放斐波那契数列，且r数组中的元素按关键字从小到大的顺序排列，并且假定元素个数n比某个Fibonacci数fm小1，即n=Fm- 1，第一次，用要检索的关键字key与r[fm-1].key进行比较，其算法思想为：
（1）若key=r[fm-1].key，则检索成功，r[fm-1]为key所在记录
（2）若key<r[fm-1].key，则下一次检索时再从1到fm-1 -1的范围内进行，此时序列长度为fm-1;
（3）key>r[fm-1].key，则下一次检索在从下标从fm-1 +1到fm -1的范围内进行，此时该序列的长度为(fm –1)-(fm-1 +1)+1=fm-fm-1 –1=fm-2 -1，从而可得到：
设r为顺序存储的线性表，则：
r[1].key ( r[2].key (……,( r[n].key
key为已知的关键字，在r中检索关键字为key的记录，若找到，则返回其下标，否则返回0。假定m为Fibonacci数列的序号，则有fm+i=n+1(i ( 0,fm+1>i+1,n为记录元素个数)。
[算法实现]
首先可定义一个递归函数，求Fibonacci数列的函数
int Fibonacci(n)
int n;
{ if(n==0)
return(0);
else
if(n==1)
return(1);
else
return (Fibonacci(n-1)+Fibonacci(n-2));
}
然后再给出Fibonacci数列检索的算法：
#define keytype int;
#define datatype int;
type struct
{ keytype key;
datatype other;
} rectype;
Fibonaccisrch(r,k,n)
rectype r[ ];
keytype k;
int n;
{ int i,p,q,t,m,flag;
i=Fibonacci(m-1); /*设m为 Fibonacci数列序号
P=Fibonacci(m-2)；
Q=Fibonacci(m-3);
S=n+1-(i+p);
if(k>r[i].key
i=i+s;
Flag=false;
While((i))&&(!flag))
Switch
{ case k==r[i].key,flag=ture;
break; /*检索成功
case k<r[i].key,if(q==0) /*检索失败
i=0;
else
{ i=i-q;
t=p;
p=q;
q=t-q;
}
break;
case k>r[i].key,if(p==1)
i=0; /*检索失败
else
{ i=i+q;
P=p-q;
q=q-p;
}
break;
default: }
return (i);
}
实验七 排序一、实验目的掌握常用的排序方法，并掌握用高级语言实现排序算法的方法。
深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用。
3、了解各种方法的排序过程及其依据的原则，并掌握各种排序方法的时间复杂度的分析方法。
二、实验内容题目一 成绩统计算法
[问题描述]
给出n个学生的考试成绩表，每条信息由姓名和分数组成，试设计一个算法：
（1）、按分数高低次序，打印出每个学生在考试中获得的名次，分数相等的为同一名次；
（2）、按名次列出每一个学生的姓名和分数。
[基本要求]
学生的考试成绩表必须通过键盘输入数据而建立，同时要对输出进行格式控制。
[算法实现]
下面给出的是用直接选择排序算法实现的C语言程序。在此基础上还可以尝试用直接插入、shell排序、冒泡排序、快续排序、归并排序等算法实现对本问题的求解
#define n 30
typedef struct student
{ char name[8];
int score;
} student r[n];
/*用直接选择排序算法统计学生成绩排名
main()
{ int num,i,j,max,temp;
printf(“\n请输入学生成绩\n”);
for(i=0;i<n;i++)
{ printf(“姓名：“)；
scanf(“%c”,stu[i].name);
scanf(“%4d”,&stu[i].score);
}
num=1;
for(i=0;i<n;i++)
{ max=i;
for(j=i+1;j<n;j++)
if(r[j].score>r[max].score)
max=j;
if(max!=i)
{ temp=r[max];
r[max]=r[i];
r[i]=temp;
}
if((i>0)&&(r[i].score<r[i-1].score))
num=num+1;
printf(num,r[i].name,r[i].score);
}
}
题目二 最小意义关键字优先的基数排序法
[基本要求]
采用最小意义关键字优先的基数排序法，实现对数列的排序，数列中的每个数据由d位数字组成，不足 d位的数据高位补0。
[算法提示]
设待排序数据序列为r1,r2,r3…..rn,他们各自的关键字为k1,k2….kn;其中每个关键字由d个分量组成，kid,kid-1…ki1,其中ki1位最大意义关键字分量，kid为最小意义关键字分量，从而将数据按关键字分量kid,kid-1…ki1的顺序对数据排序。
设待排序的数据均由3位数组成，即d=3;显然，每个数据由分量ki3,ki2,ki1组成，ki1表示第一位，ki2 表示第二位,ki3表示第三位。
由于待排序数据为数列，则每位上的数据由0-9种的某个数组成，故可设置10个队列，用数组f和e的元素fi,ei 分别表示队列的开头和结尾（i=0~9）,只要每一次排序前先将各队列置空，然后按ki3,ki2,ki1的顺序对其排序即可。
为了使排序过程尽可能地不进行数列中数据的移动，可设计结点为一个含关键字域key和指针域next的结构体。于是，第i个队列由fi和ei分别存放该队列中的第一个数据和最后一个数据在数列中的位置的下标值。数列在进行排序前、之后及排序过程中，各队列中各个数据的先后顺序通过指针域next的链域来实现，可由变量p来指示排序后这个有序数列的第一个元素的位置。
[算法实现]
#define d 3 /*关键字位数为3
#define m 10 /*基数10
typedef struct
{ int key[d]; /*关键字由d个分量组成
int next; /*静态指针域next
datatype other; /*其他域
} rectype;
typedef struct
{ int f,e; /*n个队列的首指针，和尾指针
} queue;
queue b[m]; /*用队列表示
/*对r[0]到r[n-1]进行基数排序，返回收集用的链头指针
int basesort（r）
rectype r[ ];
{ int i,j,k,t,p;
for(i=0;i<n;i++) /*将 r[0]到r[n-1]链成一个静态表
r[i].next=i+1;
r[n-1].next= -1; /*将初始链表的终端结点指针置空
p=0; /*p指针指向静态链表的第一个结点
for(j=d-1;j>=0;j--) /*进行d趟排序
for(i=0;i<m;i++) /*清空队列
{ b[i].f=-1;
b[i].e=-1;
}
while(p!=-1) /*按关键字第j个分量进行分配
{ k=r[p].key[j];
if(b[k].f==-1)
b[k].p; /*对列为空时，将 r[p]链到队列头部
else
r[b[k].e].next=p; /*否则对列非空将r[p]链到队尾
b[k].e=p; /*修改对列的尾指针
p=r[p].next; /*扫描下一个记录
}
i=0;
While(b[i].f== -1) /*检索第一个非空队列
i++;
t=b[i].e;
p=b[i].f /p为收集链表的头指针
while(i<m-1) /*检索下一个队列
{ i++;
if(b[i].f!=-1) /*队列非空时,链接
{ r[t].next=b[i].f;
t=b[i].e;
r[t].next=-1; /*本趟收集完毕,将链表的终端结点指针置空 }
return p;
}
题目三 堆排序算法
[基本要求]
写出在含有n个元素的堆中增加一个元素，且调整为堆的算法程序。
[算法提示]
由于堆可看成一棵完全二叉树，所以可以用一个数组r[1]至r[n+1]表示一个堆。其中r[1]到r[n]表示原始堆中的各个元素，r[n+1]用于存放新插入的元素。由于原来的n个元素已经构成堆，则当插入一个元素时，有可能破坏堆的结构，所以需依据情况进行调整，此时仅需要从r[n+1]出发，走一条从叶子结点r[n+1]到根结点r[1]的路径（设为小根堆）。每次就该结点r[j]和其双亲结点r[i]进行比较，若r[j].key>r[i].key，此时算法结束，不需要进行调整；此时r[1]到r[n+1]即成为堆，否则，将r[i]与r[j]进行交换，继续和上一层结点比较，直到根结点为止。
[算法实现]
#define n 15
#define datatype int
typedef struct
{ int key; /*关键字域
datatype other; /*其它域
} rectlype;
rectype r[n];
/*在堆r[1]到r[n]中插入一个新元素
heapinsert(r,x)
rectype r[ ];
datatype x;
{ int i,j;
j=n+1;
while(j>1)
{ i=j/2; /*求结点kj的双亲结点ki
if(r[i].key<x.key) /*若此时为堆跳出循环
j=1;
else
{ r[j]=r[i];
j=i;
} /*不为堆，再调整
}
r[i]=x; /*x插入正确的插入位置
}
/*主程序
main()
{ int n,i;
datatype x;
for(i=1;i<=n;i++)
{ scanf(“%d”,r[i]);
printf(“%d”,r[i]);
}
scanf(“%d”,&x);
heapinsert(r,x);
for(i=1;i<=n+1;i++)
printf(“&d”,r[i]);
}
题目四 字符串排序算法
[基本要求]
输入若干国家名称，按字典顺序将这些国家进行排序（设所有的名称均用大写或小写表示）。
[算法提示]
本题实质是对一些字符串进行排序，可以用直接选择排序或shell排序等，这里shell采用排序。Shell排序又称“缩小增量排序”。它的做法是：先取一个小于n的整数d１作为第一个增量，把文件的全部记录分成d1个组，所有距离为d1倍数的记录放在同一个组中，在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述分组和排序，直至所取得增量dt=1(dt<dt-1…<d1)，即所有记录放在同一组中进行直接插入排序为止。
[算法实现]
/*按字典顺序将这些国家进行排序
main()
{ string r[ ];
string temp;
int i,h,n,change;
scanf(“%d”,&n);
printf(“input country name\n”);
for(i=0;i<n;i++)
scanf (r[i]);
h=n;
while(h>0)
{ h=h/2; /*取增量h/2
do
{ change=false;
for(i=0;i<n-h;i++)
if(r[i]>r[i+h]) /*比较r[i]与r[i+h]
｛ temp=r[i]; /*交换
r[i]=r[i+h];
r[i+h]=temp;
change=true; /*置已交换标志
}
} while(!change);
}
printf(“output country name\n”);
for(i=0;i<n;i++)
printf(r[i]);
}
综合实验题目一 索引文件系统的使用操作
[基本要求]
假定一个以ElemType为记录类型的主文件存于D：盘LL子目录的test1.data文件中，他的索引文件存于同一目录下的test1.idx中。索引文件中的每个索引项对应主文件中的一个记录，每个记录项包含两个域：一是索引值域，又称关键字域（key），用来存储对应记录的关键字；二是记录位置域（next），用来存储对应记录在主文件的位置编号，若若主文件中包含n个记录，则next域的取值范围在0 ~ n-1之间。另外，主文件中记录的排列次序可以任意排列，即不强求按关键字有序，而索引文件是按关键字从小到大排列的有序文件。在这种带有主文件和索引文件的整个文件系统中当向主文件的末尾插入一条记录后，还要把它的索引项插入到索引文件中；当删除一条记录时，首先从索引文件中删除掉对应的索引项，然后把主文件中的被删除的记录的关键字域置为特定的值以作为删除标记即可，而不需要真正从物理上删除它；当查找一条记录时，是先查找索引文件得到对应的索引项，然后根据索引项中所含的记录位置从主文件中取出记录。由此可知，对这种文件系统的操作主要开销在对索引文件的操作上。试按照下列每一项功能编写出相应的算法程序：
向索引文件中插入一条记录的索引项（在文件系统中插入记录）；
从索引文件中删除一条记录的索引项（在文件系统中删除记录）；
从索引文件中二分查找一条记录的索引项（在文件系统中查找记录）；
[算法提示]
有题意可知，索引文件是有序文件，对索引文件的插入和删除操作都是在有序文件上进行的，操作后仍是有序文件。按二进制方式使用的文件，每次存取一个数据块的信息，一个数据块可以包含一个或若干个记录。一个数据块通常小于等于外存上的一个物理块，而一个物理块的大小通常为210即1024个字节，他是进行一次外存访问操作的信息交换单位。当从有序文件中顺序查找一个记录的插入或删除位置时，不是使每个记录的关键字同给定关键字进行比较，而是使每个数据块中的最大关键字（即该块中最后一个记录的关键字）同给定关键字进行比较，若前者小于后者，则继续访问下一个数据块并比较，否则。待插入或删除的位置必然落在本块中。
假定主文件test1.dat中记录的类型ElemType可定义为：
struct ElemType { //主文件中的记录类型
KeyType key; //关键字域
int rest; //其它域，假设用整形rest表示
}
索引文件test1.idx中类型可定义为：
struct IndexItem { //索引文件中的记录类型
KeyType key; //关键字域
int next; //保存对应记录的存储位置域
}
而关键字的类型KeyType可事先通过typedef语句定义为整形：
typedef int KeyType;
一个数据块中所含的索引项个数m和每个索引项的大小b可分别用下面语句定义为全局变量：
const int m=100; //m可定义为大于等于1的任意整数
const int b=sizeof(IndexItem); //保存索引文件中的记录长度以上定义仅供参考，其它算法（略）
题目二 散列文件的使用操作
[基本要求]
在外存磁盘上建立一个散列文件，按照下列功能编写出相应算法：
初始化散列文件；
向散列文件中插入一个元素；
向散列文件中一次插入n个元素；
从散列文件中删除一个元素；
从散列文件中查找一个元素。
[算法提示]
散列存储方式不仅适用与内存，也同样适用于外存，即文件也可以采用散列方式存储，以散列方式存储的文件称为散列文件。散列文件通常采用链接法处理冲突，并且把保存每个单链表表头指针的表头向量用一个文件单独存储起来，称此为散列表文件，把所有单链表中的结点用一个文件单独存储起来，称此为散列主文件。散列主文件中每个结点的类型可定义为：
struct FLNode { //散列主文件中的结点类型
ElemType data; //值域
int next; 指向下一个结点的指针域
}
其中data域用来存储待散列的元素，next域用来存储下一个同义词元素在散列主文件中的存储位置，即所在结点的位置序号。散列主文件中第一个结点的位置序号为0，字节地址为0，第二个结点的位置序号为1，字节地址为sizeof (FLNode)，第三个结点的位置序号为2，字节地址为2* sizeof (FLNode)，依次类推。当一个结点为同义词单链表中的最后一个结点时，则next域为空，假定用数值-1表示。
散列表文件中、每一个结点的类型为整形int，每个结点的值为指定对应单链表的第一个结点的位置序号。若相应的单链表不存在，则该结点的值为空，同样用数值-1表示。散列表文件中每个结点的初始值均为-1。
初始化散列表文件时，首先按输出方式打开并建立散列表文件和散列主文件，接着动态分配一个具有m+1个整数位置的数组空间A，然后把A中的每个元素君置为-1，表示空指针，最后把数组内容写入散列表文件即可。
向散列文件中插入一个元素x时，首先根据元素的关键字x.key，散列表长度m和所选择的任一散列函数计算出散列地址d，接着为x生成一个内存结点，并使该结点的next域为散列表文件中位置d的元素值（即表头指针），然后把该内存结点的值写入到散列主文件的一个空闲结点中，若不存在空闲结点则写入到该文件的末尾，最后把该结点在散列主文件中的序列赋给散列表文件中位置d的元素中，使得新插入的结点被链接到散列地址为d的单链表的表头。
向散列文件中一次插入n个元素的操作，是上述插入一个元素过程的重复，当然算法开始时的打开文件和结束时的关闭文件是不需要重复的。
从散列文件中删除一个关键字为x.key的元素时，首先是计算出散列地址d，接着从散列表文件中下标为d的位置取出对应单链表的表头指针，然后遍历该单链表从中查找出关键字为x.key的结点，并从单链表中删除该结点，其元素值由x带回，最后把被删除的结点链接到空闲结点表的表头。假定空闲结点表的表头指针保存在散列表文件中下标为m的位置，若该位置为-1，则表明散列主文件中不存在空闲结点。
从散列文件中查找一个关键字为x.key的元素时，同样是首先计算出散列地址d，接着从散列表文件中下标为d的位置取出对应单链表的表头指针，然后从单链表中顺序查找出对应的元素并由x带回。
主要全局类型和常量说明：
const int m=13; //定义散列表长度，其值取决于待散列的元素数量和选取的装填因子(的大小。
Typedef int KeyType; //定义关键字类型
Struct ElemType { //元素类型
KeyType key; //关键字域
int rest; //其它域
}；
Struct FLNode; { //索引主文件中的结点类型
ElemType data; //值域
int next; //指向下一个结点的指针域
}；
const int b1=sizeof(int); //保存索引表文件中的记录长度
const int b2=sizeof(FLNode);//保存索引主文件中的记录长度以上定义仅供参考，其它算法（略）
