数据结构耿国华高教版_第2章课件

《数据结构耿国华高教版_第2章课件》由会员分享，可在线阅读，更多相关《数据结构耿国华高教版_第2章课件（85页珍藏版）》请在金锄头文库上搜索。

1、2020/8/29,1,数据结构课件,西北大学计算机系,本演示文稿可能包含观众讨论和即席反应。使用 PowerPoint 可以跟踪演示时的即席反应， 在幻灯片放映中，右键单击鼠标 请选择“会议记录” 选择“即席反应”选项卡 必要时输入即席反应 单击“确定”撤消此框 此动作将自动在演示文稿末尾创建一张即席反应幻灯片，包括您的观点。,2020/8/29,2,第2章 线性表,2.1 线性表的概念及运算 2.2 线性表的顺序存储 2.3 线性表的链式存储 2.4 一元多项式的表示及相加,2020/8/29,3,2.1 线性表的概念及运算,2.1.1 线性表的逻辑结构 2.1.2 线性表的抽象数据类型定

2、义,2020/8/29,4,线性表的定义,线性表(Linear List)是由n (n0)个类型相同的数据元素a1,a2,，an组成的有限序列，记做（a1,a2,，ai-1，ai，ai+1， ，an）。 数据元素之间是一对一的关系，即每个数据元素最多有一个直接前驱和一个直接后继。 线性表的逻辑结构图为：,2020/8/29,5,线性表的特点,同一性：线性表由同类数据元素组成，每一个ai必须属于同一数据对象。 有穷性：线性表由有限个数据元素组成，表长度就是表中数据元素的个数。 有序性：线性表中相邻数据元素之间存在着序偶关系。,2020/8/29,6,2.1.2 线性表的抽象数据类型定义,抽象数据

3、类型定义 ： ADT LinearList 数据元素：D=ai| aiD0, i=1,2,，n n0 ，D0为某一数据对象 关系： | ai, ai+1D0，i=1,2, ,n-1 基本操作： （1）InitList（L） 操作前提：L为未初始化线性表。 操作结果：将L初始化为空表。 （2）DestroyList(L) 操作前提：线性表L已存在。 操作结果：将L销毁。 （3）ClearList(L) 操作前提：线性表L已存在 。 操作结果：将表L置为空表。 ADT LinearList,2020/8/29,7,2.2 线性表的顺序存储,2.2.1 线性表的顺序存储结构 2.2.2 线性表顺序存

4、储结构上的基本运算,2020/8/29,8,顺序存储结构的定义,线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素，使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。采用顺序存储结构的线性表通常称为顺序表。 假设线性表中每个元素占k个单元，第一个元素的地址为loc(a1)，则第k个元素的地址为： loc(ai) =loc(a1)+(i-1)k,2020/8/29,9,顺序存储结构示意图,2020/8/29,10,顺序存储结构的C语言定义,#definemaxsize=线性表可能达到的最大长度

5、； typedef struct ElemType elemmaxsize； /* 线性表占用的数组空间*/ int last； /*记录线性表中最后一个元素在数组elem 中的位置（下标值），空表置为-1*/ SeqList； 注意区分元素的序号和数组的下标，如a1的序号为1，而其对应的数组下标为0。,2020/8/29,11,2.2.2 线性表顺序存储结构的基本运算,线性表的基本运算： 查找操作 插入操作 删除操作 顺序表合并算法 线性表顺序存储结构的优缺点分析,2020/8/29,12,查找操作,线性表的两种基本查找运算 按序号查找GetData(L,i)：要求查找线性表L中第i个数据元

6、素，其结果是L.elemi-1或L-elemi-1。 按内容查找Locate（L,e）: 要求查找线性表L中与给定值e相等的数据元素，其结果是：若在表L中找到与e相等的元素，则返回该元素在表中的序号；若找不到，则返回一个“空序号”，如-1。 线性表的查找运算算法描述为：,2020/8/29,13,线性表的查找运算,int Locate(SeqList L，ElemType e) i=0 ; /*i为扫描计数器，初值为0，即从第一个元素开始比较*/ while (i=L.last) /*若没找到，则返回空序号*/ ,2020/8/29,14,插入操作,线性表的插入运算是指在表的第i (1in+1

7、)个位置，插入一个新元素e，使长度为n的线性表 (e1，ei-1，ei，en) 变成长度为n+1的线性表（e1，,ei-1，e，ei，en）。 线性表的插入运算算法。,2020/8/29,15,插入算法示意图,已知：线性表 (4,9,15,28,30,30,42,51,62)，需在第4个元素之前插入一个元素“21”。则需要将第9个位置到第4个位置的元素依次后移一个位置，然后将“21”插入到第4个位置，,2020/8/29,16,插入运算,int InsList(SeqList *L,int i,ElemType e) int k; if( (iL-last+2) ) /*首先判断插入位置是否合

8、法*/ printf(“插入位置i值不合法”)；return(ERROR); if(L-last=maxsize-1) printf(“表已满无法插入”)； return(ERROR); for(k=L-last;k=i-1;k-) /*为插入元素而移动位置*/ L-elemk+1=L-elemk; L-elemi-1=e; /*在C语言中数组第i个元素的下标为i-1*/ L-last+; return(OK); 算法演示（此处连接算法演示程序）。,2020/8/29,17,删除操作,线性表的删除运算是指将表的第i(1in)个元素删去，使长度为n的线性表 (e1，,ei-1，ei，ei+1，e

9、n)，变成长度为n-1的线性表(e1，,ei-1， ei+1，en)。 算法思路示意 算法实现,2020/8/29,18,删除算法示意,将线性表(4,9,15,21,28,30,30,42,51,62)中的第5个元素删除。,2020/8/29,19,删除算法,int DelList(SeqList *L,int i,ElemType *e) /*在顺序表L中删除第i个数据元素，并用指针参数e返回其值*/ int k; if(iL-last+1) printf(“删除位置不合法！”)； return(ERROR)； *e= L-elemi-1; /* 将删除的元素存放到e所指向的变量中*/ fo

