منتدى طلاب جامعة السودان المفتوحة
اسرة منتدى طلاب جامعة السودان المفتوحة تتمنى لكم اقامة طيبة برفقتها نرجو الدخول اذا كنت عضوا او التسجيل او زر اخفاء للزوار

منتدى طلاب جامعة السودان المفتوحة

المدير العام المنتدى : وليد عبدالوهاب احمد
 
الرئيسيةالتسجيلدخول
شاطر | 
 

 هياكـل البيانـات

استعرض الموضوع السابق استعرض الموضوع التالي اذهب الى الأسفل 
كاتب الموضوعرسالة
وليد عبدالوهاب احمد



عدد المساهمات: 252
تاريخ التسجيل: 12/11/2010
العمر: 32

مُساهمةموضوع: هياكـل البيانـات   الثلاثاء مايو 24, 2011 12:16 pm

هياكـل البيانـات
لوحدة الأولى

النداء الذاتي والمؤشرات

(خلفية برمجية)
المقدمة

تمهيد

عزيزي الدارس،

مرحبا بك إلى هذه الوحدة ، الوحدة الأولى

تحتوي هذه الوحدة على قسمين رئسين القسم الأول منها يتناول مفهوم النداء الذاتي للدوال وهو كيفية قيام الدالة بتكرار نفسها أو استدعاء الدالة لنفسها مجدداّ ، حيث ساعد استخدم النداء الذاتي للدوال في حل كثير من المسائل الرياضية بكثرة وذلك لكونها أنسب طريقة برمجية للتعامل مع جمع وضرب المتسلسلات وترتيبها.

القسم الثاني يتناول مفهوم المؤشرات وفيه نوضّح كيفية الوصول للقيّم مباشرة أو من خلال المؤشر الذي يؤشر بطريقة مباشرة إلي القيمة أي من خلال عنوان المتغّير.

وكذلك يشير القسم الثاني لكيفية إدارة الذاكرة واستخدام مساحة أكبر من تلك التي كانت تستخدمها المصفوفات.

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


1 . النداء الذاتي للدوال Recursion function

النداء الذاتي للدالة هو أن تعيد الدالة تكرار نفسها أو تستدعي الدالة نفسها مجدداّ حيث يتم استدعاءها داخل الدالة بنفس اسم الدالة إلى أن يتحقق شرط التوقف للدالة المستدعاة وهنالك بعض الملاحظات التي يجب أن تذكر وهي:

§ تستدعى الدالة نفسها داخل الدالة بواسطة معاملات مختلفة في كل مرة يتم الاستدعاء.

§ في النداء الذاتي للدوال إذا لم يتم وضع شرط التوقف فستستدعي الدالة نفسها إلى ما لا نهاية function will call itself forever

§ عند اكتمال آخر استدعاء للدالة يقوم المترجم بإرجاع كل القيم التي نتجت عند الاستدعاء الذاتي وتبدأ بآخر قيمة نتجت عند الاستدعاء حتى أول قيمة.

استخدم النداء الذاتي للدوال في حل كثير من المسائل الرياضية بكثرة وذلك لكونها أنسب طريقة برمجياً للتعامل مع جمع وضرب المتسلسلات وترتيبها.

مثال (1)

اكتب برنامجاً لإيجاد مضروب أي عدد صحيح N وذلك من خلال

1. استخدام الدوال العادية

2. استخدام النداء الذاتي

1. من خلال استخدام الدوال العادية

#include

#include

int fact(int n)

{

int F=1;

for (int i=n;i>=1;)

F*=i--;

return F;

}

void main()

{

int N;

cout<<"\nEnter the value of N : ";

cin>>N;

cout<<"Factorial of "<
getch();

}

2. من خلال استخدام النداء الذاتي للدوال

#include

#include

int fact(int n)

{

if (n <=1)

return 1;

else

return (n*fact(n-1));

}

void main()

{

int N;

cout<<"\nEnter the value of N : ";

cin>>N;

cout<<"Factorial of "<
getch();

}

وعليه يكون إخراج البرنامج على النحو التالي:




