VC驿站

 找回密码
 加入驿站

QQ登录

只需一步,快速开始

搜索
查看: 126|回复: 0

VC++基础班-[28]动态数组及动态链表的讲解

[复制链接]
admin 发表于 2018-2-8 00:48:20 | 显示全部楼层 |阅读模式
------------------------------------------ Begin ----------------------------------------
C++中也有相应的动态数组、动态链表、映射表的模板类,就是STL中的:vector、list、map
他们属于C++标准中的一部分,对于程序的移植性来说也是不错的,但是在MFC编程中使用 CArray、CList、CMap 会更方便一些!
CArray、CList、CMap 的由来?……

①、数组的基本说明:
数组是固定大小的,相同数据类型的元素的顺序集合,每个元素在数组中有一个固定的位置。
将10个数放入数组中,假设数组的名称为number,可以称数组中第一个元素为 number[0],第二个数为 number[1]……其中 0、1~9 称为元素的下标,
下标表明元素在数组中的相对位置。

例如,普通的常规静态数组定义为:
  1. int number[20];
  2. CPoint pt[10];
  3. CButton btn[10];
复制代码

====================================================
②、MFC中的动态数组类是:CArray
CArray 是一个模板类,类似于常规数组,但是长度可动态增长;
常规数组在使用前必须先知道元素的个数,即先确定大小,而MFC的动态数组类 CArray 创建的对象可以根据需要动态地增大或减小,
数组的起始下标是0,而上限可以是固定的,也可以随着元素的增加而增加,数组在内存中的位置仍然是连续的(这一点很关键)!

虽然 CArray 是一个模板类,但是微软在 MFC 中针对各种常用的变量类型分别定义了:
CByteArray、CDWordArray、CObArray、CPtrArray、CStringArray、CUIntArray、CWordrray 等,
所以,如果大家在程序中使用的数据结构有合适以上几种的类型的,可以直接拿过来用,无需重复定义,详见MSDN!
========================================================
③、CArray 类型对象的定义:其中带有 ARG_ 前缀的是传入类型,另外一个则是返回类型
  1. CArray <int, int> arrInt;
  2. CArray <CPoint, CPoint &> arrPoint;
  3. CArray <CButton, CButton &> arrButton;
复制代码

//在使用基本类型的时候,第二个参数可以不用传引用,但是使用类类型等符合类型的时候第二个参数最好传递对象的引用,
//这样可以避免拷贝构造函数的调用,提高效率!

  1. CStringArray arrString;
  2. CByteArray arrByte;
复制代码

====================================================
④、CArray 类的使用:
  1. // 插入节点、删除节点、遍历数组
  2. INT_PTR idx = 0;
  3. CArray <CPoint, CPoint &> arrPoint;
  4. //arrPoint.SetSize(100, 10);
  5. BOOL bRet = arrPoint.IsEmpty();
  6. for (idx = 0; idx < 100; ++idx){
  7.         CPoint pt;
  8.         pt.SetPoint(idx, idx);
  9.         arrPoint.Add(pt);//元素的添加
  10. }
  11. int nCount = arrPoint.GetCount();
  12. int maxIdx = arrPoint.GetUpperBound();
  13. bRet = arrPoint.IsEmpty();
  14. CPoint point = arrPoint.GetAt(10);
  15. arrPoint.RemoveAt(10, 5); //指定元素的删除
  16. nCount = arrPoint.GetCount();
  17. point = arrPoint.GetAt(10);
  18. point = arrPoint[11];

  19. //数组的遍历
  20. for (idx = 0; idx < arrPoint.GetCount(); ++idx){
  21.         CPoint pt = arrPoint.GetAt(idx);
  22.         pt.x = 123;
  23. }

  24. point.x = point.y = 999;
  25. arrPoint.SetAt(5, point);

  26. for (idx = 0; idx < arrPoint.GetCount(); ++idx){
  27.         CPoint pt = arrPoint.GetAt(idx);
  28.         pt = pt;
  29. }

  30. arrPoint.RemoveAll();
  31. nCount = arrPoint.GetCount();
  32. bRet = arrPoint.IsEmpty();
复制代码

====================================================
⑤、CArray 的效率问题:
问:CArray 确实很好用,但是为什么到了10万个数据以后,赋值的速度就很慢了呢?
答:CArray 是很好用的,只是因为你没有指定数组的最大尺寸。
因此,当你添加新元素时,该类会从堆中重新分配空间,不幸的是,该类会在每次插入新元素时都为数组重新分配空间,
如果你向它添加了很多新元素,所有这些分配和复制数组的操作会就会使它变慢。

