计算机软件技术基础实验报告.docx

计算机软件技术基础实验报告.docx

《计算机软件技术基础实验报告.docx》由会员分享，可在线阅读，更多相关《计算机软件技术基础实验报告.docx（30页珍藏版）》请在冰点文库上搜索。

计算机软件技术基础实验报告

《计算机软件技术基础》实验报告

专业_____________

年级_____________

学号_____________

学生姓名_____________

指导老师_____________

南华大学计算机学院编

实验要求

1．每次实验中有若干习题，每个学生至少应该完成其中的两道习题。

2．上机之前应作好充分的准备工作，预先编好程序，经过人工检查无误后，才能上机，以提高上机效率。

3．独立上机输入和调试自己所编的程序，切忌抄袭、拷贝他人程序。

4．上机结束后，应整理出实验报告。

书写实验报告时，重点放在调试过程和小节部分，总结出本次实验中的得与失，以达到巩固课堂学习、提高动手能力的目的。

实验一线性表

【实验目的】

1．熟悉VC环境，学习如何使用C语言实现线性表的两种存储结构。

2．通过编程、上机调试，进一步理解线性表的基本概念,熟练运用C语言实现线性表基本操作。

3．熟练掌握线性表的综合应用问题。

【实验内容】

必做：

1．一个线性表有n个元素（n

（1）现有一元素x要插入到线性表的适当位置上，并保持线性表原有的顺序不变。

采用链式存储表示方法实现，设计程序实现

（2）从单链表中删除指定的元素x，若x在单链表中不存在，给出提示信息。

要求：

指定的值x由键盘输入；

程序能处理空链表的情况。

选做：

3．设有头结点的单链表，编程对表中的作一值只保留一个结点，删除其余值相同的结点。

要求：

该算法用函数（非主函数）实现；

在主函数中调用创建链表的函数创建一个单链表，并调用该函数，验证算法的正确性。

4．已知非空单链表第一个结点由head指出，请写一算法，交换p所指结点与其下一个结点在链表中的位置。

要求：

该算法用函数Reverse（head,p）实现，其中head为表头指针，p指向要交换的结点；

在主函数中调用创建链表的函数创建一个单链表，并调用该函数，验证算法的正确性。

要求：

建立一个结点中含有三个域的单链表；

在主函数中调用此算法，构成双向循环链表；

在主函数中利用正向和逆向两种方式输出链表中的数据，验证算法的正确性。

【实验报告】

实习时间：

实习地点：

实习机号：

具

体

实

验

内

容

#include

#include

#defineNULL0

#defineLENsizeof（linklist）

typedefstructnode

{

intdata;

structnode*next;

}linklist;

linklist*creat（）

{

inti;

linklist*head,*r,*q;

q=（linklist*）malloc（LEN）;

head=q;

r=q;

q->next=NULL;

printf（"Pleaseinputthenumber:

\n"）;

scanf（"%d",&i）;

while（i!

=0）

{

q=（linklist*）malloc（LEN）;

q->data=i;

q->next=NULL;

r->next=q;

r=r->next;

scanf（"%d",&i）;

}

returnhead;

}

voidprint（linklist*head）

{

linklist*p;

p=head->next;

while（p!

=0）

{

printf（"%d\n",p->data）;

p=p->next;

}

}

voiddeletelist（inti,linklist*head）

{

linklist*p,*q;

intk=1;

p=head;

q=p->next;

while（（q!

=NULL）&&（i!

=k））

{

k++;

p=q;

q=q->next;

}

p->next=q->next;

}

voidinsertlist（inti,intx,linklist*head）

{

intk=0;

linklist*p,*q,*p1;

p=head;

q=p->next;

while（（q!

=NULL）&&（k

{

k++;

p=q;

q=q->next;

}

p1=（linklist*）malloc（LEN）;

p1->data=x;

p1->next=p->next;

p->next=p1;

}

voidmain（）

