第4章数组和字符串

Java字符串与数组问题及答案来源⾃《Java程序员⾯试笔试宝典》第四章 Java基础知识 4.5字符串与数组1、字符串创建与存储的机制是什么？Java中字符串声明与初始化主要有两种情况：(1)String s1 = new String("abc")与String s2 = new String("abc")语句执⾏String s1 = new String("abc")语句，字符串池中不存在"abc"，则会创建⼀个字符串常量"abc"，并将它添加到字符串常量池中，然后new String()会在堆中创建⼀个新的对象，s1指向堆中的String对象紧接着创建String s2 = new String("abc")语句，因为字符串常量池中已经有了字符串常量"abc"，所以不会再创建"abc"，直接new String()在堆中创建⼀个新的对象，然后使⽤s2指向这个对象s1与s2指向堆中的不同String对象，地址⾃然也不相同(2)String s1 = "abc"语句与String s2 = "abc"语句在JVM中存在着⼀个字符串常量池，其中保存了着很多String 对象，s1,s2引⽤的是同⼀个常量池中的对象。

当创建⼀个字符串常量时，例如String s1 = "abc"，会⾸先在字符串常量池中查找是否已经有相同的字符串被定义，若已经定义，则直接获取对其的引⽤，此时不需要创建字符串常量"abc"，如果没有定义，则⾸先创建字符串常量"abc"，然后把它加⼊到字符串池中，再将引⽤返回例⼦1：String s1 = new String("abc"); // 先查找常量区有⽆"abc"常量，若⽆则将其"abc"添加到常量区，再在堆中创建对象，将s1指向堆中的对象String s2 = new String("abc"); // 发现在常量区已经有了"abc"，在堆中创建对象，将s2指向堆中的对象例⼦2：String s1 = "abc"; // 在常量区⾥⾯创建⼀个"abc"字符串对象，s1获取对其的引⽤String s2 = "abc"; // 发现在常量区已经有了"abc"，s2直接获取对其的引⽤引申 - 对于String类型的变量s，赋值语句s=null和赋值语句s=""有什么区别？s=null，是指s不指向任何⼀个字符串；s=""中的s指向空字符串笔试题 - new String("abc")创建了⼏个对象？⼀个或两个，如果常量池中原来就有"abc"，那么只创建⼀个对象，否则创建两个对象2、==、equals和hashCode有什么区别？==：是运算符，⽤于⽐较两个变量是否相等。

