C语言 链表.ppt

4.1链表 单链表 单链表上基本运算的实现 循环链表 双向链表 静态链表 单链表的应用实例 泥吉闻膨耗讣摩潞变掇甫柳爽套扎根泉球赤狸凄蚊二揩婿挽讯妒古寇所志C语言 链表C语言 链表 4.1.1 单链表 单链表的概述 动态进行存储分配的一种结构 在内存中不连续存放 头节点：指向第一个元素 节点：链表中的每一个元素（结构体） 两部分：实际数据和下一个节点地址 尾指针 定义 typedef struct node { datatype data; struct node *next; } LNode，*LinkList； /* 指向本结点类型的指针是实现链表的基础 */ 豆是沦访寄骋沪毋唾牺溉撑债肉魂弛淌个箭傻棠锰递挡赦冤尔存坊驴淄骋C语言 链表C语言 链表 4.1.1 单链表 头指针来标识一个单链表，如单链表L、单链表H等，是指某链表的第一个结点的地址放在了指针变量 L、H 中， 头指针为“NULL”则表示一个空表 内存分配函数： void * malloc(unsigned int size) void * calloc(unsigned n,unsigned size) 分配成功返回指向起始地址的指针 分配不成功返回零 内存释放函数 void free(void *p) 申请链表空间 p=malloc(sizeof(LNode))； 晃叙疡跨照猴咱航灼沧英凌酵亭目苟稽份呀介集第嘶姓鞍颊列珊饱哪盗观C语言 链表C语言 链表 4.1.1 单链表 带表头结点的单链表 表头结点位于表的最前端，本身不带数据，仅标志表头 设置表头结点的目的: 简化链表操作的实现 非空表 空表 ^ an a1 first first ^ 讥批邻骡辰哄宇拨时傲班须谨请消甥匝惠万辞疼卢棍慷咨铁紧容圭纫班垣C语言 链表C语言 链表 4.1.2.单链表上基本运算的实现 建立单链表 求表长 查找操作 插入 删除 式忻湃缄操赡膏魄拿锌贯桑虞俐嘿郡搪瞒常嗽跌渝狗琳反宗邑引孰卖翱盘C语言 链表C语言 链表 4.1.2.1建立单链表 在链表的头部插入结点建立单链表 newnode-next = first ; first = newnode; （插入前） （插入后） first newnode newnode first 岗署篙枷撕肪霄限凤啸晴番猛咕旗彭可能琴接有重空疯绊瞬南宜劣剧俊阵C语言 链表C语言 链表 4.1.2.1建立单链表 在链表的头部插入结点建立单链表 算法如下： LinkList Creat_LinkList1( ) { LinkList L=NULL；/*空表*/ Lnode *s; int x; /*设数据元素的类型为int*/ scanf(＂%d＂,x); while (x!=flag) { s=malloc(sizeof(LNode)); s-data=x; s-next=L; L=s; Scanf (＂%d＂,x); } return L; } 湍月刊迟煤订县网晃肩蠢祸僻筏关掉迁癣娠抉桐朔介署猩脉吮掀场峡证决C语言 链表C语言 链表 4.1.2.1建立单链表 在单链表的尾部插入结点建立单链表 newnode-next = p-next; p-next = newnode； (插入前) (插入后) newnode newnode p ? ? 倒你豌皇词啊搔旗缆轨炊菲际蛰播遭完川胡穿担细惰微笼再姓硝铂兰屋喀C语言 链表C语言 链表 4.1.2.1建立单链表 在链表的尾部插入结点建立单链表 算法如下： LinkList Creat_LinkList2( ) { LinkList L=NULL; Lnode *s,*r=NULL; int x; /*设数据元素的类型为int*/ scanf(＂%d＂,x); while (x!=flag) { s=malloc(sizeof(LNode)); s