Solved

Quries Regarding Data Structures

Posted on 2004-08-31
3
228 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

Free Tool: Postgres Monitoring System

A PHP and Perl based system to collect and display usage statistics from PostgreSQL databases.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

A short article about a problem I had getting the GPS LocationListener working.
Since upgrading to Office 2013 or higher installing the Smart Indenter addin will fail. This article will explain how to install it so it will work regardless of the Office version installed.
With the power of JIRA, there's an unlimited number of ways you can customize it, use it and benefit from it. With that in mind, there's bound to be things that I wasn't able to cover in this course. With this summary we'll look at some places to go…
In this seventh video of the Xpdf series, we discuss and demonstrate the PDFfonts utility, which lists all the fonts used in a PDF file. It does this via a command line interface, making it suitable for use in programs, scripts, batch files — any pl…

828 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