国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > php开源 > 综合技术 > 线性表-顺序表、链表类模板的实现(数据结构基础 第2周)

线性表-顺序表、链表类模板的实现(数据结构基础 第2周)

来源:程序员人生   发布时间:2016-08-03 09:05:39 阅读次数:1429次

学习完课程后,自己用C++实现了简单的顺序表和链表,并用约瑟夫问题做了测试,不保证完全正确。
其中有1点需要注意1下:C++中类模板声明头文件和实现头文件不可以分离到.h和.cpp中,否则没法正常编译,详见:https://www.zhihu.com/question/20630104

源码
1.顺序表
//seqlist.h

#pragma once #include <iostream> using namespace std; template <class T> class seqlist { private: T* aList; //存储顺序表的实例 int maxSize; //顺序表实例的最大长度 int curLen; //顺序表确当前长度 int position;//当前处理位置 public: seqlist(const int size); ~seqlist(); void clear(); //置空线性表 int length(); bool isEmpty(); //线性表为空时,返回true bool append(const T value); //在表尾添加1个元素value,表的长度增1 bool insert(const int p, const T value); //在位置p上插入1个元素value,表的长度增1 bool delet(const int p); //删除位置p上的元素,表的长度减1 bool getPos(int& p, const T value); //查找值为value的元素并返回其位置 bool getValue(const int p, T& value); //把位置p元素值返回到变量value bool setValue(const int p, const T value); //用value修改位置p的元素值 }; template <class T> seqlist<T>::seqlist(const int size) { maxSize=size; aList = new T[maxSize]; curLen=position=0; } template <class T> seqlist<T>::~seqlist() { delete []aList; } template <class T> void seqlist<T>::clear() { delete [] aList; curLen=position=0; aList=new T[maxSize]; } template <class T> int seqlist<T>::length() { return curLen; } template <class T> bool seqlist<T>::isEmpty() { if (curLen==0) { return true; } else { return false; } } template <class T> bool seqlist<T>::append(const T value) { if (curLen>=maxSize) //检查顺序表是不是溢出 { cout << "The list is overflow" << endl; return false; } aList[curLen]=value; curLen++; return true; } //设元素类型为T,aList是存储顺序表的数组,maxSize是其最大长度; //p为新元素value的插入位置,插入成功则返回true,否则返回false template <class T> bool seqlist<T>::insert(const int p, const T value) { if (curLen>=maxSize) //检查顺序表是不是溢出 { cout << "The list is overflow" << endl; return false; } if (p<0 || p>curLen) //检查插入位置是不是合法 { cout << "Insertion point is illegal" << endl; return false; } for(int i=curLen; i>p; i--) aList[i]=aList[i-1]; //从表尾curLen⑴起往右移动直到p aList[p]=value; //位置p处插入新元素 curLen++; //表的实际长度增1 return true; } //设元素的类型为T;aList是存储顺序表的数组;p为行将删除元素的位置 //删除成功则返回true, 否则返回false template <class T> bool seqlist<T>::delet(const int p) { if (curLen<=0) //检查顺序表是不是为空 { cout << "No element to delete" << endl; return false; } if (p<0 || p>curLen-1) //检查删除位置是不是合法 { cout << "deletion is illegal" << endl; return false; } for(int i=p; i<curLen; i++) aList[i]=aList[i+1]; curLen--; return true; } template <class T> bool seqlist<T>::getPos(int& p, const T value) { for(int i=0; i<curLen; i++) if (aList[i]==value) { p=i; return true; } cout << "can not find element: " << value << endl; return false; } template <class T> bool seqlist<T>::getValue(const int p, T& value) { if (curLen<=0) //检查顺序表是不是为空 { cout << "No element" << endl; return false; } if (p<0 || p>curLen-1) //检查删除位置是不是合法 { cout << "getvalue is illegal" << endl; return false; } value = aList[p]; return true; } template <class T> bool seqlist<T>::setValue(const int p, const T value) { if (curLen<=0) //检查顺序表是不是为空 { cout << "No element" << endl; return false; } if (p<0 || p>curLen-1) //检查删除位置是不是合法 { cout << "setvalue is illegal" << endl; return false; } aList[p] = value; return true; }

//source.cpp

#include <iostream> #include "seqlist.h" #include <stdio.h> using namespace std; void josephus_seq(seqlist<int>& palist, int s, int m) { int del = s; int w=0; for(int i=palist.length(); i>0; i--) { del=(del+m-1)%i; //要删除的元素的索引 if (del==0) del = i; palist.getValue(del-1, w); //求出第del个元素的值 printf("Out element %d \n", w); //元素出列 palist.delet(del-1); //删除出列的元素 } } int main() { seqlist<int> jos_alist(100); int n, s, m; printf("\n please input the values(<100) of n = "); //参与游戏的人数 scanf("%d", &n); printf("please input the values of s = "); //开始的人 scanf("%d", &s); printf("please input the values of m = "); ///单词计数 scanf("%d", &m); for (int i=0; i<n; i++) { jos_alist.append(i+1); } josephus_seq(jos_alist, s, m); return 0; }

