Форум программистов, компьютерный форум, киберфорум
C для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.86/21: Рейтинг темы: голосов - 21, средняя оценка - 4.86
0 / 0 / 2
Регистрация: 09.10.2012
Сообщений: 32
1

Односвязнай список на статическом массиве

05.12.2012, 20:54. Показов 4285. Ответов 21
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
В общем, застряла.
Задание звучит так:

Элементы ОЛС находятся в массиве MemList, расположенном в статической памяти. Базовый тип зависит от задачи. «Свободные» элементы массива объединяются в список, на начало которого указывает поле-указатель первого элемента массива. Выделение памяти под информационную часть элемента ОЛС и запись в неё значения происходит при выполнении процедуры PutList. При выполнении процедуры GetList память, занимаемая элементом, освобождается.

Что есть на данный момент: файл list.h
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#ifndef LIST_H_INCLUDED
#define LIST_H_INCLUDED
#define   SizeList    100
 
const   ListOk = 0;//список найден
const   ListNotMem = 1//список не найден
const   ListUnder = 2;//список пустой 
const   ListEnd  = 3;//конец списка
 
typedef int BaseType;
 
typedef unsigned int *Ptrel;
 
typedef struct {
    Basetype data;//данные
    Ptrel next;//указатель на следующий эллемент
} Element memlist[SizeList];
 
typedef struct {
    Ptrel start;//указатель на первый эллемент
    Ptrel ptr;//указатель на текущий эллемент
    unsigned int n;
} List;
 
short listerror;
 
void initlist(List *l);//иницилизация списка+
int FullList(List *l)//проверка: список пуст+
int EndList(List *l)//проверка: конец списка+
usigned int Count(List *l)//кол-во эллементов в списке+
void BeginPtr(List *l)//Ptr на начало списка+
void EndPtr(List *l)//Ptr на конец списка+
void MovePtr(List *l)//Ptr на следующий эллемент+
void MoveTo(List *l, unsigned int n)//Ptr на n-ый эллемент+
void ReadList(List *l,BaseType *E)//чтение эллемента Е+
void PutList(List *l, BaseType E);//включение Е в L
void GetList(List *l, BaseType *E)//удаление E из L
void CopyList(List *l1,List *l2)//копирование l1 в l2
void DoneList(List *l)//удалить l
void InitMem()/*присваивает Flag каждoго элемента в 0*/
int EmptyMem() /*возвращает 1, если в массиве нет свободных элементов*/
unsigned  NewMem()//возвращает номер свободного элемента
void DisposeMem(unsigned n) /*делает n-й элемент масcива cвободным*/
#endif // LIST_H_INCLUDED
list.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
void initlist(List *l);//иницилизация списка
{
    l.start=NULL;
    l.ptr=NUll;
    l.n=0;
    listerror=listUnder;
}
 
int FullList(List *l)//проверка: список пуст
{
    if(l.n==0){listError=listEnd;
                return(1);}
      else return(0);
}
 
int EndList(List *l)//проверка: конец списка
{
    if(l.n==l.ptr){listError=ListEnd;
                    return(1)}
        else return(0);      
}
 
usigned int Count(List *l)//кол-во эллементов в списке
{
    return(l.n);
}
 
void BeginPtr(List *l)//Ptr на начало списка
{
    l.ptr=l.start;
}
 
void EndPtr(List *l)//Ptr на конец списка
{
    l.ptr=l.n;
}
 
void MovePtr(List *l)//Ptr на следующий эллемент
{
    l.ptr++;
}
 
void MoveTo(List *l, unsigned int n)//Ptr на n-ый эллемент
{
    l.ptr=l.ptr+n;
}
 
void ReadList(List *l,BaseType *E)//чтение эллемента Е
{
    if(l.ptr>l.n) ListError=ListUnder
      else {ListError=ListOk;
            E=*l.ptr};
}
 
void PutList(List *l, BaseType E);//включение Е в L
{   
        
}
 
void GetList(List *l, BaseType *E)//удаление E из L
{
    
}
 
void DoneList(List *l)//удалить l
{
    
}
 
void CopyList(List *l1,List *l2)//копирование l1 в l2
{
    DoneList(l2);
    l2.n=l1.n;
    l2.ptr=l1.ptr;
    l2.stert=l1.start;
    //выделитть память!!!!
}
 
void InitMem()/*присваивает Flag каждoго элемента в 0*/
{
    int i;
    for(i=0;i<SizeList;i++)
      memlist[i].next=0;
}
 
int EmptyMem() /*возвращает 1, если в массиве нет свободных элементов*/
{
    return(memlist[0].next==0);
}
 
unsigned  NewMem()//возвращает номер свободного элемента
{
    return()
}
 
void DisposeMem(unsigned n) /*делает n-й элемент масcива cвободным*/

Собственно, совершенно запуталась в указателях.
1. Указатель на эллемент массива - просто индекс? То есть на первый эллемент структуры указатель будет
C
1
l.ptr=1
. Или как-то иначе?
2. Вот, например, включение эллемента - memlist[0].next - указывает на поле data. Как обратиться к полю next через него?

Если есть общие рекомендации по реализации - с радостью выслушаю. На этом списке будут реализованы еще очередь и стек.

Добавлено через 2 часа 32 минуты
А да, еще вопрос:
Как через указатель обратиться к эллементу структуры? В Керниган-Ричи есть глава, посвященная этому, но там черт ногу сломит, во всяком случае, я не разобралась

