下载文档原格式
第4章串串：限定数据元素类型的线性表。
1 逻辑结构1.1 定义位串：数据元素属于{0,1}ASCII码串: 数据元素属于ASCII码字符集。
数字串：数据元素属于整数集合2 顺序串///////////////////////////////// // 项目路径：7动态顺序串/////////////////////////////////2.2 构造/析构（测试函数Test1）template <class T>String<T>:: String( ){ m_Data=NULL; m_Size=m_Length=0; }template <class T>String<T>::String(T a[], int n){ m_Size = m_Length = n;m_Data = new T[m_Size];if(!m_Data) throw "内存不够，上溢";for(int i=0; i<m_Length; i++)m_Data[i]=a[i];}template <class T>String<T>::String(String &s) // 拷贝构造函数{ m_Size = m_Length = s.m_Length;m_Data = new T[m_Size];if(!m_Data) throw "内存不够，上溢";for(int i=0; i<m_Length; i++)m_Data[i]=s.m_Data[i];}template <class T>String<T>:: ~String( ){ delete []m_Data; }2.3 比较（测试函数Test2）// 重载<template <class T>bool String<T>::operator<(String &s){ for(int i=0; i<m_Length && i<s.m_Length; i++) { if(m_Data[i]<s.m_Data[i]) return true;if(m_Data[i]>s.m_Data[i]) return false;}if(m_Length<s.m_Length) return true;return false;}// 重载==template <class T>bool String<T>::operator==(String &s){ for(int i=0; i<m_Length && i<s.m_Length; i++) if(m_Data[i]!=s.m_Data[i]) return false; if(m_Length==s.m_Length) return true;return false;}2.4 取子串、连接（测试函数Test3）// 取子串template <class T>String<T> String<T>::Substr(int pos,int len) { if(pos+len>m_Length) // 预防子串长度越界len=m_Length-pos;String<T> s;s.m_Length=s.m_Size=len;s.m_Data = new T[s.m_Size];if(!s.m_Data) throw "内存不够，上溢";for(int i=0; i<len; i++)s.m_Data[i]=m_Data[pos+i];return s;}// 连接stemplate <class T>void String<T>::Concat(String s){ if(m_Length+s.m_Length > m_Size) // 空间不够ReNew(m_Length+s.m_Length);for(int i=0; i<s.m_Length; i++)m_Data[m_Length+i] = s.m_Data[i];m_Length += s.m_Length;}// 重新分配串的存储空间template <class T>void String<T>::ReNew(int size){ T *p=new T[size]; // 重新申请空间 m_Size=size;for(int i=0; i<m_Length; i++) // 数据迁移p[i]=m_Data[i];delete []m_Data; // 释放原串空间 m_Data = p;}2.5 插入、删除（测试函数Test4）// 第i个位置上插入stemplate <class T>void String<T>::Insert(int pos, String s){ if(m_Length+s.m_Length > m_Size) // 空间不够 ReNew(m_Length+s.m_Length);for(int i=m_Length-1; i>=pos; i--) // 向后移位 m_Data[i+s.m_Length] = m_Data[i];for(i=0; i<s.m_Length; i++)m_Data[pos+i] = s.m_Data[i];m_Length += s.m_Length;}// 删除子串template <class T>void String<T>::Delete(int pos,int len){ for(int i=pos+len; i<m_Length; i++) // 向前移位 m_Data[i-len] = m_Data[i];m_Length -= len;}2.6 顺序串的评价优点：访问子串方便，缺点：空间大小不灵活，插入、删除费时。
