[欢迎上传]Data Structures and Algorithms Using C++

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

.

• Data Structures and Algorithms Using C++

• By: Ananda Rao Akepogu; Radhika Raju Palagiri

• Publisher: Pearson India

• Pub. Date: July 30, 2010

• Print ISBN-13: 978-81-317-5567-9

• Web ISBN-13: 978-93-325-1199-6

• Pages in Print Edition: 576

• Subscriber Rating: [0 Ratings]

  
  

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：Structures Algorithms Structure Algorithm struct

Brute Force Pattern Matching Algorithm

Brute force pattern matching algorithm is a good and simple algorithm for pattern matching. This algorithm finds all the possible substrings over the given large string, and checks for the given pattern on all the possible substrings.

If the pattern is with length 5, then the first substring from the text will be from the first character to the 5th character. The first substring will be cross checked with the pattern. If the substring and the pattern match, then the brute force algorithm returns with TRUE. If the substring and the pattern do not match, then the second substring will be from second character of the text to the 6th character of the text. The second substring will be cross checked with the pattern, if matches return TRUE or else the same process will be continued until the start index of the substring reaches n-length(P).

1. Program 15.1
   
2. 
   
3. #include<iostream.h>
   
4. 
   
5. #include<string.h>
   
6. 
   
7. #include<iomanip.h>
   
8. 
   
9. void main()
   
10. 
    
11. {
    
12. 
    
13. char Text[256],Pattern[50];
    
14. 
    
15. int m,n;
    
16. 
    
17. cout <<“\nEnter Text, At end enter‘.’\n”;
    
18. 
    
19. for(int i=0;i<256;i++)
    
20. 
    
21. {
    
22. 
    
23. char ch;
    
24. 
    
25. cin.get(ch);
    
26. 
    
27. if(ch!=‘.’)
    
28. 
    
29. {
    
30. 
    
31. Text[i]=ch;
    
32. 
    
33. }
    
34. 
    
35. else break;
    
36. 
    
37. }
    
38. 
    
39. n=strlen(Text);
    
40. 
    
41. cout<<“\nEnter Pattern For Search:”;
    
42. 
    
43. cin>>Pattern;
    
44. 
    
45. m=strlen(Pattern);
    
46. 
    
47. for(i=0;i<=(n-m);i++)
    
48. 
    
49. {
    
50. 
    
51. for(int j=0;j<m;j++)
    
52. 
    
53.   {
    
54. 
    
55.   if(Pattern[j]!=Text[i+j])break;
    
56. 
    
57.   }
    
58. 
    
59. If (j==m)
    
60. 
    
61.   {
    
62. 
    
63.   cout<<“\nThe Pattern\‘”<<Pattern<<“\‘Found at”<<i<<“on the given Text\““ <<Text<<”\””;
    
64. 
    
65.   }
    
66. 
    
67. }
    
68. 
    
69. }

复制代码

The Boyer-Moore Algorithm

The Brute Force Algorithm finds all the possible substrings that can be matched with the search pattern, and searches all the characters of the given text. The Boyer-Moore (B-M) Algorithm is a faster algorithm when the search string is large. It is one of the best suitable algorithms for searching the words in the text document. Unlike the Brute Force algorithm, the Boyer-Moore Algorithm skips the unnecessary checks.

The B-M Algorithm works with a ‘backward’ approach, the target string is aligned with the start of the check string, and the last character of the target string is checked against the corresponding character in the check string. In the case of a match, then the second-to-last character of the target string is compared to the corresponding check string character. In the case of a mismatch, the algorithm computes a new alignment for the target string based on the mismatch. In the case of mismatch the algorithms skip checking some of the characters.

Boyer-Moore Algorithm steps: Character comparison is done from right of the pattern to the left:

• Constructing the SHIFT Table
• GOOD SUFFIX SHIFT or BAD CHARACTER SHIFT
  

1. Program 15.2
   
2. 
   
3. //Boyer-Moore
   
4. 
   
5. #include<conio.h>
   
6. 
   
7. #include<string.h>
   
8. 
   
9. #include<iostream.h>
   
10. 
    
11. #include<stdio.h>
    
12. 
    
13. int*build_table(char*p)
    
14. 
    
15. {
    
16. 
    
17. int last[128];
    
18. 
    
19. int i;
    
20. 
    
21. for(i=0;i<128;i++)last[i]=-1;
    
22. 
    
23. for(i=0;i<strlen(p);i++)
    
24. 
    
25. {
    
26. 
    
27.   last[p[i]]=i;
    
28. 
    
29. }
    
30. 
    
31. return(last);
    
32. 
    
33. }
    
34. 
    
35. int min(int a,int b)
    
36. 
    
37. {
    
38. 
    
39. if(a>b)return(b);
    
40. 
    
41. else return(a);
    
42. 
    
43. }
    
44. 
    
45. int search(char*t,char*p)
    
46. 
    
