什麽是串列 ? 他是要干麻用的 ? 我突然发现我跟老师好像都没有跟你们仔细提到这个问题 串列 简单来说就是一堆资料串在一起 ( 康熙字典有云：「串者，与贯通也。」 ) 先想像之前学过的阵列 阵列就像表格一样 当你需要存很 n 笔资料的时候 不需要宣告 int a,b,c,d, .... n; 只要宣告 int a[n]; // 这个语法只适用 dev c++ 电脑就会在记忆体内分配连续 n 个int的空间给你 阵列很好用 只要给电脑 初始位置 和 index 就可以当一般变数使用 ex: a[5]=3; a是初始位置 5是index 3是存进去的资料 但是阵列因为先天上的设计 - 连续空间 所以遇到一些问题的时候很棘手 例如 你要在 a[4] a[5] 之间插入一笔资料 必须要把 a[5] 以後的东西往後推 ( a[n] 存到 a[n+1] ) 再把 新的资料放到 a[5] 另外一个困难就是 如果要删除 a[3] 要把 a[3] 以後的资料 往前推一格 ( a[n+1] 存到 a[n] ) 要解决上面的问题 这时候就是串列派上用场的时候了 串列只有起始位置 他没有 index 阵列有 起始位置 每笔资料有 这个资料 还有 index 串列有 起始位置 每笔资料有 这个资料 还有 下一个人的记忆体位址(用指标存) 看下面的图 ┌─┬┐ ┌─┬┐ ┌─┬┐ head →│１│─→│５│─→│８│─→ NULL 　　　　└─┴┘　└─┴┘　└─┴┘ head 就是起始位置 就好像阵列 int a[10]里面 a 是一个指标指向起始位置一样 改成这样之後 插入删除资料就变的很轻松 插入资料 ┌─┬┐　　 ┌─┬┐ ┌─┬┐ head →│１│─┐　┌│５│─→│８│─→ NULL 　　　　└─┴┘│　│└─┴┘　└─┴┘ 　　　　 ┌──┘　└┐ 　　　　　│ ┌─┬┐│　　 └→│３│─┘ 　　　　　　　└─┴┘ 要把 3 插到 1, 5中间 就把 1 接到 3, 把 3 接到 5, 也就是说 把前面一个人接到新的点, 把新的点接到後面的点 删除资料 ┌─┬┐　　 ┌─┬┐ ┌─┬┐ head →│１│───→│５│─→│８│─→ NULL 　　　　└─┴┘Ｘ　Ｘ└─┴┘　└─┴┘ 　　　　 ┌──┘　└┐ 　　　　　│ ┌─┬┐│　　 └→│３│─┘ 　　　　　　　└─┴┘ 要把 1, 3, 5 的 3 删除 只要把 1 接到 5 就好了 也就是说 把前面一个人 接到 要删除的点後面的点 那有了串列 还要阵列干嘛? 阵列因为是连续空间 所以他的优点是 速度快 知道他的长度是多少 串列是不连续空间 所以速度较慢 长度要从head跑到NULL才知道长度 优点是 资料常常会增减的时候很方便 -> 是什麽意思? 就好像要动指标 a 的资料的时候 要用 *a 要动指标a的class成员的时候 要用 a-> 所以 a->link()的意思是说 呼叫 a指标所指的那个物件的link函数 为什麽有时候用 head=p; 不用 head->link(p); 看一下新增节点(插入)的程式码 如果新的点要放在最前面的时候 不可以直接 head->link(p); 因为这样是 head所指到的人 链结到p 这样会导致 p变成第二个人 要改成 head = p; ( head 存 p 里面存的位址 也就是说 head 指到 p指到的那个物件 ) 这就是 if(q2==NULL) head=p; else q2.link(p); 的原因 ( 我们在while外面指定 q1一开始=head q2一开始=NULL ) 最後要说 基本上期中考应该就是串列了 考试带着课本还有之前交的作业 看懂自己写或是参考来的程式码 每一行在干麻 如果题目出现变化 你要改哪里怎麽改 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 203.68.15.209