.实验一、单链表的插入和删除一、目的了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。

二、要求：建立一个数据域定义为字符串的单链表，在链表中不允许有重复的字符串；根据输入的字符串，先找到相应的结点，后删除之。

三、程序源代码#include"stdio.h"#include"string.h"#include"stdlib.h"#include"ctype.h"typedef struct node //定义结点{char data[10]; //结点的数据域为字符串struct node *next; //结点的指针域}ListNode;typedef ListNode * LinkList; // 自定义LinkList单链表类型LinkList CreatListR1(); //函数，用尾插入法建立带头结点的单链表ListNode *LocateNode(); //函数，按值查找结点void DeleteList(); //函数，删除指定值的结点void printlist(); //函数，打印链表中的所有值void DeleteAll(); //函数，删除所有结点，释放内存//==========主函数==============void main(){char ch[10],num[10];LinkList head;head=CreatListR1(); //用尾插入法建立单链表，返回头指针printlist(head); //遍历链表输出其值printf(" Delete node (y/n):");//输入“y”或“n”去选择是否删除结点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);}DeleteAll(head); //删除所有结点，释放内存}//==========用尾插入法建立带头结点的单链表===========LinkList CreatListR1(void){char ch[10];LinkList head=(LinkList)malloc(sizeof(ListNode)); //生成头结点ListNode *s,*r,*pp;r=head;r->next=NULL;printf("Input # to end "); //输入“#”代表输入结束printf("Please input Node_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 # to end ");printf("Please input Node_data:");scanf("%s",ch);}return head; //返回头指针}//==========按值查找结点，找到则返回该结点的位置，否则返回NULL==========ListNode *LocateNode(LinkList head, char *key){ListNode *p=head->next; //从开始结点比较while(p&&strcmp(p->data,key)!=0 ) //直到p为NULL或p-> data为key止p=p->next; //扫描下一个结点return p; //若p=NULL则查找失败，否则p指向找到的值key的结点}//==========删除带头结点的单链表中的指定结点======= void DeleteList(LinkList head,char *key){ListNode *p,*r,*q=head;p=LocateNode(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");}//==========删除所有结点，释放空间===========void DeleteAll(LinkList head){ListNode *p=head,*r;while(p->next){r=p->next;free(p);p=r;}free(p);}运行结果：加的添加结点的代码：int Insert(ListNode *head) // the insert function {ListNode *in,*p,*q;int wh;printf("input the insert node:");in=(ListNode *)malloc(sizeof(ListNode));in->next=NULL;p=(ListNode *)malloc(sizeof(ListNode));p->next=NULL;q=(ListNode *)malloc(sizeof(ListNode));q->next=NULL;if(!in)return 0;scanf("%s",in->data);printf("input the place where you want to insert you data:");scanf("%d",&wh);for(p=head;wh>0;p=p->next,wh--);q=p->next;p->next=in;in->next=q;return 1;}运行结果：最后提示为OK 添加成功。

实验心得：这个实验中主要修改的是ch 和num 把它们由指针改成数组因为不改的话在后面delect函数中会出现没有地址的情况找不到地址就不能执行功能然后把locate函数的判断语句改一下避免矛盾的出现。

实验二、二叉树操作一、目的掌握二叉树的定义、性质及存储方式，各种遍历算法。

二、要求采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。

三、程序源代码#include"stdio.h"#include"string.h"#define Max 20 //结点的最大个数typedef struct node{char 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(NULL); //读入#，返回空指针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(BinTree 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=TreeDepth(T->lchild); //求左深度hr=TreeDepth(T->rchild); //求右深度max=hl>hr? hl:hr; //取左右深度的最大值NodeNum=NodeNum+1; //求结点数if(hl==0&&hr==0) leaf=leaf+1; //若左右深度为0，即为叶子。