連結リストのコードを書きます: 連結リストの定義:
struct Node {
// data is used to store an integer value in this node
int data;
// a pointer points to the next node
Node* link;
// inializes the node with a 0 value in data and a null pointer in link
Node() : data(0), link(NULL) {};
// destructor release space allocated to the linked list
~Node() {delete link;}
};
リンクされたリストを表示:
void display_and_count(Node* aLink) {
cout << "Entries: ";
int nodeNumber = 0; // elements number of linked list
for(Node* iterator = aLink; iterator->link != NULL; iterator=iterator->link) {
cout << iterator->data << ", ";
nodeNumber++;
}
cout << "contans " << nodeNumber << " nodes." << endl;
}// end display_and_count
ここで、しきい値に基づいて 1 つの連結リストを 2 つの LESS と MORE に分割し、元の連結リストのノードを削除する関数を作成します。
void split_them_up(Node* aLink, Node* less, Node* more, int threshold) {
Node* lessHead = less; // head of less
Node* moreHead = more; // head of more
bool isThresholdInALink = false; // store if threshold is an element of aLink
for(Node* iterator = aLink; iterator->link != NULL; iterator = iterator->link) {
if(iterator->data < threshold) {
less->data = iterator->data;
less->link = new Node;
less = less->link;
}
else if(iterator->data > threshold) {
more->data = iterator->data;
more->link = new Node;
more = more->link;
}
else {
isThresholdInALink = true;
}
} // end for(Node* iterator = aLink; iterator->link != NULL; iterator = iterator->link)
less = lessHead;
more = moreHead;
delete aLink;
// If threshold is an element of aLink, then the new linked list contains the only threshold.
// If threshold isn't in aLink, then the new linked list contains nothing
aLink = new Node;
if(isThresholdInALink) {
aLink->data = threshold;
aLink->link = new Node;
} // end if(isThresholdInALink)*/
} // end split_them_up
次に、これが主な機能です。
int main() {
Node* ENTRIES = new Node; // define a linked list
get_input(ENTRIES);
display_and_count(ENTRIES);
Node* less = new Node; // define less list
Node* more = new Node; // define more list
cout << "Enter a threshold: ";
int thd; // threshold
cin >> thd;
split_them_up(ENTRIES, less, more, thd);
cout << "Less list: " << endl;
display_and_count(less);
cout << "More list: " << endl;
display_and_count(more);
cout << "ENTRIES: " << endl;
display_and_count(ENTRIES);
}
get_input 関数は、ユーザーから整数を取得し、最後に -1 を取得します。
void get_input(Node* aLink) {
Node* head = aLink; // head of linked list
int capacity=1; // the capacity of intArray
int* intArray = new int[capacity]; // an array stores user input
int size=0; // actual number of elements stored in the intArray
cout << "Input some integers, -1 to end: ";
while(true) {
int input;
cin >> input;
if(input == -1) break;
if(!isContained(intArray, size, input)) {
intArray[size]=input;
size++;
// if size meets capacity, double capacity
if(size >= capacity) {
int* temp = new int[capacity];
int oldCapacity = capacity;
for(int i=0; i < oldCapacity; i++) temp[i]=intArray[i];
delete[] intArray;
capacity = 2*capacity;
intArray = new int[capacity];
for(int i=0; i < oldCapacity; i++) intArray[i]=temp[i];
delete[] temp;
} // end if(size >= capacity)
} // end if(!contained(intArray, size, input))
} // end while(true)
for(int i=0; i<size; i++) {
aLink->data = intArray[i];
aLink->link = new Node;
aLink = aLink->link;
}
delete[] intArray;
aLink = head;
} // end get_input
含まれています：
bool isContained(int* array, int aSize, int n) {
for(int i=0; i<aSize; i++) {
if(array[i] == n) return true;
}
return false;
} // end isContained
Linux システムで実行する場合、すべて問題ありません。しかし、Windows では、split_them_up の後に ENTRIES にランダムな値が表示され、プログラムがクラッシュして「アクセス違反の読み取り場所」が表示されます。