【数据结结构课件】线性表

Tuesday,May05,20201数据结构课件西北大学计算机系本演示文稿可能包含观众讨论和即席反应。使用PowerPoint可以跟踪演示时的即席反应，•在幻灯片放映中，右键单击鼠标•请选择“会议记录”•选择“即席反应”选项卡•必要时输入即席反应•单击“确定”撤消此框此动作将自动在演示文稿末尾创建一张即席反应幻灯片，包括您的观点。Tuesday,May05,20202第2章线性表2.1线性表的概念及运算2.2线性表的顺序存储2.3线性表的链式存储2.4一元多项式的表示及相加Tuesday,May05,202032.1线性表的概念及运算2.1.1线性表的逻辑结构2.1.2线性表的抽象数据类型定义Tuesday,May05,20204线性表的定义线性表(LinearList)是由n(n≥0)个类型相同的数据元素a1,a2,…，an组成的有限序列，记做（a1,a2,…，ai-1，ai，ai+1，…，an）。数据元素之间是一对一的关系，即每个数据元素最多有一个直接前驱和一个直接后继。线性表的逻辑结构图为：Tuesday,May05,20205线性表的特点同一性：线性表由同类数据元素组成，每一个ai必须属于同一数据对象。有穷性：线性表由有限个数据元素组成，表长度就是表中数据元素的个数。有序性：线性表中相邻数据元素之间存在着序偶关系ai,ai+1。Tuesday,May05,202062.1.2线性表的抽象数据类型定义抽象数据类型定义：ADTLinearList{数据元素：D={ai|ai∈D0,i=1,2,…，nn≥0，D0为某一数据对象}关系：Ｓ＝｛ai,ai+1|ai,ai+1∈D0，i=1,2,…,n-1｝基本操作：（1）InitList（L）操作前提：L为未初始化线性表。操作结果：将L初始化为空表。（2）DestroyList(L)操作前提：线性表L已存在。操作结果：将L销毁。（3）ClearList(L)操作前提：线性表L已存在。操作结果：将表L置为空表。………}ADTLinearListTuesday,May05,202072.2线性表的顺序存储2.2.1线性表的顺序存储结构2.2.2线性表顺序存储结构上的基本运算Tuesday,May05,20208顺序存储结构的定义线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素，使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。采用顺序存储结构的线性表通常称为顺序表。假设线性表中每个元素占k个单元，第一个元素的地址为loc(a1)，则第k个元素的地址为：loc(ai)=loc(a1)+(i-1)×kTuesday,May05,20209顺序存储结构示意图存储地址内存空间状态逻辑地址Loc(a1)a11Loc(a1)+(2-1)ka22………loc(a1)+(i-1)kaii………loc(a1)+(n-1)kann...loc(a1)+(maxlen-1)k空闲Tuesday,May05,202010顺序存储结构的C语言定义#definemaxsize=线性表可能达到的最大长度；typedefstruct{ElemTypeelem[maxsize]；/*线性表占用的数组空间*/intlast；/*记录线性表中最后一个元素在数组elem[]中的位置（下标值），空表置为-1*/}SeqList；注意区分元素的序号和数组的下标，如a1的序号为1，而其对应的数组下标为0。Tuesday,May05,2020112.2.2线性表顺序存储结构的基本运算线性表的基本运算：1.查找操作2.插入操作3.删除操作4.顺序表合并算法线性表顺序存储结构的优缺点分析Tuesday,May05,202012查找操作线性表的两种基本查找运算1.按序号查找GetData(L,i)：要求查找线性表L中第i个数据元素，其结果是L.elem[i-1]或L-elem[i-1]。2.按内容查找Locate（L,e）:要求查找线性表L中与给定值e相等的数据元素，其结果是：若在表L中找到与e相等的元素，则返回该元素在表中的序号；若找不到，则返回一个“空序号”，如-1。线性表的查找运算算法描述为：Tuesday,May05,202013线性表的查找运算intLocate(SeqListL，ElemTypee){i=0;/*i为扫描计数器，初值为0，即从第一个元素开始比较*/while((i=L.last)&&(L.elem[i]!=e))i++;/*顺序扫描表，直到找到值为key的元素,或扫描到表尾而没找到*/if(i=L.last)return(i);/*若找到值为e的元素，则返回其序号*/elsereturn(-1);/*若没找到，则返回空序号*/}Tuesday,May05,202014插入操作线性表的插入运算是指在表的第i(1≤i≤n+1)个位置，插入一个新元素e，使长度为n的线性表(e1，…，ei-1，ei，…，en)变成长度为n+1的线性表（e1，…,ei-1，e，ei，…，en）。线性表的插入运算算法。Tuesday,May05,202015插入算法示意图已知：线性表(4,9,15,28,30,30,42,51,62)，需在第4个元素之前插入一个元素“21”。则需要将第9个位置到第4个位置的元素依次后移一个位置，然后将“21”插入到第4个位置，序号移动元素插入元素1234567810949152830304251624915283030426251491521283030426251Tuesday,May05,202016插入运算intInsList(SeqList*L,inti,ElemTypee){intk;if((i1)||(iL-last+2))/*首先判断插入位置是否合法*/{printf(“插入位置i值不合法”)；return(ERROR);}if(L-last=maxsize-1){printf(“表已满无法插入”)；return(ERROR);}for(k=L-last;k=i-1;k--)/*为插入元素而移动位置*/L-elem[k+1]=L-elem[k];L-elem[i-1]=e;/*在C语言中数组第i个元素的下标为i-1*/L-last++;return(OK);}算法演示（此处连接算法演示程序）。Tuesday,May05,202017删除操作线性表的删除运算是指将表的第i(1≤i≤n)个元素删去，使长度为n的线性表(e1，…,ei-1，ei，ei+1，…，en)，变成长度为n-1的线性表(e1，…,ei-1，ei+1，…，en)。算法思路示意算法实现Tuesday,May05,202018删除算法示意将线性表(4,9,15,21,28,30,30,42,51,62)中的第5个元素删除。序号123456781094915212830304262514915213030425162删除28后Tuesday,May05,202019删除算法intDelList(SeqList*L,inti,ElemType*e)/*在顺序表L中删除第i个数据元素，并用指针参数e返回其值*/{intk;if((i1)||(iL-last+1)){printf(“删除位置不合法！”)；return(ERROR)；}*e=L-elem[i-1];/*将删除的元素存放到e所指向的变量中*/for(k=i;i=L-last;k++)L-elem[k-1]=L-elem[k];/*将后面的元素依次前移*/L-last--;return(OK);}Tuesday,May05,202020合并算法已知：有两个顺序表LA和LB，其元素均为非递减有序排列，编写一个算法，将它们合并成一个顺序表LC，要求LC也是非递减有序排列。算法思想：设表LC是一个空表，为使LC也是非递减有序排列，可设两个指针i、j分别指向表LA和LB中的元素，若LA.elem[i]LB.elem[j]，则当前先将LB.elem[j]插入到表LC中，若LA.elem[i]≤LB.elem[j]，当前先将LA.elem[i]插入到表LC中，如此进行下去，直到其中一个表被扫描完毕，然后再将未扫描完的表中剩余的所有元素放到表LC中。算法实现此处连接算法演示Tuesday,May05,202021顺序表合并算法实现voidmerge(SeqList*LA,SeqList*LB,SeqList*LC){i=0;j=0;k=0;while(i=LA-last&&j=LB-last)if(LA-elem[i]=LB-elem[j]){LC-elem[k]=LA-elem[i];i++;k++;}else{LC-elem[k]=LB-elem[j];j++;k++;}while(i=LA-last)/*当表LA长则将表LA余下的元素赋给表LC*/{LC-elem[k]=LA-elem[i];i++;k++;}while(j=LB-last)/*当表LB长则将表LB余下的元素赋给表LC*/{LC-elem[k]=LB-elem[j];j++;k++;}LC-last=LA-last+LB-last;}Tuesday,May05,202022顺序存储结构的优点和缺点优点：1.无需为表示结点间的逻辑关系而增加额外的存储空间；2.可方便地随机存取表中的任一元素。缺点：1.插入或删除运算不方便，除表尾的位置外，在表的其它位置上进行插入或删除操作都必须移动大量的结点，其效率较低；2.由于顺序表要求占用连续的存储空间，存储分配只能预先进行静态分配。因此当表长变化较大时，难以确定合适的存储规模。Tuesday,May05,2020232.3线性表的链式存储链表定义：采用链式存储结构的线性表称为链表。现在我们从两个角度来讨论链表：1.从实现角度看，链表可分为动态链表和静态链表；2.从链接方式的角度看，链表可分为单链表、循环链表和双链表。Tuesday,May05,2020242.3.1单链表2.3.2单链表上的基本运算2.3.3循环链表2.3.4双向链表*2.3.5静态链表2.3.6顺序表和链表的比较链表Tuesday,May05,2020252.3.1单链表结点（Node）为了正确地表示结点间的逻辑关系，必须在存储线性表的每个数据元素值的同时，存储指示其后继结点的地址（或位置）信息，这两部分信息组成的存储映象叫做结点（Node）。单链表：链表中的每个结点只有一个指针域，我们将这种链表称为单链表。单链表包括两个域：数据域用来存储结点的值；指针域用来存储数据元素的直接后继的地址（或位置）。头指针：指向链表头结点的指针。Tuesday,May05,202026单链表的示例图头指针H存储地址数据域指针域1D437B1313C119HNULL25F3731A737G1943E2531Tuesday,May05,202027带头结点的单链表示意图有时为了操作的方便，还可以在单链表的第一个结点之前附设一个头结点。带头结点的空单链表带头结点的单链表∧Ha1a2…Han∧Tuesday,May05,202028单链表的存储结构描述typedefstructNode/*结点类型定义*/{ElemTypedata；structNode*next；}Node,*LinkList；/*LinkList为结构指针类型*/Tuesday,May05,2020292.3.2单链表上的基本运算线性表的基本运算：1.建立单链表2.单链表查找3.单链表插入操作4.单链表删除算法应用示例：1.求单链表的长度2.求两个集合的差Tuesday,May05,202030建立单链表头插法建表算法描述：从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点