Добавлено через 21 час 18 минут
И еще такой вопрос:
можно ли под структуру List выделить память таким образом:
C
1
2
if(calloc(1, sizeof(List)) ListError=ListNotMem
      else ListError=ListOk
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
05.12.2012, 20:54
Ответы с готовыми решениями:

Стек на статическом массиве
Может кто-нибудь написать стек на статическом массиве. Т.е чтобы был объявлен массив, объявлен...

Мусор в строковом статическом массиве C++
Если строковый статический массив заполнить \0, а потом вводить символы, количество которых &lt;...

Как представиь очередь, состоящую из структур, на статическом массиве?
из условия задачи: Разработать программу, реализующую алгоритм очереди (20 элементов). Задача...

Освобождение памяти из под Объектов в статическом массиве указателей
Всем добрый вечер! Решил расширить программу из книжки Лафорте Р. ООП в С++ стр. 574 путем...

21
4226 / 1795 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
05.12.2012, 20:58 2
Список по определению динамический. Кроме того, список не может быть и на динамическом массиве, так как в нём каждый следующий элемент должен быть доступен только через предыдущий, а добавление/удаление элемента должно гарантированно не затрагивать адреса размещения остальных элементов. Иначе это не список. Вот массив можно сделать на списке. Но не наоборот. И только динамический. Элементы массива можно дополнительно связать указателями на соседей, как в списке, но список и тогда будет не зависим от массива.
0
4226 / 1795 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
05.12.2012, 21:01 3
Элементы массива можно дополнительно связать указателями на соседей, как в списке, но список и тогда будет не зависим от массива.
0
4226 / 1795 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
05.12.2012, 21:01 4
Элементы массива можно дополнительно связать указателями на соседей, как в списке, но список и тогда будет не зависим от массива.
0
0 / 0 / 2
Регистрация: 09.10.2012
Сообщений: 32
05.12.2012, 21:02  [ТС] 5
Интерфейс был дан изначально. Реализовывать надо именно на этом интерфейсе.
0
0 / 0 / 2
Регистрация: 09.10.2012
Сообщений: 32
05.12.2012, 21:03  [ТС] 6
Интерфейс был дан изначально. Реализовывать надо именно на этом интерфейсе.
0
4226 / 1795 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
05.12.2012, 21:03 7
Можно элементы массива внести ещё и в список, но список всё равно будет не зависим от массива.
0
0 / 0 / 2
Регистрация: 09.10.2012
Сообщений: 32
05.12.2012, 21:03  [ТС] 8
Интерфейс был дан изначально. Реализовывать надо именно на этом интерфейсе.
0
4226 / 1795 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
05.12.2012, 21:03 9
Можно элементы массива внести ещё и в список, но список всё равно будет не зависим от массива.
0
0 / 0 / 2
Регистрация: 09.10.2012
Сообщений: 32
05.12.2012, 21:03  [ТС] 10
Интерфейс был дан изначально. Реализовывать надо именно на этом интерфейсе.
0
4226 / 1795 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
05.12.2012, 21:04 11
Можно элементы массива внести ещё и в список, но список всё равно будет не зависим от массива.
0
4226 / 1795 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
05.12.2012, 21:04 12
Можно элементы массива внести ещё и в список, но список всё равно будет не зависим от массива.
0
0 / 0 / 2
Регистрация: 09.10.2012
Сообщений: 32
05.12.2012, 21:04  [ТС] 13
Интерфейс был дан изначально. Реализовывать надо именно на этом интерфейсе.
0
4226 / 1795 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
05.12.2012, 21:05 14
Можно элементы массива внести ещё и в список, но список всё равно будет не зависим от массива.
0
4226 / 1795 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
05.12.2012, 21:05 15
Можно элементы массива внести ещё и в список, но список всё равно будет не зависим от массива.
0
0 / 0 / 2
Регистрация: 09.10.2012
Сообщений: 32
05.12.2012, 21:05  [ТС] 16
Интерфейс был дан изначально. Реализовывать надо именно на этом интерфейсе.
0
4226 / 1795 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
05.12.2012, 21:05 17
Можно элементы массива внести ещё и в список, но список всё равно будет не зависим от массива.
0
0 / 0 / 2
Регистрация: 09.10.2012
Сообщений: 32
05.12.2012, 21:06  [ТС] 18
Интерфейс был дан изначально. Реализовывать надо именно на этом интерфейсе.
0
4226 / 1795 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
05.12.2012, 21:08 19
То есть список из элементов массива, но не на массиве.
0
0 / 0 / 2
Регистрация: 09.10.2012
Сообщений: 32
05.12.2012, 21:11  [ТС] 20
Ну я так поняла:
есть структура - List. Это дескриптор списка. В нем хранится указатель на первый элемент и на текущий + длина списка.
Есть массив структур(элементов). Они связаны друг с другом указателями - те, которые принадлежат списку.
Это я и пыталась реализовать. Где не так, в объявлениях, или в я их использую неправильно?
0
05.12.2012, 21:11
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
05.12.2012, 21:11
Помогаю со студенческими работами здесь

Размещение данных в статическом массиве байтов фиксированной размерности с контролем переполнения
Всем привет. С лабой 3 не могу сообразить. Разработать две функции, одна из которых вводит с...

Webbrowser в статическом методе.
Всем привет, как дождаться загрузки webbrowser в статическом методе? Неудобно использовать private...

Объект в статическом методе
Помогите! Почему не могу работать с объектом в статическом методе, хотя в обычном методе все ОК??...

Ошибки в статическом классе
Есть такой вопрос. Необходимо создать статический класс MyMath, и использовать класс Math для...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru