数据结构与算法课件

上传人：子*** IP属地：未知上传时间：2026-03-20 格式：PPT 页数：74 大小：817KB 积分：6 举报 版权申诉

已阅读5页，还剩69页未读，继续免费阅读

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

数据结构与算法

2.1概述

数据结构是一门研究数据组织、存储和运算的一般方法的学科。2.1概述

数据结构是一门研究数据组织、存储和运算的一般方法的学科。能输入到计算机中并能被计算机程序处理的符号的集合。整数(1,2)、实数(1.1,1.2)字符串(Beijing)、图形、声音。2.1概述

数据结构是一门研究数据组织、存储和运算的一般方法的学科。计算机管理图书问题在图书馆里有各种卡片：有按书名编排的、有按作者编排的、有按分类编排如何将查询图书的这些信息存入计算机中既要考虑查询时间短，又要考虑节省空间2.1概述

数据结构是一门研究数据组织、存储和运算的一般方法的学科。最简单的办法之一是建立一张表，每一本书的信息在表中占一行，如2.1概述

数据结构是一门研究数据组织、存储和运算的一般方法的学科。如何将0,1,2,3,4,5,6,7,8,9这10个数存放在计算机中能最快地达到你所需要的目的？目的不同，最佳的存储方方法就不同。从大到小排列：9,8,7,6,5,4,3,2,1,0输出偶数：0,2,4,6,8,1,3,5,7,9数据元素在计算机中的表示2.1概述

数据结构是一门研究数据组织、存储和运算的一般方法的学科。对数据结构中的节点进行操作处理(插入、删除、修改、查找、排序)数据元素(DataElement)

数据元素是数据的基本单位，即数据集合中的个体。有时一个数据元数可由若干数据项(DataItem)组成。数据项是数据的最小单位。数据元素亦称节点或记录。名词解释数据结构可描述为Group=（D，R）有限个数据元素的集合有限个节点间关系的集合1．数据的逻辑结构2、数据的存储结构3、数据的运算：检索、排序、插入、删除、修改等。A．线性结构

B．非线性结构A顺序存储B链式存储线性表栈队树形结构图形结构数据结构的三个方面数据结构可描述为Group=（D，R）线性结构

A,B,C,·······，X,Y,Z学生成绩表86胡孝臣986110395刘忠赏9861107100张卓9861109成绩姓名学号线性表——结点间是以线性关系联结1．数据的逻辑结构2、数据的存储结构3、数据的运算：检索、排序、插入、删除、修改等。A．线性结构B．非线性结构A顺序存储B链式存储线性表栈队树形结构图形结构数据结构的三个方面数据结构可描述为Group=（D，R）树形结构全校学生档案管理的组织方式计算机程序管理系统也是典型的树形结构ABCDEFGH树形结构——

结点间具有分层次的连接关系HBCDEFGA1．数据的逻辑结构2、数据的存储结构3、数据的运算：检索、排序、插入、删除、修改等。A．线性结构B．非线性结构A顺序存储B链式存储线性表栈队树形结构图形结构数据结构的三个方面(亦称物理结构)1423D={1,2,3,4}R={(1,2),(1,3),(1,4),(2,3)(3,4),(2,4)}213D={1,2,3}R={(1,2),(2,3),(3,2),(1,3)}

图形结构——节点间的连结是任意的1．数据的逻辑结构2、数据的存储结构3、数据的运算：检索、排序、插入、删除、修改等。A．线性结构B．非线性结构A顺序存储B链式存储线性表栈队树形结构图形结构数据结构的三个方面(亦称物理结构)元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储内容Loc(a)=Lo+（i-1)*m顺序存储每个元素所占用的存储单元个数元素n……..元素i……..元素2元素1存储内容顺序存储结构常用于线性数据结构，将逻辑上相邻的数据元素存储在物理上相邻的存储单元里。顺序存储结构的三个弱点：1.作插入或删除操作时，需移动大量元数。2.长度变化较大时，需按最大空间分配。3.表的容量难以扩充。1．数据的逻辑结构2、数据的存储结构3、数据的运算：检索、排序、插入、删除、修改等。A．线性结构B．非线性结构A顺序存储B链式存储

线性表栈队树形结构图形结构数据结构的三个方面(亦称物理结构)1536元素21400元素11346元素3

∧元素41345h

