上篇程序设计基础
实验1 数据类型、运算符和表达式
一、 实验目的：
1．掌握C语言数据类型，熟悉如何定义整型、字符型、实型变量，以及对它们赋值的方法，了解以上数据类型输出时所使用的格式转换符号。
2．学会使用C的有关运算符，以及包含这些运算符号的表达式，特别是自加(++)和自减(——)运算符的使用。
3．进一步熟悉C程序的编辑、编译、连接和运行的过程。
二、 实验内容：
1．输入以下程序，并编译、运行，分析运行结果：
main()
{ char c1,c2;
c1=97;c2=98;
printf(″% c %c″,c1,c2);
}
运行输出结果a,b
2．输入并运行以下程序：
main()
{ int i,j,m,n;
i=8;j=10;
m=++i;n=j++;
printf(″%d,%d,%d,%d″,i,j,m,n);
}
分别作以下改动并运行：
(1)将第四行改为： m=i++;n=++j;
运行输出结果9,11,8,11
(2)程序改为：
main()
{ int i,j;
i=8;j=10;
printf(″%d,%d″,i++,j++);
}
运行输出结果8，10
(3)在(2)的基础上，将printf语句改为：
printf(″%d,%d″,++i,++j);
运行输出结果9,11
(4)再将printf语句改为：
printf(″%d,%d，%d,%d″,i,j,i++,j++);
运行输出结果8,10,8,10
(5)程序改为：
main()
{ int i,j,m=0,n=0;
i=8;j=10;
m+=i++;n-=--j;
printf(″i=%d,j=%d，m=%d,n=%d″,i,j,m,n);
}
运行输出结果i=9,j=9,m=8,n=-9
3.先判断以下程序的输出结果，再运行验证。
main()
{ int i=3,j=2,a,b,c,d;
d=(i*3,j=10);
a=(--i==j++)? --i:++j;
b=i++;
c=j;
printf(″%d,%d，%d,%d\n″,a,b,c,d);
}
运行输出结果12,2，12,10
实验2 顺序程序设计
一、 实验目的：
1．掌握赋值语句的使用。
2．掌握数据的输入输出方法，能正确使用各种格式转换符。
二、 实验内容：
1.输入以下程序：
#include "stdio.h"
main()
{
int i;
char j;
for(i=1;i<10;i++)
{
scanf("%c",&j);
printf("%c",j);
}
}
(1)运行程序，输入a↙b↙c↙d↙e↙f↙g↙h↙i↙
观察程序的执行结果，是否能够输出字母a,b,c,d,e,f,g,h,i。为什么？
能够输出abcdefghi
(2)在scanf语句后面加上语句：
getchar();
运行程序，输入a↙b↙c↙d↙e↙f↙g↙h↙i↙
观察程序的执行结果，是否能够输出字母a,b,c,d,e,f,g,h,i。为什么？
不能输出abcdefghi，输出结果为acegi
2.编制一程序，用getchar函数输入字符，然后用putchar函数输出字符，同时要求输出字符的ASCII码。分别考虑用int和char型变量来接收键盘输入的字符，两者是否等价？
（1）
#include "stdio.h"
void main()
{
char c;
printf("请输入一个字符!\n");
c=getchar();
putchar(c);
printf("\n");
printf("%d\n",c);
}
（2）
#include "stdio.h"
void main()
{
int c;
printf("请输入一个字符!\n");
c=getchar();
putchar(c);
printf("\n");
printf("%d\n",c);
}
实验3 逻辑运算和判断选取控制
一、 目的要求
1．了解C语言表示逻辑量的方法(以0代表“假”，以1代表“真”)；
2．学会正确使用逻辑运算符和逻辑表达式；
3．熟练掌握if语句和switch语句
二、 实验内容
先编程序，解以下问题，然后上机调试运行程序。
1．编写一程序，从键盘输入字符，判别输入字符是数字、大写字母还是小写字母，输出判别结果。
#include <stdio.h>
void main()
{
char c;
printf("请输入一个字符！\n");
c=getchar();
if (c>='a'&& c<='z')
printf("你输入的是小写字母");
else if (c>='A'&& c<='Z')
printf("你输入的是大写字母");
else if (c>='0'&& c<='9')
printf("你输入的是数字");
printf("\n");
}
运行效果图：
2．给出一个不多于5位的正整数，要求：
(1)求出它是几位数；
(2)分别打印出每一位数字；
(3)按逆序打印出各位数字。
#include <stdio.h>
#include <math.h>
void main()
{
long int num;
int a,b,c,d,e,m;
printf("请输入一个整数(0~99999):");
scanf("%d",&num);
if(num>9999)
m=5;
else if(num>999)
m=4;
else if(num>99)
m=3;
else if(num>9)
m=2;
else
m=1;
printf("位数=%d\n",m); /*也可这样写，如下*/
e=(int)(num/10000); /*e=num/10000%10；*/
d=(int)(num-e*10000)/1000; /*d=num/1000%10；*/
c=(int)(num-e*10000-d*1000)/100; /*c=num/100%10；*/
b=(int)(num-e*10000-d*1000-c*100)/10; /*b=num/10%10；*/
a=(int)(num-e*10000-d*1000-c*100-b*10); /*a=num%10；*/
printf("每位数字为：");
switch(m)
{
case 5: printf("%d,%d,%d,%d,%d",e,d,c,b,a);
printf("\n反序数字为：");
printf("%d%d%d%d%d\n",a,b,c,d,e);
break;
case 4: printf("%d,%d,%d,%d",d,c,b,a);
printf("\n反序数字为：");
printf("%d%d%d%d\n",a,b,c,d);
break;
case 3: printf("%d,%d,%d",c,b,a);
printf("\n反序数字为：");
printf("%d%d%d\n",a,b,c);
break;
case 2: printf("%d,%d",b,a);
printf("\n反序数字为：");
printf("%d%d\n",a,b);
break;
case 1: printf("%d",a);
printf("\n反序数字为：");
printf("%d\n",a);
break;
}
}
3．有一函数，
，用scanf函数输入任意x的值，求y的值。
#include <stdio.h>
main()
{
int x,y;
printf("请输入x的值\n");
scanf("%d",&x);
if(x<1)
y=x*x;
else if(x>=1&x<10)
y=2*x-1;
else if(x>10)
y=3*x-1;
printf("y的值为:,%d\n",y);
}
实验4 循环控制
一、 实验目的
1．熟悉用while语句，do-while语句和for语句实现循环的方法。
2．掌握在程序设计中用循环的方法实现各种算法(如穷举、迭代、递推等)。
二、 实验内容
编写程序并上机调试运行。
1．输入一行字符，分别统计出其中的英文字母、空格、数字和其它字符的个数。
#include<stdio.h>
main()
{
char c;
int w=0,x=0,y=0,z=0;
while((c=getchar())!='\n')
{if((c>='a'&& c<='z')||(c>='A' && c<='z'))
w++;
else if (c==' ')
x++;
else if (c>='0' && c<='9')
y++;
else
z++;
}
printf("w=%d,x=%d,y=%d,z=%d\n",w,x,y,z);
}
2．输出九九表。
#include<stdio.h>
main()
{
int i,j;
for(i=1;i<10;i++)
printf("%4d",i);
printf("\n------------------------------------\n");
for(i=1;i<=9;i++)
for(j=1;j<=9;j++)
{
if(j==9)
printf("%4d\n",i*j);
else
printf("%4d",i*j);
}
printf("\n");
}
实验5 数组
一、 目的要求
1．掌握一维数组和二维数组的定义、赋值和输入输出的方法；
2．掌握字符数组和字符串函数的使用；
3．掌握与数组有关的算法(特别是排序算法)。
二、 实验内容
1．编写一程序，从键盘输入任意两个字符串，然后将两个字符串连接起来，不要使用strcat函数。
#include <stdio.h>
main ()
{
char s1[80],s2[40];
int i=0,j=0;
printf("输入字符串1:");
scanf("%s",s1);
printf("输入字符串2:");
scanf("%s",s2);
while (s1[i]!='\0')
i++;
while (s2[j]!='\0')
s1[i++]=s2[j++];
s1[i]='\0';
printf("The new string is:%s\n",s1);
}
2．编写一程序，从键盘输入任意两个字符串s1和s2，然后比较字符串的大小(字符串比较是从左到右逐位比较)，如果s1>s2，输出1；s1=s2，输出0；s1<s2，输出-1。
#include<stdio.h>
main ( )
{
int i;
char s1[100],s2[100];
printf("输入字符串1:");
gets (s1);
printf("输入字符出2:");
gets (s2);
for(i=0;i<100;i++)
{
if(s1[i]>s2[i])
printf("1\n");
else if(s1[i]==s2[i])
printf("0\n");
else
printf("-1\n");
break;
}
}
3． 编写一程序，输入一字符串到数组中，然后将该数组中小写字母转换为大写字母，并复制到另一字符数组中。(复制时，‘\0’也要复制过去)
#include <stdio.h>
void main()
{
int i;
char s1[100],s2[100];
printf("请输入一串字符：\n");
scanf("%s",s1);
for(i=0;i<100;i++)
{
if(s1[i] >='a'&&s1[i]<='z')
s2[i]=s1[i]-32;
else
s2[i]=s1[i];
}
printf("字符串转换为：\n%s\n",s2);
}
实验6 函数
一、 目的要求
1．掌握定义函数的方法；
2．掌握函数实参与形参的对应关系，以及“值传递”的方式；
3．掌握函数的嵌套调用和递归调用的方法；
4．掌握全局变量和局部变量、动态变量和静态变量的概念和使用方法。
二、 实验内容
1．输入一行字符串，然后写一函数输出该行字符串中最长的单词。例如I am a student中最长的单词为student。
#include<stdio.h>
#include<string.h>
void main()
{
int i,j=0,len,m,a,b;
char str[80];
char c[100]={0};
printf("输入一行字符：\n");
gets(str);
len=strlen(str);
for(i=0;i<=len;i++)
if(str[i]==' '||str[i]=='\0')
{
c[j]=i;
j++;
}
for(m=1;m<=j;m++)
{
if((c[m]-c[m-1])>c[99])
{
c[99]=c[m]-c[m-1];
a=c[m];
b=c[m-1];
}
else c[99]=c[99];
}
for(i=b+1;i<=a-1;i++)
printf("%c",str[i]);
printf("\n");
}
2．写一个判断素数的函数，在主函数中输入一个整数，输出是否素数的信息。
#include<stdio.h>
#include<math.h>
void main()
{
int m,i;
printf("输入一个数：\n");
scanf("%d",&m);
for(i=2;i<=m-1;i++)
{
if(m%i==0)
break;
}
if(m!=i)
printf("%d不是素数",m);
else
printf("%d是素数",m);
}
实验7 指针
一、 实验目的：
1．掌握指针的概念，会定义和使用指针变量；
2．学会使用数组的指针和指向数组的指针变量；
3．学会使用字符串的指针和指向字符串的指针变量；
4．学会使用指向函数的指针变量；
5．了解指向指针的指针的概念及其使用方法。
二、 实验内容：
1．编制一函数实现任意3*3阶矩阵的转置，函数的参数用指针形式。在主函数中输入矩阵元素。
#include<stdio.h>
void main()
{
void cm(int (*p1)[3],int (*p2)[3]);
int a[3][3],b[3][3];
int (*pa)[3],(*pb)[3],i,j;
pa=a;pb=b;
for(i=0;i<3;i++)
for(j=0;j<3;j++)
scanf("%d",*(pa+i)+j);
printf("array a:\n");
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
printf("%5d",a[i][j]);
printf("\n");
}
cm(pa,pb);
printf("array b:\n");
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
printf("%5d",b[i][j]);
printf("\n");
}
}
void cm(int (*p1)[3],int (*p2)[3])
{
int i,j;
for(i=0;i<3;i++)
for(j=0;j<3;j++)
*(*(p2+i)+j)=*(*(p1+j)+i);
}
2．从键盘输入任意两个字符串s1和s2，然后用函数实现比较字符串的大小(字符串比较是从左到右逐位比较)，如果s1>s2，函数返回1；s1=s2，函数返回0；s1<s2，函数返回 -1。函数的参数采用指针形式。
#include<stdio.h>
void main()
{
char s1[30],s2[30];
int i,j;
char *p,*q;
p=s1;q=s2;
printf("请输入字符串s1:\n");
gets(s1);
printf("请输入字符串s2:\n");
gets(s2);
while(*p!='\0'&&*q!='\0'&&*p==*q)
{
p++;
q++;
}
if(*p>*q)
printf("1\n");
else if(*p==*q)
printf("0\n");
else
printf("-1\n");
}
实验8 结构体
一、 目的要求：
1．掌握结构体类型变量的定义和使用；
2．掌握结构体类型数组的概念和应用；
3．掌握链表的概念，初步学会对链表进行操作；
二、 实验内容：
1．有5个学生，每个学生的数据包括学号、姓名、三门课的成绩，从键盘输入5个学生的数据，要求打印出三门课总平均成绩，以及最高分的学生的数据(包括姓名、学号、三门课的成绩、平均分数)。要求用一个input函数输入成绩；用average函数求总平均分；用max函数找出最高分学生数据；总平均分和最高分的学生的数据在主函数中输出。
#include<stdio.h>
#define N 5
struct student
{ char num[6];
char name[8];
float score[3];
float avr;
} stu[N];
void main()
{ int i,j,maxi;
float sum,max,average;
for(i=0;i<N;i++)
{printf("input score of student %d:\n",i+1);
printf("No.:");
scanf("%s",stu[i].num);
printf("name:");
scanf("%s",stu[i].name);
for(j=0;j<3;j++)
{printf("score %d:",j+1);
scanf("%f",&stu[i].score[j]);
}
}
average=0;
max=0;
maxi=0;
for(i=0;i<N;i++)
{sum=0;
for(j=0;j<3;j++)
sum+=stu[i].score[j];
stu[i].avr=sum/3.0;
average+=stu[i].avr;
if(sum<max)
{max=sum;maxi=i;}
}
average/=N;
printf(" No. name scorel score2 score3 average\n");
for(i=0;i<N;i++)
{printf("%5s%10s",stu[i].num,stu[i].name);
for(j=0;j<3;j++)
printf("%9.2f",stu[i].score[j] );
printf(" %8.2f\n",stu[i].avr );
}
printf("average=%5.2f\n",average);
printf("The highest score is:student %s,%s.\n",stu[maxi].num,stu[maxi].name );
printf("His scores are: %6.2f,%6.2f,%6.2f,average:%5.2f.\n",stu[maxi].score[0],
stu[maxi].score[1],stu[maxi].score[2],stu[maxi].avr);
}
2．建立一个链表，每个结点包括：学号、姓名、性别、年龄。输入一个年龄，如果链表中的结点所包含的年龄等于此年龄，则将此结点删除。
#include<stdio.h>
#include<malloc.h>
#define LEN sizeof(struct student)
struct student
{
char num[6];
char name[8];
char sex[2];
int age;
struct student *next;
} stu[10];
void main()
{
struct student *p,*pt,*head;
int i,length,iage,flag=1;
int find=0;
while(flag==1)
{
printf("input length of list(<10):");
scanf("%d",&length);
if(length<10)
flag=0;
}
for(i=0;i<length;i++)
{
p=(struct student *)malloc(LEN);
if(i==0)
head=pt=p;
else
pt->next=p;
pt=p;
printf("No.:");
scanf("%s",p->num);
printf("name:");
scanf("%s",p->name);
printf("sex:");
scanf("%s",p->sex);
printf("age:");
scanf("%d",&p->age);
}
p->next=NULL;
p=head;
printf("\n No. name sex age\n");
while(p!=NULL)
{
printf("%4s%8s%6s%6d\n",p->num,p->name,p->sex,p->age);
p=p->next;
}
printf("input age:");
scanf("%d",&iage);
pt=head;
p=pt;
if(pt->age==iage)
{
p=pt->next;
head=pt=p;
find=1;
}
else
pt=pt->next;
while(pt!=NULL)
{
if(pt->age==iage)
{p->next=pt->next;
find=1;
}
else
p=pt;
pt=pt->next;
}
if(!find)
printf(" not found %d.",iage);
p=head;
printf("\n No. name sex age\n");
while(p!=NULL)
{
printf("%4s%8s",p->num,p->name);
printf("%6s%6d\n",p->sex,p->age);
p=p->next;
}
}
下篇 数据机构
实验一 线性表的顺序表示和实现
一、 实验目的
1、理解线性表的逻辑结构特性；
2、熟练掌握线性表的顺序存储结构的描述方法，以及在该存储结构下的基本操作。
二、 实验内容
实验1.1 用线性表的顺序存储结构实现十项基本操作：初始化、求长度、取元素、求前导、求后继、查找、插入、删除、判定空表、置空，生成sqlist.h文件；编写main函数调用。
【提示】sqlist.h文件的代码实现线性表的顺序存储结构的基本操作；另建一个顺序表.cpp文件实现main函数，以用户交互的方式调用顺序表的各个功能。
（1） 操作步骤：
对于这个实验是用线性表的顺序存储结构实现的十项基本操作，程序量比较大，需要按提示中的通过用户交互方式调用顺序表的各功能。
（2） 程序代码：
MysqList.cpp文件中的代码：
#include <iostream.h>
#include "MysqList.h"
void main()
{ sqlist L;
int x,i,e,aa=1,bb;
cout<<" 1.用户生成线性表."<<endl;
cout<<" 2.自动生成线性表."<<endl;
cout<<" 3.插入元素."<<endl;
cout<<" 4.删除元素."<<endl;
cout<<" 5.删除多余的元素."<<endl;
cout<<" 6.打印线性表."<<endl;
cout<<" 7.打印线性表长度."<<endl;
cout<<" 8.查找元素e的位置."<<endl;
cout<<" 9.查找第i个元素的值."<<endl;
cout<<" 10.置空线性表."<<endl;
cout<<" 11.判断表是否为空."<<endl;
cout<<" 12.退出."<<endl<<endl;
while(aa)
{cout<<endl<<endl;
cout<<"请选择一项操作的编号!(1/2/3/4/5/6/7/8/9/10/11/12):";
cin>>x;
switch(x)
{case 1:creat_Sqlist(L);break;
case 2:cout<<"1 2 3 4 5 6 7"<<endl;break;
case 3:cout<<"请输入插入的元素值! e=";
cin>>e;
cout<<"请输入插入位置! i=";
cin>>i;
bb=Listinsert_Sq(L,i,e);
if(bb==ERROR)cout<<"不合理的插入位置";
if(bb==OVERFLOW)cout<<"表已满,溢出";break;
case 4:cout<<"请输入删除元素的位置! i=";
cin>>i;
Listdelete_Sq(L,i);break;
case 5:Deletesame(L);break;
case 6:prt_sqlist(L);break;
case 7:cout<<"线性表长度="<<ListLength(L);break;
case 8:cout<<"请输入查找的元素值! e=";
cin>>e; bb=LocateElem(L,e);
if (bb==0) cout<<"元素"<<e<<"未找到。";
else cout<<"元素e="<<e<<"的位置是"<<LocateElem(L,e);;break;
case 9:cout<<"请输入查找元素的位置! i=";
cin>>i;
if(GetElem(L,i)) cout<<"第"<<i<<"元素的值是="<<GetElem(L,i);
else cout<<"输入的位置不对"<<endl; break;
case 10: ClearList(L);break;
case 11: ListEmpty(L);break;
case 12: aa=0;
}
}
}
MysqList.h文件中的代码：
//线性表的操作实现（顺序存储结构）
//编号从1开始，编号为0的元素放弃不用
#include <iostream.h>
const OK=1;
const ERROR=0;
const TRUE=1;
const FALSE=0;
const OVERFLOW=-2;
const UNDERFLOW=-1;
const MAXSIZE=20;
//结构定义
typedef struct {
int *elem; //存储空间基址,即用指针表示数组的方法
int len; //线性表的当前表长
}sqlist;
//初始化
void creat_Sqlist(sqlist &L)
{int i=1,x;
L.elem=new int[MAXSIZE];
cout<<"请输入线性表的元素,输入0结束! "<<endl;
do
{cin>>x;L.elem[i]=x; i++;}
while(x!=0);
L.len=i-2;// L.elem[i]=0后i又加1，所以i-2
}
//求长度
int ListLength(sqlist L)
{
return L.len;
}
//获取线性表第I个元素(1<=i<=L.len)
int GetElem(sqlist L,int i)
{if (i<1||i>L.len) return ERROR;
return L.elem[i];}
//查找元素e的位置
int LocateElem(sqlist L, int e)
{ int i;
L.elem[0]=e; //设哨兵
for(i=L.len;L.elem[i]!=e;--i){}
return i;
}
//插入算法：在线性表的第i-1和第i元素之间插入一个新元素e
int Listinsert_Sq(sqlist &L ,int i, int e)
{int j;
if(i<1 || i>L.len+1) return ERROR; //不合理的插入位置 i
if ( L.len==MAXSIZE) return OVERFLOW; // 表已满
for (j=L.len;j>=i;--j)
L.elem[j+1]=L.elem[j]; // 插入位置后的元素右移
L.elem[i]=e; //插入e
++L.len; //表长加1
return OK;
}
//删除算法：删除线性表中第个i元素。
int Listdelete_Sq(sqlist &L,int i)
{ int j;
if (i<1 || i>L.len) return ERROR; //不合理的删除位置 i
if (L.len==0) return UNDERFLOW; //表已空
for (j=i;j<=L.len-1;j++)
L.elem[j]=L.elem[j+1]; //被删除元素之后的元素左移
--L.len; //表长减1
return OK;
}
//删除非递减线性表中多余的相同元素
int Deletesame(sqlist &L)
{int i;
if (L.len<=1) return ERROR;
i=1;
while ( i<L.len)
if (L.elem[i]==L.elem[i+1]) Listdelete_Sq (L,i+1);
else i++;}
//打印
void prt_sqlist(sqlist L)
{ int i;
for(i=1;i<=L.len;i++)
cout<<L.elem[i]<<" ";
cout<<endl;
}
//置空
void ClearList(sqlist &L)
{L.len=0;}
//判断是否为空
bool ListEmpty(sqlist &L)
{ return(L.len==0); }
实验1.2 用一维数组做存储结构，就地逆置一线性表，即将结点的前趋与后继关系颠倒。如：(a1,a2,...an)逆置后为(an,an-1,...,a1)。***
（1） 操作步骤：
此实验需要用到三个循环：第一个循环式输入数组数据，第二个循环实现数组中数据的逆序，第三个循环将逆序后新数组中的数据输出。
（2） 程序代码：
#include "iostream.h"
void main()
{
int *p;
int m,j,i;
cout<<"数组元素个数"<<endl;
cin>>m;
p=new int[m];
cout<<"输入数组元素"<<endl;
for(i=0;i<m;i++)
{
cin>>p[i];
}
for(i=0;i<m/2;i++)
{
j=p[i];p[i]=p[m-i-1];p[m-i-1]=j;
}
cout<<"逆置后的结果"<<endl;
for(i=0;i<m;i++)
{
cout<<p[i]<<" ";
}
cout<<endl;
}
实验二 线性表的链式表示和实现
一、实验目的
1. 理解线性表的逻辑结构特性；
2. 熟练掌握线性表的链表存储结构的描述方法，以及在该存储结构下的基本操作；并能灵活运用；
二、实验内容
实验2.1 用线性表的链式存储结构实现十项基本操作：初始化（要求终端输入数据建立链表，可用正序或逆序中的一种生成）、求长度、取元素、求前导、求后继、查找、插入、删除、判定空表、置空，生成Llist.h文件；编写main函数调用。
【提示】Llist.h文件的代码实现线性表的链式存储结构的基本操作；另建一个链表.cpp文件实现main函数，以用户交互的方式调用顺序表的各个功能。
（1） 操作步骤：
此实验题和实验一中的题目差不多，需要理解顺序存储与链式存储的不同之处。
（2） 程序代码：
MysqList.cpp文件中的代码：
#include "MyLinkList.h"
void main()
{LinkList L=NULL,s,La=NULL,Lb=NULL;
int x,i,y,aa=1,n;
while(aa)
{cout<<endl;
cout<<" 1.逆序生成有序链表"<<endl;
cout<<" 2.在单链表中的第i个结点前插入一个元素x"<<endl;
cout<<" 3.在单链表中值为x的结点前插入一个元素y,如果x值不存在，则把y插在表尾"<<endl;
cout<<" 4.删除单链表中第i个元素"<<endl;
cout<<" 5.删除单链表中值为x的结点"<<endl;
cout<<" 6.打印线性表"<<endl;
cout<<" 7.查找元素X的位置"<<endl;
cout<<" 8.查找第i个元素的值"<<endl;
cout<<" 9.逆置单链表"<<endl;
cout<<" 10.合并两个有序表"<<endl;
cout<<" 11.退出。"<<endl;
cout<<"请选择一项操作的编号!(1/2/3/4/5/6/7/8/9/10/11):";
cin>>x;
switch(x)
{case 1:cout<<"输入链表长度n=";
cin>>n;
CreateList_L(L,n);break;
case 2:cout<<"请输入插入的元素值! x="; cin>>x;
cout<<"请输入插入位置! i="; cin>>i;
if (i<1||i>ListLength_L(L)) cout<<"输入的位置i不正确。"<<endl;
s=new LNode;s->data=x;s->next=NULL;
ListInsert_L(L,i,s);break;
case 3:cout<<"请输入 x=";
cin>>x;
cout<<"请输入插入的元素值! y=";
cin>>y;
Linklist_ins(L,x,y);break;
case 4:cout<<"请输入删除元素的位置! i=";
cin>>i;
if(i<1||i>ListLength_L(L)) cout<<"输入的位置i不正确。"<<endl;
else cout<<"删除第"<<i<<"个元素为"<<ListDelete_L(L,i)<<endl;break;
case 5:cout<<"请输入删除元素的值!X=";
cin>>x;
if(Linklist_del2(L,x)) cout<<"删除成功"<<endl;
else cout<<"链表中没有元素"<<x<<"删除失败"<<endl; break;
case 6:prt_Linklist(L);cout<<" 线性表长度="<<ListLength_L(L)<<endl;break;
case 7:cout<<"请输入查找的元素值! x=";cin>>x;
LocateElem(L,x);break;
case 8:cout<<"请输入查找元素的位置! i=";
cin>>i;
if(Getelem(L,i)) cout<<"第"<<i<<"元素的值是="<<Getelem(L,i)<<endl;
else cout<<"输入的位置不对"<<endl; break;
case 9:InvertLinkedList(L);
cout<<"逆置后的单链表: ";prt_Linklist(L);break;
case 10:cout<<"建立第一个有序表,输入链表长度:";
cin>>n;
CreateList_L(La,n);
cout<<"建立第二个有序表,输入链表长度:";
cin>>n;
CreateList_L(Lb,n);
MergeList_L(La,Lb,L);
cout<<"合并后的有序表:";prt_Linklist(L);break;
case 11: aa=0;
}
}
}
MyLinkList.h中的代码：
#include "MyLinkList.h"
void main()
{LinkList L=NULL,s,La=NULL,Lb=NULL;
int x,i,y,aa=1,n;
cout<<" 1.逆序生成有序链表"<<endl;
cout<<" 2.在单链表中的第i个结点前插入一个元素x"<<endl;
cout<<" 3.在单链表中值为x的结点前插入一个元素y,如果x值不存在，则把y插在表尾"<<endl;
cout<<" 4.删除单链表中第i个元素"<<endl;
cout<<" 5.删除单链表中值为x的结点"<<endl;
cout<<" 6.打印线性表"<<endl;
cout<<" 7.查找元素X的位置"<<endl;
cout<<" 8.查找第i个元素的值"<<endl;
cout<<" 9.逆置单链表"<<endl;
cout<<" 10.合并两个有序表"<<endl;
cout<<" 11.退出。"<<endl;
while(aa)
{
cout<<"请选择一项操作的编号!(1/2/3/4/5/6/7/8/9/10/11):";
cin>>x;
switch(x)
{case 1:cout<<"输入链表长度n=";
cin>>n;
CreateList_L(L,n);break;
case 2:cout<<"请输入插入的元素值! x="; cin>>x;
cout<<"请输入插入位置! i="; cin>>i;
if (i<1||i>ListLength_L(L)) cout<<"输入的位置i不正确。"<<endl;
s=new LNode;s->data=x;s->next=NULL;
ListInsert_L(L,i,s);break;
case 3:cout<<"请输入 x=";
cin>>x;
cout<<"请输入插入的元素值! y=";
cin>>y;
Linklist_ins(L,x,y);break;
case 4:cout<<"请输入删除元素的位置! i=";
cin>>i;
if(i<1||i>ListLength_L(L)) cout<<"输入的位置i不正确。"<<endl;
else cout<<"删除第"<<i<<"个元素为"<<ListDelete_L(L,i)<<endl;break;
case 5:cout<<"请输入删除元素的值!X=";
cin>>x;
if(Linklist_del2(L,x)) cout<<"删除成功"<<endl;
else cout<<"链表中没有元素"<<x<<"删除失败"<<endl; break;
case 6:prt_Linklist(L);cout<<" 线性表长度="<<ListLength_L(L)<<endl;break;
case 7:cout<<"请输入查找的元素值! x=";cin>>x;
LocateElem(L,x);break;
case 8:cout<<"请输入查找元素的位置! i=";
cin>>i;
if(Getelem(L,i)) cout<<"第"<<i<<"元素的值是="<<Getelem(L,i)<<endl;
else cout<<"输入的位置不对"<<endl; break;
case 9:InvertLinkedList(L);
cout<<"逆置后的单链表: ";prt_Linklist(L);break;
case 10:cout<<"建立第一个有序表,输入链表长度:";
cin>>n;
CreateList_L(La,n);
cout<<"建立第二个有序表,输入链表长度:";
cin>>n;
CreateList_L(Lb,n);
MergeList_L(La,Lb,L);
cout<<"合并后的有序表:";prt_Linklist(L);break;
case 11: aa=0;
}
}
}
实验2.2 单链表中的元素以递增序存放，编程删除表中所有值大于mink且小于maxk的元素。
（1） 操作步骤：
分为三个步骤：创建链表，并按递增顺序输入；输出链表的数据；删除介于两个数据之间的元素。
（2） 程序代码;
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef int ElemType;
typedef struct LNode
{ ElemType data; /* 数据子域 */
struct LNode *next; /* 指针子域 */
}LNode; /* 结点结构类型 */
LNode *L;
/* 函数声明 */
LNode *creat_L();
void delete_L(LNode *L,int i); //返回值格式变为空
/* 建立线性链表*/
LNode *creat_L()
{
LNode *h,*p,*s; ElemType x;
h=(LNode *)malloc(sizeof(LNode)); /* 分配头结点 */
h->next=NULL;
p=h;
printf("输入一串数字（以-1结束）:\ndata= ");
scanf("%d",&x); /* 输入第一个数据元素 */
while( x!=-1) /* 输入-1，结束循环 */
{
s=(LNode *)malloc(sizeof(LNode)); /* 分配新结点 */
s->data=x; s->next=NULL;
p->next=s; p=s;
printf("data= ");
scanf("%d",&x); /* 输入下一个数据*/
}
return(h);
} /* creat_L */
/* 输出单链表中的数据元素*/
void out_L(LNode *L)
{
LNode *p;
p=L->next;
printf("\n数据是:");
while(p!=NULL)
{
printf("%5d",p->data);
p=p->next;
}
} /* out_link */
/* 删除大于x小于y的值*/
void delete_L(LNode *L,int a,int b)
{
LNode *p,*q;
p=L;
q=p;
p=p->next;
if(p==NULL) printf("ERROR:链表为空");
while(p!=NULL)
{
if((p->data >a) && (p->data <b))
{ q->next=p->next;
free(p);
p=q->next;
}
else
{ q=p;
p=p->next;
}
}
} /* delete_L */
void main()
{
int a,b;
L=creat_L( ); out_L(L);
printf("\n\n请输入你要删除的元素的范围x和y:\n");
scanf("%d%d",&a,&b);
delete_L(L,a,b); out_L(L);
printf("\n");
} /* main */
实验三 内部排序算法设计
一、实验目的
1、熟练掌握各种内排序方法，深刻理解排序算法及执行过程；
2、学会分析各种内排序算法的性能；
3、了解各种排序方法的优缺点，对于实际问题能够选择一种好的排序方案。
二、实验内容
实验3.1 实现下述算法，并用以下无序序列加以验证：
49，38，65，97，76，13，27，49
(1)、直接插入排序、折半插入排序、冒泡排序
(2)、简单选择排序
(3)、快速排序
（1） 操作步骤：
此实验是对各种排序方法的实验过程，对给定数据采用不同的方法进行排序操作，每种排序方法需要用一个函数来完成。
（2） 程序代码：
#include <iostream.h>
const MAXSIZE=20;
#define LT(a,b) ((a)<(b))
#define GT(a,b) ((a)>(b))
typedef int KeyType;
typedef int InfoType;
typedef struct{
KeyType key;
InfoType otherinfo;
}RedType;
typedef struct{
RedType r[MAXSIZE+1]; //r[0]闲置做哨兵
int length;
}SqList;
//直接插入排序
void InsertSort(SqList &L)
{ int i,j;
for(i=2;i<=L.length;++i)
if(LT(L.r[i].key,L.r[i-1].key)){
L.r[0]=L.r[i];
for(j=i-1; LT(L.r[0].key,L.r[j].key); --j)
L.r[j+1]=L.r[j];
L.r[j+1]=L.r[0]; }
}
//折半插入排序
void BInsertSort(SqList &L)
{ int i,j,low,high,m;
for(i=2;i<=L.length;++i){
L.r[0]=L.r[i];
low=1;high=i-1;
while(low<=high){
m=(low+high)/2;
if (LT(L.r[0].key,L.r[m].key)) high=m-1;
else low=m+1;
}
for(j=i-1;j>=high+1;--j) L.r[j+1]=L.r[j];
L.r[high+1]=L.r[0];
}
}
//希尔排序
void ShellInsert(SqList &L, int dk)
{/* 对顺序表L作一趟希尔排序。 前后记录位置的增量是dk
r[0]只是暂存单元，不作哨兵用。当j≤0时，插入位置已找到*/
for (int i=dk+1;i<=L.length;++i)
if LT(L.r[i].key,L.r[i-dk].key)
{
L.r[0]=L.r[i];
for (int j=i-dk;j>0 && LT(L.r[0].key,L.r[j].key);j-=dk)
L.r[j+dk]=L.r[j]; /*记录后移，查找插入位置*/
L.r[j+dk]=L.r[0];
}
}
/*按增量序列dlta[0…t-1]对顺序表L作希尔排序*/
void ShellSort(SqList &L, int dlta[], int t)
{
for (int k=0;k<t;++k)
ShellInsert(L,dlta[k]); /*一趟增量为dlta[k]的插入排序*/
}
//QuickSort
int Partition(SqList &L,int low,int high)
{
int pivotkey;
L.r[0]=L.r[low];
pivotkey=L.r[low].key;
while(low<high){
while(low<high&&L.r[high].key>=pivotkey) --high;
L.r[low]=L.r[high];
while(low<high&&L.r[low].key<=pivotkey) ++low;
L.r[high]=L.r[low];
}
L.r[low]=L.r[0];
return low;
}
void QSort(SqList &L,int low,int high)
{
int pivotloc;
if(low<high){
pivotloc=Partition(L,low,high);
QSort(L,low,pivotloc-1);
QSort(L,pivotloc+1,high);
}
}
void QuickSort(SqList &L)
{
QSort(L,1,L.length);
}
/* End QuickSort related function*/
//SelectSort
int SelectMinKey(SqList &L,int i)
{ int k;
int j;
k=i;
for(j=i;j<L.length+1;j++)
if(L.r[k].key>L.r[j].key)
k=j;
return k;
}
void SelectSort(SqList &L)
{
RedType t;
int i,j;
for(i=1;i<L.length;++i){
j=SelectMinKey(L,i);
if(i!=j) {
t=L.r[i];
L.r[i]=L.r[j];
L.r[j]=t;
}
}
}/*End SelectSort related function */
//堆排序
typedef SqList HeapType;
void HeapAdjust(HeapType &H,int s,int m)
{
RedType rc;
int j;
rc=H.r[s];
for(j=2*s;j<=m;j*=2){
if(j<m && LT(H.r[j].key,H.r[j+1].key)) ++j;
if(!LT(rc.key,H.r[j].key)) break;
H.r[s]=H.r[j];
s=j;
}
H.r[s]=rc;
}
void HeapSort(HeapType &H)
{
RedType t;
int i;
for(i=H.length/2;i>0;--i)
HeapAdjust(H,i,H.length);
for(i=H.length;i>1;--i){
t=H.r[1];
H.r[1]=H.r[i];
H.r[i]=t;
HeapAdjust(H,1,i-1);
}
}
//打印
void prt_sqlist(SqList L)
{ int i;
for(i=1;i<=L.length;i++)
cout<<L.r[i].key<<" ";
cout<<endl;
}
void main()
{
int a[]={49,38,65,97,76,13,27,49};
int dlta[]={5,3,1}; //希尔排序增量
int i,k=1,t=3;
SqList s;
for(i=1;i<9;i++) s.r[i].key=a[i-1]; //生成顺序表
s.length=i-1;
cout<<"待排序列为:"; prt_sqlist(s);
cout<<endl<<"1,插入排序"<<endl<<"2,折半排序"<<endl<<"3,希尔排序"<<endl<<"4,快速排序"<<endl<<"5,选择排序"<<endl<<"6,堆排序"<<endl;
while(k) {
cout<<"按键1..6，选择一种排序方法,按0退出 ";
cin>>k;
switch(k){
case 1:
InsertSort(s);break;
case 2:
BInsertSort(s);break;
case 3:
ShellSort(s,dlta,t);break;
case 4:
QuickSort(s);break;
case 5:
SelectSort(s);break;
case 6:
HeapSort(s);break;
}
cout<<"排序的结果:"<<endl;prt_sqlist(s);
}}
实验四 栈、队列算法设计
一、实验目的
1、熟悉栈这种特殊线性结构的特性；
2、熟练掌握栈在顺序存储结构和链表存储结构下的基本运算；
3、熟悉队列这种特殊线性结构的特性；
4、熟练掌握队列在链表存储结构下的基本运算。
二、 实验内容
实验4.1 用顺序和链式存储结构分别实现栈的初始化、求长度、获取栈顶元素、压栈、出栈、判空、置空等操作，生成sqStack.h文件和LinkStack.h文件；编写main函数调用。
（1） 用顺序存储结构实现基本操作。
（2） 程序代码：
sqstack..cpp文件中的代码
#include <iostream.h>
#include "sqstack.h"
void main()
{
int x; sqstack Sa;
cout<<"-----------------栈的演示程序----------------"<<endl;
cout<<"首先初始化栈，此时栈为空"<<endl;
InitStack(Sa);
cout<<"输入入栈序列，压栈，输0结束。"<<endl;
cin>>x;
while(x!=0)
{ Push(Sa,x);cin>>x;}
cout<<"现在栈有"<<StackLength(Sa)<<"个元素"<<endl;
cout<<"现在出栈，把元素保存到变量中"<<endl;
Pop(Sa,x);cout<<"出栈的元素为"<<x<<endl;
cout<<"让我们看看还剩哪个元素"<<endl;
while(!StackEmpty(Sa))
{Pop(Sa,x);cout<<x<<endl; }
}
sqstack.h文件中的程序代码：
const ERROR=0;
const TRUE= 1;
const FALSE= 0;
const OK= 1;
const STACK_INIT_SIZE= 10;
const STACKINCREMENT= 1;
const OVERFLOW= 0;
typedef int SElemType;
typedef struct
{ SElemType *elem;
int top;
int stacksize;
}sqstack;
//构造一个一定大小的空栈
void InitStack(sqstack &S)
{
S.elem=new SElemType[STACK_INIT_SIZE];
S.top=-1;
S.stacksize=STACK_INIT_SIZE;
}
//销毁栈
void DestroyStack(sqstack &S)
{delete []S.elem; }
//置为空栈
void ClearStack(sqstack &S)
{S.top=-1;}
//判空
bool StackEmpty(sqstack &S)
{ if(S.top==-1) return TRUE;
else return FALSE;
}
//栈的长度
int StackLength(sqstack S)
{return S.top+1;}
//获取栈顶元素
int GetTop(sqstack &S,SElemType &e)
{ if(S.top==-1) return ERROR;
e=S.elem[S.top]; return OK;}
//压栈
int Push(sqstack &S,SElemType e)
{ if(S.top==S.stacksize)return OVERFLOW;
S.elem[++S.top]=e;
return OK;
}
//出栈
int Pop(sqstack &S,SElemType &e)
{ if(S.top==-1) return ERROR;
e=S.elem[S.top--]; return OK;}
（3） 用链式存储结构实现基本操作。
（4） 程序代码：
MyLinkList.cpp中的文件代码:
//栈的链式存储表示
#include <iostream.h>
#include "MyLinkList.h"
const STACK_INIT_SIZE=10; //存储空间初始分配量
const STACKINCREMENT=2; //存储空间分配增量
//结点类型, 结点指针类型
typedef LinkList LinkStack;
//----栈的基本操作---------
//初始化，设S为空栈
void InitStack(LinkStack &s)
{s=NULL;}
void Push_L(LinkStack &s,int e ){
LinkStack p;
p=new LNode;
p->data=e;p->next=s;s=p;
}
bool Pop_L(LinkStack &s, int &e){
LinkStack p;
if(s)
{ p =s;s= s->next;
e=p->data;
delete p;
return TRUE;
} else return FALSE;
}
void main()
{
int x; LinkStack Sa;
cout<<"-----------------链栈的演示程序----------------"<<endl;
cout<<"首先初始化栈，此时栈为空"<<endl;
InitStack(Sa);
cout<<"输入入栈序列，压栈，输0结束。"<<endl;
cin>>x;
while(x!=0)
{ Push_L(Sa,x);cin>>x;}
cout<<"现在栈有"<<ListLength_L(Sa)<<"个元素"<<endl;
cout<<"现在出栈，把元素保存到变量中"<<endl;
while(Sa)
{Pop_L(Sa,x);cout<<"出栈的元素为"<<x<<endl;}
if(!Sa) cout<<"现在栈为空"<<endl;}
MyLinkList.h中的文件代码：
//创建不带表头结点的单链表
#include<iostream.h>
const OK=1;
const ERROR=0;
const TRUE=1;
const FALSE=0;
//带表头结点的单链表的结构定义：
typedef struct LNode{
int data;
struct LNode *next;
}LNode,*LinkList;
// 建立单链表,逆序
void CreateList_L(LinkList &L, int n)
{ LNode *p;
L= NULL; //生成头指针
int i;
cout<<"输入"<<n<<"个链表元素:"<<endl;
for (i=n;i>0;--i)
{ p=new LNode;
cin>>p->data; //逆序输入an,an-1 …. a1
p->next=L; L=p;}
}
//判断是否为空
bool empty_list(LinkList L)
{ return (L==NULL)?TRUE:FALSE;
}
//获取单链表长度
int ListLength_L(LinkList L)
{ //L为链表的头指针，本函数返回 L 所指链表的长度
LinkList p;
int k=0;
p=L;
while (p) { k++; p=p->next; } //k计非空结点数
return k; } // ListLength_L
//取单链表中的第i (i>0)个结点)
int Getelem(LinkList L, int i)
{ LinkList p;; int j=1;
p=L;
while( p && j<i)
{ p=p->next;++j; }
if(!p||j>i) return ERROR;
else return p->data; }
//在链表查找某元素，返回位置
void LocateElem(LinkList L,int x)
{ int j;LNode *p; //P为扫描指针,j为计数器
if(empty_list(L)) cout<<"空表。"<<endl;
else {
p=L;j=1;
while((p->data!=x) && p){j++; p=p->next;}
if(p->data==x)cout<<"元素"<<x<<"是第"<<j<<"个元素"<<endl;
else cout<<"没找到元素"<<x<<endl;
}
}
//在单链表L中的第i (i>0)个结点前插入一个元素x
int ListInsert_L(LinkList &L,int i,LNode *s){
if (i==1) {s->next=L;L=s;return OK;}
else{
LNode *p;int j;
p=L;j=1;
while(p&&j<i-1){p=p->next;++j;}
if(!p||j>i-1) return ERROR;
else{s->next=p->next;p->next=s;return OK;}
}
}//ListInsert_L
//在单链表中值为x的结点前插入一个元素y,如果x值不存在，则把y插在表尾。
void Linklist_ins(LinkList &L, int x, int y)
{ LNode *p,*q,*s;
s=new LNode; s->data=y;s->next=NULL;
p=L;
while ( p && p->data!=x ) { q=p; p=p->next;}
if(p==L){s->next=L;L=s;}
else{s->next=p; q->next=s;}
}
//删除单链表L中的第i (i>0)个元素。
int ListDelete_L(LinkList &L,int i)
{LNode *p,*q;
int j;
if (i==1) {q=L;L=L->next;}
else{
p=L; j=1 ;
while (p ->next && j<i-1) //指针P定位到ai的前驱结点
{ p=p->next; ++j;}
q=p->next; p->next=q->next; } //修改指针
return q->data; delete q; //释放结点空间
}
//删除单链表L中的值为x的结点
int Linklist_del2(LinkList &L, int x)
{ LNode *p,*q;
p=L;
while ( p && p->data!=x ) { q=p; p=p->next;}
if (!p) return ERROR;
if(p==L)L=L->next;
else q->next=p->next;
delete p;return OK;
}
//输出单链表
void prt_Linklist(LinkList L)
{ LNode *p;
p=L;
while (p) {cout<<p->data<<" "; p=p->next; }
}
void InvertLinkedList( LinkList &L) {
LNode *p,*s;
p = L; L = NULL; // 设逆置后的链表的初态为空
while ( p ) { // p 为遍历指针，指向待逆置链表的头
s = p; p = p->next; //删除 p 所指链表的第一个结点(s 结点)
s->next = L; L = s; // 将 s 结点插入到逆置表的表头
}
} // InvertLinkedList
//合并有序表
void MergeList_L(LinkList &La,LinkList &Lb, LinkList &Lc)
{ //pa、pb、 pc分别是La、Lb、Lc的遍历指针
LNode *pa,*pb,*pc;//三个链表的遍历指针
pa = La; pb= Lb;
//确定合并后链表的头
if (pa->data <= pb->data ) {Lc=pc=La;pa=pa->next;}
else {Lc=pc=Lb; pb=pb->next;}
while (pa && pb) //当La、Lb未结束时
{ if (pa->data <= pb->data )
{pc->next = pa; pc = pa; pa = pa->next;}
else { pc->next = pb; pc = pb; pb = pb->next;}
}
pc->next = pa?pa:pb;
}
实验4.2 编写一个判断表达式中括号是否匹配的程序。
（1） 操作步骤
（2） 程序代码：
/*栈实现判断表达式中括号是否配对的算法,包括(),[],{}三类括号并可以任意嵌套使用*/
#include "sqstack_char.h"
#include <iostream.h>
#include <string.h>
int IsOk(sqstack &S,char pExp[])
{ int i;
char c;
int nLen = strlen(pExp);
bool bResult=TRUE;
for (i=0;i<nLen && bResult;i++)
{//左括号入栈
if (pExp[i]=='{' || pExp[i] == '[' || pExp[i] == '(') Push(S,pExp[i]);
//右括号判断，可能出栈或出错
if (pExp[i] == '}')
{if (!Pop(S,c) || c!='{') bResult = FALSE;}//出错
if (pExp[i] == ']')
{if (!Pop(S,c) || c != '[') bResult = FALSE;}//出错
if (pExp[i] == ')')
{if (!Pop(S,c) || c != '(') bResult = FALSE;}//出错
}
return bResult && StackEmpty(S);
}
void main()
{ sqstack Sa;
cout<<"-----判断表达式中括号是否配对-----"<<endl;
InitStack(Sa);
char exp[]="12*(12+5)*(({}))";
if(IsOk(Sa,exp)) cout<<"正确"<<endl;
else cout<<"出错"<<endl;
char exp1[]="12*(12+5)*(({})]))";
if(IsOk(Sa,exp1)) cout<<"正确"<<endl;
else cout<<"出错"<<endl;}
sqstack_char.h文件中代码：
const ERROR=0;
const TRUE= 1;
const FALSE= 0;
const OK= 1;
const STACK_INIT_SIZE= 10;
const STACKINCREMENT= 1;
const OVERFLOW= 0;
typedef char SElemType;
typedef struct
{ SElemType *elem;
int top;
int stacksize;
}sqstack;
//构造一个一定大小的空栈
void InitStack(sqstack &S)
{
S.elem=new SElemType[STACK_INIT_SIZE];
S.top=-1;
S.stacksize=STACK_INIT_SIZE;
}
//销毁栈
void DestroyStack(sqstack &S)
{delete []S.elem; }
//置为空栈
void ClearStack(sqstack &S)
{S.top=-1;}
//判空
bool StackEmpty(sqstack &S)
{ if(S.top==-1) return TRUE;
else return FALSE;
}
//栈的长度
int StackLength(sqstack S)
{return S.top+1;}
//获取栈顶元素
int GetTop(sqstack &S,SElemType &e)
{ if(S.top==-1) return ERROR;
e=S.elem[S.top]; return OK;}
//压栈
int Push(sqstack &S,SElemType e)
{ if(S.top==S.stacksize)return OVERFLOW;
S.elem[++S.top]=e;
return OK;
}
//出栈
int Pop(sqstack &S,SElemType &e)
{ if(S.top==-1) return ERROR;
e=S.elem[S.top--]; return OK;}
实验4.3 用递归的方法解决阶乘问题和费波那契数列。
1、 阶乘
（1） 程序代码：
/*用递归算法求n的阶乘
fab(n)= 1. 1 n=1
2. n*fab(n-1 n>1*/
#include <iostream.h>
int fab(int n)
{if(n==0) return 1;
else return n*fab(n-1);
}
int main()
{ int n;
cout<<"请输入数值n: "<<endl;
cin>>n;
cout<<endl<<"n的阶乘为: "<<fab(n)<<endl;
return n;
}
2、 费波那契数列
（1） 程序代码：
/*求解二阶斐波那奇数列的值
n=0 fib(n)=0
n=1 fib(n)=1
n>1 fib(n)=fib(n-1)+fib(n-2)*/
#include <iostream.h>
int fib(int n)
{if(n==0) return 0;
else if(n==1) return 1;
else return fib(n-1)+fib(n-2);
}
int main()
{ int n;
cout<<"请输入整数n: ";
cin>>n;
cout<<endl<<"第n项斐波那奇数列值为: "<<fib(n)<<endl;
return 0;
}
实验4.4 用链式存储结构实现队列的初始化、进队、出队操作，生成LinkQueue.h文件，编写main函数调用。
（1） 程序代码：
MyLinkList.cpp中的代码：
//链式队列
#include <iostream.h>
#include "MyLinkList.h"
typedef LinkList QueuePtr;
typedef int QElemType;
typedef struct{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
void InitQueue(LinkQueue &Q) {
//构造一个空队列Q
Q.front=Q.rear=new LNode;
Q.front->next=NULL; }
void Destroyqueue(LinkQueue &Q) {
//队列Q存在则销毁Q
while(Q.front){
Q.rear=Q.front->next;
delete Q.front;Q.front=Q.rear;}
}
void EnQueue(LinkQueue &Q,QElemType e) {
//队列Q存在,插入元素e为Q的队尾元素
QueuePtr p;
p=new LNode;
p->data=e; p->next=NULL;
Q.rear->next=p;
Q.rear=p;}
int DeQueue(LinkQueue &Q,QElemType &e) {
//Q为非空队列,删除Q的队头元素,并用e返回其值
if(Q.front==Q.rear)return ERROR; //Q为空队列
QueuePtr p;
p=Q.front->next; //第一个元素
e=p->data;
Q.front->next=p->next; //删除
if(Q.rear==p) Q.rear=Q.front;
delete p ;
return OK;}
bool QueueEmpty(LinkQueue Q)
// 队列Q存在,若Q为空队列则返回TRUE,否则返回FALSE
{if(Q.front->next=NULL) return TRUE;
else return FALSE;}
int QueueLenght(LinkQueue Q)
// 队列Q存在,返回Q的元素个数,即队列的长度
{int j=1;
QueuePtr p=Q.front->next;
while(p){p=p->next;j++;}
return j-1; }
int GetHead(LinkQueue Q,QElemType &e)
//Q为非空队列,用e返回Q的队头元素
{ if(Q.front==Q.rear)return ERROR; //Q为空队列
QueuePtr p=Q.front->next; //第一个元素
e=p->data; return OK;}
main()
{
int x; LinkQueue Qa;
cout<<"-------------链队的演示程序-------------"<<endl;
cout<<"1、初始化链队，此时链队为空"<<endl;
InitQueue(Qa);
cout<<"2、元素120、110、22入队"<<endl;
x=120;EnQueue(Qa,x);
x=110;EnQueue(Qa,x);
x=22;EnQueue(Qa,x);
cout<<"3、链队有"<<QueueLenght(Qa)<<"个元素"<<endl;
DeQueue(Qa,x);
cout<<"4、队头元素出队"<<x<<endl;
GetHead(Qa,x);
cout<<"5、现在的队头元素为"<<x<<endl;
cout<<"6、现在销毁链队"<<endl; Destroyqueue(Qa);
cout<<"现在链队为空"<<endl; }
MyLinkList.h文件中的代码：
// 创建不带表头结点的单链表
#include<iostream.h>
const OK=1;
const ERROR=0;
const TRUE=1;
const FALSE=0;
//带表头结点的单链表的结构定义：
typedef struct LNode{
int data;
struct LNode *next;
}LNode,*LinkList;
// 建立单链表,逆序
void CreateList_L(LinkList &L, int n)
{ LNode *p;
L= NULL; //生成头指针
int i;
cout<<"输入"<<n<<"个链表元素:"<<endl;
for (i=n;i>0;--i)
{ p=new LNode;
cin>>p->data; //逆序输入an,an-1 …. a1
p->next=L; L=p;}
}
//判断是否为空
bool empty_list(LinkList L)
{ return (L==NULL)?TRUE:FALSE;
}
//获取单链表长度
int ListLength_L(LinkList L)
{ //L为链表的头指针，本函数返回 L 所指链表的长度
LinkList p;
int k=0;
p=L;
while (p) { k++; p=p->next; } //k计非空结点数
return k; } // ListLength_L
//取单链表中的第i (i>0)个结点)
int Getelem(LinkList L, int i)
{ LinkList p;; int j=1;
p=L;
while( p && j<i)
{ p=p->next;++j; }
if(!p||j>i) return ERROR;
else return p->data; }
//在链表查找某元素，返回位置
void LocateElem(LinkList L,int x)
{ int j;LNode *p; //P为扫描指针,j为计数器
if(empty_list(L)) cout<<"空表。"<<endl;
else {
p=L;j=1;
while((p->data!=x) && p){j++; p=p->next;}
if(p->data==x)cout<<"元素"<<x<<"是第"<<j<<"个元素"<<endl;
else cout<<"没找到元素"<<x<<endl;
}
}
//在单链表L中的第i (i>0)个结点前插入一个元素x
int ListInsert_L(LinkList &L,int i,LNode *s){
if (i==1) {s->next=L;L=s;return OK;}
else{
LNode *p;int j;
p=L;j=1;
while(p&&j<i-1){p=p->next;++j;}
if(!p||j>i-1) return ERROR;
else{s->next=p->next;p->next=s;return OK;}
}
}//ListInsert_L
//在单链表中值为x的结点前插入一个元素y,如果x值不存在，则把y插在表尾。
void Linklist_ins(LinkList &L, int x, int y)
{ LNode *p,*q,*s;
s=new LNode; s->data=y;s->next=NULL;
p=L;
while ( p && p->data!=x ) { q=p; p=p->next;}
if(p==L){s->next=L;L=s;}
else{s->next=p; q->next=s;}
}
//删除单链表L中的第i (i>0)个元素。
int ListDelete_L(LinkList &L,int i)
{LNode *p,*q;
int j;
if (i==1) {q=L;L=L->next;}
else{
p=L; j=1 ;
while (p ->next && j<i-1) //指针P定位到ai的前驱结点
{ p=p->next; ++j;}
q=p->next; p->next=q->next; } //修改指针
return q->data; delete q; //释放结点空间
}
//删除单链表L中的值为x的结点
int Linklist_del2(LinkList &L, int x)
{ LNode *p,*q;
p=L;
while ( p && p->data!=x ) { q=p; p=p->next;}
if (!p) return ERROR;
if(p==L)L=L->next;
else q->next=p->next;
delete p;return OK;
}
//输出单链表
void prt_Linklist(LinkList L)
{ LNode *p;
p=L;
while (p) {cout<<p->data<<" "; p=p->next; }
}
void InvertLinkedList( LinkList &L) {
LNode *p,*s;
p = L; L = NULL; // 设逆置后的链表的初态为空
while ( p ) { // p 为遍历指针，指向待逆置链表的头
s = p; p = p->next; //删除 p 所指链表的第一个结点(s 结点)
s->next = L; L = s; // 将 s 结点插入到逆置表的表头
}
} // InvertLinkedList
//合并有序表
void MergeList_L(LinkList &La,LinkList &Lb, LinkList &Lc)
{ //pa、pb、 pc分别是La、Lb、Lc的遍历指针
LNode *pa,*pb,*pc;//三个链表的遍历指针
pa = La; pb= Lb;
//确定合并后链表的头
if (pa->data <= pb->data ) {Lc=pc=La;pa=pa->next;}
else {Lc=pc=Lb; pb=pb->next;}
while (pa && pb) //当La、Lb未结束时
{ if (pa->data <= pb->data )
{pc->next = pa; pc = pa; pa = pa->next;}
else { pc->next = pb; pc = pb; pb = pb->next;}
}
pc->next = pa?pa:pb;
}