第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'};解析：可以对一维数组的全部元素或部分元素赋初值。

return(0);}算法4.19 稀疏矩阵十字链表的查找算法4.1 稀疏矩阵常用的压缩存储方法有（ ）和（ ）两种。

4.2 设有一个10 × 10的对称矩阵A采用压缩方式进行存储，存储时以按行优先的顺序存储其下三角阵，假设其起始元素a00的地址为1，每个数据元素占2个字节，则a65的地址为（ ）。

4.3 若串S =“software”，其子串的数目为（ ）。

4.4 常对数组进行的两种基本操作为（ ）和（ ）。

4.5 要计算一个数组所占空间的大小，必须已知（ ）和（ ）。

4.6 对于半带宽为b的带状矩阵，它的特点是：对于矩阵元素a ij，若它满足（ ），则a ij = 0。

4.7 字符串是一种特殊的线性表，其特殊性体现在（ ）。

4.8 试编写一个函数，实现在顺序存储方式下字符串的strcompare（S1，S2）运算。

4.9 试编写一个函数，实现在顺序存储方式下字符串的replace（S，T1，T2）运算。

4.10 试编写一个函数，实现在链式存储方式下字符串的strcompare（S1，S2）运算。

4.11 试编写一个函数，实现在链式存储方式下字符串的replace（S，T1，T2）运算。

4.12 已知如下字符串，求它们的next数组值。

（1）“bbdcfbbdac”。

（2）“aaaaaaa”。

（3）“babbabab”。

4.13 已知正文t =“ababbaabaa”，模式p =“aab”，试使用KMP快速模式匹配算法寻找p在t中首次出现的起始位置，给出具体的匹配过程分析。

4.14 已知三维数组A[3][2][4]，数组首地址为100，每个元素占用1个存储单元，分别计算数组元素A[0][1][2]在按行优先和按列优先存储方式下的地址。

4.15 已知两个稀疏矩阵A和B，其行数和列数均对应相等，编写一个函数，计算A和B之和，假设稀疏矩阵采用三元组表示。

4.16 写出两个稀疏矩阵相乘的算法，计算：C pn= A pm∗B mn其中，A、B和C都采用三元组表示法存储。

c语言大一1至6章知识点C语言是一种程序设计语言，被广泛应用于计算机科学和软件开发领域。

在大一的学习过程中，学生通常需要学习C语言的基础知识。

本文将介绍C语言大一1至6章的知识点，帮助读者全面理解并掌握这些内容。

第一章：概述C语言的概述部分主要介绍了C语言的发展历程、特点以及应用领域。

同时，还简要介绍了C语言程序的结构和运行过程。

第二章：数据类型与运算符在C语言中，数据类型和运算符是基础的概念和工具。

这一章节主要包括以下几个方面的知识点：1. C语言的基本数据类型，如整型、浮点型、字符型等；2. 数据类型的声明和定义方式；3. C语言的运算符，包括算术运算符、关系运算符、逻辑运算符等；4. 运算符的优先级和结合性规则。

第三章：控制语句控制语句是程序设计中用于控制程序执行流程的关键部分。

在C语言中，常用的控制语句包括：1. 条件语句（if语句和switch语句），用于根据条件执行相应的代码块；2. 循环语句（while语句、do-while语句和for语句），用于重复执行一段代码块；3. 跳转语句（break语句、continue语句和goto语句），用于改变程序的执行顺序。

第四章：数组与字符串数组和字符串是C语言中常用的数据结构和数据类型。

该章节主要包括：1. 数组的概念和基本操作，包括数组的声明、初始化和访问；2. 多维数组的定义和使用；3. 字符串的概念和表示方法，以及常用的字符串函数。

第五章：函数函数是C语言中组织代码的重要工具。

在这一章节中，主要介绍：1. 函数的定义和声明，以及函数的调用过程；2. 函数参数传递的方式，包括按值传递和按引用传递；3. 递归函数的概念和使用方法。

第六章：指针与动态内存管理指针是C语言中的重要特性，也是较难理解和掌握的部分。

该章节主要涵盖：1. 指针的概念和基本操作，包括指针的声明、初始化和使用；2. 指针和数组之间的关系，指针的运算和指针的比较；3. 动态内存管理，包括动态内存的分配和释放。