Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
СТРУКТУРА ДАНИХ “ЛІНІЙНИЙ ЗВ’ЯЗАНИЙ СПИСОК.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Електронні обчислювальні машини
Інформація про роботу
Рік:
2007
Тип роботи:
Лабораторна робота
Предмет:
Організація та функціонування комп’ютерів
Група:
КІ-1
Варіант:
15
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет „Львівська політехніка”
Кафедра ЕОМ
Звіт до лабораторної роботи №2
“ СТРУКТУРА ДАНИХ “ЛІНІЙНИЙ ЗВ’ЯЗАНИЙ СПИСОК” ”
Варіант№15
Виконав:
ст.гр. КІ-1
Львів 2007
Мета Роботи: Дослідити СТРУКТУРУ ДАНИХ “ЛІНІЙНИЙ ЗВ’ЯЗАНИЙ СПИСОК”.
2. Постановка задачі
Написати програму, яка будує два лінійних зв’язаних списки L1 i L2, що містить відповідно по N1 i N2 випадкових цілих чисел з проміжку [30; 300] і розміщує K елементів списку L2, починаючи з елемента P2 в список L1, починаючи з позиції P1 в ньому.
Опис алгоритму
Ініціалізовуємо два лінійних зв’язаних списку L1 i L2. За допомогою функції srand задаємо елементи списків. Далі ми визначаємо позиції Р1 та Р2 у списках. За допомогою циклу for від 1 до змінної К ми всавляємо елементи із позиції Р2 списку L2 у список L1 з позиції Р1.
Текст програми
Лістинг main.c
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include "plist.h"
#include "plist.c"
list MergeLists(list list2);
int fl;
void main()
{
list l2, tmp1, tmp2;
infotype x = 0;
Init(&l2);
printf("\nEnter elements:\n");
do
{
printf("Enter the new element(zero - break inputing elements): ");
scanf("%d",&x);
if (x!=0)
AddEnd(&l2,x);
}
while (x);
PrintStraight(l2);
tmp1 = l2;
tmp2 = FindLast (l2);
fl = 1;
while ((tmp1 = tmp1 -> next), (tmp2 = FindBefore (l2,tmp2)));
if (tmp1 -> data != tmp2 -> data)
fl = 0;
if (fl = 0)
printf ("Spusok dzerkalny");
else
printf ("Spusok ne dzerkalny");
getch();
return;
}
list MergeLists(list list2)
{
list mlist = NULL;
while (list2 )
{
AddEnd(&mlist,list2->data);
list2 = list2->next;
};
return mlist;
}
Лістинг pLIST.c
// Реалізація інтерфейсу обробки списків
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "plist.h"
// Ініціалізація списку
void Init(list *head_list_ptr)
{
*head_list_ptr = NULL;
return;
}
// Перевірка чи список порожній
int Empty(list head_list)
{
return head_list == NULL;
}
// Додавання нового вузла на початок списку
void AddStart(list *head_list_ptr, infotype new_data)
{
list new_node;
new_node = malloc(sizeof(struct node));
new_node->data = new_data;
new_node->next = *head_list_ptr;
*head_list_ptr = new_node;
return ;
}
// Додавання нового вузла в кінець списку
void AddEnd(list *head_list_ptr, infotype new_data)
{
list new_node;
new_node = malloc(sizeof(struct node));
new_node->data = new_data;
new_node->next = NULL;
if (Empty(*head_list_ptr)) *head_list_ptr = new_node;
else
FindLast(*head_list_ptr)->next = new_node;
return ;
}
// Вставка нового вузла після заданого вузла списку
void PutAfter(list *node_prt, infotype new_data)
{
list new_node = NULL;
new_node = malloc(sizeof(struct node));
new_node->data = new_data;
new_node->next = (*node_prt)->next;
(*node_prt)->next = new_node;
return ;
}
// Вставка нового вузла перед заданим вузлом списку
void PutBefore(list *node_prt, infotype new_data)
{
PutAfter(node_prt,new_data);
Change(node_prt,&((*node_prt)->next));
return ;
}
// Обмін інформаційних полів двух заданих вузлів списку
void Change(list *node1_ptr, list *node2_ptr)
{
infotype tmp = (*node1_ptr)->data;
(*node1_ptr)->data = (*node2_ptr)->data;
(*node2_ptr)->data = tmp;
}
// Пошук вузла із заданим значенням в списку
list Find(list head_list, infotype search_data)
{
while ((head_list) && (head_list->data != search_data)) head_list = head_list->next;
return head_list;
}
// Пошук вузла в списку, що знаходиться перед заданим вузлом
list FindBefore(list head_list, list node)
{
while ((head_list->next != node) && head_list) head_list = head_list->next;
return head_list;
}
// Пошук вузла в списку що знаходиться після заданого вузла
list FindAfter(list node)
{
return node->next;
}
// Пошук останнього вузла списку
list FindLast(list head_list)
{
if (head_list) while (head_list->next) head_list = head_list->next;
return head_list;
}
// Вилучення заданого вузла зі списку
void Delete(list *head_list_ptr, list *node_ptr)
{
list tmp , save_ptr=*node_ptr;
assert(*head_list_ptr);
assert(*node_ptr);
if (*node_ptr == *head_list_ptr)
*head_list_ptr = (*head_list_ptr)->next;
else
if (!((*node_ptr)->next))
{
tmp = FindBefore(*head_list_ptr,*node_ptr);
tmp->next = NULL;
}
else
{
tmp = (*node_ptr)->next;
(*node_ptr)->data = tmp->data;
(*node_ptr)->next = tmp->next;
save_ptr = tmp;
};
free(save_ptr);
return ;
}
// Роздрук списку в прямому порядку
void PrintStraight(list head_list)
{
while (head_list)
{
printf(printfspec,head_list->data);
head_list = head_list->next;
}
printf("\n");
return;
}
// Роздрук списку в зворотньому порядку
void PrintReverse(list head_list)
{
if (head_list)
{
PrintReverse(head_list->next);
printf(printfspec,head_list->data);
}
return;
}
Лістинг pLIST.h
// Інтерфейс обробки списків
#define infotype int
#define printfspec "%d "
/*
Нагадую символи форматування для основних типів даних:
----------------+-----------------------------
| %c | char |
|---------------+----------------------------|
| %d | int, short |
|---------------+----------------------------|
| %ld | long |
|---------------+----------------------------|
| %f | float, double |
|---------------+----------------------------|
| %s | arrays of type of char |
|---------------+----------------------------|
| %u | unsigned int,unsigned short|
|---------------+----------------------------|
| %lu | unsigned long |
----------------+-----------------------------
*/
struct node
{ infotype data;
struct node *next;
};
typedef struct node *list;
void Init(list *head_list_ptr);
int Empty(list head_list);
void AddStart(list *head_list_ptr, infotype new_data);
void AddEnd(list *head_list_ptr, infotype new_data);
void PutAfter(list *node_prt, infotype new_data);
void PutBefore(list *node_prt, infotype new_data);
void Change(list *node1_ptr, list *node2_ptr);
list Find(list head_list, infotype search_data);
list FindBefore(list head_list, list node_ptr);
list FindAfter(list node_ptr);
list FindLast(list head_list);
void Delete(list *head_list_ptr, list *node_ptr);
void PrintStraight(list head_list);
void PrintReverse(list head_list);
Результати тестування
1.
Enter elements:
Enter the new element(zero - break inputing elements):1
Enter the new element(zero - break inputing elements):2
Enter the new element(zero - break inputing elements):3
Enter the new element(zero - break inputing elements):3
Enter the new element(zero - break inputing elements):2
Enter the new element(zero - break inputing elements):1
Enter the new element(zero - break inputing elements):0
1 2 3 3 2 1
Spusok dzerkalny
2.
Enter elements:
Enter the new element(zero - break inputing elements):1
Enter the new element(zero - break inputing elements):8
Enter the new element(zero - break inputing elements):3
Enter the new element(zero - break inputing elements):5
Enter the new element(zero - break inputing elements):2
Enter the new element(zero - break inputing elements):1
Enter the new element(zero - break inputing elements):0
1 8 3 5 2 1
Spusok ne dzerkalny
Висновок: На данній лабораторній роботі було досліджено СТРУКТУРУ ДАНИХ “ЛІНІЙНИЙ ЗВ’ЯЗАНИЙ СПИСОК”.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора