《数据结构与程序设计王丽苹14chapter06顺序list.ppt》由会员分享，可在线阅读，更多相关《数据结构与程序设计王丽苹14chapter06顺序list.ppt（23页珍藏版）》请在三一办公上搜索。
1、10/13/2023,数据结构与程序设计,1,数据结构与程序设计(14),王丽苹,10/13/2023,数据结构与程序设计,2,第六章 Lists and Strings列表和字符串,Restricted lists,like stacks and queues,in which changes only at the ends of it.Lists,in which insertions,deletions,and retrievals may occur at any point of it.Strings,是特殊的List，表示字符的集合。,10/13/2023,数据结构与程序设计,3
2、,List Definition P213,A list of elements of type T is a finite sequence of elements of T together with the following operations:1.Construct the list,leaving it empty.2.Determine whether the list is empty or not.3.Determine whether the list is full or not.4.Find the size of the list.5.Clear the list
3、to make it empty.6.Insert an entry at a specified position of the list.7.Remove an entry from a specified position in the list.8.Retrieve the entry from a specified position in the list.9.Replace the entry at a specified position in the list.10.Traverse the list,performing a given operation on each
4、entry.,10/13/2023,数据结构与程序设计,4,Implementation of List,List的有两种实现方式：顺序实现链式实现目录List下例程：为List的顺序实现方式。,10/13/2023,数据结构与程序设计,5,Implementation of List P219,enum Error_codeunderflow,overflow,range_error,success;const int max_list=30;template class List public:/methods of the List ADTList();int size()const;b
5、ool full()const;bool empty()const;void clear();void traverse(void(*visit)(List_entry,10/13/2023,数据结构与程序设计,6,Implementation of List,template List:List()/*Post:The List has been created and is initialized to be empty.*/count=0;,10/13/2023,数据结构与程序设计,7,Implementation of List,template int List:size()cons
6、t/*Post:The function returns the number of entries in the List.*/return count;,10/13/2023,数据结构与程序设计,8,Implementation of List,template bool List:full()const/*Post:The function returns true or false according to whether the List is full or not.*/return(count=max_list);,10/13/2023,数据结构与程序设计,9,Implement
7、ation of List,template bool List:empty()const/*Post:The function returns true or false according to whether the List is empty or not.*/return count=0;,10/13/2023,数据结构与程序设计,10,Implementation of List,template void List:clear()/*Post:All List entries have been removed;the List is empty.*/count=0;,10/13
8、/2023,数据结构与程序设计,11,Implementation of List,template Error_code List:insert(int position,const List_entry,10/13/2023,数据结构与程序设计,12,Implementation of List,template Error_code List:remove(int position,List_entry,10/13/2023,数据结构与程序设计,13,Implementation of List,template Error_code List:replace(int position,
9、const List_entry,10/13/2023,数据结构与程序设计,14,Implementation of List,template Error_code List:retrieve(int position,List_entry,10/13/2023,数据结构与程序设计,15,补充：指向函数的指针,定义格式为：函数返回值类型(*指针变量)(形参列表);函数存放在内存的代码区域内，它们同样有地址，我们如何能获得函数的地址呢？如果我们有一个int test(int a)的函数，那么，它的地址就是函数的名字，这一点如同数组一样，数组的名字就是数组的起始地址。定义一个指向函数的指针用如下
10、的形式，以上面的test()为例：int(*fp)(int a);/这里就定义了一个指向函数的指针 函数指针不能指向不同类型，或者是带不同参数的函数。指向函数的指针常用于函数的形参中,10/13/2023,数据结构与程序设计,16,#include#include using namespace std;int test(int a);void main()cout“函数地址：”testendl;/显示函数入口地址 int(*fp)(int a);/定义了一个指向函数的指针fp fp=test;/将函数test的地址赋给函数指针fp coutfp(5)endl;/输出fp(5),这是标准c+的
11、写法,cout(*fp)(10)endl;/(*fp)(10)这是兼容c语言的标准写法,/两种写法的功能相同,但注意区分,避免写的程序产生移植性问题!int test(int a)return a;,10/13/2023,数据结构与程序设计,17,Implementation of List,template void List:traverse(void(*visit)(List_entry,10/13/2023,数据结构与程序设计,18,Implementation of List,template void update(List_entry,10/13/2023,数据结构与程序设计,1
12、9,Implementation of List,template void print(List_entry,10/13/2023,数据结构与程序设计,20,Implementation of List,void main()List mylist;for(int i=0;i5;i+)mylist.insert(i,i);/for(int i=1;i5;i+)mylist.insert(i,i);coutYour list have mylist.size()elements:endl;mylist.traverse(print);mylist.remove(0,i);coutAfter r
13、emove(0):endl;mylist.traverse(print);/实参为函数名 printcoutAfter update:endl;mylist.traverse(update);/实参为函数名 updatemylist.traverse(print);,10/13/2023,数据结构与程序设计,21,Result,Your list have 5 elements:01234After remove(0):1234After update:2468,10/13/2023,数据结构与程序设计,22,各项操作的时间代价分析,Insert and remove require time approximately proportional to n.List（构造函数）,Clear,Empty,Full,Size,Replace and Retrieve operate in constant time（常量时间）.,10/13/2023,数据结构与程序设计,23,课后作业,P217E5，E8，E11,
