(10)--第一次上机要求数据结构.ppt

数据结构上机;上机任务;一、熟悉实验环境;2.选择创建【Consoleapplication】——Go;3.在语言中选择C语言;4.填写项目名称和地址，点击Next?finished;二、上机内容

;任务一.实现顺序表的以下基本操作

1.voidInitList(SeqListL);

//创建一个顺序表

2.intInsert(SeqListL,ListDatax,inti);

//向顺序表中插入元素

3.intDelete(SeqListL,ListDatax);

//删除顺序表中的某个元素

4-1.intIsIn(constSeqListL,ListDatax);

//链表中是否存在x,如果存在则返回1,否则返回0

;任务一.实现顺序表的以下基本操作

4-2.intFind(constSeqListL,ListDatax);

//查询顺序表中值与x相同数据的序号,如果顺序表中不存在x,则返回-1.

4-3.intNext(constSeqListL,ListDatax);

//查询序列表中值为x的节点的后继,如果不存在则返回-1.

4-4.intPrevious(constSeqListL,ListDatax){

//查询序列表中值为x的节点的前驱,如果不存在则返回-1.;任务一.实现顺序表的以下基本操作

5.voidPrintList(constSeqListL);

//输出顺序表中的元素.要求相邻元素之间有空格,输出完最后一个元素后增加换行.

//例如[1,2,3]的输出结果为123\n

注意观察分析所写算法的复杂度。;任务二.顺序表拓展1

实现函数

intGetAverage(constSeqListL);

//返回顺序表所有元素的平均值.(结果取平均值的整数部分.);任务三.顺序表拓展2

实现函数

voidUnique(SeqListL);

/*

去除顺序表中所有的重复数据.

例如,如果顺序表L中的数据原来为

[1,2,3,4,2,3]

则Unique(L)后,结果为

[1,2,3,4]

*/;实现一个可变长的顺序表

我们可以注意到#defineLiseSize100限制了顺序表的最大长度。如果我们更改我们的定义方式

typedefintListData;

typedefstruct{

ListData*data;//存储空间基址

intlength; //当前元素个数

intListSize;

}SeqList;

则可以通过控制ListSize来控制数组的大小。当然由于分配的内存长度可能与ListSize不符，需要释放并重新分配空间。;实现一个可变长的顺序表

现在考虑以下算法：

假定最开始??，ListSize=1，每当SeqList中数据充满整个线性表时，我们将ListSize进行ListSize*=2操作，并重新分配内存空间，将数据复制到新的空间，再释放原来分配到的空间。每次数据满时都重复这种操作。

假定经过一系列Delete()操作，留下的数据已经不足ListSize的四分之一，此时我们将ListSize进行ListSize/=2操作，并重新分配内存空间，将数据复制到新的空间，再释放原来的空间。每次数据量不足ListSize的四分之一时都进行这种操作。;实现一个可变长的顺序表

这种数据结构被称作“动态数组”。C++的STL标准库中vector就是用这种方法实现的。

可以证明，这种方法会让每个元素分配的时间代价降低为O(1)。

附加题要求：重构Insert,Delete,unqiue方法，使得线性表不会收到最大长度的限制。

注意内存泄漏问题、程序正确性以及时间空间复杂度问题。

参考博客：/qqarticle/details作业命名方式;注意事项