动态数据结构 (2)精选PPT.ppt

《动态数据结构 (2)精选PPT.ppt》由会员分享，可在线阅读，更多相关《动态数据结构 (2)精选PPT.ppt（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、动态数据结构第1页，此课件共24页哦 123 .n 如图的链式结构可以满足要求如图的链式结构可以满足要求:当增加一张卡片时，只需要向计算机系统申请一块空间，联到链的适当位置上。例如，当增加一张卡片时，只需要向计算机系统申请一块空间，联到链的适当位置上。例如，要增加一张卡片要增加一张卡片 50 插入到插入到 2、3 之间，则只需要如下修改指针：之间，则只需要如下修改指针：若删除一节，只需要将其从链上摘下来即可。例删除若删除一节，只需要将其从链上摘下来即可。例删除2节得节得:链上已经没有链上已经没有2节了，删掉的节所占的存储空间还可以还回计算机系统，以便作节了，删掉的节所占的存储空间还可以还回计算

2、机系统，以便作其它用途。其它用途。50第2页，此课件共24页哦 这就是一种动态数据结构中的这就是一种动态数据结构中的链表。动态数据结构上的一项是一个动链表。动态数据结构上的一项是一个动态变量，指针是标识动态变量的有力手段。动态变量与静态变量的区别在于态变量，指针是标识动态变量的有力手段。动态变量与静态变量的区别在于:o静态变量是程序中由程序员静态变量是程序中由程序员“显式显式”说明的变量。它有一个名字，在说明的变量。它有一个名字，在编译时，编译程序已经给它分配存储空间。这块存储空间用变量的名编译时，编译程序已经给它分配存储空间。这块存储空间用变量的名字来标识。字来标识。o动态变量在程序中没有动

3、态变量在程序中没有“显式显式”说明，它没有名字，在编译时编译说明，它没有名字，在编译时编译程序不知道有该变量，不给（也不可能给）它分配空间。动态变量程序不知道有该变量，不给（也不可能给）它分配空间。动态变量是在程序运行时，随程序存储数据的需要，由申请空间函数（例如是在程序运行时，随程序存储数据的需要，由申请空间函数（例如malloc，当然也是由程序员安排的）随机的动态的申请来的空间。，当然也是由程序员安排的）随机的动态的申请来的空间。它没有名字，一般动态变量都由指针标识。当使用完毕后，由释放它没有名字，一般动态变量都由指针标识。当使用完毕后，由释放空间函数（例如空间函数（例如free）释放，还

4、回计算机存储管理系统，以备它用。）释放，还回计算机存储管理系统，以备它用。第3页，此课件共24页哦sizeof 运算符运算符:单目运算符单目运算符 sizeof 的的o操作数操作数是类型。是类型。o运算结果运算结果是求得相应类型的尺寸，即存储相应类型数据所需要的字节是求得相应类型的尺寸，即存储相应类型数据所需要的字节数。数。例：例：sizeof(int)/*结果是结果是2*/sizeof(char)/*结果是结果是1*/sizeof(struct date)/*若若 struct date 是第十一章定义的日期类型，结果是是第十一章定义的日期类型，结果是6*/第4页，此课件共24页哦mallo

5、c 函数函数:原型是：原型是：void*malloc(unsigned long size);功能是：功能是：申请足够大内存区域用来存储长度为申请足够大内存区域用来存储长度为size的数据对象，返回该区域的首指的数据对象，返回该区域的首指针。针。返回指针是返回指针是void类型的，调用者必须使用显示强制类型转换，把该指针转类型的，调用者必须使用显示强制类型转换，把该指针转换成所需要类型的指针。换成所需要类型的指针。#include 例例:float*p;p=(float*)malloc(sizeof(float);第5页，此课件共24页哦free函数函数 动态申请的内存如果不再使用，应当适时释

6、放。这样可以提高程序运行效率。动态申请的内存如果不再使用，应当适时释放。这样可以提高程序运行效率。free函函数用来释放经过数用来释放经过malloc申请的动态空间。申请的动态空间。free的函数原型是的函数原型是 void free(void*ptr);free函数的功能是：释放由函数的功能是：释放由malloc申请的内存区域。申请的内存区域。free的参数的参数ptr是一个指是一个指针，指向以前由针，指向以前由malloc申请的一个内存区域。例申请的一个内存区域。例 free(p)/*释放释放p所指向的，前边由所指向的，前边由malloc申请的内存空间申请的内存空间*/一块存储区域一经释放

7、，便不能再使用。一块存储区域一经释放，便不能再使用。第6页，此课件共24页哦实用问题实用问题:若指针变量指向的用若指针变量指向的用malloc申请来的动态变量，是狐立的不能与其它变量相联系，显然作申请来的动态变量，是狐立的不能与其它变量相联系，显然作用不大。引进动态变量的目的是构造动态数据结构。例如象本章开始介绍的那样，构造一个链表用不大。引进动态变量的目的是构造动态数据结构。例如象本章开始介绍的那样，构造一个链表等。这就要求一个数据项上除基本的数据信息外，还应包含与其它数据项相联系的信息，也就是等。这就要求一个数据项上除基本的数据信息外，还应包含与其它数据项相联系的信息，也就是包含指针，呈左

