首页 > 代码库 > vc++基础班[28]---动态数组及动态链表的讲解

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

2024-11-14 01:28:02   203人阅读

C++中也有相应的动态数组、动态链表、映射表的模板类，就是STL中的：vector、list、map
他们属于C++标准中的一部分，对于程序的移植性来说也是不错的，但是在MFC编程中使用 CArray、CList、CMap 会更方便一些！
CArray、CList、CMap 的由来？……
 
①、数组的基本说明：
数组是固定大小的，相同数据类型的元素的顺序集合，每个元素在数组中有一个固定的位置。
将10个数放入数组中，假设数组的名称为number，可以称数组中第一个元素为 number[0]，第二个数为 number[1]……其中 0、1～9 称为元素的下标，
下标表明元素在数组中的相对位置。
 
例如，普通的常规静态数组定义为：
int number[20];
CPoint pt[10];
CButton btn[10];
====================================================
②、MFC中的动态数组类是：CArray
CArray 是一个模板类，类似于常规数组，但是长度可动态增长；
常规数组在使用前必须先知道元素的个数，即先确定大小，而MFC的动态数组类 CArray 创建的对象可以根据需要动态地增大或减小，
数组的起始下标是0，而上限可以是固定的，也可以随着元素的增加而增加，数组在内存中的位置仍然是连续的（这一点很关键）！
 
虽然 CArray 是一个模板类，但是微软在 MFC 中针对各种常用的变量类型分别定义了：
CByteArray、CDWordArray、CObArray、CPtrArray、CStringArray、CUIntArray、CWordrray 等，
所以，如果大家在程序中使用的数据结构有合适以上几种的类型的，可以直接拿过来用，无需重复定义，详见MSDN！
========================================================
③、CArray 类型对象的定义：其中带有 ARG_ 前缀的是传入类型，另外一个则是返回类型
CArray <int, int> arrInt;
CArray <CPoint, CPoint &> arrPoint;
CArray <CButton, CButton &> arrButton;
//在使用基本类型的时候，第二个参数可以不用传引用，但是使用类类型等符合类型的时候第二个参数最好传递对象的引用，
//这样可以避免拷贝构造函数的调用，提高效率！
 
CStringArray arrString;
CByteArray arrByte;
====================================================
④、CArray 类的使用：
// 插入节点、删除节点、遍历数组
INT_PTR idx = 0;
CArray <CPoint, CPoint &> arrPoint;
//arrPoint.SetSize(100, 10);
BOOL bRet = arrPoint.IsEmpty();
for (idx = 0; idx < 100; ++idx){
 CPoint pt;
 pt.SetPoint(idx, idx);
 arrPoint.Add(pt);//元素的添加
}
int nCount = arrPoint.GetCount();
int maxIdx = arrPoint.GetUpperBound();
bRet = arrPoint.IsEmpty();
CPoint point = arrPoint.GetAt(10);
arrPoint.RemoveAt(10, 5); //指定元素的删除
nCount = arrPoint.GetCount();
point = arrPoint.GetAt(10);
point = arrPoint[11];
 
//数组的遍历
for (idx = 0; idx < arrPoint.GetCount(); ++idx){
 CPoint pt = arrPoint.GetAt(idx);
 pt.x = 123;
}
 
point.x = point.y = 999;
arrPoint.SetAt(5, point);
 
for (idx = 0; idx < arrPoint.GetCount(); ++idx){
 CPoint pt = arrPoint.GetAt(idx);
 pt = pt;
}
 
arrPoint.RemoveAll();
nCount = arrPoint.GetCount();
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_ 前缀的是传入类型，另外一个则是返回类型
CList <int, int> arrInt;
CList <CPoint, CPoint &> arrPoint;
CList <CButton, CButton &> arrButton;
//在使用基本类型的时候，第二个参数可以不用传引用，但是使用类类型等符合类型的时候第二个参数最好传递对象的引用，
//这样可以避免拷贝构造函数的调用，提高效率！
====================================================
⑨、CList 类的使用：
int idx = 0;
CList <CPoint, CPoint &> ptList(100);
BOOL bRet = ptList.IsEmpty();
for (idx = 0; idx < 100; ++idx){
 CPoint pt;
 pt.SetPoint(idx, idx);
 ptList.AddTail(pt);//向链表结尾添加元素
}
int nCount = ptList.GetCount();
bRet = ptList.IsEmpty();
 
//POSITION ps = 10;
CPoint point = ptList.GetAt(ptList.FindIndex(10));
ptList.RemoveAt(ptList.FindIndex(10)); //指定元素的删除
nCount = ptList.GetCount();
point = ptList.GetAt(ptList.FindIndex(10));
 
