《数据结构(用C语言描述)ppt课件(完整版).ppt》由会员分享，可在线阅读，更多相关《数据结构(用C语言描述)ppt课件(完整版).ppt（356页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、21世纪高职高专创新精品规划教材世纪高职高专创新精品规划教材(用C语言描述)第一章绪论第二章线性表第三章栈和队列第四章其他线性数据结构第五章树和二叉树第六章图第七章查找第八章排序目录1.1什么是数据结构1.2基本概念和术语1.3数据结构课程的内容1.4算法和算法分析1.5算法性能分析与度量第一章第一章 绪论绪论1.1什么是数据结构数据结构（数据结构（Data Structure）是计算机及相关专业）是计算机及相关专业的技术基础课，是十分重要的核心课程。所有的计的技术基础课，是十分重要的核心课程。所有的计算机系统软件和应用软件都要用到各种类型的数据算机系统软件和应用软件都要用到各种类型的数据结构
2、。结构。只要我们建立了相关的数据结构，按照某种算法编只要我们建立了相关的数据结构，按照某种算法编写了相关程序，就可以实现计算机自动检索。写了相关程序，就可以实现计算机自动检索。问题：问题：通过计算机查找某个学生的有关情况或者想查询某个专业或年级的学生的有关情况。分析：建立一张按学号顺序排列的学生信息表和分别按姓名、专业、年级顺序排列的索引表，便可实现相关的查询学生信息检索系统案例1学号姓名性别专业年级980001吴承志男计算机科学与技术98级980002李淑芳女信息与计算科学98级990301刘丽女数学与应用数学99级990302张会友男信息与计算科学99级990303石宝国男计算机科学与技术
3、99级000801何文颖女计算机科学与技术2000级000802赵胜利男数学与应用数学2000级000803崔文靖男信息与计算科学2000级010601刘丽女计算机科学与技术2001级010602魏永鸣男数学与应用数学2001级学生信息表计算机科学与技术1，5，6，9信息与计算科学2，4，8数学与应用数学3，7，102000级6，7，82001级9，1098级1，299级3，4，5专业索引表年级索引表记录号12345678910学生信息检索系统案例1崔文靖8何文颖6李淑芳2刘丽3，9石宝国5魏永鸣10吴承志1赵胜利7张会有4姓名索引表学号姓名性别专业年级980001吴承志男计算机科学与技术98
4、级980002李淑芳女信息与计算科学98级990301刘丽女数学与应用数学99级990302张会友男信息与计算科学99级990303石宝国男计算机科学与技术99级000801何文颖女计算机科学与技术2000级000802赵胜利男数学与应用数学2000级000803崔文靖男信息与计算科学2000级010601刘丽女计算机科学与技术2001级010602魏永鸣男数学与应用数学2001级学生信息表记录号12345678910教学计划编排问题教学计划编排问题案例2问题：问题：如何通过计算机编排教学计划？算法分析：算法分析：一个教学计划包含许多课程，在教学计划包含的许多课程之间，有些必须按规定的先后次序
5、进行，有些则没有次序要求。即有些课程之间有先修和后续的关系，有些课程可以任意安排次序。这种各个课程之间的次序关系可用一个称作图的数据结构来表示课程编号课程名称先修课程C1计算机导论无C2数据结构C1，C4C3汇编语言C1C4C程序设计语言C1C5计算机图形学C2，C3，C4C6接口技术C3C7数据库原理C2，C9C8编译原理C4C9操作系统C2（a）计算机专业的课程设置C1C2C3C6C4C5C9C7C8（b）表示课程之间优先关系的有向图图1.2教学计划编排问题的数据结构由以上两个例子可见，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树、图之类的数据结构。因此，可以说数据结构课
6、程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。目的是为了了解计算机处理对象的特性，将实际问题中所涉及的处理对象在计算机中表示出来并对它们进行处理。1.2基本概念和术语数据（Data）：信息的载体，它能够被计算机识别、存储和加工处理。数据元素（DataElement）：数据的基本单位。在不同的条件下，数据元素又可称为元素、结点、顶点、记录等。数据对象（DataObject）或数据元素类（DataElementClass）：具有相同性质的数据元素的集合。数据结构是指互相之间存在着一种或多种关系的数据元素的集合。数据元素之间的关系称为结构。根据数据元素间
7、关系的不同特性，通常有下列四类基本的结构：集合结构。在集合结构中，数据元素间的关系是“属于同一个集合”。集合是元素关系极为松散的一种结构。线性结构。该结构的数据元素之间存在着一对一的关系。树型结构。该结构的数据元素之间存在着一对多的关系。图形结构。该结构的数据元素之间存在着多对多的关系，图形结构也称作网状结构。（a）集合结构（b）线性结构（c）树型结构（d）图形结构图1.3四类基本结构的示意图集合结构如集合结构如:整数集合整数集合1 1、3 3、-5-5、200200、0 0字母集合字母集合A A、b b、C C、z z线性结构线性结构A,B,C,，X,Y,Z学生成绩表86胡孝臣9861103
8、95刘忠赏9861107100张卓9861109成绩姓名学号线性表线性表结点间是以线性关系联结结点间是以线性关系联结线性表栈队树形结构树形结构全校学生档案管理的组织方式全校学生档案管理的组织方式计算机程序管理系统也是典型的树形结构计算机程序管理系统也是典型的树形结构ABCDEFGH树形结构结点间具有分层次的连接关系HBCDEFGA1423D=1,2,3,4R=(1,2),(1,3),(1,4),(2,3)(3,4),(2,4)213D=1,2,3R=(1,2),(2,3),(3,2),(1,3)图形结构图形结构节点间的连结是任意的节点间的连结是任意的一个数据结构有两个要素。一个是数据元素的集合
9、，另一个是关系的集合。可以采用一个二元组来表示。Data_Structure（D，R）有限个数据有限个数据元素的集合元素的集合有限个元素间关有限个元素间关系的集合系的集合数据的逻辑结构形式如：数据的逻辑结构形式如：集合结构集合结构:松散式前后数据元素没有关联松散式前后数据元素没有关联,如整数类型的数据；如整数类型的数据；线线 性性 式：数据元素按一定顺序排列式：数据元素按一定顺序排列,元素间存在一对一关系；元素间存在一对一关系；树状结构：像自然界的树树状结构：像自然界的树,元素间存在一对多关系元素间存在一对多关系,如文件夹；如文件夹；图状网络图状网络:数据元素间多对多关系数据元素间多对多关系,
10、如城市交通网。如城市交通网。数据结构包括数据的逻辑结构（LogicalStructure）和数据的物理结构（PhyicalStructure）。数据结构包括数据的逻辑结构（LogicalStructure）和数据的物理结构（PhyicalStructure）。计算机管理图书问题计算机管理图书问题 在图书馆里有各种卡片：有按书名编排的、在图书馆里有各种卡片：有按书名编排的、有按作者编排的、有按分类编排有按作者编排的、有按分类编排如何将查询图书的这些信息存入计算机中如何将查询图书的这些信息存入计算机中既要考虑查询时间短，又要考虑节省空间既要考虑查询时间短，又要考虑节省空间也叫存储结构。每一个数据元
11、素的也叫存储结构。每一个数据元素的存放形式及逻辑结构机内表示形式，存放形式及逻辑结构机内表示形式，元素的表示及元素间关系元素的表示及元素间关系最简单的办法之一是建立一张表，最简单的办法之一是建立一张表，每一本书的信息在表中占一行，如每一本书的信息在表中占一行，如 有四种存储方式有四种存储方式 ：顺顺 序序 方方 式式 ：数据元素逻辑上相连物理上也相连；：数据元素逻辑上相连物理上也相连；链式存储方式：数据元素逻辑上相连物理通过指针相连；链式存储方式：数据元素逻辑上相连物理通过指针相连；索引存储方式：数据元素通过索引表相连系；索引存储方式：数据元素通过索引表相连系；散列存储方式：数据元素通过散列函
12、数相连系；散列存储方式：数据元素通过散列函数相连系；数据元素在计算机中的表示数据元素在计算机中的表示,又称数据的物理结构又称数据的物理结构数据结构包括数据的逻辑结构（LogicalStructure）和数据的物理结构（PhyicalStructure）。1.3数据结构课程的内容方面层次数据表示数据处理抽象逻辑结构基本运算实现存储结构算法评价不同数据结构的比较及算法分析图1.5数据结构体系的课程内容1.4 1.4 算法的基本概念算法的基本概念算算法法：是是对对特特定定问问题题求求解解步步骤骤的的一一种种描描述述，使得问题能在有限时间内被机械求解求解。算法的五个特性：算法的五个特性：有穷性、确定性
13、、可行性、输入和输出。有穷性、确定性、可行性、输入和输出。评价算法：评价算法：正确性、易读性、健壮性、高效。正确性、易读性、健壮性、高效。算法的五个特性：算法的五个特性：有穷性：有穷性：一个算法必须在执行有穷步之后结束。一个算法必须在执行有穷步之后结束。确定性：确定性：算算法法的的每每一一步步必必须须是是确确切切定定义义的的。对对于于相相同同输输入入必必须须得得到相同结果到相同结果 。可行性：可行性：算法的每一步都是能够实现的，即可操作的。算法的每一步都是能够实现的，即可操作的。输入：输入：一一个个算算法法具具有有零零个个或或多多个个输输入入，这这些些输输入入取取自自特特定定的的数数据对象集合
14、据对象集合输出：输出：算法执行完毕，必须有一个或若干个输出结果。算法执行完毕，必须有一个或若干个输出结果。1.5 算法性能分析与度量算法性能分析与度量时间复杂度一个程序的时间复杂度（TimeComplexity）是指程序运行从开始到结束所需要的时间。一般情况下，算法中原操作重复执行的次数是规模n的某个函数T(n)。许多时候要精确地计算T(n)是困难的，我们引入渐进时间复杂度在数量上估计一个算法的执行时间，也能够达到分析算法的目的。定义（大记号）：如果存在两个正常数c和n0，使得对所有的n，nn0，有：f(n)cg(n)则有：f(n)(g(n)例如，一个程序的实际执行时间为T(n)2.7n3+3
15、.8n2+5.3则T(n)(n3)。通常用(1)表示常数计算时间。常见的渐进时间复杂度有：(1)(log2n)(n)(nlog2n)(n2)(n3)(2n)空间复杂度是指程序运行从开始到结束所需的存储量。程序运行所需的存储空间包括以下两部分：固定部分。这部分空间与所处理数据的大小和个数无关，或者称与问题的实例的特征无关。主要包括程序代码、常量、简单变量、定长成分的结构变量所占的空间。可变部分。这部分空间大小与算法在某次执行中处理的特定数据的大小和规模有关。例如100个数据元素的排序算法与1000个数据元素的排序算法所需的存储空间显然是不同的。计算例1：计算下面程序段的时间复杂度temp=a;/
16、*执行1次*/a=b;/*执行1次*/b=temp;/*执行1次*/分析：以上三个语句均执行一次，该程序段的执行时间是一个与n无关的常数，因此，时间的复杂度为常数阶，记做T（n）=O(1)。计算例2：计算下面程序段的时间复杂度S=1;/*执行1次*/for(i=1;i=n;i+）/*执行n次*/S=S*i;/*执行n次*/分析：以上语句共执行了2n+1次，故T（n）=2n1时间复杂度记为：T（n）O(n)计算例3：计算下面程序段的时间复杂度inti=1;while(i=n)i=i*2;分析：设循环为k次，则：2k-1n2k，取对数有：k-1log2nk即：klog2n+12*log2n(当n为
17、大于1的整数时成立)故时间复杂度为：T(n)=O(log2n)第二章第二章 线性表线性表目录2.1线性表的定义及逻辑结构2.2线性表的基本操作2.3线性表的顺序存储结构2.3.1顺序表2.3.2顺序表上基本运算的实现2.3.3案例分析2.4线性表的链式存储结构2.4.1单链表2.4.2单链表上的基本运算2.4.3循环链表2.4.4双向链表2.4.6案例分析2.5顺序表和链表的比较线线性性表表是是n个个元元素素的的有有限限序序列列，它它们们之之间间的的关关系可以排成系可以排成一个接一个一个接一个的线性序列：的线性序列：a1，a2，ai，ai+1，an其中其中n称作表的长度，当称作表的长度，当n=
18、0时，称作空表。时，称作空表。起始结点起始结点没有前驱没有前驱终端结点终端结点没有后继没有后继i i为序号为序号ai为为ai+1的前驱的前驱ai+1为为ai的后继的后继2.1线性表的定义及逻辑结构线性表的定义及逻辑结构2.除第一个和最后一个数据元素之外，其它除第一个和最后一个数据元素之外，其它数据元素有且仅有一个前驱和一个后继。数据元素有且仅有一个前驱和一个后继。第一个数据元素无前驱，第一个数据元素无前驱，最后一个数据元素无后继。最后一个数据元素无后继。线性表的特点：线性表的特点：1.线性表中所有元素的线性表中所有元素的数据类型数据类型相同。相同。3.由由序号序号决定数据元素在表中的位置。决定
19、数据元素在表中的位置。在线性表上常用的运算有：在线性表上常用的运算有：初始化（建立空表）初始化（建立空表）求长度求长度取表元取表元按值查找按值查找插入操作插入操作删除操作删除操作2.2线性表的基本操作线性表的基本操作an.ai.a2a1元素2.3.1顺序表顺序表顺序存储是将逻辑上相邻的数据元素存储在物理上相邻的存储单元里。即元素按一定的次序一个接一个排好后依次存入到连续的存储空间里.2000+(n-1)*2.2000+(i-1)*2.20022000地址设a的存储地址为Loc(a)，每个数据元素占d个存储地址，则第i个数据元素的地址为：Loc(ai)=Loc(a)+(i-1)*d1=i=n如右
20、图：a1=2000,d=22.3线性表的顺序存储结构线性表的顺序存储结构第第1个元素个元素第第2个元素个元素第第i个元素个元素DataDataDatai-1i-1Datan-1n-1元素元素a a1 1元素元素a a2 2.元素元素a ai i.元素元素N N可用可用C语言中的一维数组来描述语言中的一维数组来描述.#defineMaxsize100/*预留数组的最大容量预留数组的最大容量*/typedefstructdatatypeDataMaxsize;intlastSeqList,*L线性表的顺序存储结构定义线性表的顺序存储结构定义线性表的顺序存储结构定义线性表的顺序存储结构定义LastL
21、astdatalast maxsizeL L最多能存放最多能存放MaxsizeMaxsize个元素个元素 Last=Last=最后一个元素数组下标值，值最后一个元素数组下标值，值=Maxsize-1.L-DataiDatai最后一个数组元素的引用用最后一个数组元素的引用用LastLast表示时方式有：表示时方式有：L.DataL.lastL.DataL.last或或L-DataL-lastL-DataL-last元素元素a an n.元素元素a ai i.元素元素a a2 2元素元素a a1 1bb+db+(i-1)*d存储地址存储地址内存状态内存状态第第i个元素的个元素的ai存储地址：存储地
22、址：Loc(ai)=Loc(a1)+(i-1)*dLoc(ai)=b+（i-1)*d顺序存储结构示意图顺序存储结构示意图顺序存储结构示意图顺序存储结构示意图首地址首地址起始地址起始地址基地址基地址d d为每个元素为每个元素所占用的存所占用的存储单元个数储单元个数b+(maxlen-1)*d在访问线性表时，可以利在访问线性表时，可以利用上述给出的数学公式，用上述给出的数学公式，快速地计算出任何一个数快速地计算出任何一个数据元素的存储地址。据元素的存储地址。SeqList*init_SeqList()SeqList*L;L=malloc(sizeof(SeqList);L-last=-1;retu
23、rnL;2.3.2顺序表上基本运算的实现顺序表上基本运算的实现主函数的调用主函数的调用main()main()SeqList*Q;SeqList*Q;Q=init_SeqList();Q=init_SeqList();.1.顺序表的初始化顺序表的初始化ai-1.a2a1anai+1aixai-1.a2a1aiai+1an01i-1a2a1anai+1aiin-1.2.插入运算插入运算aiai+1an.x xai-1.a2a1alastai+1aixint Insert_SeqList(SeqList*L，int i，datatype x)int j;if(L-last=MAXSIZE1)pri
24、ntf(表满表满);return(-1);/*表空间已满，不表空间已满，不能插入能插入*/if(iL-last+2)/*检查插入位置的正确性检查插入位置的正确性*/printf(位置错位置错);return(0);for(j=L-last;j=i-1;j-)L-dataj+1=L-dataj;/*结点移动结点移动*/L-datai-1=x;/*新元素插入新元素插入*/L-last+;/*last仍指向最后元素仍指向最后元素*/return(1);/*插入成功，返回插入成功，返回*/datalastmaxsizeai-1.a2a1aiai+1alastx第第i i位置位置(位置位置从从1 1开始
25、数开始数)直到找到第直到找到第i i位位在第在第i位置插入运算位置插入运算.a2a1an.ai+1aii-1i第第n位位i数组下标last=n-1aiai+1an.注意数组下注意数组下标从标从0 0开始开始顺序插入运算的算法分析顺序插入运算的算法分析插入运算算法：插入运算算法：ai-1.a2a1aiai+1an当当i=1i=1时，时，每个元素每个元素均要后移均要后移一位，共一位，共移动移动n n次次xx当当i=n+1i=n+1时，时，每个元素均每个元素均不需要后移，不需要后移，共移动共移动0 0次次最坏情况时间复杂性为最坏情况时间复杂性为n,n,量级为量级为O(n);O(n);时间的平均复杂性
26、为：时间的平均复杂性为：n+1n+1(0+1+2+.+n(0+1+2+.+n)=2 2n n设有设有n n个元素个元素:在第在第i i位置上插入一个元素位置上插入一个元素,须移动须移动n-i+1n-i+1个元素个元素,在等概率下在等概率下,可插入元素的位置为可插入元素的位置为n+1,n+1,每个位置上插入元素的概率为每个位置上插入元素的概率为:Pi=1/(n+1)Pi=1/(n+1)插入操作的时间复杂度为插入操作的时间复杂度为:Ein=P Ein=P1 1*n+P*n+P2 2*(n-1)+P*(n-1)+P3 3*(n-2)+.+*(n-2)+.+P Pn-1n-1*2+P*2+Pn n*1
27、+P*1+Pn+1n+1*0*0 =n/2 =n/2 时间复杂度为时间复杂度为O(n)O(n)ai-1.a2a1anai+1aidelete_seqlist（Seqlist*L，inti）intj;if（iL.last+1）printf(不不 存存 在在 第第 i个个 元元 素素 );return(0);for(j=i;j=L.last;j+)L.dataj-1=L.dataj;L.last=L.last-1;datalastmaxsizeai-1.a2a1ai+1an第第i i位置位置元素为元素为datai-datai-11j=lastj=i-1j=i.a2a1an.ai+1ai第第last
28、+1last+1个个元素元素第第1 1个元素个元素data0data03.删除第删除第i位置元素运算位置元素运算i i为元素位置为元素位置,j,j为下标值为下标值删除运算算法：删除运算算法：ai-1.a2a1aiai+1an当当i=1i=1时，后时，后面每个元素面每个元素均要前移一均要前移一位，共移动位，共移动n-1n-1次次当当i=ni=n时，时，每个元素每个元素均不需要均不需要前移，共前移，共移动移动0 0次次最坏情况时间复杂性为最坏情况时间复杂性为n-1,n-1,量级为量级为O(n);O(n);时间的平均复杂性为：时间的平均复杂性为：=n n(0+1+.+(n-1)(0+1+.+(n-1
29、)2 2n-1n-1顺序删除运算的算法分析顺序删除运算的算法分析设有设有n n个元素个元素:在第在第i i位置上删除一个元素位置上删除一个元素,须移动须移动n-in-i个元素个元素,在等概率下在等概率下,可删除元素的位置为可删除元素的位置为n n个个,每个位每个位置上删除元素的概率为置上删除元素的概率为:Pi=1/n:Pi=1/n 插入操作的时间复杂度为插入操作的时间复杂度为:Ein=P Ein=P1 1*(n-1)+P*(n-1)+P2 2*(n-2)+P*(n-2)+P3 3*(n-3)+.*(n-3)+.+P +Pn-1n-1*1+P*1+Pn n*0 *0 =(n-1)/2 =(n-1
30、)/2 时间复杂度为时间复杂度为O(n)O(n)分析插入和删除算法可得如下结论分析插入和删除算法可得如下结论:顺序存储结构表示的线性表，在做插入顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移动大约一半的数据或删除操作时，平均需要移动大约一半的数据元素。当线性表的数据元素量较大，并且经常元素。当线性表的数据元素量较大，并且经常要对其做插入或删除操作时，这一点需要值得要对其做插入或删除操作时，这一点需要值得考虑。考虑。ai-1.a2a1anai+1ai=xint Location_SeqList(SeqList*L,datatype x)int i=0;while(idatai!=x)
31、i+;if(iL-last)return-1;elsereturn i;/*返回的是存储位置返回的是存储位置*/.a2a1an.ai+1ai=xdata(i-1)ai-1.a2a1aiai+1anx返回下标返回下标在顺序表中找出第一个值为在顺序表中找出第一个值为x的元素下标值的运算的元素下标值的运算4.定位定位 (按值查找按值查找)data(0)data(0)若要返若要返回序号回序号(位置位置号号)程程序如何序如何修改修改?ai-1.a2a1anai+1ai定位运算算法：定位运算算法：当当x=x=a1时，共时，共需需1 1次比次比较操作较操作当当x=x=an时，共需时，共需比较比较n n次次最
32、坏情况时间复杂性为最坏情况时间复杂性为n,n,量量级为级为O(n);O(n);时间的平均复杂性为：时间的平均复杂性为：=n n(1+2+.+n)(1+2+.+n)2 2n+1n+1顺序定位运算的算法分析顺序定位运算的算法分析2.3.3案例分析案例分析案例案例1：问题：问题：将两个递增有序的顺序表A、B，进行合并成一个递增有序的顺序表C，并要求同样的数据元素在新表中只出现一次。算法分析：算法分析：两个顺序表按递增方式排列，在进行合并时，依次比较，哪个线性表中的元素值小就先将这个元素复制到新的线性表中，若两个元素相等，则复制一个即可，一直到其中的一个线性表中的元素全部复制到新表后，将另一个表中剩余
33、的元素复制到新表中即可。算法见2.3.3_1算法的时间性能是O(m+n)，其中m是A的表长，n是B的表长。例2问题：问题：将顺序表(a1，a2，.，an)重新排列为以ai为界的两部分：ai前面的值均比ai小，ai后面的值都比ai大(这里假设数据元素的类型具有可比性,不妨设为整型)，这一操作称为划分。ai也称为基准。基本思路：从第二个元素开始到最后一个元素，逐一向后扫描：当前数据元素aj比ai大时，表明它已经在ai的后面，不必改变它与ai之间的位置，继续比较下一个。当前结点若比ai小，说明它应该在ai的前面，此时将它上面的元素都依次向下移动一个位置，然后将它置入最上方。voidpart(SeqL
34、ist*L)inti,j;datatypex,y;x=L-data0;/*将基准置入x中*/for(i=1;ilast;i+)if(L-dataidatai;for(j=i-1;j=0;j-)/*移动*/Ldataj+1=L-dataj;L-data0=y;例3问题：问题：比较两个线性表的大小。两个线性表的比较依据下列方法：设A、B是两个线性表，均用向量表示，表长分别为m和n。A和B分别为A和B中除去最大共同前缀后的子表。例如A=(x,y,y,z,x,z)，B=(x,y,y,z,y,x,x,z)，两表最大共同前缀为(x,y,y,z)。则A=（x,z），B=（y,x,x,z），若A=B=空表，则
35、A=B；若A=空表且B空表，或两者均不空且A首元素小于B首元素，则AB。例3算法实现如下：intcompare(A,B,m,n)intA,B;intm,n;inti=0,j,AS,BS,ms=0,ns=0;/*AS,BS作为A,B*/while(Ai=Bi)i+;/*找最大共同前缀*/for(j=i;jm;j+)ASj-i=Aj;ms+;/*求A,ms为A的长度*/for(j=i;j0|ms0&ns0&AS0P-nextP P元素元素ai的的结点结点指针指针P P指向指向ai，P-next指向指向ai+1线性表的链式存储结构描述线性表的链式存储结构描述线性表的链式存储结构描述线性表的链式存储结
36、构描述 通常指针通常指针P P是一个动态变量，在需要时由库函是一个动态变量，在需要时由库函数数malloc(size)malloc(size)产生，如产生，如:p=malloc(sizeof(Lnode)p=malloc(sizeof(Lnode)该函数分配一个该函数分配一个LnodeLnode数据类型所占的空间长度存放数据元素并数据类型所占的空间长度存放数据元素并返回一个该空间的起始地址给指针返回一个该空间的起始地址给指针P P。当该结点不再需要时，可由当该结点不再需要时，可由free(p)free(p)释放空间。释放空间。p-data p-data表示一个数据元素；表示一个数据元素；p-n
37、ext p-next表示下一个元素的起始存放地址的指表示下一个元素的起始存放地址的指针。针。创立单链表创立单链表(在表头添加在表头添加在表头添加在表头添加)LinkList Creat_LinkList1()LinkList L=NULL；/*空表空表*/Lnode*s;int x;/*设数据元素的类型为设数据元素的类型为int*/scanf(%d,&x);while(x!=flag)s=malloc(sizeof(LNode);s-data=x;s-next=L;L=s;Scanf(%d,&x);return L;L L2.4.2 单链表上的基本运算单链表上的基本运算创立单链表创立单链表(在
38、表头添加在表头添加在表头添加在表头添加)linklistcreat_linklist()linklistL=null;LNode*s;intx;scanf(“%d”,&x)；while(x!=-1)/设设flag值为值为-1s=malloc(sizeof(LNode)；s-data=x;s-next=L;L=s；scanf(%d”,&x)；returnL;L L2525s sx=25x=25L L创立单链表创立单链表(在表头添加在表头添加在表头添加在表头添加)linklistcreat_linklist()linklistL=null;LNode*s;intx;scanf(“%d”,&x)；w
39、hile(x!=-1)s=malloc(sizeof(LNode)；s-data=x;s-next=L;L=s；scanf(%d”,&x)；returnL;x=45x=454545s sL L2525 L Llinklistcreat_linklist()linklistL=null;LNode*s;intx;scanf(“%d”,&x)；while(x!=-1)s=malloc(sizeof(LNode)；s-data=x;s-next=L;L=s；scanf(%d”,&x)；returnL;x=18x=184545s s2525 L L1818s sL L创立单链表创立单链表(在表头添加在
40、表头添加在表头添加在表头添加)linklistcreat_linklist()linklistL=null;LNode*s;intx;scanf(“%d”,&x)；while(x!=-1)s=malloc(sizeof(LNode)；s-data=x;s-next=L;L=s；scanf(%d”,&x)；returnL;x=76x=764545s s2525 1818L L7676s sL L创立单链表创立单链表(在表头添加在表头添加在表头添加在表头添加)linklistcreat_linklist()linklistL=null;Lnode*s,*r=null;intx;scanf(“%d”
41、,&x)；while(x!=-1)s=malloc(sizeof(LNode)；s-data=x;if(L=null)L=s；elser-next=s；r=s；scanf(%d”,&x)；if(r!=nullr-next=null)；returnL;NULLL Lr r创立单链表创立单链表(在表尾添加在表尾添加在表尾添加在表尾添加)NULLL Lr rx xs slinklistcreat_linklist()linklistL=null;Lnode*s,*r=null;intx;scanf(“%d”,&x)；while(x!=-1)s=malloc(sizeof(LNode)；s-data=
42、x;if(L=null)L=s；elser-next=s；r=s；scanf(%d”,&x)；if(r!=nullr-next=null)；returnL;x=29x=29创立单链表创立单链表(在表尾添加在表尾添加在表尾添加在表尾添加)r rL L29297676s slinklistcreat_linklist()linklistL=null;Lnode*s,*r=null;intx;scanf(“%d”,&x)；while(x!=-1)s=malloc(sizeof(LNode)；s-data=x;if(L=null)L=s；elser-next=s；r=s；scanf(%d”,&x)；i
43、f(r!=nullr-next=null)；returnL;x=76x=76r r创立单链表创立单链表(在表尾添加在表尾添加在表尾添加在表尾添加)linklistcreat_linklist()linklistL=null;Lnode*s,*r=null;intx;scanf(“%d”,&x)；while(x!=-1)s=malloc(sizeof(LNode)；s-data=x;if(L=null)L=s；elser-next=s；r=s；scanf(%d”,&x)；if(r!=nullr-next=null)；returnL;x=18x=18r rL L29297676r rr r1818
44、创立单链表创立单链表(在表尾添加在表尾添加在表尾添加在表尾添加)linklistcreat_linklist()linklistL=null;Lnode*s,*r=null;intx;scanf(“%d”,&x)；while(x!=-1)s=malloc(sizeof(LNode)；s-data=x;if(L=null)L=s；elser-next=s；r=s；scanf(%d”,&x)；if(r!=nullr-next=null)；returnL;x=45x=451818r rL L29297676r rr r4545s sr r创立单链表创立单链表(在表尾添加在表尾添加在表尾添加在表尾添加
45、)linklistcreat_linklist()linklistL=null;Lnode*s,*r=null;intx;scanf(“%d”,&x)；while(x!=-1)s=malloc(sizeof(LNode)；s-data=x;if(L=null)L=s；elser-next=s；r=s；scanf(%d”,&x)；if(r!=nullr-next=null)；returnL;x=-1x=-11818r rL L29297676r rr r4545s sr rnullnull创立单链表创立单链表(在表尾添加在表尾添加在表尾添加在表尾添加)int length_linklist(li
46、nklist L)int length_linklist(linklist L)LNode*p=L;/*pLNode*p=L;/*p指向指向首节点首节点L*/Int j=0;Int j=0;while(p-next)/while(p-next)/当当P P指向指向an时时,p-next,p-next为空为空,结束结束 p=p-nextp=p-next;/*/*第一次第一次循环循环P P为为首首节点的指针域里的值节点的指针域里的值,即即指向指向节点节点a1*/j+;/*j+;/*表长计算从首节点表长计算从首节点a1开始到开始到an.*/return(j);return(j);a1a2ana3.P
47、PP PnP Pn-next-next2.2.2.2.求单链表的表长求单链表的表长求单链表的表长求单链表的表长(带首结点带首结点带首结点带首结点)L LPPPPint length_linklist(linklist L)int length_linklist(linklist L)LNode*p=L;/*pLNode*p=L;/*p指向指向节点节点a1*/int j;int j;if(p=NULL)return 0;/*if(p=NULL)return 0;/*空表时空表时*/*/j=1j=1while(p-next!=NULL)/while(p-next!=NULL)/当当P P指向指向a
48、n时时,p-next,p-next为空为空,结束结束 p=p-nextp=p-next;j+;/*;j+;/*表长计算从节点表长计算从节点a1开始到开始到an.*/return(j);return(j);L LPPP Pn-next-next2.2.2.2.求单链表的表长求单链表的表长求单链表的表长求单链表的表长(不带首结点不带首结点不带首结点不带首结点)a1a2ana3.PPPP查找方法查找方法:从头指针开始从头指针开始,修改指针修改指针p=p-next,p=p-next,使顺链表顺序往使顺链表顺序往下搜索下搜索,直到找到为止直到找到为止.查找次数为查找次数为i i次次.L L.a2a1aa
49、iP PLNode Get_linklist(linklist L,int i)LNode Get_linklist(linklist L,int i)LNode LNode*p=L;j=0*p=L;j=0;while(p-next!=NULL)&(jnext!=NULL)&(jnext为空或P已指向节点i时结束 p=p-next;p=p-next;/第一次循环P指向首节点a1 j+;j+;/表长计算从首节点a1开始到an.if(i=j)return(p);if(i=j)return(p);else return(Null);else return(Null);3.3.按序号查找按序号查找(找
50、表中第找表中第i i个结点个结点,返回该节点序号或指针返回该节点序号或指针)P1P1P2P2PiPiLNode locate_linklist(linklist L,datatype x)LNode locate_linklist(linklist L,datatype x)LNodeLNode p=Lp=L-next;-next;while(p!=Null)&(p-data!=x)while(p!=Null)&(p-data!=x)p=p-next;p=p-next;if(p-data=x)return(p);if(p-data=x)return(p);else return(0);else