• Status: Solved
• Priority: Medium
• Security: Public
• Views: 239

# Quries Regarding Data Structures

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

Thanks & Regards
Venish Joe
0
venishjoe
2 Solutions

Commented:
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

Commented:
#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

Author Commented:
Thank U very Much for the Help U Provided
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.