数据结构 第4章.ppt

2020 2 5 数据结构 1 1 构造一个空的带头结点的单链表 算法2 7intinitlist l linklist 三 单链表的操作 2 3线性表的链式存储结构 单链表 2020 2 5 数据结构 2 实际程序 intinitlist l linklist l if l node malloc sizeof node NULL 向系统申请一个头结点的空间 return 0 l next NULL return 1 2 3线性表的链式存储结构 单链表 2020 2 5 数据结构 3 intgetelem l linklistl inti elementype 2 取元素 算法2 8 2020 2 5 数据结构 4 if p j i 第i个元素不存在 printf ierror return 0 e p data 取第i个元素 printf ok return 1 2020 2 5 数据结构 5 3 插入结点 算法2 9 核心语句 s data e s next p next 将新结点插入到l中 p next s 2020 2 5 数据结构 6 intlistinsert l linklist if p j i 1 i小于1或者大于表长 算法2 9结点插入算法 2020 2 5 数据结构 7 printf ierror return 0 s node malloc sizeof node 生成新结点 s data e s next p next 将新结点插入到l中 p next s printf ok return 1 2020 2 5 数据结构 8 4 删除结点 算法2 10 核心语句 p next p next next 注意free 图2 9从链表中删除一个结点 2020 2 5 数据结构 9 intlistdelete l linklist if p next j i 1 i的值非法 算法2 10结点的删除算法 2020 2 5 数据结构 10 printf ierror return 0 q p next 保存第i个结点的位置 e q data 保存第i个结点的值 p next q next 删除第i个结点 free q 释放空间 printf ok 删除成功 return 1 2020 2 5 数据结构 11 while p 在P所指的结点插入 所以p所指的结点应该存在 while p next 删除的是P所指的下一个结点 所以p next所指的结点应该存在 两个程序有什么不同 2020 2 5 数据结构 12 逆位序输入n个元素的值 建立带表头结点的单链线性表l 元素插入在表头 voidcreatelist l linklist i 5 创建单链表 算法2 11 2020 2 5 数据结构 13 p node malloc sizeof node 申请新结点 scanf 将新结点插入到表头 2020 2 5 数据结构 14 顺位序输入n个元素的值 建立带表头结点的单链表l 元素插入在表尾 voidcreatelist l linklist 创建单链表 算法2 11 2020 2 5 数据结构 15 for i n i 0 i p node malloc sizeof node 申请新结点 scanf 2020 2 5 数据结构 16 intListLength linklisthead linklistp head p指向头结点 intsize 0 size初始为0 while p next NULL 循环计数 p p next size returnsize 6 求单链表中数据元素的个数 2020 2 5 数据结构 17 四 单链表的操作效率分析 1 查找因线性链表只能顺序存取 即在查找时要从头指针找起 查找的时间复杂度为O n 时间效率分析 2 插入和删除因线性链表不需要移动元素 只要修改指针 仅就插入或删除而言 时间复杂度为O 1 但是 如果要在单链表中进行在某结点前插或删除操作 因为要从头查找前驱结点 所以一般情况下 单链表插入和删除操作的时间复杂度是O n 同顺序表 2020 2 5 数据结构 18 五 实验 编程实现 建立一个单链表 首先依次输入数据元素1