離散數學(7)

第七章 Relations: The Second Tine Around

A relation R on a set A is called reflexive(反身性) if for all x ε A (x,x) ε R

Relation R on set A is called symmetric(對稱性) if(x,y) εR → (y,x) ε R for
all x,y ε A

For a set A, a relation R on A is called transitive of, for all x,y,z ε A, (x,y),(y,z) ε R → (x,z) ε R.(So if x “is related to” y, and y “is related to” z, we want x “related to” z, withy playing the role of “intermediary”.

Given a relation R on a set A, R is called antisymmetric if for all a,b εA ,(aRb and bRa) → a=b

A relation R on a set A is called a partial order, or a partial ordering relation, if R is reflexive, antisymmetric, and transitive.

If A, B, and C are sets with R1cAxB and R2c BxC, then the composite relation R1◦R2 is a relation from A to C defined by  R1◦R2={(x,z)|x εA,
z ε C, and thereexists y ε B with (x,y) εR (y,z) εR2}

長方桌排列

有10個人 在長方桌作排列

一邊可坐3人 一邊可坐2人

共有10! /2種排列

作業系統(2)

第二章 System Structures

An operating System provides the environment within which programs are executed.

User interface. Almost all operating systems have a user interface(UI). The interface cam take several forms. One is DTrace Command-line interface(CLI), which uses text commands and a method for entering them.

Another is a batch interface, in which commands and directives to control those commands are entered into files, and those files are executed.

Most commonly, a graphical user interface(GUI) is used. Here, the interface is a window system with a pointing device and direct I/O, choose from menus, and make selections and a keyboard to enter text.

On systems with multiple command interpreters to choose from, the interpreters are known as shells.

System calls provide an interface to the services made available by an operating system.

System programs, also known as system utilities, provide a convinient environment for program development and execution.

The kernel has a set of core components and links in additional services either during boot time or during run time. Such a strategy uses dynamically loadable modules and is common in modern implementations of UNIX.

Seven types of loadable kernel modules
1. Scheduling classes
2. File systems
3. Loadable system calls
4. Executable formats
5. STREAMS modules
6. Miscellaneous
7. Device and bus drivers.

離散數學(6)

第六章 Languages: Finite State Machines

If ∑ is an alphabet and n ε Z+, we define the powers of ∑ recursively as follows:

1)∑1=∑

2)∑^n+1={xy|x ε ∑, y ε ∑^n} where xy denote the juxtaposition of x and y

For a alphabet ∑ we define ∑0={λ},where λ denotes the empty string—that is, the string consisting of no symbols taken from ∑.

If ∑ is an alphabet

a)∑ +=n=1 to 無限大U∑ n=Un ε z+∑ n

b)∑ *=n=0 to無限大 U∑ n

離散數學(5)

第五章 Relations and Functions

5.1 Cartesian Products and Relations

For sets A,B the Cartesian product, or cross product, of A and B is denoted by AxB and equals{(a,b)|a ε A,b ε B}.

For sets A,B, any subset of AxB is called a (binary) relation from A to B. Any subset of AxA is called a (binary) relation on A.

For nonempty sets A, B, a function, or mapping, from A to B, denoted

f :A → B, is a relation from A to B in which every element of A appears exactly once as the first component of an ordered pair in the relation.

For the function of f:A → B, A is called the domain(定義域) of f and B the codomain(對應域) of f. The subset of B consisting of those elements that appear as second component in the ordered pairs of f is called the range(值域) of f and is also denoted by f(A) because it is the set of images under f.

A domain f:A → B is called one-to-one, or injective, if each element of B appears at most once as the image of an element of A.

A function of f:A → B is called onto, or surjective, if f(A)=B—that is, if for all b ε B there is at least one a ε A with f(a)=b.

作業系統(1)

第一章 Introduction

An operating systen is a program that manages the computer hardware.

The hardware—the central processing unit(CPU), the memory, and the input/ouput(I/O) devices – provides the basic computers resources for the system.

The application programs—such as word processors, spreadsheets, compiler, and Web browsers—define the ways in which these resources are used to solve users' computing problems.

The operating system controls the hardware and coordinate its use among various application programs fir the various users.

A more common definition, and the one that we usually follow, is that the operating system is the one program running at all times on the computer—usually called the kernel.

Softeare may trigger an interrupt by executing a special operation called a system call.

On a single-processor system, there is one main CPU capable of excuting a general-purpose instuction set, including instructions from user processes.

Multiprocessor systems(also known as parallel systems or tightly coupled systems) are growing in importance. Such systems have two or more processors inclose communication, sharingthe computer bus and sometimes the clock, memory, and peripheral devices.

A trap (or an exception) is software-generated interrupt caused either by an error(for example, division by zero or invalid memory access) or by a specific request from a user program that an operating-system service be performed.

User mode amd kernel mode(also called supervisor mode, system mode, or privileged mode). A bit, called the mode bit, is added to the hardware of the computer to indicate the current mode : kernel(0) or user(1).

Embedded systems almost always run real-time operating system. A real-time system is used when rigid time requirements have been placed on the operation of a processor or the flow of data.


The operating system is responsible for the following activities in connection with process management

i)Scheduling processes and threads on the CPUs
ii)Creating and deleting both user and system processes
iii)Suspending and resuming processes
iv)Providing mechanisms for process synchronization
v)Proving mechanisms for process communication.

離散數學(4)

第四章 Properties of the integers: Mathematical Induction

All that is needed is for the open statement S(n) to be true for some first element n0 ε Z so that the induction process has a starting place. We need the truth of S(n0) for our basis step. The integer n0 could be 5 just as well as 1. It could even be zero or negative because the set Z+ in union with {0}{ or any finite set of negative integers is well ordered.

Principle of Mathematical Induction

[S(n0) ^ [all k>=n0[s(k) → s(k+1)]]] → all n >=no s(n)

Principle of Strong Mathematical Induction

a) If s(n0),s(n0+1), s(n0+2)...,s(n1-1),s(n1) are true

b)If whenever s(n0) s(n0+1)...s(k-1)and s(k) are true for some k ε z+, where k>=n1, then the statement s(k+1) is also true;then s(n) is true for all n>=n0

If a,b ε z and b=\0 , we say that b divides a and we write b|a, if there is an integer n such that a=bn, where this occurs we say that b is a divisor(因數), or a is a multiple(倍數) of b.

a) 1|a and a|0

b) [(a|b)^(b|a)] → a=+-b

c)[(a|b)^(b|c)] → a|c

d) a|b → a|bx for all x ε Z

e) If x=y+z for some x,y,z ε Z, and a divides two of the three integers x,y and z, then a divides the remaining integer.

f)[(a|b)^a|c)] → a|(bx+cy) for all x,y ε Z

g)For 1<=i<=n let ci ε Z. If a divides each ci, then a|(c1x1+c2x2+...+cnxn), where xi ε Z for all 1<=i<=n

離散數學(3)

第三章 Set Theory

A set should be well-defined collection of objects. These objects are called elements and we said to be members of the set.

If C,D are sets from a universe U, we say that C is a subset of D and write C c D or D c C , if every element of C is an element of D. If , in addition, D contains an element that is not in C, then C is called a proper subset of D, and this is denoted by C c D

for A,B c U we define the flowing

a) A U B( the union of A and B) = {x|x ε A V ε B}

b) A∩B( the intersection of A and B) = {x| x ε A ^ ε B}

c)AΔB(the symmetric difference of A and B ) = {x| (x ε A V ε B) ^

x not ε A∩B}={x|x ε AUB ^ x not ε A∩B}

離散數學(2)

第二章 Fundamentals of Logic

In the development of any mathematical theory, assertions are made in the form of sentences. Such verbal or written assertions, called statements (or propositions), are declarative sentences that are either true or false.

1)Transform a given statement p into the statement ¬p, which denotes its negation and is read “Not p.”

2)

a) Conjunction:The conjunction of the statements p,q is denoted by p^q, which is read “p and q.”

b) Disjunction: The expression p V q denotes the disjunction of the statements p,q and is read “p or q.”

c)Implication: We say that “p implies q” and write p->q to designate the statement, which is the implication of q by p.

i)If p, then q.

ii)p is sufficient for q

iii)p is sufficient condition for q

iv)q is necessary for p
v)q is a necessary condition for p
vi) p only if q
d) Bi-conditional: The bi-conditional of two state¬ments p,q is denoted by
p ↔ q, which is read “p if and only if q” or “p is necessary and sufficient for q”
“p if and only if q” 可縮寫成 “p iff q”

p q p^q p V q p V q p->q q ↔ p

0 0 0 0 0 1 1

0 1 0 1 1 1 0

1 0 0 1 1 0 0

