数据结构-chap例、学生健康情况登记表如下

第二 线性例、学生健康情况登记表如 王 系统分(1)逻辑结构的(2)系统操作的分 结(4)系统实线性表的逻辑结构及其基本操a-Linearlist=(D,其中a；接前趋ai-1和一个直接后继ai+1。 数据元素：ai同属于一个数据元素类，i=1,2,……,nn≧0Initiate(L)构造一个空的线性表L。

Locate(L,x)定位操作。Prior(L,data)求前驱。link(L,data)求后继。 template<classT>classLinearList{

virtualintSizeconst0;//virtualintLength()const=virtualintSearch(Tx)const=0;virtualintLocate(inti)const=0;virtualT*getData(inti)const=0;virtualvoidsetData(inti,Tx)=

virtualboolInsert(inti,Tx)=0;virtualboolRemove(inti,T&x)=0;virtualboolIsEmpty()const=0;virtualboolIsFull()const=0;virtualvoidSort()=0；virtualvoidinput()=virtualvoidoutput()=virtual(LinearList<T>&L)=

线性表在计算机中的实 结2.操作的实线性表的顺 结组地址连续的单元里。用这种方法的线地址的计 位置LOC(a1)，那么线性表中第i个数据元素的位置LOC(a地址的计由于LOC(ai)与第i-1个数据元素 LOC(ai)=LOC(ai-因此线性表的第i个数据元素ai LLa+i顺 空间属性操作#definemaxSize//constintmaxSize=最大容量TypedefintT;typedefstructTdata[maxSize];//顺序表的静 表intn;//int

}typedefintT;typedefstruct{Tintintn;//int}

SeqListLa.n则表示线性表的当前元素个数顺序表上实现的基 i个元素是La.data[i-1]。constintdefaultSize=100;template<classT>classSeqList:publicLinearList<T>{TintmaxSize;intlast;

voidreSize(int SeqList(intsz=defaultSize);SeqList(SeqList<T>&L);

～SeqList{delete intSize()const{returnmaxSize;}//求表最大容量intLength()const{returnlast+1;} intSearch(T&x)const;intLocate(inti)const;boolgetData(inti,T&x);//取第iboolInsert(inti,T&x);boolRemove(inti,T&x);

template<classT>SeqList<T>::SeqList(intsz){if(sz>0)maxSize=sz;last=-data=newT[maxSize];if(data==NULL)

cerr 分配错误！exit(1);}template<class

SeqList<T>::SeqList(SeqList<T>&L){Tvalue;maxSize= last=L.Length()-data=newT[maxSize];if(data==NULL)

{cerr 分配错误！endl;for(inti1ilast+1 L.getData(i,value);data[i-1]=value;template<classintSeqList<T>::search(T&x)constfor(inti=1;i<=n;i++) if(data[i-1]==x)returnreturn

查找算法的分(a1，…ai-(a1，…ai-插入算法的步骤；将线性表的第i元素以及其后面的所有元把线性表的长度增加1template<class

boolSeqList<T>::Insert(inti,T&x)//将新元素x插入到表中第i(1≤i≤n+1if(nmaxSizereturn if(i1||iLength()+1returnfalse;//参数ifor(intjlast+1jij-- data[j]=data[j-data[i-1] //插入(i表项在data[i-1]处 return 分析算法的复杂这里的问题规模是表的长度，设它的值为n，a) …ai-a)删除算法的步骤把线性表的长度减少1template<classboolSeqList<T>::Remove(inti,T&x) if(n0)return if(i1||ilast+1return x=data[i-for(intjijlast data[j-1]= returnvoidUnion(SeqList<int>&SeqList<int>&LB)intn1=LA.Length(),n2=LB.Length();inti,k,x;for(i=0;i<n2;i++)x=LB.getData(i);k=

if(k {LA.Insert(n1,x);n1++;}voidIntersection(SeqList<int>&SeqList<int>&LB){intn1=LA.Length();intx,k,i=while(i<n1)x k if(k LA.Remove(ix);n1--//在LAelse }}完整系统的运行逻

例、学生健康情况登记表如 一 79

线性表^^ structListNode{ intdata; //Tdata;ListNode*(SinglyLinkedΛΛ:反classList//链表类,直接使用链表结点类的数据ListNode

//表头指结点指针的定 ListNode<T> newp=newListNode<T>(deletep->link=q;(q空指针NULL或01、头插入template<classT>List<T>::HLinkList(intn){for p=newListNode<T>(}}单链表的建 template<classT>List<T>::RLinkList(intn) p=newListNode<T>(tail-

}}template<classList<T>::RLinkList(intn{

引入表头first=tail=newListNode<T>( p=newNode<T>();

}}设置表头结点的目统一空表与非空表简化链表操作的实

1a

在单链表的类模板定义中，增加了表头结点template<classstructLinkNodeTdata;LinkNode<T>*link;

LinkNode()linkNULL LinkNode(Titem,LinkNode<T>*ptr={data=item;link=ptr;} booloperator(Txreturndata.keyxbooloperator!=(Tx){returndata.key!=x;template<classT>classList{LinkNode<T*first;//表头指针List()firstnewLinkNode<T>;}//List(Tx){first=newLinkNode<T>(x);List(List<T>&~List(){voidmakeEmpty();intLength()const;

LinkNode<T*Search(Tx)搜索含xLinkNode<T>*Locate(inti);T*getData(inti);voidsetData(inti,TboolInsert(inti,Tx);boolRemove(inti,T&x);

boolIsEmpty() {returnfirst->link==NULL?true:false;}LinkNode<T>*getFirst()const{returnfirst;}voidsetFirst(LinkNode<T>*f){first=f;}voidSort();voidPrint();

voidprint(template<classT>VoidList<T>::Print(){ListNode<T>*p=first-while(p!=NULL p=p- }}intlength(

template<classintList<T>::Length(){ListNode<T>*p=first-intcount=while(p!=NULL)p=p->link;

}return}算法分查找操按序号查找——单链表找第i个元素——按值查找——LinkNode<T>*locate(intiitemplate<classLinkNode<T>*List<T>::Locate(inti)//i个元素的地址。若i0iif(i0)return LinkNode<T>*current=first;intk=0;while(current!=NULL&&k<i){current=current- k++;return 算法的分1）最好情况：当然是要找的结点序号为1时，此时只需 情况：当要找的结点序号大于或等于n时，比较 LinkNode<T>*::Search(Txxtemplate<classLinkNode<T>*List<T>::Search(Tx)//该结点地址否则返回NULLLinkNode<T>*current=first-while(current!=NULL&¤t->data!=xcurrent=current-returncurrent;算法分 xboolList<T>::Insert(inti,T 寻找第i个结点，使指针p若由于i不合理而找不到相应的结点，则输出信息，否则生成一个新结点s，并将s插入到结点p之后ixxtemplate<classboolList<T>::Insert(inti,Tx)LinkNode<T>*current=if(current==NULL)returnfalse;LinkNode<T>*newNode=newLinkNode<T>(x);newNode->link=current->link;current->link=newNode;

return 插ananpx xp->link=p->link-boolList<T>::Remove(inti,T&x寻找第i号结点，使指针p若由于i不合理而找不到相应的结点，则返回NULL，改变p的指针域，使得第i号结点从链表中被删除，释template<classboolList<T>::Remove(inti,T&x) LinkNode<T>*current=Locate(i-if(current==NULL||current->link==returnfalse;//删除不成功LinkNode<T*delcurrent->link;current->link=del->link;x=del->data;deletereturn算法分删除算法分改进方案: template<classT>List<T>::~List(){LinkNode<T>*q;while(first!=NULL){q //保存被删结first=first-delete}

//从链上摘下该结//删其他形式的链式结循环链anan-

template<classT>structCircLinkNode{Tdata;

CircLinkNode(CircLinkNode<T>*next=NULL){link=next;}CircLinkNode(Td,CircLinkNode<T>*next=NULL){data=d;link=next;}boolOperator==(Tx){returndata.key==x.key;boolOperator!=(Tx){returndata.key!=x.key;template<classT>classCircList{

CircLinkNode<T>*first*last;//头指针CircList(constTx);intLength()

boolIsEmpty(){returnfirst->link==first;CircLinkNode<T>*getHead()voidsetHead(CircLinkNode<T>*pCircLinkNode<T>*Search(Tx);//搜索CircLinkNode<T>*Locate(inti);//定位T*getData(intivoidsetData(inti,Tx);boolInsert(inti,Tx);boolRemove(inti,T&x);

搜索

current current搜索成currentcurrent 搜索

搜索不成template<classCircListNode<T>*CircList<T>::Search(Tx{current=first-while(current!=first&¤t->data!=xcurrent=current->link;returncurrent;}例、在链表上实现将两个线性表3)。 非空 空p==p->llink->rlink==p->rlink- p- p-template<classstructDblNodeT

DblNode<T*lLink DblNode(DblNode<T>*l=DblNode<T>*r=NULLlLinkl;rLinkr DblNode(Tvalue,DblNode<T>*l=DblNode<T>*r=datavalue;lLinkl;rLinkr//template<classclassDblList{

DblListTuniqueVal first=newDblNode<T>first->rLink=first->lLink=DblNode<T>*getFirst()const{returnfirst;}voidsetFirst(DblNode<T>*ptr){first=ptr;}DblNode<T>*Search(Tx,intd);DblNode<T>*Locate(inti,intd,boolInsert(inti,Tx,intdboolRemove(inti,T&x,intd); boolIsEmpty(){returnfirst->rlink==first;}DblNode<T 双向链表的操作特

搜索

搜索成搜索

搜索不template<classDblNode<T>*DblList<T>::Search(Tx,intd)DblNode<T>*current=(d==first->lLink:first->rLink; while(current!=first&¤t->data!=x)current=(d==0)current->lLink:current-if(current!=first)returnelsereturn

boolDblList<T>::Insert(inti,Tx,intdppess->rlink=p->llink; p->rlink=s;s->rlink->llink=s; s->llink=p;stemplate<classboolDblList<T>::Insert(inti,Tx,intd)DblNode<T>*current=Locate(i,ifcurrentNULLreturn DblNode<T>*newNd=newif(d==0){ newNd->lLinkcurrent->lLink链入lLink链current->lLink=newNd;newNd->lLink->rLinknewNd;//链入rLinknewNd->rLink=}else{ newNd->rLink=current->rLink;//链入rLink链current->rLink=newNd;newNd->rLink->lLinknewNd;//链入lLinknewNd->lLink=}return boolDblList<T>::Remove(inti,T&x,intd由参数i和搜索方向d求得结点的指针p若第i个结点存在，则删除双向循环链表中的由p所指

pp->llink->rlink=p->rlink;p->rlink->llink=p->llink;template<classboolDblList<T>::Remove(inti,T&x,intd)DblNode<T>*current=Locate(i,if(currentNULLreturn current->rLink->lLink=current-current->lLink->rLink=current-x=current->data;deletereturn

作就只需修改相应结点的指针域即可完成，从而克服了顺序 结点额外增加相应的指针域，从而使结点的 密度比顺 在链式结构中要查找某一结点，一般要从链头开始沿链进行扫描才能找到该结点，其平均时间复杂度为O(n)。因此，链式结构是一种非随机结构。线性表的应例1.将一个元素插入到一个有序表中，并要求插入新元素(1)设线性表在数组A[1..arrsize]的前elenum个分量中，且递增有序。试编写一个算法：将x插入到线性表的例2（1） 思路分由于这n个人原坐的位置号分别为1，3，...,n,显然我们可以采用数组结实例分析——顺voidJosephus(intn,intstart,intm{intcount,j,*A=newint[n]forj=0j<nj //初始化，把各位置号存入数组count=1;start--whilecountn //当前已站出来人的数{cout<<A[start];输出当前要站出来人的位置for(j=start;j<n-count;j++A[j]=A[