Solved

Quries Regarding Data Structures

Posted on 2004-08-31
3
225 Views
Last Modified: 2010-08-05
Hai Experts,

I have a few questions to ask.

#1. How should represent a straight-sided simple
polygon using a best suited linked list.

#2. An Efficient data structure with the supporting algorithm(s)
for picking a point in a user interface

#3. In Linked Lists fast deletion has the problem of leaving the deleted
elements unreachable yet occupied, thus causing wastage in storage spaces.Any
Solution for this problem

Awating for your Reply.....

Thanks & Regards
Venish Joe
0
Comment
Question by:venishjoe
3 Comments
 
LVL 45

Assisted Solution

by:sunnycoder
sunnycoder earned 200 total points
ID: 11949524
Hi venishjoe,
> #1. How should represent a straight-sided simple
> polygon using a best suited linked list.

Depends on what you intend to do with the information .... A linked list of structs with each struct representing co-ordinates of a vertex and elements linked in clockwise or counter-clockwise direction is good enough ...

You can also consider a variation of adjacency lists used to represent a graph.
 
> #2. An Efficient data structure with the supporting algorithm(s)
> for picking a point in a user interface

Not too clear ... What do you mean by picking a point in a user interface? Looking for some widget in the UI you prepared or what ?

> #3. In Linked Lists fast deletion has the problem of leaving the deleted
> elements unreachable yet occupied, thus causing wastage in storage spaces.Any
> Solution for this problem

When you search for a node, and find it
temp -> points to the node searched
prev -> points to node previous to the above node
prev = temp->next;
free (temp);

Keep a separate pointer to that node so that you can free it when you are done with changing the links

Sunnycoder
0
 
LVL 5

Accepted Solution

by:
rsriprac earned 300 total points
ID: 11950331
#1. How should represent a straight-sided simple
polygon using a best suited linked list.

Most efficient would be circular-single-linked-list, and each item in the list will represent the coordinate of the point.  There should also be a marker to prevent double-traversing.  It will be highly efficient.

#2. An Efficient data structure with the supporting algorithm(s)
for picking a point in a user interface

You should use distance-based picking algorithm, i.e. when the user clicks on or near the dot, measure the for the closeer dot and select that one.  Other then that, there is no need for a  data structure for handling events, since you are not storing any information.

#3. In Linked Lists fast deletion has the problem of leaving the deleted
elements unreachable yet occupied, thus causing wastage in storage spaces.Any
Solution for this problem

Sure, if you do a circular linked-list it should follow:

1 -> 2 -> 3 -> 4 -> ...-> n -> 1

You want to remove 3, scan till you hit 3, as you scan store the previous item

previous -> 2

 then create a deletion marker-pointer and point to 3:

deletion -> 3


re-link the list to remove the deletion by using the address in the 3 pointed to by the deletion pointer:

1 -> 2 -> 4 -> ...-> n -> 1

and then remove 3.

If you want a faster scan, then create a b-tree indexing.

-Ram
0
 
LVL 4

Author Comment

by:venishjoe
ID: 11972695
Thank U very Much for the Help U Provided
0

Featured Post

Better Security Awareness With Threat Intelligence

See how one of the leading financial services organizations uses Recorded Future as part of a holistic threat intelligence program to promote security awareness and proactively and efficiently identify threats.

Join & Write a Comment

Suggested Solutions

Title # Comments Views Activity
squareUp  challenge 22 107
strDist challenge 35 84
WMI, model #, retrieving information 10 94
C# Error - Add Failed 12 53
This article is meant to give a basic understanding of how to use R Sweave as a way to merge LaTeX and R code seamlessly into one presentable document.
This is about my first experience with programming Arduino.
An introduction to basic programming syntax in Java by creating a simple program. Viewers can follow the tutorial as they create their first class in Java. Definitions and explanations about each element are given to help prepare viewers for future …
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …

747 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

10 Experts available now in Live!

Get 1:1 Help Now