8、图形式。该结构必须用结构体类型描述，链表上一个节点的类型定义形式如右图包含指针，呈左图形式。该结构必须用结构体类型描述，链表上一个节点的类型定义形式如右图所示。所示。类型定义形式类型定义形式 struct t 基本数据部分；基本数据部分；struct t *next;基本数据基本数据部分部分指针部分指针部分一个数据项一个数据项 第7页，此课件共24页哦o 静态建立链表,遍历链表o#define NULL 0o#include stdio.hostruct studentochar name20;/*说明学生的姓名*/oint number;/*说明学生的房间号*/ofloat score;/*

9、说明学生的分数*/ostruct student *link;/*指向下一个结点的指针*/o ;omain()ostruct student a,b,c,*head,*p;oscanf(%s,a.name);oa.number=1;a.score=90;oscanf(%s,b.name);ob.number=2;b.score=92;oscanf(%s,c.name);oc.number=3;c.score=89;ohead=&a;oa.link=&b;ob.link=&c;oc.link=NULL;op=head;第8页，此课件共24页哦odoo printf(%s%d%fn,p-name,

10、p-number,p-score);o p=p-link;o while(p!=NULL);o遍历结点：遍历结点：p=p-link;第9页，此课件共24页哦o 动态建立链表（尾动态建立链表（尾插入法建立链表）o/*建立一个5个结点的链表，存放学生数据（包括姓名、学号、成绩）。可编写一个建立链表的函数creat。程序如下：*/o#include o#include o#define LEN sizeof(struct stu)ostruct stu*create(int n);ostruct stuochar name20;/*说明学生的姓名*/oint number;/*说明学生的房间号*/o

11、int score;/*说明学生的分数*/ostruct stu *link;/*指向下一个结点的指针*/o;omain()oostruct stu*p;op=create(3);odo/*输出并检验量表建的是否正确*/o printf(%s%d%dn,p-name,p-number,p-score);o p=p-link;owhile(p!=NULL);o第10页，此课件共24页哦ostruct stu*create(int n)o struct stu*head,*pf,*pb;o int i=0;o for(i=0;iname,&pb-number,&pb-score);o if(i=0

12、)o pf=head=pb;o else pf-link=pb;o pb-link=NULL;o pf=pb;o oreturn head;第11页，此课件共24页哦o 动态建立链表（动态建立链表（头插入法建立链表）o/*建立一个5个结点的链表，存放学生数据（包括姓名、学号、成绩）。可编写一个建立链表的函数creat。程序如下：*/o#include o#include o#define LEN sizeof(struct stu)ostruct stu*create(int n);ostruct stuochar name20;/*说明学生的姓名*/oint number;/*说明学生的房间

13、号*/oint score;/*说明学生的分数*/ostruct stu *link;/*指向下一个结点的指针*/o;omain()oostruct stu*p;op=create(3);odo/*输出并检验量表建的是否正确*/o printf(%s%d%dn,p-name,p-number,p-score);o p=p-link;owhile(p!=NULL);o第12页，此课件共24页哦o/*前插法创建单链表前插法创建单链表*/ostruct stu*create(int n)ooint i;ostruct stu *p,*head;ohead=NULL;/*建立空头结点建立空头结点*/o

14、for(i=0;iname,&p-number,&p-score);o p-link=head;/*指向头节点指向头节点*/o head=p;/*更换头节点更换头节点*/ooreturn head;o第13页，此课件共24页哦创建单向链表创建单向链表:创建单向链表，是指用一项一项的数据逐步建立、形成一个链表。可以分成向链头加入创建单向链表，是指用一项一项的数据逐步建立、形成一个链表。可以分成向链头加入数据和向链尾加入数据两种方式。数据和向链尾加入数据两种方式。创建单向链表可以分成向链头加入数据和向链尾加入数据两种方式。新项加入链头就是创建单向链表可以分成向链头加入数据和向链尾加入数据两种方式。

15、新项加入链头就是压栈的算法；新项加入链尾就是队列中入队的算法。压栈的算法；新项加入链尾就是队列中入队的算法。遍历单向链表遍历单向链表:遍历是指从头到尾将链表上数据全部加工一遍。可用如下左端的算法。但实用中，经常用如下遍历是指从头到尾将链表上数据全部加工一遍。可用如下左端的算法。但实用中，经常用如下右端右端 的算法来遍历单向链表。的算法来遍历单向链表。p =head;p0=NULL;while(p!=NULL)p =head;加工加工 P-while(p!=NULL)p =p-next;加工加工 P-p0 =p;p =p-next;第14页，此课件共24页哦 在单向链表上检索在单向链表上检索:检

