Differences

This shows you the differences between two versions of the page.

--- courses:programming:extra_tasks [2017/03/23 09:39]
pro100kot
+++ courses:programming:extra_tasks [2017/05/04 08:18]
pro100kot
@@ Line 61: / Line 61: @@
 **Идея:**
-Идеологически - линейный односвязный список это структура данных, представляющая собой список узлов, каждый их когорого хранит какие-то данные и указатель на следующий элемент. Это некая альтернатива массиву, но куда более гибкая: порядок элементов в списке не связан с их расположением в памяти. Это порождает, например, то, что такие операции как поиск и удаление не связаны со сдвигами остальных элементов, однако все операции со списком являются исключительно последовательными - прямой доступ к элементам списка невозможен. Кратко можно почитать [[https://en.wikipedia.org/wiki/Linked_list|тут]]. Либо в какой-нибудь книге по структурам данных.
+Идеологически - линейный односвязный список это структура данных, представляющая собой список узлов, каждый их которого хранит какие-то данные и указатель на следующий элемент. Это некая альтернатива массиву, но куда более гибкая: порядок элементов в списке не связан с их расположением в памяти. Это порождает, например, то, что такие операции как поиск и удаление не связаны со сдвигами остальных элементов, однако все операции со списком являются исключительно последовательными - прямой доступ к элементам списка невозможен. Кратко можно почитать [[https://en.wikipedia.org/wiki/Linked_list|тут]]. Либо в какой-нибудь книге по структурам данных.
 **Реализация**
@@ Line 83: / Line 83: @@
   * Подумать как можно реализовать удаление n-го элемента списка.  (int remove(struct node *root, int n);)
+**Бинарное дерево поиска**
+Подробнее, например, [[https://en.wikipedia.org/wiki/Binary_search_tree|тут]]
+<code c treeNode.h>
+struct node
+{
+  int data; //полезные данные
+  struct node *left; //указатель на левого потомка
+  struct node *right; //указатель на правого потомка
+};
+</code>
+**Функции: **
+Реализуйте следующие функции:
+  * Вставка элемента в дерево
+  * Поиск элемента в дереве
+  * Определение высоты дерева
+  * Вывод элементов дерева в порядке их возрастания (ЛКП обход дерева)
+  * Вывод элементов дерева с отображением структуры. Например: <code>((5)10(15))20((25)30(35))</code>
+  * Удаление всех элементов дерева
+  * Удаление заданного элемента - рекомендую подумать и попробовать реализовать самостоятельно
+Для удобства, рекомендуется использовать отдельную функцию для создания узла:
+<code c createNode.h>
+struct node* createNode(int n, struct node *left, struct node *right)
+{
+	struct node *cur = malloc(sizeof(struct node));
+	cur->left = left;
+	cur->right = right;
+	cur->data = n;
+	return cur;
+}
+</code>
+** Пример на обзор txt файлов во вложенных папках:**
+<code c dir-list.c>
+#include <stdio.h>
+#include <string.h>
+#include <sys/types.h>
+#include <dirent.h>
+void printFile(const char *path, const int lvl);
+void dirTraveler(const char *startDir, const int lvl);
+int main()
+{
+	dirTraveler(".",0);
+	return 0;
+}
+void dirTraveler(const char *startDir, const int lvl)
+{
+    char path[1000];
+    strcpy(path, startDir);
+    DIR *dir=opendir(path);
+    if(dir)
+    {
+	struct dirent *de = readdir(dir);
+        while(de)
+        {
+			if(de->d_type == DT_REG && strstr(de->d_name,".txt"))
+			{
+				int path_len = strlen(path);
+                strcat(path, "/");
+                strcat(path, de->d_name);
+				printFile(path, lvl);
+                path[path_len] = '\0';
+			}
+            if(de->d_type == DT_DIR && 0!=strcmp(".", de->d_name) && 0!=strcmp("..", de->d_name))
+            {
+                int path_len = strlen(path);
+                strcat(path, "/");
+                strcat(path, de->d_name);
+                dirTraveler(path, lvl+1);
+                path[path_len] = '\0';
+            }
+           de = readdir(dir);
+        }
+    }
+    closedir(dir);
+}
+void printFile(const char *path, const int lvl)
+{
+	int i;
+	char s[100];
+	for(i=0;i<lvl;i++)
+		printf("\t");
+	printf("%s[\n", path);
+	FILE *f = fopen(path, "r");
+	if(f)
+	{
+		while(fgets(s,sizeof(s)/sizeof(char),f))
+		{
+			for(i=0;i<lvl+1;i++)
+				printf("\t");
+			printf("%s",s);
+		}
+		fclose(f);
+	}
+	for(i=0;i<lvl;i++)
+		printf("\t");
+	printf("]\n");
+}
+</code>

se.moevm.info

User Tools

Site Tools

Differences

Page Tools