线性表双向链表和习题课课件.ppt
《线性表双向链表和习题课课件.ppt》由会员分享,可在线阅读,更多相关《线性表双向链表和习题课课件.ppt(43页珍藏版)》请在三一办公上搜索。
1、双向链表,线性表(List),部分操作的实现,小结和作业,双向循环链表,习题讲解,复习,一元多项式,复习-单链表,逻辑形态,空链表,复习-循环单链表,尾指针:,头指针:,双向链表,一、作用:方便定位一个结点的前驱结点和后继结点,二、结点的形式,三、C语言描述,typedef struct DuLNode ElemType data;struct DuLNode*prior;struct DuLNode*next;DuLNode;,双向链表,五、逻辑形态,四、头指针的描述,typedef struct DuLNode*DuLinkList;,部分操作的实现,InitList(&L),ListIn
2、sert(&L,i,e),ListDelete(&L,i,&e),ListLength(L),InitList,Status InitList(DuListLink&L),node=(DuLNode*)malloc(sizeof(DuLNode);,return(OK);,if(!node)return(ERROR);,node-prior=node-next=NULL;,L=node;,ListLength,1、p指向头结点,j=0,2、如果p-next不为空,j+,p-next,3、重复2,直到 p-next为空,j即为长度。,ListLength(讨论),1、p指向头结点,j=0,2、如
3、果p-prior不为空,j+,p-prior,3、重复2,直到 p-prior为空,j即为长度。,ListLength,int ListLength(DuLinkList L),ListInsert,逻辑结构的变化,(a1,ai-1,ai,an)(a1,ai-1,e,ai,an),存储结构的变化,ListInsert,s-next=p-next;s-prior=p;p-next=s;s-next-prior=s;,p,s,ListInsert,1、p指向头结点,分析:,2、执行p=p-next i-1次,使得p指向第 i-1 个结点,3、申请一个新结点s,调整s、第i-1和第i个结点的指针,L
4、istInsert,找到第i-1个结点的代码是:,p=L;j=0;,while(ji-1),p=p-next;,j+,ListInsert,生成一个新结点存放数据元素e 的代码是:,s=(DuLNode*)malloc(sizeof(DuLNode);,if(!s)return(ERROR);,s-data=e;,ListInsert,s-next=p-next;s-prior=p;p-next=s;s-next-prior=s;,ListInsert(讨论),s,s-next=p-next;s-prior=p;p-next=s;s-next-prior=s;,i=1?i=length+1?,
5、ListDelete(讨论),(a1,ai-1,ai,ai+1,an),(a1,ai-1,ai+1,an),逻辑结构的变化:,存储结构的变化:,ListDelete(讨论),p-next=p-next-next;p-next-prior=p;,p,q,q=p-next;,ListDelete(讨论),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、释放结点q,Li
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 线性 双向 习题 课件
链接地址:https://www.31ppt.com/p-3732511.html