شرح مادة CPCS 204 هياكل البيانات 1 - جامعة الملك عبدالعزيز

مادة CPCS 204، هياكل البيانات 1 (Data Structures I). هي الجسر بين “أعرف أكتب كود” و”أعرف أكتب كود فعال”. في خطة قسم علوم الحاسب بجامعة الملك عبدالعزيز، هذه المادة تُعتبر من أهم المواد اللي تبني عليها بقية مسارك الأكاديمي والمهني. أسئلة المقابلات الوظيفية في شركات التقنية الكبرى تدور بشكل كبير حول مواضيع هذه المادة.

المادة تبني على كل شيء تعلمته في CPCS 202 (أساسيات جافا) و CPCS 203 (البرمجة كائنية التوجه). لو أساسياتك في جافا و OOP قوية، CPCS 204 تصير ممتعة وليست مجرد مادة صعبة.

ليش مادة CPCS 204 مهمة جدا؟

• المقابلات الوظيفية: الجزء الأكبر من أسئلة المقابلات التقنية في الشركات الكبرى يدور حول هياكل البيانات، Linked Lists, Stacks, Queues, Trees
• أساس لمواد متقدمة: قواعد البيانات تستخدم أشجار B-Tree، أنظمة التشغيل تستخدم الطوابير، الشبكات تستخدم المكدسات
• كتابة كود فعال: تتعلم الفرق بين حل يشتغل في ثانية وحل يشتغل في ساعة، نفس المشكلة!
• التفكير التحليلي: المادة تعلّمك تحلل أي مشكلة وتختار هيكل البيانات المناسب

نظرة عامة على مادة CPCS 204

الأسابيع	الموضوع	المفاهيم الرئيسية
1-2	تحليل الخوارزميات (Algorithm Analysis)	Big-O, Big-Omega, Big-Theta
3-4	التكرار (Recursion)	حالة الأساس، الحالة التكرارية، أمثلة
5-6	القوائم المتصلة (Linked Lists)	Singly, Doubly، إضافة، حذف، تمرير
7-8	المكدسات (Stacks)	LIFO, push, pop, تطبيقات
9-10	الطوابير (Queues)	FIFO, enqueue, dequeue, circular queue
11-13	الأشجار (Trees)	Binary Tree, BST, traversals
14	خوارزميات الترتيب والبحث	Bubble, Selection, Insertion, Merge, Quick Sort
15	مراجعة شاملة	،

1. تحليل الخوارزميات، Algorithm Analysis & Big-O

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

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=1000
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

التكرار (Recursion) من أكثر المواضيع اللي تسبب إحباط لطلاب CPCS 204. لو حسيت إن الفكرة مو واضحة من أول مرة، هذا طبيعي جدا. المفتاح هو التتبع خطوة بخطوة.

2. التكرار، Recursion

كل ما تحاول تفهم الـ Recursion يضيع تركيزك؟ التكرار ببساطة: دالة تستدعي نفسها حتى توصل لحالة أساس (base case) وتتوقف.

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

كل دالة تكرارية لازم فيها:

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);
}

برج هانوي (Tower of Hanoi)

نقل n أقراص من عمود المصدر إلى عمود الهدف باستخدام عمود مساعد:

public static void towerOfHanoi(int n, char src, char dst, char tmp) {
    if (n == 1) {
        System.out.println("انقل 1 من " + src + " إلى " + dst);
        return;
    }
    towerOfHanoi(n - 1, src, tmp, dst);  // انقل n-1 للمساعد
    System.out.println("انقل " + n + " من " + src + " إلى " + dst);
    towerOfHanoi(n - 1, tmp, dst, src);  // انقل n-1 للهدف
}

القوائم المتصلة هي أول هيكل بيانات “حقيقي” تتعامل معه، التعامل مع الـ Nodes والمؤشرات يحتاج طريقة تفكير مختلفة عن المصفوفات. خذ وقتك وارسم كل عملية على ورقة.

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

المصفوفة حجمها ثابت. لو تبي تضيف عنصر لازم تنشئ مصفوفة جديدة. القائمة المتصلة تحل هذي المشكلة: حجمها ديناميكي ويتغير حسب الحاجة.

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

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

