数据结构（C语言版）实验报告.doc

1、实验 1实验题目：单链表的插入和删除实验目的：了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。实验要求：建立一个数据域定义为字符串的单链表，在链表中不允许有重复的字符串；根据输入的字符串，先找到相应的结点，后删除之。实验主要步骤：1、分析、理解给出的示例程序。2、调试程序，并设计输入数据（如：bat，cat ，eat，fat，hat，jat，lat ，mat，#） ，测试程序的如下功能：不允许重复字符串的插入；根据输入的字符串，找到相应的结点并删除。3、修改程序：（1） 增加插入结点的功能。（2） 将建立链表的方法改为头插入法。程序代码:#include“s

2、tdio.h“#include“string.h“#include“stdlib.h“#include“ctype.h“typedef struct node /定义结点char data10; /结点的数据域为字符串struct node *next; /结点的指针域ListNode;typedef ListNode * LinkList; / 自定义 LinkList 单链表类型LinkList CreatListR1(); /函数，用尾插入法建立带头结点的单链表LinkList CreatList(void); /函数，用头插入法建立带头结点的单链表ListNode *LocateNod

3、e(); /函数，按值查找结点void DeleteList(); /函数，删除指定值的结点void printlist(); /函数，打印链表中的所有值void DeleteAll(); /函数，删除所有结点，释放内存ListNode * AddNode(); /修改程序：增加节点。用头插法，返回头指针/=主函数=void main()char ch10,num5;LinkList head;head=CreatList(); /用头插入法建立单链表，返回头指针printlist(head); /遍历链表输出其值printf(“ Delete node (y/n):“); /输入“y“或“n

4、“ 去选择是否删除结点scanf(“%s“,num);if(strcmp(num,“y“)=0 | strcmp(num,“Y“)=0)printf(“Please input Delete_data:“);scanf(“%s“,ch); /输入要删除的字符串DeleteList(head,ch);printlist(head);printf(“ Add node ? (y/n):“); /输入“y“或“n“ 去选择是否增加结点scanf(“%s“,num);if(strcmp(num,“y“)=0 | strcmp(num,“Y“)=0)head=AddNode(head);printlis

