数据结构与程序设计（王丽苹）14-chapter06（顺序list）

4/30/2026数据结构与程序设计1数据结构与程序设计(14)王丽苹lipingwang@4/30/2026数据结构与程序设计2第六章ListsandStrings

列表和字符串Restrictedlists,likestacksandqueues,inwhichchangesonlyattheendsofit.Lists,inwhichinsertions,deletions,andretrievalsmayoccuratanypointofit.Strings,是特殊的List，表示字符的集合。4/30/2026数据结构与程序设计3ListDefinitionP213AlistofelementsoftypeTisafinitesequenceofelementsofTtogetherwiththefollowingoperations: 1.Constructthelist,leavingitempty. 2.Determinewhetherthelistisempty

ornot. 3.Determinewhetherthelistisfullornot. 4.Findthesize

ofthelist. 5.Clear

thelisttomakeitempty. 6.Insert

anentryataspecifiedpositionofthelist. 7.Remove

anentryfromaspecifiedpositioninthelist. 8.Retrieve

theentryfromaspecifiedpositioninthelist. 9.Replace

theentryataspecifiedpositioninthelist. 10.Traverse

thelist,performingagivenoperationoneachentry.4/30/2026数据结构与程序设计4ImplementationofListList的有两种实现方式：顺序实现链式实现目录List下例程：为List的顺序实现方式。4/30/2026数据结构与程序设计5ImplementationofListP219enumError_code{underflow,overflow,range_error,success};constintmax_list=30;template<classList_entry>classList{public://methodsoftheListADT List(); intsize()const; boolfull()const; boolempty()const; voidclear(); voidtraverse(void(*visit)(List_entry&));//遍历整个List Error_coderetrieve(intposition,List_entry&x)const; Error_codereplace(intposition,constList_entry&x); Error_coderemove(intposition,List_entry&x); Error_codeinsert(intposition,constList_entry&x);protected://datamembersforacontiguouslistimplementation intcount; List_entryentry[max_list];};4/30/2026数据结构与程序设计6ImplementationofListtemplate<classList_entry>List<List_entry>::List()/*Post:TheListhasbeencreatedandisinitializedtobeempty.*/{ count=0;}4/30/2026数据结构与程序设计7ImplementationofListtemplate<classList_entry>intList<List_entry>::size()const/*Post:ThefunctionreturnsthenumberofentriesintheList.*/{ returncount;}4/30/2026数据结构与程序设计8ImplementationofListtemplate<classList_entry>boolList<List_entry>::full()const/*Post:ThefunctionreturnstrueorfalseaccordingtowhethertheListisfullornot.*/{ return(count==max_list);}4/30/2026数据结构与程序设计9ImplementationofListtemplate<classList_entry>boolList<List_entry>::empty()const/*Post:ThefunctionreturnstrueorfalseaccordingtowhethertheListisemptyornot.*/{returncount==0;}4/30/2026数据结构与程序设计10ImplementationofListtemplate<classList_entry>voidList<List_entry>::clear()/*Post:AllListentrieshavebeenremoved;theListisempty.*/{count=0;}4/30/2026数据结构与程序设计11ImplementationofListtemplate<classList_entry>Error_codeList<List_entry>::insert(intposition,constList_entry&x)/*Post:IftheListisnotfulland0<=position<=n;wherenisthenumberofentriesintheList,thefunctionsucceeds:Anyentryformerlyatpositionandalllaterentrieshavetheirpositionnumbersincreasedby1andxisinsertedatpositionoftheList.Else:Thefunctionfailswithadiagnosticerrorcode.*/{ if(full())returnoverflow; if(position<0||position>count)returnrange_error; for(inti=count-1;i>=position;i--)entry[i+1]=entry[i]; entry[position]=x; count++; returnsuccess;}4/30/2026数据结构与程序设计12ImplementationofListtemplate<classList_entry>Error_codeList<List_entry>::remove(intposition,List_entry&x)/*Post:If0<=position<n,wherenisthenumberofentriesintheList,thefunctionsucceeds:TheentryatpositionisremovedfromtheList,andalllaterentrieshavetheirpositionnumbersdecreasedby1.Theparameterxrecordsacopyoftheentryformerlyatposition.Else:Thefunctionfailswithadiagnosticerrorcode.*/{ if(empty())returnunderflow; if(position<0||position>=count)returnrange_error; x=entry[position]; for(inti=position;i<count-1;i++)entry[i]=entry[i+1]; count--; returnsuccess;}4/30/2026数据结构与程序设计13ImplementationofListtemplate<classList_entry>Error_codeList<List_entry>::replace(intposition,constList_entry&x)/*Post:If0<=position<n,wherenisthenumberofentriesintheList,thefunctionsucceeds:Theentryatpositionisreplacedbyx;allotherentriesremainunchanged.Else:Thefunctionfailswithadiagnosticerrorcode.*/{ if(position<0||position>=count)returnrange_error; entry[position]=x; returnsuccess;}4/30/2026数据结构与程序设计14ImplementationofListtemplate<classList_entry>Error_codeList<List_entry>::retrieve(intposition,List_entry&x)const/*Post:If0<=position<n,wherenisthenumberofentriesintheList,thefunctionsucceeds:Theentryatpositioniscopiedtox;allListentriesremainunchanged.Else:Thefunctionfailswithadiagnosticerrorcode.*/{ if(position<0||position>=count)returnrange_error; x=entry[position]; returnsuccess;}4/30/2026数据结构与程序设计15补充：指向函数的指针定义格式为：函数返回值类型(*指针变量)(形参列表);函数存放在内存的代码区域内，它们同样有地址，我们如何能获得函数的地址呢？如果我们有一个inttest(inta)的函数，那么，它的地址就是函数的名字，这一点如同数组一样，数组的名字就是数组的起始地址。定义一个指向函数的指针用如下的形式，以上面的test()为例：int(*fp)(inta);//这里就定义了一个指向函数的指针函数指针不能指向不同类型，或者是带不同参数的函数。指向函数的指针常用于函数的形参中4/30/2026数据结构与程序设计16#include<iostream>#include<string>usingnamespacestd;

inttest(inta);

voidmain(){cout<<“函数地址：”<<test<<endl;//显示函数入口地址

int(*fp)(inta);//定义了一个指向函数的指针fpfp=test;//将函数test的地址赋给函数指针fpcout<<fp(5)<<endl;//输出fp(5),这是标准c++的写法,cout<<(*fp)(10)<<endl;//(*fp)(10)这是兼容c语言的标准写法,//两种写法的功能相同,但注意区分,避免写的程序产生移植性问题!}

inttest(inta){returna;}4/30/2026数据结构与程序设计17ImplementationofListtemplate<classList_entry>voidList<List_entry>::traverse(

void(*visit)(List_entry&))/*Post:Theactionspecifiedbyfunction(*visit)hasbeenperformedoneveryentryoftheList,beginningatposition0anddoingeachinturn.*/{ for(inti=0;i<count;i++)(*visit)(entry[i]);}4/30/2026数据结构与程序设计18ImplementationofListtemplate<classList_entry>voidupdate(List_entry&x){ x*=2; }4/30/2026数据结构与程序设计19ImplementationofListtemplate<classList_entry>voidprint(List_entry&x){ cout<<x<<endl; }4/30/2026数据结构与程序设计20ImplementationofListvoidmain(){ List<int>mylist; for(int