أولا، نعرّف الـ Node، كل عنصر يحمل بيانات ومؤشر للتالي:

class Node {
    int data;
    Node next;

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

الآن نبني القائمة المتصلة. الإضافة في البداية O(1)، نربط العنصر الجديد بالـ head:

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;
    }

الحذف من البداية O(1) وطباعة القائمة O(n):

    public void removeFirst() {
        if (head != null) head = head.next;
    }

    public void display() {
        Node cur = head;
        while (cur != null) {
            System.out.print(cur.data + " -> ");
            cur = cur.next;
        }
        System.out.println("null");
    }
}

القائمة المتصلة الثنائية (Doubly Linked List)

كل Node فيه مؤشرين: واحد للعنصر التالي وواحد للعنصر السابق.

class DNode {
    int data;
    DNode next, prev;

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

4. المكدسات، Stacks

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

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

نبني المكدس باستخدام مصفوفة. المتغير top يشير لآخر عنصر (-1 يعني فاضي):

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

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

push، إضافة عنصر فوق المكدس، وpop، إزالة آخر عنصر:

    public void push(int val) {
        arr[++top] = val;           // O(1)
    }

    public int pop() {
        return arr[top--];          // O(1)
    }

peek، رؤية بدون إزالة، وisEmpty، هل المكدس فاضي:

    public int peek() {
        return arr[top];            // O(1)
    }

    public boolean isEmpty() {
        return top == -1;
    }
}

تطبيقات المكدس

• التحقق من توازن الأقواس: {[()]} متوازنة، {[(])} غير متوازنة
• تحويل التعابير الحسابية: Infix to Postfix
• Undo في البرامج: كل عملية تتخزن في stack وآخر عملية تتراجع أولا
• استدعاء الدوال: الـ call stack في أي لغة برمجة

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 (ch == ')' && top != '(') return false;
            if (ch == ']' && top != '[') return false;
            if (ch == '}' && top != '{') return false;
        }
    }
    return stack.isEmpty(); // لازم فاضي
}

5. الطوابير، Queues

الطابور يشتغل بمبدأ FIFO، First In, First Out. أول عنصر يدخل هو أول عنصر يطلع. مثل طابور الكاشير: أول شخص يوصل هو أول شخص يُخدم.

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

نبني طابور دائري (Circular Queue) باستخدام مصفوفة. نستخدم % capacity عشان نرجع للبداية لما نوصل آخر المصفوفة:

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

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

enqueue، إضافة في النهاية:

    public void enqueue(int val) {
        rear = (rear + 1) % capacity;  // دائري
        arr[rear] = val;
        size++;                        // O(1)
    }

dequeue، إزالة من البداية:

    public int dequeue() {
        int val = arr[front];
        front = (front + 1) % capacity; // دائري
        size--;
        return val;                      // O(1)
    }

peek و isEmpty:

    public int peek() { return arr[front]; }
    public boolean isEmpty() { return size == 0; }
}

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

لاحظ في الكود أعلاه استخدمنا % capacity. هذا يخلي الطابور “دائري” بحيث لما نوصل لنهاية المصفوفة نرجع للبداية. بدون هذا، الطابور يضيّع مساحة كثيرة.

طابور الأولويات (Priority Queue)، مقدمة

في طابور الأولويات، العنصر اللي يطلع أولا هو العنصر ذو الأولوية الأعلى وليس بالضرورة اللي دخل أولا. جافا توفّر PriorityQueue جاهزة:

import java.util.PriorityQueue;

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(30);
pq.add(10);
pq.add(20);

System.out.println(pq.poll()); // 10 - الأصغر يطلع أول (Min-Heap)
System.out.println(pq.poll()); // 20
System.out.println(pq.poll()); // 30

الأشجار الثنائية وأشجار البحث من أهم المواضيع في المادة وأكثرها تكرارا في الاختبارات. لو تقدر تفهم BST وتتبع الـ Traversals، أنت في وضع ممتاز.

6. الأشجار، Trees

الشجرة هيكل بيانات هرمي، كل عنصر (Node) عنده أب واحد وممكن يكون عنده أبناء.

شجرة البحث الثنائية (Binary Search Tree، BST)