16、索是指在单向链表上查找关键字等于某给定值的节点检索是指在单向链表上查找关键字等于某给定值的节点,若找到则带回相应节点的指针；若找到则带回相应节点的指针；否则带回否则带回NULL。设关键字域域名为。设关键字域域名为key；欲检索的关键字值为；欲检索的关键字值为key0.如下算法实现检如下算法实现检索：索：p0=NULL;p =head;while(p!=NULL&p-key!=key0)p0=p;p =p-next;第15页，此课件共24页哦向单向链表插入一项向单向链表插入一项:设有下图的链表，现在要把设有下图的链表，现在要把r所指示的数据项插入到所指示的数据项插入到 p0、p 所指两项之间。操

17、所指两项之间。操作是作是:r-next =p;p0-next =r;p0 =r;/*使使 p0 仍为仍为 p 的前一项的前一项*/r:5p0:p:1234.第16页，此课件共24页哦 从单向链表上删除一项从单向链表上删除一项:设有下图的链表，现在要删除设有下图的链表，现在要删除p所指项。删除算法是：所指项。删除算法是：p0-next =p-next;free(p)-q=p;p =p-next;p0-next =p;free(q)p0:1234.p:q:第17页，此课件共24页哦o/*动态建立一个链表，存放学生的学号和成绩动态建立一个链表，存放学生的学号和成绩,数据结束条件为输入学号数据结束条件

18、为输入学号为为0,并编写遍历打印链表、编写根据条件（学号）删除结点的函数、并编写遍历打印链表、编写根据条件（学号）删除结点的函数、按顺序插入结点的函数按顺序插入结点的函数*/ostruct studentoint num;/*说明学生的学号说明学生的学号*/ofloat score;/*说明学生的成绩说明学生的成绩*/ostruct student *next;/*指向下一个结点的指针指向下一个结点的指针*/o;o#include o#include o#define LEN sizeof(struct student)ostruct student*create();oint n;第18页，

19、此课件共24页哦o/*创建链表以输入学号为零结束101 90|103 98|105 76|0 0*/ostruct student*create()o struct student*head,*p1,*p2;o n=0;o p1=p2=(struct student*)malloc(LEN);/*开辟一个新单元*/o scanf(%d%f,&p1-num,&p1-score);ohead=NULL;o while(p1-num!=0)o n=n+1;o if(n=1)head=p1;o else p2-next=p1;o p2=p1;o p1=(struct student*)malloc(L

20、EN);o scanf(%d%f,&p1-num,&p1-score);o o p2-next=NULL;o return head;o第19页，此课件共24页哦C程序设计程序设计 第十二章第十二章 动态动态 主讲：高利军主讲：高利军 o/*遍历并输出链表*/ovoid print(struct student*head)ostruct student*p;o printf(nNow,These%d records are:n,n);o p=head;o if(head!=NULL)o do o printf(%d%5.1fn,p-num,p-score);o p=p-next;o while

21、(p!=NULL);o第20页，此课件共24页哦o/*删除链表结点103*/ostruct student*del(struct student*head,int num)ostruct student*p1,*p2;oif(head=NULL)printf(nlist null!);oelseo p1=head;o while(num!=p1-num&p1-next!=NULL)o /*p1指向的不是所要找的结点,并且后面还有结点*/o p2=p1;p1=p1-next;/*p1后移一个结点*/o if(num=p1-num)/*找到了*/o if(p1=head)head=p1-next;

22、o /*若p1指向的是首结点,把第二个结点地址赋予head*/o else p2-next=p1-next;o /*否则将下一 结点地址赋给前一结点地址*/o printf(delete:%dn,num);o n=n-1;o else printf(%d not been found!n,num);/*找不到结点*/o oreturn head;第21页，此课件共24页哦o/*插入链表结点102 90*/ostruct student*insert(struct student*head,struct student*stud)ostruct student*p0,*p1,*p2;o p1=h

23、ead;/*p1指向第一个结点*/o p0=stud;/*p0指向要插入结点*/o if(head=NULL)head=p0;p0-next=NULL;/*p0指向结点作为头结点*/o elseo while(p0-nump1-num)&(p1-next!=NULL)o p2=p1;/*p2指向刚才p1指向的结点*/o p1=p1-next;/*p1后移一个结点*/o if(p0-numnum)o if(head=p1)head=p0;/*插入原来第一个结点之前*/o else p2-next=p0;/*插入p2指向结点之后*/o p0-next=p1;o o elseo p1-next=p0

24、;p0-next=NULL;/*插到最后的结点之后*/o on=n+1;oreturn head;第22页，此课件共24页哦C程序设计程序设计 第十二章第十二章 动态动态 主讲：高利军主讲：高利军 o/*主程序*/omain()oostruct student*head,stu;oint del_num;oprintf(input records:n);ohead=create();/*返回头指针*/oprint(head);/*输出全部结点，验证链表的正确性*/oprintf(ninput the deleted record:);oscanf(%d,&del_num);/*输入要删除的学号*/ohead=del(head,del_num);oprint(head);/*输出全部结点，验证删除后链表的正确性*/oprintf(ninput the inserted record:);oscanf(%d%f,&stu.num,&stu.score);/*输入要插入的结点*/ohead=insert(head,&stu);/*返回头指针*/oprint(head);/*输出全部结点，验证插入后链表的正确性*/o第23页，此课件共24页哦第24页，此课件共24页哦