单链表的插入和删除实验报告.doc
《单链表的插入和删除实验报告.doc》由会员分享,可在线阅读,更多相关《单链表的插入和删除实验报告.doc(42页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、*- 实验一、单链表的插入和删除一、目的了解和掌握线性表的逻辑结构和链式存储结构,掌握单链表的基本算法及相关的时间性能分析。二、要求:建立一个数据域定义为字符串的单链表,在链表中不允许有重复的字符串;根据输入的字符串,先找到相应的结点,后删除之。三、程序源代码#includestdio.h#includestring.h#includestdlib.h#includectype.htypedef struct node /定义结点 char data10; /结点的数据域为字符串struct node *next; /结点的指针域 ListNode;typedef ListNode * Lin
2、kList; / 自定义LinkList单链表类型LinkList CreatListR1(); /函数,用尾插入法建立带头结点的单链表ListNode *LocateNode(); /函数,按值查找结点void DeleteList(); /函数,删除指定值的结点void printlist(); /函数,打印链表中的所有值void DeleteAll(); /函数,删除所有结点,释放内存/=主函数=void main() char ch10,num10; LinkList head; head=CreatListR1(); /用尾插入法建立单链表,返回头指针 printlist(head)
3、; /遍历链表输出其值 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 ch10; Lin
4、kList 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 *)mallo
5、c(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 ) /
6、直到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
7、-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 *hea
8、d) / the insert functionListNode *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
9、want to insert you data:);scanf(%d,&wh);for(p=head;wh0;p=p-next,wh-);q=p-next;p-next=in;in-next=q;return 1;运行结果:最后提示为OK 添加成功。实验心得:这个实验中 主要修改的是ch 和 num 把它们由指针改成数组 因为不改的话在后面delect函数中会出现没有地址的情况 找不到地址就不能执行功能 然后把locate函数的判断语句改一下 避免矛盾的出现。实验二、二叉树操作一、 目的掌握二叉树的定义、性质及存储方式,各种遍历算法。二、 要求采用二叉树链表作为存储结构,完成二叉树的建立,先序
10、、中序和后序以及按层次遍历的操作,求所有叶子及结点总数的操作。三、 程序源代码#includestdio.h#includestring.h#define Max 20 /结点的最大个数typedef struct node char data; struct node *lchild,*rchild;BinTNode; /自定义二叉树的结点类型typedef BinTNode *BinTree; /定义二叉树的指针int NodeNum,leaf; /NodeNum为结点数,leaf为叶子数/=基于先序遍历算法创建二叉树=/=要求输入先序序列,其中加入虚结点“#”以示空指针的位置=BinTr
11、ee 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-lchil
12、d); /先序遍历左子树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); /访问结点 /=采用后序遍历求二叉树
13、的深度、结点数及叶子数的递归算法=int TreeDepth(BinTree T) int hl,hr,max; if(T)hl=TreeDepth(T-lchild); /求左深度hr=TreeDepth(T-rchild); /求右深度max=hlhr? hl:hr; /取左右深度的最大值NodeNum=NodeNum+1; /求结点数if(hl=0&hr=0) leaf=leaf+1; /若左右深度为0,即为叶子。return(max+1); else return(0);/=利用“先进先出”(FIFO)队列,按层次遍历二叉树=void Levelorder(BinTree T) int
14、 front=0,rear=1; BinTNode *cqMax,*p; /定义结点的指针数组cq cq1=T; /根入队 while(front!=rear) front=(front+1)%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; /右子树入队 /=主函数=void main() Bi
15、nTree root; int i,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);printf(t3: Postorder traversaln);printf(t4: PostTr
16、eeDepth,Node number,Leaf numbern);printf(t5: Level Depthn); /按层次遍历之前,先选择4,求出该树的结点数。printf(t0: Exitn);printf(t*n);scanf(%d,&i); /输入菜单序号(0-5)switch (i)case 1: printf(Print Bin_tree Preorder: );Preorder(root); /先序遍历break;case 2: printf(Print Bin_Tree Inorder: );Inorder(root); /中序遍历break;case 3: printf(
17、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,leaf);break;case 5: printf(LevePrint Bin_Tree: );Levelorder(root); /按层次遍历break;default: exit(1);printf(n); whi
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 单链表 插入 以及 删除 实验 试验 报告 讲演 呈文
限制150内