《计算机软件基础》
实践报告
题目C语言程序上机操作专业学生姓名准考证号指导教师
20__年5月
一、单链表
实验内容：单链表的定义、创建、插入和删除操作，将数据显示出来。源程序
include
definenull0
defineslnodestructnode
slnode/定义结构体/
{intdata;
slnodene_t;
slnodeh;
slnodecreate_sl()
{slnodep,s;
int_;
h=(slnode)malloc(sizeof(slnode));
p=h;
h->ne_t=null;/初始化/
_=get_data();
while(_!=-1)/创建，以输入-1结束/
{s=(slnode)malloc(sizeof(slnode));
s->data=_;
if(h->ne_t==null)h->ne_t=s;
elsep->ne_t=s;
p=s;
_=get_data();}
p->ne_t=null;
returnh;}
get_data()/获取数据元素/
{int_;
scanf("%d",_);
return_;}
slnodeinsert(slnodeh,inti,int_)
/在第i个结点处插入数据元素_/
{slnodep,s;
intj;p=h;j=0;
while(p->ne_t!=nullj {p=p->ne_t;j++;} if(j!=i-1) {printf("iisinvalid!"); return0;} else {s=(slnode)malloc(sizeof(slnode)); s->data=_; s->ne_t=p->ne_t; p->ne_t=s; returnh;} slnodedelete(slnodeh,inti)/删除第i个结点/ {slnodep,s; intj;p=h;j=0; while(p->ne_t!=nullj {p=p->ne_t; j++;} if(j!=i-1) {printf("iisinvalid!");return0;}else {if(p->ne_t==null) {printf("iisinvalid!"); return0;} else {s=p->ne_t; p->ne_t=s->ne_t; free(s); returnh;} voidprint(slnodeh) /显示链表中的数据元素/ {slnodep; printf("
Now,Theserecordsare:
");p=h->ne_t; if(h!=null) {printf("%5d",p->data); p=p->ne_t; }while(p!=null); voidmain()/主函数，调用各个函数/{slnodeh; intt,data,m; h=create_sl(); print(h); printf("
"); scanf("%d%d",t,data); h=insert(h,t,data); print(h); printf("
"); scanf("%d",m); h=delete(h,m); print(h); 2.1顺序栈 实验内容：栈的顺序存储结构的定义、创建、插入和删除，将数据元素显示出来。 include definema_10 Typedefstruct/定义结构体/ {charstack[ma_]; inttop; }qstype; qstypes; initiateqs()/初始化/ {s->top=-1; returns; intpush()/入栈/ {int_; if(s->top>=ma_-1)/栈满则结束/ return0; else while((_=get_data())!=-1) s->top++; s->stack[s->top]=_;/将_进栈/ return1; get_data() int_; scanf("%d",_); return_; main() {intsign; qstypes; s=initiateqs(); sign=push(); if(sign==0) {printf("overflow"); else {intp; p=s->top; while(p!=-1) {printf("%5d",s->stack[p]); /将栈中元素显示出来同时不改变栈中元素/ p--; printf("
"); if(s->top==-1) {printf("null"); else {while(s->top!=-1) {printf("%5d",s->stack[s->top]);/只能删除栈顶元素/s->top--;} printf("
");/将栈中元素显示出来同时删除栈中元素/} 2.2链式栈 实验内容：栈的链式存储结构的定义、创建、插入和删除，将数据元素显示出来。 include definenull0 typedefstructnode/定义结构体/ {intdata; structnodene_t; }slnode; slnodeh; initiatels()/初始化/ {h=(slnode)malloc(sizeof(slnode)); h->ne_t=null;/创建头结点/ returnh; pushls(slnodeh,int_)/把数据元素插入栈中/{slnodep; p=(slnode)malloc(sizeof(slnode)); p->data=_; p->ne_t=h->ne_t; h->ne_t=p; main() {intch; slnodeh,p; h=initiatels(); scanf("%d",ch); while(ch!=-1)/输入以-1结束/ {pushls(h,ch); scanf("%d",ch);} p=h->ne_t; while(p->ne_t!=null)/输出栈中元素同时删除/{p=h->ne_t; h->ne_t=p->ne_t; ch=p->data; printf("%5d",ch);} printf("
"); 3.1顺序队 实验内容：队的顺序存储结构的定义、创建、插入和删除，将数据元素显示出来。 include definema_10 typedefstruct {intqueue[ma_]; intfront;intrear; }qqtype; qqtypeq; voidinitiateqq()/初始化/ {q->front=-1; q->rear=-1; intenterqq(qqtypeq)/入队/ {int_; if(q->rear==ma_-1)/队已满/ return0; else {while((_=get_data())!=-1) {q->rear++;q->queue[q->rear]=_;} return1;} get_data()/输入数据元素/ int_; scanf("%d",_); return_; main() {intsign; qqtypeq; q=initiateqq(); if((sign=enterqq(q))==1) printf("creatqueue:
"); while(q->front!=q->rear)/输出出对元素/ {q->front++; printf("%5d",q->queue[q->front]);} printf("
"); 3.2链式队 实验内容：队的链式存储结构的定义、创建、插入和删除，将数据元素显示出来。 include definenull0 typedefstructnode {intdata; structnodene_t; }slnode; typedefstruct/定义链式队列结构体/ {slnodeh; slnoderear; }lqtype; voidinitiatelq(lqtypeq) {q->h=(slnode)malloc(sizeof(slnode)); q->rear=q->h; q->h->ne_t=null; voidenterlq(lqtypeq)/入队/ {int_; while((_=get_data())!=-1) {slnodep; p=(slnode)malloc(sizeof(slnode)); p->data=_; p->ne_t=null; if(q->h==null)q->h=p; q->rear->ne_t=p; q->rear=p;} get_data()/输入数据元素/ int_; scanf("%d",_); return_; intdeletelq(lqtypeq)/出队/ {slnodep; int_; if(q->h->ne_t==null)return-1;/队以空/else {p=q->h->ne_t;q->h->ne_t=p->ne_t; _=p->data;free(p); if(q->h->ne_t==null)q->rear->ne_t=null;return_;}/返回队头元素/ main() {intt; lqtypeq; initiatelq(q); enterlq(q); printf("outqueue:"); while((t=deletelq(q))!=-1) printf("%5d",t); printf("
"); 四、二叉树 实验内容：二叉树的链式存储结构的数据定义、创建先序、中序和后序遍历，并将结果序列输出。源程序 include definenull0 intcounter=0; typedefstructbtreenode/定义二叉树结构体/{intdata; structbtreenodelchild; structbtreenoderchild; }bnode; bnodep; bnodecreat(int_,bnodelbt,bnoderbt)/建立一个只有根结点的二叉树/{bnodep; p=(bnode)malloc(sizeof(bnode)); p->data=_; p->lchild=lbt; p->rchild=rbt; returnp; bnodeins_lchild(bnodep,int_)/以_作为左孩子插入/ {bnodeq; if(p==null) printf("illegalinsert."); else {q=(bnode)malloc(sizeof(bnode)); q->data=_; q->lchild=null; q->rchild=null; if(p->lchild!=null) q->rchild=p->lchild; p->lchild=q;} bnodeins_rchild(bnodep,int_)/以_作为右孩子插入/ {bnodeq; if(p==null) printf("illegalinsert"); else {q=(bnode)malloc(sizeof(bnode)); q->data=_; q->lchild=null; q->rchild=null; if(p->rchild!=null) q->lchild=p->rchild; p->rchild=q;} voidprorder(bnodep)/输出二叉树的结构/ {if(p==null) return; printf("%d %u %d %u %u
",++counter,p,p->data,p->lchild,p->rchild);if(p->lchild!=null) prorder(p->lchild); if(p->rchild!=null) prorder(p->rchild); voidpreorder(bnodep)/前序遍历二叉树/{if(p==null) return; printf("%5d",p->data); if(p->lchild!=null) preorder(p->lchild); if(p->rchild!=null) preorder(p->rchild); voidinorder(bnodep)/中序遍历二叉树/{if(p==null) return; if(p->lchild!=null) inorder(p->lchild); printf("%5d",p->data); if(p->rchild!=null) inorder(p->rchild); voidpostorder(bnodep)/后序遍历二叉树/{if(p==null) return; if(p->lchild!=null) postorder(p->lchild); if(p->rchild!=null) postorder(p->rchild); printf("%5d",p->data); main() {bnodebt,p,q; int_; printf("Inputroot:");/建立排序二叉树/scanf("%d",_); p=creat(_,null,null); bt=p; scanf("%d",_); while(_!=-1) {p=bt;q=p; while(_!=p->dataq!=null) {p=q; if(_ elseq=p->rchild;} if(_==p->data) {printf("Thedataise_it.");return;}10 else if(_ elseins_rchild(p,_); scanf("%d",_); p=bt; printf("structureofthebinarytree:
"); printf("number address data lchild rchild
"); prorder(p); printf("preorder:"); preorder(p); printf("
"); printf("inorder:"); inorder(p); printf("
"); printf("postorder:"); postorder(p); printf("
"); 五、查找 5.1顺序查找 include definema_20 intseq_search(ints[],intk,intn) /在序列s[0]~s[n-1]中，从头开始顺序查找关键字为k的记录/{inti; s[n]=k;/设置监视哨/ i=0; while(s[i]!=k) i++; if(i {printf("findit."); returni;/找到，返回位置值i/ else {printf("notfindit."); return-1; intgetdata(intlist[])/输入序列/ {intnum,i; printf("total="); scanf("%d",num); for(i=0;i {printf("data[%d]=",i); scanf("%d",list[i]); returnnum;/返回序列记录个数/ main() {intlist[ma_],n,inde_,_; n=getdata(list); printf("searchkey="); scanf("%d",_); inde_=seq_search(list,_,n); if(inde_>=0) printf("data[%d]=%d
",inde_,_); else printf("%d:notfound.
",_); 5.2二分查找 include definema_20 intbinary(int_,intlist[],intn)/从list[]中查找_/{intlow,high,mid; low=0; high=n-1; while(low<=high) {mid=(low+high)/2;/折半/ if(_ else {if(_>list[mid])/在后部分查找/low=mid+1; else returnmid; return-1; intgetdata(intlist[])/输入数组list[]/{intnum,i; printf("total="); scanf("%d",num); for(i=0;i {printf("data[%d]=",i); scanf("%d",list[i]);} returnnum; main() {intlist[ma_],n,inde_,_; n=getdata(list); printf("searchkey=");/输入待查找数据/ scanf("%d",_); inde_=binary(_,list,n); if(inde_>=0) printf("data[%d]=%d
",inde_,_); else printf("%d:notfound.
",_); 六、排序 6.1插入排序 include definema_40 typedefstruct {intkey; charname; }elemtype; elemtype_[ma_]; voidgetsort(elemtype_[],intn)/输入记录的关键字/{inti; printf("Recorder:"); for(i=0;i scanf("%d",_[i].key); voidinsertsort(elemtype_[],intn)/用直接插入排序法排序/{inti,j,k,m; elemtypeswap; for(i=0;i {swap=_[i+1]; j=i; while(j>XXX<_[j].key) {_[j+1]=_[j]; j--;} _[j+1]=swap; m=i+1; printf("No%dinsertsort ",m); for(k=0;k printf("%d ",_[k].key); printf("
"); main() {elemtype_[ma_]; intn; printf("n="); scanf("%d",n); getsort(_,n); insertsort(_,n); 6.2选择排序 include definema_40 typedefstruct {intkey; charname; }elemtype; elemtype_[ma_]; voidgetsort(elemtype_[],intn)/输入待排序记录/{inti; printf("Recorder:"); for(i=0;i scanf("%d",_[i].key); voidselectsort(elemtype_[],intn) /对记录序列进行直接选择排序/ {inti,j,small,k,m; elemtypeswap; for(i=0;i /在剩余记录序列中选择关键字最小的记录/{small=i; for(j=i;j if(_[j].key<_[small].key) small=j; if(small!=0) {swap=_[i]; _[i]=_[small]; _[small]=swap;} m=i+1; printf("No.%dselectsort: ",m); for(k=0;k printf("%d ",_[k].key); printf("
"); main() {elemtype_[ma_]; intn; printf("n="); scanf("%d",n);/输入待排序的元素个数/getsort(_,n);/输入待排序的元素/selectsort(_,n);/直接选择排序/ 6.3冒泡排序 include definema_40 typedefstruct {intkey; charname; }elemtype; elemtype_[ma_]; voidgetsort(elemtype_[],intn)/输入待排序记录/{inti; printf("Recorder:"); for(i=0;i scanf("%d",_[i].key); voidhubblesort(elemtype_[],intn)/用冒泡法排序/{inti,j,k,flag; elemtypeswap; flag=1; for(i=1;i {flag=0; for(j=0;j if(_[j].key>_[j+1].key)/比较两数的大小/{flag=1; swap=_[j]; _[j]=_[j+1]; _[j+1]=swap; if(flag==0) return; main() {elemtype_[ma_]; intn,i; printf("n=");/输入待排序记录的个数/ scanf("%d",n); getsort(_,n); hubblesort(_,n); printf("Outputthenumber:"); for(i=0;i printf("%d ",_[i]);/输出以排好的序列/ printf("
"); 七、实验收获 通过这次的上机实验，我巩固和提高了大一时学的C语言编程能力，当时只是学的只是一些简单算法的实现，这次在之前的基础上涉及到了链表、队、栈、二叉树等数据结构，选择合适的数据结构可以提高在一定程度上降低时间和空间复杂度，提高运算效率，实现算法的最优化。链表可以根据需要随时开辟动态空间，提高内存的利用率，对于插入、删除操作也很简单。对于队和栈只能从固定的一端插入和删除，用于解决一些特殊的问题。二叉树的用途也极为广泛，以及由二叉树衍生出的排序、最优、线索二叉树。 在实验过程中也遇到了各种困难，从不知道怎么写声明区的编写如包含文件，宏定义，函数声明，全局变量声明，结构体等的定义到程序写完后的语法错误以及出现死循环等情况。只能抱着各种指导书，对照着程序去找错误，刚开始程序写得很慢，还要花很长时间去调试，后来慢慢地总结出经验，把这个过程分成四部分进行，一、定义，二、写被调用的子函数，三、主函数，四、调试，每一步的基础是理解，理解每种数据结构的存储方式、各个步骤的目的和原理，写完后开始调试，根据错误提示，有方向、有目的地去纠错，先检查是不是有语法错误，在深入检查。有时会碰到死循环的情况，这是因为没有设置好终止条件，如对于数据元素_的输入，以-1的输入作为终止的条件。 我们往往写不出程序，这其中的原因我觉得是对程序的结构不是很了解，对实验的内容也不熟练的结果，数据结构给我们许多程序的算法和模型，对我们写程序的思维有很大的锻炼，我们应珍惜每次上机实验的机会去实践课堂上所学的东西并从中发现问题，从而达到提升写程序的能力。实验时不要以写完作为目的，当程序运行成功后，可以尝试用其他的方法，多想、多实践，如果把程序稍作改动会不会影响结果，为什么会影响，不要怕出现错误，这样才知道自己的哪些想法是错误的。这才是实验的真正目的，在实验中收获知识，提升自己。