شرح مادة عال 212 (CSC 212) تراكيب البيانات - جامعة الملك سعود

مادة عال 212 (CSC 212)، تراكيب البيانات (Data Structures)، من اهم المواد في خطة قسم علوم الحاسب بجامعة الملك سعود. هذي المادة هي الفرق بين طالب يكتب كود “يشتغل” وطالب يكتب كود فعال ومنظم. لو سالت اي مبرمج محترف عن اهم مادة درسها في الجامعة، غالبا الجواب يكون: هياكل البيانات.

المادة تبني على كل شيء تعلمته في عال 111 و عال 113 (اساسيات جافا والبرمجة كائنية التوجه). لو اساسياتك في جافا قوية، عال 212 تصير ممتعة وتفتح لك ابواب كثيرة في بقية مسارك الاكاديمي.

ليش عال 212 مادة محورية في خطتك؟

مادة عال 212 ليست مجرد مادة تعدّيها وتنساها. هي اساس لـ 6 مواد متقدمة على الاقل:

• المقابلات الوظيفية: شركات التقنية الكبرى مثل Google و Microsoft و Amazon تبني اسئلة المقابلات حول هياكل البيانات. لو تبي تشتغل في شركة تقنية كبيرة، هذي المادة هي تذكرتك
• مواد متقدمة: عال 311 (تصميم الخوارزميات) و عال 361 (الذكاء الاصطناعي) و عال 227 (نظم التشغيل) كلها تعتمد مباشرة على عال 212
• كتابة كود فعال: تتعلم ليش حل بسيط يخلص في ثانية وحل ثاني يخلص في ساعة. نفس المشكلة بالضبط
• التفكير التحليلي: المادة تعلّمك تحلل المشكلة اول، ثم تختار هيكل البيانات المناسب

نظرة عامة على محتوى عال 212

الاسابيع	الموضوع	المفاهيم الرئيسية
1-2	تحليل الخوارزميات (Algorithm Analysis)	Big-O, Big-Omega, Big-Theta, ADTs
3	التكرار (Recursion)	حالة الاساس، حالة تكرارية، امثلة
4-5	القوائم المتصلة (Linked Lists)	Singly, Doubly، عمليات الاضافة والحذف
6	المكدسات (Stacks)	LIFO, push, pop, تطبيقات عملية
7	الطوابير (Queues)	FIFO, enqueue, dequeue, circular queue
8-9	الاشجار (Trees)	Binary Tree, BST, عمليات التمرير
10-11	اشجار AVL المتوازنة	الدورانات الاربع، الموازنة التلقائية
12	الاكوام (Heaps)	Min/Max Heap, HeapSort, Priority Queue
13	جداول الهاش (Hash Tables)	دوال الهاش، حل التصادمات
14	الرسوم البيانية (Graphs)	BFS, DFS, تمثيل الرسوم
15	خوارزميات الترتيب والمراجعة	Merge, Quick, Bubble, Selection Sort

1. تحليل الخوارزميات (Algorithm Analysis)

قبل ما تتعلم اي هيكل بيانات، لازم تفهم كيف تقيس كفاءة الكود. لو كتبت حلين لنفس المشكلة، كيف تعرف ايهم اسرع؟

Big-O Notation

Big-O يقيس اسوا حالة لاداء الخوارزمية مع زيادة حجم البيانات.

O(1)، وقت ثابت: عملية واحدة بغض النظر عن حجم البيانات.

// الوصول لعنصر بالفهرس - ثابت
public static int getFirst(int[] arr) {
    return arr[0];
}

O(n)، خطي: حلقة واحدة تمر على كل العناصر.

// جمع كل العناصر - خطي
public static int sum(int[] arr) {
    int total = 0;
    for (int i = 0; i < arr.length; i++)
        total += arr[i];
    return total;
}

O(n²)، تربيعي: حلقتين متداخلتين، كل عنصر يتقارن مع كل العناصر.

// طباعة كل الازواج - تربيعي
public static void printPairs(int[] arr) {
    for (int i = 0; i < arr.length; i++)
        for (int j = 0; j < arr.length; j++)
            System.out.println(arr[i] + ", " + arr[j]);
}

