《线性表顺序表稀疏矩阵字符串PPT课件》由会员分享，可在线阅读，更多相关《线性表顺序表稀疏矩阵字符串PPT课件（114页珍藏版）》请在金锄头文库上搜索。
1、n n线性表n n顺序表 n n稀疏矩阵n n字符串一、线性表一、线性表线性表性表 一一样数据数据类型的元素的有限序列型的元素的有限序列 叫叫线性表。性表。 a1, a2, ,an-1, ana1为首元，首元，an为末元，末元， n叫叫线性表的性表的长度度 ai的后的后继是是ai+1, i=1, ,n-1. an没有后没有后继。ai的前的前驱是是ai-1, i=2, ,n. a1没有前没有前驱。ai可以是根本数据可以是根本数据类型也可以是型也可以是struct 类型。型。没有数据的没有数据的线性表叫空表。空表的性表叫空表。空表的长度度n=0。a1a2a3a4a5a6线性表是最简单的也是最根本的
2、数据构造。线性表可以用来构造字符串，集合，栈，队列，用来排序。线性表可以顺序表示用一组地址延续的存储单元一次存储数据元素。线性表也可以用线性链表表示。二、二、顺序表序表线性表的性表的顺序序表示表示 可以用通用数组定义通用线性表。通用数组是可变长度的数组，也叫平安数组。类模版 通用数据类型/array.h 例. 通用数组 笼统数组类型 template class Array T *alist; /指针数据 表示一个数组 int size; /表示数组长度 public: Array(int s=50) /构造函数 Array(const Array&X); /拷贝构造函数 Array( )de
3、lete element; /析构函数 Array&operator=(const Array&X);/ 赋值函数重载 T& operator (int i)； /一元运算 重载 下标函数 operator T*( )const; /强迫类型转换,将当前 /对象变成指向它的首地址的指针， int ArraySize( )const; /取数组长 void Resize(int sz); /数组长重定义 friend ostream& operator(ostream&, const Array&); /输出操作重载 ；#include #include templatetemplateclas
4、s SeqListclass SeqList Arraylistitem; /list storage array Arraylistitem; /list storage array int size; int size; public: public: SeqList(void); / constructor SeqList(void); / constructor构造函数构造函数 / list access methods / list access methods 线性表的访问操作线性表的访问操作 int ListSize(void) const; / int ListSize(voi
5、d) const; /取线性表的长取线性表的长 int ListEmpty(void)const; / int ListEmpty(void)const; /问表能否空表问表能否空表 int Find (T& item) const; / int Find (T& item) const; /查找一个元素查找一个元素 T GetData(int pos) const; / T GetData(int pos) const; /取线性表中元素取线性表中元素/ list modification methods/ list modification methods线性表的修正操作线性表的修正操作
6、void Insert(const T& item);/ void Insert(const T& item);/表尾插入元素表尾插入元素 void Insert(const T& item void Insert(const T& item，int i);int i); / / 在第在第i i个位插入一个新元素个位插入一个新元素 void Delete(const T& item);/ void Delete(const T& item);/删除一个元素删除一个元素 T DeleteFront(void); / T DeleteFront(void); /删除首元删除首元 void Clea
7、rList(void); / void ClearList(void); /清空清空;/ constructor. set size to 0/ constructor. set size to 0templatetemplateSeqList:SeqList(void): SeqList:SeqList(void): listitem(size),size(0)listitem(size),size(0) / return number of elements in list/ return number of elements in listtemplatetemplateint int
8、SeqList:ListSize(void) SeqList:ListSize(void) constconst return size; return size; / tests for an empty list/ tests for an empty listtemplatetemplateint int SeqList:ListEmpty(void) SeqList:ListEmpty(void) constconst return size = 0; return size = 0; / clears list by setting size to 0/ clears list by
9、 setting size to 0templatetemplatevoid SeqList:ClearList(void)void SeqList:ClearList(void) size = 0; size = 0; / / Take Take item item as as key key and and search search the the list. list. /return True if item is in the list and /return True if item is in the list and / false otherwise. If found,
10、assign the list / false otherwise. If found, assign the list / element to the reference parameter item./ element to the reference parameter item.templatetemplateint SeqList:Find(T& item) constint SeqList:Find(T& item) const int i = 0; int i = 0; if (ListEmpty()return 0; if (ListEmpty()return 0; / re
11、turn False when list empty / return False when list emptywhile(isize &!(item=listitemi)while(isize &!(item=listitemi) i+; i+; if (i size) if (i size) item = listitemi; item = listitemi; / assign list element to item / assign list element to item return 1; / return True return 1; / return True else e
12、lse return 0; / return false return 0; / return false / insert item at the rear of the list. / insert item at the rear of the list. templatetemplatevoid SeqList:Insert(const T& item)void SeqList:Insert(const T& item) / /假设超长，扩展内存假设超长，扩展内存 if (size+1 listitem.ListSize( ) if (size+1 listitem.ListSize(
13、 ) listitem.Resize(size+1); listitem.Resize(size+1); / index of rear is current value of / index of rear is current value of /size. insert at rear /size. insert at rear listitemsize = item; listitemsize = item; size+; / increment list size size+; / increment list size template /template /在第在第i i位插入位
14、插入void SeqList:Insert(const T& item, int i)void SeqList:Insert(const T& item, int i) if (i0) if (i0)cout“ican not be negative!; return;cout=size)Insert(item);return; if(i=size)Insert(item);return; if (size+1 listitem.ListSize( ) if (size+1 listitem.ListSize( ) listitem.Resize(size+1); listitem.Resiz
15、e(size+1); int k=size-1; int k=size-1; /shift /shift the the tail tail of of the the listlist /to /to the the right right one one positionposition while (k = i) while (k = i) listitemk+1 = listitemk; listitemk+1 = listitemk; k-; k-; listitemi = item; listitemi = item; size+; / increament list size s
16、ize+; / increament list size /search for item in the list /search for item in the list /and delete it if found/and delete it if foundtemplatetemplatevoid SeqList:Delete(const T& item)void SeqList:Delete(const T& item) int i = 0; int i = 0; / search for item / search for item while while (i (i size s
17、ize & & !(item !(item = = listitemi)listitemi) i+; i+; if if (i (i size) size) / / successful successful if if i i sizesize / shift the tail of the list / shift the tail of the list /to the left one position/to the left one position while (i size-1) while (i size-1) listitemi = listitemi+1; listitem
18、i = listitemi+1; i+; i+; size-; / decreament size size-; / decreament size /delete /delete element element at at front front of of list list and and return return / / its its value. value. terminate terminate the the program program with with / an error message if the list is empty./ an error messag
19、e if the list is empty. template template T SeqList:DeleteFront(void) T SeqList:DeleteFront(void) T frontItem; T frontItem; / list is empty if size = 0 / list is empty if size = 0 if (size = 0) if (size = 0) cerr cerr Attempt Attempt to to delete delete the the front /front / of of an an empty empty
20、 list! list! endl;endl; exit(1); exit(1); frontItem = listitem0; frontItem = listitem0; / get value from position 0. / get value from position 0. Delete(frontItem); Delete(frontItem); / / delete delete the the first first item item and and shift termsshift terms return frontItem; return frontItem; /
21、 / return return the the original original valuevalue / return value at position pos in list. / return value at position pos in list. / if pos is not valid list position,/ if pos is not valid list position,/ teminate program with an error message./ teminate program with an error message.templatetemp
22、lateT SeqList:GetData(int pos) constT SeqList:GetData(int pos) const / terminate program if pos out of range / terminate program if pos out of range if (pos = size) if (pos = size) cerr pos is out of range! endl; cerr pos is out of range! endl; exit(1); exit(1); return listitempos; return listitempo
23、s; 测试测试 #include “ iostream.h #include “aseqlist.hvoid main(void) SeqList a,b; int x; for(int i=0;i20;i+) a.Insert(i); coutinput isx; b.Insert(x+1); for(i=0;i20;i+) couta.GetData(i) ; coutendl; for(i=0;i20;i+) for(i=0;i20;i+) coutb.GetData(i) ; coutb.GetData(i) ; coutendl; coutendl; a.Insert(99,0);
24、a.Insert(98,10); a.Insert(99,0); a.Insert(98,10); a.Insert(97,20); a.Insert(96,30); a.Insert(97,20); a.Insert(96,30); int k=a.ListSize( ); int k=a.ListSize( ); for(i=0;ik;i+) for(i=0;ik;i+) couta.GetData(i) ; couta.GetData(i) ; coutendl; coutendl; 顺序表运用的例： 1. 用顺序表做插入,选择排序. 2. 合并两个已排序的线性表 3. 用顺序表做集合:
25、 只插入不反复的元素 4. 求两个集合的交合并 5. 表示一个多项式 6. 求多项式的和差积商,微分,积分 7. 存储一个矩阵, 求矩阵的和,积,逆顺序线性表复杂度分析顺序线性表复杂度分析 1.从已建立的顺序表中“取表长 ，“取第i个元素的复杂性是O(1),2.2. 在表长n的顺序表第i位前插入一个元素，要把表尾n-i+1个元素后移一格。3. 假设每一位都插入一个数，从第1位到末尾第n+1位，总挪动次数是：4. i=1i=n+1(n-i+1)=1+2+n=n*(n+1)/25. 平均复杂度为O(n/2).6.3. 删除第i位元素，要把表尾n-i个元素前移一格。假设每一位都删除一个数，从第1位到
26、末尾第n位，总挪动次数是：7. i=1i=n+1(n-i)=1+2+(n-1)=n*(n-1)/28. 平均复杂度为O(n-1)/2). 一个阶数很高的矩阵中假设有许多相等的元素，或零元素，成为特殊矩阵。 对特殊矩阵可以进展紧缩存储三、稀疏矩阵三、稀疏矩阵特殊矩阵特殊矩阵 对称矩阵 上下三角矩阵 对角矩阵 稀疏矩阵对称矩阵对称矩阵 矩阵 A=(aij)n,n aij= aji , 0i,jn 每一对元素分配一个存储空间，可以 将n2个元素存储到n(n+1)/2个空间中下三角矩阵下三角矩阵 a11 a21a22 a31a32 a33 an1an2 an3 ann 1+2+3+ +n=n(n+1)
27、/2T sn(n+1)/2; 0 1 2 3 4 5 6 ksa11a21a22a31a32a33 k=i(i-1)/2+j-1; ij; k=j(j-1)/2+i-1; ij. s12=aij=aji; i=4, j=3s0=a11; s1=a21; sk=aij对角矩阵对角矩阵 a11 a12 a21 a22 a23 an-1n ann-1 anna11 a12a21a22a23sksk=aij; k=3(i-1)+j; j=k%3; i=(k-j)/3 稀疏矩阵稀疏矩阵 Sparse Matrixm*n阶矩阵 A=(aij)mn 中有t个非零元素, 假设 =t/(m*n)5%,称A为稀疏
28、矩阵 0 12 9 0 0 0 0 0 0 0 0 0 0 0 -3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 0 15 0 0 -7 0 0 0/smatrix.dat 6 7 8 1 2 12 1 3 9 3 1 3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7稀疏矩阵的存储稀疏矩阵的存储 row col elem 1 2 12 1 3 9 3 1 3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7templateclass Triple public: int row, col; T elem; Set
29、Val(int r,int c,T d) elem=d;row=r;col=c; ;稀疏矩稀疏矩阵元素的元素的类TRiple稀疏矩阵类的定义稀疏矩阵类的定义#define MAXSIZE 500templateclass SparseMatrix Triple dataMAXSIZE+1; int mu, nu, tu; /行数、列数、元素个数 public: SparseMatrix( )mu=nu=tu=0; SparseMatrix(char*filename); SparseMatrix Transpose( ); SparseMatrix Add(SparseMatrix b); S
30、parseMatrix Muliply(SparseMatrix b); void print( )const; ;templateSparseMatrix:SparseMatrix(char *filename) ifstream fin; int i,r,c; T d; fin.open(filename, ios:in | ios:nocreate); if (!fin) cerr The maze data file filename cannot be opened! munutu; for (i = 1; i r cd; datai.SetVal(r,c,d); fin.close
31、( );矩矩阵的的转置置 T=Mfor(col=1;col=nu;col+) for(row=1;row=mu;row+) Tcolrow=Mrowcol时间复杂度O(mu*nu)Mrow col elem 1 2 12 1 3 9 3 1 3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 Mrow col elem 2 1 12 3 1 9 1 3 3 6 3 14 3 4 24 2 5 18 1 6 15 4 6 -7Mrow col elem 1 2 12 1 3 9 3 1 3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7Mrow col
32、 elem 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14稀疏矩稀疏矩阵的的转置置 T=M 算法算法5.1template SparseMatrix SparseMatrix : Transpose( )SparseMatrix temp; int i, j, k=1; temp.mu=nu; temp.nu=mu; temp.tu=tu; if(tu)for(i=1;i=nu;+i) for(j=1;j=tu;+j) if(dataj.col=i) temp.datak.row=dataj.col; temp.datak.col=
33、dataj.row; temp.datak.elem=dataj.elem; k+; return temp; 稀疏矩阵的转置的时间复杂度稀疏矩阵的转置的时间复杂度 O(nu*tu)假设tunu*mu O(nu*tu)=O(mu*nu*nu)不是一个好算法！该当改良！ 快速转置快速转置 依次逐个对号入座依次逐个对号入座 Mrow col elem 1 2 12 1 3 9 3 1 3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7Mrow col elem 2 1 12 3 1 9先求出M中每一列即M中每一行元素的个数numcol，确定M每行起始位置cpotcol。快速转
34、置快速转置Mrow col elem 1 2 12 1 3 9 3 1 3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 col 1 2 3 4 5 6 7numcolcpotcol 1 2 3 2 5 2 7 1 8 0 8 1 9 row colelemcpot1cpot2cpot3cpot4cpot62 1 123 1 91 3 96 3 14快速转置算法快速转置算法5.2template SparseMatrix SparseMatrix :Transpose( )SparseMatrix temp; int i, j, k； int*num=new intnu
35、+1; int* cpot=new intnu+1; cpot1=1; temp.mu=nu; temp.nu=mu;temp.tu=tu; if(tu)for(i=1;i=nu;+i)numi=0; for(i=1;i=tu;+i)+numdatai.col; for(i=1;inu;+i)cpoti+1=cpoti+numi; for(i=1;i=tu;+i)j=datai.col;k=cpotj; temp.datak.row=j; temp.datak.col=datai.row; temp.datak.elem=datai.elem; +cpotj; return temp; 时间复
36、复杂性性O(nu+tu)稀疏矩阵的加法稀疏矩阵的加法template SparseMatrix SparseMatrix: Add(SparseMatrix b )SparseMatrix temp; if(mu!=b.mu|nu!=b.nu) cerr“error end;return temp; temp.mu=mu; temp.nu=nu; int i=1, j=1, k=1; while(i=tu|j=b.tu) if(datai.rowb.dataj.row) | (datai.row=b.dataj.row) & (datai.colb.dataj.col) temp.datak=
37、datai; k+;i+; else if(datai.row=b.dataj.row)& (datai.col=b.dataj.col)temp.datak.row=datai. row; temp.datak.col=datai.col; temp.datak.elem=datai. elem+ b.dataj. elem k+;i+;j+;else temp.datak=b.dataj;k+;j+; temp.tu=k-1; return temp; 矩阵的乘法矩阵的乘法Amp*Bpn (aij)*(bij)=(1kpaik*bkj) 2 0 0 -1 0 1 0 3 0 0 1 0 1
38、 0 1 0 0 -1 0 0 0 2 0 1 3 0 1 0a11*b11 a11*b12 a11*b13 a11*b14a12*b21 a12*b22 a12*b23 a12*b24a13*b31 a13*b32 a13*b33 a13*b34a14*b41 a14*b42 a14*b43 a14*b44 时间复复杂度度mpn稀疏矩阵的乘法稀疏矩阵的乘法Arow col elem 1 2 12 1 3 9 3 1 3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7Brow col elem rposrow 1 1 8 rpos1= 1 2 3 4 rpos2= 2 3
39、 2 1 rpos3=3 3 5 -1 4 1 2 rpos4=5 4 4 -3 5 1 5 rpos5=7 6 2 -2 rpos6=8template SparseMatrix SparseMatrix: Multiply(SparseMatrix b )SparseMatrix temp; if(nu!=b.mu) cer“error end;return temp; temp.mu=mu;temp.nu=b.nu; int *num=new intb.mu+1; int *rpos=new intb.mu+1; rpos1=1; T ctempb.nu+1; for(int i=1;i
40、=b.mu;i+) numi=0; for(i=1;i=b.tu;i+)+numb.datai.row; for(i=1;i=b.mu;i+)rposi+1=rposi+numi; int k=1,j, r,c,t=0; while(k=tu) for( j=1;j=b.nu;j+) ctempj=0; r=datak.row; while(k=tu&datak=r) c=datak.col; for(i=rposc;irposc+1;i+;) j=b.datai.col; ctempj=ctempj+datak.elem*b.datai.elem; k+; for(j=1;j=b.nu;j+
41、) if(ctempj!=0) t+; temp.datat.row=r; temp.datat.col=j; temp.datat.elem=ctempj; temp.tu=t; return temp; 稀疏矩阵乘法的时间复杂度稀疏矩阵乘法的时间复杂度 O(tu.*b.nu)稀疏矩阵的输出稀疏矩阵的输出template void SparseMatrix : print( )constint i, j,k=1; for(i=1;i=mu;i+) for(j=1;j=nu;j+) if (i=datak.row)&(j=datak.col) coutsetw(4)datak.elem; k+
42、; else coutsetw(4)0; coutendl; 串串串-由字符组成的线性表，也叫 字符串串是非数值计算算法处置的主要对象在方式匹配，程序编译，数据处置等领域有广泛的运用串类型的定义串类型的实现串的方式匹配C言语中有关串的函数#include strlen(char *s);strcpy(char *s, char *t);strcmp(char*s, char *t);strcat(char *s, char *t);strchr(char*s, char c);strrchr(char*s, char c);没有插入，删除不好记，不好用串类型的定义串类型的定义1。用数组定义串
43、#define MAXSTRLEN 255 typedef unsigned SStringMAXSTRLEN+1; Sstring s1, s2; /用s10, s20存储各自的长度2。堆分配存储表示。堆分配存储表示 typedef struct char *ch; int length; HString; HString s; s.length=15; s.ch=new chars.length; 3.块链存储块链存储 #define CHUNKSIZE 80typedef struct Chunk char chCHUNKSIZE; Chunk *next; ；typedef struc
44、t Chunk *head,*tail; int curlen; LString; /定长字符串作元素的线性链表堆分配存堆分配存储串串类的的实现/“strclass.h#define STRING_CLASS#include #include #include #ifndef NULLconst int NULL = 0;#endif / NULLconst int outOfMemory = 0, indexError = 1;#ifndef STRING_CLASSclass String char *str; int size; void Error(int errorType, int
45、 badIndex = 0) const; public: String(char *s = “ ); String(const String& s); String(void); String& operator= (const String& s); String& operator= (char *s); int operator= (const String& s) const; int operator= (char *s) const; friend int operator= (char *str, const String& s); int operator!= (const
46、String& s) const; int operator!= (char *s) const; friend int operator!= (char *str, const String& s); int operator (const String& s) const; int operator (char *s) const; friend int operator (char *str, const String& s); int operator= (const String& s) const; int operator= (char *s) const; friend int
47、 operator (const String& s) const; int operator (char *s) const; friend int operator (char *str, const String& s); int operator= (const String& s) const; int operator= (char *s) const; friend int operator= (char *str, const String& s); String operator+ (const String& s) const; String operator+ (char
48、 *s) const; friend String operator+ (char *str,const String& s); void operator+= (const String& s); void operator+= (char *s);/ String functions int Find(char c, int start) const; int FindLast(char c) const; String Substr(int index, int count) const; void Insert(const String& s, int index); void Ins
49、ert(char *s, int index); void Remove(int index, int count); char& operator (int n); operator char* (void) const; / String I/O friend ostream& operator (istream& istr, String& s); int ReadString(istream& is=cin, char delimiter=n); int Length(void) const; int IsEmpty(void) const; void Clear(void);void
50、 String:Error(int errorType, int badIndex) const if (errorType = outOfMemory) cerr Memory exhausted! endl; else cerr Index badIndex out of range endl; exit(1);/ constructor. allocate memory and copy in a C+StringString:String(char *s) size = strlen(s) + 1; str = new char size; / terminate program if
51、 memory is exhausted. if (str = NULL) Error(outOfMemory); strcpy(str,s);/ copy constructorString:String(const String& s) / current object as length of s size = s.size; / allocate same amount of space as s uses. copy string str = new char size; if (str = NULL) Error(outOfMemory); strcpy(str, s.str);/
52、 destructorString:String(void) delete str;/ assignment operator. String to StringString& String:operator= (const String& s) if (s.size != size) delete str; str = new char s.size; if(str = NULL) Error(outOfMemory); / assign size to be size of s size = s.size; / copy s.str and return reference to curr
53、ent object strcpy(str, s.str); return *this;/ assignment operator. C+String to StringString& String:operator= (char *s) int slen = strlen(s) + 1; / if sizes differ, delete current string and reallocate if (slen != size) delete str; str = new char slen; if (str = NULL) Error(outOfMemory); size = slen
54、; strcpy(str, s); return *this;/ all relational operators use C+ string function strcmp/ String = Stringint String:operator= (const String& s) const return strcmp(str,s.str) = 0;/ String = C+Stringint String:operator= (char *s) const return strcmp(str,s) = 0;/ C+String = String. this is a friend fun
55、ction, since/ the left operand is a C+String.int operator= (char *str, const String& s) return strcmp(str,s.str) = 0;/ String != Stringint String:operator!= (const String& s) const return strcmp(str,s.str) != 0;/ String != C+Stringint String:operator!= (char *s) const return strcmp(str,s) != 0;/ C+S
56、tring != Stringint operator!= (char *str, const String& s) return strcmp(str,s.str) != 0;/ String Stringint String:operator (const String& s) const return strcmp(str,s.str) 0;/ String C+Stringint String:operator (char *s) const return strcmp(str,s) 0;/ C+String Stringint operator (char *str, const S
57、tring& s) return strcmp(str,s.str) 0;/ String = Stringint String:operator= (const String& s) const return strcmp(str,s.str) = 0;/ String = C+Stringint String:operator= (char *s) const return strcmp(str,s) = 0;/ C+String = Stringint operator= (char *str, const String& s) return strcmp(str,s.str) Stri
58、ngint String:operator (const String& s) const return strcmp(str,s.str) 0;/ String C+Stringint String:operator (char *s) const return strcmp(str,s) 0;/ C+String Stringint operator (char *str, const String& s) return strcmp(str,s.str) 0;/ String = Stringint String:operator= (const String& s) const ret
59、urn strcmp(str,s.str) = 0;/ String = C+Stringint String:operator= (char *s) const return strcmp(str,s) = 0;/ C+String = Stringint operator= (char *str, const String& s) return strcmp(str,s.str) = 0;/ concatention: String + StringString String:operator+ (const String& s) const String temp; int len; d
60、elete temp.str; len = size + s.size - 1; temp.str = new char len; if (temp.str = NULL)Error(outOfMemory); temp.size = len; strcpy(temp.str,str); / copy str to temp strcat(temp.str, s.str); / concatenate s.str return temp; / return temp/ concatention: String + C+String. same algorithm as/ String + St
61、ring, with a C+String as the right operandString String:operator+ (char *s) constString temp; int len; delete temp.str; len = size + strlen(s); temp.str = new char len; if (temp.str = NULL) Error(outOfMemory); temp.size = len; strcpy(temp.str,str); strcat(temp.str, s); return temp;/ concatention: C+
62、String + String. same algorithm as/ String + String, with a C+String as the left operandString operator+ (char *cs, const String& s) String temp; int len; delete temp.str; len = strlen(cs) + s.size; temp.str = new char len; if (temp.str = NULL) s.Error(outOfMemory); temp.size = len; strcpy(temp.str,
63、 cs); strcat(temp.str, s.str); return temp;/ concatenate and assign: String += String/ the current object is modifiedvoid String:operator+= (const String& s) char *tempstr; int len; len = size + s.size - 1; tempstr = new char len; if (tempstr = NULL) Error(outOfMemory); strcpy(tempstr,str); strcat(t
64、empstr, s.str); delete str; str = tempstr; size = len;void String:operator+= (char *s) int len; char *tempstr; len = size + strlen(s); tempstr = new char len; if (tempstr = NULL) Error(outOfMemory); strcpy(tempstr,str); strcat(tempstr, s); delete str; str = tempstr; size = len;int String:Find(char c
65、, int start) const int ret; char *p; p = strchr(&strstart, c); if (p != NULL) ret = int(p-str); else ret = -1; return ret;/ return index of last occurrence of c in stringint String:FindLast(char c) const int ret; char *p; / use C+ library function strrchr. returns pointer to/ the last occurrence of
66、a character in the string p = strrchr(str, c); if (p != NULL) ret = int(p-str); / compute index else ret = -1; / return -1 on failure return ret; int charsLeft = size-index-1, i; String temp; char *p, *q; if (index = size-1) return temp; if (count charsLeft) count = charsLeft; delete temp.str; temp.
67、str = new char count+1; if (temp.str = NULL) Error(outOfMemory); for(i=0,p=temp.str,q=&strindex;i count;i+) *p+ = *q+; *p = 0; temp.size = count+1; return temp;String String:Substr(int index, int count) constvoid String:Insert(const String& s, int index) int newsize, length_s = s.size-1, i; char *ne
68、wstr, *p, *q; newsize = size + length_s; newstr = new char newsize; if (newstr = NULL)Error(outOfMemory); for(i=0,p = newstr, q = str; i = index-1;i+) *p+ = *q+; strcpy(p,s.str); p += length_s; strcpy(p,&strindex); delete str; size = newsize; str = newstr; void String:Insert(char *s, int index) int
69、newsize, length_s = strlen(s), i; char *newstr, *p, *q; newsize = size + length_s; newstr = new char newsize; if (newstr = NULL) Error(outOfMemory); for(i=0,p = newstr, q = str;i = size-1) return; if (count charsLeft) count = charsLeft; newsize = size - count; newstr = new char newsize; if (newstr =
70、 NULL)Error(outOfMemory); for(i=0,p=newstr,q=str;i = index-1;i+) *p+ = *q+; q += count; strcpy(p,q); delete str; size = newsize; str = newstr;/ String index operatorchar& String:operator (int n) if (n = size-1) Error(indexError,n); return strn;/ pointer conversion operatorString:operator char* (void
71、) const return str;istream& operator (istream& istr, String& s)char tmp256; if (istr tmp) delete s.str; / delete existing string s.size = strlen(tmp) + 1; s.str = new char s.size; if (s.str = NULL) s.Error(outOfMemory); strcpy(s.str,tmp); return istr;ostream& operator (ostream& ostr, const String& s
72、) ostr s.str; return ostr;/ read characters from istrint String:ReadString (istream& istr, char delimiter) char tmp256; if (istr.getline(tmp, 256, delimiter) delete str; size = strlen(tmp) + 1; str = new char size; if (str = NULL)Error(outOfMemory); strcpy(str,tmp); return size-1; else return -1; /
73、return -1 on end of fileint String:Length(void) const return size-1;int String:IsEmpty(void) const return size = 1;void String:Clear(void) delete str; size = 1; str = new char size; if (str = NULL) Error(outOfMemory); str0 = 0;#endif / STRING_CLASS测试#include #pragma hdrstop#include strclass.h#define
74、 TF(b) (b) ? TRUE : FALSE)void main(void) String s1(STRING ), s2(CLASS), s3; int i; char c, cstr30; s3 = s1 + s2; cout s1 concatenated with s2 = s3 endl; cout Length of s2 = “ s2.Length( ) endl; cout The first occurrence of S in s2 = s2.Find(S,0) endl; cout The last occurrence of S in s2 is s2.FindL
75、ast(S) endl; cout “Insert OBJECT into s3 at position 7. endl; s3.Insert(OBJECT , 7); cout s3 endl; s1 = FILE1.S; for(i=0;i = A & c = Z) c += 32; / convert c to lower case s1i = c; cout The string FILE1.S converted to lower case is ; cout s1 endl; cout Test relational operators with strings ; cout s1
76、 = ABCDE s2 = BCF endl; s1 = ABCDE; s2 = BCF; cout s1 s2 is TF(s1 s2) endl; cout s1 = s2 is TF(s1 = s2) endl; cout Use operator char* ( ) to get s1 as a C+ string: ; strcpy(cstr, s1); cout cstr endl;/*STRING concatenated with CLASS = STRING CLASSLength of CLASS = 5The first occurrence of S in CLASS = 3The last occurrence of S in CLASS is 4Insert OBJECT into s3 at position 7.STRING OBJECT CLASSThe string FILE1.S converted to lower case is file1.sTest relational operators with strings s1 = ABCDE s2 = BCFs1 s2 is TRUEs1 = s2 is FALSEUse operator char* ( ) to get s1 as a C+ string: ABCDE*/