{intx,i,choice,n;

linklist*head;

head=creat（）;

printf（"Pleaseinputyourchoice:

\n1.print2.delete3.insert4.exit\n"）;

while

（1）

{

printf（"Pleaseinputthechoice:

"）;

scanf（"%d",&choice）;

switch（choice）

{

case1:

print（head）;

break;

case2:

printf（"Pleaseinputdeletenumbern:

"）;

scanf（"%d",&n）;

deletelist（n,head）;

print（head）;

break;

case3:

printf（"Pleaseinputi,x:

"）;

scanf（"%d,%d",&i,&x）;

insertlist（i,x,head）;

print（head）;

break;

case4:

break;

default:

break;

}

if（choice==4）break;

if（choice>=5）printf（"theinputnumberiserror!

\n"）;

}

}

程

序

调

试

过

程

实

习

小

结

实验二堆栈与队列

【实验目的】

1．学习如何使用C语言实现堆栈与队列。

2．熟悉堆栈与队列的基本操作及应用。

【实验内容】

1．现有一顺序队列，其结构描述为：

#defineMAX100

typedefstruct

{ElemTypequeue[MaxQueueSize];

intfront;//队头指针

intcount;//计数器

}QueueType;

要求：

设计队列的几种几种操作：

初始化、进队、出队、取队头元素和判断队列是否非空。

编写一个主函数进行测试。

2．顺序堆栈实验

要求：

设计堆栈的几种几种操作：

初始化、入栈、出栈、取栈顶元素和判断堆栈是否非空。

编写一个主函数进行测试。

【实验报告】

实习时间：

实习地点：

实习机号：

具

体

实

验

内

容

#include

#include

#defineLENsizeof（quenode）

typedefstructnode

{

intdata;

structnode*next;

}quenode;

typedefstruct

{

quenode*front,*rear;

}linkque;

voidinitlque（linkque*lp）

{

quenode*q;

q=（quenode*）malloc（LEN）;

if（q==NULL）

printf（"内存分配不成功!

\n"）;

else

printf（"内存分配成功!

\n"）;

lp->front=q;

lp->front->next=NULL;

lp->rear=lp->front;

}

voidinsertlque（linkque*lp,intx）

{

quenode*p;

p=（quenode*）malloc（LEN）;

p->data=x;

p->next=NULL;

lp->rear->next=p;

lp->rear=p;

}

voidshowlque（linkque*lp）

{

quenode*p;

p=lp->front->next;

if（p==NULL）

printf（"thelinkqueisnull!

\n"）;

else

{

while（p!

=NULL）

{

printf（"%d\n",p->data）;

p=p->next;

}

}

}

voidexitlque（linkque*lq,int*x）

{

quenode*p;

p=lq->front->next;

if（p==NULL）

printf（"thelinkqueisnull!

\n"）;

else

{

lq->front->next=lq->front->next->next;

*x=p->data;

free（p）;

printf（"theexitingnumberis:

"）;

printf（"%d\n",*x）;

}

}

voidmain（）

{

linkqueq;

intchoice,x,m;

printf（"Pleaseinputyourcommander:

\n1.initlinkque2.insertlinkque3.exitlinkque4.showlinkque5.exit\n"）;

while

（1）

{

printf（"Pleaseinputthenumber:

"）;

scanf（"%d",&choice）;

switch（choice）

{

case1:

initlque（&q）;

break;

case2:

{

printf（"Pleaseinputx:

"）;

scanf（"%d",&x）;

insertlque（&q,x）;

}

break;

case3:

exitlque（&q,&m）;

break;

case4:

showlque（&q）;

break;

case5:

break;

default:

break;

}

if（choice>=5）break;

}

}

程

序

调

试

过

程

实

习

小

结

实验三队列与栈的应用

必做：

1、设一个算术表达式中包含圆括号、方括号和花括号三种类型的括号，编写一个算法判断其中的括号是否匹配。

