线性表和数组课件

引入线性结构l线性结构是最常用、最简单的一种数据结构。而线性表是一种典型的线性结构。其基本特点是线性表中的数据元素是有序且是有限的。l在这种结构中：l 存在一个唯一的被称为“第一个”的数据元素；l 存在一个唯一的被称为“最后一个”的数据元素；l 除第一个元素外，每个元素均有唯一一个直接前驱；l 除最后一个元素外，每个元素均有唯一一个直接后继。l列车编组 线性结构的定义：线性结构的定义：若结构是非空有限集，则有且仅有一个开始结点和一个终端结若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前驱和一个直接后继。点，并且所有结点都最多只有一个直接前驱和一个直接后继。线性结构的表达式线性结构的表达式（a1，a2，a3，an）线性结构的特点：线性结构的特点：有且仅有一个有且仅有一个首结点和尾结点首结点和尾结点 除首尾结点以外，其它结点除首尾结点以外，其它结点有且仅有一个有且仅有一个前驱结点前驱结点 和一个后继结点和一个后继结点线性结构包括：线性结构包括：线性表、栈、队列、数组和广义表线性表、栈、队列、数组和广义表结点间的逻辑关系是一对一的结点间的逻辑关系是一对一的线性结构 2.1 线性表的线性表的逻辑结构逻辑结构 2.2 线性表的顺序表示和实现线性表的顺序表示和实现 2.3 线性表的链式表示和实现线性表的链式表示和实现 2.4 一元多项式的表示和相加一元多项式的表示和相加第2章 线性表一、线性表的定义一、线性表的定义 L=（a1,a2,ai-1,ai,ai+1,an）由由n个元素构成的有限序列，记为个元素构成的有限序列，记为n n为线性表的为线性表的长度长度,当当n=0n=0时时L L为空表为空表ai的直接前驱的直接前驱ai的直接后继的直接后继 同一线性表中的元素必定具有相同特性，即属同一线性表中的元素必定具有相同特性，即属同一线性表中的元素必定具有相同特性，即属同一线性表中的元素必定具有相同特性，即属 同一数据对象，且相邻元素具有序偶关系同一数据对象，且相邻元素具有序偶关系同一数据对象，且相邻元素具有序偶关系同一数据对象，且相邻元素具有序偶关系 n n是有限大是有限大是有限大是有限大2.1 线性表的逻辑结构线性表中的数据元素ai所代表的具体含义随具体应用的不同而不同，在线性表的定义中，只不过是一个抽象的表示符号。l 线性表中的结点可以是单值元素(每个元素只有一个数据项)。l例1:26个英文字母组成的字母表：(A，B，C、Z）l例2：某校从1978年到1983年各种型号的计算机拥有量的变化情况：(6，17，28，50，92，188）l例3：一副扑克的点数 (2，3，4，J，Q，K，A)线性表中的线性表中的结点结点可以是可以是记录型记录型元素，每个元素含有多个元素，每个元素含有多个数据项数据项，每个项称为结点的一个域，每个项称为结点的一个域。每个元素有一个可以。每个元素有一个可以唯一标识每个结点的唯一标识每个结点的数据项组数据项组，称为，称为关键字关键字。例例4：学生情况登记表学生情况登记表学号学号姓名姓名性别性别年龄年龄班级班级0205210102052101于春梅于春梅女女2020计计0210210205210202052102林苹林苹女女2020计计0210210205210302052103康强康强男男2121计计0210210205210402052104黄一爽黄一爽女女2020计计0210212.1 线性表的类型定义l 若线性表中的结点是按值(或按关键字值)由小到大(或由大到小)排列的，称线性表是有序的。l 线性表是一种相当灵活的数据结构，其长度可根据需要增长或缩短。l 对线性表的数据元素可以访问、插入和删除。二、线性表的抽象数据类型表示二、线性表的抽象数据类型表示（ADT 见教材见教材P7）ADT List ADT List数据对象：数据对象：数据关系：数据关系：基本操作：基本操作：D=ai|aiElemSet,i=1,2,n,n0R=|ai 1,ai D,i=2,nInitList(&L);/建建空表，初始化空表，初始化DestoryList(&L);/撤销表，释放内存撤销表，释放内存int ListLength(L);/求表中元素个数，即表长求表中元素个数，即表长PriorElem(L,cur_e,&pre_e);/求求当前元素当前元素cur_e的前驱的前驱NextElem(L,cur_e,&next_e);/求当前求当前元素元素cur_e的后继的后继GetElem(L,i);/取线性表取线性表L L中的第中的第i i个元素个元素ListInsertBefore(&L,i,e);/在在第第i个元素之前插入新的元素个元素之前插入新的元素eListDelete(&L,i,&e);/删除第删除第i个元素并返回此元素个元素并返回此元素2.1 线性表的逻辑结构两集合合并 教材P18void union(List&La,List Lb)La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i=Lb_len;i+)GetElem(Lb,i,e);if(!LocateElem(La,e,equal)ListInsert(La,+La_len,e);void MergeList(List La,List Lb,List&Lc)InitList(Lc);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);while(i=La_len)&(j=Lb_len)/La和Lb均非空 GetElem(La,i,ai);GetElem(Lb,j,bj);if(ai=bj)ListInsert(Lc,+k,ai);+i;else ListInsert(Lc,+k,bj);+j;while(i=La_len)/La有剩余元素 GetElem(La,i+,ai);ListInsert(Lc,+k,ai);while(j=Lb_len)/Lb有剩余元素 GetElem(Lb,j+,bj);ListInsert(Lc,+k,bj);/MergeList一、顺序表的表示一、顺序表的表示顺序存储定义：顺序存储定义：把逻辑上相邻的元素存储在物理把逻辑上相邻的元素存储在物理 位置上相邻的存储单元中。位置上相邻的存储单元中。采用顺序存储结构存储的线性表采用顺序存储结构存储的线性表简言之：简言之：逻辑相邻，物理也相邻逻辑相邻，物理也相邻顺序存储方法：顺序存储方法：用一组用一组地址连续地址连续的存储单元依次的存储单元依次 存放线性表的数据元素。存放线性表的数据元素。2.2 线性表的顺序表示和实现已知：已知：L=（a1,a2,ai-1,ai,ai+1,an）bb+1b+2b+(maxlen-1)a1a2ai-1aiai+1anb+(i-1)占占k个存储单元个存储单元b+(i-1)*kLoc(ai+1)Loc(ai)存储单元的个数存储单元的个数+k=Loc(ai)loc(a1)=+(i-1)*k Loc(a1)表示线性表第表示线性表第1个元素个元素a1的存储位置，的存储位置，若每个元素占用若每个元素占用k个存储单元个存储单元2.2 线性表的顺序表示和实现线性表顺序存储结构的特点线性表顺序存储结构的特点1、逻辑上相邻的物理元素，其物理位置上也相邻 2、若已知线性表中第1个元素的存储位置，则线性表中任意 一个元素的位置都可由公式计算得出。即，线性表的顺序存储结构是一种随机存取的存储结构。例：例：一个一维数组一个一维数组M，下标范围是，下标范围是0到到9，每个数组元素用，每个数组元素用相邻的相邻的5个字节存储。存储器按字节编址，设存储数组元素个字节存储。存储器按字节编址，设存储数组元素M0的第一个字节的地址是的第一个字节的地址是98，则，则M3的第一个字节的地的第一个字节的地址是址是 。1132.2 线性表的顺序表示和实现先为顺序表空间设定一个初始分配量，一旦因插入元素而空先为顺序表空间设定一个初始分配量，一旦因插入元素而空间不足时，可为顺序表增加一个固定长度的空间增量。间不足时，可为顺序表增加一个固定长度的空间增量。线性表的动态分配顺序存储结构线性表的动态分配顺序存储结构#define LIST_INIT_SIZE 100/存储空间的初始分配量存储空间的初始分配量#define LISTINCREMENT 10/存储空间的分配增量存储空间的分配增量Typedef struct ElemType*elem;/表基址表基址(用指针用指针*elemelem表示表示）int length;/表长度（表长度（表中有多少个元素表中有多少个元素）int listsize;/当前分配的表尺寸（当前分配的表尺寸（字节单位字节单位）SqList;存储结构描述如下存储结构描述如下（见教材（见教材P P2121）：2.2 线性表的顺序表示和实现sizeof(x)的意思是：的意思是：计算变量计算变量x的长度的长度(字节数字节数)malloc(m)函数的意思是：新开一片函数的意思是：新开一片大小为大小为m字节的连续空间，并把该字节的连续空间，并把该区首址作为函数值。区首址作为函数值。Status InitList_Sq(SqList&L)/创建一个空线性表创建一个空线性表 L.elem=(ElemType*)malloc(LIST_INIT_SIZE sizeof(ElemType);If(!L.elem)exit(OVERFLOW);/分配失败，结束程序分配失败，结束程序 L.length=0;/暂无元素放入，空表暂无元素放入，空表 L.listsize=LIST_INIT_SIZE;/表尺寸表尺寸=初始分配量初始分配量 Return OK;/InitList_Sq/InitList_Sq动态创建一个空顺序表的算法：动态创建一个空顺序表的算法：（见教材（见教材P P2121）2.2 线性表的顺序表示和实现二、线性表的顺序存储实现二、线性表的顺序存储实现1、插入、插入插入、删除、查找插入、删除、查找 含义：在线性表的含义：在线性表的第第i i个元素之前个元素之前插入一个新的插入一个新的 数据元素数据元素 实现步骤实现步骤 将第将第n n到第到第i i个元素依次向后移动一个位置个元素依次向后移动一个位置 将要插入的元素保存到第将要插入的元素保存到第i i个位置上个位置上 将表长将表长n n加加1 1共（共（n-i+1n-i+1）个元素）个元素ai-1和和ai的逻辑关系发生变化的逻辑关系发生变化注意：注意：i i的取值范围的取值范围1in+11in+12.2 线性表的顺序表示和实现 实现算法实现算法(教材教材P P2222)realloc(*p,newsize)realloc(*p,newsize)函数的意思是：新开一片大小为函数的意思是：新开一片大小为newsizenewsize的连的连续空间，并把以续空间，并把以*p*p为首址的原空间数据都拷贝进去。为首址的原空间数据都拷贝进去。Status ListInsert_Sq(SqList&L,int i,ElemType e)if(i L.length+1)return ERROR;/检验检验i 值的合法性值的合法性 if(L.length L.listsize)/若表长超过表尺寸则要增加尺寸若表长超过表尺寸则要增加尺寸 newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENTLISTINCREMENT)*sizeof(ElemType);if(newbase=NULL)exit(OVERFLOW);/分配失败则退出并报错分配失败则退出并报错L.elem=newbase;/重置新基址重置新基址L.listsize=L.listsize+LISTINCREMENT LISTINCREMENT;/增加表尺寸增加表尺寸2.2 线性表的顺序表示和实现 q=&(L.elemi-1);/q为插入位置为插入位置 for(p=&L.elemL.length-1;p=q;-p)*(p+1)=*p;/插入位置及之后的元素统统后移插入位置及之后的元素统统后移,p为元素位置为元素位置*q=e;/插入插入e+L.length;/增加增加1个数据元素，则表长个数据元素，则表长+1 return OK;/ListInsert_Sq2.2 线性表的顺序表示和实现2、删除、删除 含义：删除线性表的含义：删除线性表的第第i i个位置个位置上的元素上的元素 实现步骤实现步骤 将第将第i+1i+1到第到第n n个元素依次向前移动一个位置个元素依次向前移动一个位置 将表长将表长n n减减1 1共（共（n-in-i）个元素）个元素ai-1、ai、ai+1的逻辑关系发生变化的逻辑关系发生变化注意：注意：i i的取值范围的取值范围1in1in2.2 线性表的顺序表示和实现Status ListDelete_Sq(SqList&L,int i,ElemType&e)/在顺序表在顺序表L中删除第中删除第 i 个元素，用个元素，用 e 返回其值返回其值 if(i L.length)return ERROR;/i 值不合法，返回值不合法，返回 p=&L.elemi-1;/p 是被删除元素的位置是被删除元素的位置 e=*p;/被删除元素的值赋给被删除元素的值赋给 e q=L.elem+L.length-1;/q 是表尾的位置是表尾的位置 for(+p;pdataai的值的值p-nextai+1的地址的地址2.3 线性表的链式表示和实现（1）单链表的建立和输出）单链表的建立和输出例：用单链表结构来存放2626个英文字母组成的线性 表（a a，b b，c c，z z）,请写出C C语言程序。实现思路：实现思路：先开辟头指针，然后陆续为每个结点开辟存储空先开辟头指针，然后陆续为每个结点开辟存储空间并及时赋值，后继结点的地址要提前送给前面的指针。间并及时赋值，后继结点的地址要提前送给前面的指针。难点分析：难点分析：每个数据元素在内存中是每个数据元素在内存中是“零散零散”存放的，其存放的，其首地址怎么找？又怎么一一链接？首地址怎么找？又怎么一一链接？2.3 线性表的链式表示和实现#include#includetypedef struct node char data;struct node*next;node;node*p,*q,*head;/一般需要一般需要3 3个指针变量个指针变量int n;/数据元素的个数数据元素的个数int m=sizeof(node);/*/*结构类型定义好之后，每个变量的结构类型定义好之后，每个变量的 长度就固定了，长度就固定了，m m求一次即可求一次即可*/*/将全局变量及函数提前说明：将全局变量及函数提前说明：2.3 线性表的链式表示和实现void build()/字母链表的生成。字母链表的生成。int i;head=(node*)malloc(m);/m=sizeof(node)前面已求出前面已求出p=head;for(i=1;idata=i+a-1;/第一个结点值为字符第一个结点值为字符a p-next=(node*)malloc(m);/为后继结点开新空间为后继结点开新空间 p=p-next；/让指针变量让指针变量P指向后一个结点指向后一个结点p-data=i+a-1;/最后一个元素要单独处理最后一个元素要单独处理p-next=NULL;/单链表尾结点的指针域要置空！单链表尾结点的指针域要置空！2.3 线性表的链式表示和实现void display()/字母链表的输出字母链表的输出p=head;while(p)/当指针不空时循环，仅限于无头结点的情况当指针不空时循环，仅限于无头结点的情况 printf(%c,p-data);p=p-next;/让指针不断后移让指针不断后移 讨论：讨论：要统计链表中数据元素的个数，该如何改写？要统计链表中数据元素的个数，该如何改写？sum=0;sum=0;sum+;2.3 线性表的链式表示和实现（2 2）单链表的读取）单链表的读取思路：思路：要读取第要读取第i i个数据元素，必须从头指针起一直找到该个数据元素，必须从头指针起一直找到该 结点的指针结点的指针p p读取读取第第i i个数据元素的操作函数可写为：个数据元素的操作函数可写为：Status GetElem_L(LinkList L,int i,ElemType&e)p=L-next;j=1;/带头结点的链表带头结点的链表 while(p&jnext;+j;if(!p|ji)return ERROR;/第第i i个元素不存在个元素不存在 e=p-data;return OK;缺点：缺点：想寻找单链表中第想寻找单链表中第i i个元素，只能从头指针开始逐一个元素，只能从头指针开始逐一 查询，无法随机存取查询，无法随机存取 。2.3 线性表的链式表示和实现在单链表中第在单链表中第i i个位置插入一个元素个位置插入一个元素x的示意图如下：的示意图如下：xs链表插入的核心语句：链表插入的核心语句：Step 1Step 1Step 1Step 1：s-next=p-next;s-next=p-next;Step 2Step 2Step 2Step 2：p-next=s p-next=s；p-nexts-next思考：思考：1 1、Step1Step1和和2 2能否互换？能否互换？2 2、若已知指向、若已知指向ai的指针为的指针为P P，能否实现插入操作？，能否实现插入操作？x 结点的生成方式：结点的生成方式：s=(node*)malloc(m);s-data=x;s-next=?插插插插 入入入入 x（3 3）单链表的插入）单链表的插入pai-1aipai-1ai2.3 线性表的链式表示和实现 Status ListInsert_L(LinkList L，int I，ElemType x)/L 为带头结点的单链表的头指针为带头结点的单链表的头指针/在链表中第在链表中第i 个结点之前插入新的元素个结点之前插入新的元素 x /LinstInsert_Lp=L;j=0;if(!p|j i-1)return ERROR；/i 大于大于n+1或者小于或者小于1 s=（LinkList）malloc（sizeof（Lnode）;/生成新结点生成新结点if(s=NULL)return ERROR;while(p&j next；+j；/寻找第寻找第 i-1 个结点个结点s-data=x;s-next=p-next;p-next=s;/插入插入return OK；算法的时间复杂度算法的时间复杂度为为:O(n)2.3 线性表的链式表示和实现在单链表中删除第在单链表中删除第i i个元素的示意图如下：个元素的示意图如下：pai+1 ai-1ai删除动作的核心语句（要借助辅助指针变量删除动作的核心语句（要借助辅助指针变量q q）：）：q=p-next;/首先保存首先保存ai的指针；的指针；p-next=q-next;/将将ai-1、ai+1两结点相连，淘汰两结点相连，淘汰ai结点；结点；free(q)；/彻底释放彻底释放ai结点空间结点空间p-next(p-next)-nextq（4 4）单链表的删除）单链表的删除2.3 线性表的链式表示和实现（三）应用举例（三）应用举例已知：已知：线性表线性表A A和和B B，分别由，分别由单链表单链表LaLa和和LbLb存储，其中数据存储，其中数据 元素按值元素按值非递减有序排列非递减有序排列（即已经有序）；（即已经有序）；例：例：两个链表的归并两个链表的归并重点是链表重点是链表要求：要求：将将A A和和B B归并为一个新的线性表归并为一个新的线性表C C,C,C的数据元素仍按的数据元素仍按 值非递减排列。设线性表值非递减排列。设线性表C C由单链表由单链表 Lc Lc 存储。存储。假设：假设：A=A=（3 3，5 5，8 8，1111），），B=B=（2 2，6 6，8 8，9 9，1111）预测：预测：合并后的合并后的C C=（2,3,5,6,8,8,9,112,3,5,6,8,8,9,11，1111）2.3 线性表的链式表示和实现链表示意图：链表示意图：合并算法设计：算法设计：算法主要包括算法主要包括搜索、比较、插入搜索、比较、插入三个操作：三个操作：搜索：搜索：需要设立需要设立三个指针三个指针来指向来指向La、Lb和和Lc c链表；链表；比较：比较：比较比较La a和和Lb b表中结点数据的大小；表中结点数据的大小；插入：插入：将将La a和和Lb b表表中数据中数据较小的结点插入新链表较小的结点插入新链表Lc c。3 5 8 11 LaLb2 6 8 11 9 Lc 2 3 5 6 8 8 9 11 11 2.3 线性表的链式表示和实现PcPaPa、PbPb用于搜索用于搜索LaLa和和LbLb，PcPc指向新链表指向新链表LcLc的当前结点。的当前结点。链表链表LcLc存储在新开辟的空间中存储在新开辟的空间中，归并过程示意如下：，归并过程示意如下：Lb2 6 8 119 3 5 8 11 LaLc 2 3 5 Pa6 Pb8 PcPbPcPaPaPcPcPbPcPaPb2.3 线性表的链式表示和实现PaPa、PbPb用于搜索用于搜索LaLa和和LbLb，PcPc指向新链表指向新链表LcLc的当前结点。的当前结点。链表链表LcLc利用当前空间进行存储，利用当前空间进行存储，归并过程示意如下：归并过程示意如下：Lc=PcLb2 6 8 119 3 5 8 11 LaPaPbX XPcX XPbPcPaPcPaPcPbX XPcX XPaPcPbX XPcPbPcX X2.3 线性表的链式表示和实现算法实现：算法实现：Void MergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc)free(Lb);/释放释放LbLb的头结点的头结点 pc-next=pa?pa:pb;/插入非空表的剩余段插入非空表的剩余段 while(pa&pb)/将将pa pa、pbpb结点按大小依次插入结点按大小依次插入Lc中中 if(pa-datadata)pc-next=pa;pc=pa;pa=pa-next;else pc-next=pb;pc=pb;pb=pb-next;pa=LaLa-next;pb=LbLb-next;Lc=pc=La；/有头结点有头结点?是条件运算符（为真是条件运算符（为真则取第则取第1 1项）项）2.3 线性表的链式表示和实现特点：特点：1、从任一结点出发均可找到表中其他结点。、从任一结点出发均可找到表中其他结点。2、操作仅有、操作仅有 一一 点与单链表不同：点与单链表不同：单链表单链表-p=NULL 或或 p-next=NULL 循环链表循环链表-p=head 或或 p-next=head（四）循环链表：（四）循环链表：表中最后一个结点的指针域指向头结点，使表中最后一个结点的指针域指向头结点，使 整个链表形成一个环。整个链表形成一个环。带头结点的带头结点的空空循环链表样式循环链表样式H循环链表示意图循环链表示意图a1heada2an2.3 线性表的链式表示和实现单链表中查找只能从前往后，而不能从后往前查。单链表中查找只能从前往后，而不能从后往前查。为了查找方便，提高查找速度，可以在结点上增加为了查找方便，提高查找速度，可以在结点上增加一个指针域，用来存结点的直接前驱，这样的链表，一个指针域，用来存结点的直接前驱，这样的链表，称为称为双向链表双向链表。其结点的结构为其结点的结构为：priordatanext（五）双向链表（五）双向链表abc L2.3 线性表的链式表示和实现双向链表的插入操作：双向链表的插入操作：设设p已指向第已指向第 i 元素，请在第元素，请在第 i 个元素前插入元素个元素前插入元素 x x的前驱是的前驱是ai-1：s-prior=p-prior;ai-1的后继是的后继是x：p-prior-next=s;x的后继是的后继是ai：s-next=p ;ai 的前驱是的前驱是 x：p-prior=s;注意：要修改注意：要修改双向指针！双向指针！x sai-1 ai 指针域的变化指针域的变化：p2.3 线性表的链式表示和实现指针域的变化指针域的变化：后继方向：ai-1的后继由 ai(指针p)变为 ai+1(指针 p-next);p-prior-next=p-next ;ai-1 ai+1 ai p双向链表的删除操作：双向链表的删除操作：设设p指向第指向第 i 个元素，删除第个元素，删除第 i 个个 元素元素注意：要修改注意：要修改双向指针！双向指针！前驱方向：ai+1 的前驱由 ai(指针p)变为ai-1(指针 p-prior);p-next-prior=p-prior;2.3 线性表的链式表示和实现双向链表双向链表(Doubly Linked List)双向链表结点结构双向链表结点结构：指向直接前驱指向直接前驱 指向直接指向直接后继后继非空表非空表 空表空表firstfirst双向循环链表的定义双向循环链表的定义typedef int ListData;typedef struct dnode ListNode data;struct dnode*prior,*next;DblNode;typedef DblNode*DblList;建立空的双向循环链表建立空的双向循环链表void CreateDblList(DblList&first)first=(DblNode*)malloc (sizeof(DblNode);if(first=NULL)print(“存储分配错存储分配错!n”);exit(1);first-prior=first-next=first;/表头结点的链指针指向自己表头结点的链指针指向自己计算双向循环链表的长度计算双向循环链表的长度int Length(DblList first)/计算带表头结点的双向循环链表的长度计算带表头结点的双向循环链表的长度 DblNode*p=first-next;int count=0;while(p!=first)p=p-next;count+;return count;双向循环链表的插入双向循环链表的插入(非空表非空表)q-prior=p;q-next=p-next;p-next=q;q-next-prior=q;在结点在结点*p 后插入后插入25firstfirst314815pp31482515q双向循环链表的插入双向循环链表的插入(空表空表)q-prior=p;q-next=p-next;p-next=q;q-next-prior=q;pqfirst25firstp在结点在结点*p 后插入后插入25int Insert(DblList first,int i,ListData x)DblNode*p=Locate(first,i-1);/指针定位于插入位置指针定位于插入位置 if(p=first&i!=1)return 0;DblNode*q=(DblNode*)malloc (sizeof(DblNode);/分配结点分配结点 q-data=x;q-prior=p;p-next-prior=q;/在前驱方向链入新结点在前驱方向链入新结点 q-next=p-next;p-next=q;/在后继方向链入新结点在后继方向链入新结点 return 1;双向循环链表的删除双向循环链表的删除p-next-prior=p-prior;p-prior-next=p-next;(非空表非空表)删除删除48firstfirst314815p3115双向循环链表的删除双向循环链表的删除p-next-prior=p-prior;p-prior-next=p-next;first31p删除删除31int Remove(DblList first,int i)DblNode*p=Locate(first,i);/指针定位于删除结点位置指针定位于删除结点位置 if(p=first)return 0;p-next-prior=p-prior;p-prior-next=p-next;/删除结点删除结点 p free(p);/释放释放 return 1;一、多项式的线性表示方法一、多项式的线性表示方法Pn(x)=p0+p1x+p2x2+.+pnxn其系数可用线性表其系数可用线性表P（p0,p1,p2,pn）来表示。来表示。若多项式的阶次很高，而系数若多项式的阶次很高，而系数pi不为零的很少，所以，不为零的很少，所以，线性表线性表P可表示为：可表示为：P=(p0,e0)，(p1,e1)，.(pn,en)此时，可采用链式存储结构。此时，可采用链式存储结构。p0e0 p1e1 pnenL通常设计两个数据域（系数项和指数项）和一个指针域通常设计两个数据域（系数项和指数项）和一个指针域coefexpnlink2.4 一元多项式的表示及相加二、如何编程实现两个一元多项式相加？二、如何编程实现两个一元多项式相加？例：例：a=3xa=3x1414+2x+2x8 8-10 x-10 x6 6b=8xb=8x1414-3x-3x1010+10 x+10 x6 63 142 8-10 6a链表链表a a：链表链表b b：8 14-3 1010 6b1 1、运算规则：、运算规则：两多项式中两多项式中指数相同的项对应系数相加指数相同的项对应系数相加，若和不为若和不为0,0,则构成多项式则构成多项式c=(a+b)c=(a+b)中的一项；中的一项；a a和和b b中所中所有有指数不相同的项均应拷贝到指数不相同的项均应拷贝到c c中中。2.4 一元多项式的表示及相加2 2、实现思路：、实现思路：依次依次比较比较PaPa和和PbPb所指结点中的指数所指结点中的指数项，依项，依Pa-expn=、Pb-expn等情况，等情况，再决定是再决定是将两系数域的数值相加（并判其和是否为将两系数域的数值相加（并判其和是否为0 0），还），还是将较高指数项的结点插入到新表是将较高指数项的结点插入到新表c c中。中。3 142 8-10 6papb8 14-3 1010 6pc1114-310282.4 一元多项式的表示及相加1.1.线性结构线性结构(包括表、栈、队、数组）的定义和特点：包括表、栈、队、数组）的定义和特点：2.2.仅一个首、尾结点，其余元素仅一个直接前驱和一个仅一个首、尾结点，其余元素仅一个直接前驱和一个3.3.直接后继。直接后继。2.2.线性表线性表3.3.顺序存储顺序存储特征：特征：逻辑相邻，物理也相邻；逻辑相邻，物理也相邻；优点：优点：随机存取结构随机存取结构缺点：缺点：插入、删除需要移动大量元素插入、删除需要移动大量元素改进方案：改进方案：链式存储结构链式存储结构逻辑结构：逻辑结构：“一对一一对一”或或 “1:11:1”存储结构：存储结构：顺序存储、链式存储顺序存储、链式存储运运 算：算：插入、删除插入、删除第2章 小结循环链表的特点：循环链表的特点：从任一结点出发均可找到表中其他结点从任一结点出发均可找到表中其他结点双向链表的特点：双向链表的特点：可方便可方便找到任一结点的前驱找到任一结点的前驱找到任一结点的前驱找到任一结点的前驱4.4.链式存储链式存储特征：特征：逻辑上相邻，物理上不一定相邻逻辑上相邻，物理上不一定相邻；优点：优点：插入、删除快插入、删除快缺点：缺点：随机查找修改慢随机查找修改慢5.5.几种特殊链表的特点：几种特殊链表的特点：第2章 小结 教学要求：教学要求：1 1、了解线性表的逻辑结构特性，线性表的两种存储实现方式。、了解线性表的逻辑结构特性，线性表的两种存储实现方式。2 2、熟练掌握两种存储结构的描述方法。链表是本章的重点和、熟练掌握两种存储结构的描述方法。链表是本章的重点和 难点。难点。3 3、熟练掌握顺序表的定义与实现，包括查找、插入、删除算、熟练掌握顺序表的定义与实现，包括查找、插入、删除算 法的实现。法的实现。4 4、熟练掌握在各种链表结构中实现线性表操作的基本方法。、熟练掌握在各种链表结构中实现线性表操作的基本方法。第2章 线性表1 1、已知、已知L L是无表头结点的单链表，且是无表头结点的单链表，且P P结点既不是首元结点，也不是尾结点，结点既不是首元结点，也不是尾结点，试从下列提供的答案中选择合适的语句序列。试从下列提供的答案中选择合适的语句序列。a.a.在在P P结点之后插入结点之后插入S S结点的语句序列是结点的语句序列是 。b.b.在在P P结点之前插入结点之前插入S S结点的语句序列是结点的语句序列是 。c.c.在表首插入在表首插入S S结点的语句序列是结点的语句序列是 。d.d.在表尾插入在表尾插入S S结点的语句序列是结点的语句序列是 。（1 1）p-next=s;p-next=s;（2 2）p-next=p-next-next;p-next=p-next-next;（3 3）p-next=s-next;p-next=s-next;（4 4）s-next=p-next;s-next=p-next;（5 5）s-next=L;s-next=L;（6 6）s-next=NULL;s-next=NULL;（7 7）Q=p;Q=p;（8 8）while(p-next!=Q)p=p-next;while(p-next!=Q)p=p-next;（9 9）while(p-next!=NULL)p=p-next;while(p-next!=NULL)p=p-next;（1010）p=Q;p=Q;（1111）p=L;p=L;（1212）L=S;L=S;（1313）L=p;L=p;练习2 2、已知、已知L L是表头结点的非空单链表，且是表头结点的非空单链表，且P P结点既不是首元结点，也不是尾结点，结点既不是首元结点，也不是尾结点，试从下列提供的答案中选择合适的语句序列。试从下列提供的答案中选择合适的语句序列。a.a.删除删除P P结点的直接后继结点的语句序列是结点的直接后继结点的语句序列是 。b.b.删除删除P P结点的直接前驱结点的语句序列是结点的直接前驱结点的语句序列是 。c.c.删除删除P P结点的语句序列是结点的语句序列是 。d.d.删除首元结点的语句序列是删除首元结点的语句序列是 。e.e.删除表尾结点的语句序列是删除表尾结点的语句序列是 。（1 1）p=p-next;p=p-next;（2 2）p-next=p;p-next=p;（3 3）p-next=p-next-next;p-next=p-next-next;（4 4）p=p-next-next;p=p-next-next;（5 5）while(p!=NULL)p=p-next;while(p!=NULL)p=p-next;（6 6）while(Q-next!=NULL)p=Q;Q=Q-next;while(Q-next!=NULL)p=Q;Q=Q-next;（7 7）while(p-next!=Q)p=p-next;while(p-next!=Q)p=p-next;（8 8）while(p-next-next!=Q)p=p-next;while(p-next-next!=Q)p=p-next;（9 9）while(p-next-next!=NULL)p=p-next;while(p-next-next!=NULL)p=p-next;（1010）Q=p;Q=p;（1111）Q=p-next;Q=p-next;（1212）p=L;p=L;（1313）L=L-next;L=L-next;（1414）free(Q);free(Q);练习3 3、简述下列算法的功能。、简述下列算法的功能。Status A(ListedList L)/LStatus A(ListedList L)/L是无表头结点的单链表是无表头结点的单链表 if(L&L-next)if(L&L-next)Q=L;Q=L;L=L-next;L=L-next;P=L;P=L;while(p-next)p=p-next;while(p-next)p=p-next;p-next=Q;p-next=Q;Q-next=NULL:Q-next=NULL:Return OK;Return OK;/A/A练习1 1、简述以下三个概念的区别：头指针、头结点、首元、简述以下三个概念的区别：头指针、头结点、首元 结点。结点。2 2、假设元素依值递增有序排列的线性表、假设元素依值递增有序排列的线性表A A和和B B分别表示分别表示 两个集合（即同一表中的元素值各不相同），现要两个集合（即同一表中的元素值各不相同），现要 求另辟空间构成一个线性表求另辟空间构成一个线性表C C，其元素为，其元素为A A和和B B中元中元 素的素的交集交集，且表，且表C C中的元素也依值递增有序排列。中的元素也依值递增有序排列。试对单链表编写求试对单链表编写求C C的算法。的算法。3 3、试以循环链表作多项式的存储结构，编写求其导数的、试以循环链表作多项式的存储结构，编写求其导数的 算法，要求利用原多项式中的结点空间存放其导函数算法，要求利用原多项式中的结点空间存放其导函数 （多项式），同时释放所有无用（被删）结点。（多项式），同时释放所有无用（被删）结点。作业在线性表的在线性表的第第i i个位置前个位置前插入一个元素的示意图如下：插入一个元素的示意图如下：12132124283042771213212425252830427712345678123456789插入插入25252525i=5i=5123456789121321242528304277123456781213212428304277i=5删除顺序表中删除顺序表中第第i i个个元素的示意图如下：元素的示意图如下：另一种表述顺序表顺序表(SeqList)的类型定义的类型定义#define ListSize 100 /最大允许长度最大允许长度typedef int ListData;typedef struct ListData*data;/存储空间基址存储空间基址 int length;/当前元素个数当前元素个数 顺序表基本运算顺序表基本运算n初始化初始化 void InitList(SeqList&L)L.data=(ListData*)malloc (ListSize*sizeof(ListData);if(L.data=NULL)printf(“存储分配失败存储分配失败!n”);exit(1);L.length=0;按值查找按值查找：找找x x在表中的位置，若查找成功，在表中的位置，若查找成功，返回表项的位置，否则返回返回表项的位置，否则返回-1-1 int Find(SeqList&L,ListData x)int i=0;while(i L.length&L.datai!=x)i+;if(i L.length)return i;else return-1;按值查找按值查找：判断判断x x是否在表中是否在表中int IsIn(SeqList&L,ListData x)n int i=0,found=0;nwhile(i=0&i=0&i 0&i L.length)return i-1 1;else return-1;插入插入25 34 57 16 48 09 63 0 1 2 3 4 5 6 750插入 x25 34 57 5016 48 09 63 0 1 2 3 4 5 6 750i顺序表插入时，平均数据移动次数顺序表插入时，平均数据移动次数AMN在各表项在各表项插入概率相等时插入概率相等时顺序表的插入顺序表的插入 int Insert(SeqList&L,ListData x,int i)/在表中第在表中第 i 个位置插入新元素个位置插入新元素 x if(i L.length|L.length=ListSize)return 0;/插入不成功插入不成功 else for(int j=L.length;j i;j-)L.dataj=L.dataj-1;L.datai=x;L.length+;return 1;/插入成功插入成功 删除25 34 57 50 16 48 09 63 16删除 x25 34 57 50 48 09 63 0 1 2 3 4 5 6 7顺序表删除平均数据移动次数顺序表删除平均数据移动次数AMN在各表项在各表项删除概率相等时删除概率相等时顺序表的删除顺序表的删除 int Delete(SeqList&L,ListData x)/在表中删除已有元素在表中删除已有元素 x int i=Find(L,x);/在表中查找在表中查找 x if(i=0)L.length-;for(int j=i;j L.length;j+)L.dataj=L.dataj+1;return 1;/成功删除成功删除 return 0;/表中没有表中没有 x 顺序表的应用顺序表的应用:集合的集合的“并并”运算运算void Union(SeqList&A,SeqList&B)int n=Length(A);int m=Length(B);for(int i=0;i m;i+)int x=GetData(B,i);/在在B中取一元素中取一元素 int k=Find(A,x);/在在A中查找它中查找它 if(k=-1)/若未找到插入它若未找到插入它 Insert(A,x,n);n+;集合的集合的“交交”运算运算 void Intersection(SeqList&A,SeqList&B)int n=Length(A);int m=Length(B);int i=0;while(i-link=first;first=newnode;（插入前）（插入前）（插入后）（插入后）firstnewnodenewnodefirst第二种情况：在链表中间插入第二种情况：在链表中间插入 newnode-link=p-link;p-link=newnode；(插入前插入前)()(插入后插入后)newnodepnewnodep第三种情况：在链表末尾插入第三种情况：在链表末尾插入 newnode-link=p-link;p-link=newnode；p (插入前插入前)()(插入后插入后)newnodenewnodep 算法描述算法描述int Insert(LinkList&first,int x,int i)/在链表第在链表第 i 个结点处插入新元素个结点处插入新元素 x ListNode*p=first;int k=0;while(p!=NULL&k-link;k+;/找第找第 i-1个结点个结点 if(p=NULL&first!=NULL)printf(“无效的插入位置无效的插入位置!n”);/终止插终止插入入 return 0;ListNode*newnode=/创建新结点创建新结点 (ListNode*)malloc(sizeof(ListNode);newnode-data=x;if(first=NULL|i=1)/插入空表或非空表第一插入空表或非空表第一个结点之前个结点之前 newnode-link=first;/新结点成为第一个结点新结点成为第一个结点 if(first=NULL)last=newnode;/若是空表，表尾指若是空表，表尾指针指向新结点针指向新结点 first=newnode;else/插在表中间或末尾插在表中间或末尾newnode-link=p-link;if(p-link=NULL)last=newnode;p-link=newnode;return 1;n删除删除在单链表中删除在单链表中删除ai结点结点 q=p-link;p-link=q-link;删除前删除前删除后删除后ai-1aiai+1pqpai-1ai+1aiint Delete(LinkList&first,int i)/在链表中删除第在链表中删除第 i 个结点个结点 ListNode*p,*q;if(i=0)/删除表中第删除表中第 1 个结点个结点 q=first;first=first-link;else p=first;int k=0;while(p!=NULL&k-link;k+;/找第找第 i-1个结点个结点if(p=NULL|p-link=NULL)/找不到第i-1个结点 printf(“无效的删除位置!n”);return 0;else/删除中间结点或尾结点元素 q=p-link;p-link=q-link;if(q=last)last=p;/删除表尾结点 k=q-data;free(q);return k;/取出被删结点数据并释放q带带表头结点表头结点的单链表的单链表表头结点表头结点位于表的最前端，本身不带数据，仅标志表头。位于表的最前端，本身不带数据，仅标志表头。设置表头结点的目的设置表头结点的目的:简化链表操作的实现。简化链表操作的实现。非空表非空表 空表空表ana1firstfirst插入插入q-link=p-link;p-link=q;firstqfirstqfirstqfirstqpppp插入前插入前插入后插入后qq插入ppint Insert(LinkList first,ListData x,int i)/将新元素将新元素 x 插入在链表中第插入在链表中第 i 号结点位置号结点位置 ListNode*p=Locate(first,i-1);if(p=NULL)return 0;/参数参数i值不合理返回值不合理返回0 ListNode*newnode=/创建新结点创建新结点 (ListNode*)malloc(sizeof(ListNode);newnode-data=x;newnode-link=p-link;/链入链入 p-link=newnode;return 1;删除删除 q=p-link;p-link=q-link;delete q;删除前删除前first(非空表）非空表）(空表）空表）firstfirstpqpqfirst删除后删除后int delete(LinkList first,int i)/将链表第将链表第 i 号元素删去号元素删去 ListNode*p,*qp=Locate(first,i-1);/寻找第寻找第i-1个个结点结点 if(p=NULL|p-link=NULL)return 0;/i值不合理或空表值不合理或空表 q=p-link;p-link=q-link;/删除结点删除结点 free(q);/释放释放 return 1;前插法建立单链表前插法建立单链表从一个空表开始，重复读入数据：从一个空表开始，重复读入数据：生成新结点生成新结点将读入数据存放到新结点的数据域中将读入数据存放到新结点的数据域中将该新结点插入到链表的前端将该新结点插入到链表的前端直到读入结束符为止。直到读入结束符为止。firstqfirstqLinkList createListF(void)char ch;ListNode*q;LinkList head=/建立表头结点建立表头结点 (LinkList)malloc(sizeof(ListNode);head-link=NULL;while(ch=getchar()!=n)q=(listNode*)malloc(sizeof(ListNode);q-data=ch;/建立新结点建立新结点 q-link=head-link;/插入到表前端插入到表前端 head-link=q;return head;后插法建立单链表后插法建立单链表每次将新结点加在链表的表尾；每次将新结点加在链表的表尾；尾指针尾指针r,总是指向表中最后一个结点，新结点总是指向表中最后一个结点，新结点插在它的后面；插在它的后面；qfirstrfirstrLinkList createListR(void)char ch;LinkList head=/建立表头结点建