第4章数组和字符串程序4.1 一维数组类#include <assert.h>template <class T>class Array1D{public:Array1D(int sz=0); //缺省时长度为0 ~Array1D(){ delete []elements; }T& operator [](int i)const; //取元素值 Array1D<T>&operator=(const Array1D<T> &r); //整体赋值friend istream &operator>>(istream &in, Array1D<T> &r);friend ostream &operator<<(ostream &out, const Array1D<T> &r);private:int size;T *elements; //指向T类型数组的指针};template <class T>Array1D<T>::Array1D(int sz){assert(sz>=0); //越界检查 size=sz;elements=new T[sz];}template <class T>T& Array1D<T>::operator [](int i)const{assert(i>=0&&i<size); //越界检查return elements[i];}template <class T>Array1D<T>& Array1D<T>::operator=(const Array1D<T> &r) //数组r整体赋值给this {if(this!=&r) { //防止自我赋值size=r.size;delete []elements; //释放原空间elements=new T[size]; //重新分配空间for(int i=0; i<size; i++)elements[i]=r.elements[i]; //复制元素}return *this;}template <class T>istream &operator>>(istream &in, Array1D<T> &r){cout<<"Intput array\n";for(int i=0; i<r.size; i++) in>>r.elements[i];return in;}template <class T>ostream &operator<<(ostream &out, const Array1D<T> &r){cout<<"Array=";for(int i=0; i<r.size; i++) out<<r.elements[i]<<' ';out<<endl;return out;}程序4.2应用一维数组类的主程序#include "array1d.h"void main(){Array1D<int> a(5),b(8);Array1D<int> c; //采用缺省长度0 cin>>a; cout<<"a "<<a;cin>>b; cout<<"b "<<b;cout<<"c "<<c;cout<<"a[0]="<<a[0]<<"; "<<"b[5]="<<b[5]<<endl;c=b; cout<<"c=b, c "<<c;b=a; cout<<"b=a, b "<<b;}程序4.3稀疏矩阵类template <class T>class SparseMatrix{public:SparseMatrix(int maxRowSize, int maxColSize){};~SparseMatrix(){};virtual void Add(const SparseMatrix <T> &B, SparseMatrix <T> &C) const;virtual void Mul(const SparseMatrix <T> &B, SparseMatrix <T> &C) const;virtual void Transpose(SparseMatrix <T> &B)const;private:int maxRows, maxCols;};程序4.4 Term结构template <class T>struct Terms{int row,col;T value;};程序4.5行三元组表示的稀疏矩阵的C++类template <class T>class SeqTriple{public:SeqTriple(int mSize);~SeqTriple(){ delete [] trip; };void Add(const SeqTriple<T> &B, SeqTriple<T> &C) const;void Mul(const SeqTriple<T> &B, SeqTriple<T> &C) const;void Transpose(SeqTriple<T> &B)const;friend istream &operator >>(istream &input, const SeqTriple <T> &);friend ostream &operator <<(ostream &output, const SeqTriple <T> &);private:int maxSize; //最大元素个数int m,n,t; //稀疏矩阵的行数、列数和非零元素个数 Term<T> *trip; //动态一维数组的指针};程序4.6稀疏矩阵的快速转置template <class T>void SeqTriple<T>::Transpose(SeqTriple<T>& B)const{ //将this①转置赋给Bint *num=new int[n]; int *k=new int[n]; //为num和k分配空间B.m=n; B.n=m; B.t=t;if (t>0){for (int i=0; i<n; i++) num[i]=0; //初始化numfor (i=0; i<t; i++) num[trip[i].col]++; //计算numk[0]=0;for(i=1; i<n; i++) k[i]=k[i-1]+num[i-1];//计算kfor(i=0; i<t; i++) { //扫描this对象的三元组表int j=k[trip[i].col]++; //求this对象的第i项在B中的位置jB.trip[j].row=trip[i].col; //将this对象的第i项转置到B的位置jB.trip[j].col=trip[i].row;B.trip[j].value=trip[i].value;}}delete [] num; delete [] k;}程序4.7字符串类#include <string.h>class String{public:String();String(const char *p);~String(){ delete [] str; };int Find(int i, String &P);private:int n; //当前串长char *str; //动态一维字符数组的指针};String::String(const char *p){n=strlen(p);str=new char[n+1];strcpy(str, p);}程序4.8 简单匹配算法int String::Find(int i, String &P){if (i<0 || i>n-1) { //越界检查cout<<"Out of bounds!"<<endl;return -1;}char *pp=P.str, //模式串指针pp指向第1个字符char *t=str+i; //主串指针t指向下标i的字符while (*pp!='\x0'&&i<=n-P.n) //pp未到串尾同时剩余字符数超过模式串长，则循环if (*pp++!=*t++) {pp=P.str; //模式串回到第1个字符t=str+(++i); //主串回到i+1的位置}if (*pp=='\0') return i; //若pp已到串尾，则匹配成功return -1;}程序4.9 KMP算法的C++程序(设串P的f值已求得)int String::FindKMP(int i, String &P){if (i<0 || i>n-1) { //越界检查cout<<"Out of bounds!"<<endl;return -1;}int j=0, m=P.n;while (i<n&&j<m)if (j==-1||str[i]==P.str[j]) {i++; j++; //相等或j=-1时,i、j均后移1个位置 }else j=P.f[j]; //到达失配点, j回溯到f[j]return ((j==m)?i-m:-1);}程序 4.10 失败函数的C++程序void String::Fail(){ // 计算失败函数int j=0,k=-1;f[0]=-1;while (j<n)if ((k==-1) || (str[j]==str[k])){j++; k++; //k==-1或str[j]==str[k]时，j,k各扩展1位，j无回溯f[j]=k; //求得的k存入f[j]}else k=f[k]; //str[j]不等于str[k]时，k回溯到f[k] }程序4.11改进的失败函数的C++程序void String::Fail (){int j=0,k=-1;f[0]=-1;while (j<n)if ((k==-1) || (str[j]==str[k])){j++; k++; //当k=-1或str[j]=str[k]时，j,k各扩展1位 if (str[j]==str[k]) f[j]=f[k]; //将字符p k和p j比较，若相等则将f[k]存入f[j] else f[j]=k; //否则求得的k存入f[j]}else k=f[k]; //str[j]不等于str[k]时，k回溯到f[k]，j无回溯}。

第4章 数组4.1内容概述本章主要介绍了数值数组和字符数组的定义、初始化、元素引用和数组数据的输入与输出，字符数组实现字符串、字符串函数的实现与调用。

指针数组与数组指针定义、元素引用。

利用一维数组实现如挑数、排序、求和等实际应用问题。

利用二维数组实现矩阵的应用问题。

利用字符数组实现字符串的各种操作。

本章知识结构如图4.1所示。

图4.1 第4章知识结构图考核要求：掌握一维数组、二维数组、字符数组和指针数组的定义和初始化；掌握数组元素存储地址计算；掌握数组元素的下标法、指针法引用；掌握字符数组与字符串的区别与联系；掌握有关字符串处理函数的使用方法；能利用一维数组、二维数组解决向量、矩阵等实际应用问题。

重点难点：本章的重点是一维数组、二维数组和字符数组的定义、初始化、元素引用，字符串处理函数的使用。

本章的难点是字符串与字符数组的区别，指针数组和数组元素的指针法引用。

核心考点：数组的定义、初始化和数组元素的引用方法，一维数组、二维数组和字符数组的实际应用，字符串的处理方法。

4.2 典型题解析【例4.1】以下对一维数组a 的定义中正确的是（ ）。

A. char a(10);B. int a[0..100];C. int a[5];D. int k=10;int a[k];解析：一维数组定义的一般形式为：类型标识符 数组名[常量表达式]其中，常量表达式可以是任意类型，一般为算术表达式，其值表示数组元素的个数，即数组长度。

答案：C【例4.2】以下对一维数组的定义中不正确的是（ ）。

A. double x[5]={2.0,4.0,6.0,8.0,10.0};数组数值数组 定义 初始化 元素引用 数组元素输入和输出 指针数组 定义初始化 应用字符数组 定义 初始化 元素引用 数组元素输入和输出B. int y[5]={0,1,3,5,7,9};C. char ch1[ ]={'1', '2', '3', '4', '5'};D. char ch2[ ]={'\x10', '\xa', '\x8'};解析：可以对一维数组的全部元素或部分元素赋初值。