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

计算机软件技术基础实验报告专 业 _年 级 _学 号 _学生姓名 _指导老师 _南华大学计算机学院编I 实验要求1每次实验中有若干习题，每个学生至少应该完成其中的两道习题。2上机之前应作好充分的准备工作，预先编好程序，经过人工检查无误后，才能上机，以提高上机效率。3独立上机输入和调试自己所编的程序，切忌抄袭、拷贝他人程序。4上机结束后，应整理出实验报告。书写实验报告时，重点放在调试过程和小节部分，总结出本次实验中的得与失，以达到巩固课堂学习、提高动手能力的目的。实验一 线性表【实验目的】1熟悉VC环境，学习如何使用C语言实现线性表的两种存储结构。2通过编程、上机调试，进一步理解线性表的基本概念,熟练运用C语言实现线性表基本操作。3熟练掌握线性表的综合应用问题。【实验内容】必做：1一个线性表有n个元素（nMAXSIZE, MAXSIZE指线性表的最大长度），且递增有序。（1）现有一元素x要插入到线性表的适当位置上，并保持线性表原有的顺序不变。采用链式存储表示方法实现，设计程序实现 （2）从单链表中删除指定的元素x，若x在单链表中不存在，给出提示信息。 要求：指定的值x由键盘输入；程序能处理空链表的情况。选做： 3设有头结点的单链表，编程对表中的作一值只保留一个结点，删除其余值相同的结点。要求：该算法用函数（非主函数）实现；在主函数中调用创建链表的函数创建一个单链表，并调用该函数，验证算法的正确性。4已知非空单链表第一个结点由head指出，请写一算法，交换p所指结点与其下一个结点在链表中的位置。要求：该算法用函数Reverse(head,p)实现，其中head为表头指针，p指向要交换的结点；在主函数中调用创建链表的函数创建一个单链表，并调用该函数，验证算法的正确性。要求：建立一个结点中含有三个域的单链表；在主函数中调用此算法，构成双向循环链表；在主函数中利用正向和逆向两种方式输出链表中的数据，验证算法的正确性。【实验报告】实习时间： 实习地点： 实习机号：具体实验内容#include#include#define NULL 0#define LEN sizeof(linklist)typedef struct nodeint data;struct node *next;linklist;linklist *creat()int i;linklist *head,*r,*q;q=(linklist *)malloc(LEN);head=q;r=q;q-next=NULL;printf(Please input the number: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);return head;void print(linklist *head)linklist *p;p=head-next;while(p!=0)printf(%dn,p-data);p=p-next;void deletelist(int i,linklist *head)linklist *p,*q;int k=1;p=head;q=p-next;while(q!=NULL)&(i!=k)k+;p=q;q=q-next;p-next=q-next;void insertlist(int i,int x,linklist *head)int k=0;linklist *p,*q,*p1;p=head;q=p-next;while(q!=NULL)&(knext;p1=(linklist *)malloc(LEN);p1-data=x;p1-next=p-next;p-next=p1;void main()int x,i,choice,n;linklist *head;head=creat();printf(Please input your choice:n 1.print 2.delete 3.insert 4.exitn);while(1)printf(Please input the choice:); scanf(%d,&choice);switch(choice)case 1:print(head);break;case 2:printf(Please input deletenumber n:);scanf(%d,&n);deletelist(n,head);print(head);break;case 3:printf(Please input i,x:);scanf(%d,%d,&i,&x);insertlist(i,x,head);print(head);break;case 4:break;default:break;if(choice=4) break;if(choice=5) printf(the input number is error!n);程序调试过程实习小结实验二 堆栈与队列【实验目的】1学习如何使用C语言实现堆栈与队列。2熟悉堆栈与队列的基本操作及应用。【实验内容】1 现有一顺序队列，其结构描述为：# define MAX 100typedef struct ElemType queueMaxQueueSize; int front; / 队头指针int count; / 计数器 QueueType;要求：设计队列的几种几种操作：初始化、进队、出队、取队头元素和判断队列是否非空。编写一个主函数进行测试。2顺序堆栈实验要求：设计堆栈的几种几种操作：初始化、入栈、出栈、取栈顶元素和判断堆栈是否非空。编写一个主函数进行测试。【实验报告】实习时间： 实习地点： 实习机号：具体实验内容#include#include#define LEN sizeof(quenode)typedef struct nodeint data;struct node *next;quenode;typedef structquenode *front,*rear;linkque;void initlque(linkque *lp)quenode *q;q=(quenode *)malloc(LEN);if(q=NULL)printf(内存分配不成功!n);elseprintf(内存分配成功!n);lp-front=q;lp-front-next=NULL;lp-rear=lp-front;void insertlque(linkque *lp, int x)quenode *p;p=(quenode *)malloc(LEN);p-data=x;p-next=NULL;lp-rear-next=p;lp-rear=p;void showlque(linkque *lp)quenode *p;p=lp-front-next;if(p=NULL)printf(the linkque is null!n);elsewhile(p!=NULL)printf(%dn,p-data);p=p-next;void exitlque(linkque *lq, int *x)quenode *p;p=lq-front-next;if(p=NULL)printf(the linkque is null!n);elselq-front-next=lq-front-next-next;*x=p-data;free(p);printf(the exiting number is:);printf(%dn,*x);void main()linkque q;int choice,x,m;printf(Please input your commander:n 1.initlinkque 2.insertlinkque 3.exitlinkque 4.showlinkque 5.exitn);while(1)printf(Please input the number:);scanf(%d,&choice);switch(choice)case 1:initlque(&q);break;case 2:printf(Please input x:);scanf(%d,&x);insertlque(&q,x);break;case 3:exitlque(&q,&m);break;case 4:showlque(&q);break;case 5:break;default:break;if(choice=5) break;程序调试过程实习小结实验三 队列与栈的应用必做：1、设一个算术表达式中包含圆括号、方括号和花括号三种类型的括号，编写一个算法判断其中的括号是否匹配。提示：本题使用一个运算符栈st，当遇到的（、或时进栈，当遇到、）时判断栈顶是否为相应的括号，若是退栈继续执行；否则算法结束。选做：2、假设以数组sequ0.MaxSize-1存放环形队列的元素，同时设变量rear和len分别指示环形队列中队尾元素的位置和内含元素的个数。试写出此环形队列队满的条件，并设计相应入队和出队的算法。（根据题目填空完善程序）提示：该环形队列对满的条件为：len= =MaxSize，队空的条件为：len= =0。由rear,len求队列头指针front的过程为： front=rear-len+1； if (front0) front=front+MaxSize；即 front=(rear-len+1+MaxSize)%MaxSize# include # define maxsize 6typedef char queue maxsize；int rear=0, len=0；int enqueue (queue qu, char x)if (len= =maxsize)return 0；elserear=(rear+1) %maxsize；qurear=x；len+；return 1；int dequeue (queue qu, char *x)int front；if (len= =0)return 0；elsefront=(rear-len+1+maxsize) %maxsize；*x=qufront；len-；return 1；void main()char x；queue qu；printf( “a入队n”）；enqueue (qu, a)；printf( “b入队n”）；enqueue (qu, b)；printf( “c入队n”）；enqueue (qu, c)；printf( “出队一次：”）；dequeue (qu, &x)；printf( “%cn”,x)；printf( “d入队n”）；enqueue (qu, d)；printf( “e入队n”）；enqueue (qu, e)；printf( “出队一次：”）；dequeue (qu, &x)；printf（“%cn”,x)；printf( “f入队n”）；enqueue (qu, f)；printf( “g入队n”）；enqueue (qu, g)；printf( “出队一次：”）；dequeue (qu, &x)；printf（“%cn”,x)；printf（“余下元素出列：”）；while (len0)dequeue (qu, &x)；printf（“%cn”,x)；printf（“n”）；输出：. 入队. 入队出队一次： . 入队. 入队出队一次： . 入队. 入队出队一次： 余下元素出列： 【实验报告】实习时间： 实习地点： 实习机号：具体实验内容#include#include#define LEN sizeof(linkstack)#define NULL 0typedef struct nodeint data;struct node *next;linkstack;void instack(linkstack *&top, int x)linkstack *p;p=(linkstack *)malloc(LEN);p-data=x;p-next=top;top=p;void outstack(linkstack *&top)linkstack *p;int x;p=top;if(p=NULL)printf(Stack is empty!n);/return NULL;/else top=p-next;x=p-data;free(p);printf(%dn,x);/return x;/void showstack(linkstack *&top)linkstack *p;p=top;if(p-data=0)printf(the stack is null!n);elsewhile(p-data!=0)printf(%dn,p-data);p=p-next;void initstack(linkstack *&top)top=(linkstack *)malloc(LEN);top-data=0;top-next=NULL;void main()int choice,x;linkstack *top;top=(linkstack *)malloc(LEN);top-data=0;top-next=NULL;printf(Please look at the choice: 1.instack 2.outstack 3.showstack 4.exitn);while(1)printf(Please input your choice:);scanf(%d,&choice);switch(choice)case 1:printf(Please input x:n);scanf(%d,&x);while(x!=0)instack(top,x);scanf(%d,&x);break;case 2:outstack(top);break;case 3: showstack(top);break; case 4:break;default:break;if(choice=4) break;if(choice=5) printf(the inputting number is error!n);程序调试过程实习小结实验四 树一、 实验目的 1.掌握二叉树，二叉树排序数的概念及存储方法。2.掌握二叉树的遍历算法。3.熟练掌握编写实现树的各种运算的算法。一、 实验内容 树的基本运算：创建树；输出树；遍历树；求二叉树的深度；创建二叉排序树；二叉排序树的查找；二叉排序树的删除；创造哈夫曼树；输出哈夫曼树；1、建立一棵二叉树并中序遍历。（填空） #include “ stdio.h”#include “malloc.h”struct node char data； struct node *lchild , *rchild； bnode；typedef struct node * blink；blink add(blink bt,char ch) if(bt=NULL) bt=nalloc(sizeof(bnode)； bt-data = ch； bt-lchild = bt-rchild =NULL； else if ( ch data) bt-lchild = add(bt-lchild ,ch)； else bt-rchild = add(bt-rchild,ch)； return bt；void inorder(blink bt) if(bt) inorder(bt-lchild)； printf（“%c”,bt-data）； inorder(bt-rchild)； main() blink root = null； int i,n； char x； scanf（“%c”,&n)； for(i=1；ilchild =NULL&bt-rchild=NULL) no+； preorder(bt-lchild；) preorder(bt-rchild；) blink creat() blink bt； char ch； ch = getchar()； if (ch!=#) bt= n