[2018年必威体育精装版整理]04双链表.pptVIP

电子科技大学通信与信息工程学院 居太亮 单链表的优点： 离散存放，不受链表初始大小限制，插入和删除时不进行结点内容的搬移 单链表的缺点： 查找费时：每个结点只有直接后继的地址，只能从表头开始一一查找。则平均查找次数为？ N/2次 怎样改进？ 双向链表 1.2.1 线性表--双向链表 双向链表：表中每个结点有两个指针域：一个指向直接后继，一个指向直接前驱。如下图： head 1.2.1 线性表--双向链表 *prior 指向直接前驱结点 data 数据元素 *next 指向直接后继结点 *prior a(i) *next *prior a(i+1) *next 1.2.1 线性表--双向链表 双向链表的结点结构： typedef struct { elemtype data; //数据域,各种类型。 struct node *prior； // 指向前驱节点的指针 struct node *next; //指向后继节点的指针 }node; 双向链表指针操作： p=q-prior=s-prior-prior=p-next-prior q=p-next=s-prior s=q-next=p-next-next 插入：参见教材p13算法7，图1.9; 删除：参见教材p14算法8, 图1.10; 1.2.1 线性表--双向链表 a(i-1) a(i) a(i+1) p q s 插入算法描述： void insertdl(node *p,int x){node *t,*tmp; tmp=p-prior; t=(node*)malloc(sizeof(node));t-data=x; t-prior=tmp; // t-prior=tmp=p-prior t-next=p; tmp-next=t; //p-prior-next=t p-prior=t;} 1.2.1 线性表--双向链表插入 a(i-1) x a(i) tmp t p 删除算法描述： void deletedl(node *p){node *t,*tmp; tmp=p-prior;t=p-next; tmp-next=t; // p-prior-next=p-next t-prior=tmp; // p-next-prior=p-prior free(p);} 1.2.1 线性表--双向链表删除 a(i-1) a(i) a(i+1) tmp p t 定义：表中最后一个结点的指针域不为空，而是指向表头，整个链表形成一个环。 特点：与一般链表不同之处在于只要给定循环链表中任一结点的地址，就可以查遍表中所有的结点，而不必从头指针开始。如下图： 1.2.1 线性表--循环链表 对循环链表的遍历可以从任何一个节点开始 a1 ai+1 an head tail ai-1 ... ... ai 无头节点的循环链表 header ai+1 an tail a1 ... ai … 带头节点的循环链表 1.2.1 线性表--循环链表 问题描述：两个单链表合并为一个单链表(头指针) head a(1) a(n) ^ … ha head b(1) b(n) ^ … hb void connect_a(node **ha,node *hb){ //需要**指针吗？ node *p=*ha; while(p-next!=NULL)p=p-next; p-next=hb-next; free(hb);} 合并后的单链表的头指针是？ 主调函数应该怎么写？ 1.2.1 线性表--循环链表 问题描述：两个循环链表合并为一个循环链表(尾指针) head a(1) a(n) … ra head b(1) a(n) … rb head a(1) a(n) … ra head b(1) b(n) … rb p void connect_b(node *ra, node *rb) {node *p=rb-next; rb-next=ra-next; ra-next=p-next; free(p);} 合并后的循环链表的尾指针是？ 主调函数应该怎么写？ 例：删除一个单向链表中数据大于100的所有结点 *算法分析： 1) 逐个取结点元素进行比较 ai-1 ai ai+1 …… …… current while(current!=NULL){ …… current=current-next; } 2) 删除大于100的结点（无专门的头节点） if(current-data100){ 删除由current指针指向的结点 } ai-1 ai ai+1 …… …… current last last-n