线性表双向链表和习题课课件

双向链表线性表(List)部分操作的实现小结和作业双向循环链表习题讲解复习一元多项式双向链表线性表(List)部分操作的实现小结和作业双向循环链复习-单链表a1a2a3LL逻辑形态空链表复习-单链表a1a2a3LL逻辑形态空链表复习-循环单链表a1a2a3L尾指针：a1a2a3L头指针：L复习-循环单链表a1a2a3L尾指针：a1a2a3L头指针：双向链表一、作用：方便定位一个结点的前驱结点和后继结点二、结点的形式ai三、C语言描述typedefstructDuLNode{ElemTypedata;

structDuLNode*prior;

structDuLNode*next;

}DuLNode；双向链表一、作用：方便定位一个结点的前驱结点和后继结点二、结双向链表五、逻辑形态四、头指针的描述typedefstructDuLNode*DuLinkList;La2a3a1L双向链表五、逻辑形态四、头指针的描述typedefstr部分操作的实现InitList(&L)ListInsert(&L,i,e)ListDelete(&L,i,&e)ListLength(L)部分操作的实现InitList(&L)ListInsert(InitListStatusInitList(DuListLink&L){node=(DuLNode*)malloc(sizeof(DuLNode));}return(OK);if(!node)return(ERROR);node->prior=node->next=NULL;L=node;LInitListStatusInitList(DuListListLength1、p指向头结点,j=02、如果p->next不为空，j++,p->next3、重复2，直到p->next为空，j即为长度。a2a3a1LListLength1、p指向头结点,j=02、如果p->ListLength(讨论)1、p指向头结点,j=02、如果p->prior不为空，j++,p->prior3、重复2，直到p->prior为空，j即为长度。a2a3a1LListLength(讨论)1、p指向头结点,j=02、如ListLengthintListLength(DuLinkListL){count=0;p=p->next;count++}}return(count);p=L;while(p->next){count=0;p=p->prior;count++}}return(count);p=L;while(p->prior){ListLengthintListLength(DuLinListInsert逻辑结构的变化<ai-1,ai>→<ai-1,e>,<e,ai>(a1,…,ai-1,ai,…,an)

→

(a1,…,ai-1,e,ai,…,an)存储结构的变化ListInsert逻辑结构的变化<ai-1,ai>ListInsertai-1aies->next=p->next;s->prior=p;

p->next=s;

s->next->prior=s;

psai-1aiListInsertai-1aies->next=p->ListInsert1、p指向头结点分析：2、执行p=p->nexti-1次，使得p指向第i-1个结点3、申请一个新结点s，调整s、第i-1和第i个结点的指针ListInsert1、p指向头结点分析：2、执行p=p->ListInsert找到第i-1个结点的代码是：p=L;j=0;while(j<i-1

){p=p->next;j++}ListInsert找到第i-1个结点的代码是：p=L;jListInsert生成一个新结点存放数据元素e的代码是：s=(DuLNode*)malloc(sizeof(DuLNode));if(!s)return(ERROR);s->data=e;ListInsert生成一个新结点存放数据元素e的代码是：ListInserts->next=p->next;s->prior=p;

p->next=s;

s->next->prior=s;

ListInserts->next=p->next;ListInsert(讨论)a2a3a1Less->next=p->next;s->prior=p;

p->next=s;

s->next->prior=s;

i=1?i=length+1???ListInsert(讨论)a2a3a1Less->nextListDelete(讨论)

(a1,…,ai-1,ai,ai+1,…,an)<ai-1,ai>,<ai,ai+1><ai-1,ai+1>(a1,…,ai-1,ai+1,…,an)逻辑结构的变化：存储结构的变化：ListDelete(讨论)(a1,…,ai-1,aListDelete(讨论)ai-1aiai+1p->next=p->next->next;p->next->prior=p;pai-1qq=p->next;ListDelete(讨论)ai-1aiai+1p->nexListDelete(讨论)1、p指向头结点q=p->next;p->next=p->next->next;

p->next->prior=p;

e=q->data;free(q);2、执行i-1次p=p->next，p指向了第i-1个结点3、q=p->next,q指向第i个结点4、修改第i-1个和第i个结点的指针5、释放结点qListDelete(讨论)1、p指向头结点q=p->nListDelete(讨论)a2a3a1Lp->next=p->next->next;p->next->prior=p;ai-1aiai+1pai-1i=1?i=length???ListDelete(讨论)a2a3a1Lp->next=双向循环链表1、每个结点的next域构成了一个循环单链表2、每个结点的prior域构成了另一个循环单链表逻辑形态La2a3a1L双向循环链表1、每个结点的next域构成了一个循环单链表2、双向循环链表-Insertai-1aiepsai-1ais->next=p->next;s->prior=p;

p->next=s;

s->next->prior=s;

a2a3a1L双向循环链表-Insertai-1aiepsai-1ais-双向循环链表-Deletep->next=p->next->next;p->next->prior=p;a2a3a1Lai-1pai-1aiai+1双向循环链表-Deletep->next=p->next线性表的应用---一元多项式p=(p0,p1,…，pn)但是对于形如:S(x)=1+3x10000–2x20000线性表的应用---一元多项式p=(p0,p1,…，p稀疏一元多项式

一般情况下的一元稀疏多项式可写成：

Pn(x)=p1xe1+p2xe2+…+pmxem其中：pi是指数为ei的项的非零系数，0≤e1<e2<┄<em=n可以下列线性表表示：((p1,e1),(p2,e2),…,(pm,em))稀疏一元多项式一般情况下的一元稀疏多项式可写成：可以下列稀疏一元多项式

P999(x)=7x3-2x12-8x999例如:((7,3),(-2,12),(-8,999))稀疏一元多项式P999(x)=7x3-2x12-稀疏一元多项式的实现typedefstruct{//项的表示

floatcoef;//系数

intexpn;//指数}

ElemType;typedefLinkListpolynomial;

//用带表头结点的有序链表表示多项式稀疏一元多项式的实现typedefstruct{一元多项式的操作AH=1-3x6+7x12BH=-x4+3x6-9x10+8x14-36712AH36-910814BH-1410

10CH-14-910712814

一元多项式的操作AH=1-3x6+7x12-3习题讲解-2.212.21逆置顺序表a1a2a3a4……an-3an-2an-1anL.elemL.lengthL.listsizeanan-1an-2an-3……a4a3a2a1L.elemL.lengthL.listsizea1

ana2an-1a3an-2ai

an-i+1i=1,…,length/2习题讲解-2.212.21逆置顺序表a1习题讲解-2.21voidreverse(SqList&l){if(L.length<=1)return;for(i=1;i<=L.length%2;i++){tmp=L.elem[i-1];L.elem[i-1]=L.elem[L.length-i];L.elem[L.length-i]=L.elem[i-1];}}ai

an-i+1i=1,…,length/2习题讲解-2.21voidreverse(SqList习题讲解-2.22(方法一)La1a2…an2.22逆置线性链表Lanan-1…a1习题讲解-2.22(方法一)La1a2…an2.22逆置线习题讲解-2.22(方法一)(a1,a2,…,ai-1,ai,ai+1,…,an-1,an)(an,an-1,…,ai+1,ai,ai-1,…,a2,a1)ai的前驱变成了后继，后继变成了前驱该问题的核心是要修改数据元素的邻里关系习题讲解-2.22(方法一)(a1,a2,…,ai-1习题讲解-2.22(方法一)1、p指向要修改指针的结点，初始时是a12、q指向p的后继？否则，修改p的指针，链就断了3、t指向p的前驱？在新表中t是p的后继4、p->next=t，t=p，p=q，q=p->next5、重复执行，直到q为空指针La1a2ptq6、L->next->next=NULL,L->next=p;习题讲解-2.22(方法一)1、p指向要修改指针的结点，初始习题讲解-2.22(方法一)1、如果表中只有一个结点，不处理2、如果表是空表，不处理LL习题讲解-2.22(方法一)1、如果表中只有一个结点，不处理习题讲解-2.22(方法一)voidreverse(LinList&L){if(!L->next||!L->next->next)return;//空表或单元素t=L,p=t->next,q=p->next;//t,p,q分别指向ai-1,ai,ai+1while(q){p->next=t;t=p,p=q,q=p->next;}L->next->next=NULL;L->next=p;}习题讲解-2.22(方法一)voidreverse(Lin习题讲解-2.22(方法二)a1a2a3

LLp

succa1

psucca2psucca3p习题讲解-2.22(方法二)a1a2a3LLpsucca习题讲解-2.22(方法二)voidreverse(LinkList&L){//逆置带头结点的单链表Lp=L->next;L->next=NULL;while(p){suc