解决该问题的方法是,你可以使用SetSize函数的第二个参数来改变这种重新分配的频率。
例如,如果你把该参数设置为500,则每次数组空间超出时它才重新分配并添加500个新空间,而不是1个,
这样一来,你就可以不用重新分配而添加了另外499个元素空间,这也会大大提高程序的运行速度。

====================================================
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
====================================================
⑥、链表的基本说明:
链表也是一个有序数据的集合,但每个元素包含下一个元素的地址。
每个元素包含两部分:数据和链(链是存储下一个元素地址的指针)
此处只讨论单链表,每个节点仅有一个指向后继节点的链。通常使用一个指针变量指向第一个元素,称为链表的头指针。链表的最后一个元素包含一个空指针,标识链表的结束。
链表是一种复杂的数据结构,其数据之间的相互关系使链表分成三种:单链表、循环链表、双向链表

链表在内存中的位置是不连续的(这一点很关键)!

例如,普通的链表节点定义为:
struct node
{
    int num;
    struct node *p;
} ;
====================================================
⑦、MFC中的动态链表类是:CList
CList 是双向链接表,因此 头、尾和表中已知位置(POSITION)的元素插入速度很快。
按值或者索引查找需要顺序搜索,然而如果表很长则速度可能慢!

虽然 CArray 是一个模板类,但是微软在 MFC 中针对各种常用的变量类型分别定义了:
CPtrList、CObList、CStringList 等,
所以,如果大家在程序中使用的数据结构有合适以上几种的类型的,可以直接拿过来用,无需重复定义,详见MSDN!
====================================================
⑧、CList 类型对象的定义:其中带有 ARG_ 前缀的是传入类型,另外一个则是返回类型
  1. CList <int, int> arrInt;
  2. CList <CPoint, CPoint &> arrPoint;
  3. CList <CButton, CButton &> arrButton;
复制代码

//在使用基本类型的时候,第二个参数可以不用传引用,但是使用类类型等符合类型的时候第二个参数最好传递对象的引用,
//这样可以避免拷贝构造函数的调用,提高效率!
====================================================
⑨、CList 类的使用:
  1. int idx = 0;
  2. CList <CPoint, CPoint &> ptList(100);
  3. BOOL bRet = ptList.IsEmpty();
  4. for (idx = 0; idx < 100; ++idx){
  5.         CPoint pt;
  6.         pt.SetPoint(idx, idx);
  7.         ptList.AddTail(pt);//向链表结尾添加元素
  8. }
  9. int nCount = ptList.GetCount();
  10. bRet = ptList.IsEmpty();

  11. //POSITION ps = 10;
  12. CPoint point = ptList.GetAt(ptList.FindIndex(10));
  13. ptList.RemoveAt(ptList.FindIndex(10)); //指定元素的删除
  14. nCount = ptList.GetCount();
  15. point = ptList.GetAt(ptList.FindIndex(10));

  16. //链表的遍历
  17. POSITION pos = ptList.GetHeadPosition();
  18. for (idx = 0; idx < ptList.GetCount(); ++idx) {
  19.         CPoint pt = ptList.GetNext(pos);
  20.         pt.x = 123;
  21. }

  22. point.x = point.y = 999;
  23. ptList.SetAt(ptList.FindIndex(5), point);

  24. pos = ptList.GetHeadPosition();
  25. for (idx = 0; idx < ptList.GetCount(); ++idx) {
  26.         CPoint pt = ptList.GetNext(pos);
  27.         pt = pt;
  28. }

  29. ptList.RemoveAll();
  30. nCount = ptList.GetCount();
  31. bRet = ptList.IsEmpty();
复制代码


⑩、※※※ 链表与数组的区别 ※※※
   数组是将元素在内存中连续存放,由于每个元素占用内存相同,所以可以通过下标迅速访问数组中任何元素。
但是如果要在数组中增加一个元素,需要移动大量元素,在内存中空出一个元素的空间,然后将要增加的元素放在其中。
同样的道理,如果想删除一个元素,同样需要移动大量元素去填掉被移动的元素。

   链表恰好相反,链表中的元素在内存中不是顺序存储的,而是通过存在元素中的指针联系到一起。如:上一个元素有个指针指到下一个元素,以此类推,直到最后一个元素。
