资源预览内容
第1页 / 共86页
第2页 / 共86页
第3页 / 共86页
第4页 / 共86页
第5页 / 共86页
第6页 / 共86页
第7页 / 共86页
第8页 / 共86页
第9页 / 共86页
第10页 / 共86页
亲,该文档总共86页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
1,第9章 链表,快速排序法 A1 AN,2,关键数据,一趟快速排序:将所有比关键数据小的数据放在它左边,所有比关键数据大的数据放在它右边,i=1,j=N,3,34 56 78 12 33 7 19,i,j,1)利用j从后向前扫描,找到第一个比关键数据小的数,交换,19 56 78 12 33 7 34,i,j,2)利用i从前向后扫描,找到第一个比关键数据大的数,交换,19 34 78 12 33 7 56,i,j,3)重复(1)即利用j从后向前扫描,找到第一个比关键数据小的数,交换,19 7 78 12 33 34 56,4,19 7 78 12 33 34 56,19 7 34 12 33 78 56,19 7 33 12 34 78 56,条件 ij不满足了,一趟排序结束,19 7 33 12 34 78 56,递归,递归,5,void quicksort(int a,int left,int right) int i,j,temp; i=left; j=right; temp=aleft; if(left=right) return; while(i=temp ,6,int main() int a7=17,2,6,12,1,9,5; int i; quicksort(a,0,6); /*排好序的结果*/ for(i=0;i7;i+) printf(“%4d“,ai); return 0; ,7,第9章 链表,9.1 链表概述 9.2 链表的创建 9.3 链表的运算 9.4 结点的插入与删除,8,本知识点在本课程知识体系中地位,链表是一种常见的重要的数据结构,它是动态的进行内存存储分配的一种结构,存储空间能动态进行增长或缩小的数据结构。 链表主要用于两个目的:一是建立不定长度的数组。二是链表可以在不重新安排整个存储结构的情况下,方便且迅速地插入和删除数据元素。,9,例如:建立一个学生管理程序,要求实现学生的数据动态录入、查询和删除,链表概述,插入新数据,删除,问题特点:事先不确定学生人数,如果采用事先确定长度的存储结构,将会带来存储空间的浪费,必须用动态存储结构存放数据,10,程序中存放大量数据:链表和数组 数组存放数据:必须事先定义固定的长度(即元素个数 数组存放数据:物理存储单元要求在内存中分配连续存储空间 链表存放数据:可以根据需要,动态开辟内存单元。 链表存放数据:物理存储单元非连续,非顺序的存储结构,11,链表:是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。,节点,节点:数据+指针,数据:存放数据存储单元,指针:指示后继元素存储位置,12,9.1.1 链表的概念,一种称为结点(node)的数据类型: 这个结构体类型中,data成员表示数据域,代表结点的数据信息。,typedef struct tagNODE /结点数据类型 ElemType data; /数据域 struct tagNODE *link; /指针域 NODE;,例如:节点的构成 上图每个节点具有如下结构体类型: struct tagSTU long num; float score; structer tagSTU *next; ; /链节成员 其中: 成员num、score用于存放一个节点的具体数据; 成员next是指针类型,用于存放下一节点指针, 最后一个节点的next 成员存放空指针NULL; 成员next是指向与自身同一类型的结构,这种结 构称为自引用结构。(只有指针成员可自引用) 动态链表的节点是在运行时动态生成的。,动态内存分配和释放 建立和维护动态数据结构需要实现动态内存 分配;如在链表中插入节点需要先申请一段存储 区域,而删除一个节点需要释放该节点原先占用 的存储区域,这可由标准函数实现。 内存分配函数原形: void *malloc(unsigned size); 功能:申请长度为size个字节的内存空间;若申请 成功,返回存储块起始指针,该指针类型为 void *;否则返回空指针(NULL)。 内存释放函数原形:void free(void *p); 功能:释放p所指向的内存块。 包含文件:malloc.h、stdlib.h中均有其原型声明。,链表的类型 单链表:每个节点只有一个指向后继节点的指针 双向链表:每个节点有两个用于指向其它节点的指针;一个指向前趋节点,一个指向后继节点 循环链表:使最后一个节点的指针指向头节点 链表构造方式 用多个结构体变量可构成静态链表 将动态申请空间而建立的节点链接动态链表,采用动态链表的意义 与定长数据结构数组相比,链表能更好地利用内存,按需分配和释放存储空间。 在链表中插入或删除一个节点,只需改变某节点“链节”成员的指向,而不需要移动其它节点,相对数组元素的插入和删除效率高。 即:链表特别适合于对大线性表频繁插入和删除元素、或数据域成员数目不定的数据结构。,17,链表类型-单向链表:包含两个域,一个信息域和一个指针域。这个链接指向列表中的下一个节点,而最后一个节点则指向一个空值,18,链表类型-双向链表:,每个节点有两个指针域:一个指向前一个节点;而另一个指向下一个节点,19,链表类型循环链表:首节点和末节点被连接在一起,用单链表实现双向链表,20,9.1.1 链表的概念,可以看出,链表是一种物理存储非连续(非顺序)的存储结构,数据元素的逻辑顺序是通过链表中的指针域实现的。 链表由一系列结点组成,结点可以在运行时动态生成,因而链表可以动态增长或缩短。同时,结点是按指针域连接起来的,插入或删除结点非常简便和迅速。 通常,链表包含创建、遍历、插入、删除等运算。,21,9.1.2 单链表与双链表,1单链表 单链表每个结点包含一个指向直接后继结点的指针域,其形式为: next指向直接后继结点,由它构成了一条链。,typedef struct tagLNode /单链表结点类型 ElemType data; /数据域 struct tagLNode *next; /指针域:指向直接后继结点 LNode, *LinkList; /LNode为单链表结构体类型,LinkList为单链表指针类型,22,9.1.2 单链表与双链表,图9.2 单链表结构,指针L指向单链表头结点,头结点指向开始结点,开始结点又指向下一个结点,直到最后一个尾结点。尾结点的next为0,表示NULL指针,约定单链表的结点的next为0时表示尾结点。上述链表称为带头结点的单链表,若开始结点为头结点,则称这样的链表为不带头结点的单链表。,23,9.1.2 单链表与双链表,2双链表 双链表每个结点包含指向前驱结点和指向直接后继结点的指针域,其形式为:,typedef struct tagDNode /双链表结点类型 ElemType data; /数据域 struct tagDNode *prev,*next; /指针域:分别指向前驱结点和直接后继结点 DNode, *DLinkList; /DNode为双链表结构体类型,DLinkList为双链表指针类型,24,9.1.2 单链表与双链表,图9.3 双链表结构,指针L指向双链表头结点,其每个结点分别有指向前一个结点和后一个结点的指针。沿着next指针,头结点指向开始结点,开始结点又指向下一个结点,直到尾结点,尾结点的next为0。沿着prev指针,尾结点指向前一个结点,直到头结点head,头结点的prev为0。约定双链表的结点的next为0时表示尾结点,prev为0时表示头结点。双链表也有带头结点和不带头结点之分。,25,9.1.2 单链表与双链表,与单链表相比,双链表可以从前向链和后向链遍历整个链表,这样简化了链表排序方法及运算。同时,当一个链数据受损(如数据库设备故障)时可以根据另一个链来恢复它。,26,9.1.2 单链表与双链表,3循环链表 若单链表尾结点指向头结点而不是0,则该链表是循环单链表。 同理,若双链表尾结点next指向头结点而不是0,头结点prev指向尾结点而不是0,则该链表是循环双链表。,27,9.1.2 单链表与双链表,图9.4 循环单链表和循环双链表,28,9.2 链表的创建,29,9.2.1 创建单链表,通过第7章介绍的内存动态分配技术可以产生新结点的内存单元,例如: 调用malloc、realloc内存分配函数或free释放函数时,在程序中需要文件包含命令:,LinkList p; /链表指针 p=(LinkList)malloc(sizeof(LNode); /分配LNode类型内存单元且将地址保存到p中,#include ,30,9.2.1 创建单链表,创建链表常用两种方法:头插法和尾插法。 (1)头插法建立链表CreateLinkF(&L,n,input() 该方法先建立一个头结点*L,然后产生新结点,设置新结点的数据域;再将新结点插入到当前链表的表头,直至指定数目的元素都增加到链表中为止。其步骤为: 创建头结点*L,设置*L的next为0。 动态分配一个结点s,输入s的数据域。 将s插入到开始结点之前,头结点之后,即s-next=p-next,p-next=s。 重复步骤加入更多结点。,31,9.2.1 创建单链表,采用头插法创建单链表的算法如下:,1 void CreateLinkF(LinkList *L,int n, void(*input)(ElemType*) 2 /头插法创建单链表,调用input输入函数输入数据 3 LinkList s; 4 *L=(LinkList)malloc(sizeof(LNode); 5 (*L)-next=NULL; /初始时为空表 6 for (; n0; n-) /创建n个结点链表 7 s=(LinkList)malloc(sizeof(LNode); 8 input( /头结点之后 11 12 ,指向头节点的头指针,32,9.2.1 创建单链表,1 void CreateLinkF(LinkList *L,int n, void(*input)(ElemType*),参数L表示将要创建出来的单链表指针,之所以是LinkList类型的指针类型(即指针的指针),其原因是需要将链表返回到调用函数中。n表示创建链表时需要输入的元素数目,由实际应用中的具体要求确定。,33,9.2.1 创建单链表,图9.5 头插法建立的单链表L,运行时若输入5个元素:1、2、3、4、5,则调用 建立的单链表如图所示。,LinkList L; CreateLinkF( /创建单链表L,34,9.2.1 创建单链表,(2)尾插法建立链表CreateLinkR(&L,n,input() 头插法建立的链表中结点的次序与元素输入的顺序相反,若希望两者次序一致,可采用尾插法建立链表。该方法是将新结点插到当前链表的末尾上,,35,9.2.1 创建单链表,采用尾插法创建单链表的算法如下:,1 void CreateLinkR(LinkList *L,int n, void(*input)(ElemType*) 2 /尾插法创建单链表,调用input输入函数输入数据 3 LinkList p,s; 4 p=*L=(LinkList)malloc(sizeof(LNode); 5 for (; n0; n-) /创建n个结点链表 6 s=(LinkList)malloc(sizeof(LNode); 7 input( /尾结点 11
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号