基本数据结构（数组、串、广义表）

男娘i 2022-09-19 12:20 164阅读 0赞

编程基础文章目录：

<table> 
 <tbody> 
  <tr> 
   <td><span style="font-size:18px"><a href="http://blog.csdn.net/linj_m/article/details/17393031" rel="nofollow">五大基础算法</a></span></td> 
   <td><span style="font-size:18px"><a href="http://blog.csdn.net/linj_m/article/details/17587533" rel="nofollow">基础数据结构（栈和队列）</a></span></td> 
   <td><span style="font-size:18px"><a href="http://blog.csdn.net/linj_m/article/details/15503241" rel="nofollow">散列表</a></span></td> 
  </tr> 
  <tr> 
   <td><span style="font-size:18px"><a href="http://blog.csdn.net/linj_m/article/details/17509315" rel="nofollow">常见C++知识</a></span></td> 
   <td><span style="font-size:18px"><a href="http://blog.csdn.net/linj_m/article/details/17587559" rel="nofollow">基础数据结构（数组、串、广义表）</a></span></td> 
   <td><span style="font-size:18px"><a href="http://blog.csdn.net/linj_m/article/details/13985589" rel="nofollow">四大比较排序算法</a></span></td> 
  </tr> 
  <tr> 
   <td><span style="font-size:18px"><a href="http://blog.csdn.net/linj_m/article/details/17550027" rel="nofollow">基础数据结构（线性表）</a></span></td> 
   <td><span style="font-size:18px"><a href="http://blog.csdn.net/linj_m/article/details/17587565" rel="nofollow">基础数据结构（树和堆）</a></span></td> 
   <td>&nbsp;</td> 
  </tr> 
 </tbody> 
</table>

微博：[LinJM-机器视觉][LinJM-] Blogger：[LinJM][]

**数组**

数组是由相同类型的数据元素构成的一个有限集合，对于m（m>=1）维数组，每个元素受m个线性关系的约束，所以数组是线性表的推广，一维数组可以看作是一个线性表；二维数组可以看作元素是线性表的线性表，依次类推。

**多维数组的概念与存储**

二维数组也可叫做矩阵，它可以看作是由n个行向量和m个列向量所组成的向量，a\[n\]\[m\]，总共n\*m个数组元素。

对于二维数组a\[n\]\[m\]，为能根据它的数组元素的下标得出在相应一维数组中对应的下标，需要区分2种存储方式，即行优先顺序和列优先顺序。

**特殊矩阵压缩存储**

对称矩阵、三角矩阵、对角矩阵

**[稀疏矩阵][Link 1]**

稀疏矩阵（sparse matrix）是矩阵中的一种特殊情况，其非零元素的个数远远小于零元素的个数。

只存储矩阵中极少数的非零元素<row,column, value>

**稀疏矩阵的转置**

//常规矩阵的转置
    for(int i = 0; i < A.rows; i++)
    	for(int j = 0; j < A.cols; j++)
    		B[j][i] = A[i][j];
    
    //稀疏矩阵的转置
    template <class T>
    SparseMatrix<T> SparseMatrix<T>::Transpose(){
    	SparseMatrix<T> b(maxTerms);//创建一个稀疏矩阵类的对象b
    	b.rows = cols;				//矩阵b的行数=矩阵a的列数
    	b.cols = rows;				
    	b.terms = terms;			//矩阵b的非零元素数传送
    	if(terms > 0){
    		int k,i,currentB = 0;	//存放位置指针
    		for(k=0;k<cols;k++)
    			for(i=0;i<terms;i++)
    				if(smArray[i].col == k){
    					b.smArray[currentB].row = k;
    					b.smArray[currentB].col = smArray[i].row;
    					b.smArray[currentB].value = smArray[i].value;
    					currentB++;
    				}
    	}
    	return b;
    }

例题：

![SouthEast][]

**字符串**

字符串，是一串文字和符号的序列。确切地说，字符串是由零个或多个字符的顺序排列所组成的数据结构，其基本组成元素是单个字符，字符串的长度可变。

字符串在计算机处理中使用非常广泛，人机之间信息的交换、文字信息的处理，生物信息学中基因信息的提取以及web信息的提取等，都离不开字符串的处理。

字符串的处理，得到许多程序设计语言的支持。C++语言提供了一个string.h类，提供了丰富的可操作的函数，为程序员编写有关文字处理的应用，给予了极大的方便。

C++中有关字符串的库函数

> strcpy 字符串复制
> 
> strncpy 字符串部分复制
> 
> strcat 字符串连接
> 
> strncat 将特定数量字符串连接到另一字符串
> 
> strchr 在给定字符串中搜寻指定字符

字符串的实现：数组存储表示、链接存储表示

**广义表**

广义表（generalized list）简称表，是线性表的推广。一个广义表LS定义为n个元素a0、a1、a2、a3、……an-1组成的有限序列。

LS = （a0、a1、a2、a3、……an-1）；

其中，LS为表名，ai是表中元素，它或者是数据元素或者是子表。n是表的长度。

广义表的定义是递归的，因为在表的描述中又利用到了表，允许表中有表。

有广义表的定义，可以得到以下几个性质：

> 有序性
> 
> 有长度
> 
> 有深度

通常用链表结构作为广义表的存储表示。

在用于表示广义表的链表中，每一个表结点可以由3个域表示：

（1）标志域 utype

用来标明该结点是什么类型的结点

=0，是广义表专用的附加头结点

=1，是原子结点

=2，是子表结点

（2）信息域 info

不同类型的结点在这个域中存放的内容不同

=0，info存放引用计数ref

=1，存放数据值value

=2，存放指向子表表头的指针link

（3）尾指针域 tlink

utype = 0时，该指针域存放指向该表表头元素结点的指针

utype ！=0时，该指针存放同一层下一个表结点的地址

本文地址：[http://blog.csdn.net/linj\_m/article/details/17587559][http_blog.csdn.net_linj_m_article_details_17587559]

**参考文献：**  
\[1\] 殷人昆. 数据结构 (用面向对象方法与 C++ 语言描述)\[M\]. 2007.  
\[2\] Cormen T H, Leizerson C E, Rivest R L. 算法导论\[M\]. 2006.  
\[3\] 维基百科

[LinJM-]: http://weibo.com/cengineer
[LinJM]: http://blog.csdn.net/linj_m
[Link 1]: http://blog.csdn.net/linj_m/article/details/11853133
[SouthEast]: /images/20220828/8f54d99719814d23a2c9b515ceb1e247.png
[http_blog.csdn.net_linj_m_article_details_17587559]: http://blog.csdn.net/linj_m/article/details/17587559