1 1 1 1 0 1¬ 1

A compound statement is called a tautology if it is true for all truth value assignments for its component statements. If a compound statement is false for all such assignments, then it is called a contradiction.

¬

Two statements s1,s2 are said to be logically equivalent, and we write

s1 ↔ s2, when the statement s1 is true if and only if the statement s2 is true.

¬

Let s be a statement. If s contains no logical connectives other than ^ and V, then the dual of s denoted sd, is the statement obtained from s by replacing each occurrence of ^ and V by V and ^, respectively, and each occurrence of T0 and F0 by F0 and To, respectively.

The principle of duality, let s and t be statements that contain no logical connectives other than ^ and V.

if s ↔ t, than sd ↔ td

p->q ↔ ~p V q

The statement ¬q → ¬p is called contrapositive of the implication p → q

The statement q → p is called the converse of p → q

¬p → ¬q is called the inverse of p → q

The contrapositive(否逆)：¬q → ¬p

The converse(逆): q → p

The inverse (否) : ¬p → ¬q

When we write allxp(x)->exist x p(x) we are saying that the implication allxp(x) → exist x p(x) is a logical implication.


Two substitution rules
1)Suppose that the compound statement P is a tautology. If p is primitive statement that appears in P and we replace each occurrence of p by the same q, then the resulting compound statement P1 is also a taotology.
2)Let P be a compound statement where p is an arbitrary statement that appears in P, and let q be a statement such that q ↔ p, Suppose that in P we replace one or more occurences of p by q. Then this replacement yields the compound statement P1. Under these circumstances P1 ↔ P.

p → q   <=> ~p V q  <=> ~q → ~p

離散數學(1)

第一章 Fundamental Principles of Counting

Enumeration, or counting, may strike one as an obvious process that a student learns when first studying arithmetic.

Our study of discrete and combinatorial mathematics begins  with two basic principles of counting: the rules of sum and product.

The Rule of Sum: If a first task con be performed in m ways, while a second task can be performed in n ways, and the two task cannot be performed simultaneously, then performing either task can be accomplished in any one of m+n ways.

The Rule of Product: If a procedure can be broken down into first and second stages, and if there are m possible outcomes for first stage and if, for each of these outcomes, there are n possible outcomes for the second stage, then the total procedure can be carried out, in the designated order, in mn ways.

For an integer n >= 0, n factorial ( denoted n¦)
is defined by 0¦=1
                         n¦=(n)(n-1)(n-2)...(3)(2)(1) for n >= 1

Given a collection of n distinct objects, any(linear) arrangement of these objects is called a permutation of the collection.

If there are n distinct objects and r is an integer, with 1<=r<=n, then by the rule of product, the number of permutation of size r for the n objects

p(n,r)=n*(n-1)*(n-2)*...*(n-r+1)
=(n)(n-1)(n-2)...(n-r+1)*(n-r)(n-r-1)...(3)(2)(1)/((n-r+1)*(n-r)(n-r-1)...(3)(2)(1))
=n¦/(n-r)¦

If there are n objects with n1 indistinguishable objects of a first type, n2  indistinguishable objects of a second type,..., and nr  indistinguishable objects of a nth type, where n1+n2+...+nr=n
then there are n¦/(n1¦n2¦...nr¦) (linear) arrangements of the given n objects.

If we start with n distinct objects, each selection, or combination, of r of these objects, with no reference to order,corresponds to r¦ permutations of size r from the n objects. Thus the number of combinations of size r from a collection of size n is

C(n,r)=P(n,r)/r¦=n¦/(r¦(n-r)¦)  0<=r<=n

The binomial Theorem
(x+y)^n=(n,0)x^0y^n+(n,1)X^1y^n-1+(n,2)X^2y^(n-2)+...+(n,n-1)x^(n-1)y^1+(n,n)x^ny^0=form k=0 to n∑(n,k)x^ky^(n-k)

C++(1)

第一章 Introduction to Computers and C++ Programming

A computer is a device capable of performing computations and making logical decisions at speeds millions of times faster than human beings can.

Input Unit

Output Unit

Memory Unit

Arithmetic and Logic Unit

General Processing Unit

Secondary Storage Unit

#include <iostream>

using std::cout;

using std::cin;

using std::endl;

int main()

