数据结构与指针应用详解

### 数据结构与指针应用详解 #### 1. 链表与自包含类 链表是数组之后最常用的数据存储方式。它避免了数组可能造成的内存空间浪费，但缺点是查找特定元素时，需要从链表头部开始沿着链接链一直找到目标链接，这可能比较耗时。而数组元素只要提前知道索引，就能快速访问。 在使用自引用类和结构体时，有一个潜在的陷阱需要注意。类可以包含指向自身类型对象的指针，但不能包含自身类型的对象。例如： ```cpp class sampleclass { sampleclass* ptr; // 这是可行的 }; class sampleclass { sampleclass obj; // 不能这样做 }; ``` 对于结构体也是如此。 链表的通用组织形式可以用于更复杂的情况。每个链接可以包含更多的数据，比如不再是一个整数，而是多个数据项，或者是指向结构体或对象的指针。还可以添加额外的成员函数，例如从链表的任意部分添加和删除链接。另外，析构函数也是一个重要的成员函数，它可以释放不再使用的内存块，遍历链表并使用 `delete` 释放每个链接占用的内存。 #### 2. 指针到指针 下面通过一个程序来展示指向对象的指针数组，并介绍如何根据对象中的数据对这些指针进行排序，这涉及到指针到指针的概念。 程序的思路是创建一个指向 `person` 类对象的指针数组。与 `PTROBJS` 示例类似，但进一步添加了 `PTRSORT` 示例中的 `order()` 和 `bsort()` 函数的变体，以便根据人名的字母顺序对一组 `person` 对象进行排序。以下是 `PERSORT` 程序的代码： ```cpp // persort.cpp // sorts person objects using array of pointers #include <iostream> #include <string> //for string class using namespace std; class person //class of persons { protected: string name; //person’s name public: void setName() //set the name { cout << "Enter name: "; cin >> name; } void printName() //display the name { cout << endl << name; } string getName() //return the name { return name; } }; int main() { void bsort(person**, int); //prototype person* persPtr[100]; //array of pointers to persons int n = 0; //number of persons in array char choice; //input char do { //put persons in array persPtr[n] = new person; //make new object persPtr[n]->setName(); //set person’s name n++; //count new person cout << "Enter another (y/n)? "; //enter another cin >> choice; // person? } while( choice=='y' ); //quit on ‘n’ cout << "\nUnsorted list:"; for(int j=0; j<n; j++) //print unsorted list { persPtr[j]->printName(); } bsort(persPtr, n); //sort pointers cout << "\nSorted list:"; for(j=0; j<n; j++) //print sorted list { persPtr[j]->printName(); } cout << endl; return 0; } //end main() //-------------------------------------------------------------- void bsort(person** pp, int n) //sort pointers to persons { void order(person**, person**); //prototype int j, k; //indexes to array for(j=0; j<n-1; j++) //outer loop for(k=j+1; k<n; k++) //inner loop starts at outer order(pp+j, pp+k); //order the pointer contents } //-------------------------------------------------------------- void order(person** pp1, person** pp2) //orders two pointers { //if 1st larger than 2nd, if( (*pp1)->getName() > (*pp2)->getName() ) { person* tempptr = *pp1; //swap the pointers *pp1 = *pp2; *pp2 = tempptr; } } ``` 程序执行时，首先会要求输入人名。用户输入后，程序会创建一个 `person` 类对象，并将输入的名字设置为该对象的 `name` 数据。同时，程序会将指向该对象的指针存储在 `persPtr` 数组中。当用户输入 `n` 表示不再输入人名时，程序会调用 `bsort()` 函数，根据人名成员变量对 `person` 对象进行排序。 例如，输入以下数据： ``` Enter name: Washington Enter another (y/n)? y Enter name: Adams Enter another (y/n)? y Enter name: Jefferson Enter another (y/n)? y Enter name: Madison Enter another (y/n)? n ``` 输出结果为： ``` Unsorted list: Washington Adams Jefferson Madison Sorted list: Adams Jefferson Madison Washington ``` 实际上，在对 `person` 对象进行排序时，并不是移动对象本身，而是移动指向对象的指针。这样可以避免在内存中移动对象，尤其是当对象较大时，这可能会非常耗时。而且，如果需要，还可以同时在内存中保留多种排序方式，例如按姓名和按电话号码排序，而无需多次存储对象。 `bsort()` 函数的第一个参数和 `order()` 函数的两个参数的类型都是 `person**`。这两个星号表示这些参数用于传递 `persPtr` 数组的地址，或者在 `order()` 函数中传递数组元素的地址。因为 `persPtr` 数组是指向 `person` 对象的指针数组，所以其地址的类型是 `person**`，即指针的指针。 #### 3. 字符串比较 `PERSORT` 程序中的 `order()` 函数经过修改，可以按字典顺序对两个字符串进行排序，也就是按字母顺序排列。它使用 C++ 库函数 `strcmp()` 来比较字符串。该函数接受两个字符串 `s1` 和 `s2` 作为参数，返回值如下： | 返回值 | 条件 | | ---- | ---- | | <0 | `s1` 在 `s2` 之前 | | 0 | `s1` 与 `s2` 相同 | | >0 | `s1` 在 `s2` 之后 | 字符串通过 `(*pp1)->getName()` 这样的语法来访问。`pp1` 是一个指向指针的指针，这里需要先解引用一层，再通过 `->` 操作符访问对象的 `getName()` 函数获取名字。 #### 4. 算术表达式解析 程序员经常会遇到解析符号字符串的问题，例如用户在键盘上输入的命令、自然语言句子、编程语言语句和代数表达式等。下面通过一个程序来展示如何解析像 `6/3+2*3-1` 这样的算术表达式。 程序使用了之前设计的 `Stack` 类，并对其进行了修改，使其存储 `char` 类型的数据。栈用于