فرمت فایل : word (لینک دانلود پایین صفحه) تعداد صفحات 75 صفحه
دادهها:
مجموعههایی از مقادیر یک عنصر دادهای به معنی واحد منحصر به فرد از مقادیر است.
عناصر دادهای که به زیرعنصرها تقسیم شوند، عنصرهای چند قسمتی نامیده میشوند و آن دسته از عناصر که چند قسمتی نیستند عنصرهای ابتدایی نامیده میشوند مثل اسم یک کارمند شامل زیر عنصر است اسم اول، اسم وسط و اسم آخر شماره تامین اجتماعی SSN بصورت یک عنصر منحصر بفرد.
موجودیت Entity : شیء است که دارای خصیصهها با خواص معین باشد و ممکن است مقادیری به آن نسبت داده شود موجودیت کارمند دارای خصیصههای :
اسم ،
سن ،
جنسیت،
SSN (شمارة تامین اجتماعی)
مقادیر
علی
24
مرد
14235
هر خصیصه از یک موجودیت دارای یک دامنه از مقادیر است.
به دادههای دارای معنی یا دادههای پردازش شده اطلاعات میگویند.
به دادههایی که دارای خصیصههای با مقادیر معین باشد اطلاعات میگویند.
سلسله مراتب دادهها:
فیلد: یک واحد ابتدایی منحصر بفرد از اطلاعات است. (نمایانگر یک خصیصه ازموجودیت)
رکورد: مجموعهای از مقادیر فیلدهای یک موجودیت معین.
فایل: مجموعهای از رکوردهای موجودیت در یک مجموعه از موجودیتهای معین.
Px: به فیلدی که بطور منحصر بفرد رکورد داخل فایل را مشخص میکند فیلد اولیه یا اصلی میگوییم.
مثال: 1- نگاه معاملات اتومبیل: شماره سریالpk Accessories Price gear Type (لوازم همراه)
2- سازمان: Dues Owed Tel.No Address (دیون بدهکار)
رکوردها با طولهای متغیر مثل
رکوردهای دانشجویی
(تعداد درسهای متفاوت)
تمام رکوردها دارای فیلدهای برابر
و یکسان مقدار حافظه ی هر فیلد مساوی
پپیک فایل میتواند دارای یک رکورد با طول ثابت یا با طول متغیر باشد.
تعریف ساختمان داده: دادهها میتوانند بصورتهای متفاوتی سازماندهی شوند. مدل منطقی یا ریاضی سازماندهی دادهها به یک صورت خاص، یک ساختمان یک ساختمان داده نامیده میشود.
این سازماندهی باید بتواند رابطههای واقعی بین دادهها را منعکس کرده و ساده باشد تا بتوان به راحتی دادهها را پردازش کرد.
آرایهها: آرایة یک بعدی، سادهترین نوع ساختمان داده است.
یک لیست متناهی با n عنصر دادهای مشابه که به عناصر آن به ترتیب به کمک مجموعهای از n عدد متوالی که معمولا از n , ….. , 2 , 1 میباشد، دسترسی پیدا میکنیم.
اگر نام آرایه A باشد، عناصر آن را a1 , a2 , a3 , …. an یا با نماد پرانتزی
A(1) , A(2) , …. , A(n) و یا نماد کروشهای A[1] , A[2] , … A[n]
STUDENT
1
John Down
2
Ali M
3
Reza
4
5
6
زمانیکه از نماد پرانتزی و یا کروشهای استفاده میشود نام آرایه به حروف بزرگ نوشته میشود.
مثال: آرایه خطی STUDENT
STUDENT [2] = Ali m.
آرایه خطی= ارایه یک بعدی
دسترسی فقط از طریق یک اندیس
آرایه دو بعدی یا در اصطلاح ریاضی ماتریس (در تجارت جدول):
دواندیس داریم: مثال: فروشگاه زنجیرهای که از 28 فروشگاه که هر کدام 4 بخش دارند تشکیل شده (فروش/ هفتگی) دانشگاه آزاد که هر کدام از واحدها چند رشته دارند (تعداد دانشجو)
4
3
2
1
store
28702
1
2
.
.
.
28
Pointer
مشتری
a
b
a
d
c
b
a
.
.
A
B
C
D
.
.
.
.
.
1
2
3
4
5
.
.
.
n
Pointer
مشتری
3
2
1
1
2
1
3
1
1
A
B
C
D
1
2
3
0
1
1
0
n
لیستهای پیوندی: یک شرکت خدماتی، مشخصات مشتریهای خود را در یک فایل نگهداری میکند که فروشنده مرتبط با ان مشتری را نیز مشخص میکند.
یک اشاره گر فضای کمتری نسبت به یک اسم میگیرد. در صورت افزایش اطلاعات این صرفهجویی بیشتر خود را نشان میدهد.
یک مزیت دیگر پیدا کردن نام مشتریان یک فروشنده است که به سادگی انجام میگیرد به جای search در کل فایل پیکانها دنبال میشوند.
Pointer
فروشنده
3,6
1,2,4
. . . .
a
b
c
عیب اینکار: هر فروشنده ممکن است چند اشارهگر داشته باشد وبا اضافه ویا حذف شدن مشتریها، مجموعه اشارهگرها تغییرکند.
راه حل: هر فروشنده یک اشاره گر دارد که به مشتری اول اشاره میکند که اشاره گر آن نیز به نوبه خود به مشتری دوم و .... Link مشتری آخر به 0
Pointer
فروشنده
3
2
1
a
b
c
Link
مشتری
5
A
1
2
3
.
.
.
n
4
6
7
8
B
C
D
E
.
.
Pointer (اشاره گر): یک عنصر از یک لیست بر یک عنصر از لیست دیگر اشاره می کند.
Link (پیوند): یک عنصر از لیست به یک عنصر دیگری از همان لیست اشاره می کند.
درختها:
اغلب شامل رابطه سلسله مراتبی بین عناصر مختلف هستند. ساختمان داده ای که این رابطه را نشان می دهد یک گراف درختی ریشه دار یا فقط درخت نامیده می شود.
کارمند
پشته (Stack): به آن سیستم LIFO یا آخرین ورودی اولین خروجی است یک لیست خطی که اضافه و کم کردن عناصر فقط از یک سر لیست امکان پذیر است. مثال: یک پشته از بشقابها
صف (Queue) : یک سیستم FIFO است. اولین ورودی اولین خروجی است. لیست خطی که اضافه کردن عناصر تنها از انتهای لیست (Rear) و برداشتن عناصر از ابتدا (front) صورت می گیرد. مثل : ایستگاه اتوبوس
گراف (Graph): گاهی اوقات داده ها یک رابطه بین حقیقت عناصر طبیعت را نشان می دهد و بصورت سلسله مراتبی نیستند. مثل : ارتباط بین شهرها.
عملیات بر روی ساختمان داده ها: چهار عمل اصلی شامل:
- پیمایش: دسترسی به اطلاعات یک رکورد آن هم دقیقاً یکبار پیمایش
می گویند.
2- جستجو: عمل یافتن مکان یک رکورد با یک مقدار کلیدی معین یا رکوردهایی که روی یک یا چند شرط صدق میکنند.
3- اضافه کردن: افزودن رکورد جدید به ساختمان داده.
4- حذف کردن: حذف یک رکورد جدید از ساختمان داده.
گاهی از بیش از یک عمل برای یک هدف استفاده میشود. مثل:
1- یک رکورد با کلید معلوم حذف میشود.2- مرتب کردن 3- ادغام کردن
الگوریتم: پیچیدگی الگوریتم، توازن بین زمان اجرا و حافظه
یک الگوریتم یک لیست خوش تعریف از مراحلی است که برای حل یک مساله معین در نظر گرفته شده است زمان و حافظه دو معیار اصلی در کارآیی یک الگوریتم هستند.
رشتهها:
ابتدا کامپیوترها برای پردازش دادههای عددی استفاده میشود ولی امروزه بیشتر برای پردازش دادههای غیر عددی موسوم به دادههای کاراکتری مورد استفاده قرار میگیرد.
در دروس کامپیوتری معمولاً به دنبالهای از کاراکترها به جای اصلاح «کلمه» رشته میگویند (String)
String آرایهای از کاراکترهاست
کاراکترهای الفبایی:
ABCDE…
کاراکترهای رقمی : ....0 1 2 3
کاراکترهای مخصوص : + - / * ( ) , . $ = ‘
رشته تهی : طول رشته صفر است.
یک رشته، دنباله متناهی از صفر تا چند کاراکتر است طول رشته ثابت نیست وبا دادههایی که در آن ذخیره شده است مشخص میشود.
تعداد کاراکترهای یک رشته ، طول رشته نامیده میشود.
رشتهای که هیچ کاراکتری ندارد، رشته تهی یا رشته پوچ نام دارد. نمایش رشتهها دربین علامت نقل قول است.
“The End” , ‘ ‘ , ‘ ‘
اگر در پاسکال از دستور Name := “ ” , استفاده میکنیم. رشته Name را به تهی تبدیل میکند.
دو رشته S1 و S2 را با هم ترکیب میکنیم و رشتة S2 حاصل میشود به اینکار پیوند یا اتصال S1 و S2 میگویند.
S1||S2
“The” || 'o'|| ‘End’ = ‘The End’ اما ‘The’ || ‘End’=’The End’
طول رشته حاصل برابر با طول رشتههای ترکیب شده است.
رشته Y یک زیر رشته از S نامیده میشود.
S=X||Y||Z
مثال: ‘The’ یک زیر رشته ابتدایی ‘The End’ است.
طول یک زیر رشته نمیتواند از طول رشته بیشتر باشد.
توجه: برای نمایش یک کاراکتر یک بایت فضا مورد نیاز است. کامپیوتری که به یک بایت از حافظه دسترسی پیدا کند، یک ماشین با قابلیت آدرس دهی بایتی میگویند.
در پاسکال میتوان با استفاده از زیر برنامه Val رشته را به عدد تبدیل کرد:
در پاسکال میتوان با استفاده از زیر برنامه Sbr عدد را به رشته تبدیل کرد:
Val (st , number , error):
Sbr (number ; format , numstring)
ذخیرة رشتهها:
1- ساختارهایی که طول ثابت دارند - طول رکوردها برابر (تعداد کاراکترهایکسان)
مزایا: 1- دسترسی آسان به اطلاعات
2- update : آسان هر رکورد معین (طول نباید بیشتر از طول ثابت رکورد باشد)
معایب : 1- اگر فضاهای خالی زیاد باشد خواندن تمام رکورد
هدر رفتن زمان
2- بعضی از رکوردها نیاز به حافظه بیشتر از مقدار ثابت دارند.
3- تصحیح یک یا چند کاراکتر تغییر تمام رکوردها.
2- حافظه با طول متغیر که ماکزیمم طول ثابت دارند: به دو روش صورت می گیرد 1- در پایان رشته علامت $$ 2- طول رشته را به عنوان فیلد اضافه در یک آرایه نگهداشت.
3- ذخیره رشتهها بصورت پیوندی : این روش استفاده زیاد دارد.
لیست پیوندی یک طرفه: یک دنباله از خانههای حافظه به نام گره است که بصورت خطی مرتب شدهاند و هر گره شامل یک فیلد موسوم به پیوند یا اتصال است که به گره بعدی لیست اشاره میکند.
در هر خانه حافظه یک کاراکتر با تعدادمین کاراکتر جایگزین میشود و یک پیوند که یک مقداری از حافظه را اشغال میکند آدرس خانه حافظهای را که شامل کاراکتربعدی است به دست میدهد.
مثال: رشتة ‘The End’
هر گره یک کاراکتر:
هر گره سه کاراکتر:
عملیات بر روی رشتهها:
زیر رشته: مستلزم داشتن اطلاعات زیر است: 1- نام رشته یا خود رشته.
2- مکان اولین کاراکتر زیر رشته در رشتة داده شده .
3- طول زیر رشته یا مکان آخرین کاراکتر زیر رشته.
SOBSTRING (String , initial , length)
1در پاسکال : S=’I am Learning Pascal’; S1=copy (S , 15 , 6) ; S1=’Pascal’
شاخص گذاری (تطبیق الگو): مکان یابی رشته P که برای نخستینبار، در رشته T ظاهر شده است.
INDEX (text , pattern)
تحقیق جامع و کامل درباره ساختمان داده ها در سی پلاس پلاس
