数据结构与算法 线性表

1、第2章 线性表,2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 线性表的应用示例,线性结构是最简单且最常用的一种数据结构。包括线性表、栈、队列、串。 线性结构具有下列特点： 存在一个唯一的没有前驱的（头）数据元素。 存在一个唯一的没有后继的（尾）数据元素。 此外，每一个数据元素均有一个直接前驱和一个直接后继数据元素。,线性结构,2.1 线性表的类型定义,线性表由一组具有相同属性的数据元素构成。 数据元素在不同的具体情况下，可以有不同的含义。 在一些复杂的线性表中，每一个数据元素又可以由若干个数据项组成，在这种情况下，通常将数据元素称为记录（re

2、cord）。,例如，职工工资表,每一个职工的工资是一个记录（数据元素）。,每个记录包含八个数据项。,如果n0，则除a0和an-1外，有且仅有一个直接前趋和一个直接后继数据元素。 如果n=0，则为一个空表，表示无数据元素。,一个线性表是n （n0 ）个数据元素a0，a1，a2，an-1的有限序列。,综上所述：,LinearList=(D,R) 其中，D= ai| aiElemSet,i=0,1,2, ，n-1 n1 R=| ai-1，aiD, i=1,2, ，n-1 Elemset为某一数据对象集；n为线性表的长度。,抽象数据类型线性表的定义如下：,ADT List 数据对象：D= ai| ai

