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

实验一 线性表的基本操作 一、实验目的与基本要求1掌握数据结构中的一些基本概念。数据、数据项、数据元素、数据类型和数据结构，以及它们之间的关系。2 了解数据的逻辑结构和数据的存储结构之间的区别与联系；数据的运算与数据的逻辑结构的关系。3 掌握线性表的基本操作：插入、删除、查找以及线性表的合并等运算。4 掌握运用C语言上机调试线性表的基本方法。二、实验条件1 硬件：一台微机2 软件：操作系统和C语言系统三、实验方法确定存储结构后，上机调试实现线性表的基本运算。四、实验内容1 试编写在无头结点的单链表上实现线性表基本运算LOCATE（L，X），INSERT（L，X，1）和DELETE（L，1）的算法。2 假设有两个按数据元素值递增有序排列的线性表A和B，均以单链表作为存储结构。编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许值相同）排列的线性表C，并要求利用原表（即A表和B表）结点空间存放表C。3 将一个线性表中的值就地逆置。4 在线性表的顺序存储结构的第一个位置上插入一个元素。（注意区分链表和顺序表）实验代码：#includestdlib.h#includestdio.hstruct node /定义结构体int d;struct node *next;struct node *head1,*head2,*p,*q;void pre(struct node *head) /打印数据printf(链表中的数据为：n);p=head;while(p!=NULL)printf(%5d,p-d);q=p;p=p-next;printf(n);struct node *creat() /建立链表struct node *head;int x;printf(输入你要储存的数据：n);head=NULL;q=NULL;scanf(%d,&x);while(x0)p=(struct node *)malloc(sizeof(struct node);p-d=x;p-next=NULL;if(head=NULL) head=p;else q-next=p;q=p;scanf(%d,&x);getchar();pre(head);return (head);void locate(struct node *head,int x) /查找链表中的数据int u=1;p=head;while (p-next!= NULL) if (p-d=x) break; else p=p-next;u+; if(p-d!= x)printf(无此结点);printf(在链表中的位置为：);printf(%d,u);void insert(struct node *head,int x, int i) /插入数据 p = head;int j=1; q=(struct node *)malloc(sizeof(struct node); q-d=x;if(i=1) q-next=head; head=q;elsewhile(jnext !=NULL)j+;p=p-next;q-next=p-next;p-next=q;void delet(struct node *head,int i) /删除数据 p=head;int j=1;if(inext; free(q);elsewhile(jnext != NULL) p=p-next;j+;q=p-next; p-next=q-next; free(q);void hebing(struct node *x,struct node *y) /合并两个链表p=x;q=y;while(p-next!=NULL)p=p-next;p-next=q;pre(x);void paixu(struct node *head) /对链表中的数据进行排序int m,n,i=1,t;p=head;while(p-next!=NULL)p=p-next;i+;p=head;for(n=i;n1;n-)p=head;for(m=1;mnext;if(p-dd)t=p-d;p-d=q-d;q-d=t;p=p-next; void caozuo(struct node *head) /操作界面int m,n;char t;printf(输入你要的操作：，查找 2，插入 3，删除n);scanf(%c,&t);switch(t)case 1:printf(输入你要查找的元素的值：n); scanf(%d,&m);locate(head,m);break;case 2:printf(输入你要插入的元素的值和位置：n); scanf(%d,&m);scanf(%d,&n);insert(head,m,n);pre(head);break;case 3:printf(输入你要删除的元素的位置：n); scanf(%d,&m);delet(head,m);pre(head);break;default:printf(errorn);void main() /主函数char frag=y,n=NULL;printf(输入你要建立的第A链表中的元素：n);head1=creat();printf(输入你要建立的第B链表中的元素：n);head2=creat();doprintf(选择你要操作的链表A/B或者合并排序操作C：n); /选择操作scanf(%c,&n);getchar();switch(n) case A:caozuo(head1);break;case B:caozuo(head2);break;case C:hebing(head1,head2);paixu(head1);pre(head1);break;default:printf(errorn);printf(n是否继续y/n：n); scanf(%c,&frag); getchar();while(frag=y);实验2 栈和队列的基本操作一、实验目的与基本要求1掌握栈和队列的顺序存储和链式存储结构2 掌握栈和队列的特点。3 掌握栈和队列的基本运算。二、实验条件1硬件：一台微型计算机2软件：操作系统和C语言系统。三、实验方法确定存储结构后，上机调试实现栈和队列的基本运算。四、实验内容1 写出栈的入栈和出栈的算法2 写出队列的入队和出队算法。实验代码：#includestdlib.h#includestdio.hstruct nodeint d;struct node *next;int num;struct node *head;void pre()struct node *p;printf(链表中的数据为：n);p=head;while(p!=NULL)printf(%5d,p-d);p=p-next;printf(n);void creat()struct node *p,*q;int x;printf(输入你要储存的数据，输入负数作为结束：n);head=NULL;q=NULL;scanf(%d,&x);while(x0)num+;p=(struct node *)malloc(sizeof(struct node);p-d=x;p-next=NULL;if(head=NULL) head=p;else q-next=p;q=p;scanf(%d,&x);getchar();pre();void insert(int x, int i) struct node *p,*q;p = head;int j=1; q=(struct node *)malloc(sizeof(struct node); q-d=x;if(i=1) q-next=head; head=q;elsewhile(jnext !=NULL)j+;p=p-next;q-next=p-next;p-next=q;void delet(int i) struct node *p,*q;p=head;int j=1;if(inext; free(q);elsewhile(jnext != NULL) p=p-next;j+;q=p-next; p-next=q-next; free(q);void push() int n;num+;printf(请输入数据：);scanf(%d,&n);getchar();insert(n,num);pre();void pop()delet(num);num-;pre();void rudui()int n;num+;printf(请输入数据：);scanf(%d,&n);getchar();insert(n,1);pre();void chudui()delet(num);num-;pre();void main()char frag=y;int n;creat();doprintf(选择你要的操作入栈出栈入队出队：n);scanf(%d,&n);getchar();switch(n)case 1:printf(入栈操作);push();printf(n);break;case 2:printf(出栈操作);pop();printf(n);break;case 3:printf(入队操作);rudui();printf(n);break;case 4:printf(出队操作);chudui();printf(n);break;default:printf(errorn);printf(n是否继续y/n：n); scanf(%c,&frag); getchar();while(frag=y);实验3 二叉树的构造一、实验目的与基本要求熟练掌握二叉树的构造方法。二、实验条件1硬件：微机2软件：操作系统和C语言系统三、实验方法确定存储结构后，上机调试二叉树的构造方法。四、实验内容设计一个读入一串整数构成一棵二叉树的程序。（深度至少为2）实验代码：#include#includestruct btnode /二叉树结构体char d;struct btnode *lchild;struct btnode *rchild;struct btnode *creatbt(struct btnode *bt,int k) /建立二叉树struct btnode *p,*t;t=(struct btnode *)malloc(sizeof(struct btnode);printf(输入元素(输入时结束所在分枝):);char b;scanf(%c,&b);getchar();if(b!=0)p=(struct btnode *)malloc(sizeof(struct btnode);p-d=b;p-lchild=NULL;p-rchild=NULL;if(k=0)t=p;if(k=1)bt-lchild=p;if(k=2)bt-rchild=p;creatbt(p,1);creatbt(p,2);return t;void pretrav(struct btnode *bt) /前序遍历if(bt!=NULL)printf(%cn,bt-d);pretrav(bt-lchild);pretrav(bt-rchild);return;void intrav(struct btnode *bt) /中序遍历if(bt!=NULL)intrav(bt-lchild);printf(%cn,bt-d);intrav(bt-rchild);return;void postrav(struct btnode *bt) /后序遍历if(bt!=NULL)postrav(bt-lchild);postrav(bt-rchild);printf(%cn,bt-d);return;int main()struct btnode *m;char frag=y;int s;do printf(请选择n1、建立二叉树n2、前序遍历n3、中序遍历n4、后序遍历n5、退出n);scanf(%d,&s);getchar();switch(s)case 1:m=creatbt(0,0);break;case 2:pretrav(m);break;case 3:intrav(m);break;case 4:postrav(m);break;default:printf(是否继续n y/n);scanf(%c,&frag);getchar();break;while(frag=y);实验4 排序的基本操作一、实验目的与基本要求1掌握常用的排序方法，并用高级语言实现排序算法。2理解排序的定义和各种排序的特点。3了解排序过程以及依据的原则，并了解各种排序方法的时间复杂度分析。二、实验条件1硬件：一台微机2软件：操作系统和C语言系统三、实验方法确定存储结构后，上机调试不同的排序方法。四、实验内容1设计一待排序的线性表以顺序存储结构存储，试写出冒泡排序算法。2给出n个学生的考试成绩表，每条信息由姓名与分数组成，试设计一个算法：（1）按分数高低次序，打印出每个学生在考试中获得的名次，分数相同的为同一名次。（2）按名次列出每个学生的姓名与分数。实验代码:#includestdlib.h#includestdio.hstruct node /结构体变量int f;int m;char n;struct node *next;void pre(struct node *head) /打印数据struct node *p;printf(链表中的数据为：n);printf(名次 姓名 分数n);p=head;while(p!=NULL)printf(%5d,p-m);printf(%5c,p-n);printf(%5d,p-f);printf(n);p=p-next;printf(n);int num;s