《C程序设计C程序设计 (88).pdf》由会员分享，可在线阅读，更多相关《C程序设计C程序设计 (88).pdf（37页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、C C程序设计程序设计Programming in CProgramming in C用链表表示动态用链表表示动态“数组数组”1、链表的基本概念2、创建链表C C程序设计程序设计程序设计程序设计3 3第第9 9章章 链表链表使用数组时必须事先定义好数组长度（即元素个数），这个长度一经定义就是固定不变的。如果事先难以确定元素个数，则必须把数组长度定义得足够大，这将占用许多内存。另一方面，在数组中若要插入或删除某个元素，需要移动插入点或删除点后面所有的数组元素，这将运行大量时间。4 4第第9 9章章 链表链表链表是一种存储空间能动态进行增长或缩小的数据结构。链表主要用于两个目的：一是建立不定长度的
2、数组。二是链表可以在不重新安排整个存储结构的情况下，方便且迅速地插入和删除数据元素。由于这些原因，链表广泛地运用于数据管理中。5 59.1 9.1 链表概述链表概述首先设计一种称为结点（node）的数据类型：typedef structtypedef struct tagNODEtagNODE /结点数据类型/结点数据类型ElemType dataElemType data;/数据域/数据域structstruct tagNODEtagNODE*linklink;/指针域/指针域 NODENODE;6 69.1.1 9.1.1 链表的概念链表的概念这个结构体类型中，data成员表示数据域，代表
3、结点的数据信息。ElemType可以是简单的内置数据类型，也可以是复杂的数据类型，如typedef structtypedef struct tagElemTypetagElemType /复杂的数据元素类型/复杂的数据元素类型./任意数目、任意组合、任意类型的数据成员/任意数目、任意组合、任意类型的数据成员 ElemTypeElemType;7 79.1.1 9.1.1 链表的概念链表的概念数据域是链表中的信息对象（元素），实际应用中结合具体要求设计其数据类型。为方便介绍，这里将ElemType简单设定为int型，即typedef inttypedef int ElemTypeElemTyp
4、e;/简单的数据元素类型/简单的数据元素类型8 89.1.1 9.1.1 链表的概念链表的概念link成员表示指针域，存放另一个结点的地址，是链表中的组织者。假定有一个NODE类型的对象指针L，将一个新结点的地址赋给L的link成员，则L可以通过它的link成员“链接”到新结点上，重复这个过程可以得到如图的链表结构。9 99.1.1 9.1.1 链表的概念链表的概念可以看出，链表是一种物理存储非连续（非顺序）的存储结构，数据元素的逻辑顺序是通过链表中的指针域实现的。链表由一系列结点组成，结点可以在运行时动态生成，因而链表可以动态增长或缩短。同时，结点是按指针域连接起来的，插入或删除结点非常简便
5、和迅速。通常，链表包含创建、遍历、插入、删除等运算。10109.1.2 9.1.2 单链表与双链表单链表与双链表1单链表单链表每个结点包含一个指向直接后继结点的指针域，其形式为：typedef structtypedef struct tagLNodetagLNode /单链表结点类型/单链表结点类型ElemType dataElemType data;/数据域/数据域structstruct tagLNodetagLNode*nextnext;/指针域：指向直接后继结点/指针域：指向直接后继结点 LNodeLNode,*,*LinkListLinkList;/LNode为单链表结构体类型，L
6、inkList为单链表指针类型/LNode为单链表结构体类型，LinkList为单链表指针类型11119.1.2 9.1.2 单链表与双链表单链表与双链表next指向直接后继结点，由它构成了一条链。12129.1.2 9.1.2 单链表与双链表单链表与双链表指针L指向单链表头结点，头结点指向开始结点，开始结点又指向下一个结点，直到最后一个尾结点。尾结点的next为0，表示NULL指针，约定单链表的结点的next为0时表示尾结点。上述链表称为带头结点的单链表，若开始结点为头结点，则称这样的链表为不带头结点的单链表。13139.1.2 9.1.2 单链表与双链表单链表与双链表2双链表双链表每个结点
7、包含指向前驱结点和指向直接后继结点的指针域，其形式为：typedef structtypedef struct tagDNodetagDNode /双链表结点类型/双链表结点类型ElemType dataElemType data;/数据域/数据域structstruct tagDNodetagDNode*prevprev,*,*nextnext;/指针域：分别指向前驱结点和直接后继结点/指针域：分别指向前驱结点和直接后继结点 DNodeDNode,*,*DLinkListDLinkList;/DNode为双链表结构体类型，DLinkList为双链表指针类型/DNode为双链表结构体类型，DL
8、inkList为双链表指针类型14149.1.2 9.1.2 单链表与双链表单链表与双链表next指向直接后继结点，prev指向前驱结点，由它们构成了两条链。15159.1.2 9.1.2 单链表与双链表单链表与双链表指针L指向双链表头结点，其每个结点分别有指向前一个结点和后一个结点的指针。沿着next指针，头结点指向开始结点，开始结点又指向下一个结点，直到尾结点，尾结点的next为0。沿着prev指针，尾结点指向前一个结点，直到头结点head，头结点的prev为0。约定双链表的结点的next为0时表示尾结点，prev为0时表示头结点。双链表也有带头结点和不带头结点之分。16169.1.2 9
9、.1.2 单链表与双链表单链表与双链表与单链表相比，双链表可以从前向链和后向链遍历整个链表，这样简化了链表排序方法及运算。同时，当一个链数据受损（如数据库设备故障）时可以根据另一个链来恢复它。17179.1.2 9.1.2 单链表与双链表单链表与双链表图9.4 循环单链表和循环双链表3循环链表若单链表尾结点指向头结点而不是0，则该链表是循环单链表。18189.1.2 9.1.2 单链表与双链表单链表与双链表图9.4 循环单链表和循环双链表若双链表尾结点next指向头结点而不是0，头结点prev指向尾结点而不是0，则该链表是循环双链表。19199.2 9.2 链表的创建链表的创建在程序中欲要使用
10、链表，需要创建链表。20209.2.1 9.2.1 创建单链表创建单链表通过前面的内存动态分配技术可以产生新结点的内存单元，例如：LinkList pLinkList p;/链表指针/链表指针p p=(=(LinkListLinkList)mallocmalloc(sizeofsizeof(LNodeLNode););/分配LNode类型内存单元且将地址保存到p中/分配LNode类型内存单元且将地址保存到p中21219.2.1 9.2.1 创建单链表创建单链表调用malloc、realloc内存分配函数或free释放函数时，在程序中需要文件包含命令：#include#include 22229
11、.2.1 9.2.1 创建单链表创建单链表创建链表常用两种方法：头插法和尾插法。23239.2.1 9.2.1 创建单链表创建单链表（1）头插法建立链表CreateLinkF(&L,n,input()该方法先建立一个头结点*L，然后产生新结点，设置新结点的数据域；再将新结点插入到当前链表的表头，直至指定数目的元素都增加到链表中为止。其步骤为：创建头结点*L，设置*L的next为0。动态分配一个结点s，输入s的数据域。将s插入到开始结点之前，头结点之后，即s-next=p-next，p-next=s。重复步骤加入更多结点。24249.2.1 9.2.1 创建单链表创建单链表采用头插法创建单链表的
12、算法如下：1 voidvoid CreateLinkFCreateLinkF(LinkListLinkList*L L,intint n n,voidvoid(*(*inputinput)()(ElemTypeElemType*)*)2 /头插法创建单链表，调用input输入函数输入数据/头插法创建单链表，调用input输入函数输入数据3 LinkList sLinkList s;4*L L=(=(LinkListLinkList)mallocmalloc(sizeofsizeof(LNodeLNode););/创建头结点/创建头结点5(*(*L L)-)-nextnext=NULLNULL;
13、/初始时为空表/初始时为空表6 forfor(;(;n n 0 0;n n-)-)/创建n个结点链表/创建n个结点链表7 s s=(=(LinkListLinkList)mallocmalloc(sizeofsizeof(LNodeLNode););/创建新结点/创建新结点8 inputinput(&(&s s-datadata););/调用input输入数据域/调用input输入数据域9 s s-nextnext=(*=(*L L)-)-nextnext;/将s增加到开始结点之前/将s增加到开始结点之前10(*(*L L)-)-nextnext=s s;/头结点之后/头结点之后11 12 2
14、5259.2.1 9.2.1 创建单链表创建单链表参数L表示将要创建出来的单链表指针，之所以是LinkList类型的指针类型（即指针的指针），其原因是需要将链表返回到调用函数中。n表示创建链表时需要输入的元素数目，由实际应用中的具体要求确定。26269.2.1 9.2.1 创建单链表创建单链表考虑到数据域可能是复杂的数据类型，输入不止是一个简单的scanf。因此设计input函数指针，CreateLinkF调用它实现定制的数据域输入。例如voidvoid inputinput(ElemTypeElemType*epep)/实现数据域元素输入的定制函数/实现数据域元素输入的定制函数/在函数中可以
15、写更加复杂、任意形式、任意数目的输入/在函数中可以写更加复杂、任意形式、任意数目的输入scanfscanf(%d,(%d,epep););27279.2.1 9.2.1 创建单链表创建单链表运行时若输入5个元素：1、2、3、4、5，则调用建立的单链表如图所示。LinkList LLinkList L;CreateLinkFCreateLinkF(&(&L L,5 5,inputinput););/创建单链表L/创建单链表L28289.2.1 9.2.1 创建单链表创建单链表（2）尾插法建立链表CreateLinkR(&L,n,input()头插法建立的链表中结点的次序与元素输入的顺序相反，若希
16、望两者次序一致，可采用尾插法建立链表。该方法是将新结点插到当前链表的末尾上，其步骤为：创建头结点*L，设置*L的next为0，且令指针p指向*L。动态分配一个结点s，输入s的数据域。将s插入到当前链表末尾，即p-next=s，p=s。重复步骤加入更多结点。29299.2.1 9.2.1 创建单链表创建单链表采用尾插法创建单链表的算法如下：1 voidvoid CreateLinkRCreateLinkR(LinkListLinkList*L L,intint n n,voidvoid(*(*inputinput)()(ElemTypeElemType*)*)2 /尾插法创建单链表，调用inpu
17、t输入函数输入数据/尾插法创建单链表，调用input输入函数输入数据3 LinkList pLinkList p,s s;4 p p=*=*L L=(=(LinkListLinkList)mallocmalloc(sizeofsizeof(LNodeLNode););/创建头结点/创建头结点5 forfor(;(;n n 0 0;n n-)-)/创建n个结点链表/创建n个结点链表6 s s=(=(LinkListLinkList)mallocmalloc(sizeofsizeof(LNodeLNode););/创建新结点/创建新结点7 inputinput(&(&s s-datadata);)
18、;/调用input输入数据域/调用input输入数据域8 p p-nextnext=s s,p p=s s;/将s插入到当前链表末尾/将s插入到当前链表末尾9 10 p p-nextnext=NULLNULL;/尾结点/尾结点11 30309.2.1 9.2.1 创建单链表创建单链表运行时若输入5个元素：1、2、3、4、5，则调用CreateLinkR(&L,5,input)建立的单链表如图所示。31319.2.1 9.2.1 创建单链表创建单链表（3）初始化链表InitList(&L)构造一个空链表（即没有数据结点）的算法如下：1 voidvoid InitListInitList(Link
19、ListLinkList*L L)/构造一个空的单链表L/构造一个空的单链表L2 3*L L=(=(LinkListLinkList)mallocmalloc(sizeofsizeof(LNodeLNode););/创建头结点，*L指向头结点/创建头结点，*L指向头结点4(*(*L L)-)-nextnext=NULLNULL;/初始时为空表/初始时为空表5 32329.2.1 9.2.1 创建单链表创建单链表（4）判断链表是否为空表ListEmpty(L)检测一个链表是否为空表的算法如下：1 intint ListEmptyListEmpty(LinkList LLinkList L)/检测
20、L是否为空表/检测L是否为空表2 /若L为空表返回TRUE，否则返回FALSE/若L为空表返回TRUE，否则返回FALSE3 returnreturn L L-nextnext=NULLNULL;4 33339.2.2 9.2.2 创建双链表创建双链表双链表每个结点有两个指针域，next指向直接后继结点，prev指向前驱结点。建立双链表的过程与单链表相似，只是需要再处理prev指针，建立前向链即可。34349.2.2 9.2.2 创建双链表创建双链表采用头插法创建双链表的算法如下：1 voidvoid CreateLinkFCreateLinkF(DLinkListDLinkList*L L,
21、intint n n,voidvoid(*(*inputinput)()(ElemTypeElemType*)*)2 /头插法创建双链表，调用input输入函数输入数据/头插法创建双链表，调用input输入函数输入数据3 DLinkList sDLinkList s;4*L L=(=(DLinkListDLinkList)mallocmalloc(sizeofsizeof(DNodeDNode););/创建头结点/创建头结点5(*(*L L)-)-prevprev=(*=(*L L)-)-nextnext=NULLNULL;/初始时为空表/初始时为空表6 forfor(;(;n n 0 0;n
22、 n-)-)/创建n个结点链表/创建n个结点链表7 s s=(=(DLinkListDLinkList)mallocmalloc(sizeofsizeof(DNodeDNode););/创建新结点/创建新结点8 inputinput(&(&s s-datadata););/调用input输入数据域/调用input输入数据域9 s s-nextnext=(*=(*L L)-)-nextnext;/将s增加到开始结点之前/将s增加到开始结点之前10 ifif(*(*L L)-)-nextnext!=!=NULLNULL)(*)(*L L)-)-nextnext-prevprev=s s;/开始结点
23、之前是s/开始结点之前是s11(*(*L L)-)-nextnext=s s,s s-prevprev=*=*L L;/头结点之后是s，s之前是头结点/头结点之后是s，s之前是头结点12 13 35359.2.2 9.2.2 创建双链表创建双链表采用尾插法创建双链表的算法如下：1 voidvoid CreateLinkRCreateLinkR(DLinkListDLinkList*L L,intint n n,voidvoid(*(*inputinput)()(ElemTypeElemType*)*)2 /尾插法创建双链表，调用input输入函数输入数据/尾插法创建双链表，调用input输入函
24、数输入数据3 DLinkList pDLinkList p,s s;4 p p=*=*L L=(=(DLinkListDLinkList)mallocmalloc(sizeofsizeof(DNodeDNode););/创建头结点/创建头结点5(*(*L L)-)-prevprev=(*=(*L L)-)-nextnext=NULLNULL;/初始时为空表/初始时为空表6 forfor(;(;n n 0 0;n n-)-)/创建n个结点链表/创建n个结点链表7 s s=(=(DLinkListDLinkList)mallocmalloc(sizeofsizeof(DNodeDNode););/
25、创建新结点/创建新结点8 inputinput(&(&s s-datadata););/调用input输入数据域/调用input输入数据域9 s s-nextnext=NULLNULL;/当前结点是尾结点/当前结点是尾结点10 p p-nextnext=s s,s s-prevprev=p p,p p=s s;/将s增加到链尾/将s增加到链尾11 12 36369.2.2 9.2.2 创建双链表创建双链表构造一个空的双链表（即没有数据结点）的算法如下：1 voidvoid InitListInitList(DLinkListDLinkList*L L)/构造一个空的单链表L/构造一个空的单链表L2 3*L L=(=(DLinkListDLinkList)mallocmalloc(sizeofsizeof(DNodeDNode););/创建头结点，*L指向头结点/创建头结点，*L指向头结点4(*(*L L)-)-prevprev=(*=(*L L)-)-nextnext=NULLNULL;/初始时为空表/初始时为空表5 结束结束