Solved

A struct question

Posted on 2004-04-14
5
268 Views
Last Modified: 2010-04-15
The question I found it from the text as following:
You are required to design, implement and test a function, sort_list(.), which will sort such a list according to the priority value computed by whatever function is passed as its second argument. The first argument is to be a pointer to the head of the list. Since the OS will have other structures with pointers to IORB's, the list must be sorted in place.

typedef struct iorb {
            
                        short base_pri;
                        struct iorb *link;
                        char filler[110];
                        
                        } IORB;
void sort_list(IORB **list,int(*newpr)(short));
int newp(short base)
{
return base;
}
just want to know how to build up a list and how to insert a value.

Thanks,
Frank
0
Comment
Question by:fj8283888
[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
5 Comments
 
LVL 45

Expert Comment

by:sunnycoder
ID: 10821502
From what I could gather, you will be given the list ... All you need to do is to get priorities and sort it

step 1. traverse the list (arg 1 ) ... for each element, get priority using function given as arg 2 ... store this value in the node's base_pri field

step2: sort the list in place
0
 
LVL 12

Accepted Solution

by:
stefan73 earned 125 total points
ID: 10821801
Hi fj8283888,

Sorting in-place of a linked list can be done by bubble sort, which is bad by means of having quadratic behaviour, but easy to implement.

The problem with priority queues is to have both a favourable insert and fetch behaviour.

O(n) for insert and O(1) for fetch is trivial - it's just a linked list where you insert a new node after the last node of equal or higher priority.

Probably the fastest way should be a binary tree with the smallest element (or highest priority) on top.

Cheers,
Stefan
0
 
LVL 9

Expert Comment

by:ankuratvb
ID: 10821820
To build a list,you need a pointer for the start node.
Lets say the start node is p;

The first node insertion:
Allocate memory for node
//p=malloc(sizeof(struct iorb));
//Insert data into the node.
p->data=//ur data here
//Set next pointer to NULL for now.
p->link=NULL;

The next time around,you allocate memory to append to this list.
i.e. create a new node,set the link pointer of the prev. node to point to this new node'
0

Featured Post

Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

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

Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were small…
This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use for-loops in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use conditional statements in the C programming language.

705 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