中山大学C++视频课件第9章_黎培兴分析

1、C+语言程序设计*MathXP2l线性群体线性群体的概念直接访问群体-数组类顺序访问群体-链表类栈类队列类3群体是指由多个数据元素组成的集合体。群体可以分为两个大类：线性群体和非线性群体。线性群体中的元素按位置排列有序，可以区分为第一个元素、第二个元素等。非线性群体不用位置顺序来标识元素。4线性群体中的元素次序与其位置关系是对应的。在线性群体中，又可按照访问元素的不同方法分为直接访问、顺序访问和索引访问。在本章我们只介绍直接访问和顺序访问。第一个元素第二个元素第三个元素最后一个元素5l静态数组是具有固定元素个数的群体，其中的元素可以通过下标直接访问。缺点：大小在编译时就已经确定，在运行时无法修

2、改。l动态数组由一系列位置连续的，任意数量相同类型的元素组成。优点：其元素个数可在程序运行时改变。直接访问线性群体6l数组类模板：例9.1（9_1.h）直接访问线性群体#ifndef ARRAY_CLASS#define ARRAY_CLASS#include #include #ifndef NULLconst int NULL = 0;#endif / NULLenum ErrorType invalidArraySize, memoryAllocationError, indexOutOfRange ;char *errorMsg = Invalid array size, Memory

3、 allocation error, Invalid index: ;template class Array private: T* alist; int size; void Error(ErrorType error,int badIndex=0) const; public: Array(int sz = 50); Array(const Array& A); Array(void); Array& operator= (const Array& rhs); T& operator (int i); operator T* (void) const; i

4、nt ListSize(void) const; void Resize(int sz); ;/类成员函数的实现略9l例9.2 求范围2N中的质数，N在程序运行时由键盘输入。直接访问线性群体#include #include #include 9_1.hvoid main(void) Array A(10); int n; int primecount = 0, i, j; cout = 2 as upper limit for prime numbers: ; cin n; Aprimecount+ = 2; / 2是一个质数for(i = 3; i n; i+) if (primecoun

5、t = A.ListSize（ ）) A.Resize(primecount + 10); if (i % 2 = 0) continue; j = 3; while (j i/2) Aprimecount+ = i; for (i = 0; i primecount; i+) cout setw(5) Ai; if (i+1) % 10 = 0) cout endl; cout endl;12l链表是一种动态数据结构，可以用来表示顺序访问的线性群体。l链表是由系列结点组成的，结点可以在运行时动态生成。l每一个结点包括数据域和指向链表中下一个结点的指针（即下一个结点的地址）。如果链表每个结点中

6、只有一个指向后继结点的指针，则该链表称为单链表。顺序访问线性群体13顺序访问线性群体 data1 data2 data3 datan NULLheadrear14template class Node private: Node *next; public: T data; Node(const T& item,Node* ptrnext = NULL); void InsertAfter(Node *p); Node *DeleteAfter(void); Node *NextNode(void) const; /实现略顺序访问线性群体15顺序访问线性群体 data1 data2 p

7、 q data16顺序访问线性群体 data1 data2 data3 p q17l生成结点l输出链表l查找结点l插入结点l删除结点l清空链表顺序访问线性群体18#ifndef NODE_LIBRARY#define NODE_LIBRARY#include #include #include 9_3.h顺序访问线性群体/ 生成节点template Node *GetNode(const T& item, Node *nextPtr = NULL) Node *newNode; newNode = new Node(item, nextPtr); if (newNode = NULL)

8、 cerr Memory allocation failure! endl; exit(1); return newNode;enum AppendNewline noNewline,addNewline;/ 输出链表template void PrintList(Node *head, AppendNewline addnl = noNewline) Node *currPtr = head; while(currPtr != NULL) if(addnl = addNewline) cout data endl; else cout data NextNode（ ）; /查找节点templ