2.链表
//lnklist.h

#pragma once template <class T> class Link { public: T data; //用于保存结点元素的内容 Link<T> *next; //指向后继结点的指针 Link(const T info, Link<T>* nextValue=NULL) { data=info; next= nextValue; } Link():next(NULL) {} }; template <class T> class lnkList:public Link<T> { private: Link<T> *head, *tail; //单链表的头尾指针 Link<T>* setPos(const int i); //返回第i个元素的指针值 public: lnkList(); //构造函数 ~lnkList(); //析构函数 bool isEmpty(); //判断链表是不是为空 void clear(); //置空线性表 int length(); //返回此链表当前实际长度 bool append(const T value); //在表尾添加1个元素value,表的长度增1 bool insert(const int i, const T value); //在位置i上插入1个元素value,表的长度增1 bool delet(const int i); //删除位置i上的元素,表的长度减1 bool getValue(const int i, T& value); //把位置i元素值返回到变量value bool getPos(int& i, const T value); //查找值为value的元素并返回其位置 }; template <class T> lnkList<T>::lnkList() { head=NULL; tail=NULL; } template <class T> lnkList<T>::~lnkList() { if (head==NULL) { return; } Link<T>* cur=head; while(cur != NULL) { Link<T>* del=cur; cur = cur->next; delete del; } delete cur; head=NULL; tail=NULL; } template <class T> Link<T>* lnkList<T>::setPos(const int i) { int count=0; Link<T>* p=head; //循链定位,若i为0则定位到第1个结点 while(p != NULL && count<i) { p=p->next; count++; } return p; //指向结点i } template <class T> bool lnkList<T>::insert(const int i, const T value) { Link<T> *p, *q; if ((p=setPos(i-1))==NULL) //p是位置i结点的先驱 { cout << "Insertion point is illegal" << endl; return false; } q = new Link<T>(value, p->next); p->next = q; if (p==tail) //插入点在链尾,插入结点成为新的链尾 { tail = q; } return true; } template <class T> bool lnkList<T>::delet(const int i) { Link<T> *p, *q; if (i==0){ //删除头结点 q=head; head=head->next; delete q; return true; } p=setPos(i-1); if (p==NULL || p==tail) { //删除的结点不存在 cout << "deletion is illegal" << endl; return false; } q=p->next; //q是真正待删除结点 if (q==tail) //待删结点为尾结点,则修改尾指针 { tail = p; p->next=NULL; } else p->next=q->next; //删除结点q并修改链指针 delete q; return true; } template <class T> bool lnkList<T>::isEmpty() { if (head==NULL) { return true; } else { return false; } } template <class T> void lnkList<T>::clear() { if (head==NULL) { return; } Link<T>* cur=head; while(cur != NULL) { Link<T>* del=cur; cur = cur->next; delete del; } delete cur; head=NULL; tail=NULL; } template <class T> int lnkList<T>::length() { int count=0; Link<T>* cur=head; while(cur) { count++; cur = cur->next; } return count; } template <class T> bool lnkList<T>::append(const T value) { Link<T>* newLink = new Link<T>(value); if (head==NULL) { head=newLink; tail=head; } else { tail->next = newLink; tail=newLink; } return true; } template <class T> bool lnkList<T>::getPos(int& i, const T value) { Link<T>* cur=head; int count=0; while(cur) { if (cur->data==value) { i=count; return true; } cur = cur->next; count++; } cout << "can not find element: " << value << endl; return false; } template <class T> bool lnkList<T>::getValue(const int i, T& value) { int count=0; Link<T>* cur=head; //循链定位,若i为0则定位到第1个结点 while(cur != NULL && count<i) { cur=cur->next; count++; } if (cur==NULL) { return false; } else { value = cur->data; return true; } }

//source.cpp

#include <iostream> #include "lnklist.h" #include <stdio.h> using namespace std; void josephus_seq(lnkList<int>& palist, int s, int m) { int del = s; int w=0; for(int i=palist.length(); i>0; i--) { del=(del+m-1)%i; //要删除的元素的索引 if (del==0) del = i; palist.getValue(del-1, w); //求出第del个元素的值 printf("Out element %d \n", w); //元素出列 palist.delet(del-1); //删除出列的元素 } } int main() { lnkList<int> jos_alist; int n, s, m; printf("\n please input the values(<100) of n = "); //参与游戏的人数 scanf("%d", &n); printf("please input the values of s = "); //开始的人 scanf("%d", &s); printf("please input the values of m = "); ///单词计数 scanf("%d", &m); for (int i=0; i<n; i++) { jos_alist.append(i+1); } josephus_seq(jos_alist, s, m); return 0; }
生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生