河南科技大学计算机软件技术基础实验指导书及参考代码.doc
《河南科技大学计算机软件技术基础实验指导书及参考代码.doc》由会员分享,可在线阅读,更多相关《河南科技大学计算机软件技术基础实验指导书及参考代码.doc(19页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、目 录实验一单链表的运算2实验二 二叉树的建立和遍历5实验三 二叉排序树的建立和查找6实验四 windows操作系统及应用9实验五 数据库建立10实验六 数据库查询12附录13实验一单链表的运算一、 实验目的1掌握单链表的基本运算:建立、插入和删除2掌握运用C语言上机调试单链表的基本方法。二、 实验环境操作系统和C语言系统三、 预习要求了解单链表的建立、插入和删除算法,编写完整的程序。四、 实验内容设计算法,实现线性结构上的单链表的产生以及元素的查找、插入与删除。具体实现要求:(1)从键盘输入n个整数,以0作为结束标记,产生不带表头的单链表,并输入结点值。(2)从键盘输入1个整数,在单链表中查
2、找该结点的位置。若找到,则显示“找到了”;否则显示“找不到”。(3)从键盘输入2个整数,一个表示欲插入的位置i,另一个表示欲插入的数值x,将x插入在对应位置上,输出单链表所有结点值,观察输出结果。(4)从键盘输入1个整数,表示欲删除结点的位置,输出单链表所有结点值,观察输出结果。五、 参考算法#include #include /*单链表的定义*/typedef int DataType;/*DataType可以是任何相应的数据类型如int, float或char*/typedef struct node/*结点类型定义*/DataType data;/*结点的数据域*/struct node
3、 *next;/*结点的指针域*/ListNode;typedef ListNode *LinkList;void main()int i;DataType key,x;LinkList head;ListNode *p;LinkList CreateList(void);void PrintList(LinkList head);LinkList LocateNode(LinkList head,DataType key);LinkList GetNode(LinkList head,int i);void InsertList(LinkList *head,DataType x,int i
4、);void DeleteList(LinkList *head,int i);/clrscr();head=CreateList();/*建立单链表*/PrintList(head);/*打印单链表*/printf(n输入要查找的值:);scanf(%d,&key);p=LocateNode(head,key);/*单链表查找*/printf(n请输入欲插入元素的位置:);scanf(%d,&i);printf(n请输入欲插入的元素:);scanf(%d,&x);InsertList(&head,x,i);/*单链表插入*/PrintList(head);/*打印单链表*/printf(n请
5、输入欲删除结点的位置:);scanf(%d,&i);DeleteList(&head,i);/*单链表删除*/PrintList(head);/*打印单链表*/*单链表的建立,从后向前生成*/LinkList CreateList(void) LinkList head,p; int x; head=NULL; printf(input some inteagers until 0!); scanf(%d,&x); while(x) p=(LinkList)malloc(sizeof(ListNode); /*以下三行:新建结点并初始化*/ p-data=x; p-next=NULL; if(
6、head=NULL) head=p; else p-next=head;head=p; scanf(%d,&x); return (head);/*单链表的打印*/void PrintList(LinkList head) LinkList p; p=head; while(p!=NULL) printf(%5d,p-data); p=p-next; /*单链表的查找,输入一个整数,显示该结点的位置*/LinkList LocateNode(LinkList head,DataType key)/*在不带头结点的单链表head中查找其值为key的结点*/ LinkList p; if(head
7、=NULL)printf(List is null!);return (head); if(head-data=key)printf(the wanted data is:%d,head-data);return (head); p=head; while(p-data!=key)&(p=NULL) p=p-next; if(p!=NULL)printf(the wanted data is:%d,p-data); else printf(the wanted data is not found!); return (p);/*单链表的查找2,在不带头结点的单链表head中查找第i个结点*/L
8、inkList GetNode(LinkList head,int i) LinkList p; int n=1; p=head; while(p!=NULL)&(ni) if(nnext; return (p);/*单链表的插入*/void InsertList(LinkList *head,DataType x,int i)/*将值为x的新结点插入到不带头结点的单链表head的第i个结点的位置上*/ LinkList p,q; p=(LinkList)malloc(sizeof(ListNode);/*以下三行:新建结点并初始化*/ p-data=x; p-next=NULL; if(in
9、ext=*head;*head=p; else/*找到要插入的前一个位置,然后插入*/ q=GetNode(*head,i-1); p-next=q-next; q-next=p; /*单链表的删除,删除不带头结点的单链表中的第i个结点*/void DeleteList(LinkList *head,int i) LinkList p,q; if(i=0)|(*head=NULL)printf(List is null or inext);free(*head);*head=p;return; p=*head; while(p!=NULL)&(-i0) q=p;p=p-next; if(p=N
10、ULL)printf(iL!); else q-next=p-next;free(p);实验二 二叉树的建立和遍历一、 实验目的1掌握二叉树的建立算法2掌握二叉树的前序、中序和后序遍历算法。二、 实验环境操作系统和C语言系统三、 预习要求复习二叉树的生成及遍历算法,编写完整的程序。四、 实验内容要求采用二叉链表作为存储结构,完成二叉树的建立,前序、中序和后序遍历的操作,求所有叶子及结点总数的操作等。具体实现要求:分别利用前序遍历、中序遍历、后序遍历所建二叉树。五、 参考算法二叉树的建立算法思路:主要利用二叉树的性质:在编号的完全二叉树中,编号为i的结点如果存在左孩子,则其编号为2i;若其存在右
11、孩子,则其编号为2i+1;若存在父结点,则其编号为i/2取整。对任意二叉树,先按满二叉树对其进行编号,算法中使用一个辅助向量s来存放指向树结点的指针。如si中存放编号为i的结点的指针,即为该结点的地址。当结点编号i=1时,所产生的结点为根结点,同时将指向该结点的指针存入s1。当结点编号i1时,产生一个新的结点后,也要将指向该结点的指针存入si,由上述性质可知:j=i/2为它的双亲结点编号。如果i为偶数,则它是双亲结点的左孩子,即让sj-lch=si;若i为奇数,则它是双亲结点的右孩子,即让sj-rch=si。这样就将新输入的结点逐一与其双亲结点相连,生成二叉树。二叉树的遍历算法可以使用递归算法
12、实现,也可采用非递归算法实现,可参考教材上算法实现。#include #include #include /*二叉树的定义*/typedef char DataType;/*DataType可以是任何相应的数据类型如int, float或char*/typedef struct btnode/*结点类型定义*/DataType data;/*结点的数据域*/struct btnode *lchild;/*结点的左指针域*/struct btnode *rchild;/*结点的右指针域*/BtNode;void main()DataType ch20;BtNode *s20,*bt,*p;int
13、 i=0;/* 以下三行按照前中后序遍历二叉树的函数声明*/void pretrav(BtNode *bt);void intrav(BtNode *bt);void postrav(BtNode *bt);/*按满二叉树编号后的顺序输入结点字符,空的位置用#代替,字符个数不要超过20个*/printf(ninput some characters:);scanf(%s, ch);/*输入结点字符*/for(i=0; idata = chi;p-lchild = NULL;p-rchild = NULL;si = p;if(chi = #)continue;/*如果输入的是#,即该位置没有结点
14、,无需找其父节点*/if(i 0)if(i%2 = 1) si/2-lchild = p; /*根据i的奇偶性,将p结点链到其父节点的(左/右?)指针上*/else si/2-1-rchild = p; /*将p结点链到其父节点的(左/右?)指针上*/for(i=0; ilchild!=NULL & si-rchild!=NULL)printf(%c,%c,%cn,si-data,si-lchild-data,si-rchild-data);else if(si-lchild!=NULL) printf(%c,%c,%cs rchild is NULL!n,si-data,si-lchild-
15、data,si-data);else if(si-rchild!=NULL) printf(%c,%cs lchild is NULL!,%cn,si-data,si-data,si-rchild-data);else printf(%c,%cis a leaf!n,si-data,si-data);/* 以下按照前中后序遍历二叉树*/printf(npretrav!);pretrav(s20);printf(nintrav!);intrav(s20);printf(npostrav!);postrav(s20);printf(n);while(1);/*前序遍历二叉树*/void pretr
16、av(BtNode *bt)BtNode *p;p = bt;if(p != NULL)printf(%c,p-data);pretrav(bt-lchild);pretrav(bt-rchild);return;/*中序遍历二叉树*/ void intrav(BtNode *bt)if(bt != NULL)intrav(bt-lchild);printf(%c,bt-data);intrav(bt-rchild);return;/*后序遍历二叉树*/void postrav(BtNode *bt)if(bt != NULL)postrav(bt-lchild);postrav(bt-rch
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 河南 科技大学 计算机 软件技术 基础 实验 指导书 参考 代码
限制150内