数据结构与算法-线性表

2线性表2/49线性表主要知识点顺序表单链表循环单链表循环双向链表静态链表设计举例双链表3/49

唯一头元素

唯一尾元素

除头元素外，均有一个直接前驱

除尾元素外，均有一个直接后继线性结构特点:OOOOO线性头尾12

3

452.1线性表的概念4/49其中a1是头元素，an是尾元素，ai是第i个元素。ai-1是ai的直接前驱，ai是ai-1的直接后继。当2≤i≤n时，ai有且只有一个直接前驱。当1≤i≤n-1时，ai有且只有一个直接后继。线性表可以表示为n个数据元素的有限序列:(a1，…，ai-1，ai，…，an)2.1线性表的概念5/49线性表的存储顺序存储顺序表链式存储链表6/49用一组地址连续的存储单元依次存储线性表的数据元素。a1a2aian……bb+l…b+(i-1)l…b+(n-1)lb+nl存储地址内存状态设每个元素需占用l个存储单元LOC(ai)表示元素ai的存储地址则LOC(a1)是第一个数据元素a1的存储地址，也是整个线性表的起始地址LOC(ai+1)=LOC(ai)+lLOC(ai)=LOC(a1)+(i-

1)l2.2顺序表7/49算法2.1在第i

个数据元素之前插入一个新的元素思想:1.将第n

到i

个元素均向后移动一个位置。2.将新元素放置在第i

个位置。a1ai-1aian……例，在第i个元素前插入ba1ai-1aian……b8/49例，在第4个元素之前插入元素25。451293369512345657693325插入259/49算法时间复杂度:移动元素的个数取决于插入元素位置。i=1，需移动n个元素；i=i，需移动n–i+1个元素；i=n+1，需移动0个元素；10/49假设pi是在第

i个元素之前插入一个新元素的概率则长度为n

的线性表中插入一个元素所需移动元素次数的期望值为:Eis=∑

pi(n–i+1)n+1i=1设在任何位置插入元素等概率，pi=n+11Eis=∑(n–i+1)=n+11i=1n+12nO(n)11/49算法2.2删除第i

个数据元素思想:a1ai-1ai+1an……a1ai-1ai+1an……ai1.删除第i

个数据元素。2.将第i+1

到n

个元素均向前移动一个位置。12/49例，删除第4个元素25。删除2545129253369123456753369513/49算法时间复杂度:移动元素的个数取决于删除元素位置。i=1，需移动n-

1个元素；i=i，需移动n–i个元素；i=n，需移动0个元素；14/49假设qi是删除第

i个元素的概率则长度为n

的线性表中删除一个元素所需移动元素次数的期望值为:Edl=∑

qi

(n–i)ni=1设删除任何位置的元素等概率，qi=n1Edl=∑(n–i)=n1i=1n2n-

1O(n)15/49

顺序表中的其余操作都和数据元素个数n无关，因此，在顺序表中插入和删除一个数据元素的时间复杂度为O(n)，其余操作的时间复杂度都为O(1)。16/49

可随机存取表中任意数据元素，算法简单，空间单元利用率高；优点:

直接可获取线性表的长度例，L.elem[i-1]表示第i

个数据元素例，L.length表示线性表长度缺点:

数据元素的插入、删除相对麻烦，需要预先确定数据元素的最大个数，插入和删除时需要移动较多的数据元素。顺序表特点17/49线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素。存储单元可以是连续的，也可以是不连续的。2.3链表18/49结点:

两部分信息组成，存储数据元素信息的数据域，存储直接后继存储位置信息的指针域。datalink数据域，存放数据信息指针域，指向下一个数据单元2.3.1单链表19/49a1a2…0anHeadHead:

头指针，指向链表中第一个结点。0:

空指针，有时也表示为“NULL”或“∧”。头结点:

记录线性表的某些性质信息(如长度)。a1a2…0anHead2.3.1单链表20/49a1a2…0anHead单链表存储结构typedef

struct

LNode{ElemTypedata；struct

LNode

*next；}LNode

，*

LinkList

；空表:0Head21/49单链表特点缺点：不可随机存取表中任意数据元素不可直接获取线性表的长度优点：插入、删除方便22/49例，取第i=3个元素。ZhaoQian0LiLSunp=L->nextj=1p=p->nextj=2p=p->nextj=3e=p->data=Sun时间复杂度:O(n)23/49优点:数据元素的插入、删除相对方便在a，b之间插入元素x:abpxss->next=p->nextp->next=s24/49删除元素b:acpbq=p->nextp->next=p->next->next?

p->next=q->nextq=p->next

3）free(q)；25/4921350Lb0627La6789

Lcpapb,pcpapcpb

Lcpc

pbpa

Lcpcpa

pbLcpbpapcLc算法：

将两个有序单链表合并为一个有序单链表26/49算法：

将两个有序单链表合并为一个有序单链表pa=La->next；pb=Lb->next；//分别指向第一个结点pc->next=pa?pa:pb

；//处理剩余部分while(pa&&pb){if(pa->data<=pb->data){pc->next=pa；pc=pa；pa=pa->next；}else{pc->next=pb

