《数据结构示例(一)——顺序表和链表》由会员分享，可在线阅读，更多相关《数据结构示例(一)——顺序表和链表（11页珍藏版）》请在金锄头文库上搜索。
1、1、顺序表 template class SeqList private: T *data; int size; int MaxSize; public: SeqList(int sz=100); SeqList() delete data; int Length() const return size; bool IsEmpty() const return size=0; void Insert(const T void Delete(int k); T GetData(int k) const; int Find(const T void Output(ostream ; templat
2、e SeqList:SeqList(int sz) MaxSize=sz; data=new TMaxSize; size=0; template void SeqList:Insert(const T i-) datai+1=datai; datak-1=x; size+; template void SeqList:Delete(int k) if(size=0) cerrsize ) cerr T SeqList:GetData(int k) const if( ksize ) cerr int SeqList:Find(const T while(i int SeqList:Find(
3、const T i void SeqList:Output(ostream i ostream return out; 2、链表template struct Node T data; Node *next; ; template class LinkList private: Node *head; public: LinkList(); LinkList(); int Length() const; bool IsEmpty() const; void Insert(const T void Delete(int k); T GetData(int k) const; Node * Fin
4、d(const T void ClearList(); void Output(ostream ; template LinkList:LinkList() head = new Node; head-next = NULL; template LinkList:LinkList() Node *p; while(head) p = head; head = head-next; delete p; template int LinkList:Length() const Node *p = head-next; int k=0; while(p) k+; p=p-next; return k
5、; template bool LinkList:IsEmpty() const return head-next = NULL; template void LinkList:Insert( const T int i=0; while(p i+; if(!p) cerr *s = new Node; s-data = x; s-next = p-next; p-next=s; template void LinkList:Delete(int k) if(k *p = head; int i=0; while(p-next i+; if(p-next=NULL) cerr *q = p-n
6、ext; p-next = q-next; delete q; template T LinkList:GetData(int k) const if(k *p=head; int i=0; while(p i+; if(!p) cerrdata; template Node* LinkList:Find(const T while(p return p; /*或 template Node* LinkList:Find(const T while(p)i(p-data = x) return p; else p=p-next; return NULL; /*/template void Li
7、nkList:ClearList() Node *p, *q; p = head-next; while(p) q = p; p = p-next; delete q; head-next = NULL; template void LinkList:Output(ostream while(p) outdatanext; out ostream return out; 3、链表（另一表示法，带 size） template struct Node T data; Node* next; ; template class LinkList private: Node* head; int si
8、ze;public: LinkList(); LinkList(); int Length() const return size; bool IsEmpty() const return size=0; void Insert(const T void Delete(int k); T GetData(int k) const; Node * Find(const T ; template LinkList:LinkList() head = new Node; head-next = NULL; size=0; template LinkList:LinkList() Node *p; w
9、hile(head) p = head; head = head-next; delete p; template void LinkList:Insert( const T for(int i=1; inext;Node *s = new Node; s-data = x; s-next = p-next; p-next = s; size+; template void LinkList:Delete(int k) if( ksize ) cerr* p = head; for(int i=1; inext;Node *q = p-next; p-next = q-next; delete
10、 q; size-; template T LinkList:GetData(int k) const if( ksize ) cerr *p=head; for(int i=1; inext;return p-data; template Node* LinkList:Find(const T while(p return p; 4、对单链表的扩充 void DeleteItems(const T /删除所有值等于 x 的元素 void Reverse(); /将单链表反转 Node* Locate(int i) const; /查找第 i 个结点 Node* max() const; /找
11、出具有最大值的结点 int Count(const T /统计值等于 x 的元素的个数 void Create(int n); /输入 n 个数，建立单链表 void DeleteEqual(); /删除连续出现的值相同的多余元素 void SelectSort()/单链表上的简单选择排序算法template void LinkList:DeleteItems(const T while(q) if(q-data=x) p-next = q-next;delete q;q = p-next;else p = q; q = q-next; template void LinkList:Rever
12、se() /将单链表反转 Node *p=head-next, *q;head-next = NULL;while(p) q = p;p = p-next;q-next = head-next;head-next = q; template Node* LinkList:Locate(int i) const /查找第 i 个结点 if(i *p=head; int k=0; while(p k+; return p; template Node* LinkList:max() const /找出具有最大值的结点 if(IsEmpty() return NULL;Node *pmax, *p;
13、pmax = head-next;p = pmax-next;while(p) if( p-data pmax-data ) pmax = p;p = p-next;return pmax; templateint LinkList:Count(const T int n;while(p) if(p-data = x) n+;p = p-next;return n; template void LinkList:Create(int n) /输入 n 个数，建立单链表 Node *p=head, *q;for(int i=1; i;cin q-data;p-next = q;p = q;q-n
14、ext = NULL; template void LinkList:DeleteEqual() /删除连续出现的值相同的多余元素 Node *p=head-next, *q=p-next;while(q) if(p-data = q-data) p-next = q-next;delete q;q = p-next;else p = q; q=q-next; template void LinkList:SelectSort()/单链表上的简单选择排序算法 Node *p=head, *q, *r, *s;while(p-next-next) s = p;q = p-next;r = q;w
15、hile(r-next) if( r-next-data next-data ) s = r;r = r-next; if(s!=p) p-next = s-next;s-next = s-next-next;p-next-next = q;p = p-next; 其中 if 处可改为if(s!=p) p-next = s-next;s-next = q;Node *t = q-next;q-next = p-next-next;p-next-next = t;5、链表的迭代器类template class ListIterator private:Node *ptr;public: ListIterator(Node *p=0):ptr(p)作者：Leid