47. {
    
48. 
    
49. int*last=build_table(p);
    
50. 
    
51. int n=strlen(t);
    
52. 
    
53. int m=strlen(p);
    
54. 
    
55. int i=m-1;
    
56. 
    
57. if(i>n-1)return(-1);
    
58. 
    
59. int j=m-1;
    
60. 
    
61.   do{
    
62. 
    
63. if(p[j]==t[i])
    
64. 
    
65.   if(j==0)return i;
    
66. 
    
67.   else {
    
68. 
    
69.     i--;
    
70. 
    
71.     j--;
    
72. 
    
73.     }
    
74. 
    
75. else {
    
76. 
    
77.   i+=m-min(j,1+last[t[i]]);
    
78. 
    
79.   j=m-1;
    
80. 
    
81.   }
    
82. 
    
83. }while(i<=n-1);
    
84. 
    
85. return(-1);
    
86. 
    
87. }
    
88. 
    
89. void main()
    
90. 
    
91. {
    
92. 
    
93. char T[128],P[128];
    
94. 
    
95. int index;
    
96. 
    
97. clrscr();
    
98. 
    
99. cout << “\nEnter Text:”;
    
100. 
     
101. gets(T);
     
102. 
     
103. cout <<“\nEnter Pattern:”;cin>>P;
     
104. 
     
105. index=search(T,P);
     
106. 
     
107. if(index!=-1)
     
108. 
     
109. {
     
110. 
     
111. cout<<“\nMatch Found At:”<<index;
     
112. 
     
113. }
     
114. 
     
115. else {
     
116. 
     
117. cout<<“\nMatch Not Found”;
     
118. 
     
119. }
     
120. 
     
121. }

复制代码

1. Algorithm 4.1
   
2. Set i=LB        //Initializing the counter variable
   
3. Repeat step3 and 4 while i<=UB
   
4. VISIT (A[i])    //process the element
   
5. i=i+1   //Moving to next location, increment the counter
   
6. End
   
7. Or using for loop
   
8. Repeat for i=LB to UB
   
9. VISIT (A[i])
   
10. End

复制代码

1. Algorithm 4.2
   
2. INSERT(ARR,N,POS,ITEM)
   
3. ARR is an array of size N. POS is the index to insert the element.
   
4. Set i=N        //initialize the counter variable
   
5. Repeat steps 3 and 4 while i>=POS
   
6. Move ith element downwards
   
7. Set ARR[i+1] = ARR[i].
   
8. Set i=i-1      //decrement the counter variable.
   
9. Insert element at ‘POS’
   
10. Set ARR[POS]=ITEM
    
11. Set N=N+1      //increment N value
    
12. End

复制代码

1. Algorithm 4.3
   
2. DELETE(ARR, N, POS, ITEM)
   
3. Set ITEM=ARR[POS]
   
4. Repeat for i=POS to N-1
   
5. Set ARR[i] = ARR[i+1] //move elements upward
   
6. Set N=N-1
   
7. End

复制代码

1. Algorithm 4.4
   
2. SORT :
   
3. Set N=UB
   
4. while i>=LB do
   
5. Set q=LB    //comparing the first
   
6. while j<i do
   
7. check whether A[j]&A[j+1] are in order, if so swap the elements
   
8. SWAP(A[j], A[j+1])
   
9. Set j=j+1
   
10. Set i=i-1
    
11. End

复制代码

Chapter 6 Summary

• Stack is a non-primitive linear data structure into which elements are inserted and deleted from the same end called Top.
• Stack supports two basic operations, Push and Pop.
• There are many applications of stacks like recursion elimination, evaluation of expressions, etc.
• Stack can be implemented using arrays or linked lists.
  

Chapter 7 Summary

• A queue is a non-primitive linear data structure in which elements are inserted from one end and deleted from another end. It is also called as first in first out, i.e. the element is inserted first will be deleted first. The end into which elements are inserted is called the rear end and the end from which elements are deleted is called the front end.
• A queue basically supports two operations, insert and delete.
• A queue has many applications, like it is used in operating systems for job scheduling, in networks, to check whether a given string is a palindrome or not, etc.
• Types of queues are circular queue and doubly ended queue.
• Insertion of elements can also be done at the rear when its value is the maximum size in circular queue.
• In deque insertion and deletion operations can perform on both sides of the queue, so it is called as double-ended queue.
• Input-restricted deque and output-restricted deque are the two types of deque.
  

Chapter 8 Summary

• Dictionary contains data elements as pairs of the form (k, v), where k is the key and v is the value.
• A dictionary with duplicates is a dictionary which allows two or more (key, value) pairs with the same key.
• An ordered dictionary can be represented as an ordered linear list.
• Skip lists are sorted linked lists. In a skip list, nodes have many ‘next’ references known as forward references, whereas in an ordinary list nodes have only one ‘next’ reference.
• Linear probing is a technique for resolving hash collisions of values of hash functions by searching the hash table sequentially for a free location. The disadvantage of linear probing is primary clustering.
• Quadratic probing is another method for resolving collisions in hash tables. It operates by taking the original hash value and adding successive values of a quadratic polynomial to the starting value. Quadratic probing avoids the clustering problem that occurs with linear probing.
• Double hashing is a technique used in hash table to resolve hash collisions. It uses one hash value as a starting value and continual evolution of an interval until the desired value is found, an empty location is found or the entire table is searched.