数据结构：数组与线性表.ppt

数据结构,数组与线性表,第二章 数组与线性表,数组,数组是由一些单元组成的，每个单元对应着一组下标值和一个数组元素。 n维数组的每个单元对应n个下标值。 数组元素可以是基本数据类型，如整型、实型、字符型等，也可以是有多个数据项的一种结构。 同一数组中各个元素必须是同一数据类型，每个数组元素都占有相同数量的存储单元，才能用下标来唯一的确定数组中的元素。,第二章 数组与线性表,数组的顺序存储结构,在计算机中，表示数组是采用一组连续的存储单元顺序地存储各数组元素。 可以用下标值随机的访问该数组的任意一个元素。 计算数组元素存储地址的公式称为寻址公式。 设数组为A，每个数组元素占s个存储单元，一旦定义了它的维数和各维的上、下界，就可以得到计算数组元素地址的寻址公式。,第二章 数组与线性表,1. 一维数组寻址公式,对于一维数组，若其下标的下界为LB，上界为UB，第一元素（其下标为LB）的地址为Loc(LB)，下标为i的数组元素Ai的地址为Loc(i)，则计算Loc(i)的寻址公式为： Loc(i)=Loc(LB)+(i-LB)*s 在C语言中，数组下标的下界为0，则数组中任意一元素Ai的寻址公式为： Loc(i)=Loc(0)+i*s 0in-1,第二章 数组与线性表,2. 二维数组寻址公式,在C语言中，采用矩阵元素以行为主存储，即同一行的元素连续存放，存储完一行再存储下一行。 设二维数组Amn，m、n分别表示数组的行和列，用Loc(i,j)表示数组元素Aij的地址，每个单元占用s个存储单元，则寻址公式为： Loc(i,j)=Loc(0,0)+(i*n+j)*s 0im-1, 0jn-1,第二章 数组与线性表,定义一A23数组，对应的矩阵如下： 数组元素A12，其下标i=1，j=2，故它前面已经有i=1行，每行有3个元素，另外本行有j=2个元素，所以在元素A12之前，本数组已有5个元素。,第二章 数组与线性表,已知数组A中，每个元素AIJ在存贮时要占3个字节，设I从1变化到8，J从1变化到10，分配内存时是从地址SA开始连续按行存贮分配的。试问：A58的起始地址为 ASA+141 B. SA+180 C. SA+222 D. SA+225,第二章 数组与线性表,在编程时（使用任一种高级语言，不一定是C），如果需要从磁盘文件中输入一个很大的二维数组（例如1000*1000的double型数组），按行读（即外层循环是关于行的）与按列读（即外层循环是关于列的）相比，在输入效率上 【 】 A. 没有区别 B. 按行读的方式要高一些 C. 按列读的方式要高一些 D. 取决于数组的存储方式。,第二章 数组与线性表,3. 三维数组寻址公式,三维数组Amnp可分解为p个m*n的二维数组。 按行为主存储的数组元素Aijk的寻址公式为： Locijk=Loc000+(i*n*p+j*p+k)*s 0im-1, 0jn-1，0pp-1 对于更多维的数组，数组元素在内存中的存储可以此类推。,第二章 数组与线性表,线性表（Linear List）,线性表是由有限数目的相同类型数据元素组成的序列。 表中的数据元素，除了第一个和最后一个以外，都有一个且只有一个前驱元素，同时也都有一个且只有一个后继元素； 第一个元素只有一个后继元素而无前驱元素；最后一个元素只有一个前驱元素而无后继元素。 线性表的元素个数n称为这个表的长度，当n=0时，这个表叫做空表。,第二章 数组与线性表,线性表在计算机内存中采用各元素顺序存储的方式。 如果已知线性表第一个元素的地址和每个元素占用的存储单元数，由任一元素的序号就可以计算出该元素在内存中的地址。 在编程时以一维数组表示线性表最简单，用的也最普遍。,第二章 数组与线性表,线性表的运算,对于给定的线性表，可进行如下的基本运算： 1. 求线性表的长度n； 2. 在第i个数据元素前面插入一个新的数据元素； 3. 删除第i个数据元素； 4. 存取或更新线性表第i个元素； 5. 将两个或两个以上的线性表合并成一个线性表； 6. 将一个线性表拆成多个线性表； 7. 将线性表中各数据元素按某个域值（如关键字）递增或递减的顺序重新排列； 8. 在线性表中查找满足某种条件的数据元素；,第二章 数组与线性表,1. 数据元素的插入(insert),设用一个一维数组An表示此线性表，原来有m个元素（mn），元素值已给定。 规定数组的下标从1开始，即这里数据元素对应的数组下标从1到n。 要求在第i个元素前插入一个新数据元素，值为G，因原线性表的数据元素是连续排列的，中间没有空单元，所以第i个元素及其后面的各元素均需向后移动一个单元位置，这样才能将G插入到i位置，且元素总数由m增加为（m+1）。,第二章 数组与线性表,插入函数,void insert(A, int n, m, i, G) int j; if (in+1) printf(“i值错！n”); else for (j=m;j=i;j-) Aj+1=Aj; /*将第i个元素及其后面的元素后移*/ Ai=G; m+; /*线性表长度加1*/ ,第二章 数组与线性表,插入函数分析,在循环语句中，当i=1时，须循环m次，表示元素插入线性表头的前面，则原线性表中m个元素均须向后移动一个单元，这是最不利的情况。 当i=m+1时，则循环一次也不进行，这时元素直接插入到线性表尾的后面，所以线性表的所有m个元素均不移动，这是最好的情况。,第二章 数组与线性表,2. 数据元素的删除(Delete),设用一个一维数组An表示此线性表，原来有n个元素，元素值已给定。 要求删除第i个数据元素，由于线性表元素在数组中必须连续排列，中间不能有空单元，故将此元素删除后，它后面的所有元素都需要向前移动一个单元，且数据元素总数由原来的n减少到n-1.,第二章 数组与线性表,删除函数,void delete(A,int n,i) int j; if (in) printf(“i值错！n”); else for (j=i;j=n;j+) Aj=Aj+1; n-; ,第二章 数组与线性表,删除函数分析,在循环语句中，当i=1时，需循环(n-1)次，这是要删除线性表表头元素，是最不利的情况； 当i=n时，则循环一次也不执行，只是将元素数目n比原来减少一个，而第n个数据元素不必再考虑，其余的各单元的元素均维持不变，这是最好的情况。,第二章 数组与线性表,3. 算法的时间复杂性,可以用数据元素的移动次数来度量这两个算法的时间复杂性。 插入时，最少循环0次，最多循环n次，如i的各种取值概率相同，则平均循环次数为n/2； 删除时最少的循环次数为0次，最多为n-1次，当i取值概率相同时，平均循环次数为(n-1)/2。 用数量级的形式表示线性表插入、删除运算的时间复杂性均为O(n)。,数据结构,链表,第三章 链表,链表,知 识 点 单链表的结点形式、组织方法和特点 单链表的基本运算和相应的算法 循环链表的组织方法和基本运算算法 双链表的结点形式、组织方法和特点 双链表的基本运算和相应的算法 顺序表与链表比较，各自的优、缺点 链表的应用 用十字链表表示稀疏矩阵,第三章 链表,难 点 双链表插入、删除运算的算法 利用链接结构的特点设计有效算法，解决与链表结构相关的应用问题 要 求 熟练掌握以下内容: 单链表的结构特点、基本运算并能设计简单算法 循环链表的结构特点、基本运算并能设计简单算法 双链表的结构特点、基本运算并能设计简单算法 了解以下内容： 用十字链表表示稀疏矩阵 链接堆栈，链接队列的应用以及一元多项式加法的应用实例,第三章 链表,第三章目录,3.1 单链表及其运算 3.2 循环链表与双向链表 3.3 链表应用举例 3.4 表示稀疏矩阵的十字链表 3.5 应用举例及分析 小 结 习题与练习,第三章 链表,3.1.1 单链表,1. 结点: 在链式存储结构中，结点不仅存放数据元素的值，还附加一个指针（链），用来指向该结点的直接后继结点。 其中，data部分称为数据域，用于存储线性表的一个元素，next部分称为指针域或链域，用于存放一个指针，即存放该结点的直接后继结点的地址。,第三章 链表,2. 单链表,所有结点通过指针的链接而构成的线性表称为单链表。线性表（a1，a2，an，）的单链表可直观地画成： head是单链表的头指针，指向开始结点a1, an是终端结点，其指针域为空，不指向任何结点。 一个单链表由头指针head唯一标识和确定，因此，可用头指针来命名单链表。,第三章 链表,单链表的特点,链表中每个结点只包含一个指针域。 整个链表的存取必须从头指针head开始进行，头指针表示链表中第一个结点的存储位置。,第三章 链表,3. 单链表的类型定义,假设线性表中数据元素的类型为datatype，单链表的类型定义如下： struct node datatype data; struct node * next; ListNode; typedef ListNode *linklist; 一个结点是由两个域data和next组成的记录,data是结点的数据域，next是结点的链域。,第三章 链表,4. 指针的概念,假设p是一个pointer类型，应正确区分指针型变量、指针、指针所指的结点和结点的内容这四个密切相关的不同概念： p的值（如果有的话）是一个指针，即是一个所指结点的地址 。 该指针（若不是NULL）指向的某个node型结点用*p来标识。 结点 *p是由两个域组成的记录，这两个域分别用pdata域和pnext域来标识，它们各有自己的值，pdata的值是一个数据元素，pnext的值是一个指针。,第三章 链表,3.1.2 单链表的基本运算,1. 遍历(Traversal)：根据已给的表头指针，按由前向后的次序访问单链表的各个结点。 在实际应用中遍历是对单链表的最基本运算，例如，当要打印或显示出各个结点的数值域值、计算单链表的长度(即结点数目)或寻找某一个结点时都需要遍历单链表。 假设head是单链表的头指针，计算一个已建立好的单链表的结点个数的算法如下：,第三章 链表,计算结点个数算法,int length(node *head) /*求表head的长度*/ int count=0; /*计数器置初值*/ node *p=head; /*p指向头结点*/ while (p!=NULL) p=p-next; count+; return(count); /*返回表长值*/ ,第三章 链表,算法分析,此算法的关键是while循环语句，开始时p指针指向头结点，每一循环都修改指针值，让它指向下一个结点，同时将计数链表长度的变量count加1。 这样每循环一次就向后推移一个结点，直到p所指结点*p的链域值为NULL为止。 空指针NULL起标志的作用，若无此标志，尾结点链域的值为“无定义”，上述算法中的while语句在做最后一次判断时将出现“运行错”，这是应予避免的。,第三章 链表,2. 插入,所谓插入是指在单链表中第i个结点(i0)之后插入一个元素为x的结点。 实现插入算法主要完成三个基本操作： 1) 在单链表上找到插入位置，即找到第i个结点。 可以用遍历的方法，即从表头起顺次访问单链表的结点，直至找到第i个结点。 2) 生成一个以x为值的新结点。 可通过C的库函数malloc(size)来产生。 3) 将新结点链入单链表中。 需要改变相关结点的指针 ，如下面的图所示。,第三章 链表,假设指针p指向单链表中的第i个结点，指针s指向已生成的新结点，链入新结点的操作如下： 将新结点*s的链域指向结点*p的后继结点 (即s-next=p-next)； 将结点*p的链域指向新结点(即p-next=s)。,第三章 链表,插入算法,void insert (node *head, int i, x) node *s,*p; int j; s=(node * )malloc(sizeof(node); /*生成新结点*/ s-data=x; if(i=0) /*如果i=0,则将s所指结点插入到表头*/ s-next=NULL; head=s; else p=head; j=1; /*查找第i个结点，由p所指向*/,第三章 链表,插入算法续,while( p!=NULL ,第三章 链表,3. 删除,当需要从单链表上删除结点时，就要通过删除运算来完成。 删除单链表上一个其值为x的结点的主要操作是： 1) 用遍历的方法在单链表上找到该结点； 2) 从单链表上删除该结点。 欲从单链表上删除一个结点，需修改该结点的前一个结点的指针，如下面的图所示。,第三章 链表,假设指针q指向待删除结点的前一个结点，指针p指向要删除的结点，删除该结点的操作如下：将该结点的前一个结点*q的链域指向*p的后继结点（即q-next=p-next）。,第三章 链表,删除算法,void delete(node *head, int x) node *p, *q; if (head=NULL) printf(“链表下溢！n”); /*判空*/ if(head-data=x) / *如表头结点值等于x*/ p=head; head=head-next; free(p); else q=head; /*从第二个结点开始查找*/ p=head-next;,第三章 链表,删除算法续,while(p!=NULL ,返回,第三章 链表,3.2.1 循环链表,循环链表（circular linked list）是一种首尾相接的链表，将单链表表尾结点原来的空指针改为指向表头结点，就成为循环链表。 循环链表并不多占存储单元，但从循环链表的任一个结点出发都可以访问到此链表的每一个结点，因为当访问到表尾结点后又能返回到头结点。,第三章 链表,1. 带头指针的循环链表,通常在循环链表的表头结点前面再加一个空结点,也叫空表头结点。 表空时空表头结点的指针指向其本身，如下面的图所示为空循环链表。 空表头结点除指针以外的数据域是没有用的，但为了将此结点与一般结点相区别，常常是将其赋以一个特别的数据，以与一般结点相区别。,第三章 链表,思考,在循环链表和单链表中，当需要从头到尾扫描整个链表时，如何判断已经到达表尾了？两者有什么差异？,第三章 链表,2. 带尾指针的循环链表,另一种方法是不设头指针而改设尾指针，这样无论是找头结点还是尾结点都很方便。因为尾结点由尾指针rear来指示，则头结点的位置是rear-next-next。,第三章 链表,3.2.2 双链表,双向链表中每个结点除了有向后指针外，还有指向其前一个结点的指针，这样形成的链表中有两条不同方向的链，因此从某一结点均可向两个方向访问。 双链表的结点形式为： 其中链域prior和next分别指向本结点的直接前趋和直接后继结点。,第三章 链表,如果循环链表的结点再采用双向指针，就成为双向循环链表。,第三章 链表,双链表较单链表虽然要多占用一些存储单元，但对其插入和删除操作以及查找结点的前趋和后继都非常方便。 双链表结构是一种对称结构，设指针p指向双链表的某一结点，则双链表的对称性可用下式来表示： p=(p-prior)-next=(p-next)-prior 即结点*p的地址既存放在其前趋结点 *(p-prior)的后继指针域中，又存放在它的后继结点*(p-next)的前趋指针域中。,第三章 链表,1. 双链表的插入,设要在p所指结点的前面插入一个新结点*q，则需要修改4个指针 ： q-prior=p-prior; q-next=p; (p-prior)-next=q; p-prior=q;,第三章 链表,2. 双链表的删除,设p指向待删除的结点，则删除该结点步骤为： (p-prior) -next=p-next; (p-next) -prior=p-prior; 这两个语句的执行顺序可以颠倒，执行这两个语句之后，可调用free(p),将*p结点释放。,返回,第三章 链表,例1,有一个单链表L(至少有一个结点)，其头结点指针为head，编写一个函数将L逆置，即最后一个结点变成第1个结点，原来倒数第二个结点变成第二个结点如此等等。 解：本题采用的算法是，从头到尾遍历单链表L，并设置3个附加指针p、q、r,p指向当前处理的结点，q指向p的下一个结点，r指向q的下一个结点，q、r的作用是为了防止倒置指针时，下一个结点的丢失而设置的，有了这三个指针，就可以方便地实现指针的倒置。最后将第一个结点的next域置为NULL，并将头指针指向最后一个结点，这样达到了本题的要求。,第三章 链表,例3.1算法,void invert(node *head) node *p,*q,*r; p=head; q=p-next; while(q!=NULL) /*没有后继时停止*/ r=q-next; q-next=p; p=q; q=r; head-next=NULL; head=p; ,第三章 链表,例2,有两个循环单链表，头指针分为head1和head2，编写函数将链表head2链接到链表head1之后，链接后的链表仍保持是循环链表的形式。 解：先分别找到两个链表的表尾，将head2放入链表head1的表尾，将两个链表链接起来，然后将head1放入原head2链表的表尾，构成新的循环链表。,第三章 链表,例3.2算法,link(node *head1,head2) node *p,*q; p=head1; while(p-next!=head1) p=p-next; q=head2; while(q-next!=head2) q=q-next; p-next=head2; q-next=head1; ,第三章 链表,例3,给出在双链表中第i个结点(i0)之后插入一个元素为x的结点的函数。 解：在前面双链表一节中，已经给出了在一个结点之前插入一个新结点的方法，在一个结点之后插入一个新结点的思想与前面是一样的。,第三章 链表,例3.3算法,void insert(dnode *head,int i,x) dnode *s,*p; int j; s=(dnode *)malloc(sizeof(dnode); /*建立一个待插入的结点，由s指向*/ s-data=x; if(i=0) /*如i=0,将s所指结点插入到表头后返回*/ s-next=head; head-prior=s; head=s; ,第三章 链表,例3.3算法续,else p=head; /*查找第i个结点，由p指向*/ j=1; while(p!=NULL if(p!=NULL) /*若查找成功，把s插入到p之后*/ if(p-next=NULL) /*若p是最后一个结点，则直接把s结点链入*/,第三章 链表,例3.3算法续, p-next=s; s-next=NULL; s-prior=p; else s-next=p-next;