线性链表二叉树的C语言实现.docx
《线性链表二叉树的C语言实现.docx》由会员分享，可在线阅读，更多相关《线性链表二叉树的C语言实现.docx（13页珍藏版）》请在冰点文库上搜索。
线性链表二叉树的C语言实现
目录
目录1
线性链表的基本操作2
设计题目2
设计目的2
设计内容和要求2
数据结构及算法设计的思想2
数据结构及算法设计3
线性链表功能详细介绍5
二叉树的基本操作7
设计题目7
设计目的7
设计内容和要求7
数据结构及算法设计思想7
数据结构及算法设计8
二叉树功能详细介绍9
心得体会11
线性链表的基本操作
设计题目
链表的基本操作
设计目的
1．掌握线性链表的建立。
2．掌握线性链表的基本操作。
设计内容和要求
利用链表的插入运算建立线性链表，然后实现链表的查找、插入、删除、计数、输出、排序、逆置等运算（查找、插入、删除、查找、计数、输出、排序、逆置要单独写成函数），并能在屏幕上输出操作前后的结果。
数据结构及算法设计的思想
1、线性表的逻辑结构特征：
①总存在第一个元素和最后一个元素；
②除第一个元素外，每一个元素都有唯一的直接前驱元素；
③除最后一个个元素外，每一个元素都有唯一的直接后继元素。
2、线性链表的特点：
在单链表中，任何两个元素的存储位置之间没有固定的联系
3、线性链表的存储结构特点：
1）用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以不是连续的）
2）插入和删除操作时要修改结点中的指针域。
3）用线性链表表示线性表时，数据元素之间的逻辑关系是有结点中的指针指示的，换句话说，指针为数据元素之间的逻辑元素之间的逻辑关系的映像，则逻辑上相邻的两个数据元素其存储物理位置不要求紧邻，由此，这种存储结构为非顺序映像或链式映像。
4、线性链表的存取必须从头指针开始，头指针指示链表中第一个结点的存储位置；由于最后一个元素没有直接后继，则线性链表中最后一个结点的指针为“空”（NULL）。
数据结构及算法设计
1、定义线性链表的单链表存储结构
structLinkList
{
intdata;
structLinkList*next;
};
typedefstructLinkListLNode;
typedefLNode*Link;
2、读取输入数据并建以此建立线性链表
intLinkList（LNode*head,intn）
{
LNode*newhead;
inti;
intd;
newhead=（Link）malloc（sizeof（LNode））;
head=newhead;
for（i=0;i{
scanf（"%d",&d）;
newhead->data=d;
newhead->next=（Link）malloc（sizeof（LNode））;
if（i==n-1）newhead->next=NULL;
else
newhead=newhead->next;
}
returnhead;
}
3、线性链表的插入
voidLinkListInsert（LNode*head）
{
LNode*ptr=head,*ptr2;
intp;
inte;
inti;
LNode*s;
printf（"PleaseInputthepositon:
\n"）;
scanf（"%d",&p）;
printf（"PleaseInputtheelement:
\n"）;
scanf（"%d",&e）;
s=（Link）malloc（sizeof（LNode））;
s->data=e;
for（i=1;i{
ptr=ptr->next;
}
ptr2=ptr->next;
s->next=ptr2;
ptr->next=s;
}
4、链表中元素的删除：
读取输入的整数i并删除该位置的元素
voidDelete（LNode*head）
{
LNode*ptr=head,*ptr2;
inti,delPosition;
printf（"Pleaseinputthepositon:
\n"）;
scanf（"%d",&delPosition）;
for（i=2;i{
ptr=ptr->next;
}
ptr2=ptr->next;
ptr->next=ptr2->next;
free（ptr2）;
}
5、查找元素在链表中的位置
voidGetLinkList（LNode*head）
{
LNode*ptr1=head;
intfindElem;
inti=0;
printf（"Pleaseinputtheelement:
"）;
scanf（"%d",&findElem）;
while（ptr1）
{
if（ptr1->data!
=findElem）
{
ptr1=ptr1->next;
i++;
}
else
{
gotoLOOP;
}
}
LOOP:
if（ptr1->data==findElem）
{
printf（"\nThelocatonis%d.\n",i+1）;
}
else
printf（"\nHavenotfindthe[%d]inthelinearlist.\n",findElem）;
}
6、计数：
统计线性链表中元素的个数并输出
voidcount（LNode*head）
{
inti=0;
LNode*ptr=head;
while（ptr）
{
ptr=ptr->next;
i++;
}
printf（"Thereare（is）%delem（s）inLinklist.\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．掌握二叉树的概念和性质
2.掌握任意二叉树存储结构
3．掌握任意二叉树的基本操作
设计内容和要求
对任意给定的二叉树（顶点数自定）建立它的二叉链表存储结构，并实现二叉树的先序、中序、后序三种遍历，输出三种遍历的结果。
数据结构及算法设计思想
1、二叉树的特点：
二叉树是一种树形结构，它的特点是每个结点至多只有两棵子树，并且二叉树的子树有左右之分，其次序不能任意颠倒
2、二叉树的存储结构：
包括顺序存储结构、链式存储结构
3、二叉树的遍历：
a、先序遍历二叉树：
（1）访问根节点；
（2）先序遍历左子树；
（3）先序遍历右子树；
b、中序遍历二叉树：
（1）中序遍历左子树；
（2）访问根节点；
（3）中序遍历右子树；
c、后序遍历二叉树：
（1）后序遍历左子树；
（2）后序遍历右子树；
（3）访问根节点；
数据结构及算法设计
1、建立二叉树
BT*createbt（void）
{
BT*q;
structnodel*s[30];
intj,i,x;
printf（"BuildaTree（endby（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;
s[i]=q;
if（i!
=1）
{
j=i/2;
if（i%2==0）s[j]->lchild=q;
elses[j]->rchild=q;
}
printf（"i,x="）;
scanf（"%d,%c",&i,&x）;
}
returns[1];
}
2、先序遍历二叉树
voiddlr_order（BT*bt）
{
if（bt!
=NULL）
{
printf（"%c",bt->data）;
dlr_order（bt->lchild）;
dlr_order（bt->rchild）;
}
}
3、中序遍历二叉树
voidldr_order（BT*bt）
{
if（bt!
=NULL）
{
ldr_order（bt->lchild）;
printf（"%c",bt->data）;
ldr_order（bt->rchild）;
}
}
4、后序遍历二叉树
voidlrd_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语言的掌握。
对熟悉的知识加深印象，对容易出错的地方提高警惕，从而使原本简单的程序变得复杂，机械的操作变得熟练。
并在程序全部可以运行后又尝试着修改代码以寻求新的方法。
只有多动手操作，才知道结果，才有创新的念头，只看课本，只掌握书上的内容是远远不够的。
阅读他人编写的代码，多动手、勤动脑是学习计算机只是的捷径。
升级会员 