10、r(k=i;ilast;k+) L-elemk-1= L-elemk; /*将后面的元素依次前移*/ L-last-; return(OK); ,2020/8/29,20,合并算法,已知：有两个顺序表LA和LB，其元素均为非递减有序排列，编写一个算法，将它们合并成一个顺序表LC，要求LC也是非递减有序排列。 算法思想 ：设表LC是一个空表，为使LC也是非递减有序排列，可设两个指针i、j分别指向表LA和LB中的元素，若LA.elemiLB.elemj，则当前先将LB.elemj插入到表LC中，若LA.elemiLB.elemj ，当前先将LA.elemi插入到表LC中，如此进行下去，直到其中一个

11、表被扫描完毕，然后再将未扫描完的表中剩余的所有元素放到表LC中。 算法实现 此处连接算法演示,2020/8/29,21,顺序表合并算法实现,void merge(SeqList *LA, SeqList *LB, SeqList *LC) i=0;j=0;k=0; while(ilast ,2020/8/29,22,顺序存储结构的优点和缺点,优点： 1.无需为表示结点间的逻辑关系而增加额外的存储空间； 2.可方便地随机存取表中的任一元素。 缺点： 1.插入或删除运算不方便，除表尾的位置外，在表的其它位置上进行插入或删除操作都必须移动大量的结点，其效率较低； 2.由于顺序表要求占用连续的存储空间

12、，存储分配只能预先进行静态分配。因此当表长变化较大时，难以确定合适的存储规模。,2020/8/29,23,2.3 线性表的链式存储,链表定义： 采用链式存储结构的线性表称为链表 。 现在我们从两个角度来讨论链表： 1.从实现角度看，链表可分为动态链表和静态链表； 2.从链接方式的角度看，链表可分为单链表、循环链表和双链表。,2020/8/29,24,2.3.1 单链表 2.3.2 单链表上的基本运算 2.3.3 循环链表 2.3.4 双向链表 *2.3.5 静态链表 2.3.6 顺序表和链表的比较,链表,2020/8/29,25,2.3.1 单链表,结点（Node）为了正确地表示结点间的逻辑关

13、系，必须在存储线性表的每个数据元素值的同时，存储指示其后继结点的地址（或位置）信息，这两部分信息组成的存储映象叫做结点（Node）。 单链表：链表中的每个结点只有一个指针域，我们将这种链表称为单链表。 单链表包括两个域：数据域用来存储结点的值；指针域用来存储数据元素的直接后继的地址（或位置）。 头指针 ：指向链表头结点的指针。,2020/8/29,26,单链表的示例图,2020/8/29,27,带头结点的单链表示意图,有时为了操作的方便，还可以在单链表的第一个结点之前附设一个头结点。 带头结点的空单链表 带头结点的单链表,2020/8/29,28,单链表的存储结构描述,typedef stru

14、ct Node / * 结点类型定义 * / ElemType data； struct Node * next； Node, *LinkList；/* LinkList为结构指针类型*/,2020/8/29,29,2.3.2 单链表上的基本运算,线性表的基本运算： 建立单链表 单链表查找 单链表插入操作 单链表删除 算法应用示例： 求单链表的长度 求两个集合的差,2020/8/29,30,建立单链表,头插法建表 算法描述：从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头结点之后，直至读入结束标志为止。,2020/8/29,31,头插

15、法建表算法,Linklist CreateFromHead() LinkList L; Node *s; int flag=1; /* 设置一个标志，初值为1，当输入“$”时，flag为0，建表结束*/ L=(Linklist)malloc(sizeof(Node)；/*为头结点分配存储空间*/ L-next=NULL; while(flag) c=getchar(); if(c!=$) /*为读入的字符分配存储空间*/ s=(Node*)malloc(sizeof(Node); s-data=c; s-next=L-next; L-next=s; elseflag=0; ,2020/8/29

16、,32,尾插法建表,C1 ,s,r,L,2020/8/29,33,尾插法建表算法,Linklist CreateFromTail() /*将新增的字符追加到链表的末尾*/ LinkList L; Node *r, *s; int flag =1; L=(Node * )malloc(sizeof(Node);/*为头结点分配存储空间*/ L-next=NULL; r=L; /*r指针始终动态指向链表的当前表尾*/ while(flag)/*标志，初值为1。输入“$”时flag为0，建表结束*/ c=getchar(); if(c!=$) s=(Node*)malloc(sizeof(Node); s-data=c; r-next=s; r=s else flag=0;