{

    int num1, num2;

    cout << “Enter two integers, and I will tell you\n”

           << “the relationships they satisfy:”;

    cin >> num1 >> num2;

    if(num1==num2)

        cout << num1 << “ is equal to “ << num2 << endl;

    if( num1 != num2 )

        cout << num1 << “ is not equal to “ << num2 << endl;

    return 0; //indicate that program ended successfully

}

資料結構(8)

第八章 Graphs and Their Applications

8.1 Graphs

A graph consists of a set of nodes(or vertices) and a set of arcs(or edges). Each arc in a graph is specified by a pair of nodes.

Note that a graph need not to be a tree, but that a tree must br a graph.

A node n is incedent to an arc x if n is one of the two nodes in the ordered pair of nodes that constitute x. The degree of a node is the number of arcs incident to it.

The indegree of a node n is the number of arcs that have n as the head, and the outdegree of n is the number of arcs that have n as the tail.

Such a graph, in which a number is associated with each arc, is called a weighted graph or a network. The number associated with an arc is called its weight.

A path from a node to itself is called a cycle.

#define MAXNODES 50

struct node{

/*information associated with each node*/

};

struct arc{

int adj;

/*information associated with each arc*/

};

struct graph{

struct node nodes[MAXNODES];

struct arc arcs[MAXNODES][MAXNODES]

};

struct graph g;

void join(int adj[][MAXNODES], int node1, int node2)

{

/* add an arc from node1 to node2*/

adj[node1][node2]=TRUE;

}

void remv(int adj[][MAXNODES], int node1, int node2)

{

/* delete an arc from node1 to node2*/

adj[node1][node2]=FALSE;

}

int adjacent(int adj[][MAXNODES], int node1, int node2)

{

return ((adj[node1][node2]==TRUE)?TRUE:FALSE);

}

Transitive Closure

Its value is TRUE if and only if the values of both adj[i][k] and adj[k][j] are TRUE, which implies that there is an arc from node I to node k and an arc from node k to node j.

path0[i][j]=adj, since the only way to go from node I to node j without passing through any other nodes is to go directly from I to j.

void transclose(int adj[][MAXNODES], int path[][MAXNODES])

{

int I,j,k;

for(i=0;i<MAXNODES;++i)

for(j=0;j<MAXNODES;++j)

path[i][j]=adj[i][j];

for(k=0;i<MAXNODES;++k)

for(i=0;j<MAXNODES;++i)

if(path[i][k]==TRUE)

for(j=0;j<MAXNODES;++j)

path[i][j]=path[i][j]||path[k][j];

}

Page 527 Shortest-Path Algorithm

Spanning Forests

A forest may be defined as an acyclic graph on which every node has one or no predecessors.

資料結構(9)

第九章 Storage Management

A list is simply a sequence of objects called elements. Associated with each list element is a value.

q=nullelt;

p=first(list);

while(p!=nullelt)

{

if(info(p)=='w')

{

/*remode node(p) from the list*/

p=next(p);

if(q == nullelt)

setnext(q,p);

}

else

{

p=q;

p=next(p);

}

}

#define INTGR 1

#define CH 2

#define LST 3

struct nodetype{

int utype;

union{

int intgrinfo;

char charinfo;

struct nodetype *listinfo;

} info;

struct nodetype *next;

};

typedef struct nodetype *NODEPTR;

NODEPTR tail(NODEPTR list)

{

if(list==NULL)

{

printf(“illegal tail operation”);

exit(1);

}

else

return list->next;

}

struct {

int utype;

union{

int intgrinfo;

char charinfo;

struct nodetype *listinfo;

} info;

} infotype;

typedef struct infotype *INFOPTR;

void head(NODEPTR list,INFOPTR pitem)

{

if(list==NULL)

{

printf(“illegal head operation”);

exit(1);

}

pitem = (INFOPTR) malloc (sizeof(struct infotype));

pitem->utype=list->utype;

pitem->info=list->info;

return;

}

NODEPTR addon(NODEPTR list,struct infotype *pitem)

{

NODEPTR newptr;

newptr=(INFOPTR)malloc(sizeof(struct nodetype));

newptr->utype=pitem->utype;

newptr->info = pitem->info;

newptr->next=list;

return newptr;

}

void settail(NODEPTR *plist,NODEPTR t1)

{

NODEPTR p;

p=*plist->next;

*plist->next=t1;

freelist(p);

}

Reference Count Method

Under this method each node has an additional count field that keeps a count (called the reference count) of the number of pointers(both internal and external) to that node.

Collection and Compaction