如果要访问链表中一个元素,需要从第一个元素开始,一直找到需要的元素位置。但是增加和删除一个元素对于链表数据结构就非常简单了, 只要修改元素中的指针就可以了。

   ※※※ 从上面的比较可以看出,如果需要快速访问数据,很少或不插入和删除元素,就应该用数组,相反, 如果需要经常插入和删除元素就需要用链表了!

====================================================
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
====================================================

11、映射表的基本说明:
映射表类 也称作为“字典”,就像一种只有两列的表格,一列是关键字,一列是数据项,它们是一一对应的,是以键值对的形式出现的!
关键字是唯一的(※ 这点很重要),给出一个关键字,映射表会很快找到对应的数据项。
映射表的查找是以哈希表的方式进行的,因此在映射表中查找数值项的速度很快。
映射类最适用于需要根据关键字进行快速检索的场合。

例如:公司的所有职员都有一个工号和自己的姓名,工号就是关键字,给出一个工号,就可以很快的找到相应的姓名!
姓名可以重复,或者说有同名的情况,但是工号一定不能出现重复的!

12、MFC中的动态映射表类是:CMap

虽然 CMap 是一个模板类,但是微软在 MFC 中针对各种常用的变量类型分别定义了:
CMapWordToPtr、CMapPtrToWord、CMapPtrToPtr、CMapWordToOb、CMapStringToPtr、CMapStringToOb、CMapStringToString 等,
所以,如果大家在程序中使用的数据结构有合适以上几种的类型的,可以直接拿过来用,无需重复定义,详见MSDN!

13、CMap 类型对象的定义:其中带有 ARG_ 前缀的是传入类型,另外一个则是返回类型
  1. CMap <int, int, CString, LPCTSTR> intMapString;
  2. CMap <int, int, int, int> intMapInt;
  3. CMap <int, int, CPoint, CPoint &> intMapPoint;
  4. CMap <long, long, CButton, CButton &> longMapButton;
  5. CMap <CString, LPCTSTR, int, int> strMapString;
复制代码

//在使用基本类型的时候,第二、四个参数可以不用传引用,但是使用类类型等符合类型的时候第二、四个参数最好传递对象的引用,
//这样可以避免拷贝构造函数的调用,提高效率!

14、CMap 类的使用:
  1. CMap<int, int, CString, LPCTSTR> intMapString(20);

  2. CString strText;
  3. for (int idx = 0; idx < 20; ++idx){
  4.         strText.Format(_T("%s%d"), _T("The number is : "), idx);
  5.         intMapString.SetAt(idx, strText);
  6. }

  7. int nCount = intMapString.GetCount();
  8. BOOL bRet = intMapString.IsEmpty();

  9. strText.Empty();
  10. intMapString.Lookup(10, strText);//根据key查找元素
  11. intMapString.RemoveKey(10); //根据key删除元素
  12. nCount = intMapString.GetCount();

  13. strText.Empty();
  14. intMapString.Lookup(10, strText); //还能找到吗?

  15. //映射表的遍历
  16. int nKey = 0;
  17. POSITION pos = intMapString.GetStartPosition();
  18. while (pos != NULL) {
  19.         strText.Empty();
  20.         intMapString.GetNextAssoc(pos, nKey, strText);
  21. }

  22. intMapString.SetAt(5, _T("abcdefg123"));

  23. intMapString.RemoveAll();
  24. nCount = intMapString.GetCount();
  25. bRet = intMapString.IsEmpty();
复制代码



★ 课后作业:
1、练习使用 CStringArray 等类的使用;
------------------------------------- End -------------------------------------------

相关课程演示细节还请观看视频教程!
本套教程由VC驿站原创,提供视频教程+售后答疑服务!
教程介绍及详情请见:http://www.cctry.com/thread-17282-1-1.html
VC驿站Vip会员详情请见:http://www.cctry.com/static/vip/index.html

发帖求助前要善用论坛搜索功能,那里可能会有你要找的答案;

如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请编辑帖子并把分类改成【已解决】

如何回报帮助你解决问题的坛友,一个好办法就是给对方加【热心】【驿站币】,加分不会扣除自己的积分,做一个热心并受欢迎的人!

您需要登录后才可以回帖 登录 | 加入驿站

本版积分规则

 
 
在线客服
工作时间:
8:00-18:00
客服热线:
13591366679
官方微信扫一扫

QQ|小黑屋|手机版|VC驿站 ( 辽ICP备09019393号 )

返回顶部
x

VC驿站微信公众号cctry2009

GMT+8, 2018-2-18 11:22

Powered by Discuz! X3.4

© 2009-2018 cctry.com

快速回复 返回顶部 返回列表