c程序设计第九章ppt西工大

《c程序设计第九章ppt西工大》由会员分享，可在线阅读，更多相关《c程序设计第九章ppt西工大（86页珍藏版）》请在金锄头文库上搜索。

1、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

2、 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); r

3、eturn 0; ,7,第9章 链表,9.1 链表概述 9.2 链表的创建 9.3 链表的运算 9.4 结点的插入与删除,8,本知识点在本课程知识体系中地位,链表是一种常见的重要的数据结构，它是动态的进行内存存储分配的一种结构，存储空间能动态进行增长或缩小的数据结构。 链表主要用于两个目的：一是建立不定长度的数组。二是链表可以在不重新安排整个存储结构的情况下，方便且迅速地插入和删除数据元素。,9,例如：建立一个学生管理程序，要求实现学生的数据动态录入、查询和删除,链表概述,插入新数据,删除,问题特点：事先不确定学生人数，如果采用事先确定长度的存储结构，将会带来存储空间的浪费,必须用动态存储结构

4、存放数据,10,程序中存放大量数据：链表和数组 数组存放数据：必须事先定义固定的长度（即元素个数 数组存放数据：物理存储单元要求在内存中分配连续存储空间 链表存放数据：可以根据需要，动态开辟内存单元。 链表存放数据：物理存储单元非连续，非顺序的存储结构,11,链表：是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。,节点,节点：数据+指针,数据:存放数据存储单元,指针：指示后继元素存储位置,12,9.1.1 链表的概念,一种称为结点（node）的数据类型： 这个结构体类型中，data成员表示数据域，代表结点的数据信息。,typedef struc

5、t tagNODE /结点数据类型 ElemType data; /数据域 struct tagNODE *link; /指针域 NODE;,例如：节点的构成 上图每个节点具有如下结构体类型： struct tagSTU long num; float score; structer tagSTU *next; ; /链节成员 其中： 成员num、score用于存放一个节点的具体数据； 成员next是指针类型，用于存放下一节点指针， 最后一个节点的next 成员存放空指针NULL； 成员next是指向与自身同一类型的结构，这种结 构称为自引用结构。(只有指针成员可自引用) 动态链表的节点是在运

6、行时动态生成的。,动态内存分配和释放 建立和维护动态数据结构需要实现动态内存 分配；如在链表中插入节点需要先申请一段存储 区域，而删除一个节点需要释放该节点原先占用 的存储区域，这可由标准函数实现。 内存分配函数原形： void *malloc(unsigned size); 功能：申请长度为size个字节的内存空间；若申请 成功，返回存储块起始指针，该指针类型为 void *；否则返回空指针(NULL)。 内存释放函数原形：void free(void *p); 功能：释放p所指向的内存块。 包含文件：malloc.h、stdlib.h中均有其原型声明。,链表的类型 单链表：每个节点只有一个

7、指向后继节点的指针 双向链表：每个节点有两个用于指向其它节点的指针；一个指向前趋节点，一个指向后继节点 循环链表：使最后一个节点的指针指向头节点 链表构造方式 用多个结构体变量可构成静态链表 将动态申请空间而建立的节点链接动态链表,采用动态链表的意义 与定长数据结构数组相比，链表能更好地利用内存，按需分配和释放存储空间。 在链表中插入或删除一个节点，只需改变某节点“链节”成员的指向，而不需要移动其它节点，相对数组元素的插入和删除效率高。 即：链表特别适合于对大线性表频繁插入和删除元素、或数据域成员数目不定的数据结构。,17,链表类型-单向链表：包含两个域，一个信息域和一个指针域。这个链接指向列

8、表中的下一个节点，而最后一个节点则指向一个空值,18,链表类型-双向链表：,每个节点有两个指针域：一个指向前一个节点；而另一个指向下一个节点,19,链表类型循环链表：首节点和末节点被连接在一起,用单链表实现双向链表,20,9.1.1 链表的概念,可以看出，链表是一种物理存储非连续（非顺序）的存储结构，数据元素的逻辑顺序是通过链表中的指针域实现的。 链表由一系列结点组成，结点可以在运行时动态生成，因而链表可以动态增长或缩短。同时，结点是按指针域连接起来的，插入或删除结点非常简便和迅速。 通常，链表包含创建、遍历、插入、删除等运算。,21,9.1.2 单链表与双链表,1单链表 单链表每个结点包含一

9、个指向直接后继结点的指针域，其形式为： 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时表示尾结点。上

10、述链表称为带头结点的单链表，若开始结点为头结点，则称这样的链表为不带头结点的单链表。,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指向双链表头结点，其每个结

11、点分别有指向前一个结点和后一个结点的指针。沿着next指针，头结点指向开始结点，开始结点又指向下一个结点，直到尾结点，尾结点的next为0。沿着prev指针，尾结点指向前一个结点，直到头结点head，头结点的prev为0。约定双链表的结点的next为0时表示尾结点，prev为0时表示头结点。双链表也有带头结点和不带头结点之分。,25,9.1.2 单链表与双链表,与单链表相比，双链表可以从前向链和后向链遍历整个链表，这样简化了链表排序方法及运算。同时，当一个链数据受损（如数据库设备故障）时可以根据另一个链来恢复它。,26,9.1.2 单链表与双链表,3循环链表 若单链表尾结点指向头结点而不是0，

12、则该链表是循环单链表。 同理，若双链表尾结点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.

13、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,

14、 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

15、*),参数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