for(i=1;i<MAXNODES;i++)

{

node[i].header=0;

node[i].headptr='N';

node[i].infoptr='N';

node[i].nextptr='N';

}

newloc=0;

for(nd=1;nd<MAXNODES;nd++)

if(node[nd].mark==TRUE)

newloc++;

p=node[nd].header;

source = node[nd].headptr;

while(p!=0)

if(source=='I')

{

q=node[p].lstinfo;

source=node[p].infoptr;

node[p].lstinfo=newloc;

node[p].infoptr='N';

p=q;

}

else

{

q=node[p].next;

source=node[p].nextptr;

node[p].next=newloc;

node[p].nextptr='N';

p=q;

}

node[nd].headptr='N';

node[nd].header=0;

if((node[nd].utype==LST)&&(node[nd].lstinfo!=0))

{

p=node[nd].lstinfo;

node[nd].lstinfo=node[p].header;

node[nd].infoptr=node[p].headptr;

node[p].header=nd;

node[p].headptr='I';

}

p=node[nd].next;

node[nd].next=node[p].header;

node[nd].nextptr=node[p].headptr;

if(p!=0)

{

node[p].header=nd;

[node[p].headptr='L';

}

}

newloc=0;

for(nd=1;nd<MAXNODES;nd++)

if(node[nd].mark)

{

newloc++;

p=node[nd].header;

source = node[nd].headptr;

while(p!=0)

if(source=='I')

{

q=node[p].lstinfo;

source=node[p].infoptr;

node[p].lstinfo=newloc;

node[p].infoptr ='N';

p=q;

}

else

{

q=node[p].next;

source=node[p].nextptr;

node[p].next=newloc;

node[p].nextptr ='N';

p=q;

}

node[nd].headptr='N';

node[nd].header=0;

node[nd].mark=false;

node[newloc]=node[nd];

}

資料结構(7)

第七章Searching

7.1 Basic Search Techniques

A table or a file is a group of elements, each of which is called a record. Associated with each record is a key, which is used to differentiate among different records.

In the simplest form, the key is contained within the record at a specific offset from the start of the record. Such a key is called an internal key or an embedded key.

For every file there is at least one set of keys that is unique. Such a key is called a primary key.

It will probably not be unique, since there may be two records with the same state in the file, such a key is called a secondary key.

A search algorithm is an algorithm that accepts an argument a and tries to find a record whose key is a.

A table of records in which a key is used for retrieval is often called a search table or as dictionary.

Dictionary as an abstract data type

typedef KEYTYPE ... /* a type of key*/

typedef RECTYPE … /* a type of record*/

RECTYPE nullrec=... /*a “null” record*/

KEYTYPE keyfunct(r)

RECTYPE r;

{…
};

abstract typedef [rectype] TABLE (RECTYPE);

abstract member(tbl,k)

TABLE(RECTYPE) tbl;

KEYTYPE k;

postcondition if(there exists an r in tbl such that keyfunct(r)==k)

then member = TRUE

else member = FALSE

abstract RECTYPE search(tbl,k)

TABLE(RECTYPE) tbl;

KEYTYPE k;

