Справочник Томас Ниман Thomas Niemann



Скачать 467.32 Kb.
страница12/12
Дата14.06.2013
Размер467.32 Kb.
ТипДокументы
1   ...   4   5   6   7   8   9   10   11   12

4.8 Коды для разделенных списков



typedef int T; /* type of item to be sorted */

#define compLT(a,b) (a < b)

#define compEQ(a,b) (a == b)
/*

* levels range from (0 .. MAXLEVEL)

*/

#define MAXLEVEL 15
typedef struct Node_ {

T data; /* user's data */

struct Node_ *forward[1]; /* skip list forward pointer */

} Node;
typedef struct {

Node *hdr; /* list Header */

int listLevel; /* current level of list */

} SkipList;
SkipList list; /* skip list information */
#define NIL list.hdr
Node *insertNode(T data) {

int i, newLevel;

Node *update[MAXLEVEL+1];

Node *x;
/***********************************************

* allocate node for data and insert in list *

***********************************************/
/* find where data belongs */

x = list.hdr;

for (i = list.listLevel; i >= 0; i--) {

while (x->forward[i] != NIL

&& compLT(x->forward[i]->data, data))

x = x->forward[i];

update[i] = x;

}

x = x->forward[0];

if (x != NIL && compEQ(x->data, data)) return(x);
/* determine level */

newLevel = 0;

while (rand() < RAND_MAX/2) newLevel++;

if (newLevel > MAXLEVEL) newLevel = MAXLEVEL;
if (newLevel > list.listLevel) {

for (i = list.listLevel + 1; i <= newLevel; i++)

update[i] = NIL;

list.listLevel = newLevel;

}
/* make new node */

if ((x = malloc(sizeof(Node) +

newLevel*sizeof(Node *))) == 0) {

printf ("insufficient memory (insertNode)\n");

exit(1);

}

x->data = data;
/* update forward links */

for (i = 0; i <= newLevel; i++) {

x->forward[i] = update[i]->forward[i];

update[i]->forward[i] = x;

}

return(x);

}
void deleteNode(T data) {

int i;

Node *update[MAXLEVEL+1], *x;
/*******************************************

* delete node containing data from list *

*******************************************/
/* find where data belongs */

x = list.hdr;

for (i = list.
listLevel; i >= 0; i--) {


while (x->forward[i] != NIL

&& compLT(x->forward[i]->data, data))

x = x->forward[i];

update[i] = x;

}

x = x->forward[0];

if (x == NIL || !compEQ(x->data, data)) return;
/* adjust forward pointers */

for (i = 0; i <= list.listLevel; i++) {

if (update[i]->forward[i] != x) break;

update[i]->forward[i] = x->forward[i];

}
free (x);
/* adjust header level */

while ((list.listLevel > 0)

&& (list.hdr->forward[list.listLevel] == NIL))

list.listLevel--;

}
Node *findNode(T data) {

int i;

Node *x = list.hdr;
/*******************************

* find node containing data *

*******************************/
for (i = list.listLevel; i >= 0; i--) {

while (x->forward[i] != NIL

&& compLT(x->forward[i]->data, data))

x = x->forward[i];

}

x = x->forward[0];

if (x != NIL && compEQ(x->data, data)) return (x);

return(0);

}
void initList() {

int i;
/**************************

* initialize skip list *

**************************/
if ((list.hdr = malloc(sizeof(Node) + MAXLEVEL*sizeof(Node *))) == 0) {

printf ("insufficient memory (initList)\n");

exit(1);

}

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

list.hdr->forward[i] = NIL;

list.listLevel = 0;

}

5. Литература


[1] Donald E. Knuth. The Art of Computer Programming, volume 3. Massachusetts:

Addison-Wesley, 1973. Есть русский перевод: Д.Кнут. Искусство программирования для ЭВМ. Т.3. Изд-во “Мир”, М.1978.
[2] Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest. Introduction to Algo-

rithms. New York: McGraw-Hill, 1992.
[3] Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. Data Structures and Algorithms. Massachusetts: Addison-Wesley, 1983.
[4] Peter K. Pearson. Fast hashing of variable-length text strings. Communications of the

ACM, 33(6):677-680, June 1990.
[5] William Pugh. Skip lists: A probabilistic alternative to balanced trees. Communications

of the ACM, 33(6):668-676, June 1990.

6. Словарь


Term

Термин

sort by insertion

сортировка вставками

array

массив

linked list

линейный список

comparison

сравнение

in-place

на месте (без дополнительных массивов)

stable sort

устойчивая сортировка

underflow

вырождение

overflow

переполнение

red-black tree

красно-черное дерево

skip list

разделенный список

rotation

вращение




1 Терминология Д.Кнута (т.1,п.2.3.1): postorder. В оригинале данной работы этот же порядок назван in-order.

1   ...   4   5   6   7   8   9   10   11   12

Похожие:

Справочник Томас Ниман Thomas Niemann iconБердникова Дарья Владимировна Лингвистические особенности текстов произведений англо-шотландского фольклора Художественный текст, примером которого является баллада “Thomas the Rhymer” «Томас Рифмоплет»
Художественный текст, примером которого является баллада “Thomas the Rhymer” («Томас Рифмоплет»), несет в себе не только смысловое...
Справочник Томас Ниман Thomas Niemann iconДжефферсон томас
Джефферсон, томас (Jefferson, Thomas) (1743–1826), 3-й президент сша, автор Декларации независимости, архитектор, ученый, просветитель....
Справочник Томас Ниман Thomas Niemann iconТомас Роберт Мальтус Thomas Robert Malthus
Опыт о законе народонаселения и его воздействии на будущее улучшение общества с замечаниями о построениях гг. Годвина, Кондорсе и...
Справочник Томас Ниман Thomas Niemann iconТомас нагель что все это значит? Очень краткое введение в философию Thomas Nagel «What Does It All Mean? A very Short Introduction to Philosophy»
Нагель провел в стенах Корпус Кристи Колледжа в Оксфордском университете (Англия), где имел честь слушать лекции Джона Остина и получить...
Справочник Томас Ниман Thomas Niemann iconСправочник сталкера. Азбука выживания «Справочник сталкера. Азбука выживания»
Этот справочник, вы без труда обнаружите на схеме несколько принципиальных ошибок в действиях группы, приведших в конечном счете...
Справочник Томас Ниман Thomas Niemann iconСправочник Москва, 2004 год Организации социальной направленности района «Академический». Справочник
«Академический» юзао г. Москвы. Справочник, в первую очередь, адресован жителям района и округа, которые могут воспользоваться услугами,...
Справочник Томас Ниман Thomas Niemann iconПроект летней полевой игры по мотивам книги Thomas Malory "Le Morte Darthure"
Проект летней полевой игры по мотивам книги Thomas Malory “Le Morte Darthure” и других источников
Справочник Томас Ниман Thomas Niemann iconТомас гоббс гоббс, томас
Якова I, изучал философию в правление Карла I, был знаменит и находился под подозрением при Кромвеле и, наконец, вошел в моду как...
Справочник Томас Ниман Thomas Niemann iconСправочник по языку c я пишу на c с 1989 года. Этот краткий справочник был составлен мною очень давно

Справочник Томас Ниман Thomas Niemann iconСправочник "Тип мед персоналу" Добавлен новый справочник. Так как в справочник "Тип персоналу"
Тип мед персоналу” (это значение влияет на формирование отчетов). Всем должностям не медицинских специальностей присваивается значение...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org