يتم إرسال العدد المراد إيجاد المضروب له إلى الدالة والتي بدورها تستقبله في متغير من النوع intn) ) داخل الدالة, إذا كان هذا العدد أصغر أو يساوي واحداً فإن الدالة ستعيد قيمة المضروب (1) إما إذا كان أكبر من الواحد فإنها ستعيد حاصل ضرب

(n*fact(n-1))

وبما إننا ذكرنا اسم الدالة مرة ثانية داخل الدالة نفسها لكن مع ملاحظة أن القيمة المرسلة إلى الدالة هذه المرة أقل من القيمة المرسلة إلى الدالة من البرنامج الرئيس فسيتم استدعاء الدالة مرة أخرى وهكذا إلي أن ترسل الدالة قيمة واحد إلي الدالة نفسها وعندئذ يتحقق شرط التوقف.

مثال (2)

اكتب برنامجاً لحساب فابونانسي Fibonacci number وذلك من خلال العلاقة التالية

F(0) = 0

F(1) = 1

F = F(n-1) + F(n-2)

#include

#include

int fib(int n)

{

if (n==0||n==1)

return n;

else

return fib(n-1)+fib(n-2);

}

void main()

{

int N;

cout<<"\nEnter the value of N : ";

cin>>N;

cout<<"Fibonacci of "<
getch();

}

نلاحظ عند استدعاء الدالة في البرنامج الرئيس من خلال عبارة Fib(N) نرسل للدالة العدد N وتستقبله في المتغير n ثم بعد ذلك يتم اختبار الشرط هل هذا العدد يساوى 0 أو 1 فإذا كانت الإجابة بنعم فان الدالة سوف تعيد هذه القيمة إلى البرنامج الرئيس أما إذا كانت اكبر منهم فإنها سوف تستدعي الدالة مرة أخرى من خلال التعبير التالي:

return fib(n-1)+fib(n-2);

هنا الاستدعاء الذاتي للدالة قد تم أكثر من مرة وفى كل مرة بمعامل مختلف عن الأخرى. وعلية يكون إخراج البرنامج علي النحو التالي:

2 . المؤشرات Pointers

1.2 مقدمة عن المؤشرات

المؤشرات هي عبارة عن متغيرات تحتوي علي عناوين في الذاكرة كقيم مخزنة ضمنها فالمتغير العادي عادة يحتوي علي قيمة مخزنة مباشرة ضمنه بينما المؤشر يتضمن عنواناً في الذاكرة لمتغير يحتوي علي قيمة وعلية يمكن الوصول إلي هذه القيمة من خلال المتغير ويسمي بالوصول المباشر للقيمة أو من خلال المؤشر الذي يؤشر بطريقة مباشرة إلي القيمة أي من خلال عنوان المتغير والشكل رقم (1) يبين طريقة الوصول المباشر وغير المباشر لقيم المتغيرات.



الشكل رقم ( 1 ) طريقة الوصول المباشر والغير مباشر لقيمة المتغير Var .

كما هو معروف لدينا أن لكل بايت في الذاكرة عنواناً هو عبارة عن أرقام وأن كل برنامج عند وضعه في الذاكرة يحتل نطاقاً معيناً من تلك العناوين ولهذا لكل متغير ودالة في البرنامج عنوان (1) . يمكن معرفة العنوان الذي يحتله متغير ما في لغة ++C باستعمال عامل العنوان & .

مثال (3)

اكتب برنامجاً يعرف 3 متغيرات ويعطيها القيم 11, 22, 33 على التوالي ثم يعرض عناوينها.


#include

#include

void main()

{

int var1 =11;

int var2 =22;

int var3 =33;

cout<
<
<
getch();

}

إخراج البرنامج:






تعتمد العناوين التي تحتلها متغيرات البرنامج على عدة أمور منها:

§ الجزء من الذاكرة الذي يحتله البرنامج.

§ حجم نظام التشغيل.

§ وجود برامج أخرى تعمل في الذاكرة أم لا.

كل هذه الأسباب قد تؤدي للاختلاف في نتائج البرنامج عند التنفيذ من شخص لآخر ونلاحظ أيضاً أن العناوين تكتب بالتدوين الست عشري والذي يشار إليه ب 0 x الظاهرة قبل كل رقم كل عنوان في إخراج البرنامج أعلاه.

يعتبر عرض عنوان المتغير في الذاكرة ليس مفيداً وإنما المفيد هو القيمة التي يحتلها هذا العنوان لهذا نلجأ إلي تعريف متغيرات تكون قادرة علي تخزين قيم العناوين وهذا المتغير يسمى متغير مؤشر أو مؤشراً. إن المؤشر ليس كالمتغير الذي يتم تخزين عنوانه انه مؤشر إلى النوع int وهو في الأصل ليس من النوع int .

مثال (4)

أعد كتابة البرنامج الموجود بالمثال رقم (3) ليعطي عنوانين المتغيرات من خلال المؤشرات

#include

#include

void main()

{

int var1 =11;

int var2 =22;

int var3 =33;

int* ptr;

ptr = &var1;

cout<
ptr = &var2;

cout<
ptr = &var3;

cout<
getch();

}

إخراج البرنامج يكون علي النحو التالي:




وهو يشبه إخراج البرنامج الموجودة بالمثال رقم (3) ونلاحظ في البرنامج أنه تم الإعلان عن متغير مؤشر من خلال التعبير

int* ptr ;

تعرف تلك العبارة المتغير ptr كمؤشر إلى النوع int وبعبارة أخرى نقول إن هذا المتغير يمكنه تخزين عناوين متغيرات عددية صحيحة. وبالتالي يمكن أن نعلن عن مؤشرات من أنواع أخري مثل التعابير التالية:

char* cptr ; //pointer to char

int* iptr; //pointer to int

float* fptr; //pointer to float

أن كتابة النجمة قريبة من النوع أو من المؤشر يعد أمر غير مهم بالنسبة للمترجم لكن وضعها بالقرب من النوع يساعد على التشديد أنها جزء من النوع وليست جزء من الاسم نفسه. العبارة التالية توضح تعريف أكثر من مؤشر في نفس السطر.

int *ptr1, *ptr2, *ptr3;

يمكن أن يخزن المؤشر عنوان أي متغير من أي نوع لكن يجب إعطائه قيمة ما وإلا سيشير المؤشر إلى عنوان لا يرغب المستخدم في الإشارة إليه، كالإشارة إلى شفرة البرنامج أو إلى نظام التشغيل ويمكن أن تؤدي قيم المتغيرات المتشردة إلى تعطل النظام كما أن اكتشافها أمر صعب لأن المترجم لا يعطي تنيبه حولها.

في حالة عدم معرفة اسم المتغير ولكن معرفة عنوانه فيمكن الوصول إلى محتوياته. والتركيب النحوي الخاص بمعرفة قيمة المتغير من خلال معرفة عنوانه بدلاً من اسمه تتضح في البرنامج التالي:

تدريب (2)

مثال (5)

اكتب برنامجاً يستعمل مؤشر لتعيين قيمة إلى متغير ثم تعيين تلك القيمة إلى متغير آخر:

#include

#include

void main()

{

int var1, var2;

int* ptr ;

ptr =&var1;

*ptr = 37;

var2 = *ptr;

cout <
getch();

}

تقويم ذاتي

تدريب (3)

2.2 إدارة الذاكرة بواسطة delete و new

قد رأينا أن أكثر الآليات التي تستخدم لتخزين عدد كبير من المتغيرات أو الكائنات هي المصفوفة وقد صاحب استعمال المصفوفات بعض من القصور يتمثل في حجم المصفوفة ثابت في معظم الأحيان وقد لا يعرف المستخدم كمية الذاكرة التي يحتاج إليها أثناء تشغيل البرنامج لهذا وفرت لغة ++ C أسلوباً لتوفّر مساحة من الذاكرة وذلك من خلال العامل new .

1.2.2 العامل new

تزود لغة ++ C أسلوباً آخر للحصول على مساحة من الذاكرة يخصص هذا العامل ذاكرة ذات حجم معين ويعيد مؤشراً. البرنامج التالي يبين استعمال العامل new للحصول على ذاكرة لسلسلة :


#include

#include

void main()

{

char* str=“computer science”;

int len=strlen(str) ;

char* ptr;

ptr=new char [len +1];

strcpy (ptr,str) ;

cout<<“ptr =“<
delete[ ] ptr;

getch();

}


الكلمة الأساسية new يليها نوع المتغيرات التي سيتم تخصيصها وعدد تلك المتغيرات ونقوم هنا بتخصيص المتغيرات من نوع char ونحتاج len+1 حيث تساوي طول السلسلة str وهو أمر معروف من خلال الدالة المكتبية strcpy() . يعيد العامل new مؤشراً يشير إلى بداية قطعة الذاكرة ويحصل على الذاكرة ديناميكياً أي أثناء تنفيذ البرنامج

2.2.2 العامل delete

يرافق العامل new العامل delete يعيد تحرير الذاكرة إلى نظام التشغيل. العبارة التالية تعيد إلى النظام كمية الذاكرة التي يشير إليها المؤشر ptr .


Delete [ ] ptr;




1 ) العناوين في الأساس مرقمة من أعلى إلي أسفل أي تظهر بترتيب تنازلي لأن المتغيرات التلقائية يتم تخزينها في المكدس الذي ينمو إلى الأسفل في الذاكرة. أما لو كانت المتغيرات خارجية (معرفة خارج أي دالة) لحصلت المتغيرات على عناوين تصاعدية لأنه يتم تخزين المتغيرات الخارجية في الذاكرة التكويمية.
الرجوع الى أعلى الصفحة اذهب الى الأسفل
وليد عبدالوهاب احمد



عدد المساهمات: 252
تاريخ التسجيل: 12/11/2010
العمر: 32

مُساهمةموضوع: رد: هياكـل البيانـات   الثلاثاء مايو 24, 2011 1:06 pm

هذه مجموعه من التعريفات المهمه في ماده هياكل بيانات


Data
Facts without meaning
حقائق مجرده من المعنى

************************************************** ********************
Data Structure
Objects we generate to store data in them, and algorithm to process these data
كائن احنا ننشئه عشان نخزن بيانات فيه, و خوارزميه عشان تشغل هذه البيانات
************************************************** ************
Algorithm
Non finite set of instruction that if followed, it will perform particular task
مجموعه غير محدوده من التعليمات التي اذا تتبعت حتعمل عمليه معينه
************************************************** ************
Program
Is a non empty finite of instruction written with specific language
تعليمات محدوده غير فاضيه مكتوبه بلغه معينه
************************************************** ********************
Robustness
The program be strong …eg x=square root of y ….(y must be >0)…this condition to make the program better.
انه نعمل شروط واشياء عشان البرنامج يكون قوي
************************************************** ***********
stack
is a list in which all insertions and deletions are made
at one end, called the top. The last element to be inserted into
the stack will be the first to be removed. Thus stacks are
sometimes referred to as Last In First Out (LIFO) lists.
Application of Stacks
e.g.
Evaluation of arithmetic expressions:
Usually, arithmetic expressions are written in infix notation, e.g.
A+B*C
Another e.g. : Reversing word order
STACKS _ SKCATS
************************************************** ************
Abstract Data Type
- An Abstract Data Type is some sort of data together
with a set of functions (interface) that operate on the data.
- Access is only allowed through that interface.
- Implementation details are ‘hidden’ from the user.
************************************************** *************
Queue
is an ordered collection of items from which items may be
deleted at one end (called the front of the queue) and into which items may
be inserted at the other end (the rear of the queue).
Application of Queues
In a multitasking operating system, the CPU time is shared between multiple
processes. At a given time, only one process is running, all the others are
‘sleeping’. The CPU time is administered by the scheduler. The scheduler keeps
all current processes in a queue with the active process at the front of the queue.
************************************************** **********
Circular Queue

An implementation of a bounded queue using an array.
************************************************** ***********
Double Ended Queue
Double-ended queues are like vectors, except that they allow fast insertions and deletions at the beginning (as well as the end) of the container.
************************************************** *************
Link List
A linked list is called so because each of items in the list is a part of a structure, which is linked to the structure containing the next item. This type of list is called a linked list since it can be considered as a list whose order is given by links from one item to the next.
************************************************** ************
Double Link List

A data structure in which each element contains pointers to the next and previous elements in the list, thus forming a bidirectional linear list



OR
A linked list where each item contains links to both its predecessor and its successor. This makes it possible to traverse the list in either direction. The flexibility given by double linking must be offset against the overhead of the storage and the setting and resetting of the extra links involved when items are inserted or removed.
************************************************** *************
Trees

A data structure accessed beginning at the root node. Each node is either a leaf or an internal node. An internal node has one or more child nodes and is called the parent of its child nodes. All children of the same node are siblings. Contrary to a physical tree, the root is usually depicted at the top of the structure, and the leaves are depicted at the bottom
************************************************** *************
Q-What are the draw backs of using sequential storage to represent stacks and queue?
ما هي العوائق للذاكره عند استخدام الستاك او الكيو؟
Ans- one major drawback is that a fixed amount of storage remains allocated to the stack or queue even when the structure is actually using smaller amount or possibly no storage at all. Furthermore, no more than fixed amount of storage maybe allocated, thus introducing the possibility of overflow.
واحد من العوائق انه القيمه المحدده والثابته للتخزين و تظل في الذاكره , و ومش اكثر من الرقم المحدد نقدر نخزن فيه فلهذا كل ما حندخل و قدو معبى حتحصل مشكله الoverflow انه قدو زياده
************************************************** *************
Q- Why we use circular queue?

In a normal Queue when queue becomes full we can not add more items so
following items are lost. But in a circular queue when queue becomes full
it will start overwriting the items from beginning so that new items/data won't
waste. It is logical also because it is assumed that if an item is useful it
would have been fetched before queue get full and if it is still there when
queue has reached to it's capacity that means it is not very useful and
overwriting this won't harm.
بالمختصر انه لما بنستخدم الكيو العاديه وتمتلي ما نقدر نضيق أي عنصر بعدها فحيضيع. لكن في السيركولار لما قدو ممتلى يبداء يعمل فوق االعناصر الاوله و في أي مكان تم حذف عنصر في الكيو فنقدر نستغل المساحه احسن عشان العنصر الجديد ما يضيع
************************************************** ****
another understandable definition of
Double-ended queue
is an abstract data structure that implements a queue for which elements can only be added to or removed from the front (head) or back (tail). It is also often called a head-tail linked list.
************************************************** ****
Trees
Acyclic graph of vertices union edges
************************************************** ****
binary tree
is a tree in which each node has at most two childs or 1 or 0

************************************************** ****
binary search tree
a binary tree in which the key value in any node is greater than
the key value in its left child and any of its children (the nodes in the left subtree) ,and less than the key value in its right child and any of its children (the nodes in
the right subtree)
************************************************** ****
Types of Binary Tree
1-complete binary tree
a binary tree that is either full or full through the next-to-last
level, with the leaves on the last level as far to the left as possible
2-full binary tree
a binary tree in which all of the leaves are on the same level and
every nonleaf node has two children
3- rooted binary tree
is a rooted tree in which every node has at most two children.
4- perfect binary tree
is a full binary tree in which all leaves are at the same depth or same level (This is ambiguously also called a complete binary tree.)
************************************************** ****
leaf node
tree node that has no children

************************************************** ****
recursive definition
a definition in which something is defined in terms of a smaller
version of itself
recursion
the situation in which a subprogram calls itself
recursive call
a subprogram call in which the subprogram being called is the same as
the one making the call
************************************************** ****
OperationADT can be written with algorithm of one of these two methods :
Recursive ( which has short code and less space but time expensive)
Non-Recursive (which has large code and large space but short time)