postcondition (not member(tbl,k)&& (search == nullrec)

|| (member(tbl,k) &&keyfunct(search)==k);

abstract insert(tbl,r)

TABLE(RECTYPE) tbl;

KEYTYPE r;

precondition member(tbl,keyfunct(r))==FALSE

postcondition insert(tbl,r);

(tbl-[r])==tbl'

abstract delete(tbl,k)

TABLE(RECTYPE) tbl;

KEYTYPE k;

postcondition tbl==(tbl'-[search(tbl,k)]);

Binary Search

The most efficient method of searching a sequential table without the use of auxiliary indices or table is the binary search.

O(logn)

low=0;

hi=n-1;

while(low<=hi)

{

mid=(low+hi)/2;

if(key==k(mid))

return mid;

if(key<k(mid))

hi=mid-1;

else

low=mid+1

}

return -1;

Interpolation Search

Another technique for searching an ordered array is called interpolation search. If the keys are uniformly distributed between k(0) and k(n-1)

O(loglogn)

Tree Searching

Inserting into a binary tree

q=null;

p=tree;

while(p!=null)

{

if(key==k(p))

return p;

q=p;

if(key<k(p))

p=left(p);

else

p=right(p);
}

v=maketree(rec,key);

if(q==null)

tree=v;

else

if(key<k(q))

left(q)=v;

else

right(q)=v;

return v;

Deleting from a binary search tree

q=null;

p=tree;

while(p!=null && k(p)!=key)

{

q=p;

p=(key<k(p)?left(p):right(p);

}

if(p==null)

return;

Balanced Trees

If the probability of searching for a key in a table is the same for all keys, a balanced tree yields the most efficient search.

/* Part I: search and inset into the binary tree*/

fp=null;

p=tree;

fya=null;

ya=p;

/* ya points the youngest ancestor whick may become unbalanced*/

while(p!=null)

{

if(key==k(p))

return p;

q= (key <k(p))? left(p):right(p);

if(q!=null)

if(bal(q)!=0)

{

fya=p;

ya=q;

}

fp=p;

p=q;

}

q=maketree(rec,key);

bal(q)=0;

(key<k(fp))?left(fp)=q:right(fp)=q;

p=(key<k(ya))?left(ya):right(ya);

s=p;

while(p!=q)

{

if(key<k(p))

{

bal(p)=1;

p=left(p);

}

else

{

bal(p)=-1;

p=right(p);

}

}

/*Part II:tree is unbalanced*/

imbal=(key<k(ya))?1:-1;

if(bal(ya)==0)

{

bal(ya)=imbal;

return q;

}

/* part III:rebalanced*/

if(bal(s)==imbal)

{

P=S;

if(imbal==-1)

rightrotation(ya);

else

leftrotation(ya);

bal(ya)=0;

bal(s)=0;

}

else

{

if(imbal==1)

{

p=right(s);

leftrotation(s);

left(ya)=p;

rightrotation(ya);

}

else

{
p=left(s);

right(ya)=p;

rightrotation(s);

leftrotation(ya);

}

if(bal(p)==0)

{

bal(ya)=0';

bal(s)=0;

}

else

{

if(bal(p)==imbal)

{

bal(ya)=-imbal;

bal(s)=0;

}

else

{

bal(ya)=0;

bal(s)=imbal;

}

}

bal(p)=0

}

if(fya==null)

tree=p;

else

ya=right(fya))?right(fya)=p:left(fya)=p;

return q;

A multiway search tree of order n is a general tree in which each node has n or fewer subtrees and contains one fewer key than it has subtrees.

p=tree;

if(p==null)

{

position = -1;

return -1;

}

i=nodesearch(p,key);

if(i<numtrees(p)-1&& key==k(p,i)

{

position=i;

return p;

}

return search(son(p,i));

====================================

p=tree;

while(p!=null)

{

i=nodesearch(p,key);

if(i<numtrees(p)-1&& key==k(p,i)

{

position=i;

return p;

}

p=son(p,i);

}

position = -1;

return -1;

traversing a multiway tree

if(tree !=null)

{

nt=numtrees(tree);

for(i=0;i<nt-1;i++)

{

traverse(son(tree,i);

printf(“%d”,k(tree,i));

}

traverse(son(tree,nt);

}

B+-Trees

One of the major drawbacks of the B-tree is the difficulty of traversing the key sequentially.

11.4 Hashing

A function that transforms a key into a table index is called a hash function. If h is a hash function and key is a key, h(key) is called the hash of key and is the index at which a record with the key should be placed.

#define TABLESIZE …

typedef KEYTYPE …

typedef RECTYPE …

struct record{

KEYTYPE k;

RECTYPE r;

} table[TABLESIZE];

int search(KEYTYPE key,RECTYPE rec)

{

int i;

i=h(key);

while(table[i].k!=key && table[i].k!=nullkey)

{

i=rh(i); //rehash

}

if(table[i].k==nullkey)

{

table[i].k=key;

table[i].r=rec;

}

return i;

}

struct nodetype *search(KEYTYPE key, RECTYPE rec)

{

struct nodetype *p,*q,*s;

i=h(key);

q=NULL;

p=bucket[i];

while(p!=NULL&&p->k!=key)

{

q=p;

p=p->next;

}

if(p->k==key)

return p;

s=getnode();

s->k=key;

s->r=rec;

s->next=NULL;

if(q==NULL)

bucket[i]=s;

else

q->next=s;

return s;

}

Perfect Hash Functions

Given a set of keys K={k1,k2,...,kn} a perfect hash function is a hash function h such that h(ki)!=h(kj) for all distinct i and j.

h(key)=((r+s*key)%x)d

remainder reduction perfect hash function.