提示：

本题使用一个运算符栈st，当遇到的‘（’、‘[’、或‘{’时进栈，当遇到‘}’、‘]’、‘）’时判断栈顶是否为相应的括号，若是退栈继续执行；否则算法结束。

选做：

2、假设以数组sequ[0..MaxSize-1]存放环形队列的元素，同时设变量rear和len分别指示环形队列中队尾元素的位置和内含元素的个数。

试写出此环形队列队满的条件，并设计相应入队和出队的算法。

（根据题目填空完善程序）

提示：

该环形队列对满的条件为：

len==MaxSize，队空的条件为：

len==0。

由rear,len求队列头指针front的过程为：

front=rear-len+1；

if（front<0）front=front+MaxSize；

即front=（rear-len+1+MaxSize）%MaxSize

#include

#definemaxsize6

typedefcharqueue[maxsize]；

intrear=0,len=0；

intenqueue（queuequ,charx）

{

if（len==maxsize）

return0；

else

{

rear=（rear+1）%maxsize；

qu[rear]=x；

len++；

return1；

}

}

intdequeue（queuequ,char*x）

{

intfront；

if（len==0）

return0；

else

{

front=（rear-len+1+maxsize）%maxsize；

*x=qu[front]；

len--；

return1；

}

}

voidmain（）

{

charx；

queuequ；

printf（“a入队\n”）；

enqueue（qu,‘a’）；

printf（“b入队\n”）；

enqueue（qu,‘b’）；

printf（“c入队\n”）；

enqueue（qu,‘c’）；

printf（“出队一次：

”）；

dequeue（qu,&x）；

printf（“%c\n”,x）；

printf（“d入队\n”）；

enqueue（qu,‘d’）；

printf（“e入队\n”）；

enqueue（qu,‘e’）；

printf（“出队一次：

”）；

dequeue（qu,&x）；

printf（“%c\n”,x）；

printf（“f入队\n”）；

enqueue（qu,‘f’）；

printf（“g入队\n”）；

enqueue（qu,‘g’）；

printf（“出队一次：

”）；

dequeue（qu,&x）；

printf（“%c\n”,x）；

printf（“余下元素出列：

”）；

while（len>0）

{

dequeue（qu,&x）；

printf（“%c\n”,x）；

}

printf（“\n”）；

}

输出：

.入队

.入队

出队一次：

.入队

.入队

出队一次：

.入队

.入队

出队一次：

余下元素出列：

【实验报告】

实习时间：

实习地点：

实习机号：

具

体

实

验

内

容

#include

#include

#defineLENsizeof（linkstack）

#defineNULL0

typedefstructnode

{

intdata;

structnode*next;

}linkstack;

voidinstack（linkstack*&top,intx）

{

linkstack*p;

p=（linkstack*）malloc（LEN）;

p->data=x;

p->next=top;

top=p;

}

voidoutstack（linkstack*&top）

{

linkstack*p;

intx;

p=top;

if（p==NULL）

{

printf（"Stackisempty!

\n"）;

//returnNULL;//

}

else

{

top=p->next;

x=p->data;

free（p）;

printf（"%d\n",x）;

//returnx;//

}

}

voidshowstack（linkstack*&top）

{

linkstack*p;

p=top;

if（p->data==0）

printf（"thestackisnull!

\n"）;

else

{

while（p->data!

=0）

{

printf（"%d\n",p->data）;

p=p->next;

}

}

}

voidinitstack（linkstack*&top）

{

top=（linkstack*）malloc（LEN）;

top->data=0;

top->next=NULL;

}

voidmain（）