//链表的遍历
POSITION pos = ptList.GetHeadPosition();
for (idx = 0; idx < ptList.GetCount(); ++idx) {
 CPoint pt = ptList.GetNext(pos);
 pt.x = 123;
}
 
point.x = point.y = 999;
ptList.SetAt(ptList.FindIndex(5), point);
 
pos = ptList.GetHeadPosition();
for (idx = 0; idx < ptList.GetCount(); ++idx) {
 CPoint pt = ptList.GetNext(pos);
 pt = pt;
}
 
ptList.RemoveAll();
nCount = ptList.GetCount();
bRet = ptList.IsEmpty();
 
⑩、※※※ 链表与数组的区别 ※※※
　　 数组是将元素在内存中连续存放，由于每个元素占用内存相同，所以可以通过下标迅速访问数组中任何元素。
但是如果要在数组中增加一个元素，需要移动大量元素，在内存中空出一个元素的空间，然后将要增加的元素放在其中。
同样的道理，如果想删除一个元素，同样需要移动大量元素去填掉被移动的元素。
 
　　 链表恰好相反，链表中的元素在内存中不是顺序存储的，而是通过存在元素中的指针联系到一起。如：上一个元素有个指针指到下一个元素，以此类推，直到最后一个元素。
如果要访问链表中一个元素，需要从第一个元素开始，一直找到需要的元素位置。但是增加和删除一个元素对于链表数据结构就非常简单了， 只要修改元素中的指针就可以了。
 
　　 ※※※ 从上面的比较可以看出，如果需要快速访问数据，很少或不插入和删除元素，就应该用数组，相反， 如果需要经常插入和删除元素就需要用链表了！
 
====================================================
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
====================================================
 
11、映射表的基本说明：
映射表类 也称作为“字典”，就像一种只有两列的表格，一列是关键字，一列是数据项，它们是一一对应的，是以键值对的形式出现的！
关键字是唯一的（※ 这点很重要），给出一个关键字，映射表会很快找到对应的数据项。
映射表的查找是以哈希表的方式进行的，因此在映射表中查找数值项的速度很快。
映射类最适用于需要根据关键字进行快速检索的场合。
 
例如：公司的所有职员都有一个工号和自己的姓名，工号就是关键字，给出一个工号，就可以很快的找到相应的姓名！
姓名可以重复，或者说有同名的情况，但是工号一定不能出现重复的！
 
12、MFC中的动态映射表类是：CMap
 
虽然 CMap 是一个模板类，但是微软在 MFC 中针对各种常用的变量类型分别定义了：
CMapWordToPtr、CMapPtrToWord、CMapPtrToPtr、CMapWordToOb、CMapStringToPtr、CMapStringToOb、CMapStringToString 等，
所以，如果大家在程序中使用的数据结构有合适以上几种的类型的，可以直接拿过来用，无需重复定义，详见MSDN！
 
13、CMap 类型对象的定义：其中带有 ARG_ 前缀的是传入类型，另外一个则是返回类型
CMap <int, int, CString, LPCTSTR> intMapString;
CMap <int, int, int, int> intMapInt;
CMap <int, int, CPoint, CPoint &> intMapPoint;
CMap <long, long, CButton, CButton &> longMapButton;
CMap <CString, LPCTSTR, int, int> strMapString;
//在使用基本类型的时候，第二、四个参数可以不用传引用，但是使用类类型等符合类型的时候第二、四个参数最好传递对象的引用，
//这样可以避免拷贝构造函数的调用，提高效率！
 
14、CMap 类的使用：
CMap<int, int, CString, LPCTSTR> intMapString(20);
 
CString strText;
for (int idx = 0; idx < 20; ++idx){
 strText.Format(_T("%s%d"), _T("The number is : "), idx);
 intMapString.SetAt(idx, strText);
}
 
int nCount = intMapString.GetCount();
BOOL bRet = intMapString.IsEmpty();
 
strText.Empty();
intMapString.Lookup(10, strText);//根据key查找元素
intMapString.RemoveKey(10); //根据key删除元素
nCount = intMapString.GetCount();
 
strText.Empty();
intMapString.Lookup(10, strText); //还能找到吗？
 
//映射表的遍历
int nKey = 0;
POSITION pos = intMapString.GetStartPosition();
while (pos != NULL) {
 strText.Empty();
 intMapString.GetNextAssoc(pos, nKey, strText);
}
 
intMapString.SetAt(5, _T("abcdefg123"));
 
intMapString.RemoveAll();
nCount = intMapString.GetCount();
bRet = intMapString.IsEmpty();
 
 
★ 课后作业：
1、练习使用 CStringArray 等类的使用；
------------------------------------- End -------------------------------------------

 

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


联系
我们