第2章-2 线性链表

1、2021-7-32021-7-3LongmanLongman1 1 2.1.3 2.1.3 线性表的链式存储结构线性表的链式存储结构-链表链表 /数据元素数据元素 SLNODE *next;/指向下一个指向下一个 /结点的指针结点的指针 h-next = NULL; 2021-7-32021-7-3LongmanLongman1010 单链表的基本运算单链表的基本运算 elemtype x; h=(SLNODE*)malloc(sizeof(SLNODE); p=h; h-next = NULL; x=get_data(); while(x!=-1) s=(SLNODE*)malloc(siz

2、eof(SLNODE); S-data=x; if(h-next=NULL) h-next=s; else p-next=s; 2021-7-32021-7-3LongmanLongman1212 单链表的基本运算单链表的基本运算 x=get_data(); p-next=NULL; 2021-7-32021-7-3LongmanLongman1313 单链表的查找单链表的查找 while(p!=NULL return p; 2021-7-32021-7-3LongmanLongman1414 单链表的查找单链表的查找 int j = 0; while(p-next!=NULL j+; if(

3、j=i) return p; else return NULL; 2021-7-32021-7-3LongmanLongman1515 单链表的插入单链表的插入 int j; p=h;j=0; while(p-next!=NULL j+; if(j!=i-1) printf(“i is invalid!”); return 0; else s = malloc(sizeof(SLNODE); s-data = x; s-next = p-next; p-next = s; return 1; 2021-7-32021-7-3LongmanLongman1717 删除算法删除算法 else s

4、= p-next; p-next = s-next; free(s); 2021-7-32021-7-3LongmanLongman1919 另外一种按值查找的删除算法另外一种按值查找的删除算法 int Del_(NODE* h,elemtype x) NODE *p,*q; p=h; q = h-next; while(q != NULL) q=q-next; if(q = NULL) printf(“要删除的接点不存在要删除的接点不存在n”)； else p-next = q-next; free(q); 2021-7-32021-7-3LongmanLongman2020 2. 2. 双

5、向链表（双向链表（Double linked list)Double linked list) 2021-7-32021-7-3LongmanLongman2424 双向链表结点的双向链表结点的C C语言描述语言描述 DNODE *prior,*next; ; 2021-7-32021-7-3LongmanLongman2525 双向链表的插入双向链表的插入 x s (1) (2) s=(DNODE *)malloc(sizeof(DNODE); s-data = x; s-next = p-next; /(1) s-prior = p; /(2) p-next-prior = s; /(3)

6、 p-next = s; /(4) 2021-7-32021-7-3LongmanLongman2727 ba p c 双向链表的删除双向链表的删除 q = p-next; q-next-prior = p; /(1) p-next = q-next; /(2) free(q); 2021-7-32021-7-3LongmanLongman2929 3. 3. 循环链表结构循环链表结构(Circular Linked List)(Circular Linked List) q = p-next; while(q-next ! = p) q = q -next; return q; 2021-7-32021-7-3LongmanLongman3333 两个循环单链表的合并两个循环单链表的合并 p=rb -next; rb-next = ra-next; ra-next = p-next; free(p); 2021-7-32021-7-3LongmanLongman3535 2.1.4 2.1.4 顺序表和链表的比较顺序表和链表的比较 顺序表顺序表链表链表 基于存储基于存储 空间考虑空间考虑 静态分配，不灵活静态分配，不灵活 存储密度存储密度100% 动态分配，灵活动态分配，灵活 存储密度小于存储密度小于50% 基于时间基于时间 考虑考虑 随机访问结构，适合随机访问结构，适合