vc++第8章 简单链表及其应用.ppt

简单链表及其应用 链表 思考 如何描述一个班的学生基本信息 学号 姓名 年龄等 structstudent intID charName 20 intage stu 30 分配固定长度连续空间 操作没有灵活性如何添加新转入学生信息 链表 将若干个同类型的结构体类型数据按一定的原则连接起来 structstudent intID charName 20 intage student next 链表的特点 coutID student p head coutName p p next coutage 链表的特点 结点可不连续存储操作灵活 便于扩充 动态分配空间 NULL 链表的特点 链表的操作之建立无序链 链表为空 head 0 head p1 p2 p1 head data1 链表的操作之建立无序链 链表为空 head 0 head p1 p2 p1 链表不为空p2 next p1 p2 p1 p1用来指向新结点p2用来指向链表当前尾结点 head data1 链表的操作之输出链表上各个结点的值 遍历链表结点 看 一个输出一个 p head coutdata p p next coutdata p p next p NULL 遍历的终止条件 链表的操作之删除某结点 先找到要删除结点 如果是头结点p1 head head head next deletep1 head data4 链表的操作之删除某结点 先找到要删除结点 以 找到 或 到尾找不到 为终止条件的遍历p2 head while p2 data data3 head data4 链表的操作之删除某结点 p1 next p2 next p2指向要删除结点 p1指向要删除结点的前驱结点deletep2 先找到要删除结点 包括其前驱结点 再删除 head data4 链表的操作之删除整个链 遍历链表 看 一个删一个 p1 head head head next 或head p1 next deletep1 head data4 链表的操作之删除整个链 遍历链表 看 一个删一个 while head NULL p1 head head head next 或head p1 next deletep1 head 链表的操作之插入结点保持有序 p next head head p head 5 链表的操作之插入结点保持有序 p2 next p p next 0 head 5 链表的操作之插入结点保持有序 p next p2 p1 next p 先找到插入点 head 5 链表的操作之总结 链表的操作主要依靠指针和动态空间实现头指针是链表的访问依据改变部分链表的函数 插入 删除结点等 需要返回改变后的链表 通过头指针 课堂练习 设计函数统计链表的结点个数遍历链表 看 一个 计数器累加一次返回值为结点的个数 整型intcount constnode head constnode p head intn 0 while p NULL n p p next retrunn 课堂练习 将一无序链表按升序排序冒泡排序if p data p next data temp p data p data p next data p next data temp 课堂练习 将一无序链表按升序排序冒泡排序if p data p next data temp p data p data p next data p next data temp p p next 课堂练习 将一无序链表按升序排序冒泡排序if p data p next data temp p data p data p next data p next data temp p p next 课堂练习 将一无序链表按升序排序冒泡排序if p data p next data temp p data p data p next data p next data temp p p next 课堂练习 voidsort node head node p head for