数据结构之链表.ppt
《数据结构之链表.ppt》由会员分享,可在线阅读,更多相关《数据结构之链表.ppt(40页珍藏版)》请在课桌文档上搜索。
1、SCIE,University of Electronic Science and Technology of China,1,2.1线性表,线性表不同的实现方式:2.1.1顺序表 数组存储 顺序表定义 顺序表基本操作:遍历、插入、删除 顺序表算法分析2.1.2单链表2.1.3双向链表 链接存储2.1.4循环链表,SCIE,University of Electronic Science and Technology of China,2,2.1线性表,#include stdio.h“struct list_seq int data20;int length;int main()struct
2、 list_seq list;int no,i;list.length=0;for(i=0;i10;i+)scanf(%d,SCIE,University of Electronic Science and Technology of China,3,2.1.2单链表,一、链表的引入数组结构的缺点:1、在插入、删除时要移动大量的节点2、表的大小固定。预先在申明数组时指定,无法更改原因:存放的连续性突破离散存放用指针来表示元素之间的关系。,SCIE,University of Electronic Science and Technology of China,4,2.1.2单链表,用链表实现线
3、性表(非连续存储),线性表元素:a1、a2、a3、a4.,链表链点,线性关系:,a1,a2,a3,a4,指针域,指针关系,a1,a2,a3,a4,顺序存储,链式存储,SCIE,University of Electronic Science and Technology of China,5,2.1.2单链表,二、链表的定义 链点,元素域,链接域,数据域(数据元素域):存放一个数据元素。链接域(关系域):存放指向下一个元素的指针元素间的关系。,数据域+链接域=结点(链点),SCIE,University of Electronic Science and Technology of China
4、,6,2.1.2单链表,链表,由链点及链点相互间的链接构成,head,链表头,链表尾,链表长度(节点数目),SCIE,University of Electronic Science and Technology of China,7,2.1.2单链表,定义,struct node_typeelemtype data;struct node_type*next;,struct list_typenode_type*head;node_type*tail;int length;,链点的定义,链表的定义,data,next,8,2.1.2单链表,SCIE,University of Electro
5、nic Science and Technology of China,8,带头节点的单链表,head,带头节点链表的引入是为了使算法对空表和非空表的处理一致,普通单链表对链表尾的判断(假定p是链表尾的指针)空表:p=null;非空表:p-next=null;,带头节点单链表对链表尾的判断空表:p-next=null;非空表:p-next=null;,SCIE,University of Electronic Science and Technology of China,9,2.1.2单链表,初始化算法:elemtype initlist(node*h)*h=(node*)malloc(si
6、zeof(node);(*h)-next=null;三、链表的基本操作访问插入删除,SCIE,University of Electronic Science and Technology of China,10,2.1.2单链表,访问操作问题描述:访问链表的第i个节点问题分析:输入:链表,i输出:链点指向链点的指针算法实现分析:,只能从链表头开始,一个一个“数”下去,直到第i个。,a1,an,head,a2,temp,temp,temp,SCIE,University of Electronic Science and Technology of China,11,2.1.2单链表,从自然语
7、言到算法语言,如何描述我们找到第i个节点的动作。1、先找到链表首结点的地址2、通过“地址”,找到链点3、在链点中找到后继元素的“地址”4、记录这个地址,p=list-head;,p-data,p=p-next;,p-next,SCIE,University of Electronic Science and Technology of China,12,2.1.2单链表,继续完善描述1、先找到链表首结点的地址2、通过“地址”,找到链点3、在链点中找到后继元素的“地址”4、记录这个地址,回到2,p=list-head;,p-data,p=p-next;,p-next,计数,如果计数到i,就结束,
8、counter=1;,counter+;,if(counter=i),break;,SCIE,University of Electronic Science and Technology of China,13,2.1.2单链表,node_type*get_node(list,i),while(counter next;,int counter;node_type*p;,return p;,if(p=NULL)return NULL;,p=list-head;counter=1;,p,逐个“数”的动作,counter:,1,2,3,设i 3,当in时算法结果怎样?,思考,SCIE,Unive
9、rsity of Electronic Science and Technology of China,14,2.1.2单链表,注意,1、p=p-next;,沿链表前进,2、循环结束条件,counter=i 或 node=NULL,counter list-length,思考,如果希望获得值为x的元素,如何实现?,while(p-data=x&p!=NULL),SCIE,University of Electronic Science and Technology of China,15,2.1.2单链表,链表插入操作问题描述:在元素ai前插入新的元素new_node;问题分析:输入:链表,l
10、ocation,x输出:插入新元素后的链表。算法实现分析,SCIE,University of Electronic Science and Technology of China,16,2.1.2单链表,a1,ai,an,head,ai-1,.,.,anew,SCIE,University of Electronic Science and Technology of China,17,2.1.2单链表,void insertl(list,new_node,location),找到ai-1,执行插入动作,两个步骤:,ai-1-next=anew;,anew-next=ai;,SCIE,Uni
11、versity of Electronic Science and Technology of China,18,2.1.2单链表,while(counter next;,void insertl(list,new_node,location),找到ai-1,p-next=new_node;,new_node-next=,?,ai-1-next=anew;,anew-next=ai;,p,p list-header;counter=1,q,q=p-next;,q;,法一,SCIE,University of Electronic Science and Technology of China,
12、19,2.1.2单链表,while(counter next;,void insertl(list,new_node,location),new_node-next=p-next;,p-next=new_node;,p,p list-header;counter=1,法二,SCIE,University of Electronic Science and Technology of China,20,2.1.2单链表,void insertl(list,new_node,location),while(counter next;,new_node-next=p-next;,p-next=new
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构
链接地址:https://www.desk33.com/p-229807.html