《动态数据结构 (2)优秀课件.ppt》由会员分享，可在线阅读，更多相关《动态数据结构 (2)优秀课件.ppt（24页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、动态数据结构第1 页，本讲稿共24 页 1 2 3.n 如图的链式结构可以满足要求:当增加一张卡片时，只需要向计算机系统申请一块空间，联到链的适当位置上。例如，要增加一张卡片 50 插入到 2、3 之间，则只需要如下修改指针：若删除一节，只需要将其从链上摘下来即可。例删除2 节得:链上已经没有2 节了，删掉的节所占的存储空间还可以还回计算机系统，以便作其它用途。50第2 页，本讲稿共24 页 这就是一种动态数据结构中的链表。动态数据结构上的一项是一个动态变量，指针是标识动态变量的有力手段。动态变量与静态变量的区别在于:o 静态变量是程序中由程序员“显式”说明的变量。它有一个名字，在编译时，编译
2、程序已经给它分配存储空间。这块存储空间用变量的名字来标识。o 动态变量在程序中没有“显式”说明，它没有名字，在编译时编译程序不知道有该变量，不给（也不可能给）它分配空间。动态变量是在程序运行时，随程序存储数据的需要，由申请空间函数（例如malloc，当然也是由程序员安排的）随机的动态的申请来的空间。它没有名字，一般动态变量都由指针标识。当使用完毕后，由释放空间函数（例如free）释放，还回计算机存储管理系统，以备它用。第3 页，本讲稿共24 页sizeof 运算符:单目运算符 sizeof 的o 操作数是类型。o 运算结果是求得相应类型的尺寸，即存储相应类型数据所需要的字节数。例：sizeof
3、(int)/*结果是2*/sizeof(char)/*结果是1*/sizeof(struct date)/*若 struct date 是第十一章定义的日期类型，结果是6*/第4 页，本讲稿共24 页malloc 函数:原型是：void*malloc(unsigned long size);功能是：申请足够大内存区域用来存储长度为size 的数据对象，返回该区域的首指针。返回指针是void 类型的，调用者必须使用显示强制类型转换，把该指针转换成所需要类型的指针。#include 例:float*p;p=(float*)malloc(sizeof(float);第5 页，本讲稿共24 页free
4、 函数 动态申请的内存如果不再使用，应当适时释放。这样可以提高程序运行效率。free 函数用来释放经过malloc 申请的动态空间。free 的函数原型是 void free(void*ptr);free 函数的功能是：释放由malloc 申请的内存区域。free 的参数ptr 是一个指针，指向以前由malloc 申请的一个内存区域。例 free(p)/*释放p 所指向的，前边由malloc 申请的内存空间*/一块存储区域一经释放，便不能再使用。第6 页，本讲稿共24 页实用问题:若指针变量指向的用malloc 申请来的动态变量，是狐立的不能与其它变量相联系，显然作用不大。引进动态变量的目的是
5、构造动态数据结构。例如象本章开始介绍的那样，构造一个链表等。这就要求一个数据项上除基本的数据信息外，还应包含与其它数据项相联系的信息，也就是包含指针，呈左图形式。该结构必须用结构体类型描述，链表上一个节点的类型定义形式如右图所示。类型定义形式 struct t 基本数据部分；struct t*next;基本数据部分指针部分一个数据项 第7 页，本讲稿共24 页o 静态建立链表,遍历链表o#define NULL 0o#include stdio.ho struct studento char name20;/*说明学生的姓名*/o int number;/*说明学生的房间号*/o float
6、score;/*说明学生的分数*/o struct student*link;/*指向下一个结点的指针*/o;o main()o struct student a,b,c,*head,*p;o scanf(%s,a.name);o a.number=1;a.score=90;o scanf(%s,b.name);o b.number=2;b.score=92;o scanf(%s,c.name);o c.number=3;c.score=89;o head=&a;o a.link=&b;o b.link=&c;o c.link=NULL;o p=head;第8 页，本讲稿共24 页o doo
7、printf(%s%d%fn,p-name,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)o struct stu*create(int n);o struct stuo char name20;/*说明学生的姓名*/o int numbe
8、r;/*说明学生的房间号*/o int score;/*说明学生的分数*/o struct stu*link;/*指向下一个结点的指针*/o;o main()o o struct stu*p;o p=create(3);o do/*输出并检验量表建的是否正确*/o printf(%s%d%dn,p-name,p-number,p-score);o p=p-link;o while(p!=NULL);o 第10 页，本讲稿共24 页o struct stu*create(int n)o struct stu*head,*pf,*pb;o int i=0;o for(i=0;iname,&pb-n
9、umber,&pb-score);o if(i=0)o pf=head=pb;o else pf-link=pb;o pb-link=NULL;o pf=pb;o o return head;第1 1 页，本讲稿共24 页o 动态建立链表（头插入法建立链表）o/*建立一个5个结点的链表，存放学生数据（包括姓名、学号、成绩）。可编写一个建立链表的函数creat。程序如下：*/o#include o#include o#define LEN sizeof(struct stu)o struct stu*create(int n);o struct stuo char name20;/*说明学生的姓
10、名*/o int number;/*说明学生的房间号*/o int score;/*说明学生的分数*/o struct stu*link;/*指向下一个结点的指针*/o;o main()o o struct stu*p;o p=create(3);o do/*输出并检验量表建的是否正确*/o printf(%s%d%dn,p-name,p-number,p-score);o p=p-link;o while(p!=NULL);o 第12 页，本讲稿共24 页o/*前插法创建单链表*/o struct stu*create(int n)o o int i;o struct stu*p,*head
11、;o head=NULL;/*建立空头结点*/o for(i=0;iname,&p-number,&p-score);o p-link=head;/*指向头节点*/o head=p;/*更换头节点*/o o return head;o 第13 页，本讲稿共24 页创建单向链表:创建单向链表，是指用一项一项的数据逐步建立、形成一个链表。可以分成向链头加入数据和向链尾加入数据两种方式。创建单向链表可以分成向链头加入数据和向链尾加入数据两种方式。新项加入链头就是压栈的算法；新项加入链尾就是队列中入队的算法。遍历单向链表:遍历是指从头到尾将链表上数据全部加工一遍。可用如下左端的算法。但实用中，经常用如
12、下右端 的算法来遍历单向链表。p=head;p0=NULL;while(p!=NULL)p=head;加工 P-while(p!=NULL)p=p-next;加工 P-p0=p;p=p-next;第14 页，本讲稿共24 页 在单向链表上检索:检索是指在单向链表上查找关键字等于某给定值的节点,若找到则带回相应节点的指针；否则带回NULL。设关键字域域名为key；欲检索的关键字值为key0.如下算法实现检索：p0=NULL;p=head;while(p!=NULL&p-key!=key0)p0=p;p=p-next;第15 页，本讲稿共24 页向单向链表插入一项:设有下图的链表，现在要把r 所指
13、示的数据项插入到 p0、p 所指两项之间。操作是:r-next=p;p0-next=r;p0=r;/*使 p0 仍为 p 的前一项*/r:5p0:p:1 234.第16 页，本讲稿共24 页 从单向链表上删除一项:设有下图的链表，现在要删除p 所指项。删除算法是：p0-next=p-next;free(p)-q=p;p=p-next;p0-next=p;free(q)p0:1 2 34.p:q:第17 页，本讲稿共24 页o/*动态建立一个链表，存放学生的学号和成绩,数据结束条件为输入学号为0,并编写遍历打印链表、编写根据条件（学号）删除结点的函数、按顺序插入结点的函数*/o struct s
14、tudento int num;/*说明学生的学号*/o float score;/*说明学生的成绩*/o struct student*next;/*指向下一个结点的指针*/o;o#include o#include o#define LEN sizeof(struct student)o struct student*create();o int n;第18 页，本讲稿共24 页o/*创建链表以输入学号为零结束101 90|103 98|105 76|0 0*/o struct student*create()o struct student*head,*p1,*p2;o n=0;o p1
15、=p2=(struct student*)malloc(LEN);/*开辟一个新单元*/o scanf(%d%f,&p1-num,&p1-score);o head=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(LEN);o scanf(%d%f,&p1-num,&p1-score);o o p2-next=NULL;o return head;o 第19 页，本讲稿共24 页C 程序设计 第十二章 动态 主讲：高利军 o/*遍历并输出
16、链表*/o void print(struct student*head)o struct 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(p!=NULL);o 第20 页，本讲稿共24 页o/*删除链表结点103*/o struct student*del(struct student*head,int num)o struct student*p1,*p2;o if(head=N
17、ULL)printf(nlist null!);o elseo 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;o/*若p1 指向的是首结点,把第二个结点地址赋予head*/o else p2-next=p1-next;o/*否则将下一 结点地址赋给前一结点地址*/o printf(delete:%dn,num);o n=n-1;o else
18、printf(%d not been found!n,num);/*找不到结点*/o o return head;第21 页，本讲稿共24 页o/*插入链表结点102 90*/o struct student*insert(struct student*head,struct student*stud)o struct student*p0,*p1,*p2;o p1=head;/*p1 指向第一个结点*/o p0=stud;/*p0 指向要插入结点*/o if(head=NULL)head=p0;p0-next=NULL;/*p0 指向结点作为头结点*/o elseo while(p0-num
19、p1-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;p0-next=NULL;/*插到最后的结点之后*/o o n=n+1;o return head;第22 页，本讲稿共24 页C 程序设计 第十二章 动态 主讲：高利军 o/*主程序*/o main()o o
20、struct student*head,stu;o int del_num;o printf(input records:n);o head=create();/*返回头指针*/o print(head);/*输出全部结点，验证链表的正确性*/o printf(ninput the deleted record:);o scanf(%d,&del_num);/*输入要删除的学号*/o head=del(head,del_num);o print(head);/*输出全部结点，验证删除后链表的正确性*/o printf(ninput the inserted record:);o scanf(%d%f,&stu.num,&stu.score);/*输入要插入的结点*/o head=insert(head,&stu);/*返回头指针*/o print(head);/*输出全部结点，验证插入后链表的正确性*/o 第23 页，本讲稿共24 页第24 页，本讲稿共24 页