القاعدة: لكل Node، كل القيم في الشجرة اليسرى أصغر منه، وكل القيم في الشجرة اليمنى أكبر منه.

أولا، نعرّف الـ Node:

class BSTNode {
    int data;
    BSTNode left, right;

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

الإدخال، O(log n) في المتوسط. أصغر يروح يسار، أكبر يروح يمين:

class BST {
    BSTNode root;

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

البحث، O(log n) في المتوسط. نفس المنطق: أصغر يسار، أكبر يمين:

    public boolean search(BSTNode node, int val) {
        if (node == null) return false;
        if (val == node.data) return true;
        if (val < node.data) return search(node.left, val);
        return search(node.right, val);
    }
}

أنواع التمرير (Traversals)

ثلاث طرق لزيارة كل عناصر الشجرة، وهي من أهم مواضيع الاختبار:

Inorder (يسار، جذر، يمين)، يعطي الأرقام مرتبة تصاعديا في BST:

public void inorder(BSTNode node) {
    if (node == null) return;
    inorder(node.left);
    System.out.print(node.data + " ");
    inorder(node.right);
}

Preorder (جذر، يسار، يمين):

public void preorder(BSTNode node) {
    if (node == null) return;
    System.out.print(node.data + " ");
    preorder(node.left);
    preorder(node.right);
}

Postorder (يسار، يمين، جذر):

public void postorder(BSTNode node) {
    if (node == null) return;
    postorder(node.left);
    postorder(node.right);
    System.out.print(node.data + " ");
}

7. خوارزميات الترتيب، Sorting Algorithms

Bubble Sort، ترتيب الفقاعات

الفكرة: قارن كل عنصرين متجاورين وبدّل مكانهم لو مو مرتبين. كرّر حتى ما يصير تبديل.

public static void bubbleSort(int[] arr) {  // O(n²)
    int n = arr.length;
    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < n - i - 1; j++)
            if (arr[j] > arr[j + 1]) {
                int tmp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = tmp;
            }
}

Selection Sort، ترتيب الاختيار

الفكرة: في كل دورة، لاقي أصغر عنصر وحطه في مكانه الصحيح.

public static void selectionSort(int[] arr) {  // O(n²)
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        int min = i;
        for (int j = i + 1; j < n; j++)
            if (arr[j] < arr[min]) min = j;
        int tmp = arr[i]; arr[i] = arr[min]; arr[min] = tmp;
    }
}

Insertion Sort، ترتيب الإدراج

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

public static void insertionSort(int[] arr) {  // O(n²) أسوأ، O(n) أفضل
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i], j = i - 1;
        while (j >= 0 && arr[j] > key)
            arr[j + 1] = arr[j--];     // انقل لليمين
        arr[j + 1] = key;              // مكانه الصحيح
    }
}

Merge Sort، ترتيب الدمج

الفكرة: قسّم المصفوفة لنصفين، رتّب كل نصف، ثم ادمجهم.

الدالة الرئيسية تقسّم المصفوفة نصفين وتستدعي نفسها ثم تدمج، O(n log n) دائما:

public static void mergeSort(int[] arr, int left, int right) {
    if (left >= right) return;
    int mid = (left + right) / 2;
    mergeSort(arr, left, mid);        // رتّب اليسار
    mergeSort(arr, mid + 1, right);   // رتّب اليمين
    merge(arr, left, mid, right);     // ادمج
}

دالة الدمج تنسخ النصفين ثم تدمجهم بترتيب:

private static void merge(int[] arr, int l, int mid, int r) {
    int[] L = Arrays.copyOfRange(arr, l, mid + 1);
    int[] R = Arrays.copyOfRange(arr, mid + 1, r + 1);
    int i = 0, j = 0, k = l;
    while (i < L.length && j < R.length)
        arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
    while (i < L.length) arr[k++] = L[i++];
    while (j < R.length) arr[k++] = R[j++];
}

Quick Sort، الترتيب السريع

الفكرة: اختر عنصر محوري (pivot)، ضع كل العناصر الأصغر منه على يساره والأكبر على يمينه، ثم رتّب كل جهة.