O(log n)، لوغاريتمي: ينصّف البيانات كل خطوة مثل البحث الثنائي.

public static int binarySearch(int[] arr, int target) {
    int low = 0, high = arr.length - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

جدول مقارنة التعقيدات

التعقيد	الاسم	مثال	n = 1,000
O(1)	ثابت	الوصول بالفهرس	1
O(log n)	لوغاريتمي	البحث الثنائي	~10
O(n)	خطي	البحث الخطي	1,000
O(n log n)	خطي لوغاريتمي	Merge Sort	~10,000
O(n²)	تربيعي	Bubble Sort	1,000,000

2. التكرار (Recursion)

التكرار من اكثر المواضيع اللي يحس فيها الطالب بالضياع اول مرة. لو حسيت كذا، طبيعي جدا. الفكرة بسيطة: دالة تستدعي نفسها حتى توصل لحالة اساس وتتوقف.

المكونات الاساسية

كل دالة تكرارية فيها شيئين:

1. Base Case (حالة الاساس): متى تتوقف الدالة
2. Recursive Case (الحالة التكرارية): الدالة تستدعي نفسها مع مدخل اصغر

public static int factorial(int n) {
    if (n <= 1) return 1;           // حالة الاساس
    return n * factorial(n - 1);    // حالة تكرارية
}
// factorial(4) = 4 * 3 * 2 * 1 = 24

متتالية فيبوناتشي

كل رقم = مجموع الرقمين اللي قبله: 0, 1, 1, 2, 3, 5, 8, 13, ...

public static int fibonacci(int n) {
    if (n == 0) return 0;      // حالة اساس
    if (n == 1) return 1;      // حالة اساس
    return fibonacci(n - 1) + fibonacci(n - 2);
}

3. القوائم المتصلة (Linked Lists)

القوائم المتصلة هي اول هيكل بيانات “حقيقي” تتعامل معه في عال 212. الانتقال من التفكير بالمصفوفات الى التفكير بالعقد (Nodes) والمؤشرات يحتاج وقت. خذ وقتك وارسم كل عملية على ورقة.

القائمة الاحادية (Singly Linked List)

كل عنصر (Node) فيه: بيانات + مؤشر للعنصر التالي.

class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

الاضافة في البداية: O(1):

class LinkedList {
    Node head;

    public void addFirst(int data) {
        Node n = new Node(data);
        n.next = head;  // الجديد يشير للقديم
        head = n;       // الجديد يصير الاول
    }
}

الاضافة في النهاية: O(n):

public void addLast(int data) {
    Node n = new Node(data);
    if (head == null) { head = n; return; }
    Node cur = head;
    while (cur.next != null) cur = cur.next;
    cur.next = n;  // ربط بالاخير
}

مقارنة Array مع Linked List

العملية	Array	Linked List
الوصول بالفهرس	O(1)	O(n)
اضافة في البداية	O(n)	O(1)
اضافة في النهاية	O(1)*	O(n)
حذف من البداية	O(n)	O(1)

*مع ArrayList، الاضافة في النهاية O(1) amortized.

لو تبي تفهم اساسيات جافا اللي تبني عليها هذي المادة، راجع دليل جافا للمبتدئين.

4. المكدسات (Stacks)

المكدس يشتغل بمبدا LIFO: Last In, First Out. تخيّل كومة صحون: اخر صحن تحطه هو اول صحن تاخذه.

البناء والعمليات الاساسية

class Stack {
    private int[] arr;
    private int top = -1;

    public Stack(int capacity) {
        arr = new int[capacity];
    }

    public void push(int val) { arr[++top] = val; }
    public int pop() { return arr[top--]; }
    public int peek() { return arr[top]; }
    public boolean isEmpty() { return top == -1; }
}

تطبيق: التحقق من توازن الاقواس

public static boolean isBalanced(String expr) {
    Stack stack = new Stack(expr.length());
    for (char ch : expr.toCharArray()) {
        if (ch == '(' || ch == '[' || ch == '{')
            stack.push(ch);
        else if (ch == ')' || ch == ']' || ch == '}') {
            if (stack.isEmpty()) return false;
            char top = (char) stack.pop();
            if (!matches(top, ch)) return false;
        }
    }
    return stack.isEmpty();
}

تطبيقات المكدس: التحقق من الاقواس، تحويل Infix الى Postfix، زر Undo في البرامج، و call stack في استدعاء الدوال.

5. الطوابير (Queues)

تخيّل طابور الكاشير في السوبرماركت: اول واحد يوصل هو اول واحد يُخدم. هذا بالضبط مبدا FIFO (First In, First Out) اللي يشتغل عليه الطابور في البرمجة.

الطابور الدائري (Circular Queue)

نستخدم % capacity عشان لما نوصل اخر المصفوفة نرجع للبداية. بدون هذا الطابور يضيّع مساحة:

class Queue {
    private int[] arr;
    private int front = 0, rear = -1;
    private int size = 0, capacity;

    public Queue(int cap) {
        capacity = cap;
        arr = new int[cap];
    }

    public void enqueue(int val) {
        rear = (rear + 1) % capacity;
        arr[rear] = val;
        size++;
    }

    public int dequeue() {
        int val = arr[front];
        front = (front + 1) % capacity;
        size--;
        return val;
    }
}

6. الاشجار الثنائية (Binary Trees & BST)

الاشجار من اهم المواضيع في عال 212 وتاخذ وقت كبير في المنهج. كل عقدة (Node) فيها بيانات + مؤشر يسار + مؤشر يمين.

بناء الشجرة الثنائية

class TreeNode {
    int data;
    TreeNode left, right;

    public TreeNode(int data) {
        this.data = data;
    }
}

شجرة البحث الثنائية (BST)

في BST، كل عقدة: العناصر الاصغر على اليسار، والعناصر الاكبر على اليمين. هذا يخلي البحث O(log n) في الحالة المثالية.

الاضافة في BST:

public TreeNode insert(TreeNode root, int val) {
    if (root == null) return new TreeNode(val);
    if (val < root.data)
        root.left = insert(root.left, val);
    else
        root.right = insert(root.right, val);
    return root;
}

طرق التمرير (Traversals)

ثلاث طرق اساسية لزيارة كل عقد الشجرة:

// Inorder: يسار → جذر → يمين (يطلع مرتب!)
void inorder(TreeNode node) {
    if (node == null) return;
    inorder(node.left);
    System.out.print(node.data + " ");
    inorder(node.right);
}

// Preorder: جذر → يسار → يمين
// Postorder: يسار → يمين → جذر

7. اشجار AVL المتوازنة (AVL Trees)

كثير من الطلاب يعتبرون اشجار AVL اصعب موضوع في عال 212. الدورانات الاربع تحتاج تركيز وتمرين. بس لما تفهم المنطق ورا كل دوران، الموضوع يصير واضح.

المشكلة اللي تحلها AVL

لو ادخلت عناصر مرتبة في BST عادي (مثلا 1, 2, 3, 4, 5) الشجرة تصير مثل Linked List وتضيع ميزة O(log n). اشجار AVL تحافظ على التوازن تلقائيا.

قاعدة التوازن

Balance Factor = ارتفاع اليسار - ارتفاع اليمين

لو الـ Balance Factor صار اكبر من 1 او اصغر من -1، الشجرة تحتاج دوران.

الدورانات الاربع

الحالة	متى تحصل	الحل
LL (يسار-يسار)	BF > 1 والعنصر الجديد على يسار اليسار	دوران يمين واحد
RR (يمين-يمين)	BF < -1 والعنصر الجديد على يمين اليمين	دوران يسار واحد
LR (يسار-يمين)	BF > 1 والعنصر الجديد على يمين اليسار	دوران يسار ثم يمين
RL (يمين-يسار)	BF < -1 والعنصر الجديد على يسار اليمين	دوران يمين ثم يسار

دوران يمين بسيط (Right Rotation):

TreeNode rightRotate(TreeNode y) {
    TreeNode x = y.left;
    TreeNode T2 = x.right;
    x.right = y;       // y ينزل لليمين
    y.left = T2;       // الفرع الوسط ينتقل
    return x;          // x يصير الجذر الجديد
}

دوران يسار بسيط (Left Rotation):

TreeNode leftRotate(TreeNode x) {
    TreeNode y = x.right;
    TreeNode T2 = y.left;
    y.left = x;        // x ينزل لليسار
    x.right = T2;      // الفرع الوسط ينتقل
    return y;           // y يصير الجذر الجديد
}

8. الاكوام (Heaps و Priority Queue)

الـ Heap شجرة ثنائية كاملة حيث كل عقدة اب اكبر (Max Heap) او اصغر (Min Heap) من اولادها.

Min Heap vs Max Heap

• Min Heap: الجذر دائما اصغر عنصر، مفيد لايجاد الحد الادنى بسرعة
• Max Heap: الجذر دائما اكبر عنصر

العمليات الاساسية

العملية	التعقيد	الوصف
insert	O(log n)	اضف في الاخير ثم sift up
extractMin/Max	O(log n)	احذف الجذر ثم sift down
peek	O(1)	شوف الجذر بدون حذف
heapify	O(n)	حوّل مصفوفة لـ heap

HeapSort

HeapSort يستغل خاصية الـ Heap لترتيب البيانات في O(n log n):

1. ابني Max Heap من المصفوفة
2. استخرج الجذر (اكبر عنصر) وحطه في الاخير
3. اعد بناء الـ Heap
4. كرر حتى تخلص

جافا توفّر PriorityQueue جاهزة اللي هي Min Heap:

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(30);
pq.add(10);
pq.add(20);
System.out.println(pq.poll()); // 10 (الاصغر)
System.out.println(pq.poll()); // 20

9. جداول الهاش (Hash Tables)

جداول الهاش تعطيك بحث واضافة وحذف في O(1) في الحالة المثالية، وهذا يخليها من اسرع هياكل البيانات.

كيف تشتغل؟

1. دالة الهاش (Hash Function): تاخذ المفتاح وتحوله لرقم (فهرس في مصفوفة)
2. المصفوفة: تخزن القيم في الفهرس الناتج

int hash(String key, int tableSize) {
    int hashVal = 0;
    for (char ch : key.toCharArray())
        hashVal = (hashVal * 31 + ch) % tableSize;
    return hashVal;
}

مشكلة التصادم (Collision)

لما مفتاحين مختلفين يعطون نفس الفهرس، لازم نتعامل مع التصادم:

1. التسلسل (Chaining): كل خانة فيها Linked List، والعناصر المتصادمة تتسلسل.

2. العنونة المفتوحة (Open Addressing): لو الخانة مشغولة، ابحث عن خانة فاضية:

• Linear Probing: جرّب الخانة التالية (+1, +2, +3…)
• Quadratic Probing: جرّب بمربعات (+1, +4, +9…)
• Double Hashing: استخدم دالة هاش ثانية

الطريقة	الميزة	العيب
Chaining	بسيطة، ما تمتلئ	تحتاج مساحة اضافية للقوائم
Linear Probing	كاش ودي (Cache friendly)	تكتل (Clustering)
Double Hashing	توزيع افضل	اعقد في التنفيذ

10. الرسوم البيانية (Graphs)

الرسوم البيانية (Graphs) تمثّل علاقات بين عناصر: شبكات التواصل الاجتماعي، خرائط الطرق، شبكات الحاسب كلها تُمثّل كرسوم بيانية. لو تبي تعمق اكثر في شبكات الحاسب، راجع اساسيات شبكات الحاسب.

المصطلحات الاساسية

• Vertex (رأس): عقدة في الرسم
• Edge (حافة): خط يربط بين رأسين
• Directed / Undirected: هل الاتجاه مهم او لا
• Weighted / Unweighted: هل الحواف لها اوزان

تمثيل الرسوم

مصفوفة الجوار (Adjacency Matrix): جدول n×n حيث matrix[i][j] = 1 لو في حافة.

قائمة الجوار (Adjacency List): كل رأس عنده قائمة بالرؤوس المجاورة، اوفر في المساحة.

// قائمة جوار باستخدام ArrayList
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++)
    adj.add(new ArrayList<>());
