Solved

Quries Regarding Data Structures

Posted on 2004-08-31
3
229 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 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: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

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

Suggested Solutions

Title # Comments Views Activity
Need help making a program or form for inventory that exports to txt 8 50
Help Required 3 133
What does != "" mean in programming 8 184
asp Google Map 2 91
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.
In this post we will learn how to connect and configure Android Device (Smartphone etc.) with Android Studio. After that we will run a simple Hello World Program.

739 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