链式存储每个节点都由两部分组成：数据域和指针域。数据域存放元素本身的数据，指针域存放指针。数据元素之间逻辑上的联系由指针来体现。1536元素21400元素11346元素3

∧元素4head

1346

元素3

1536

…….

……..

…….

1536

元素2

1400

…….

……..

…….

∧

元素4

1346

1400

元素1

1345

指针

存储内容存储地址

链式存储13451536元素21400元素11346元素3

∧元素41345h

链式存储1.比顺序存储结构的存储密度小

(每个节点都由数据域和指针愈组成)。2.逻辑上相邻的节点物理上不必相邻。3.插入、删除灵活

(不必移动节点，只要改变节点中的指针)。链接存储结构特点：1．数据的逻辑结构2、数据的存储结构3、数据的运算：检索、排序、插入、删除、修改等。A．线性结构B．非线性结构A顺序存储B链式存储线性表栈队树形结构图形结构数据结构的三个方面(亦称物理结构)

数据结构侧重于解决问题的策略和方法，即研究算法。它不但要求给出问题的一种算法，还要求算法的时空效率高、算法结构和可读性好、容易验证等等。for(i=1;i<=n;++i)for(j=1;j<=n;++j)c[i][j]=0;算法时间复杂度表示为（n)=O(n2)2.1.2算法的基本概念

算法：是对特定问题求解步骤的一种描述。算法的五个特性：有穷性、确定性、可行性、输入和输出。评价算法：正确性、易读性、健壮性、运行时间及占用空间。

2.2线性表

线性表是n个元素的有限序列，它们之间的关系可以排成一个线性序列：

a1，a2，……

，ai，……，an其中n称作表的长度，当n=0时，称作空表。2.2.1线性表及运算2.除第一个和最后一个数据元素之外，其它数据元素有且仅有一个前驱和一个后继。第一个数据元素无前驱，最后一个数据元素无后继。线性表的特点：1.线性表中所有元素的性质相同。3.数据元素在表中的位置只取决于它自身的序号。在线性表上常用的运算有：初始化、求长度、取元素、定位、插入及删除等。2.2.2线性表的存储结构1.顺序存储结构2.链式存储结构elemlengthlistsize元素1元素2……..元素i……..01i-1V.elem[i-1]1.线性表的顺序存储结构,可用C语言中的一维数组来描述.#defineLISTINITSIZE100//线性表存储空间的初始分配量typedefstruct{ElemType*elem；//数组指针表示存储空间基址intlength；//当前长度intlistsize//当前分配的存储容量（以sizeof（ElemType）为单位）}SqlistC语言的库函数,测算ElemType节点需占用的字节数ai-1…..a2a1alegth

…ai+1aixStatusListInsert_sq（Sqlist