9、ate int Find(Node *head, T& item, Node* &prevPtr)Node *currPtr = head; prevPtr = NULL;while(currPtr != NULL) if (currPtr-data = item) return 1; prevPtr = currPtr; currPtr = currPtr-NextNode（ ）;return 0; /在表头插入节点template void InsertFront(Node* & head, T item) head = GetNode(item,head); /在

10、表尾添加节点template void InsertRear(Node* & head, const T& item) Node *newNode, *currPtr = head; if (currPtr = NULL) InsertFront(head,item); else while(currPtr-NextNode（ ） != NULL) currPtr = currPtr-NextNode（ ）; newNode = GetNode(item); currPtr-InsertAfter(newNode); / 删除链表的第一个节点template void Dele

11、teFront(Node* & head) Node *p = head; if (head != NULL) head = head-NextNode（ ）; delete p; / 删除链表中第一个数据域等于key的节点template void Delete (Node* & head, T key) Node *currPtr = head, *prevPtr = NULL; if (currPtr = NULL) return; while (currPtr != NULL & currPtr-data != key) prevPtr = currPtr; c

12、urrPtr = currPtr-NextNode（ ）; if (currPtr != NULL) if(prevPtr = NULL) head = head-NextNode（ ）; else prevPtr-DeleteAfter（ ）; delete currPtr; / 在有序链表中插入一个节点template void InsertOrder(Node* & head, T item) Node *currPtr, *prevPtr, *newNode; prevPtr = NULL; currPtr = head; while (currPtr != NULL) if

13、(item data) break; prevPtr = currPtr; currPtr = currPtr-NextNode（ ）; if (prevPtr = NULL) InsertFront(head,item); else newNode = GetNode(item); prevPtr-InsertAfter(newNode); /清空链表-删除链表中的所有节点template void ClearList(Node * &head) Node *currPtr, *nextPtr; currPtr = head; while(currPtr != NULL) nextP

14、tr = currPtr-NextNode（ ）; delete currPtr; currPtr = nextPtr; head = NULL;#endif / NODE_LIBRARY27从键盘输入10个整数，用这些整数值作为结点数据，生成一个链表，按顺序输出链表中结点的数值。然后从键盘输入一个待查找整数，在链表中查找该整数，若找到则删除该整数所在的结点（如果出现多次，全部删除），然后输出删除结点以后的链表。在程序结束之前清空链表。9-5.cpp顺序访问线性群体#include #include 9_3.h#include 9_4.hvoid main(void) Node *head =

