线性链表二叉树的C语言实现.docx

1、线性链表二叉树的C语言实现目录目录 1线性链表的基本操作 2设计题目 2设计目的 2设计内容和要求 2数据结构及算法设计的思想 2数据结构及算法设计 3线性链表功能详细介绍 5二叉树的基本操作 7设计题目 7设计目的 7设计内容和要求 7数据结构及算法设计思想 7数据结构及算法设计 8二叉树功能详细介绍 9心得体会 11线性链表的基本操作设计题目 链表的基本操作设计目的1掌握线性链表的建立。 2掌握线性链表的基本操作。设计内容和要求利用链表的插入运算建立线性链表，然后实现链表的查找、插入、删除、计数、输出、排序、逆置等运算（查找、插入、删除、查找、计数、输出、排序、逆置要单独写成函数），并能在

2、屏幕上输出操作前后的结果。数据结构及算法设计的思想1、线性表的逻辑结构特征：总存在第一个元素和最后一个元素；除第一个元素外，每一个元素都有唯一的直接前驱元素；除最后一个个元素外，每一个元素都有唯一的直接后继元素。2、线性链表的特点：在单链表中，任何两个元素的存储位置之间没有固定的联系3、线性链表的存储结构特点：1）用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以不是连续的）2）插入和删除操作时要修改结点中的指针域。3）用线性链表表示线性表时，数据元素之间的逻辑关系是有结点中的指针指示的，换句话说，指针为数据元素之间的逻辑元素之间的逻辑关系的映像，则逻辑上相邻的两个数据

3、元素其存储物理位置不要求紧邻，由此，这种存储结构为非顺序映像或链式映像。4、线性链表的存取必须从头指针开始，头指针指示链表中第一个结点的存储位置；由于最后一个元素没有直接后继，则线性链表中最后一个结点的指针为“空”（NULL）。数据结构及算法设计1、 定义线性链表的单链表存储结构struct LinkList int data; struct LinkList *next;typedef struct LinkList LNode;typedef LNode *Link;2、 读取输入数据并建以此建立线性链表int LinkList(LNode *head,int n) LNode *newh

4、ead; int i; int d; newhead=(Link) malloc (sizeof(LNode); head=newhead; for(i=0;idata=d; newhead-next=(Link) malloc (sizeof(LNode); if(i=n-1) newhead-next=NULL; else newhead=newhead-next; return head;3、 线性链表的插入void LinkListInsert(LNode *head) LNode *ptr=head,*ptr2; int p; int e; int i; LNode *s; prin

5、tf(Please Input the positon :n); scanf(%d,&p); printf(Please Input the element :n); scanf(%d,&e); s=(Link) malloc (sizeof(LNode); s-data=e; for (i=1;inext; ptr2=ptr-next; s-next=ptr2; ptr-next=s; 4、 链表中元素的删除：读取输入的整数i并删除该位置的元素void Delete(LNode *head) LNode *ptr=head,*ptr2; int i,delPosition; printf(P

6、lease input the positon :n); scanf(%d,&delPosition); for (i=2;inext; ptr2=ptr-next; ptr-next=ptr2-next; free(ptr2); 5、 查找元素在链表中的位置void GetLinkList(LNode *head) LNode *ptr1=head; int findElem; int i=0; printf (Please input the element:); scanf(%d,&findElem); while (ptr1) if(ptr1-data!=findElem) ptr1=

7、ptr1-next; i+; else goto LOOP; LOOP: if(ptr1-data=findElem) printf(nThe locaton is %d.n,i+1); else printf(n Have not find the %d in the linear list.n,findElem);6、 计数：统计线性链表中元素的个数并输出void count (LNode *head) int i=0; LNode *ptr=head; while (ptr) ptr=ptr-next; i+; printf(There are(is) %d elem(s) in Lin

8、klist.n,i); 线性链表功能详细介绍（1）本程序包含6种功能，分别为：建立线性链表、插入、统计线性链表中元素个数、删除、查找、输出（2）选择功能1为建立线性链表 下图为建立线性链表包含4个元素，分别为1、2、3、4（3）功能2为在位置i插入元素图为在位置3插入元素5（4）功能3为删除位置i的元素下图为删除位置2上的元素（5）功能4为查找元素查找元素5在线性链表中的位置（6）功能6为计数即统计线性链表中元素的个数（7）功能5为输出线性链表中的元素线性链表（1、2、3、4）删除2并在位置3插入元素后的线性链表如图所示：二叉树的基本操作设计题目二叉树的建立与遍历设计目的1掌握二叉树的概念和性

9、质 2. 掌握任意二叉树存储结构 3掌握任意二叉树的基本操作设计内容和要求对任意给定的二叉树（顶点数自定）建立它的二叉链表存储结构，并实现二叉树的先序、中序、后序三种遍历，输出三种遍历的结果。数据结构及算法设计思想1、 二叉树的特点：二叉树是一种树形结构，它的特点是每个结点至多只有两棵子树，并且二叉树的子树有左右之分，其次序不能任意颠倒2、 二叉树的存储结构：包括顺序存储结构、链式存储结构3、 二叉树的遍历：a、 先序遍历二叉树：（1） 访问根节点；（2） 先序遍历左子树；（3） 先序遍历右子树；b、 中序遍历二叉树：（1） 中序遍历左子树；（2） 访问根节点；（3） 中序遍历右子树；c、 后

10、序遍历二叉树：（1） 后序遍历左子树；（2） 后序遍历右子树；（3） 访问根节点；数据结构及算法设计1、 建立二叉树BT *createbt(void)BT *q;struct nodel *s30;int j,i,x;printf(Build a Tree(end by (0,$)n);printf();printf(i,x=);scanf(%d,%c,&i,&x);while(i!=0&x!=$)q=(BT*)malloc(sizeof(BT); /* 开辟存储空间 */q-data=x;q-lchild=NULL;q-rchild=NULL;si=q;if(i!=1)j=i/2;if(i

11、%2=0) sj-lchild=q;else sj-rchild=q;printf(i,x=);scanf(%d,%c,&i,&x);return s1;2、 先序遍历二叉树void dlr_order(BT *bt)if(bt!=NULL) printf(%c ,bt-data); dlr_order(bt-lchild); dlr_order(bt-rchild);3、中序遍历二叉树void ldr_order(BT *bt)if(bt!=NULL) ldr_order(bt-lchild); printf(%c ,bt-data); ldr_order(bt-rchild);4、后序遍历

12、二叉树void lrd_order(BT *bt)if(bt!=NULL) ldr_order(bt-lchild); ldr_order(bt-rchild); printf(%c ,bt-data);二叉树功能详细介绍1、 建立二叉树分别输入（位置，数据）以（0，$）结束如图所示建立元素为235#8的二叉数2、 功能1先序遍历二叉树输入1继续3、 功能2中序遍历二叉树输入1继续4、 后序遍历二叉树输入0关闭窗口程序结束心得体会经过一周的实训我对数据结构这门课程有了更加深刻的了解。通过查找资料解决的不少课堂学习中有疑问的地方。同时在编辑程序过程中通过对每一个函数的琢磨、调试、修改加深了对于C语言的掌握。对熟悉的知识加深印象，对容易出错的地方提高警惕，从而使原本简单的程序变得复杂，机械的操作变得熟练。并在程序全部可以运行后又尝试着修改代码以寻求新的方法。只有多动手操作，才知道结果，才有创新的念头，只看课本，只掌握书上的内容是远远不够的。阅读他人编写的代码，多动手、勤动脑是学习计算机只是的捷径。