C++ :: Linked List Or Sorting An Array?
Feb 2, 2015
I have an algorithm and I want to make it as efficient as possible. Basically it just involves putting numbers in order. I have two options, but which one would be more efficient:
1. Using a doubly linked list. Every time a user wants to add a new number, the algorithm will start searching the correct place for the number from the beginning of the list. This is efficient per se, but once there are about a million numbers and a number has to be put in at the end of the list, the algorithm must go through all the 999 999 numbers before it.
2. Using a container to store all the numbers first, then sorting the numbers. In this case, adding all the numbers is fast, but the actual sorting will take a long time.
Which option would be more efficient? I was thinking of using maybe merge sort or quick sort in option 2. Yes, I'm aware I could just use vector and sort, but that's not my goal here.
View 4 Replies
ADVERTISEMENT
Apr 3, 2014
I have two arrays of characters that I want to combine and sort according to an internal variable (init) using a forward-iterating linked list. The two arrays must stay separated, as one of the arrays (the enemies) is contained within the object (encounter), the other is passed in via pointers (the players). The array inside the object will be destroyed later (when the encounter is over and the enemies are hopefully dead) while the one that is passed in must survive to be passed into other objects at a later time (the next encounter). My thought is to sort each array by linked list separately first, then iterate through and combine the two lists, But how to do this and no support IRL.
// DECLARATION OF CLASSES //
class character{
public:
character(); // Constructor
[Code]....
View 1 Replies
View Related
Oct 19, 2013
I'm trying to sort the elements in a linked list which contain a variable amount of data in any given case. In the sample code, the code is more static, but I plan on adding it to much more dynamic code once I have it figured out. My main problem is that I am not sure how to sort the linked list while still keeping the correct pointers to the nodes. I thought about writing my own custom quick sort instead of using the C-standard library function, but how I would keep the pointers to the next nodes correct eluded me. Here is my code so far :
Code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
[Code]......
View 3 Replies
View Related
Apr 29, 2013
I know how some parts of sorting linklist works but not all of it what does the rest of the code do
Code:
#include <iostream>
#include <math.h>
using namespace std;
struct linklist {
int data;
struct linklist * pnext;
[Code] .....
what does this part of the code do
View 5 Replies
View Related
Oct 29, 2014
I am at a lost of how to sort names in alphabetical order after having the user input them into a linked list. I manage to create a program that did have the person input names into the linked list and when it is printed it displays the names in the order of how the user inputted the names.
#include <cstdlib>
#include <iostream>
using namespace std;
#include <string>
class NodeType {
public:
string NodeValue;
[Code] .....
View 1 Replies
View Related
May 31, 2013
This is the algorithm I have so far and it works great. I was wondering what other people think? Comments/Critiques??
void LinkedList::sort()
{
if (head != 0)
{
[Code].....
View 14 Replies
View Related
Mar 4, 2014
I am trying to sort a linked list using quick sort in C. Here is my code--Actually, first I am inserting data in the list from a file. For a small file, it's working fine. But for large file it's just not working.
Code:
struct node {
int data;
struct node *link;
struct node *plink;
[Code] .....
View 1 Replies
View Related
Aug 30, 2013
While I know that linked lists seem to be a fairly common problem area among beginner C programmers, most examples that I have come across abstract the sorting of a linked list to a separate function which is sadly not what I am trying to do.
The code below is my attempt to have the nodes inserted into their correct place so that once all nodes have been inserted they are already in a sorted order.
Code:
int main(int argc, char *argv[])
{
struct node_t* dict_head;
struct node_t* traversor;
struct node_t* newnode;
int list_size = 0, insert_key, search_key, delete_key, x;
char insert_word[WORDLEN];
/*Opening the dictionary file provided by the command line argument */
FILE *fp;
fp = fopen(argv[1], "r");
[Code]....
The problem is as follows. When you provide it with input in which the first word scanned is any other word than that which would be placed at the front of the list, it works as intended. For example.
7 world
0 ant
3 kodak
1 best
6 the
2 is
Produces ant -> best->is->kodak->best->world
However, swapping ant and world in the above input gives:
world->best->is->kodak->best->world
In regards to why I have my head node set as a node without a word or a key, it was suggested that I make it so that the first node inserted is set to be the head of the list and then changed as sorting required, yet this caused only additional problems.
View 10 Replies
View Related
Oct 3, 2014
Write a program that creates a forward linked list of at least 20 elements, where each element holds a random integer between 0 and 99. Print the list.
Write the function "returnMiddleList" to find the middle element of the linked list in one pass. Print the integer value of this element and the position of this element (starting at zero) in relation to the head (where the head = 0, the element pointed to by the head = 1, the element pointed to by the previous one = 2, etc).
Split the list in half at the middle element to create two entirely separate* linked lists of near equal size (+/- 1) and print the two lists. Modify the "returnMiddleList" function to accomplish this, returning the head of the second linked list and setting the link of the element pointing to that head to null. Then print the two sums of the integers stored in the elements of both lists.
Sort the two lists from least to greatest and print them out (printing at this step is optional depending on the sort approach taken). Then combine the two lists while sorting them again from least to greatest and print out the new list. (HINT: you can subdivide the lists further and sort them on a scale of one to two element lists before sorting and combining the first two unsorted lists. What is this sort called?)
I have got #1 and #2 working, but #3 and #4 is where the issue is beginning. When I split my link list into two lists and print the individual lists out, my first link list prints out 9 numbers when it should be printing out 10 (the 10th number somehow disappears?), but when I do the sum of the first list right after that, the number that has disappeared gets added in the sum! I do not know why it is disappearing, and this is one issue. Another issue is in the second list, a random "0" gets added to the list and one of the numbers is lost. My last issue is about #4 as the merge algorithm I have used does not seem to work (I am merging the list together while sorting them, but I am not using a recursion sort because we have not learned that yet).
#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;
struct nodeType {
int data;
nodeType *link;
[Code] .....
View 9 Replies
View Related
Nov 29, 2014
I was trying to implement sorting in a linked list. However, when i run the sortList() function the program abruptly terminates. Here's the complete code:
Code: /*
* {
* SingleLinkedList.c
*
* Created on: 28-Nov-2014
[Code].....
View 3 Replies
View Related
Nov 21, 2014
I need to sort the Linked list from highest to lowest or in this case. The highest Bribe gets the higher priority on the list. I have looked all over the internet and have found some pretty decent examples but I still don't truly understand how to sort it. I think from looking at so many examples I have confused myself even more. I was reading about using Doubly Linked list but I don't even know if were allowed to use that.
1. The program runs perfectly at the moment. It prints out the list but does not sort it.
2. How to make sure that I am deleting the allocated memory correctly in the deconstructor.
Header File
#include <iostream>
#ifndef PERSON_H
#define PERSON_H
struct PersonRec;
class PersonList {
[Code] .....
View 6 Replies
View Related
Feb 1, 2015
I am relatively new to C++ and am trying to bubble sort my linked list that creates 100 random integers. Everything works, but I am unsure how to continue this to include a bubble sorting method.
#include "stdafx.h"
#include <iostream>
using namespace std;
class Node{
public:
int data; //set data
[Code] ....
View 1 Replies
View Related
Feb 16, 2013
I have a code able to import a file containing words and numbers to a linked list, but I also need to sort this linked list alphabetically. I've done research on this involving bubble sorting, but no explanationcan achieve this objective.
Below is the code that can only put the file into linked list:
Code:
#include<iostream>
#include<conio.h>
#include"U:C++WordClass2WordClass2WordClass.cpp"
#include<fstream>
#include<vector>
#include<string>
using namespace std;
[Code] .....
View 5 Replies
View Related
Jun 8, 2014
I am doing a modification to a school project call rainfall statistics. I have that written, but need to sort the array and list rainfall totals from highest to lowest. I thought I knew what I was doing but I am having some difficulty locating all my errors, the error I keep getting now is:
1>------ Build started: Project: Rainfall Statistics Program, Configuration: Debug Win32 ------
1> Rainfall-main.cpp
1>Rainfall-main.cpp(88): error C2601: 'sortHighest2Lowest' : local function definitions are illegal
1> Rainfall-main.cpp(25): this line contains a '{' which has not yet been matched
1>Rainfall-main.cpp(96): error C2065: 'TOTAL_NUM_OF_MONTHS' : undeclared identifier
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========
Below is my code, I know i'm missing something, just can't see it.
#include <iostream>
#include <iomanip>
#include <string>
using namespace std;
//Here are the function prototypes
double getTotalRainfall(double[], int);
double getAverageRainfall(double[], int);
[Code] .....
View 2 Replies
View Related
Jan 29, 2014
I am trying to create an dynamic array (lno) This array will store addressess of different Linked list. What exactly I want is:- Take N Number of Linked List user want to create> eg. 2 now It will create 2 linked list for which I am trying to allocate memory.
Code:
struct node{
int data;
struct node *next;
}
first;
lno[0] Node 0's first address stored in ln[0] lno[1] Node 1's first address stored in ln[1] Here is the code in which I am facing problem with error Illegal structure Operation
Code:
#include<conio.h>#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
[code]....
View 1 Replies
View Related
Nov 24, 2014
I have a 2D array, array[20][3]. Each row represents a storm and each column represents month #, wind speed, and pressure in that order. This data is read from a file and auto-fills the array. I need to be able to give users the ability to add an additional storm or delete a storm. I know that a linked list would be the best approach but I'm not very familiar with linked lists.
View 1 Replies
View Related
May 1, 2014
I am having problems implementing ArrayList using templates. I was given a program and I have to create this implementation to make it work. It keeps giving me an error "invalid operands to binary expression" .....
ifndef Final_4_ArrayList_hpp
#define Final_4_ArrayList_hpp
#define MAX 10;
#include "List.hpp"
template <class T>
class ArrayList : public List <T> {
[Code] ....
View 1 Replies
View Related
Oct 15, 2014
This is in response to the bubble sort and selection sorts for linked lists. On my system, (Intel 2600K, 3.4ghz), it sorts a list with 4,194,304 nodes containing 64 bit unsigned integers in about 1.05 seconds.
Code:
#define NUMLISTS 32
/* number of lists */
typedef unsigned long long UI64;
typedef struct NODE_{
struct NODE_ * next;
UI64 data;
[Code]....
View 6 Replies
View Related
Dec 24, 2013
using the following header files:
Code:
#include <list>
#include <map>
#include <iostream>
#include <algorithm>
and
Code:
std::list
If there is a creation of a list, how can one find the sizeof the list. and is it possible to copy all the data from the linked list into an array. Assuming that the data is of type
Code:
char
View 1 Replies
View Related
Nov 27, 2014
Basically what are the advantages and disadvantages of having an array implementation vs linked list implementation for a stack?
View 1 Replies
View Related
Feb 13, 2013
I'm trying to implement 2d array to simulate linked list for stack and I faced several difficulties doing so.
How do I implement from Top to Bottom ordering? How do I check random index value for validity?
Source-code:
Code:
#include <iostream>
using namespace std;
int myTop, index, nex = -1;
int twoDimentionalArray[25][3], L[25];
[Code].....
And one more thing: how do I get straight 0 from 25 index in the first coulumn?
View 1 Replies
View Related
Aug 6, 2014
I've written this class and struct to create a singly linked list. The data is stored in the binary file which I've opened and read. I'm trying to load said data into a class type array. The errors I'm getting are "incompatible types in assignment of 'StatehoodInfo' to char[3]" Lines 130-134 is what I was working on.
#include <iostream>
#include <iomanip>
#include <fstream>
#include <sstream>
#include <string>
#include <cstring> //For char[] string functions
[Code] .....
View 2 Replies
View Related
Mar 26, 2013
I have an assignment where i am required to code up in C, a program to simulate a taxi rank that is implemented as a queue via an array that can hold up to a maximum of six taxis.When a taxi arrives, it joins the rear of the queue. When a taxi departs, the first taxi in the rank is used and its departure is logged.A "rolling menu" comprising integer codes as specified below is used until 0 is entered to exit the simulation. I've done this stage but now the next stage is asking me to implement the queue as a linked list. what the difference is between an array and a linked list and what is a linked list?
View 2 Replies
View Related
Apr 29, 2013
I'm trying to write a function that takes two linked lists and creates a third one with only the common elements.
It assumes the first list (the caller) has no dups, but it doesn't seem to be working. The program doesn't crash, it just hangs when it is supposed to display L3 (the third list)..everything else runs and is displayed fine.
template <typename T>
LList <T> LList <T>:: common (LList <T> &B)//common fct
{
Node <T> *hunter1 = Head;
[Code]......
View 10 Replies
View Related
Jun 29, 2013
I have a linked list comprised of chars like so...
Code:
node1 - "p"
node2 - "o"
node3 - "p"
I need a function that will take in three perameters...node *replaceChar(node *head, char key, char *str)Stipulations of this function. head is the head of the list, 'key' and 'str' are guaranteed to contain alphanumeric characters only (A-Z, a-z, and 0-9). str can range from 1 to 1023 characters (inclusively). So if I call this function with these perameters..
Code:
node *head == /*the head of the list to be examined*/
char key == "p"char *str == "dog"The new list will look like this...
node1 - 'd'
node2 - 'o'
node3 - 'g'
node4 - 'o'
node5 - 'd'
node6 - 'o'
node7 - 'g'
All instances of 'p' were replaced with 'dog' I have a toString function which takes in a string and converts it to a linked list and returns the head. So assume that you can call the function on str = "dog" so...
Code:
toString(str) == /*this will return the head to the list made from the str*/
If it's unclear what my question is...I am stumped on how to write the replaceChar function the one that takes in three perameters..
View 3 Replies
View Related
Dec 31, 2014
Code:
// Write a function called insertEntry() to insert a new entry into a linked list.
Have the procedure take as arguments a pointer to the list entry to be inserted (of type struct entry as defined in this chapter), and a pointer to an element in the list after which the new entry is to be inserted.
// The function dveloped in exercise 2 only inserts an element after an existing element in the list, thereby prenting you from inserting a new entry at the front of the list.
(Hint: Think about setting up a special structure to point to the beginning of the list.)
#include <stdio.h
struct entry1 {
int value;
struct entry1 *next;
};
[code]...
This is a working version of the exercise, but I don't think I'm doing what's asked. I was able to add an element to the beginning of the list using an if statement, not creating a special structure that points to the beginning of the list. How would I go about creating a special structure that points to the beginning of the list to add a new element at the beginning of the list?
View 8 Replies
View Related
