博客
关于我
强烈建议你试试无所不能的chatGPT，快点击我
【C/C++学院】0903-Boost/线性表/哈希存储
阅读量：6581 次
发布时间：2019-06-24

本文共 11414 字，大约阅读时间需要 38 分钟。

boost模板库与线性表

Boost的安装 

使用boost，首先需要进行的环境配置。

#include 
    
     #include 
     
      #include
      
       //区别using namespace std;void main(){	boost::array
       
         myarray = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };	boost::array
        
         ::iterator ibegin = myarray.begin();	boost::array
         
          ::iterator iend = myarray.end(); for (;ibegin!=iend;ibegin++) { cout << *ibegin << endl; } cin.get();}

线性表顺序存储

Myvector.h

#pragma oncetemplate 
    
     class myvector{public:	myvector();	~myvector();	void push_back(T t);	//增 删 查 改	T *find(T t);	void change(T*pos, T t);	void del(T t);	void show();	T operator [](int i);	void insert(T findt, T t);public:	T *p;	int n;//标记内存长度	int realn;//实际长度};

Myvector.cpp

#include "myvector.h"template 
    
     myvector
     
      ::myvector(){	p = nullptr;	n = realn = 0;}template 
      
       myvector
       
        ::~myvector(){	if (p!=nullptr)	{		delete  []p;		p = nullptr;//清空	}}template 
        
         void myvector
         
          ::push_back(T t){ if (p==nullptr) { p = new T;//分配内存 *p = t;//赋值 realn = n = 1; } else { T *ptemp = new T[n + 1];//重新分配内存 for (int i = 0; i < n;i++) { *(ptemp + i) = *(p + i);//拷贝 } *(ptemp + n) = t;//赋值最后一个元素 delete []p; p = ptemp; realn += 1; n += 1; }}template 
          
           void myvector
           
            ::show(){ if (p==NULL) { return; } else { for (int i = 0; i < realn;i++) { cout << p[i] << " "; } cout << "\n"; }}template 
            
             T * myvector
             
              ::find(T t){ for (int i = 0; i < realn; i++) { if (t==*(p+i)) { return p + i; } } return nullptr;}template 
              
               void myvector
               
                ::change(T*pos, T t){ if (pos==nullptr) { return; } else { *pos = t; }}template 
                
                 void myvector
                 
                  ::del(T t){ int pos = -1; for (int i = 0; i < realn; i++) { if (t == *(p + i)) { pos = i; break; } } if (pos!=-1) { if (pos== realn-1) { realn -= 1; } else { for (int i = pos; i < realn-1;i++) { p[i] = p[i + 1]; } realn -= 1; } }}template 
                  
                   void myvector
                   
                    ::insert(T findt, T t){ if (n == realn) { { int pos = -1; for (int i = 0; i < realn; i++) { if (findt== *(p + i)) { pos = i; break; } } if (pos!=-1) { //重新分配内存并拷贝 { T *ptemp = new T[n + 1];//重新分配内存 for (int i = 0; i < n; i++) { *(ptemp + i) = *(p + i);//拷贝 } delete[] p; p = ptemp; realn += 1; n += 1; } for (int i = realn - 2; i>=pos;i--) { p[i + 1]=p[i];//往前移动 } p[pos] = t; } } } else { int pos = -1; for (int i = 0; i < realn; i++) { if (findt == *(p + i)) { pos = i; break; } } if (pos != -1) { for (int i = realn - 1; i >= pos; i--) { p[i + 1] = p[i];//往前移动 } p[pos] = t; realn += 1; } }}template 
                    
                     T myvector
                     
                      ::operator [](int i){ if (i < 0 || i>=realn) { return NULL; } return p[i];}

Main.cpp

#include 
    
     #include
     
      #include 
      
       #include 
       
        #include "myvector.h"#include "myvector.cpp"//因为有template//一定要学会自己怎么写模板库//自己写的模板，写的通用是很难的using namespace std;void main(){	myvector
        
          myv1;	myv1.push_back(11);	myv1.push_back(12);	myv1.push_back(13);	myv1.push_back(14);	myv1.push_back(15);	myvector
         
           myv2; myv2.push_back(31); myv2.push_back(32); myv2.push_back(33); myvector
          
            myv3; myv3.push_back(131); myv3.push_back(132); myv3.push_back(133); myv3.push_back(1337); myvector< myvector
           
            * > myvv;//自己写的模板嵌套用指针 myvv.push_back(&myv1); myvv.push_back(&myv2); myvv.push_back(&myv3); myvv[0]->show(); myvv[1]->show(); myvv[2]->show(); cin.get();}void main1(){ myvector
            
              myv; myv.push_back(11); myv.push_back(12); myv.push_back(13); myv.push_back(14); myv.push_back(15); myv.show(); cin.get();}void main2(){ myvector
             
               myv; myv.push_back(11.2); myv.push_back(12.0); myv.push_back(13.5); myv.push_back(14.9); myv.push_back(15.90); myv.show(); cin.get();}void main5(){ myvector
              
                myv; myv.push_back("av"); myv.push_back("va"); myv.push_back("cc"); myv.push_back("tv"); myv.show(); cin.get();}void main4(){ vector
               
                 myv;// myv.push_back("av"); myv.push_back("va"); myv.push_back("cc"); myv.push_back("tv"); cin.get();}void main312(){ myvector
                
                  myv; myv.push_back(11); myv.push_back(12); myv.push_back(13); myv.push_back(14); myv.push_back(15); myv.show(); int *p = myv.find(13); cout << p << endl; myv.change(p, 23);// myv.show(); myv.del(12); myv.insert(23, 99); myv.show(); cout << myv[2] << endl; cin.get();}

线性表链式存储

Node.h

#pragma oncetemplate 
    
     class Node{public:	T t;//数据	Node *pNext;//指针域 };

List.h

#pragma once#include "Node.h"#include 
    
     template 
     
      class List{public:	Node
      
        *pHead;public:	List();	void add(T t);//尾部插入	void show();//显示	Node
       
         * find(T t);//查找	void change(Node
        
          *p, T newt);//修改	int getnum();//获取个数	bool deletet(T t);	void sort();	void deletesame();//删除相同的元素	bool clear();	void rev();	void insert(T oldt, T newt);	void merge(List & list);	~List();};

List.cpp

#include "List.h"template 
    
     List
     
      ::List(){	this->pHead = nullptr;//设置空节点 	cout << "链表创建" << endl;}template 
      
       List
       
        ::~List(){	cout << "链表销毁" << endl;}template 
        
         void List
         
          ::add(T t){ Node
          
            *pnew = new Node
           
            ;//分配节点 pnew->t = t;//赋值 pnew->pNext = nullptr; if (pHead==nullptr) { this->pHead = pnew;//头结点 } else { Node
            
              *p = pHead;//获取头结点位置 while (p->pNext!=nullptr)//循环到尾部 { p = p->pNext; } p->pNext = pnew; }}template 
             
              void List
              
               ::show(){ Node
               
                 *p = pHead;//获取头结点位置 while (p!= nullptr)//循环到尾部 { cout << p->t << " "; p = p->pNext; } cout << endl;}template 
                
                 Node
                 
                   * List
                  
                   ::find(T t){ Node
                   
                     *p = pHead;//获取头结点位置 while (p != nullptr)//循环到尾部 { if (p->t==t) { return p; } p = p->pNext; } return nullptr;}template 
                    
                     void List
                     
                      ::change(Node
                      
                        *p, T newt){ if (p==nullptr) { return; } p->t = newt;}template 
                       
                        int List
                        
                         ::getnum(){ int i = 0; Node
                         
                           *p = pHead;//获取头结点位置 while (p != nullptr)//循环到尾部 { i++; p = p->pNext; } return i;}template 
                          
                           bool List
                           
                            ::deletet(T t){ Node
                            
                              *p = this->find(t); if (p==nullptr) { return false; } else { if (p==pHead)//头结点 { pHead = p->pNext; delete p; } else { Node
                             
                               *p1, *p2; p1 = pHead; p2 = p1->pNext; while (p2!=p)//删除一个节点，获取前一个节点 { p1 = p2; p2 = p2->pNext; } p1->pNext = p2->pNext;//跳过p2 delete p2; } return true; }}template 
                              
                               void List
                               
                                ::sort(){ for (Node
                                
                                  *p1 = pHead; p1 != NULL;p1=p1->pNext) { for (Node
                                 
                                   *p2 = pHead; p2!= NULL; p2 = p2->pNext) { if (p1->t < p2->t) { T temp; temp = p1->t; p1->t = p2->t; p2 -> t = temp; } } }}template
                                  
                                   void List
                                   
                                    ::deletesame()//重新生成{ Node
                                    
                                      *p1, *p2; p1 = pHead->pNext; p2 = pHead; while (p1!=nullptr) { if (p1->t==p2->t) { //cout << "="; p2->pNext = p1->pNext; delete p1; p1 = p2->pNext; } else { p2 =p1; p1 = p1->pNext; } }}template
                                     
                                      bool List
                                      
                                       ::clear(){ if (pHead ==nullptr) { return false; } Node
                                       
                                         *p1, *p2; p1 = pHead->pNext; while (p1!=nullptr) { p2 = p1->pNext; delete p1; p1 = p2; } delete pHead; pHead = nullptr; return true;}template
                                        
                                         //递归void List
                                         
                                          ::rev(){ if (pHead==nullptr || pHead->pNext==nullptr) { return; } else { Node
                                          
                                            *p1, *p2, *p3; p1 = pHead; p2 = p1->pNext; while (p2!=nullptr) { p3 = p2->pNext; p2->pNext = p1; p1 = p2; p2 = p3; } pHead->pNext= nullptr; pHead = p1; }}template
                                           
                                            void List
                                            
                                             ::insert(T oldt, T newt){ Node
                                             
                                               *p = find(oldt); if (p!=nullptr) { Node
                                              
                                                *p1, *p2; p1 = pHead; p2 = p1->pNext; while (p2 != p) { p1 = p2; p2 = p2->pNext; } Node
                                               
                                                 *pnew = new Node
                                                
                                                 ; pnew->t = newt; pnew->pNext = p2; p1->pNext = pnew; }}template
                                                 
                                                  void List
                                                  
                                                   ::merge(List & list){ Node
                                                   
                                                     *p = pHead;//获取头结点位置 while (p->pNext != nullptr)//循环到尾部 { p = p->pNext; } p->pNext = list.pHead;//}

Main.cpp

#include
    
     #include
     
      #include "List.h"#include "List.cpp"#include "Node.h"using namespace std;void main(){	List
      
        * pmylist1 = new List
       
        ;	pmylist1->add(11);	pmylist1->add(11);	pmylist1->add(12);	pmylist1->add(12);		List
        
          * pmylist2 = new List
         
          ; pmylist2->add(11); pmylist2->add(11); pmylist2->add(12); List< List
          
            *> *p=new List< List
           
             *>; p->add(pmylist1); p->add(pmylist2); p->pHead->t->show(); p->pHead->pNext->t->show(); p->show(); cin.get();}void main213(){ List
            
              cmdlist; cmdlist.add("china"); cmdlist.add("calc"); cmdlist.add("born"); cmdlist.add("xery"); cmdlist.show(); cin.get();}void main4(){ List
             
               * pmylist = new List
              
               ; pmylist->add(11); pmylist->add(11); pmylist->add(12); pmylist->add(12); pmylist->add(12); pmylist->add(12); pmylist->add(15); pmylist->add(11); pmylist->show(); List
               
                 list; list.add(1231); list.add(1232); list.add(1239); list.add(1237); list.show(); pmylist->merge(list); pmylist->show(); delete pmylist; cin.get();}void main3(){ List
                
                  * pmylist = new List
                 
                  ; pmylist->add(11); pmylist->add(11); pmylist->add(12); pmylist->add(12); pmylist->add(12); pmylist->add(12); pmylist->add(15); pmylist->add(11); pmylist->add(12); pmylist->add(12); pmylist->add(12); pmylist->add(12); pmylist->add(15); pmylist->show(); pmylist->sort(); pmylist->show(); pmylist->deletesame(); pmylist->show(); pmylist->rev(); pmylist->show(); pmylist->insert(12, 1100); pmylist->show(); pmylist->clear(); pmylist->show(); delete pmylist; cin.get();}void main1(){ List
                  
                    * pmylist =new List
                   
                    ; pmylist->add(11); pmylist->add(12); pmylist->add(13); pmylist->add(15); pmylist->show(); Node
                    
                      *p = pmylist->find(13); pmylist->change(p, 19); pmylist->show(); pmylist->deletet(15); pmylist->show(); delete pmylist; cin.get();}

哈希存储

插入、删除很不方便，查找最方便。O(1).

Hashnode.h

#pragma oncetemplate
    
     class hashnode{public:		int key;//索引	T  t;  //代表数据	int cn;//代表查找次数};//0 1 2 3 4 5 6 7 8 9   索引        //9   10，           //10 1 2 3 4 5 6 7 8 9    数据   哈希   //100

Hash.h

#pragma once#include "hashnode.h"template
    
     class Hash{public:	hashnode
     
       *p;//p->存储哈希表	int n;//长度public:	 int   myhash(int key );	 void init(T * pt, int nt);	 bool  isin(int key,T t);	 hashnode
      
        *  find(int key);	Hash();	~Hash();};

Hash.cpp

#include "Hash.h"template
    
     Hash
     
      ::Hash(){	this->n = 10;	this->p = new hashnode
      
       [this->n];}template
       
        Hash
        
         ::~Hash(){	delete[] p;}template
         
          int Hash
          
           ::myhash(int key){ return key % n;}template
           
            void Hash
            
             ::init(T *pt,int nt){ for (int i = 0; i < 10;i++) { p[i].key = i; p[i].t = pt[i]; p[i].cn = 0; }}template
             
              bool Hash
              
               ::isin(int key,T t){ int res = myhash(key); if (p[res].t==t) { return true; } else { return false; }}template
               
                hashnode
                
                  * Hash
                 
                  ::find(int key){ int res = myhash(key); return p + res;}

Main.cpp

#include
    
     #include "Hash.h"#include "Hash.cpp"#include "hashnode.h"using namespace std;void main(){		Hash
     
       myhash;	int a[10] = { 10, 11, 22, 33, 44, 55, 56, 67, 78, 99 };	myhash.init(a, 10);	cout << myhash.isin(43,43) << endl;	hashnode
      
        *p = myhash.find(8);	cout << p->key << endl;	cout << p->t << endl;	cin.get();}
你可能感兴趣的文章
Swift - transform.m34动画示例
查看>>
MySQL使用rand函数实现随机数
查看>>
ES6的export与Nodejs的module.exports
查看>>
uc/os任务管理
查看>>
apache也有fastcgi模块
查看>>
发布一个TCP 吞吐性能测试小工具
查看>>
AddComponentRecursively
查看>>
JavaScript 的 async/await ： async 和 await 在干什么
查看>>
hadoop_学习_00_资源帖
查看>>
CDH中配置HDFS HA
查看>>
Zeta.js之内置服务
查看>>
CSS-选择器6-兄弟选择器
查看>>
吴恩达《机器学习》课程总结（9）神经网络的学习
查看>>
Binary Tree Paths
查看>>
Android开源之仿微信UI
查看>>
大蕉毕业三周年了,有话对你说 No.103
查看>>
Workbox3 - ServiceWorker可以如此简单
查看>>
重温Servlet学习笔记--session对象
查看>>
webpack + vue
查看>>
Android两条并排RecyclerView实时联动滑动增强
查看>>
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！
当前时间: 2025-01-23 04:56:24   当前IP: 3.145.58.162   联系邮箱:javaeecc@qq.com     Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2
强烈建议你试试无所不能的CHAT-GPT，快点击我
强烈建议你试试无所不能的CHAT-GPT，快点击我