adj.get(0).add(1);  // حافة من 0 الى 1
adj.get(1).add(0);  // حافة من 1 الى 0

خوارزميات التمرير

BFS (البحث بالعرض): يزور كل الجيران اولا ثم ينتقل للمستوى التالي، ويستخدم Queue.

void bfs(List<List<Integer>> adj, int start) {
    boolean[] visited = new boolean[adj.size()];
    Queue<Integer> q = new LinkedList<>();
    visited[start] = true;
    q.add(start);
    while (!q.isEmpty()) {
        int v = q.poll();
        System.out.print(v + " ");
        for (int neighbor : adj.get(v)) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.add(neighbor);
            }
        }
    }
}

DFS (البحث بالعمق): يروح لاعمق نقطة ثم يرجع، ويستخدم Stack او التكرار (Recursion).

الخوارزمية	هيكل البيانات المستخدم	الاستخدام
BFS	Queue	اقصر مسار، مستويات
DFS	Stack / Recursion	فحص الاتصال، الدورات

11. خوارزميات الترتيب (Sorting Algorithms)

عال 212 تغطي عدة خوارزميات ترتيب ومهم تعرف متى تستخدم كل وحدة:

الخوارزمية	التعقيد (متوسط)	التعقيد (اسوا)	مستقرة؟	ملاحظة
Bubble Sort	O(n²)	O(n²)	نعم	ابسط خوارزمية، للتعليم فقط
Selection Sort	O(n²)	O(n²)	لا	تختار الاصغر كل مرة
Insertion Sort	O(n²)	O(n²)	نعم	ممتازة للبيانات شبه المرتبة
Merge Sort	O(n log n)	O(n log n)	نعم	تقسيم ودمج، مضمونة
Quick Sort	O(n log n)	O(n²)	لا	الاسرع عمليا في اغلب الحالات
Heap Sort	O(n log n)	O(n log n)	لا	تستخدم Heap، بدون مساحة اضافية

