c数据结构之数组复习资料

《c数据结构之数组复习资料》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第2章数组一、复习要点本章主要讨论数组抽象数据类型及利用数组实现的顺序表、字符串等数据结构。它们都是线性结构。但数组是直接存取结构，对以根据数组元素的下标直接在数组中存取该元素，而利用它实现的顺序表是顺序存取结构，所有数据元素集中存储于表的前端。字符串是顺序表的特化。本章复习的要点：1、基本知识点2、算法设计>静态数组对象的定义，动态数组对象的定义>数组中数组元素的原地逆置>递归计算数组长度、数组中所有元素的和及平均值>在顺序表中搜索值为itein的元素，在有序顺序表中搜索值为item的元素>在有序顺序表中插入新元素item到第i个位置>在有序顺序表中删除第i个

2、元素>两个有序顺序表的合并，m个有序顺序表的合并二、难点与重点1、作为抽象数据类型的数组：数组的定义、数组的按行顺序存储与按列顺序存储>确定数组元素的三要素：行号、列号、元素值>数组元素的存放地址计算2、顺序表：顺序表的定义、搜索、插入与删除>顺序表搜索算法、平均比较次数的计算>插入与删除算法、平均移动次数的计算三、习题的解析2-3设有一个线性表(e0,eb•••,en.2,en.

3、)存放在一个一维数组A[arraySize]中的前n个数组元素位置。请编写一个函数将这个线性表原地逆置，即将数组的前n个原址内容置换为(en.hen-2,…，e【，eo)。【解答】t

4、emplatevoidinverse(TypeA

5、],intn){lpetmp;for(inti=0;i<=(n-1)/2;i++){tmp=A(i];A[i

6、=A[n-iT];A[nTT]=tmp;}}2-5顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下，对有127个元素的顺序表进行插入，平均需要移动多少个元素？删除一个元素，又平均需要移动多少个元素？【解答】若设顺序表中已有n二last+1个元素，last是顺序表的数据成员，表明最后表项的位置。又设插入或删除表屮各个元素的概率相等，则在插入时因有n+1个插入位置(可

7、以在表屮最后一个表项后面追加)，每个元素位置插入的概率为l/(n+l),但在删除时只能在已有n个表项范圉内删除，所以每个元素位置删除的概率为1/n。插入时平均移动元素个数AMN(AveragyMovingNumber)为AMN=丄Y(n-i-1)=-((n-1)+(n-2)+•••+1-t-0)=-(n~1)n=ni=onn22删除时平均移动元素个数AMN为1宀/.1/八，八、1n(n+1)nAMN=〉(n-i)=(n+(n-1)+…+1+0)==—n+1tt,n+1n+122根据上述推导,插入时平均移动127/2=63.5个元素，删除时平均移动(127-1)

8、/2=63个元素。2-7设有一个二维数组A[m][n],假设A[0][0]存放位置在644(I0),A[2]⑵存放位置在676(10)，每个元素占一个空问，问A[3][3](io)存放在什么位置？脚注(10)表示用10进制表示。【解答】设数组元素A[i][j]存放在起始地址为Loc(i,j)的存储单元屮。・.・Loc(2,2)=Loc(0,0)+2*n+2=644+2*n+2=676.・•・n=(676-2-644)/2=15・・・Loc(3,3)二Loc(0,0)+3*15+3二644+45+3二692.2-8利用顺序表的操作，实现以下的函数。(1)从顺序表屮

9、删除具有最小值的元素并由函数返冋被删元素的值。空出的位置由最后一个元素填补，若顺序表为空则显示出错信息并退出运行。(2)从顺序表屮删除第i个元素并由函数返回被删元素的值。如果i不合理或顺序表为空则显示出错信息并退出运行。(3)向顺序表屮第i个位置插入一个新的元素X。如果i不合理则显示出错信息并退出运行。(4)从顺序表屮删除具有给定值x的所有元素。(7)将两个有序顺序表合并成一个新的有序顺序表并由函数返回结果顺序表。【解答】顺序表的类定义#ifndefSEQLIST_H#defineSEQLIST_H#include#include

10、lib.h>template

11、当前指针(最近处理的表项