Experiment 1 physical implementation of linear table
Submit two attachments respectively:
1: For the log report file of Experiment 1, please refer to the course specification.
2: Experiment 1 source package. (the file name should also be standardized. Refer to the format of the report file)
Experiment 1 linear table experiment log
Implementation of ADT based on sequence table
[2020.10.20]
Task: create a new project and import the code template in the learning link into the "list" H "," list.h "," main.cpp "files. Compilation passed. Understand the functions of the three files and the implementation and use of each specific function in "alias. H".
[2020.10.21]
Task: after understanding each function of the linear table, complete main Cpp file string classification statistics function. Considering the workload, the function of counting the number of various strings is realized first.
[2020.10.22]
Task: on the basis that the linear table can count the number of various strings, add the function of deleting the numbers in the linear table in turn.
Encountered a problem: after adding and deleting the number function, the program ran with an error. The operation results are as follows:
Error reason: according to the feedback information, the problem lies in the remove function. After preliminary analysis, the reason for the error is that the length count of the linear table is not - 1 after deleting the element. When traversing the linear table, it exceeds the length range of the linear table, resulting in an error.
Correction method: each time a number is deleted, not only the current position should be moved forward one, but also the length value of the linear table should be reduced by one to prevent exceeding the range. The changed code and running screenshot are as follows:
It can be found that the function of deleting numbers has been realized.
So far, main Cpp file has completed the required function of statistics of various strings and the function of re outputting linear table after deleting numbers.
Implementation of ADT based on linked list
[2020.10.22]
Task: create a new project and import the code template in learning link into "link" H "," list.h "," LList.h "," main.cpp ".
Encountered a problem: an error is reported during compilation. The error is as follows:
Error reason: after prompt, it is found that some variables in the statement are not separated, which makes the program unrecognizable. Add spaces to separate variables.
[2020.10.23]
Task: understand the implementation of ADT linked list, and complete the two functions of main function counting and deleting numbers on this basis.
Problem 1: compilation failed. The screenshot of error reporting is as follows:
Error reason: the error message shows that the Link class is defined repeatedly. After inspection, I found, "Link The "H" header file lacks a macro definition, resulting in duplicate definitions of the Link class.
Modify: in "link" Add macro definition in "H" header file. As shown in the figure:
The error reported after modification is as follows:
You can find that the error of repeatedly defining the Link class is missing.
Error reason 2: the compiler shows that Line cannot be established because LList is a virtual base class. After inspection, it was found that it was because of "LList "H" header file does not implement "list" The int length() const function and int currPos() const function declared in the "H" file cause LList to be a virtual base class that cannot create objects.
Modify: in "llist The int length() const function and int currPos() const function are implemented in the "H" header file. At this point, the compilation passes smoothly.
So far, the compilation has passed. After preliminary testing, the code can run normally. The operation results are shown in the figure below:
[code part]
Linked list implementation:
link.h
#include <iostream>
#ifndef LINK_H
#define LINK_H
template <typename E> class Link {
public:
E element; // Value for this node
Link *next;
// Pointer to next node in list node pointer: points to the next node in the linked list
// Constructors constructor
Link(const E& elemval, Link* nextval =NULL)
{ element =elemval; next = nextval; }
Link(Link*nextval =NULL) { next = nextval; }
};
#endif // LINK_H
list.h
//#ifndef LIST_H_INCLUDED
//#define LIST_H_INCLUDED
#ifndef LIST_H
#define LIST_H
template <typename E> class List { // List ADT abstract data type definition
private:
void operator=(const List&) {} // Protect assignment
List(const List&) {} // Protect copy constructor
public:
List() {} // Default constructor
virtual~List() {} // Base destructor destructor
// Clear contents from the list, to make itempty. Clear the contents of the list
virtual void clear() = 0;
// Insert an element at the current location.
// item: The element to be inserted
virtual void insert(const E& item) = 0;
// Append an element at the end of the list.
// item: the element to be attached
virtual void append(const E& item) = 0;
// Remove and return the current element.
// Return: the element that was removed. Deletes the current element and returns it as a return value
virtual E remove() = 0;
// Set the current position to the start ofthe list. Sets the current position to the beginning of the sequence table
virtual void moveToStart() = 0;
// Set the current position to the end of thelist. Sets the current position to the end of the sequence table
virtual void moveToEnd() = 0;
// Move the current position one step left.No change
// if already at beginning. Move the current position one step to the left. If the current position is in the first place, it will remain unchanged
virtual void prev() = 0;
// Move the current position one step right.No change
// if already at end. Move the current position one step to the right. If the current position is at the end, it will remain unchanged
virtual void next()= 0;
// Return: The number of elements in thelist. Returns the current number of elements in the list
virtual int length() const = 0;
// Return: The position of the currentelement. Returns the position of the current element
virtual int currPos() const = 0;
// Set current position.
// pos: The position to make current. Set the current position to POS
virtual void moveToPos(int pos) = 0;
// Return: The current element. Returns the current element
virtual const E& getValue() const = 0;
};
#endif
//#endif // LIST_H_INCLUDED
LList.h
#include"list.h"
#include"link.h"
#include<assert.h>
#ifndef LLIST_H_INCLUDED
#define LLIST_H_INCLUDED
//This is the declaration for LList. It is split into two parts
//because it is too big to fit on one book page
//Linked list implementation
using namespace std;
template <typename E> class LList:public List<E> {
private:
Link<E>* head; // Pointer to list header points to the chain header node
Link<E>* tail; // Pointer to last element points to the last node in the linked list
Link<E>* curr; // Access to current element points to the current element
int cnt; // Size of list current list size
void init() { // Initialization helper method initialization
curr = tail = head = new Link<E>;
cnt = 0;
}
void removeall() {
while(head != NULL) {
curr = head;
head = head->next;
delete curr;
}
}
public:
LList(int size=100) { init(); } // Constructor constructor
~LList() { removeall(); } // Destructor destructor
void print() const; // Print list contents
void clear() { removeall(); init(); } // Clear list clear list
// Insert "it" atcurrent position insert "it" at the current position
void insert(const E& it) {
curr->next = new Link<E>(it, curr->next);
if (tail == curr) tail = curr->next; // New tail new tail pointer
cnt++;
}
void append(const E& it) { // Append "it" to list append "it" to the end of the list
tail = tail->next = new Link<E>(it, NULL);
cnt++;
}
// Remove and return current element
E remove() {
assert(curr->next != NULL); //"Noelement" if there is no element at present, the program will be interrupted
E it = curr->next->element; // Remember value saves the element value
Link<E>*ltemp = curr->next; // Remember link node saves pointer field information
if (tail == curr->next) tail = curr; // Reset tail reset tail pointer
curr->next = curr->next->next; // Remove from list remove from list
delete ltemp; // Reclaim space
cnt--; // Decrement the count decrements the length of the current linked list by one
return it;
}
void moveToStart() // Place curr at list start sets curr at the head of the linked list
{ curr = head; }
void moveToEnd() // Place curr at list end sets curr at the end of the linked list
{curr = tail; }
// Move curr one step left; no change ifalready at front
// Move the curr pointer forward one step; If you have pointed to the head, you don't need to change it
void prev() {
if (curr == head) return; // No previous element if the current pointer is a header pointer, it returns directly
Link<E>* temp = head;
// March down list until we find the previous element
while (temp->next!=curr) temp=temp->next;
curr = temp;
}
// Move curr one step right; no changeif already at end
//Move the curr pointer back one step; If you have pointed to the tail, you don't need to change it
void next()
{if (curr != tail) curr = curr->next; }
intlength() const { return cnt; } // Return length returns the current list size
// Return the position of the current element
intcurrPos() const {
Link<E>* temp = head;
int i;
for (i=0; curr != temp; i++)
temp = temp->next;
return i;
}
// Move down list to "pos" position
void moveToPos(int pos) {
assert ((pos>=0)&&(pos<=cnt));//'Position out of range' is not in range
curr = head;
for(int i=0; i<pos; i++) curr = curr->next;
}
const E& getValue() const { // Return current element returns the current element
assert(curr->next != NULL);//"No value" content is empty
return curr->next->element;
}
int length() const
{
return cnt;
}
int currPos() const
{
Link<E>* temp = head;
int i;
for(i = 0 ; curr != temp ; i++)
temp = temp->next;
return i;
}
};
#endif // LLIST_H_INCLUDED
main.c
#include "link.h"
#include "list.h"
#include "LList.h"
#include<iomanip>
#include<iostream>
#include <string.h>
using namespace std;
void print(LList<char> &A,int n);
int main()
{
LList<char> Line(100);//Create a linear table List with variable type char
int char_num = 0 , number = 0 , other = 0;//char_num number of letters, number number of numbers, other characters
char trans;//As transit character
while((trans = cin.get())!= '\n')//Put the characters in the string into the linear table in turn
Line.append(trans);
int length_list = Line.length();
int len =length_list;
Line.moveToStart();//The curr pointer of the linear table points to the header
for(int i = 0 ; i < len ; i++)//Traverse the linear table and count the number of various characters
{
char ch = Line.getValue();
if(ch >='0'&& ch <= '9')
{
number++;
Line.remove();
Line.prev();
length_list--;
}
else if((ch >='A'&& ch <= 'Z')||(ch >='a'&& ch <= 'z'))
char_num++;
else other++;
Line.next();
}
cout << char_num << ' ' << number << ' ' << other << endl;
print(Line,length_list);//Print the modified linear table
return 0;
}
/***********************
*function ofprint
*Elements in the print order table
************************/
void print(LList<char>& A,int n){
int i;
for(i=0;i<n;i++){
A.moveToPos(i);
cout<<A.getValue()<<""; //Call the getValue operation to get the current element
}
cout<<endl<<endl;
}