************************************************** ****
Infix notaion
is the common arithmetic and logical formula notation, in which operators are written infix-style between the operands they act on (e.g. 2 + 2)
Prefix notation
places an expression's operator before its operands. For example, the expression a + b becomes + a b when using prefix notation.
Postifix notation
a parenthesis-free notation for forming mathematical expressions in which each operator follows its operandsFor example, what may normally be written as "1+2" becomes "1 2 +"
************************************************** ****
inorder traversal
a systematic way of visiting all the nodes in a binary tree that visits
the nodes in the left subtree of a node, then visits the node, and then visits the nodes in the right subtree of the node
postorder traversal
a systematic way of visiting all the nodes in a binary tree that
visits the nodes in the left subtree of a node, then visits the nodes in the right subtree of the node, and then visits the node
preorder traversal
a systematic way of visiting all the nodes in a binary tree that visits
a node, then visits all the nodes in the left subtree of the node, and then visits the nodes in the right subtree of the node
************************************************** ****
Sort
process of rearringing set of elements in specific order to facilitate search for member element in a sorted set
Measure of sorting
1-Number of comparisons(C )
2-Number of moves(M)
************************************************** ****
Quick Sort
A sorting technique that sequences a list by continuously dividing the list into two parts and moving the lower items to one side and the higher items to the other. It starts by picking one item in the entire list to serve as a pivot point. The pivot could be the first item or a randomly chosen one. All items that compare lower than the pivot are moved to the left of the pivot; all equal or higher items are moved to the right. It then picks a pivot for the left side and moves those items to left and right of the pivot and continues the pivot picking and dividing until there is only one item left in the group. It then proceeds to the right side and performs the same operation again
************************************************** ****
Heap Sort(the parent is bigger then childrens)
A sorting algorithm that works by first organizing the data to be sorted into a special type of binary tree called a heap. The heap itself has, by definition, the largest value at the top of the tree, so the heap sort algorithm must also reverse the order. It does this with the following steps:
1. Remove the topmost item (the largest) and replace it with the rightmost leaf. The topmost item is stored in an array.
2. Re-establish the heap.
3. Repeat steps 1 and 2 until there are no more items left in the heap.
The sorted elements are now stored in an array. A heap sort is especially efficient for data that is already stored in a binary tree. In most cases, however, the quick sort algorithm is more efficient.

Application of Heap sort
One of the biggest application of heap sort is constructing a priority queue basic idea is that, we want to know the tasks that carry the highest priority, given a large number of things to do. and this is exactly how heap sort works.

************************************************** ****
Graph
number of non-empty set of vertices union edges

complete graph
a graph in which every vertex is directly connected to every other
vertex
edge (arc)
a pair of vertices representing a connection between two nodes in a graph
vertex
a node in a graph
************************************************** ****
Types of Graph
1- directed graph (digraph)
a graph in which each edge is directed from one vertex to
another (or the same) vertex
2-undirected graph
a graph in which the edges have no direction
3-weighted graph
a graph in which each edge carries a value
************************************************** ****
Indegree
number of input for anode and is the sum of the columns in adjacency matrix
Outdegree
number of outputs from anode and is the sum of the rows in adjacency matrix
Degree
number of inputs and outputs for a node and is the sum of rows and columns in adjacency matrix
adjacency list
************************************************** ****
Graph Representation:
1- adjacency matrix
for a graph with N nodes, an N_N table that shows the existence
(and weights) of all edges in the graph
2-adjacency list
a linked list that identifies all the vertices to which a particular vertex
is connected; each vertex has its own adjacency list
3-Linked list representation
************************************************** ****
adjacent nodes
two nodes in a graph that are connected by an edge
************************************************** ****
path
a combination of branches that might be traversed when a program or function is executed; a sequence of vertices that connects two nodes in a graph
************************************************** ****
الرجوع الى أعلى الصفحة اذهب الى الأسفل
وليد عبدالوهاب احمد



عدد المساهمات: 252
تاريخ التسجيل: 12/11/2010
العمر: 32

مُساهمةموضوع: رد: هياكـل البيانـات   الثلاثاء مايو 24, 2011 2:32 pm

كتاب هياكل بيانات
باللغة العربية

للتحميل
الرجوع الى أعلى الصفحة اذهب الى الأسفل
 

هياكـل البيانـات

استعرض الموضوع السابق استعرض الموضوع التالي الرجوع الى أعلى الصفحة 
صفحة 1 من اصل 1

صلاحيات هذا المنتدى:لاتستطيع الرد على المواضيع في هذا المنتدى
منتدى طلاب جامعة السودان المفتوحة ::  :: -