DS第7章学习小结

时间：2019-06-02 23:58:21 阅读：205 评论：0 收藏：0 [点我收藏+]

一、谈谈你对本章的学习小结

　　第7章的标题是“查找”，

　　首先通常我们用　　平均查找长度（Average Search Length， ASL）　　来衡量查找算法的性能。

　　　　技术分享图片，其中，Pi为查找表中第i个记录的概率，且P1+P2+P3+...+Pi=1

　　接着我们大概是学了

　　对线性表的查找，对树表的查找，对散列表的查找。

　　　　线性表的查找。

　　　　主要包括：顺序查找、折半查找以及分块查找。

　　　　技术分享图片

　　　　树表的查找。

　　　　树表的结构主要包括：二叉排序树（又称二叉搜索树）、平衡二叉树、B-树以及B+树。

　　　　技术分享图片

　　　　散列表的查找。

　　　　主要研究两方面的问题：如何构造散列函数，以及如何处理冲突。

　　　　　　构造散列函数常用有以下四种方法：数字分析法、平方取中法、折叠法以及除留余数法，其中除留余数法为最常用的方法。

　　　　　　处理冲突的方法通常可分为两大类：开放地址法和链地址法。

　　　　　　技术分享图片

二、同时谈谈你对上次制定目标的完成情况

　　这一章的学习实话说我还是挺浑浑噩噩的，感觉是因为没上机书上内容太多老师讲得太快课时太少？应该是我太菜了......但是对上一章图的DFS和BFS的理解以及一些相关操作的实现应该还可以吧。（我也不知道~）

三、以及接下来的目标

　　接下来就要学排序了，又是很关键的一章，

　　仲系果句话，继续努力！

附上Hashing的代码：

  1 #include<iostream>
  2 #include<cmath>
  3 using namespace std;
  4 
  5 
  6 typedef struct
  7 {
  8     int info;
  9     bool empty;
 10 }data;
 11 
 12 
 13 typedef struct
 14 {
 15     int msize;
 16     int num;
 17     data *vex;
 18     int *array;
 19 }Hashing;
 20 
 21 
 22 
 23 
 24 void create(Hashing &hashlist);
 25 bool prime(int k);
 26 int hashi(Hashing hashlist, int k);
 27 
 28 
 29 
 30 
 31 int main()//Hashing
 32 {
 33     Hashing hashlist;
 34     create(hashlist);
 35     
 36     
 37     for(int i=0; i<hashlist.num; i++)
 38     {
 39         if(i!=0)
 40         {
 41             cout<<‘ ‘;
 42         }
 43         
 44         
 45         int m=hashi(hashlist,hashlist.array[i]);
 46         if(m!=-1)
 47         {
 48             cout<<m;
 49         }
 50         else
 51         {
 52             cout<<‘-‘;
 53         }
 54     }
 55     
 56     
 57 return 0;
 58 }
 59 
 60 
 61 
 62 
 63 void create(Hashing &hashlist)
 64 {
 65     cin>>hashlist.msize>>hashlist.num;
 66     
 67     
 68     while(!prime(hashlist.msize))
 69     {
 70         hashlist.msize++;
 71     }
 72     
 73     
 74     hashlist.vex=new data[hashlist.msize];
 75     for(int i=0; i<hashlist.msize; i++)
 76     {
 77         hashlist.vex[i].empty=true;
 78     }
 79     
 80     
 81     hashlist.array=new int[hashlist.num];
 82     for(int i=0; i<hashlist.num; i++)
 83     {
 84         int k;
 85         cin>>k;
 86         hashlist.array[i]=k;
 87         int tmp=k%hashlist.msize;
 88         
 89         
 90         for(int j=0; j<hashlist.msize; j++)
 91         {
 92             int a=(tmp+j*j)%hashlist.msize;
 93             if(hashlist.vex[a].empty)
 94             {
 95                 hashlist.vex[a].empty=false;
 96                 hashlist.vex[a].info=k;
 97                 break;
 98             }
 99         }
100     }
101 }
102 
103 
104 bool prime(int k)
105 {
106     if(k<=1)
107     {
108         return false;
109     }
110     
111     
112     int m=sqrt(k);
113     for(int i=2;i<=m;i++)
114     {
115         if(k%i==0)
116         {
117             if(i>=m+1)
118             {
119                 return true;
120             }
121             else
122             {
123                 return false;
124             }
125         }
126     }
127     
128     
129     return true;
130 }
131 
132 
133 int hashi(Hashing hashlist, int k)
134 {
135     int m=k%hashlist.msize;
136     
137     for(int i=0; i<hashlist.msize; i++)
138     {
139         int j=(m+i*i)%hashlist.msize;
140         if(!hashlist.vex[j].empty && hashlist.vex[j].info==k)
141         {
142             return j;
143         }
144     }
145     return -1;
146 }

