线性表.docx
- 文档编号:9175749
- 上传时间:2023-05-17
- 格式:DOCX
- 页数:29
- 大小:20.24KB
线性表.docx
《线性表.docx》由会员分享,可在线阅读,更多相关《线性表.docx(29页珍藏版)》请在冰点文库上搜索。
线性表
顺序表
template
classList{
Public:
list();
intsize()const;
boolfull()const;
boolempty()const;
voidclear();
voidtraverse(void(*visit)(List_entry&));
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:
intcount;
List_entryentry[max_list];
};
插入算法(只有头指针的单链表)
template
Error_codeList
:
insert(intposition,constList_entry&x){
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;
}
template
voidList
:
traverse(void(*visit)(List_entry&)){
for(inti=0;i (*visit)(entry[i]); } template structNode{ Node_entryentry; Node Node(); Node(Node_entry,Node }; template classList{ public ~List(); List(constList voidoperator=(constList protected: intcount; Node Node }; template Error_codeList : insert(intposition,constList_entry&x){ if(position<0||position>count) returnrange_error; Node if(position>0){ previous=set_position(position-1); following=previous->next; } elsefollowing=head; new_node=newNode if(new_node==NULL); returnoverflow; if(position==0) head=new_node; else previous->next=new_node; count++; returnsuccess; } 单链表(当前指针) template Node : set_position(intposition)const{ Node for(inti=0;i returnq; } template classList{ public: protected: intcount; mutableintcurrent_position; Node mutableNode voidset_position(intposition)const; }; template voidList : set_position(intposition)const{ if(position current_position=0; current=head; } for(;current_position! =position;current_position++) current=current->next; } 带当前指针的单链表的结点删除算法 template Error_codeList : remove(intposition,List_entry&x){ If(empty())returndownflow; If(position<0‖position>count)returnrange_error; else{ Node if(position==o){ following=head; head=head->next;current=head;current_position=0;} else{previous=set_position(position-1); following=previous->next; previous->next=following->next; current_position++; current=previous->next;} x=following->data; deletefollowing; count--;} returnsuccess; } 建立有序表的算法 voidInsertOrder(Node Node previous=NULL; following=head; while(following! =NULL){ if(x break; previous=following; following=following->next; } new_node=newNode if(previous==NULL) head=new_node; else{ previous->next=new_node; } count++; } 用链表排序 voidLinkSort(Node_entrya[],intn){ Node inti; for(i=0;i InsertOrder(ordlist,a[i]); current=ordlist; i=0; while(current! =NULL) { a[i]=current->data;i++; current=current->next; Clear(ordlist); } 带头结点的单链表 template Node : set_position(intposition)const{ Node for(inti=0;i returnq; } 不带头结点的插入算法 template Error_codeList : insert(intposition,constList_entry&x){ if(position<0||position>count) returnrange_error; Node if(position>0){ previous=set_position(position-1); following=previous->next; } elsefollowing=head; new_node=newNode if(new_node==NULL); returnoverflow; if(position==0) head=new_node; else previous->next=new_node; count++; returnsuccess; } 带头结点的插入算法 template Error_codeList : insert(intposition,constList_entry&x){ if(position<0||position>count) returnrange_error; Node if(position>0) previous=set_position(position-1); elseprevious=head; following=previous->next; new_node=newNode if(new_node==NULL) returnoverflow; else previous->next=new_node; count++; returnsuccess; } 单链表逆置 template voidReverse(Node Node p=head;previous=NULL; while(p! =NULL){ following=p->next; p->next=previous; previous=p; p=following; } head=previous; } 子集判断算法 template BoolIsSubSet(Node Node p=head1; while(p! =NULL){ x=p->data;q=head2; while(q! =NULL){ if(q->data==x)break; elseq=q->next; } if(q==NULL)return0; p=p->next; } return1; } 求集合的交集 template Node Node p=head1;q=head2; c=newnode while(p! =NULL&&q! =NULL){ if(p->data>q->data)q=q->next; elseif(p->data<q->data)p=p->next; else{ s=newnode r->next=s;r=s; p=p->next;q=q->next; } } head=c->next; deletec; returnhead; } 数组元素奇偶调整算法 template voidOdd-EvenAdjust(List&A){ inti=0,j=A.count-1;List_entrytemp; while(i<=j){ while(A.entry[i]%2! =0&&i<=j)i++; while(A.entry[j]%2==0&&j>=i)j--; if(i temp=A.entry[i]; A.entry[i]=A.entry[j]; A.entry[j]=temp; } } } 表定位 voidLinkedList intStartPos; if(front==NULL) return; if(pos<0‖pos>count-1){ cerr<<“Reset: Invalidlistposition: ”< return; } if(pos==0){ previous=NULL; current=front; position=0; } else{ current=front->next; previous=front; startPos=1; for(position=startPos;position! =pos;position++){ previous=currrent; current=current->next; } } } 遍历函数 VoidLinkedList if(current! =NULL){ previous=current; current=current->next; position++; } } 表插入方法 VoidLinkedList Node if(previous==NULL){ new_node=newNode front=new_node; } else{ new_node=newNode previous->next=new_node; } if(previous==rear){ rear=new_node; position=count; } current=new_node; count++; } 表删除方法 voidLinkedList Node if(current==NULL){ cerr<<“Invaliddeletion! ”< return; } if(previous==NULL){ p=front; front=p->next; } else p=previous->next; if(p==rear){ rear=previous; Position--; } current=p->next; FreeNode(p); count--; } 循环链表的定义 template public: CList(); intCsize()const; boolCfull()const; boolCempty()const; voidCclear(); voidCtraverse(void(*visit)(List_entry&)); Error_codeCretrieve(intposition,List_entry&x)const; Error_codeCreplace(intposition,constList_entry&x); Error_codeCremove(intposition,List_entry&x); Error_codeCinsert(intposition,constList_entry&x); voidFirster(); BooleanFirst(); BooleanNext(); BooleanPrior(); protected: intcount; Node Node }; 双向链表结点的声明 template structNode{ Node_entryentry; Node Node Node(); Node(Node_entry,Node } 双向链表的实现 template classList{ public: protected: intcount; mutableintcurrent_position; mutableNode voidset_position(intposition)const; }; template voidList : set_position(intposition)const{ if(current_position<=position) for(;current_position! =position;current_position++) current=current−>next; else for(;current_position! =position;current_position−−) current=current−>back; } 插入结点算法 template Error_codeList : insert(intposition,constList_entry&x){ Node if(position<0||position>count) returnrange_error; if(position=0){ if(count=0) following=NULL; else{ set_position(0); following=current; } preceding=NULL; } else{ set_position(position-1); preceding=current; following=preceding->next; } new_node=newNode if(new_node==
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 线性