实验二 线性表的顺序存储(2)

*功 能：查找该元素的所在位置，获得其前驱所在位置。 *输 出：返回其前驱结点的位序。 *后置条件：e1值为前驱结点的值 */

实现代码：

template

int SeqList::qianqu(int i,datatype item) {

if(length<=1) cout<<不存在前驱 for(i=0;i

if(data[i-1]==item) return i-1; cout<<表中无此元素}

(12)求直接后继结点算法 /*

*输 入：要查找的元素e，待存放后继结点值e1 *前置条件：无

*功 能：查找该元素的所在位置，获得其后继所在位置。 *输 出：返回其后继结点的位序。 *后置条件：e1值为后继结点的值 */

实现代码：

template

int SeqList::houji(int i,datatype item) {

if(length<=1) cout<<不存在后继 for(i=0;i

if(data[i-1]==item) return i+1; cout<<表中无此元素}

上机实现以上基本操作，写出main()程序：

要求对每个算法都加以测试，判断是否正确；并测试不同类型数据的操作。 粘贴测试数据及运行结果： typedef int datatype; void main() {

int a[10]={1,2,3,4,5,6,7,8,9,10}; SeqList myList(a,10); myList.display();

cout<<表长为： cout<<第5个元素是： cout<

cout<<第一个元素前插入元素33后表为： myList.Insert(1,33); myList.display();

cout<<表长为： cout<

cout<<删除第一个元素后表为： myList.Delete(1); myList.display();

cout<<表长为： cout<

cout<<元素4的前驱位置为： cout<<元素4的后继位置为： cout<

cout<<得到第6个元素为：

cout<<得到元素6的位置为： cout<

2、用以上基本操作算法，实现A=AUB算法。（利用函数模板实现） /*

*输 入：集合A,集合B *前置条件：无

*功 能：实现A=AUB *输 出：无

*后置条件：A中添加了B中的元素。 */

实现代码： void main() {

int a[]={1,3,5,7,9}; int b[]={1,3,6,8,10};

SeqList myLista(a,5); SeqList myListb(b,5); cout<<数组为: myLista.display(); cout<

cout<<数组为: myListb.display(); cout<

int i,j;

//int m=myLista.Length(),n=myListb.Length(); int c[10];

for(i=1;i

if(myLista.Get(i)==myListb.Get(j)) {

cout<<重复的元素是: myListb.Delete(j); }

//else continue;

for(i=myLista.Length()+1,j=1;j

cout<

char a1[]={\'a\',\'b\',\'c\',\'d\',\'e\'}; char b1[]={\'a\',\'b\',\'f\',\'g\',\'h\'}; SeqList myLista1(a1,5); SeqList myListb1(b1,5); cout<<数组为: myLista1.display(); cout<

cout<<数组为: myListb1.display(); cout<

int i1,j1; char c1[10];

//int m=myLista.Length(),n=myListb.Length();

for(i1=1;i1

if(myLista1.Get(i1)==myListb1.Get(j1)) {

cout<<重复的元素是: myListb1.Delete(j1); }

//else continue;

for(i1=myLista1.Length()+1,j1=1;j1

cout<

粘贴测试数据及运行结果：

3、对以上顺序表类中的基本操作算法适当加以补充，实现向一个有序的（非递减）的顺序表中插入数据元素e算法。 /*

*输 入：插入元素e *前置条件：顺序表已有序

*功 能：将元素e插入到顺序表中适当的位置，使顺序表依然有序 *输 出：无

*后置条件：有序顺序表插入了新元素，且表长加1。 */

实现代码：

template

void SeqList::Insert(datatype item) {

int i,j;

//if (length>=MaxSize) throw 溢出

//if (i<1 || i>length+1) throw 不合法！ for(i=0;i

for (j=i+1;jdata[j]) {

datatype a; a=data[i];

data[i]=data[j]; data[j]=a; }

cout<<排序后数组为： for(i=0;i

cout<

for (i=0;i

for (j=length; j>i; j--) data[j]=data[j-1]; data[i]=item; length++; }

void main() {

int a[]={1,9,8,4,7,6,2,3}; SeqList myLista(a,8); cout<<排序前数组为： myLista.display();

myLista.Insert(5);

cout<<插入元素后数组为： myLista.display(); }

粘贴测试数据及运行结果：

4、算法实现：La,Lb为非递减的有序线性表，将其归并为Lc，该线性表仍有序（未考虑相同时删除一重复值）（利用函数类板实现） MergeList： /*

*输 入：有序线性表La,有序线性表Lb *前置条件：顺序表已有序

*功 能：将两线性表归并，不去掉相同元素 *输 出： 返回一个新的有序线性表Lc *后置条件：无 */

实现代码：

template

void SeqList::sort() {

int i,j;

for(i=0;i

for (j=i+1;jdata[j]) {

datatype a; a=data[i];

data[i]=data[j]; data[j]=a; }

cout<<排序后数组为： for(i=0;i

void main() {