；pc=pb

；pb=pb->next；}

}voidMergeList_L(LinkList&La，LinkList&Lb，LinkList&Lc){}Lc=pc=La；free(Lb)；思想:通过比较不断后移指针合并链表。27/49双向链表的结点有两个指针域:一个指向直接后继，一个指向直接前趋。priordatanext2.3.2双链表28/49双链表结点定义参考template<classT>classDLLNode{public:

DLLNode(){ next=prior=0; }

DLLNode(constT&el,DLLNode*n=0,DLLNode*p=0){data=el;next=n;prior=p;}Tdata;

DLLNode*next,*prior;};29/49双链表类定义参考template<classT>classDoublyLinkedList{public:

DoublyLinkedList(){head=newDLLNode<T>();}voidaddDLLNode(const

T&,i);voidclear(); ~DoublyLinkedList(){ clear(); }protected:

DLLNode<T>*head;};30/49性质:设d

是指向某个结点的指针，则有d->next->prior=d->prior->next=d操作:只涉及单向的操作基本相同，但插入、删除操作变化很大。ACHeadB^^空表:Head^^d31/491)插入ABXsp1.找到要在之前插入的结点，p记录。2.s->prior=p->prior；3.p->prior->next=s

；4.s->next=p

；5.p->prior=s

；32/492)删除ACB1.找到要删除的结点，p记录。p2.p->prior->next=p->next；3.p->next->prior=p->prior；4.free(p)；33/49表中最后一个节点的指针域指向头结点，形成一个环。a1…anHead0从表的任意结点出发均可以找到表中的其他结点。优点:2.3.3循环单链表tail空表:Headtail34/492.3.3循环双向链表ACHeadB空表:Head35/49☆静态链表在数组中增加一个(或两个)指针域用来存放下一个(或上一个)数据元素在数组中的下标，从而构成用数组构造的单链表。因为数组内存空间的申请方式是静态的，所以称为静态链表，增加的指针称做仿真指针。结构如下：ABCE∧headD(a)常规链表A1B2C3D4E-1┇(b)静态链表一datanext01234┇maxSize-1A2E-1B4D1C3┇(b)静态链表一datanext01234┇maxSize-136/49例题：一元多项式的表示及相加数学表示:

Pn(x)=p0+p1x+p2x2+…+pnxn计算机表示:P=(p0，p1，p2，…，pn

)可以描述为一个由n+1

个系数构成的线性表。多项式相加:设Pn(x):P=(p0，p1，p2，…，pn

)Qm(x):Q=(q0，q1，q2，…，qm

)m<n则Rn(x)=Pn(x)+Qm(x)R=(p0+q0，p1+q1，p2+q2，…，pm+qm，pm+1，…，pn

)显然，采用结构实现方便。顺序存储37/49+Rp0+q0p1+q1…pm+qmpm+1…pnq0q1qmQ…p0p1pmpn…P…38/49采用何种存储结构取决于需要实现的操作！P=((p1，e1

)，(p2，e2

)，…，(pm，em

)

)实现“求值”、“求项数”这样的操作，采用顺序存储结构。p1p2pm…e1e2em…39/49然而实际应用中，多项式的次数往往很高，且可能存在很多缺项。例，S(x)=1+3x10000+2x20000通常情况下，一元n次多项式写成:Pn(x)=p1x+p2x+…+pmxe1e2empi≠0

；0≤e1＜

e2

＜＜em

≤n…计算机表示:P=((p1，e1

)，(p2，e2

)，…，(pm，em

)

)?采用那种存储结构？40/49“多项式相加”等运算则采用链式存储结构nextcoefexpo系数指数下一个结点typedef

struct

LNode{ElemType

coef

；struct

LNode

*next；}LNode

，*

LinkList

；ElemTypeexpo；算法2.23多项式相加AddPolyn(&Pa，&Pb)要求:Pa=Pa+Pb41/49思想:依据归并两个有序表的过程，分三种情况考虑:令qa

和qb

分别指向多项式A和B中当前进行比较的结点；qa->expo

＜

qb->expo，qa所指向的结点应插入和多项式中qa->expo

＞

qb->expo，qb所指向的结点应插入和多项式中qa->expo

＝

qb->expo，求和

qa->coef+qb->coef和＝0，释放qa

和qb

所指结点；和≠0，修改qa

所指结点的系数值，释放qb

所指结点；qa-113520-2head1head2-13952740qb42/49qa=Pa->next；qb=Pb->next；case<://插入qa

结点case>://插入qb

结点case=://计算qa->coef+qb->coefswitch(cmp(qa->expo，qb->expo

)){}while(qa&&qb){}FreeNode(hb)；voidAddPolyn(polynomial&Pa，polynomial&Pb){}ha->next=qa?qa:qb

；//处理剩余部分ha=Pa；hb=Pb

；43/49case<:ha=qa

；qa=qa->next；break

；qaqb357haqaha44/49case>:hb->next=qb->next；qb=hb->next；ha=ha->next；break

；ha->nex