V，inti,ElemTypex）{if（i<1‖i>V.length+1）returnERROR;if(V.length>V.listsize)returnOVERFLOW;q=

V.elem[i-1];for(p=

V.elem[V.length-1];p>=q;

(p+1)=

q=x;++V.length;returnOK;}elemlengthlistsize…..a2a1alength…..ai+1ai01i-1iLength-1P（P+1）q

1.1插入运算ai-1…..a2a1

aiai+1

…alegth

alegth

…

…ai+1aix请同学们看以下的算法。

StatusListInsert_sq（Sqlist

V，inti,ElemTypex）{//在线性中V中第i个元素之前插入x，i的合法值为1

V.Length+1

if（i<1‖i>V.length+1）returnERROR;//i值不合法

if(V.length>V.listsize)returnOVERFLOW;//无存储空间

V.elem[i-1];//q为插入位置

for(q=

V.elem[V.length-1];p>=q;

p)//插入位置后的元素依次右移

(p+1)=

q=x;//插入x++V.length;//表长加1returnOK;}//ListInsert_sq

1.2删除运算StatusListDelete_sq（Sqlist

V，inti,ElemTypex）{

if（i<1‖i>V.length）returnERROR;P=

V.elem[i-1];x

=P;q=V.elem+V.length

1;for(++p;p<=q;++p)*(p

1)=*p

V.length;returnOK;}2线性表的链式存储结构

2.1单链表的插入运算

2.2单链表的删除运算2.线性表的链式存储结构特点：用一组任意的存储单元(可以是连续的,也可以是不连续的)存放线性表的数据元素。上图为(ZHAO，QIAN，SUN，LI，ZHOU，WU，ZHENG，WANG)线性表的线性链表存储结构，存储从头指针开始进行。线性链表表示法:a1a2an∧a3L…..TypedefstructLnode{ElemTypedata；structLnode*next；}Lnode，*linklist；线性表的链式存储结构可用C语言中的“结构指针”来描述2.线性表的链式存储结构带头结点的线性链表datanext单链表的插入运算StatusListInsert_L(LinkList&L,inti,ElemTypex){p=L;j=0;while(p&&j<i-1){p=p->next;++j;}if(!p

j>i-1)returnERROR;s=(structLNode*)malloc(sizeof(structLNode));

s->data=x;s->next=p->next;p->next=s;returnOK;}babax∧anaia1a2PPai-1xL单链表的插入运算StatusListInsert_L(LinkList&L,inti,ElemTypex){p=L;j=0;while(p&&j<i-1){p=p->next;++j;}if(!p

j>i-1)returnERROR;s=(structLNode*)malloc(sizeof(structLNode));

s->data=x;s->next=p->next;p->next=s;returnOK;}S∧anaia1a2Pai-1L单链表的插入运算StatusListInsert_L(LinkList&L,inti,ElemTypex){p=L;j=0;while(p&&j<i-1){p=p->next;++j;}if(!p

j>i-1)returnERROR;s=(structLNode*)malloc(sizeof(structLNode));

s->data=x;s->next=p->next;p->next=s;returnOK;}∧anaia1a2ai-1L单链表的插入运算StatusListInsert_L(LinkList&L,inti,ElemTypex){p=L;j=0;while(p&&j<i-1){p=p->next;++j;}if(!p

j>i-1)returnERROR;s=(structLNode*)malloc(sizeof(structLNode));

s->data=x;s->next=p->next;p->next=s;returnOK;}P∧anaia1a2ai-1L单链表的插入运算StatusListInsert_L(LinkList&L,inti,ElemTypex){p=L;j=0;while(p&&j<i-1){p=p->next;++j;}if(!p

j>i-1)returnERROR;s=(structLNode*)malloc(sizeof(structLNode));

s->data=x;s->next=p->next;p->next=s;returnOK;}P∧anaia1a2Pai-1L单链表的插入运算StatusListInsert_L(LinkList&L,inti,ElemTypex){p=L;j=0;while(p&&j<i-1){p=p->next;++j;}if(!p

j>i-1)returnERROR;s=(structLNode*)malloc(sizeof(structLNode));

s->data=x;s->next=p->next;p->next=s;returnOK;}∧anaia1a2Pai-1L单链表的插入运算StatusListInsert_L(LinkList&L,inti,ElemTypex){p=L;j=0;while(p&&j<i-1){p=p->next;++j;}if(!p

j>i-1)returnERROR;s=(structLNode*)malloc(sizeof(structLNode));

s->data=x;s->next=p->next;p->next=s;returnOK;}S∧anaia1a2Pai-1xL单链表的插入运算StatusListInsert_L(LinkList&L,inti,ElemTypex){p=L;j=0;while(p&&j<i-1){p=p->next;++j;}if(!p

j>i-1)returnERROR;s=(structLNode*)malloc(sizeof(structLNode));

s->data=x;s->next=p->next;p->next=s;returnOK;}S∧anaia1a2Pai-1xL单链表的插入运算StatusListInsert_L(LinkList&L,inti,ElemTypex){p=L;j=0;while(p&&j<i-1){p=p->next;++j;}if(!p

j>i-1)returnERROR;s=(structLNode*)malloc(sizeof(structLNode));

s->data=x;s->next=p->next;p->next=s;returnOK;}S∧anaia1a2Pai-1xL单链表的插入运算StatusListInsert_L(LinkList&L,inti,ElemTypex){p=L;j=0;while(p&&j<i-1){p=p->next;++j;}if(!p

j>i-1)returnERROR;s=(structLNode*)malloc(sizeof(structLNode));

s->data=x;s->next=p->next;p->next=s;returnOK;}在看程序之前，先介绍链表的创建。Linklistcreat(){linklisthead,p1,p2;n=0；p1=p2=(structlnode*)malloc(LEN)；scanf(“%d”,&p1->data)；head->next=NULL;while(p1->data!>0){n=n+1；

if(n==1)head->next=p1；

elsep2->next=p1；

p2=p1；p1=(structlnode*)malloc(LEN)；