3、ElemSet, i=1,2, ，n n0 数据关系：R=| ai-1，aiD, i=2, ，n 基本操作： InitList( 顺序表存储空间的总分配量 #define MAXSIZE 100 #define TRUE 1 #define FALSE 0 顺序存储类型 typedef struct ElemType dataMAXSIZE; /*存放线性表的数组*/ int length; /* length是顺序表的长度*/ SeqList;,1. 求顺序表长度,int ListLength(SeqList L) return(L.length); ,2. 检查顺序表是否为空,int Li

4、stEmpty(SeqList L) if(L.length) return(FALSE); else return(TRUE); ,3. 遍历顺序表,void ListTraverse(SeqList L) int i; if(L.length=0) printf(顺序表为空n); else printf(当前顺序表中的元素为:n); for(i=0;i=L.length-1;i+) printf(%d ,L.datai); printf(n); ,4. 从顺序表中查找元素,ElemType GetElem(SeqList L , int i) ElemType e; e=L.datai-1

5、; /第i个元素 return(e); ,5. 查找定位,/* 从顺序表中查找与给定元素值相同的元素在顺序表中的位置 */ int LocateElem(SeqList L, ElemType e) int i=0; while(iL.length ,6. 求顺序表中元素的前驱,ElemType PriorElem(SeqList L, ElemType e) int i=0; while(inext=NULL; return L; ,(只是建立一个空表，即一个头结点),（2）清空单链表,void LinkedListClear(LinkedList L) L-next=NULL; print

6、f(链表已经清空n); ,（3）检查单链表是否为空,int LinkedListEmpty(LinkedList L) if(L-next=NULL) return TRUE; else return FALSE; ,（4）遍历单链表,void LinkedListTraverse(LinkedList L) LinkedList p; p=L-next; if(p=NULL) printf(单链表为空表n); else printf(链表中的元素为:n); while(p!=NULL) printf(%d ,p-data); p=p-next; printf(n); ,（5）求单链表长度,i

7、nt LinkedListLength (LinkedList L) LinkedList p; int j; p=L-next; j=0; while(p!=NULL) j+;p=p-next; return j; ,（6）从链表中查找元素,LinkedList LinkedListGet(LinkedList L, int i) LinkedList p; int j; p=L-next; j=1; while (p!=NULL ,（7）从链表查找与给定元素值相同元素的位置,int LinkedListLocate ( LinkedList L, ElemType e) LinkedLis

8、t p; int j; p=L-next; j=1; while ( p!=NULL ,（8）向链表中插入元素,p=L; j=0; while(p ,算法：,算法演示： DSDemoWDSDemoW.exe,(9) 从链表中删除元素,(a)寻找第i个结点,P指向其前驱,(b)删除并释放第i个结点,p=L; j=0; while(p-next ,q=p-next; p-next=q-next; free(q);,算法演示： DSDemoWDSDemoW.exe,从线性链表的插入与删除算法中，可以看到要取链表中某个结点，必须从链表的头结点开始一个一个地向后查找，即不能直接存取线性链表中的某个结点。

9、 这是因为链式存储结构不是随机存储结构。 虽然在线性链表中插入或删除结点不需要移动别的数据元素，但算法寻找第i-1个或第i个结点的时间复杂度为O(n)。,比较插入算法与删除算法,循环单链表(Circular Linked List)是另一种形式的链式存储结构。是将单链表的表中最后一个结点指针指向链表的表头结点，整个链表形成一个环，这样从表中任一结点出发都可找到表中其他的结点。,2.3.2 循环单链表,（a）为带头结点的循环单链表的空表形式， （b）为带头结点的循环单链表的一般形式。,2.3.3 双向链表,1双向链表 在单链表的每个结点中只有一个指示后继的指针域，因此从任何一个结点都能通过指针域

10、找到它的后继结点； 若需找出该结点的前驱结点，则需从表头出发重新查找。 换句话说，在单链表中，查找某结点的后继结点的执行时间为O(1)，而查找其前驱结点的执行时间为O(n)。 可用双向链表来克服单链表的这种缺点，在双向链表中，每一个结点除了数据域外，还包含两个指针域，一个指针（next）指向该结点的后继结点，另一个指针（prior）指向它的前驱结点。 双向链表的结构可定义如下：,typedef struct node Elemtype data; struct node *prior, *next; dlnodetype;,和单链的循环表类似，双向链表也可以有循环表，让头结点的前驱指针指向链表

11、的最后的一个结点，让最后一个结点的后继指针指向头结点。,若p为指向双向链表中的某一个结点ai的指针，则显然有： p-next-prior=p-prior-next=p,p,（1）在双向链表中插入一个结点 在双向链表的第i个元素前插入一个结点时，可用指针p指该结点（称p结点）。 将新结点的prior指向p结点的前一个结点， 将p结点的前一个结点的next指向新结点， 将新结点的next指向p结点， 将p结点的prior指向新结点。,2双向链表的基本操作,在双向链表中，有些操作如：求长度、取元素、定位等，因仅需涉及一个方向的指针，故它们的算法与线性链表的操作相同； 在插入、删除时，需同时修改两个方

12、向上的指针，两者的操作的时间复杂度均为O(n)。,【算法2.18 双向链表的插入】 int insert_dl(dlnodetype *head, I nt i, Elemtype e) /*在带头结点的双向链表中第i个位置之前插入元素e*/ dlnodetype *p,*s; int j; j=0; p=head; while (p!=NULL ,在双向链表中删除一个结点时，可用指针p指向该结点（称p结点）。 将p结点的前一个结点的next指向p结点的下一个结点， 将p的下一个结点的prior指向p的上一个结点。,（2）在双向链表中删除一个结点,int Delete_dl(dlnodetyp

13、e *head, int i, ElemType ,【算法2.19 双向链表的删除】,链式存储结构的优点： （1）结点空间可以动态申请和释放； （2）数据元素的逻辑次序靠结点的指针来指示，不需要移动数据元素。 链式存储结构的缺点： （1）每个结点中的指针域需额外占用存储空间。 （2）链式存储结构是一种非随机存储结构。,2.4 线性表的应用示例,（一）一元多项式的表示和相加,在数学上，一个一元n次多项式可表示为 Pn(x)=p0+p1x+p2x2+pnxn 它由(n+1)个系数序列p0、p1、pn 唯一地确定。因此，在计算机中，它可用一个线性表P来表示： P=(p0, p1, ,pn) 其中，p

14、i代表Pn(x)中的i次项系数。 在这种表示法中，系数所对应的指数隐含在系数的序号中，所以值为0的系数也要列出。 现考虑两多项式进行符号相加的问题。 设Qm(x)是另一个一元m次多项式，它的线性表表示为 Q=(q0, q1, , qm),为解决0系数问题，可以不存贮0值元素。但这样就不能利用位置关系隐含指出系数对应的指数了，而必须显式地给出指数。 对任一个一元n次多项式，若不写出系数为0的项，则可表示为 pn(x) = p1xe1+p2xe2+ +pnxen 这里，p1, p2, , pn均非0，e1e2 =0 TermSet中的每个元素包含一个表示系数的实数和表示指数的整数 数据关系：R1=

15、|ai-1,ai D,且ai-1中的指数值 ai中的指数值 基本操作： CreatPolyn( int expn; typedef LinkList polynomial; /用带表头结点的有序链表表示多项式 void CreatPolyn(polynomail ,多项式相加示例,void AddPolyn(polynomial /switch, /while if(!ListEmpty(Pb) Append(Pa,qb); FreeNode(hb); /AddPolyn,作业： 1、假设有两个按元素值递增有序排列的线性表A、B，同一个表中的元素值各不相同，现要求另辟空间构成一个线性表C，其元素为A和B中元素的交集，且表C中的元素也依值递增有序排列。试对顺序表编写求C的算法。 2、设线性表中数据元素的总数基本不变，并很少进行插入或删除工作，若要以最快的速度存取线性表中的数据元素，应选择线性表的何种存储结构？为什么? 3、顺序表和链表在进行插入操作时，有什么不同？ 4、写出在