《计算机应用基础课件》1.2线性表.ppt

,第 1 章 数据结构,1.1 基本数据结构与算法 1.2 线性表 1.3 栈和队列1.4 树和二叉树 1.5 查找1.6 内部排序,姓名 学号 成绩 班级 李红 9761059 95 机97.6,10,65,865,1.2 线性表,1.线性表的定义1)定义：具有相同数据类型的n(n0)个数据元素组成的有限序列。是最简单、最常用的数据结构。2)表示:,L=(a0，a2，a3，ai-1，ai，ai+1，,.,an-1),其中:n为线性表长度(n=0称为空表)，表中相邻元素之间存在着顺序关系。a0：表头元素；an-1：表尾元素；ai-1称为ai的直接前驱；ai+1 称为ai的直接后继。,表头,表尾,1.2 线性表,1.线性表的定义1)定义：具有相同数据类型的n(n0)个数据元素组成的有限序列。是最简单、最常用的数据结构。2)表示:,L=(a0，a2，a3，ai-1，ai，ai+1，.,an-1),3)线性结构特点:,(1)有且只有一个根结点a0，无前驱。(2)有且只有一个终端结点an-1，无后继。(3)其他结点有且只有一个直接前驱和一个直接后继。,1.2 线性表,1.线性表的定义1)定义：具有相同数据类型的n(n0)个数据元素组成的有限序列。是最简单、最常用的数据结构。2)表示:,3)线性结构特点:,4)线性表的分类(1)简单线性表：数据元素是简单项(数字、字母、季节名等)。如:(12,34,4,67,8)(2)复杂线性表：数据元素由若干个数据项组成，此时数据元素称为记录或结点,如学生成绩表.,L=(a0，a2，a3，ai-1，ai，ai+1，.,an-1),学生健康情况登记表如下：,1.顺序表基本概念,1.2.2 线性表的顺序存储结构,1)顺序存储结构：用一组地址连续的存储空间依次存放线性表的各元素。,顺序表：采用顺序存储结构的线性表称为顺序表(一维数组),表中的所有元素所占存储空间连续表中各元素在存储空间中按逻辑顺序存放,顺序存储结构特点,1.2 线性表,1.顺序表基本概念,4.2.2 线性表的顺序存储结构,1)顺序存储结构：,2)第i个元素地址,4.2 线性表,其中:m：每个元素占m个存储单元Loc(a0)第一个元素地址(基址),b,b+m,b+i*m,b+n*m,存储地址,存储状态,空闲,数据元素在线性表中的位序,12,n,i,从存取方式看,线性表的顺序存储结构是可以随机存储的存储结构.,1.顺序表基本概念,1.2.2 线性表的顺序存储结构,1)顺序存储结构：,2)第i个元素地址,1.2 线性表,2.顺序表的基本运算 存取:访问线性表的第i个元素，使用或改变数据元素的值。查找:在线性表中查找满足某种条件的数据元素。插入:在线性表的第i个元素之前，插入一个同类型的元素。(*)删除:删除线性表中第i个元素。(*)求表长:求出线性表中元素的个数。置空表:建立一个空表。清除表:将已有线性表变为空表，即删除表中所有元素。,1.顺序表基本概念,1.2.2 线性表的顺序存储结构,1)顺序存储结构：,2)第i个元素地址,1.2 线性表,2.顺序表的基本运算,插入和删除,1)顺序表的插入运算:在线性表的第i个元素之前插入一个新的元素，先移动，后插入。,x,ai,先移动后插入,x,步骤：,(1)将ai an顺序向后移动,为新元素让出位置(2)将x置入”空出”的第i个位置,举例：(在第4个和第5个元素之间插入元素91),21,91,插入程序举例(在8个数中任意位置插入一个数)：#define N 8main()int aN+1=12,34,45,6,78,9,10,91,i,j,x;printf(“input the location to be inserted:”);scanf(“%d,%d”,for(j=i-1;j=N-1;j+)aj+1=aj;,for(j=N-1;j=i-1;j-)aj+1=aj;,在第i个位置上作插入x,则需将第i个至第n个元素移动，即共需移动(n-i+1)个元素。,插入运算时间性能分析：,插入运算，时间主要消耗在数据移动上。在长度为n的线性表中插入一个元素，则平均移动元素次数(期望值)：,pi：在第i个位置上作插入的概率。,等差数列求和公式:(首项+末项)项数)/2,(n-i+1),线性表(a0,a1,a2)平局移动元素个数:()*(3+2+1+0)=1.5,在一线性表(a0,a1,a2)中插入任意一数i，求平局移动元素次数:,i 移动次数(n-i+1)1(插入到第个数a0前)3 2(插入到第2个数a1前)23(插入到第3个数a2前)1(插入到第3个数a2后)0,1.顺序表基本概念,1.2.2 线性表的顺序存储结构,1)顺序存储结构：,2)第i个元素地址,1.2 线性表,2.顺序表的基本运算,插入和删除,2)顺序表删除运算：,定义：指将表中第i个元素从线性表中去掉。,原表长为n：(a0，a1，ai-1，ai，ai+1，an-1),新表长为n-1：(a0，a1，ai-1，ai+1，an-1),步骤：,(1)将ai+1 an-1，顺序向前移动(2)表长减一,举例：(删除第五个元素21),时间性能分析：,时间消耗与插入运算相同，平均移动元素次数：,qi:在第i个位置上作插入的概率。设qi=1/n 共需移动(n-i)个元素。,67,i 移动次数(n-i)1(删除第1个数a0)22(删除第2个数a1)13(删除第3个数a2)0,线性表(a0,a1,a2)平局移动元素个数:(1/3)*(2+1+0)=1,在一线性表(a0,a1,a2)中删除任意一数i，求平局移动元素次数:,作业：有一数组，存储十个数，编程序删除其中任意一个数。,1.顺序表基本概念,3.顺序表优点和缺点,优点：,逻辑上相邻元素存储位置也相邻,无需增加额外存储空间可方便随机存取表中任一元素。,缺点：,插入和删除运算不方便,必须移动大量结点,效率较低不适合元素经常变动的大的线性表。,1.2.2 线性表的顺序存储结构,1.2 线性表,2.顺序表的基本运算,链式存储结构特点:,1.2.3 线性表的链式存储结构,存储空间可以不连续。不要求逻辑上相邻的元素在物理位置上也相邻。数据元素间逻辑关系由指针域确定。,1.2 线性表,即 链表存储结构是一种动态数据结构，其特点是它包含的据对象的个数及其相互关系可以按需要改变，存储空间是程序根据需要在程序运行过程中向系统申请获得，链表也不要求逻辑上相邻的元素在物理位置上也相邻，它没有顺序存储结构所具有的弱点。,name,sum,next,结构体元素,结构体元素的地址,结构体元素的成员是地址型数据,struct student char name10;int sum;struct student*next;,p,struct student*p;,strcpy(p-name,”zhang”)；p-sum=335;p-next=?,head,p1,p2,p3,有四个结构体元素：,head,有四个结构体元素：,head,（3）尾结点的指针域置为“NULL（空）”，作为链表结束的标志,（1）头指针变量head指向链表的首结点。,（2）每个结点由2个域组成：1）数据域存储结点本身的信息。2）指针域指向后继结点的指针。,struct student char name10;int sum;struct student*next;,链式存储结构特点:,2.线性链表:定义：线性表的链式存储结构称为线性链表,1.2.3 线性表的链式存储结构,数据域:一部分存放数据元素值 指针域:存放指针,用于指向该结点的 前一个结点或后一个结点,线性链表中结点组成：,分类：单链表、循环单链表、双向链表,1.2 线性表,其单链表示意图如下：,有一线性表:(bat，cat，eat，fat，hat，jat，lat，mat),110 130 135 160头指针 head 165 170 200 205,简化为：,链尾,略,单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。,例如：若头指针名是head，则把链表称为表head。,head,用C语言描述的单链表如下：,struct node char name20;struct node*next;struct node*head;,typedef struct node char name20;struct node*next;LinkList;LinkList*head;,新的类型名代换旧的类型名，也就是说：LinkList等价与struct node,链式存储结构特点:,2.线性链表:,1.2.3 线性表的链式存储结构,1.2 线性表,3.单链表:定义：由n个结点链接，且每个结点中只包含一个指针域的链表。,例：线性单链表(A,B,C,D,E,F),逻辑状态,其中:head称为单链表的头指针,指向表中的第一个结点,物理状态,头指针 存储地址 数据域 指针域,1713192531,单链表存取:必须从头指针开始进行，依次顺着指针向链尾方向扫描。找到各个元素,因此说线性表的链式存储结构是一种顺序存储的存储结构。,head,head,head,带头节点的单链表,编程：创建带头节点的单链表。,程序算法：（1）定义三个结构体类型的指针变量head,p,s（2）利用malloc函数开辟头结点，由head,p共同来指向（3）再利用malloc函数开辟相应的内存空间，由s来指向（4）由键盘输入数据，赋给s所指向的内存空间（5）p-next=s;（6）p=s;（7）回到第（3）步;,程序算法：（1）定义三个结构体类型的指针变量head,p,s（2）利用malloc函数开辟头结点，由head,p共同来指向（3）再利用malloc函数开辟相应的内存空间，由s来指向（4）由键盘输入数据，赋给s所指向的内存空间（5）p-next=s;（6）p=s;（7）回到第（3）步;,head=p=(strutc node*)malloc(sizeof(struct node);,head,p,对带头结点的复杂链表的基本操作创建,程序算法：（1）定义三个结构体类型的指针变量head,p,s（2）利用malloc函数开辟头结点，由head,p共同来指向（3）再利用malloc函数开辟相应的内存空间，由s来指向（4）由键盘输入数据，赋给s所指向的内存空间（5）p-next=s;（6）p=s;（7）回到第（3）步;,A,s-data=getchar();,s,p,对带头结点的复杂链表的基本操作创建,head,p,程序算法：（1）定义三个结构体类型的指针变量head,p,s（2）利用malloc函数开辟头结点，由head,p共同来指向（3）再利用malloc函数开辟相应的内存空间，由s来指向（4）由键盘输入数据，赋给s所指向的内存空间（5）p-next=s;（6）p=s;（7）回到第（3）步;,s,p,对带头结点的复杂链表的基本操作创建,A,s,head,p,B,head,head,带头节点的单链表,typedef struct nodechar data;struct node*next;Linklist;Linklist*head,*p,*s;char ch;head=(Linklist*)malloc(sizeof(Linklist);printf(input letters to create a list:n);while(ch=getchar()!=n)s=(Linklist*)malloc(sizeof(Linklist);s-data=ch;p-next=s;p=s;p-next=NULL;,编程：创建带头节点的单链表。,带头节点的单链表,typedef struct nodechar data;struct node*next;Linklist;Linklist*head,*p,*s;char ch;head=(Linklist*)malloc(sizeof(Linklist);printf(input letters to create a list:n);p=head;while(ch=getchar()!=n)s=(Linklist*)malloc(sizeof(Linklist);s-data=ch;p-next=s;p=s;p-next=NULL;,2000,B,data,next,struct nodechar data;struct node*next;Linklist;Linklist*head,*p,*s;char ch;head=(Linklist*)malloc(sizeof(Linklist);printf(input letters to create a list:n);p=head;while(ch=getchar()!=n)s=(Linklist*)malloc(sizeof(Linklist);s-data=ch;p-next=s;p=s;p-next=NULL;,A,head,p,用户输入为：ABC,s,p,typedef,struct nodechar data;struct node*next;Linklist;Linklist*head,*p,*s;char ch;head=(Linklist*)malloc(sizeof(Linklist);printf(input letters to create a list:n);p=head;while(ch=getchar()!=n)s=(Linklist*)malloc(sizeof(Linklist);s-data=ch;p-next=s;p=s;p-next=NULL;,A,head,用户输入为：ABC,s,p,s,B,p,typedef,struct nodechar data;struct node*next;Linklist;Linklist*head,*p,*s;char ch;head=(Linklist*)malloc(sizeof(Linklist);printf(input letters to create a list:n);p=head;while(ch=getchar()!=n)s=(Linklist*)malloc(sizeof(Linklist);s-data=ch;p-next=s;p=s;p-next=NULL;,A,head,用户输入为：ABC,s,B,p,s,C,p,NULL,typedef,链式存储结构特点:,2.线性链表:,1.2.3 线性表的链式存储结构,1.2 线性表,3.单链表:,(1)单链表插入：增加新结点,修改链接指针,后插结点,在指针p所指结点之后插入一个指针s所指的结点修改p和s所指结点的指针域的指针即可,插入步骤,修改s指针域,使其指向p结点的后继结点:snext=pnext,p,B,X,s,修改p指针域,使其指向新结点s:pnexts,考虑上述两步骤若颠倒会怎样？,插入步骤,修改s指针域,使其指向p结点的后继结点:snext=pnext,p,B,X,s,修改p指针域,使其指向新结点s:pnexts,考虑上述两步骤若颠倒会怎样？,后面的结点都将从链表中脱离,它们占用着内存空间，程序却找不到它们了,链式存储结构特点:,2.线性链表:,1.2.3 线性表的链式存储结构,1.2 线性表,3.单链表:,(2)单链表删除：不需要移动元素,仅修改指针链接,删除结点,删除p指向的结点只修改p(被删除结点)的前驱结点的指针域即可,删除步骤,修改q结点指针域 qnextpnext,删除后,q,p,free(p);,先找到p的前驱结点q,qnextqnextnext,链式存储结构特点:,2.线性链表:,1.2.3 线性表的链式存储结构,1.2 线性表,3.单链表:,4.循环链表,特点：表中最后一个结点的指针域指向头结点，整个链表首尾相连形成一个环。,带头节点的循环链表,优点：从表中任一结点出发均可找到表中其它结点。,对带头结点的单循环链表head为空的判定条件是 head-next=head,带头结点的空循环链表,链式存储结构特点:,2.线性链表:,1.2.3 线性表的链式存储结构,1.2 线性表,3.单链表:,4.循环链表,5.双向链表,定义：在双向链表中，每个结点有两个指针域，next 指向后继结点，prior指向前趋结点。,作用：可以方便地沿向前或向后两个方向查找。克服单链表中每个结点只能找到它的后继结点，不能找到前驱结点。若要找前驱结点，必须从头指针开始重新查找的不足。,next,prior,对指向双向链表任一结点的指针p，有下面的关系：p-next-priou=p-priou-next=p,p,next,prious,prious,next,链式存储结构特点:,2.线性链表:,1.2.3 线性表的链式存储结构,1.2 线性表,3.单链表:,4.循环链表,5.双向链表,(1)插入结点：在p指针所指的结点后插入一个结点q，只需要修改p,q结点的prior和next域即可。,p,c,b,a,x,q,p,p结点作为q结点的前驱:q-prior=p；,p结点的后继作为q结点的后继:q-next=p-next；,q结点作为p 结点的后继结点的前驱结点:p-next-prior=q,q结点作为p结点的后继:p-next=q；(p的后继指向新结点q),确定新结点q的前驱和后继,链式存储结构特点:,2.线性链表:,1.2.3 线性表的链式存储结构,1.2 线性表,3.单链表:,4.循环链表,5.双向链表,p,(2)删除结点：删除P指针所指结点，只需修改P指针的前驱和后继结点的next，prior域即可。,p,p-prior-next=p-next；,p-next-prior=p-prior；,free(p)；,c,b,a,习题讲解,1.线性表的顺序存储结构和线性表的链式存储结构分别是_。A.顺序存取的存储结构、顺序存取的存储结构 B.随机存取的存储结构、顺序存取的存储结构 C.随机存取的存储结构、随机存取的存储结构 D.任意存取的存储结构、任意存取的存储结构2.在单链表中，增加头结点的目的是_。A.方便运算的实现 B.使单链表至少有一个结点 C.标识表结点中首结点的位置 D.说明单链表是线性表的链式存储实现,3 用链表表示线性表的优点是_。A.便于插入和删除操作 B.数据元素的物理顺序与逻辑顺序相同 C.花费的存储空间较顺序存储少 D.便于随机存取4.某线性表采用顺序存储结构,每个元素占4个存储单元,首地址为200,则第12个元素的存储地址是_.A.248 B.247 C.246 D.244,5.下列对于线性链表的描述中正确的是_。(05.4月）A）存储空间不一定是连续，且各元素的存储顺序是任意的B）存储空间不一定是连续，且前件元素一定存储在后件元素的前面C）存储空间必须连续，且前件元素一定存储在后件元素的前面D）存储空间必须连续，且各元素的存储顺序是任意的,6.线性表是（）A.一个有限序列，可以为空 B.一个有限序列，不能为空 C.一个无限序列，可以为空 D.一个无限序列，不能为空,7在一个长度为n的线性表中，删除值为x的元素时需要比较元 素和移动元素的总次数为（）A.（n+1）/2 B.n/2 C.n D.n+1,详见计算机基础综合实训教程P175,8.一个长度为n的顺序存储的线性表中，向第i个元素(1in+1)位置插入一个新元素时，需要从后面向前依次后移（）个元 素。A.n-i B.n-i+1 C.n-i-1 D.i,9.设单链表中指针p指向结点ai,若要删除ai之后的结点（若存 在），则需修改指针的操作为（）。A.p-next=p-next-next B.p=p-next C.p=p-next-next D.next=p,10.设单链表中指针p指向结点ai,指针q指向将要插入的新结点 x，则当x插在链表中两个数据元素ai和ai+1之间时，只要先 修改 q-next=p-next，后修改（）即可。A.p-next=q B.p-next=p-next-next C.p-next=q-next D.q-next=null,11.在一个单链表中，若要在p所指向的结点之后插入一个新结 点，则需要相继修改（）个指针域的值。A.1 B.2 C.3 D.4,12.不带头结点的单链表L为空的判定条件是（）。A.L=NULL B.L-next=NULL C.L-next=L D.L!=NULL13带头结点的单链表L为空的判定条件是（）。A.L=NULL B.L-next=NULL C.L-next=L D.L!=NULL14.在一个带有头结点的双向循环链表中，若要在p所指向的结点之前插入一个新结点，则需要相继修改（）个指针域的值。A.2 B.3 C.4 D.615.在一个带有头结点的双向循环链表中，若要在p所指向的结点之后插入一个q指针所指向的结点，则需要对q-next赋值为（）A.p-prior B.p-next C.p-next-next D.p-prior-prior16.线性表采用链式存储时，其地址（）A.必须是连续的B.一定是不连续的C.部分地址必须是连续的D.连续与否均可以,2.在一个单链表中删除指针p所指向结点时，应执行一下操作：q=p-next;p-data=p-next-data;p-next=_；free(q);,填空题 1.数据结构分为逻辑结构和存储结构，循环队列属 于 结构。（05.9月）,存储结构,p-next-next,p,q,B,C,3.在一个单链表中指针p所指向结点的后面插入一个指针q所指向的结点时，首先把_ _的值赋给q-next，然后把_的值赋给p-next。,p-next,q,4.假定指向单链表中第一个结点的表头指针为head，则向该单链 表的表头插入指针p所指向的新结点时，首先执行_赋值操 作，然后执行_赋值操作。,p-next=head,head=p,head,p,5.在一个单链表中删除指针p所指向结点的后继结点时，需要把_的值赋给p-next指针域。,p-next-next,6.在_链表中，既可以通过设定一个头指针也可 以通过设定一个尾指针来确定它，即通过头指针或 尾指针可以访问到该链表中的每个结点。,循环,7.在一个带有头结点的双向循环链表中的p所指向的结 点之前插入一个指针s所指向结点时,可执行如下操作：(1)s-prior=_；(2)p-prior-next=s;(3)s-next=_;(4)p-prior=_;,p-prior,p,s,8.线性表的长度是指_。,线性表中包含数据元素的个数,9.根据线性表的链式存储结构中每个结点所含指针的个数，链表可分为_和_。,单链表、双链表,10.循环单链表与非循环单链表的主要不同是循环单链表的尾结 点指针_，而非循环单链表的尾结点指针_。,指向链表头节点,指向空,11.访问单链表中的结点，必须沿着_依次进行。,指针域,12.在双向链表中，每个结点有两个指针域，一个指向_，另一个指向_。,前驱节点,后续节点,13.在一个双向链表中删除指针p所指向的结点时，需要对 p-next-prior指针域赋值为_。,p-prior,14.设head为单循环链表L的头结点，则L为空表的条件是_。,head-next=head,15.假设以S和X分别表示进栈和退栈操作，则对输入序列a,b,c,d,e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列是 _。,bceda,16.在一个长度为n的顺序表中的删除第i个元素（0in-1），需 要向前移动_个元素。,n-i,17.线性表L=(a1,a2,an)用数组表示，假定删除表中任一元素的 概率相同，则删除一个元素平均需要移动元素的个数是。,(n-1)/2,18.一含N个元素的顺序表，若在第i个元素之前插入一个元素，需移动 个元素。,n-i+1,19.从链表种删除q结点之后的p结点，语句为：q-next=。,p-next,20.链表中每个结点包含两部分内容，一部分为数据域，另一部 分为 域。,指针,21.在单链表中，要删除某一指定的结点，必须找到该结点的 _。,前驱,假定建立了以下链表结构，指针p、q分别指向如图所示的结点，则以下可以将q所指结点从链表中删除并释放该结点的语句组是 A)free(q);p-next=q-next;B)(*p).next=(*q).next;free(q);C)q=(*q).next;(*p).next=q;free(q);D)q=q-next;p-next=q;p=p-next;free(p);,练1,练2,若已建立如下图所示的单向链表结构,在该链表结构中，指针p、s分别指向图中所示结点，则不能将s所指的结点插入到链表末尾仍构成单向链表的语句组是 A)p=p-next;s-next=p;p-next=s;B)p=p-next;s-next=p-next;p-next=s;C)s-next=NULL;p=p-next;p-next=s;D)p=(*p).next;(*s).next=(*p).next;(*p).next=s;,