الدالة الرئيسية، O(n log n) متوسط، O(n²) أسوأ حالة:

public static void quickSort(int[] arr, int low, int high) {
    if (low >= high) return;
    int p = partition(arr, low, high);
    quickSort(arr, low, p - 1);    // رتّب اليسار
    quickSort(arr, p + 1, high);   // رتّب اليمين
}

دالة التقسيم تختار آخر عنصر كمحور وتضع الأصغر يسارا والأكبر يمينا:

private static int partition(int[] arr, int low, int high) {
    int pivot = arr[high];  // المحور
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
        }
    }
    int tmp = arr[i+1]; arr[i+1] = arr[high]; arr[high] = tmp;
    return i + 1;
}

مقارنة خوارزميات الترتيب

الخوارزمية	أفضل حالة	متوسط	أسوأ حالة	مستقرة؟
Bubble Sort	O(n)	O(n²)	O(n²)	نعم
Selection Sort	O(n²)	O(n²)	O(n²)	لا
Insertion Sort	O(n)	O(n²)	O(n²)	نعم
Merge Sort	O(n log n)	O(n log n)	O(n log n)	نعم
Quick Sort	O(n log n)	O(n log n)	O(n²)	لا

8. خوارزميات البحث، Searching

البحث الخطي (Linear Search)

public static int linearSearch(int[] arr, int target) {  // O(n)
    for (int i = 0; i < arr.length; i++)
        if (arr[i] == target) return i;
    return -1;
}

البحث الثنائي (Binary Search)

يشتغل بس على مصفوفة مرتبة. ينصّ البيانات كل خطوة.

// 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;
}

أنواع أسئلة الاختبارات في CPCS 204

نصائح للاب العملي

• ابني هياكل البيانات بنفسك، لا تعتمد على المكتبات الجاهزة. في اللاب والاختبار، المطلوب تبني Node و LinkedList و Stack من الصفر
• ارسم قبل ما تكتب، ارسم القائمة المتصلة أو الشجرة على ورقة وتتبع العمليات يدويا، بعدين حوّلها لكود
• اختبر الحالات الخاصة، القائمة فاضية، عنصر واحد فقط، الإضافة في البداية vs النهاية

نصائح المذاكرة

ربط المادة بمسارك الأكاديمي

بعد CPCS 204، راح تستخدم هياكل البيانات في كل مكان:

• قواعد البيانات: تستخدم أشجار B-Tree للفهرسة
• أنظمة التشغيل: تستخدم الطوابير لجدولة العمليات
• الشبكات: تستخدم المكدسات في بروتوكولات الشبكة
• الخوارزميات المتقدمة: تبني على هياكل البيانات اللي تعلمتها هنا

لو تبي تراجع أساسيات جافا، ارجع لـ شرح مادة CPCS 202 برمجة 1. ولو تبي تراجع مفاهيم OOP، اقرأ شرح مادة CPCS 203 برمجة 2. ولمراجعة شاملة لهياكل البيانات، اقرأ دليلنا الشامل لهياكل البيانات.

هياكل البيانات هي أساس أسئلة المقابلات التقنية. لو تبي تبدأ تجهّز نفسك لسوق العمل، اقرأ دليلنا للاستعداد للمقابلات التقنية.

خلاصة

مادة CPCS 204 من أمتع مواد علوم الحاسب لما تفهمها صح. وكلمة “تفهمها” هي المفتاح الحقيقي.

أكثر خطأ يوقع فيه طلاب 204 هو إنهم يحفظون الكود. يحفظون خطوات Merge Sort، يحفظون كيف يكتبون LinkedList — وبعدين يطلع لهم سؤال مختلف قليلا في الاختبار ويتجمدون. الحفظ ما يجدي هنا. اللي يجدي هو إنك تفهم ليش كل هيكل بيانات يتصرف بالطريقة اللي يتصرف فيها.

نصيحة أخيرة: لو وقتك ضيّق قبل الاختبار، ركّز على ثلاثة أشياء: تتبع BST وكتابة الـ Traversals، تحليل Big-O للأكواد الشائعة، والفرق بين Stack وQueue مع أمثلة تطبيقية. هذي الثلاثة تغطي نص الاختبار تقريباً.