View Code

附上QQ帐户的申请与登陆的代码：

  1 #include<iostream>
  2 #include<cmath>
  3 using namespace std;
  4 
  5 
  6 typedef struct node
  7 {
  8     long long int user;
  9     string password;
 10     node *next;
 11 }node;
 12 
 13 
 14 typedef struct
 15 {
 16     node *first;
 17 }list;
 18 
 19 
 20 typedef struct
 21 {
 22     int msize;
 23     int num;
 24     list *index;
 25 }Hashing;
 26 
 27 
 28 
 29 
 30 bool prime(int k);
 31 int exist(Hashing hashlist, long long int user, string password);
 32 int hashi(Hashing hashlist, long long int user);
 33 void set(Hashing &hashlist, long long int user, string password);
 34 
 35 
 36 
 37 
 38 int main()
 39 {
 40     Hashing hashlist;
 41     cin>>hashlist.num;
 42     hashlist.msize=hashlist.num;
 43     
 44     
 45     while(!prime(hashlist.msize))
 46     {
 47         hashlist.msize++;
 48     }
 49     hashlist.index=new list[hashlist.msize];
 50     
 51     
 52     for(int i=0; i<hashlist.msize; i++)
 53     {
 54         hashlist.index[i].first=NULL;
 55     }
 56     
 57     
 58     for(int i=0; i<hashlist.num; i++)
 59     {
 60         if(i!=0)
 61         {
 62             cout<<endl;
 63         }
 64         
 65         
 66         string a,c;
 67         long long int b;
 68 
 69 
 70         cin>>a>>b>>c;
 71         int m=exist(hashlist,b,c);
 72         if(a=="L")
 73         {    
 74             if(m==1)
 75             {
 76                 cout<<"Login: OK";
 77             }
 78             else if(m==0)
 79             {
 80                 cout<<"ERROR: Wrong PW";
 81             }
 82             else if(m==-1)
 83             {
 84                 cout<<"ERROR: Not Exist";
 85             }
 86         }
 87         else if(a=="N")
 88         {
 89             if(m==1 ||m==0)
 90             {
 91                 cout<<"ERROR: Exist";
 92             }
 93             else if(m==-1)
 94             {
 95                 set(hashlist,b,c);
 96                 cout<<"New: OK";
 97             }
 98         }
 99     }
100     
101     
102 return 0;
103 }
104 
105 
106 
107 
108 bool prime(int k)//判断是否为素数 
109 {
110     if(k<=1)
111     {
112         return false;
113     }
114     
115     
116     int m=sqrt(k);
117     for(int i=2;i<=m;i++)
118     {
119         if(k%i==0)
120         {
121             if(i>=m+1)
122             {
123                 return true;
124             }
125             else
126             {
127                 return false;
128             }
129         }
130     }
131     
132     
133     return true;
134 }
135 
136 
137 int exist(Hashing hashlist, long long int user, string password)
138 {
139     int m=hashi(hashlist,user);
140     
141     
142     node *p=hashlist.index[m].first;
143     while(p!=NULL)
144     {
145         if(p->user==user)
146         {
147             if(p->password==password)
148             {
149                 return 1;
150             }
151             else
152             {
153                 return 0;
154             }
155         }
156         p=p->next;
157     }
158     
159     
160     return -1;
161 }
162 
163 
164 int hashi(Hashing hashlist, long long int user)
165 {
166     return user%hashlist.msize;
167 }
168 
169 
170 void set(Hashing &hashlist, long long int user, string password)
171 {
172     int m=hashi(hashlist,user);
173     
174 
175     node *q=new node;
176     q->user=user;
177     q->password=password;
178     q->next=hashlist.index[m].first;
179     hashlist.index[m].first=q;
180 }

View Code

DS第7章学习小结

原文：https://www.cnblogs.com/ymj19/p/10961870.html

踩

(1)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)