数据结构实验报告-答案

数据结构(C语言版)实验报告专业班级学号姓名实验1实验题目：单链表的插入和删除实验目的：了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。实验要求：建立一个数据域定义为字符串的单链表，在链表中不允许有重复的字符串；根据输入的字符串，先找到相应的结点，后删除之。实验主要步骤：1、分析、理解给出的示例程序。2、调试程序，并设计输入数据（如：bat，cat，eat，fat，hat，jat，lat，mat，#），测试程序的如下功能：不允许重复字符串的插入；根据输入的字符串，找到相应的结点并删除。3、修改程序：（1）增加插入结点的功能。（2）将建立链表的方法改为头插入法。程序代码:#includestdio.h#includestring.h#includestdlib.h#includectype.htypedefstructnode//定义结点{chardata[10];//结点的数据域为字符串structnode*next;//结点的指针域}ListNode;typedefListNode*LinkList;//自定义LinkList单链表类型LinkListCreatListR1();//函数，用尾插入法建立带头结点的单链表LinkListCreatList(void);//函数，用头插入法建立带头结点的单链表ListNode*LocateNode();//函数，按值查找结点voidDeleteList();//函数，删除指定值的结点voidprintlist();//函数，打印链表中的所有值voidDeleteAll();//函数，删除所有结点，释放内存ListNode*AddNode();//修改程序：增加节点。用头插法，返回头指针//==========主函数==============voidmain(){charch[10],num[5];LinkListhead;head=CreatList();//用头插入法建立单链表，返回头指针printlist(head);//遍历链表输出其值printf(Deletenode(y/n):);//输入y或n去选择是否删除结点scanf(%s,num);if(strcmp(num,y)==0||strcmp(num,Y)==0){printf(PleaseinputDelete_data:);scanf(%s,ch);//输入要删除的字符串DeleteList(head,ch);printlist(head);}printf(Addnode?(y/n):);//输入y或n去选择是否增加结点scanf(%s,num);if(strcmp(num,y)==0||strcmp(num,Y)==0){head=AddNode(head);}printlist(head);DeleteAll(head);//删除所有结点，释放内存}//==========用尾插入法建立带头结点的单链表===========LinkListCreatListR1(void){charch[10];LinkListhead=(LinkList)malloc(sizeof(ListNode));//生成头结点ListNode*s,*r,*pp;r=head;r-next=NULL;printf(Input#toend);//输入#代表输入结束printf(\nPleaseinputNode_data:);scanf(%s,ch);//输入各结点的字符串while(strcmp(ch,#)!=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#toend);printf(PleaseinputNode_data:);scanf(%s,ch);}returnhead;//返回头指针}//==========用头插入法建立带头结点的单链表===========LinkListCreatList(void){charch[100];LinkListhead,p;head=(LinkList)malloc(sizeof(ListNode));head-next=NULL;while(1){printf(Input#toend);printf(PleaseinputNode_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;}}elsebreak;}returnhead;}//==========按值查找结点，找到则返回该结点的位置，否则返回NULL==========ListNode*LocateNode(LinkListhead,char*key){ListNode*p=head-next;//从开始结点比较while(p!=NULL&&strcmp(p-data,key)!=0)//直到p为NULL或p-data为key止p=p-next;//扫描下一个结点returnp;//若p=NULL则查找失败，否则p指向找到的值为key的结点}//==========修改程序：增加节点=======ListNode*AddNode(LinkListhead){charch[10];ListNode*s,*pp;printf(\nPleaseinputaNewNode_data:);scanf(%s,ch);//输入各结点的字符串pp=LocateNode(head,ch);//按值查找结点，返回结点指针printf(ok2\n);if(pp==NULL){//没有重复的字符串，插入到链表中s=(ListNode*)malloc(sizeof(ListNode));strcpy(s-data,ch);printf(ok3\n);s-next=head-next;head-next=s;}returnhead;}//==========删除带头结点的单链表中的指定结点=======voidDeleteList(LinkListhead,char*key){ListNode*p,*r,*q=head;p=LocateNode(head,key);//按key值查找结点的if(p==NULL){//若没有找到结点，退出printf(positionerror);exit(0);}while(q-next!=p)//p为要删除的结点，q为p的前结点q=q-next;r=q-next;q-next=r-next;free(r);//释放结点}//===========打印链表=======voidprintlist(LinkListhead){ListNode*p=head-next;//从开始结点打印while(p){printf(%s,,p-data);p=p-next;}printf(\n);}//==========删除所有结点，释放空间===========voidDeleteAll(LinkListhead){ListNode*p=head,*r;while(p-next){r=p-next;free(p);p=r;}free(p);}实验结果：Input#toendPleaseinputNode_data:batInput#toendPleaseinputNode_data:catInput#toendPleaseinputNode_data:eatInput#toendPleaseinputNode_data:fatInput#toendPleaseinputNode_data:hatInput#toendPleaseinputNode_data:jatInput#toendPleaseinputNode_data:latInput#toendPleaseinputNode_data:matInput#toendPleaseinputNode_data:#mat,lat,jat,hat,fat,eat,cat,bat,Deletenode(y/n):yPleaseinputDelete_data:hatmat,lat,jat,fat,eat,cat,bat,Insertnode(y/n):yPleaseinputInsert_data:putposition:5mat,lat,jat,fat,eat,put,cat,bat,请按任意键继续...示意图：心得体会：本次实验使我们对链表的实质了解更加明确了，对链表的一些基本操作也更加熟练了。另外实验指导书上给出的代码是有一些问题的，这使我们认识到实验过程中不能想当然的直接编译执行，应当在阅读并完全理解代码的基础上再执行，这才是实验的意义所在。latjathatfateatcatbatmatNULLheadlatjathatfateatcatbatmatheadlatjatfateatputcatbatmatheadNULLNULL实验2实验题目：二叉树操作设计和实现实验目的：掌握二叉树的定义、性质及存储方式，各种遍历算法。实验要求：采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。实验主要步骤：1、分析、理解程序。2、调试程序，设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点（空指针），如ABD###CE##F##，建立二叉树，求出先序、中序和后序以及按层次遍历序列，求所有叶子及结点总数。实验代码#includestdio.h#includestdlib.h#includestring.h#defineMax20//结点的最大个数typedefstructnode{chardata;structnode*lchild,*rchild;}BinTNode;//自定义二叉树的结点类型typedefBinTNode*BinTree;//定义二叉树的指针intNodeNum,leaf;//NodeNum为结点数，leaf为叶子数//==========基于先序遍历算法创建二叉树==============//=====要求输入先序序列，其中加入虚结点#以示空指针的位置==========BinTreeCreatBinTree(void){BinTreeT;charch;if((ch=getchar())=='#')return(NULL);//读入#，返回空指针else{T=(BinTNode*)malloc(sizeof(BinTNode));//生成结点T-data=ch;T-lchild=CreatBinTree();//构造左子树T-rchild=CreatBinTree();//构造右子树return(T);}}//========NLR先序遍历=============voidPreorder(BinTreeT){if(T){printf(%c,T-data);//访问结点Preorder(T-lchild);//先序遍历左子树Preorder(T-rchild);//先序遍历右子树}}//========LNR中序遍历===============voidInorder(BinTreeT){if(T){Inorder(T-lchild);//中序遍历左子树printf(%c,T-data);//访问结点Inorder(T-rchild);//中序遍历右子树}}//======