5、t(head);DeleteAll(head); /删除所有结点，释放内存/=用尾插入法建立带头结点的单链表=LinkList CreatListR1(void)char ch10;LinkList head=(LinkList)malloc(sizeof(ListNode); /生成头结点ListNode *s,*r,*pp;r=head;r-next=NULL;printf(“Input # to end “); /输入“#“代表输入结束printf(“nPlease input Node_data:“);scanf(“%s“,ch); /输入各结点的字符串while(strcmp(ch,

6、“#“)!=0) pp=LocateNode(head,ch); /按值查找结点，返回结点指针if(pp=NULL) /没有重复的字符串，插入到链表中s=(ListNode *)malloc(sizeof(ListNode);strcpy(s-data,ch);r-next=s;r=s;r-next=NULL;printf(“Input # to end “);printf(“Please input Node_data:“);scanf(“%s“,ch);return head; /返回头指针/=用头插入法建立带头结点的单链表=LinkList CreatList(void)char ch1

7、00;LinkList head,p;head=(LinkList)malloc(sizeof(ListNode); head-next=NULL;while(1)printf(“Input # to end “); printf(“Please input Node_data:“);scanf(“%s“,ch); if(strcmp(ch,“#“) if(LocateNode(head,ch)=NULL) strcpy(head-data,ch);p=(LinkList)malloc(sizeof(ListNode); p-next=head;head=p;else break;return

8、 head; /=按值查找结点，找到则返回该结点的位置，否则返回 NULL=ListNode *LocateNode(LinkList head, char *key)ListNode *p=head-next; /从开始结点比较while(p!=NULL /扫描下一个结点return p; /若 p=NULL 则查找失败，否则 p 指向找到的值为 key 的结点/=修改程序：增加节点=ListNode * AddNode(LinkList head)char ch10;ListNode *s,*pp;printf(“nPlease input a New Node_data:“);scanf

9、(“%s“,ch); /输入各结点的字符串pp=LocateNode(head,ch); /按值查找结点，返回结点指针printf(“ok2n“);if(pp=NULL) /没有重复的字符串，插入到链表中s=(ListNode *)malloc(sizeof(ListNode);strcpy(s-data,ch);printf(“ok3n“);s-next=head-next;head-next=s;return head;/=删除带头结点的单链表中的指定结点=void DeleteList(LinkList head,char *key)ListNode *p,*r,*q=head;p=Lo

10、cateNode(head,key); /按 key 值查找结点的if(p=NULL ) /若没有找到结点，退出printf(“position error“);exit(0);while(q-next!=p) /p 为要删除的结点，q 为 p 的前结点q=q-next;r=q-next;q-next=r-next;free(r); /释放结点/=打印链表=void printlist(LinkList head)ListNode *p=head-next; /从开始结点打印while(p)printf(“%s, “,p-data);p=p-next;printf(“n“);/=删除所有结点，

11、释放空间=void DeleteAll(LinkList head)ListNode *p=head,*r;while(p-next)r=p-next;free(p);p=r;free(p);实验结果：Input # to end Please input Node_data:batInput # to end Please input Node_data:catInput # to end Please input Node_data:eatInput # to end Please input Node_data:fatInput # to end Please input Node_da

12、ta:hatInput # to end Please input Node_data:jatInput # to end Please input Node_data:latInput # to end Please input Node_data:matInput # to end Please input Node_data:#mat, lat, jat, hat, fat, eat, cat, bat,Delete node (y/n):yPlease input Delete_data:hatmat, lat, jat, fat, eat, cat, bat,Insert node

13、(y/n):yPlease input Insert_data:putposition :5mat, lat, jat, fat, eat, put, cat, bat,请按任意键继续. . .示意图：lat jat hat fat eat cat batmatNULLheadlat jathatfat eat cat batmatheadlat jat fat eatputcat batmatheadNULLNULL心得体会：本次实验使我们对链表的实质了解更加明确了，对链表的一些基本操作也更加熟练了。另外实验指导书上给出的代码是有一些问题的，这使我们认识到实验过程中不能想当然的直接编译执行，

14、应当在阅读并完全理解代码的基础上再执行，这才是实验的意义所在。实验 2实验题目：二叉树操作设计和实现实验目的：掌握二叉树的定义、性质及存储方式，各种遍历算法。实验要求：采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。实验主要步骤：1、分析、理解程序。2、调试程序，设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点（空指针） ，如 ABD#CE#F#，建立二叉树，求出先序、中序和后序以及按层次遍历序列，求所有叶子及结点总数。实验代码#include“stdio.h“#include“stdlib.h“#include“stri

15、ng.h“#define Max 20 /结点的最大个数typedef struct nodechar data;struct node *lchild,*rchild;BinTNode; /自定义二叉树的结点类型typedef BinTNode *BinTree; /定义二叉树的指针int NodeNum,leaf; /NodeNum 为结点数，leaf 为叶子数/=基于先序遍历算法创建二叉树=/=要求输入先序序列，其中加入虚结点“#“以示空指针的位置=BinTree CreatBinTree(void)BinTree T;char ch;if(ch=getchar()=#)return(N

16、ULL); /读入#，返回空指针else T= (BinTNode *)malloc(sizeof(BinTNode); /生成结点T-data=ch;T-lchild=CreatBinTree(); /构造左子树T-rchild=CreatBinTree(); /构造右子树return(T);/=NLR 先序遍历=void Preorder(BinTree T)if(T) printf(“%c“,T-data); /访问结点Preorder(T-lchild); /先序遍历左子树Preorder(T-rchild); /先序遍历右子树/=LNR 中序遍历=void Inorder(BinTr

17、ee T)if(T) Inorder(T-lchild); /中序遍历左子树printf(“%c“,T-data); /访问结点Inorder(T-rchild); /中序遍历右子树/=LRN 后序遍历=void Postorder(BinTree T)if(T) Postorder(T-lchild); /后序遍历左子树Postorder(T-rchild); /后序遍历右子树printf(“%c“,T-data); /访问结点/=采用后序遍历求二叉树的深度、结点数及叶子数的递归算法=int TreeDepth(BinTree T)int hl,hr,max;if(T)hl=TreeDept

18、h(T-lchild); /求左深度hr=TreeDepth(T-rchild); /求右深度max=hlhr? hl:hr; /取左右深度的最大值NodeNum=NodeNum+1; /求结点数if(hl=0 /若左右深度为 0，即为叶子。return(max+1);else return(0);/=利用“先进先出“（FIFO）队列，按层次遍历二叉树=void Levelorder(BinTree T)int front=0,rear=1;BinTNode *cqMax,*p; /定义结点的指针数组 cqcq1=T; /根入队while(front!=rear) front=(front+1

19、)%NodeNum;p=cqfront; /出队printf(“%c“,p-data); /出队，输出结点的值 if(p-lchild!=NULL)rear=(rear+1)%NodeNum;cqrear=p-lchild; /左子树入队if(p-rchild!=NULL)rear=(rear+1)%NodeNum;cqrear=p-rchild; /右子树入队/=数叶子节点个数 =int countleaf(BinTree T)int hl,hr;if(T)hl=countleaf(T-lchild);hr=countleaf(T-rchild);if(hl=0else return hl+

20、hr;else return 0;/=主函数=void main()BinTree root;char i;int depth;printf(“n“);printf(“Creat Bin_Tree； Input preorder:“); /输入完全二叉树的先序序列，/ 用#代表虚结点，如 ABD#CE#F#root=CreatBinTree(); /创建二叉树，返回根结点do /从菜单中选择遍历方式，输入序号。printf(“t* select *n“);printf(“t1: Preorder Traversaln“); printf(“t2: Iorder Traversaln“);pri

21、ntf(“t3: Postorder traversaln“);printf(“t4: PostTreeDepth,Node number,Leaf numbern“);printf(“t5: Level Depthn“); /按层次遍历之前，先选择 4，求出该树的结点数。printf(“t0: Exitn“);printf(“t*n“);fflush(stdin);scanf(“%c“, /输入菜单序号（0-5）switch (i-0)case 1: printf(“Print Bin_tree Preorder: “);Preorder(root); /先序遍历break;case 2:

22、printf(“Print Bin_Tree Inorder: “);Inorder(root); /中序遍历break;case 3: printf(“Print Bin_Tree Postorder: “);Postorder(root); /后序遍历break;case 4: depth=TreeDepth(root); /求树的深度及叶子数printf(“BinTree Depth=%d BinTree Node number=%d“,depth,NodeNum);printf(“ BinTree Leaf number=%d“,countleaf(root);break;case 5: printf(“LevePrint Bin_Tree: “);Levelorder(root); /按层次遍历break;default: exit(1);printf(“n“); while(i!=0); 实验结果：Creat Bin_Tree； Input preorder:ABD#CE#F# * select * 1: Preorder Traversal 2: Iorder Traversal 3: Postorder traversal 4: PostTreeDepth,Node number,Leaf number