15、 NULL, *prevPtr, *delPtr; int i, key, item; for (i=0;i item; InsertFront(head, item); cout List: ; PrintList(head,noNewline); cout endl; cout key; prevPtr = head; while (Find(head,key,prevPtr) != NULL) if(prevPtr = NULL) head = head-NextNode（ ）; else delPtr=prevPtr-DeleteAfter（ ）; delete delPtr; cou

16、t List: ; PrintList(head,noNewline); cout endl; ClearList(head);30/9_6.h#ifndef LINKEDLIST_CLASS#define LINKEDLIST_CLASS#include #include #ifndef NULLconst int NULL = 0;#endif / NULL#include 9_3.h顺序访问线性群体template class LinkedList private: Node *front, *rear; Node *prevPtr, *currPtr; int size; int po

17、sition; Node *GetNode(const T& item, Node *ptrNext=NULL); void FreeNode(Node *p); void CopyList(const LinkedList& L); public: LinkedList(void); LinkedList(const LinkedList& L); LinkedList(void); LinkedList& operator= (const LinkedList& L); int ListSize(void) const; int ListEmpty(

18、void) const; void Reset(int pos = 0); void Next(void); int EndOfList(void) const; int CurrentPosition(void) const; void InsertFront(const T& item); void InsertRear(const T& item); void InsertAt(const T& item); void InsertAfter(const T& item); T DeleteFront(void); void DeleteAt(void);

19、 T& Data(void); void ClearList(void);#endif / LINKEDLIST_CLASS34#include #include 9_6.h#include 9_6.cppvoid main(void) LinkedList Link; int i, key, item; for (i=0;i item; Link.InsertFront(item);顺序访问线性群体 cout List: ; Link.Reset（ ）; while(!Link.EndOfList（ ）) cout Link.Data（ ） ; Link.Next（ ）; cout

20、endl; cout key; Link.Reset（ ）; while (!Link.EndOfList（ ）) if(Link.Data（ ） = key) Link.DeleteAt（ ）; Link.Next（ ）; cout List: ; Link.Reset（ ）; while(!Link.EndOfList（ ）) cout Link.Data（ ） ; Link.Next（ ）; cout endl;37栈是只能从一端访问的线性群体，可以访问的这一端称栈顶，另一端称栈底。ana2a1入栈出栈栈顶栈底38特殊的线性群体栈main调fun(参数)结束fun(参数)返回参数当前现场

21、返回地址入栈当前现场返回地址出栈参数出栈当前现场 返回地址39ba/a/b+c*d(a)t1+a/b+c*dt1=a/b(b)dct1*+a/b+c*d(c)t3a/b+c*dt3=t1+t2(e)t2t1+a/b+c*dt2=c*d(d)特殊的线性群体栈40l栈空栈中没有元素l栈满栈中元素个数达到上限l一般状态栈中有元素，但未达到栈满状态特殊的线性群体栈栈顶ana1a0入栈出栈数组下标maxn10一般状态栈顶入栈出栈数组下标初始状态（栈空）maxn10栈顶amaxana1a0入栈出栈数组下标maxn10栈满状态42l初始化l入栈l出栈l清空栈l访问栈顶元素l检测栈的状态（满、空）特殊的线性群

22、体栈43/9-8.h#ifndef STACK_CLASS#define STACK_CLASS#include #include const int MaxStackSize = 50; 特殊的线性群体栈template class Stack private: T stacklistMaxStackSize; int top; public: Stack (void); void Push (const T& item); T Pop (void); void ClearStack(void); T Peek (void) const; int StackEmpty(void) c

23、onst; int StackFull(void) const;/类的实现略45l例9.9 一个简单的整数计算器实现一个简单的整数计算器，能够进行加、减、乘、除和乘方运算。使用时算式采用后缀输入法，每个操作数、操作符之间都以空白符分隔。例如，若要计算3+5则输入3 5 +。乘方运算符用表示。每次运算在前次结果基础上进行，若要将前次运算结果清除，可键入c。当键入q时程序结束。l9-9.h 9-9.cpp特殊的线性群体栈/9_9.h#include #include #include #include enum Boolean False, True;#include 9_8.h class Ca

24、lculator private: Stack S; void Enter(int num); Boolean GetTwoOperands(int& opnd1, int& opnd2); void Compute(char op); public: Calculator(void) void Run(void); void Clear(void); ;void Calculator:Enter(int num) S.Push(num); Boolean Calculator:GetTwoOperands (int& opnd1, int& opnd2) if

25、 (S.StackEmpty（ ）) cerr Missing operand! endl; return False; opnd1 = S.Pop（ ）; if (S.StackEmpty（ ）) cerr Missing operand! endl; return False; opnd2 = S.Pop（ ）; return True;void Calculator:Compute(char op) Boolean result; int operand1, operand2;result = GetTwoOperands(operand1, operand2); if (result

26、= True) switch(op) case +: S.Push(operand2+operand1); break; case -: S.Push(operand2-operand1); break; case *: S.Push(operand2*operand1); break; case /: if (operand1 = 0) cerr Divide by 0! endl; S.ClearStack（ ）; else S.Push(operand2/operand1); break; case : S.Push(pow(operand2,operand1); break;cout=S.Peek（ ） c, *c != q) switch(*c) case c: S.ClearStack（ ）; break; case -: if (strlen(c)1) Enter(atoi(c); else Compute(*c); break; case +: case *: case /: case : Compute(*c); break; default: Enter(atoi(c); break; void Calculator:Clear(void)