太原理工大学现代科技学院
计算机软件技术基础课程 实验报告
专业班级
学 号
姓 名
指导教师
实验名称 顺序表的冒泡排序 同组人
专业班级 学号 姓名 成绩
实验目的与要求：理解和掌握线性表的排序技术，使用C语言根据相应算法编写一个程序，实现顺序存储的线性表的冒泡排序。要求仔细阅读下面的内容，编写C程序，上机通过，并观察其结果，写出实验报告书。
实验内容：将顺序存储的长度为n的无序线性表进行排序
具体要求：
① 根据线性表的冒泡排序的算法编写C程序，并上机调试。
② 编写的C程序要求将顺序存储的长度为n的无序线性表进行排序。
③ 实验完成后，写出实验报告书。
上机程序：
bubsort(p,n)
int n;int p[];
{
int m,k,j,i;
int d;
k=0;m=n-1;
while (k<m)
{j=m-1;m=0;
for(i=k;i<=j;i++)
if(p[i]>p[i+1])
{d=p[i];p[i]=p[i+1];p[i+1]=d;m=i;}
j=k+1;k=0;
for(i=m;i>=j;i--)
if(p[i-1]>p[i])
{d=p[i];p[i]=p[i-1];p[i-1]=d;k=i;}
}
return;
}
main()
{int i,n=10;int p[10];
printf ("input 10 number:");
printf ("\n");
for (i=0;i<10;i++)
scanf("%d",&p[i]);
bubsort(p,n);
printf("the sorted number:");
for (i=0;i<10;i++)
printf("%5d",p[i]);
printf("\n");
getch();
}
实验结果：
第二篇：计算机软件技术基础实验报告
《计算机软件基础实验报告》
实验一：一元多项式的相加
一：实验的目的与要求
1：熟悉单链表的一些操作；
2：掌握采用链表结构实现一元多项式的相加的算法。
二：实验任务
1: 分别建立两个单链表来表示两个多项式；
2: 对单链表进行插入、删除、操作;
3: 对一元多项式的相加并输出相加结果。
三：实验方案（程序）
#include<iostream.h>
typedef struct linklist{
int exp,coef;
struct linklist *next;
}node;
node *ha,*hb;
void build(node *&head)
{ int x,y,i;
node *p,*q; head=new node; p=head; for(i=1;i<10000;i++){ cin>>x>>y; cout<<endl; if((x!=0)||(y!=0)){ q=p; p->exp=x; p->coef=y; p->next=new node; p=p->next;
}else{
q->next=NULL;
delete p;
break;
}
} }
void display(node *&head)
{node *p;
p=head; while(p!=NULL){ } cout<<p->exp<<","<<p->coef<<endl; p=p->next;
}
void del(node *&head)
{node *p,*q;
q=head;
p=head;
while((q->exp!=4)||(q->coef!=6)){ p=q;
q=q->next;
}
p->next=q->next;
}
void cha(node *&head)
{node *p,*q,*s;
} p=head; q=head; while((q->exp!=5)||(q->coef!=(-6))){ p=q; q=q->next; } s=new node; s->exp=4; s->coef=8; p->next=s; s->next=q;
void jia(node *&head1, node*&head2) { node *p,*q,*u,*pre;
int x;
p=head1->next;
q=head2->next;
pre=head1;
while((p!=NULL) && (q!=NULL))
{ if(p->exp<q->exp)
{ pre=p; p=p->next;}
else if(p->exp==q->exp)
{ x=p->coef+q->coef;
if(x!=0){ p->coef=x; pre=p;}
else{ pre->next=p->next; delete p;} p=pre->next;
u=q;
q=q->next;
delete u;}
else { u=q->next; q->next=p; pre->next=q;
pre=q; q=u;}
}
if (p==NULL)
pre->next=q;
delete hb;
}
void main()
{
cout<<"创建一元多项式ha"<<endl; build(ha)
cout<<"输出ha"<<endl;
display(ha);
cout<<endl;
del(ha); cout<<"输出删除结点后的ha"<<endl; display(ha); cout<<endl; cout<<"创建一元多项式hb"<<endl; build(hb); cout<<"输出hb"<<endl; display(hb); cout<<endl; cha(hb);
cout<<"输出插入结点后的hb"<<endl; display(hb);
}
cout<<endl; jia(ha,hb); cout<<"对ha、hb求和输出求和结果"<<endl; display(ha);
输出结果：
创建一元多项式ha 0
5
1
3
4
6
5
13
输出ha
0，5
1，3
4，6
5，13
输出删除节点后的ha 0，5
1，3
5，13
创建一元多项式hb 1
3
5
-6
8
7
输出hb
1，3
5，-6
8，7
输入插入节点后的hb
1，3
4，8
5，-6
8，7
对ha、hb求和输出求和结果
0，5
1，3
4，8
5，7
8，7
实验二：二叉树的遍历 一：实验目的与要求
1:熟悉二叉树的遍历；
2：掌握对二叉树的遍历的算法。
二：实验任务
1：建立二叉树；
2：对其先序、中序、后序遍历
三：实验方案（程序）
#include<iostream.h>
typedef struct treenode{
char x;
struct treenode *lchild,*rchild;
}JD;
JD *tree;
void create()
{JD *Q[20];
int front,rear;
char ch; JD *s; tree=NULL; front=1; rear=0; cin>>ch; while(ch!='#') {s=NULL; if(ch!='@') {
} } } s=new JD; s->x=ch; s->lchild=NULL; s->rchild=NULL; rear++; Q[rear]=s; if(rear==1) tree=s; else {if(s!=NULL&&Q[front]!=NULL) {if(rear%2==0) } Q[front]->lchild=s; else Q[front]->rchild=s; if(rear%2==1) front++; }cin>>ch;
void preorder(JD *p) {if(p==NULL)
return;
cout<<p->x;
preorder(p->lchild); preorder(p->rchild); }
void inorder(JD *p)
{
if(p==NULL) return; inorder(p->lchild); cout<<p->x;
inorder(p->rchild); }void postorder(JD *p) {if(p==NULL)
return; postorder(p->lchild); postorder(p->rchild); cout<<p->x;
}
void countdu(JD *p,int *count) {if(p!=NULL)
{if(((p->lchild==NULL)&&(p->rchild!=NULL))||((p->lchild!=NULL)&&(p->rchild==NULL))) } (*count)++; countdu(p->lchild,count); countdu(p->rchild,count);
}
void main()
{ int a=0;
cout<<"建立二叉树"<<endl;
create(); cout<<"先序遍历二叉树"<<endl; preorder(tree); cout<<endl; cout<<"中序遍历二叉树"<<endl; inorder(tree); cout<<endl; cout<<"后序遍历二叉树"<<endl; postorder(tree); cout<<endl;
}
输出结果：
建立二叉树
A B C D E F G
先序遍历二叉树
A B C D E F G
中序遍历二叉树
C B D A E G F
后序遍历二叉树
C D B G F E A
实验三：二叉排序树的操作 一：实验目的与要求
1：熟悉二叉排序树的操作
二：实验任务
1：建立二叉排序树
2：对其进行中序遍历，删除10，
三：实验方案（程序）
#include<iostream.h>
typedef struct treenode{
int x;
struct treenode *lchild,*rchild; }JD;
JD *tree=NULL;
void insertbet(int y)
{ JD *p,*q,*s;
s= new JD; s->x=y; s->lchild=s->rchild=NULL; q=NULL; if(tree==NULL) { tree=s; return; } p=tree; while(p!=NULL) { q=p; if(y<p->x) p=p->lchild; else p=p->rchild; }if(y<q->x)
q->lchild=s;
else q->rchild=s;
}
void inorder(JD *p)
{ if(p==NULL)
return;
inorder(p->lchild); cout<<p->x<<" "; inorder(p->rchild);
}
void delnode(JD*p, JD* f)
{ JD*q, *s;
int flag=0;
if(p->lchild==NULL)
s=p->rchild;
else
if(p->rchild==NULL) s=p->lchild;
else
{ q=p;
s=p->lchild;
while(s->rchild!=NULL) { q=s;
s=s->rchild; } if(q==p)
q->lchild=s->lchild; else
q->rchild=s->lchild; p->x=s->x;
delete s;
flag=1; }
if(flag==0)
{ if(f==NULL)
tree=s;
else
if(f->lchild==p)
f->lchild=s;
else
f->rchild=s;
delete p;
}
}
void main()
{
int a,i; cout<<"建立二叉排序树"<<endl; for(i=0;i<10000;i++) { cin>>a; if(a!=0) insertbet(a); } else break; cout<<"中序遍历二叉树"<<endl; inorder(tree);
cout<<endl;
delnode(tree,NULL);
cout<<"删除结点10后中序遍历二叉树"<<endl; inorder(tree); cout<<endl;
}
实验结果
建立二叉排序树
10 18 3 8 12 2 7 4
中序遍历二叉树
2 3 4 7 8 10 12 18
删除结点10后中序遍历二叉树
2 3 4 7 8 12 18
实验四：图的遍历
一：实验目的与要求
1：掌握图的遍历
2：掌握邻接表，邻接矩阵的使用
二：实验任务
1：建立图
2：分别对图进行深度与广度遍历
三：实验方案（程序）
#include <iostream>
#define INFINITY 32767
#define MAX_V 20 #define QUEUE_SIZE (MAX_V+1) using namespace std;
bool *visited; typedef struct
{ char *vexs; int arcs[MAX_V][MAX_V]; int vexnum,arcnum;
}
Graph;
class Queue { public: void InitQueue()
{ base=(int *)malloc(QUEUE_SIZE*sizeof(int)); front=rear=0; }
void EnQueue(int e)
{ base[rear]=e; rear=(rear+1)%QUEUE_SIZE;
}
void DeQueue(int &e)
{ e=base[front]; front=(front+1)%QUEUE_SIZE;
}
public:
int *base; int front; int rear; };
int Locate(Graph G,char c)
{ for(int i=0;i<G.vexnum;i++)
if(G.vexs[i]==c) return i; return -1;
}
void CreateUDN(Graph &G) { int i,j,w,s1,s2; char a,b,temp;
printf("输入顶点的总数和边的总数:");
scanf("%d%d",&G.vexnum,&G.arcnum);
temp=getchar();
G.vexs=(char *)malloc(G.vexnum*sizeof(char));
printf("输入%d个顶点分别为：\n",G.vexnum);
for(i=0;i<G.vexnum;i++)
{ printf("顶点%d:",i); scanf("%c",&G.vexs[i]); temp=getchar();} for(i=0;i<G.vexnum;i++)
for(j=0;j<G.vexnum;j++)
G.arcs[i][j]=INFINITY;
printf("输入%d条边分别为：\n",G.arcnum);
for(i=0;i<G.arcnum;i++)
{ printf("边%d:",i);
scanf("%c-%c %d",&a,&b,&w);
temp=getchar();
s1=Locate(G,a); s2=Locate(G,b);
G.arcs[s1][s2]=G.arcs[s2][s1]=w; }
}
int FirstVex(Graph G,int k)
{ if(k>=0 && k<G.vexnum)
{ for(int i=0;i<G.vexnum;i++)
if(G.arcs[k][i]!=INFINITY) return i; }
return -1;
}
int NextVex(Graph G,int i,int j) 点
{ if(i>=0 && i<G.vexnum && j>=0 && j<G.vexnum)
{ for(int k=j+1;k<G.vexnum;k++)
if(G.arcs[i][k]!=INFINITY) return k; }
return -1;
}
void DFS(Graph G,int k)
{ int i; if(k==-1)
{ for(i=0;i<G.vexnum;i++) if(!visited[i]) DFS(G,i); }
else
{ visited[k]=true;
printf("%c ",G.vexs[k]);
for(i=FirstVex(G,k);i>=0;i=NextVex(G,k,i))
if(!visited[i]) DFS(G,i);
}
}
void BFS(Graph G)
{ int k;
Queue Q;
Q.InitQueue();
for(int i=0;i<G.vexnum;i++)
if(!visited[i])
{ visited[i]=true; printf("%c ",G.vexs[i]);
Q.EnQueue(i); while(Q.front!=Q.rear)
{ Q.DeQueue(k); for(int w=FirstVex(G,k);w>=0;w=NextVex(G,k,w))
if(!visited[w]) { visited[w]=true; printf("%c ",G.vexs[w]);
Q.EnQueue(w); }
}
}
}
void main() { int i; Graph G; CreateUDN(G);
visited=(bool *)malloc(G.vexnum*sizeof(bool));
printf("\n深度优先搜索结果为: ");
for(i=0;i<G.vexnum;i++) visited[i]=false; DFS(G,-1); printf("\n广度优先搜索结果为: ");
for(i=0;i<G.vexnum;i++) visited[i]=false; BFS(G); printf("\n "); }
输出结果
输出顶点总数和边的总数：6 4
深度优先搜索结果为:
1 2 5 3 4 6
广度优先搜索结果为:
1 2 3 4 5 6
实验五：查找与排序 一：实验目的与要求
1：熟悉查找与排序的操作
2：掌握、应用查找排序
二：实验任务
1：对分查找5,13,17,42,46,55,70,94中55的位置并显示 2:查找12，若没有找到打印fault
三：实验方案（对分查找程序）
#include<iostream.h>
typedef struct
{ int key;
}rec;
rec r[8]={5,13,17,42,46,55,70,94};
int binsearch(rec r[], int n, int k)
{ int low,high,mid,found;
low=1; high=n; found=0;
while((low<=high)&&(found==0))
{ mid=(low+high)/2;
if(k>r[mid].key) low=mid+1; else if(k==r[mid].key) found=1; else high=mid-1;
}if(found==1)
return mid;
else
cout<<"fault”;
return 0;
}void main()
{ cout<<"55位置为";
cout<<binsearch(r,8,55)+1<<endl; cout<<"12位置为";
cout<<binsearch(r,8,12)<<endl; }
实验结果
55的位置为6
12位置为fault
实验方案（堆排序程序）
#include<iostream.h>
#include<stdlib.h>
struct rec{
int key;};
rec a[]={19,1,23,68,35,19,84,27,14}; void sift(rec r[], int k, int n)
{ int i,j; rec x;
i=k; x=r[i]; j=2*i;
while(j<=n)
{ if((j<n)&&(r[j].key<r[j+1].key)) j++;
if(x.key<r[j].key)
{ r[i]=r[j];
i=j;
j=2*i;}
else break;
}
r[i]=x;
}
void bsift(rec r[], int n)
{ int i;
for(i=n/2;i>=1;i--)
sift(r,i,n); //cout<<r[1].key<<" "; }
void heapsort(rec r[], int n)
{ int i; rec x;
bsift(r,n);
cout<<"堆排序结果为"<<endl;
for(i=n;i>=2;i--)
{ x=r[i];
r[1]=r[i]; r[i]=x;
sift(r,1,i-1);
cout<<r[1].key<<" ";
}
}
void main()
{heapsort(a,9);
}
实验结果
堆排序的结果为
1 14 19 19 23 27 35 64 84
实验六：操作系统相关 一：实验目的与要求
了解作系统及进程
二：实验任务
建立并输出进程名，求运行时间
三：实验方案（程序）
#include<iostream.h>
typedef struct sa
{ char name[20];
int time; int priority; int state;
struct sa *next;
}PCB;
typedef struct as
{PCB *front,*rear;
}LQ;
PCB *ha;
LQ *m,*n;
void build(PCB *&head)
{PCB *p,*q;
head=new PCB; int i; p=head; for(i=0;i<5;i++) { q=p;
} cout<<"输入进程名"<<endl; cin>>p->name; cout<<"输入要求运行时间"<<endl; cin>>p->time; cout<<"输入优先数"<<endl; cin>>p->priority; cout<<"输入状态"<<endl; cin>>p->state; cout<<endl; p->next=new PCB; p=p->next; }q->next=NULL; delete p;
void chushi(LQ *&q)
{ PCB *p;
} q=new LQ; p=new PCB; p->next=NULL; q->front=q->rear=p;
void paixu(PCB *&head,LQ *&q) { PCB *p,*h;
p=head;
int x,i;
for(i=0;i<5;i++) { p=head; x=p->priority; while(p->next!=NULL) { p=p->next; if(p->priority>x) x=p->priority; } p=head; h=head; while(p->priority!=x) { h=p; p=p->next; } if(h==p) {
} } } else { } head=h->next; p->next=NULL; q->rear->next=p; q->rear=p; h->next=p->next; p->next=NULL; q->rear->next=p; q->rear=p;
void shuchu(LQ *&a,LQ *&b) {
PCB *c,*d; c=a->front; while(c->next!=NULL) { c=c->next; cout<<"进程名:"<<c->name<<endl; cout<<"要求运行时间:"<<c->time<<endl; cout<<"优先数:"<<c->priority<<endl; cout<<"状态:"; if(c->state==0) cout<<"就绪"<<endl; if(c->state==1) cout<<"运行"<<endl; if(c->state==2) cout<<"结束"<<endl; // cout<<endl; } d=b->front; while(d->next!=NULL) { d=d->next; cout<<"进程名:"<<d->name<<endl; cout<<"要求运行时间:"<<d->time<<endl; cout<<"优先数:"<<d->priority<<endl; cout<<"状态:"; if(d->state==0) cout<<"就绪"<<endl; if(d->state==1)
} cout<<"运行"<<endl; if(d->state==2) cout<<"结束"<<endl; //cout<<endl;
}
void done(LQ *&q,LQ *&h) {
PCB *s,*p,*r; do{ s=q->front->next; q->front->next=s->next; s->next=NULL; s->time--; s->priority--; s->state=1; if(s->time==0) { s->state=2; h->rear->next=s; h->rear=s; } else { r=p=q->front->next; while((s->priority<=p->priority)&&(p->next!=NULL)) { } r=p; p=p->next; if(p->next==NULL) { } else if(p==r) { } q->front->next=s; s->next=r; q->rear->next=s; q->rear=s; else { r->next=s;
}
s->next=p; } } shuchu(q,h); cout<<endl; }while(q->front->next!=q->rear); while(q->rear->time!=0) { } q->rear->time--; q->rear->priority--; q->rear->state=1; shuchu(q,h); cout<<endl; q->rear->state=2; shuchu(q,h); cout<<endl;
void main()
{
build(ha); chushi(m); chushi(n); paixu(ha,m); shuchu(m,n); cout<<endl; done(m,n); }
实验结果
输入进程名： 1
输入要求运行时间： 1
输入优先数： 1