?
Solved

Quries Regarding Data Structures

Posted on 2004-08-31
3
Medium Priority
?
232 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
3 Comments
 
LVL 45

Assisted Solution

by:sunnycoder
sunnycoder earned 800 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 1200 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

Get real performance insights from real users

Key features:
- Total Pages Views and Load times
- Top Pages Viewed and Load Times
- Real Time Site Page Build Performance
- Users’ Browser and Platform Performance
- Geographic User Breakdown
- And more

Question has a verified solution.

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

Although it can be difficult to imagine, someday your child will have a career of his or her own. He or she will likely start a family, buy a home and start having their own children. So, while being a kid is still extremely important, it’s also …
Q&A with Course Creator, Mark Lassoff, on the importance of HTML5 in the career of a modern-day developer.
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…
Progress

771 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