三婉刀、字符串和矩陣
1. 字符串
1.1 字符串的按需（堆）存儲(chǔ)結(jié)構(gòu)
實(shí)現(xiàn)：
//字符串的類
class HString //只一種類型损话，不需要模板
{
friend class BMMatching;
private:
char *ch; //若是非空串，則按串長分配存儲(chǔ)空間翎碑，空串 ch 為 NULL
int length;
public:
HString()
{//構(gòu)造函數(shù)一谬返，產(chǎn)生空串
ch = NULL;
length = 0;
}
HString(const char* str)
{//構(gòu)造函數(shù)二，產(chǎn)生與字符串常量 str 字符相同的串
length = strlen(str);
ch = new char[length];
assert(ch != NULL);
for(int i = 0; i <length; i++)
ch[i] = str[i];
}
HString(const HString &S)
{//構(gòu)造函數(shù)三日杈，產(chǎn)生與字符串的類對(duì)象 S 相同的對(duì)象
length = S.length;
ch = new char[length];
assert(ch != NULL);
for(int i = 0; i < length; i++)
ch[i] = S.ch[i];
}
~HString()
{//析構(gòu)函數(shù)朱浴，清空串
ClearString();
}
void ClearString()
{//清空串
if (ch != NULL)
{
delete[] ch;
ch = NULL;
}
length = 0;
}
void StrAssign(const char* str)
{//產(chǎn)生與字符串常量 str 字符相同的串
ClearString(); //釋放原有存儲(chǔ)空間
length = strlen(str);
if (length)
{
ch = new char[length];
assert(ch != NULL);
for(int j = 0; j < length; j++)
ch[j] = str[j];
}
}
void StrCopy(const HString &S)
{//復(fù)制串 S
ClearString();
ch = new char[S.length];
assert(ch != NULL);
for(int i = 0; i < S.length; i++)
ch[i] = S.ch[i];
length = S.length;
}
bool StrEmpty()const
{//若串為空，則返回 true 达椰；否則返回 false
return length == 0;
}
int StrCompare(const HString &S)const
{//若串 > 串S翰蠢，則返回值 >0 ，若串 = 串S啰劲，則返回 =0 梁沧，若串 < 串S，則返回 <0
for(int i = 0; i < length && i < S.length; i++) //在有效范圍內(nèi)
if (ch[i] != S.ch[i])
return ch[i] - S.ch[i]; //不相等蝇裤，則返回兩字符 ASCII 碼的差值
return length - S.length; //在有效范圍內(nèi)字符相等廷支，則返回長度之差
}
int StrLength()const
{//返回串的元素個(gè)數(shù)
return length;
}
void Concat(const HString &S1, const HString &S2)
{//返回由串 S1 和 S2 連接而成的新串
int i;
ClearString();
length = S1.length + S2.length;
ch = new char[length];
assert(ch != NULL);
for(int i = 0; i < S1.length; i++)
ch[i] = S1.ch[i];
for(int i = 0; i < S2.length; i++)
ch[S1.length + i] = S2.ch[i];
}
bool SubString(HString &Sub, int pos, int len)const
{//用 Sub 返回串的第 pos 個(gè)字符起長度為 len 的子串，成功返回 true栓辜；否則返回false
if (pos < 1 || pos > length || len < 0 || len > length-pos+1)
return false;
Sub.ClearString();
if (len)
{
Sub.ch = new char[len];
assert(Sub.ch != NULL);
for(int i = 0; i < len; i++)
Sub.ch[i] = ch[pos - 1 + i];
Sub.length = len;
}
return true;
}
bool StrInsert(int pos, const HString &S)
{//在串的第 pos 個(gè)字符之前插入串 S 恋拍，成功返回 true ;否則返回 false
int i;
char *p;
if (pos < 1 || pos > length + 1)
return false;
if (S.length)
{
p = new char[length + S.length];
assert(p != NULL);
for(int i = 0; i < pos - 1; i++)
p[i] = ch[i];
for(int i = 0; i < S.length; i++)
p[pos - 1 + i] = S.ch[i];
for(int i = pos - 1; i < length; i++)
p[i + S.length] = ch[i];
delete[] ch;
ch = p;
}
return true;
}
bool StrDelete(int pos, int len)
{//從串中刪除第 pos 個(gè)字符起長度為 len 的子串
int i;
char *p;
if (len > length - pos + 1)
return false;
p = new char[length - len];
assert(p != NULL);
for(i = 0; i < pos - 1; i++)
p[i] = ch[i];
for(i = pos - 1; i < length - len; i++)
p[i] = ch[i + len];
length -= len;
delete[] ch;
ch = p;
return true;
}
void StrPrint()const
{//輸出字符串
for(int i = 0; i < length; i++)
cout << ch[i];
cout << endl;
}
int Index(const HString &S, int pos)const
{//若串中第 pos 個(gè)字符之后存在與 S 相等的子串
//則返回第一個(gè)這樣的字串在串中的位置，否則返回 0
HString sub;
if (pos > 0 && pos <= length)
for(int i = pos; i < length - S.length + 1; i++)
{//i 從串的第 pos 到倒數(shù)第 S.length 個(gè)字符
SubString(sub, i, S.length);
if (sub.StrCompare(S) == 0) //匹配到
return i;
}
return 0;
}
bool Replace(const HString &T, const HString &V)
{//初始條件：串 T 和串 V 存在藕甩，串 T 是非空串
//操作結(jié)束：用串 V 替換串中出現(xiàn)的所有與串 T 相等的不重疊子串
int i = 1; //從串的第一個(gè)字符開始查找串 T
if (!T.length) //T 是空串
return false;
while(i) //若 i > length 施敢，在 Index() 中會(huì)返回 0
{
i = Index(T, i);
if (i)
{
StrDelete(i, T.length);
StrInsert(i, V);
i += V.length;
}
}
return true;
}
};
HString 類中存儲(chǔ)字符串的方式和 C++ 語言設(shè)置的存儲(chǔ)字符串的方式不同，在串尾沒有 "\0" 作為串結(jié)束標(biāo)志狭莱，而是單獨(dú)用一個(gè)私有數(shù)據(jù)成員 length 存放串長僵娃。這導(dǎo)致 HString 類不能使用 C++ 的 string 中的庫函數(shù)。
1.2 字符串的模式匹配算法
1.2.1 樸素的模式匹配算法
樸素的模式匹配算法即 HString 類中的 Index() 成員函數(shù)：由主串的第 pos 個(gè)字符起腋妙，檢驗(yàn)是否存在子串 S 默怨。首先令 i 等于 pos （i 為主串中當(dāng)前待比較字符的位序），j 等于 1 （j 為 S 中當(dāng)前待比較字符的位序）骤素，如果主串的第 i 個(gè)字符與 S 的第 j 個(gè)字符相同匙睹，則 i, j 各加 1 繼續(xù)比較愚屁，直至 S 的最后一個(gè)字符（找到）。若在比較期間出現(xiàn)了不同（沒找到）痕檬，令 i 等于 pos+1 集绰，j 等于 1，由 pos 的下一位置起谆棺，繼續(xù)查找是否存在子串 S栽燕。
該算法簡單，容易理解改淑，但主串的指針 i 總要回溯碍岔，特別是在有較多的字符匹配又不完全匹配的情況下，回溯得更多朵夏。這時(shí)蔼啦，主串的每個(gè)自負(fù)要進(jìn)行多次比較，顯然效率較低仰猖。
1.2.2 KMP 算法和改進(jìn)的 KMP 算法
如果能使主串的指針 i 不回溯捏肢，也就是使主串的每個(gè)字符只進(jìn)行一次比較，效率會(huì)大為提高饥侵。這是可以做到的鸵赫。當(dāng)檢測到主串中的第 i （終值）個(gè)字符與模式串 S 中第 j （終值）個(gè)字符不匹配時(shí)，i（終值）之前的字符都是已知的躏升。他們都與模式串 S 中的相應(yīng)字符相同辩棒，故 i 可仍保持在終值處不動(dòng)，j 回溯到子串 S 的第 1 個(gè)字符處與 i 的當(dāng)前字符繼續(xù)進(jìn)行比較膨疏。j 回溯到第幾個(gè)字符是由子串 S 的模式?jīng)Q定的一睁。KMP 算法根據(jù)子串 S 生成的 next 數(shù)組指示 j 回溯到第幾個(gè)字符。 next 數(shù)組的意義是這樣的：如果 next[j] = k 佃却，則當(dāng)子串 S 的第 j 個(gè)字符和主串的第 i 個(gè)字符失配時(shí)者吁，主串的第 i 個(gè)字符繼續(xù)與 S 的第 k 個(gè)字符繼續(xù)進(jìn)行比較即可。
KMP 算法還有可改進(jìn)之處饲帅。下面的 get_next() 是改進(jìn)的求數(shù)組 next() 的算法复凳。其中，next[j] = 0 洒闸，并不是將主串的當(dāng)前字符與模式串的第 0 個(gè)字符進(jìn)行比較染坯，而是主串當(dāng)前字符的下一個(gè)字符與模式串的第 1 個(gè)字符進(jìn)行比較均芽。
實(shí)現(xiàn)：
//改進(jìn)的 KMP 算法
void get_next(HString S, int next[])
{
int i = 1, j = 0;
HString subs1, subs2;
next[1] = 0; //S 的第一個(gè)字符與主串失配丘逸，主串的下一個(gè)字符與 S 的第一個(gè)字符比較
while(i < S.StrLength())
{
S.SubString(subs1, i, 1); //S 的第 i 個(gè)字符在 subs1 中
S.SubString(subs2, j, 1); //S 的第 j 個(gè)字符在 subs2 中
if (j == 0 || subs1.StrCompare(subs2) == 0) // (S.ch[i] == S.ch[j])
{
++i;
++j;
S.SubString(subs1, i, 1); //S 的第 i 個(gè)字符在 subs1 中
S.SubString(subs2, j, 1); //S 的第 j 個(gè)字符在 subs2 中
if (subs1.StrCompare(subs2) != 0) // (S.ch[i] != S.ch[j])
next[i] = j;
else
next[i] = next[j];
}
else
j = next[j]; //j 減小到前面字符相等之處
}
}
推薦閱讀：
KMP算法（研究總結(jié)，字符串）
KMP 算法（1）：如何理解 KMP
1.2.3 Boyer-Moore 算法
Boyer-Moore 算法基于以下事實(shí)：模式串一般較短掀宋，因此只包含字符集中少數(shù)字符深纲，如果主串當(dāng)前比較的字符在模式串中沒有仲锄，那就可以將模式串向右移動(dòng)直到主串該字符的下一個(gè)字符與模式串的第一個(gè)字符對(duì)齊。為了提高效率湃鹊，比較是從模式串的最后一個(gè)字符開始的儒喊。
Boyer-Moore 算法在匹配過程中對(duì)主串一些字符跳不過去檢查，但也有一些字符會(huì)被檢查多次币呵。
實(shí)現(xiàn)：
//用類實(shí)現(xiàn) BM 算法
const int N = 256; //字符集擴(kuò)展到漢字怀愧，ASCII 碼 0 ~ 255
class BMMatching //之前設(shè)置為 HString 類的友類，以便使用其私有數(shù)據(jù)成員
{
private:
HString Main, Sub; //主串余赢，模式串
bitset<N> bit; //N 個(gè)二進(jìn)制（全 0 ）的 STL 位集合類對(duì)象
void MakeBitset()
{//根據(jù)模式串確定位集合 bit 的值
int i;
for(i = 0; i < Sub.length; i++)
bit[(unsigned char)Sub.ch[i]] = 1; //令相應(yīng)的bit[] 的 ASCII 碼位的值為 1
}
int last(char c)
{//如果字符 c 不在模式串 Sub 中芯义，返回 -1 ；否則返回其在 Sub 中的最大位序
if (bit[(unsigned cha)c == 0]) //bit中對(duì)應(yīng)字符c的位值為0妻柒，則說明c不在模式串中
return -1;
else
for(int i = Sub.length - 1; i >= 0; i--) //由后向前
if (c == Sub.ch[i]) //c 在位置 i
return i;
}
public:
BMMatching(const char* str = "", const char* strS = "")
{//構(gòu)造函數(shù)扛拨，產(chǎn)生 HString 類的主串、模式串并根據(jù)模式串確定位集合 bit 的值
Main.StrAssign(strM); //用字符串 strM 構(gòu)造主串 Main
Sub.StrAssign(strS); //用字符串 StrS 構(gòu)造模式串 Sub
MakeBitset(); //根據(jù)模式串確定位集合 bit 的值
}
int BMMatching()
{//Boyer-Moore 算法
int m, n, i, j;
cout << "主串為" ;
Main.StrPrint();
cout << "模式串為" ;
Sub.StrPrint();
m = Sub.length;
n = Main.length;
j = m - 1;
i = n - 1;
do
{
if (Sub.ch[j] == Main.ch[j])
if (j == 0) //由后向前已經(jīng)比較到第一個(gè)字符
return i+1;
else
i--, j--;
else
{
i = i + m - min(j, 1+last(Main.ch[i]));
j = m - 1;
}
}while(i < n); //沒到主串尾
return 0;
}
};
注意：
漢字編碼有有兩個(gè)特性：
（1）兩個(gè)字節(jié)（字符）表示一個(gè)漢字举塔；
（2）表示漢字的字符范圍是從 128 到 255 （轉(zhuǎn)換成無符號(hào)類型）绑警。
推薦閱讀：
Boyer-Moore 算法
Sunday 算法
2. 矩陣
2.1 多維數(shù)組的順序存儲(chǔ)結(jié)構(gòu)
實(shí)現(xiàn)：
//多維數(shù)組的類
template<typename T>class MuArray
{
private:
T *base; //數(shù)組元素基址，由構(gòu)造函數(shù)分配
int dim; //數(shù)組維數(shù)
int *bounds; //數(shù)組維界基址央渣，由構(gòu)造函數(shù)分配
int *constants; //數(shù)組映像函數(shù)常量基址计盒，由構(gòu)造函數(shù)分配
bool Locate(va_list ap, int &off)const
{//若 ap 指示的各下標(biāo)值合法，則求出該元素在 base 中的相對(duì)地址 off
int i, ind;
off = 0;
for(i = 0; i < dim; i++)
{
ind = va_arg(ap, int); //逐一讀取各維的下標(biāo)值
if (ind < 0 || ind >= bounds[i]) //各維下標(biāo)值不合法
return false;
off += constants[i] * ind; //相對(duì)地址 = 各維下標(biāo) * 本維的偏移量之和
}
return true;
}
public:
MuArray(int Dim, ...)
{//構(gòu)造函數(shù)芽丹，若維數(shù) dim 和各維數(shù)長度合法章郁，則構(gòu)造相應(yīng)的數(shù)組對(duì)象
int elemtotal = 1, i; //elemtotal 是數(shù)組元素總數(shù)，初值為 1
va_list ap; //變長參數(shù)表類型志衍，在 stdarg.h 中
assert(Dim > 0);
dim = Dim;
bounds = new int[dim];
assert(bounds != NULL);
va_start(ap, Dim); //變長參數(shù) "..." 從形參 Dim 之后開始
for(i = 0; i < Dim; i++)
{
bounds[i] = va_arg(ap, int); //逐一將變長參數(shù)賦給 bounds[i]
assert(bounds[i] > 0);
elemtotal *= bounds[i]; //數(shù)組元素總數(shù) = 各維長度之乘積
}
va_end(ap); //結(jié)束提取變長參數(shù)
base = new T[elemtotal];
assert(base != NULL);
constants[dim - 1] = 1; //最后一維的偏移量為 1
for(i = Dim - 2; i >= 0; i--)
constants[i] = bounds[i + 1] * constants[i + 1]; //每一維的偏移量
}
~MuArray()
{//析構(gòu)函數(shù)暖庄，釋放所有動(dòng)態(tài)生成的存儲(chǔ)空間
delete[] base;
delete[] bounds;
delete[] constants;
}
bool Value(T &e, int n, ...)const
//在 VC++ 中，"..." 之前的形參不能是引用類型楼肪，故加形參 n
{//...依次為各維的下標(biāo)值培廓，若各下標(biāo)合法，則 e 被賦值為矩陣相應(yīng)的元素值
va_list ap;
int off;
va_start(ap, n);
if (Locate(ap, off) == false) //求得變長參數(shù)所指單元的相對(duì)地址
return false;
e = *(base + off); //將變長參數(shù)所指單元的值賦給 e
return true;
}
bool Assign(T e, ...)const
{//...依次為各維下標(biāo)值春叫，若各下標(biāo)合法肩钠，則將 e 的值賦給矩陣指定的元素
va_list ap;
int off;
va_start(ap, e);
if (Locate(ap, off) == false)
return false;
*(base + off) = e;
return true;
}
};
MuArray 中有些成員函數(shù)的形參有 "..." ，它代表變長參數(shù)表暂殖，即 "..." 可用若干個(gè)實(shí)參取代价匠。這很適合含有維數(shù)不定的數(shù)組的函數(shù)。
2.2 矩陣的壓縮存儲(chǔ)
實(shí)現(xiàn)：
//三元組行邏輯連接順序表的類
template<typename T>struct Triple
{//三元組類型的結(jié)構(gòu)體
int i, j; //行下標(biāo)呛每，列下標(biāo)
T e; //非零元素值
}
const int MAX_SIZE = 100; //非零元個(gè)數(shù)的最大值
const int MAX_RC = 20; //最大行數(shù)
template<typename T>class RLSMatrix
{
private:
Triple<T> data[MAX_SIZE + 1]; //data[0] 未用
int rpos[MAX_RC + 1]; //各行第一個(gè)非零元素的位置表
int row, col, num; //矩陣的行數(shù)踩窖，列數(shù)，非零元的個(gè)數(shù)
public:
RLSMatrix()
{//構(gòu)造函數(shù)晨横，構(gòu)造 0 行 0 列的空矩陣
row = col = num = 0;
}
RLSMatrix(char* FileName)
{//構(gòu)造函數(shù)洋腮，由文件創(chuàng)建稀疏矩陣
CreateSMatrixFromFile(FileName);
}
bool CreateSMatrixFromFile(char* FileName = "F3-1.txt") //缺省值
{//由文件創(chuàng)建稀疏矩陣箫柳，要求格式正確，默認(rèn)文件名是 F3-1.txt
int i, j;
ifstream fin(FileName); //打開文件
fin >> row >> col >> num;
if (num > MAX_SIZE || row > MAX_RC) //矩陣的行數(shù)太多或非零元個(gè)數(shù)太多
return false;
data[0].i = 0; //為下面比較做準(zhǔn)備
for(i = 1; i <= num; i++)
{
fin >> data[i].i >>data[i].j >> data[i].e;
//由文件讀入稀疏矩陣的一個(gè)非零元素
if (data[i].i < 1 || data[i].i > row || data[i].j < 1 || data[i].j >col)
return false;
if (data[i]. i < data[i - 1].i ||
data[i].i == data[i - 1].i && data[i].j <= data[i - 1].j)
return false; //行或列的輸入順序有錯(cuò)
}
fin.close();
for(i = 1; i <= row; i++) //給rpos[]賦初值 1（每行的第一個(gè)非零元素的初始位置）
rpos[i] = 1;
for(i = 1; i <= num; i++)
for(j = data[i].i + 1; j <= row; j++) //從非零元素所在行的下一行起
rpos[j]++; //每行第一個(gè)非零元素的位置 +1
return true;
}
void CopySMatrix(const RLSMatrix &M)
{//由稀疏矩陣 M 復(fù)制得到稀疏矩陣
int i;
row = M.row;
col = M.col;
num = M.num;
for(i = 0; i <= M.num; i++)
data[i] = M.data[i];
for(i = 0; i <= M.row; i++)
rpos[i] = M.rpos[i];
}
void TransposeSMatrix(const RLSMatrix &M)
{//求稀疏矩陣 M 的轉(zhuǎn)置矩陣
int i, j, k, colm[MAX_RC + 1]; //[0] 不用
row = M.col; //M 的轉(zhuǎn)置的行數(shù) = M 的列數(shù)
col = M.row; //M 的轉(zhuǎn)置的列數(shù) = M 的行數(shù)
num = M.num; //M 的轉(zhuǎn)置的非零元素個(gè)數(shù) = M 的非零元素個(gè)數(shù)
if (num) //矩陣 M 非空
{
for(i = 1; i <= row; ++i)
colm[i] = 0; //M 轉(zhuǎn)置的每行非零元素個(gè)數(shù)啥供，初值設(shè)置為 0
for(i = 1; i <= num; ++i)
++colm[M.data[i].j]; //colm[] = M 的每列非零元素個(gè)數(shù)
rpos[1] = 1; //M 轉(zhuǎn)置的第 1 行的第一個(gè)非零元素的序號(hào)是 1
for(i = 2; i <= row; ++i)
rpos[i] = rpos[i-1] + colm[i-1];//求 M 轉(zhuǎn)置中第 i 行的第一個(gè)非零元素的序號(hào)
for(i = 1; i <= row; ++i)
colm[i] = rpos[i]; //colm[i] = M 的當(dāng)前非零元素在 M 轉(zhuǎn)置中應(yīng)該存放的位置
for(i = 1; i <= num; ++i)
{
j = M.data[i].j; //在 M 轉(zhuǎn)置中的行數(shù)
k = colm[j]++; //在 M 轉(zhuǎn)置中的序號(hào)悯恍，colm[j] + 1
data[k].i = j; //將 M.data[i] 行列對(duì)調(diào)賦給 data[k]
data[k].j = M.data[i].i;
data[k].e = M.data[i].e;
}
}
}
bool AddSMatrix(const RLSMatrix &M, const RLSMatrix &N)
{//求兩稀疏矩陣的和 = M + N
int p, q, up, uq;
if (M.row != N.row || M.col != N.col)
return false;
row = M.row;
col = M.col;
num = 0; //矩陣 M 非零元素個(gè)數(shù)的初值
for(int k = 1; num <= MAX_SIZE && k <= M.row; ++k) //k 指示行號(hào)
{
rpos[k] = num + 1;
p = M.rpos[k];
q = N.rpos[k];
if (k < M.row) //不是最后一行
{
up = M.rpos[k + 1];
uq = N.rpos[k + 1];
}
else //是最后一行
{
up = M.num + 1; //給最后一行設(shè)上界
uq = N.num + 1;
}
while(p < up && q < uq)
if (M.data[p].j < N.data[q].j)
data[++num] = M.data[p++];
else if (M.data[p].j > N.data[q].j)
data[++num] = N.data[q++];
else
{
if (M.data[p].e + N.data[q].e != 0)
{
data[++num] = M.data[p];
data[num].e += N.data[q].e;
}
p++;
q++;
}
//以下兩個(gè)循環(huán)最多執(zhí)行一個(gè)
while(p < M.rpos[k + 1] && p <= M.num)
data[++num] = M.data[p++];
while(q < N,rpos[k + 1] && q <= N.num)
data[++num] = N.data[q++];
}
if (num > MAX_SIZE) //非零元素個(gè)數(shù)太多
return false;
else
return true;
}
bool SubtSMatrix(const RLSMatrix &M, RLSMatrix &N)
{//求兩稀疏矩陣的差 = M - N
int i;
bool f;
RLSMatrix S, N1;
N1.CopySMatrix(N);
for(i = 1; i < N1.num; ++i) // N1 = -N
N1.data[i].e *= -1;
f = S.AddSMatrix(M, N1); //S = M + (-N) = M - N
if (f)
{
row = S.row;
col = S.col;
num = S.num;
for(i = 0; i <= S.num; i++)
data[i] = S.data[i];
for(i = 0; i <= S.row; i++)
rpos[i] = S.rpos[i];
}
return f;
}
bool MultSMatrix(const RLSMatrix &M, RLSMatrix &N)
{//一種求稀疏矩陣乘積 M * N 的方法（利用 N 的轉(zhuǎn)置矩陣 T）
int i, j, q, p, up, uq;
T Qs; //矩陣單元 data[i][j].e 的臨時(shí)存放處
RLSMatrix T; //存 N 的轉(zhuǎn)置矩陣
if (M.col != N.row)
return false;
row = M.row;
col = N.col;
num = 0;
T.TransposeSMatrix(N);
for(i = 1; i <= row; i++)
for(j = 1; j <= col; j++)
{
Qs = 0;
p = M.rpos[i]; //p 指示矩陣 M 在 i 行的第一個(gè)非零元素的位置
q = T.rpos[j]; //q 指示矩陣 T 在 j 行的第一個(gè)非零元素的位置
if (i < M.row)
up = M.rpos[i + 1];
else
up = M.num + 1;
if (j < T.row)
uq = T.rpos[j + 1];
else
uq = T.num + 1;
while(p < up && q < uq)
if (M.data[p].j < T.data[q].j)
p++;
else if (M.data[p].j > T.data[q].j)
q++;
else
Qs += M.data[p++].e * T.data[q++].e;
if (Qs)
{
if (++num > MAX_SIZE)
return false;
data[num].i = i;
data[num].j = j;
data[num].e = Qs;
}
}
return true;
}
void PrintSMatrix()const
{//按矩陣形式輸出
int k = 1; //非零元計(jì)數(shù)器
const Triple<T> *p = data + 1; //常量指針 p 指向第一個(gè)非零元素
if (num == 0) //矩陣不存在
return;
for(int i = 1; i <= row; i++)
{
for(int j = 1; j <= col; j++)
if (k <= num && p->i == i && p->j == j)
{
cout << setw(3) << (p++)->e;
k++;
}
else
cout << setw(3) << 0;
cout << endl;
}
}
};