{

intchoice,x;

linkstack*top;

top=（linkstack*）malloc（LEN）;

top->data=0;

top->next=NULL;

printf（"Pleaselookatthechoice:

1.instack2.outstack3.showstack4.exit\n"）;

while

（1）

{

printf（"Pleaseinputyourchoice:

"）;

scanf（"%d",&choice）;

switch（choice）

{

case1:

printf（"Pleaseinputx:

\n"）;

scanf（"%d",&x）;

while（x!

=0）

{

instack（top,x）;

scanf（"%d",&x）;

}

break;

case2:

outstack（top）;

break;

case3:

showstack（top）;

break;

case4:

break;

default:

break;

}

if（choice==4）break;

if（choice>=5）printf（"theinputtingnumberiserror!

\n"）;

}

}

程

序

调

试

过

程

实

习

小

结

实验四树

一、实验目的

1.掌握二叉树，二叉树排序数的概念及存储方法。

2.掌握二叉树的遍历算法。

3.熟练掌握编写实现树的各种运算的算法。

一、实验内容

树的基本运算：

创建树；输出树；遍历树；求二叉树的深度；创建二叉排序树；二叉排序树的查找；二叉排序树的删除；创造哈夫曼树；输出哈夫曼树；

1、建立一棵二叉树并中序遍历。

（填空）

#include“stdio.h”

#include“malloc.h”

structnode{

chardata；

structnode*lchild,*rchild；

}bnode；

typedefstructnode*blink；

blinkadd（blinkbt,charch）

{

if（bt==NULL）

{

bt=nalloc（sizeof（bnode））；

bt->data=ch；

bt->lchild=bt->rchild=NULL；

}

elseif（chdata）

bt->lchild=add（bt->lchild,ch）；

else

bt->rchild=add（bt->rchild,ch）；

returnbt；

}

voidinorder（blinkbt）

{

if（bt）

{inorder（bt->lchild）；

printf（“%c”,bt->data）；

inorder（bt->rchild）；

}

}

main（）

{

blinkroot=null；

inti,n；

charx；

scanf（“%c”,&n）；

for（i=1；i<=n；i++）

{

x=getchar（）；

root=add（root,x）；

}

inorder（root）；

printf（“\n”）；

}

输入：

ephqsbma

输出：

2、求二叉树的结点数和叶子数（填空）

#include“stdio.h”

#include“alloc.h”

structnode{

chardata；

structnode*lchild,*rchild；

}bnode；

typedefstructnode*blink；

intn=0,no=0；

voidpreorder（blinkbt）

{

if（bt）

{n++；

if（bt->lchild==NULL&&bt->rchild==NULL）

no++；

preorder（bt->lchild；）

preorder（bt->rchild；）

}

}

blinkcreat（）

{

blinkbt；

charch；

ch=getchar（）；

if（ch!

=’#’）

{

bt=nalloc（sizeof（bnode））；

bt->data=ch；

bt->lchild=creat（）；

bt->rchild=creat（）；

}

else

bt=NULL；

returnbt；

}

main（）

{

blinkroot；

root=creat（）；

preorder（root）；

printf（“numberofnode：

%dnumberofleaf：

%d\n”,n,no）；

}

输入：

ab##cd###

输出：

【实验报告】

实习时间：

实习地点：

实习机号：

实验六查找与排序

【实验目的】

熟悉各种查找与排序的算法，并对各种算法的效率进行比较和测试。

【实验内容】

1．排序算法比较。

要求：

调用函数intrand（void）产生100000个待排序的数据；

测试下列各排序函数的机器实际执行时间：

a.直接插入排序；b.希尔排序c.选择排序

d.冒泡排序e.快速排序f.归并排序

【实验报告】

实习时间：

实习地点：

实习机号：

具

体

实

验

内

容

程

序

调

试

过

程

实

习

小

结

实验七综合练习

【实验目的】

1．在掌握基本概念的基础上，综合运用线性结构和树结构以及排序和查找算法进行复杂结构程序设计。

【实验内容】

1．试将一棵普通树转换成二叉树，同时转换而成的二叉树按前序、中序、后序进行遍历，并输出遍历后结点的序列。

例如，下面左