在顺序表中实现统计重复元素个数的操作：
在教材的【描述2-1】中，增加一个统计重复元素个数的成员函数： int Count(const T&x); //返回x出现的次数
在教材的【描述2-2】中，增加查找重复元素个数的成员函数的实现： //实现统计重复元素个数 template
int LinearList
int count=0;
for (int i=0; i if(element[i]==x) count++; return count; } 在顺序表中实现统计重复元素个数的操作： 在教材的【描述2-3】中，增加一个统计重复元素个数的成员函数： int Count(const T&x); //返回x出现的次数 在教材的【描述2-4】中，增加查找重复元素个数的成员函数的实现： //实现统计重复元素个数 template int LinkList LinkNode while (p!=NULL && ) { } if (p->data ==x) count++; p=p->next; return count; 第3章 栈和队列 1．具有什么特征的数据结构被称为栈和队列？先进后出、栈顶、栈底、先进先出、队头、队尾的概念是什么？ 栈：一种插入和删除都只能在表的同一端进行的线性表。 队列：一种只允许在表的一端进行插入操作，而在表的另一端进行删除操作的线性表。 先进后出：元素是以e1，e2，??en顺序进入数据结构，以相反的顺序即en，en-1，??e1离开数据结构。 栈顶：允许进行插入和删除操作的一端。 栈底：栈中与栈顶相对的另一端。 先进先出：元素是以e1，e2，??en顺序进入数据结构，以相同的顺序即e1，e2，??en。 离开数据结构。 队头：允许删除操作的一端。 队尾：允许插入操作的一端。 2．简述在顺序栈的栈顶插入一个元素的操作过程。 在插入元素之前，首先要判断栈是否为满，如果栈满，返回“沾满无法插入”等错误提示信息；否则让top指针（指向当前顺序栈的栈顶）向后移动一个元素空间（元素大小），将要插入的元素放入top指针指向的内存单元中。 3. 一个栈的输入序列为1、2、3，试给出全部可能的出栈序列。 可分为三种情况： ①、当只有一个存储空间时，只有一种出栈序列：1、2、3. ②、当有两个存储空间时，有：1、2、3， 2、1、3， 2、3、1等3种出栈序列 ③、当存储空间大于等于三个时，有：1、2、3， 2、1、3， 2、3、1， 3、2、1 等4种出栈序列。 4．循环队列的优点是什么？在循环队列中，仅依据头尾指针相等，无法判断队列是“空”还是“满”。要解决这个问题，常用的两种方法是什么？ 循环队列的优点有两点：一是可以避免发生顺序队列的“假上溢”现象；二是充分利用队列的存储空间。 两种判断队列是“空”还是“满”的方法：一是约定少用一个元素空间；二是使用计数器size记录当前队列的实际长度。 5. 简述在链接栈中插入一个元素的操作过程。 链接栈的插入操作，先将待进栈结点的指针域指向原来的栈顶结点，然后将栈顶指针top修改指向该结点，使进栈元素结点成为新的栈顶结点。 6．请列举出一些可以用栈和队列表示的实际问题。 所有“后进先出”(LIFO，Last In First Out）的实际问题都可以用栈表示。栈的应用主要有：数制的转换、括号的匹配检查、行编辑处理、表达式求解、走迷宫以及高级语言中函数的嵌套调用和递归的实现等。 所有“先进先出”(FIFO，First In First Out）的实际问题都可以用队列表示。如日常中的排队问题，队列的应用主要有：操作系统中各种资源请求排队和各种缓冲区的先进先出管理，各种应用系统中的事件规划和事件模拟，树的层次遍历和图的广度优先遍历等。 第4章 数组、字符串与广义表 1.具有什么特征的数据结构被称为数组？ 数组可以看成是形如（index，value）的数据集合，其中，index是元素的索引，表示数据的逻辑位置，任意两个数据的index都不相同；value表示数据元素的值。 2.设有二维数组a[5][6]，每个元素占相邻的8个字节，存储器按字节编址，已知a的起始地址是1000，试计算： （1）数组a的最后一个元素起始地址； 1000+（30-1）*8=1232。 （2）按行序优先时，元素a[3][5]的起始地址； 1000+（3*6+5）*8=1184 （3）按行列序优先时，元素a[4][3]的起始地址。 1000+（3*5+4）*8=1152 3.请简述数组和矩阵的关系。 矩阵是指纵横排列的二维数据表格。在高级语言编程中，通常用二维数组来描述一个矩阵，从而可以对矩阵中的元素进行随机存取。但矩阵的索引通常从1而不是像数组那样从0开始，并且使用A（i，j）而不是A[i，j]的形式来引用矩阵中的元素。 4.矩阵有哪些基本运算？ 矩阵的操作包括转置、加法、减法和乘法等。 5.稀疏矩阵的特点是什么？为什么要对稀疏矩阵采用压缩存储技术？ 稀疏矩阵的特点是矩阵中非零元素个数远远少于矩阵零元素个数。 采用压缩存储技术主要是为了节省空间。 6.设A和B是稀疏矩阵，都以三元组作为存储结构，请写出矩阵相加的算法C=A+B。 //稀疏矩阵的三元组表示 #include #define MaxSize 20 typedef int ElemType; typedef struct { int r; int c; ElemType d; } TupNode; typedef struct { int rows; int cols; int nums; TupNode data[MaxSize]; } TSMatrix; int A[M][N],B[M][N]; //建立三元组 void CreateMat(int A[M][N],TSMatrix &t,int row,int col) { int i,j; t.rows=row;t.cols=col;t.nums=0; for(i=0;i for(j=0;j if(A[i][j]!=0) { t.data[t.nums].r=i;t.data[t.nums].c=j; t.data[t.nums].d=A[i][j];t.nums++; } } } } //矩阵相加 int MatAdd(TSMatrix &a,TSMatrix &b,TSMatrix &c) { int i=0,j=0,k=0; ElemType v; if(a.rows!=b.rows||a.cols!=b.cols) return 0; c.rows=a.rows;c.cols=a.cols; while(i if(a.data[i].r==b.data[j].r) { if(a.data[i].c { c.data[k].r=a.data[i].r; c.data[k].c=a.data[i].c; c.data[k].d=a.data[i].d; i++;k++; } else if(a.data[i].c>b.data[j].c) { c.data[k].r=b.data[j].r; c.data[k].c=b.data[j].c; c.data[k].d=b.data[j].d; j++;k++; } else { v=a.data[i].d+b.data[j].d; if(v!=0) { c.data[k].r=a.data[i].r; } c.data[k].c=a.data[i].c; c.data[k].d=v; k++; i++;j++; } } else if(a.data[i].r c.data[k].r=a.data[i].r; c.data[k].c=a.data[i].c; c.data[k].d=a.data[i].d; i++;k++; } else { c.data[k].r=b.data[j].r; c.data[k].c=b.data[j].c; c.data[k].d=b.data[j].d; j++;k++; } } if (i==a.nums) while (j c.data[k].r=b.data[j].r; c.data[k].c=b.data[j].c; c.data[k].d=b.data[j].d; j++;k++; } if (j==b.nums) while (i c.data[k].r=a.data[i].r; c.data[k].c=a.data[i].c; c.data[k].d=a.data[i].d; i++;k++; } c.nums=k;