Solved

# A struct question

Posted on 2004-04-14
262 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
Question by:fj8283888
5 Comments

LVL 45

Expert Comment

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

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

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

## Join & Write a Comment Already a member? Login.

Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see so…
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use switch statements in the C programming language.

#### 762 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

#### Need Help in Real-Time?

Connect with top rated Experts

21 Experts available now in Live!