لفهم اعمق لهذي الخوارزميات مع امثلة تفصيلية، راجع دليل هياكل البيانات والخوارزميات.

اخطاء شائعة في عال 212

1. نسيان Base Case في Recursion: يسبب StackOverflowError مباشرة
2. عدم التحقق من null: قبل الوصول لـ node.next او node.left لازم تتاكد مو null
3. الخلط بين Stack و Queue: LIFO مقابل FIFO، تاكد من الفرق
4. حفظ دورانات AVL بدون فهم: في الاختبار يغيّرون الارقام وتضيع لو ما فهمت المنطق
5. الخلط بين Chaining و Open Addressing: اعرف متى تستخدم كل وحدة ومميزات وعيوب كل طريقة
6. تجاهل التعقيد: لا تكتفي بكود “يشتغل”، لازم تعرف تعقيده
7. عدم الرسم على الورقة: الاشجار والقوائم المتصلة والرسوم البيانية لازم ترسمها عشان تفهمها

ربط عال 212 بمسارك الاكاديمي

عال 212 بوابة لمواد كثيرة في خطتك بجامعة الملك سعود:

• عال 311، تصميم وتحليل الخوارزميات: تبني مباشرة على هياكل البيانات وتحليل التعقيد
• عال 227، نظم التشغيل: الطوابير لجدولة العمليات، الاشجار لنظام الملفات
• عال 361، الذكاء الاصطناعي: الرسوم البيانية والبحث (BFS/DFS) اساسية في خوارزميات الذكاء الاصطناعي
• عال 380، قواعد البيانات: اشجار B-Tree وجداول الهاش اساسية في تصميم قواعد البيانات

لو تبي نظرة عامة على مجال هندسة البرمجيات وكيف ترتبط هذي المواد ببعض، راجع اساسيات هندسة البرمجيات.

خلاصة

عال 212 مادة تحتاج تمرين عملي مستمر. القراءة وحدها ما تكفي. كل هيكل بيانات تتعلمه (من القوائم المتصلة الى اشجار AVL الى الرسوم البيانية) يفتح لك باب لفهم كيف البرامج الحقيقية تشتغل. ركّز على الرسم والتطبيق العملي وحل اسئلة الاختبارات السابقة، وان شاء الله تعدّي المادة بتقدير ممتاز.