پاورپوینت کامل ساختمان داده ها و الگوریتم ۳۹۷ اسلاید در PowerPoint

توجه : این فایل به صورت فایل power point (پاور پوینت) ارائه میگردد

 پاورپوینت کامل ساختمان داده ها و الگوریتم ۳۹۷ اسلاید در PowerPoint دارای ۳۹۷ اسلاید می باشد و دارای تنظیمات کامل در PowerPoint می باشد و آماده ارائه یا چاپ است

شما با استفاده ازاین پاورپوینت میتوانید یک ارائه بسیارعالی و با شکوهی داشته باشید و همه حاضرین با اشتیاق به مطالب شما گوش خواهند داد.

لطفا نگران مطالب داخل پاورپوینت نباشید، مطالب داخل اسلاید ها بسیار ساده و قابل درک برای شما می باشد، ما عالی بودن این فایل رو تضمین می کنیم.

توجه : در صورت  مشاهده  بهم ریختگی احتمالی در متون زیر ،دلیل ان کپی کردن این مطالب از داخل فایل می باشد و در فایل اصلی پاورپوینت کامل ساختمان داده ها و الگوریتم ۳۹۷ اسلاید در PowerPoint،به هیچ وجه بهم ریختگی وجود ندارد

---

بخشی از مطالب داخلی اسلاید ها

پاورپوینت کامل ساختمان داده ها و الگوریتم ۳۹۷ اسلاید در PowerPoint

اسلاید ۴: PerequisitesC++ پیچیدگی Big oh , theta and omega notation

اسلاید ۵: Sortingترتیب زیر را در نظر بگیرید: a[0],a[1],…, a[n-1] پس از مرتب سازی صعودی داریم: a[0] <=a[1] <= ….<=a[n-1] example:8,6,9,4,3 => 3,4,6,8,9

اسلاید ۶: Sort metodsInsertion sort Bubble sortSelection sort Count sort Shaker sort Shell sort Heap sort Merge sort Quick sort

اسلاید ۷: اضافه کردن یکinsert an element لیست ترتیبی زیر را در نظر بگیرید: input: 3, 6, 9, 14عنصر ۵ را به لیست فوق اضافه کنید. output: 3, 5, 6, 9, 14

اسلاید ۸: Insert An Element3, 6, 9, 14 insert 5 عدد ۵ را با آخرین عنصر لیست مقایسه کنید .Shift 14 right to get 3, 6, 9, , 14Shift 9 right to get 3, 6, , 9, 14 Shift 6 right to get 3, , 6, 9, 14با اضافه کردن ۵ خروجی:Output: 3, 5, 6, 9, 14

اسلاید ۹: Insert An Element// insert into a[0:i-1]Int j;For (j=i-1 ; j>=0 && t <a[ j] ;j–)A[ j+1] = a[ j]A[ j+1] = t ;

اسلاید ۱۰: Insertion sort لیستی با سایز۱ در نظر بگیرید.”اولین عنصر را داخل لیست قرار دهید.“عمل insertion را تکرار کنید بطوریکه ترتیب داده ها حفظ شود

اسلاید ۱۱: Insertion sortSort 7, 3, 5, 6, 1Start with 7 and insert 3=> 3,7 Insert 5=>3, 5, 7Insert 6=>3, 5, 6, 7Insert 1=>1, 3, 5, 6, 7

اسلاید ۱۲: Insertion sortFor (i=1 ; i<a.length ; i++){// insert a[i] into a[0:i-1] //code to insert comes here}

اسلاید ۱۳: Insertion sort For (i=1 ; i<a.length ; i++){// insert a[i] into a[0:i-1] //code to insert comes hereint t =a[ j]int j;For ( j=i-1 ; j>=0 && t <a[ j] ; j–)A[ j+1] = a[ j]A[ j+1] = t ;}

اسلاید ۱۴: Complexityیا پیچیدگیپیچیدگی مکانی /حافظه ایپیچیدگی زمانی شمارش یک عملگر خاصشمارش تعداد مراحل پیچیدگی Asymptotic

اسلاید ۱۵: Compration count شمارش مقایسه ای For (i=1 ; i<a.length ; i++){// insert a[i] into a[0:i-1] //code to insert comes hereint t =a[ j]int j;For ( j=i-1 ; j>=0 && t <a[ j] ; j–)A[ j+1] = a[ j]A[ j+1] = t ;}

اسلاید ۱۶: Compration countیک نمونه کاراکتری از n را در نظر بگیرید، که در آن n طول لیستی باشد که می خواهیم روی آن Insertion sort را انجام دهیم.و تعداد توابع این نمونه کاراکتری را بشمارید.؟؟؟؟Determine count as a function of this instance characteristic.

اسلاید ۱۷: Compration countFor (j=i-1 ; j>=0 && t <a[ j] ;j–)A[ j+1] = a[ j];چند مقایسه انجام شده است ؟

اسلاید ۱۸: Compration countFor (j=i-1 ; j>=0 && t <a[ j] ;j–)A[ j+1] = a[ j];شمارش تعداد مقایسات وابسته به a[] وt با توجه به i

اسلاید ۱۹: Compration countWorst-case count=maximum countBest –case count=minimum count Avarage count

اسلاید ۲۰: Worst-case Compration countFor (j=i-1 ; j>=0 && t <a[ j] ;j–)A[ j+1] = a[ j];A=[1,2,3,4] and t=0 =>4 comparesA=[1,2,3,..,i] and t=0 =>i compares

اسلاید ۲۱: Worst-case Compration countfor(int i=1; i< n ; i++)For (j=i-1 ; j>=0 && t <a[ j] ;j–)A[ j+1] = a[ j];تعداد کل مقایسات :Total comprase =1+2+3+…+(n-1) =(n-1)n/2

اسلاید ۲۲: Step countیک مرحله از محاسبات وابسته است به مقادیر n برای مثال :۱۰ add , 100 subtracts,1000 multipliesفقط یک step محسوب میشود .وبه این مفهوم نمی باشد که با افزایش n یک مرحله نیز به تعداد step اضافه شود.

اسلاید ۲۳: Step count s/eFor (i=1 ; i<a.length ; i++) 1{// insert a[i] into a[0:i-1] 0 //code to insert comes here 1 int t =a[ j] 0 int j; 1 For ( j=i-1 ; j>=0 && t <a[ j] ; j–) 1 A[ j+1] = a[ j] 1 A[ j+1] = t ; 0}

اسلاید ۲۴: Step counts/e همیشه ۰ یا یک نمی باشدX=mymath.sum(a,n)Where n is the instance characteristic has a s/e count of n

اسلاید ۲۵: Step count s/e stepFor (i=1 ; i<a.length ; i++) 1{// insert a[i] into a[0:i-1] 0 //code to insert comes here 1 int t =a[ j] 0 int j; 1 i+1For ( j=i-1 ; j>=0 && t <a[ j] ; j–) 1 iA[ j+1] = a[ j] 1 A[ j+1] = t ; 0}

اسلاید ۲۶: Step countFor (int i=1;; i<a.length; i++){2i+3}Step count for For (int i=1; i<a.length;; i++)Is n Step count for body of for loop is 2(1+2+3+…+n-1)+3(n-1)=(n-1)n +3(n-1)=(n-1)(n+3)

اسلاید ۲۷: محاسبه پیچیدگی در مرتب سازی درجی O(n2)به چه معنی می باشد؟

اسلاید ۲۸: محاسبه پیچیدگی در مرتب سازی درجیبدترین حالت:(n2)بهترین حالت: (n)بنابراین انتظار میرود بدترین حالت زمانی است که n دوبل میشود(تکرار میشود).

اسلاید ۲۹: محاسبه پیچیدگی در مرتب سازی درجیآیا O(n2)خیلی زیاد است؟الگوریتم تجربی(practical) چه میباشد؟

اسلاید ۳۰: Faster Computer Vs Better Algorithmپیشرفت الگوریتم ها مفید تر از پیشرفت سخت افزار است.

اسلاید ۳۱: ساختمان داده Data Structureانواع داده :داده هایی که در یک مجموعه قرار می گیرند(در ارتباط).Ex: integer= {0, +1,-1,+2,-2,….} days of week = {S,M,T,W,TH,SA}

اسلاید ۳۲: Data objectداده هایی که نامربوط با هم هستند. Example: MyDataObject={apple, chair, 2,5,red,green ,jack}

اسلاید ۳۳: Data StructureData oject +روابطی که وجود دارد برای مقایسه میان عناصرEx:369<370280+4=284

اسلاید ۳۴: Data Structureمیان عناصری که مقایسه میشوند در یک مثال:۳۶۹۳ is more signification than 6 3 is immediately to the left of 69 is immediately to the right of 6

اسلاید ۳۵: Data Structureروابط خاص معمولا توسط عملگر های خاص روی چندین نمونه داده ایجاد می شود عبارتند از:Add,subtract, predecessor,multiply ضرب ، تفریق ، جمع

اسلاید ۳۶: Linear (or Ordered) listsInstannces are of the form(e0,e1,e2,….,en-1)Where ei denodes a list element n>=0 is finiteList size is n

اسلاید ۳۷: Linear (or Ordered) listsL= (e0,e1,e2,e3,….,en)روابط زیر بر قرار است: : e0 عنصر جلوی لیست میباشد. “zeroth element”:en-1 عنصر آخرلیست میباشد. “last elements”: ei+1 دقیقا بعدازei قرار می گیرد.

اسلاید ۳۸: مثالهایی از لیست های خطی:Student in COP3530=(jack,jill, Abe ,Henry,Mary ,…,judy)Exams in COP3530=(exam1, exam 2, exam3)Days of Week=(S,M,T,W,TH,SA)Months=(Jan,Feb ,Mar ,Apr,…,Nov,Dec)

اسلاید ۳۹: Linear list Oprations-size()اندازه گیری سایز لیست Example: L=(a,b,c,d,e)Size=5

اسلاید ۴۰: Linear list Oprations-get(the index)یک عنصر را میگیرد و اندیس آن را بعنوان خروجی می دهد.Example: L=(a,b,c,d,e)Get(0)=aGet(2)=cGet(4)=e Get(-1)=errorGet(9)=error

اسلاید ۴۱: Linear list Oprations-indexof (the element)اندیس هر عنصر را برمی گرداند. L= (a,b,d,b,a) Index of(d)=2Index of(a)=0Index of(z)=-1

اسلاید ۴۲: Linear list Oprations-remove(the index)حذ ف را انجام داده و محتوای اندیس مورد نظر را برمی گرداند. L=(a,b,c,d,e,f,g)Remove(2) returns cand L become (a,b,d,e,f,g) index of d,e,f and g decrease by 1

اسلاید ۴۳: Linear list Oprations-remove(the index)حذ ف را انجام داده و محتوای اندیس مورد نظر را برمی گرداند.L=(a,b,c,d,e,f) Remove(-1)=>error Remove(20)=>error

اسلاید ۴۴: Data structure specification Language independetAbstract Data TypeJava Abstaract class

اسلاید ۴۵: Liner List Abstaract Data Type AbstractData Type Linear List{ instancesOrdered finit collection of zero or more elementsعملگر هاEmpty( ):نتیجه درست را بر می گرداند اگر و فقط اگر لیست خالی باشد ،در غیرنتیجه : false میبا شد.Size( ):اندازه لیست را بر می گرداند.بعبارتی تعداد عناصر داخل لیست را بر می گرداند.

اسلاید ۴۶: Data Representation MethodsArray —chapter 5Linked—chapter 6Simulated

اسلاید ۴۷: Linear List Array Representation 1 2 3 4 5 6 L=(a,b,c,d,e)

اسلاید ۴۸: Right to Left Mapping

اسلاید ۴۹: Mapping That Skip Every Other position

اسلاید ۵۰: Wrap Around Mapping

اسلاید ۵۱: Represention Used In Text 1 2 3 4 5 6

اسلاید ۵۲: Add/Remove An Element _1Size=5

اسلاید ۵۳: Add/Remove An Element_2Add ( l, g)size-=6

اسلاید ۵۴: Length of Array element[]چون نمی دانیم چه تعداد عنصر در لیست وجود خواهد داشت ،بنابراین باید یک مقدار اولیه برای آن فرض کرد.و سپس بر حسب نیاز آن را افزایش داد.

اسلاید ۵۵: Liner List Abstaract Data TypeGet (index): خروجی آن اندیس عنصر میباشد بر طبق جایگاه آن ودرصورتی مقدار(۱-) را برمی گرداند که عنصر مورد نظر در لیست نباشد.Remove (index):عنصر را حذف کرده و محتوای عنصر را برمی گرداند.Add (index, x): عنصر x را در index داده شده اضافه کرده و پس از آن شماره اندیس ما بقی عناصر از موقعیت جاری یک واحد افزایش میابد.Output( ):خروجی لیست است که از چپ به راست مرتب می شود.

اسلاید ۵۶: Linear List As Java abstract ClassPublic abstractclass Linear ListAsAbstractClass{Public abstarct Boolean isEmpty();Public abstarct int size();Public abstarct object get(int index);Public abstarct int indexOf(Object the element);Public abstarct object remove(int index);Public abstarct void add(int index, Object the element);Public abstarct string to sorting();}

اسلاید ۵۷: Linked Representationعناصر لیست در حافظه با ترتیبی دلخواه نگهداری می شوند.explicit information (called a link)اطلاعات صریح که لینک نامیده می شوندبرای رفتن از یک عنصر به عنصر دیگر استفاده میشوند

اسلاید ۵۸: Memory Layoutabcdecaedbهرلینک از یک جدول دلخواه استفاده می کند. A linked representation uses an arbitrary layout.برای نمایش لیست ها از آرایه ها استفاده می شود. L = (a,b,c,d,e)

اسلاید ۵۹: Linked Representationتهی می باشد. (e) اشاره گر عنصر:firstNodeبرای اشاره به عنصر شروع استفاده میشود.caedbfirstNode

اسلاید ۶۰: Normal Way To Draw A Linked Listفیلد اشاره گر فیلد دادهabcdenullfirstNode

اسلاید ۶۱: Chainدریک زنجیر یا در یک لیست از اشاره گر هاهر نود نشان دهنده یک عنصر می باشد.از یک نود به نود دیگر یک اشاره گر وجود دارد.اشاره گر آخرین لیست تهی میباشد.abcdenullfirstNode

اسلاید ۶۲: Node Representationpackage dataStructures;class ChainNode{ Object element; ChainNode next;} nextelement

اسلاید ۶۳: Constructors Of ChainNode ChainNode() {}nullnullnullelementnextelementChainNode(Object element) {this.element = element;} ChainNode(Object element, ChainNode next) {this.element = element; this.next = next;}

اسلاید ۶۴: get(0)checkIndex(0);desiredNode = firstNode; return desiredNode.element;abcdenullfirstNode

اسلاید ۶۵: get(1)checkIndex(1);desiredNode = firstNode.next; return desiredNode.element;abcdenullfirstNode

اسلاید ۶۶: get(2)checkIndex(2);desiredNode = firstNode.next.next; return desiredNode.element;abcdenullfirstNode

اسلاید ۶۷: get(5)checkIndex(5); desiredNode = firstNode.next.next.next.next.next;return desiredNode.element; abcdenullfirstNode

اسلاید ۶۸: NullPointerExceptiondesiredNode = firstNode.next.next.next.next.next.next;abcdenullfirstNode

اسلاید ۶۹: Remove An Elementremove(0)abcdenullfirstNodefirstNode = firstNode.next;

اسلاید ۷۰: abdenullfirstNodecremove(2)ابتدا نود قبل از نودی را که بخواهد حذف شود را انتخاب کنیدfirst node یعنی ccbeforeNode = firstNode.next;bbeforeNode

اسلاید ۷۱: remove(2)اکنون اشاره گرآن را تغییر دهید. beforeNodeدرbeforeNode.next = beforeNode.next.next; beforeNodeabcdenullfirstNode

اسلاید ۷۲: add(0,’f’)abcdenullfirstNodefnewNodeگام اول: نود جدید را انتخاب کنید که حتما دارای فیلد داده واشاره گرباشد .ChainNode newNode = new ChainNode(new Character(‘f’), firstNode);

اسلاید ۷۳: add(0,’f’)abcdenullfirstNodefnewNodeگام اول: آن را بعنوان نود آغاز انتخاب کنید.firstNode = newNode;

اسلاید ۷۴: One-Step add(0,’f’)abcdenullfirstNodefnewNodefirstNode = new ChainNode( new Character(‘f’), firstNode);

اسلاید ۷۵: add(3,’f’)گام اول: ابتدا نود با اندیس ۲را انتخاب کنید.abcdenullfirstNodefnewNodebeforeNodecگام دوم: حال نود جدید را ایجاد کرده بطوریکه دارای فیلد داده و فیلد اشاره گر داشته باشد.ChainNode newNode = new ChainNode(new Character(‘f’), beforeNode.next); finally link beforeNode to newNodebeforeNode.next = newNode;

اسلاید ۷۶: Two-Step add(3,’f’)beforeNode = firstNode.next.next;beforeNode.next = new ChainNode(new Character(‘f’), beforeNode.next);abcdenullfirstNodefnewNodebeforeNodec

اسلاید ۷۷: The Class Chain

اسلاید ۷۸: The Class Chainnext (datatype ChainNode)element (datatype Object) کاربردChainNodeabcdenullfirstNodesize =تعدادعناصر لیست میباشد. شمارش

اسلاید ۷۹: The Class Chain /** linked implementation of LinearList */package dataStructures;Import c++; // has Iteratorpublic class Chain implements LinearList{ // data members protected ChainNode firstNode; protected int size; // methods of Chain come here}

اسلاید ۸۰: Constructors /** ایجاد یک لیست خالی */ public Chain(int initialCapacity) { // مقادیر اولیه :firstNode and size // null and 0 } public Chain() {this(0);}

اسلاید ۸۱: The Method isEmpty /** مقدار درست را برمی گردانداگر وفقط اگر لیست خالی باشد */ public boolean isEmpty() {return size == 0;}

اسلاید ۸۲: The Method size() /** خروجی آن شمارش تعداد عناصر داخل لیست میباشد */ public int size() {return size;}

اسلاید ۸۳: The Method checkIndows IndexOutOfBoundsException when * index is not between 0 and size – 1 *//**اندیس مربوط به هر عنصر را بر می گرداند و زمانی که ۰ یا ۱- را برگرداند به این مفهوم است که آن عنصر در لیست وجود ندارد.*/ void checkIndex(int index) { if (index < 0 || index >= size) throw new IndexOutOfBoundsException (index = + index + size = + size); }

اسلاید ۸۴: The Method get public Object get(int index) { checkIndex(index); // نود دلخواه راتغییر دهید ChainNode currentNode = firstNode; for (int i = 0; i < index; i++) currentNode = currentNode.next; return currentNode.element; }abcdenullfirstNode

اسلاید ۸۵: The Method indexOf public int indexOf(Object theElement) { // یک زنجیر از نودها را جستجو کنید ChainNode currentNode = firstNode; int index = 0; // اندیس نود جاری while (currentNode != null && !currentNode.element.equals(theElement)) { // به نود بعدی تغییر دهید currentNode = currentNode.next; index++; }

اسلاید ۸۶: The Method indexOf // اطمینان از اینکه عنصر مربوطه را یافته ایم if (currentNode == null) return -1; else return index; }

اسلاید ۸۷: Removing An Elementremove(0)firstNode = firstNode.next;abcdenullfirstNode

اسلاید ۸۸: Remove An Element public Object remove(int index) { checkIndex(index); Object removedElement; if (index == 0) // نود شروع را حذف کنید { removedElement = firstNode.element; firstNode = firstNode.next; }

اسلاید ۸۹: remove(2) را یافته و اشاره گر آن را تغییر دهیدbeforeNode beforeNode.next = beforeNode.next.next; beforeNodeabcdenullfirstNode

اسلاید ۹۰: Remove An Element else { // جایگاهی برای قرار دادن نود جاری میباشد:q ChainNode q = firstNode; for (int i = 0; i < index – 1; i++) q = q.next; removedElement = q.next.element; q.next = q.next.next; // نود دلخواه را حذف کنید } size–; return removedElement; }

اسلاید ۹۱: One-Step add(0,’f’)abcdenullfirstNodefnewNodefirstNode = new ChainNode(‘f’, firstNode);

اسلاید ۹۲: Add An Element public void add(int index, Object theElement) { if (index < 0 || index > size) // موقعیت لیست نادرست است throw new IndexOutOfBoundsException (index = + index + size = + size); if (index == 0) // به جلو اضافه کنید. firstNode = new ChainNode(theElement, firstNode);

اسلاید ۹۳: Two-Step add(3,’f’)beforeNode = firstNode.next.next;beforeNode.next = new ChainNode(‘f’, beforeNode.next);abcdenullfirstNodefnewNodebeforeNodec

اسلاید ۹۴: Adding An Element else { // عنصر جدید را بیابید ChainNode p = firstNode; for (int i = 0; i < index – 1; i++) p = p.next; // pاضافه کنید بعد از p.next = new ChainNode(theElement, p.next); } size++; }

اسلاید ۹۵: Chain With Header NodeabcdenullheaderNode

اسلاید ۹۶: Empty Chain With Header NodeheaderNodenull

اسلاید ۹۷: Circular ListabcdefirstNode

اسلاید ۹۸: Doubly Linked ListabcdenullfirstNodenulllastNode

اسلاید ۹۹: Doubly Linked Circular ListabcdefirstNode

اسلاید ۱۰۰: Doubly Linked Circular List With Header NodeabceheaderNoded

اسلاید ۱۰۱: Empty Doubly Linked Circular List With Header NodeheaderNode

اسلاید ۱۰۲: Arrays

اسلاید ۱۰۳: ۱D Array Representation In C, and C++یک نمونه آرایه یک بعدی x = [a, b, c, d]د ر خانه های مجاور یکدیگر قرار میگیرند Memoryabcdstart location(x[i]) = start + i

اسلاید ۱۰۴: Space Overheadspace overhead = 4 bytes for start + 4 bytes for x.length = 8 bytes(میزان فضایی که برای آرایه فوق نیاز داریم )Memoryabcdstart

اسلاید ۱۰۵: ۲D Arraysآرایه دو بعدی a declared as:int [][]a = new int[3][4];که در یک جدول نشان داده م شود.a[0][0] a[0][1] a[0][2] a[0][3]a[1][0] a[1][1] a[1][2] a[1][3]a[2][0] a[2][1] a[2][2] a[2][3]

اسلاید ۱۰۶: Rows Of A 2D Arraya[0][0] a[0][1] a[0][2] a[0][3] row 0a[1][0] a[1][1] a[1][2] a[1][3] row 1a[2][0] a[2][1] a[2][2] a[2][3] row 2

اسلاید ۱۰۷: Columns Of A 2D Arraya[0][0] a[0][1] a[0][2] a[0][3]a[1][0] a[1][1] a[1][2] a[1][3]a[2][0] a[2][1] a[2][2] a[2][3]column 0column 1column 2column 3

اسلاید ۱۰۸: ۲D Array Representation In C and C++سطر های آرایه دو بعدی ,آرایه های یک بعدی هستند.نمایش آرایه های دوبعد با استفاده از آرایه یک بعدی x = [row0, row1, row 2] row 0 = [a,b, c, d] row 1 = [e, f, g, h] row 2 = [i, j, k, l]and store as 4 1D arrays آرایه دو بعدی x a, b, c, de, f, g, hi, j, k, l

اسلاید ۱rray Representation In Java, C, and C++x.length = 3x[0].length = x[1].length = x[2].length = 4abcdefghijklx[]

اسلاید ۱۱۰: Space Overheadspace overhead = overhead for 4 1D arrays = 4 * 8 bytes = 32 bytes = (number of rows + 1) x 8 bytesabcdefghijklx[]

اسلاید ۱۱۱: Array Representation In C and C++این نمایش آرایه آرایه ها نامیده می شود.با توجه به شکل فوق نیازبه حافظه ای با سایز های ۳و۴و۴و۴ برای ذخیره آرایه های یک بعدی دارد.یک بلوک حافظه شامل سایزتعداد ستونها و سطرها میباشدabcdefghijklx[]

اسلاید ۱۱۲: Row-Major MappingExample 3 x 4 array:a b c de f g hi j k lآرایه فوق در یک آرایه یک بعدی قرار گرفته است بطوریکه هر عنصر آن یک سطر از آرایه فوق است و بعبارتی هر سطر آن یک آرایه یک بعدی می باشد.عناصرداخل هر سطر از چپ به راست مرتب شده اند .سطرها از بالا به پایین مرتب شده اند .We get y[] = {a, b, c, d, e, f, g, h, i, j, k, l}row 0row 1row 2…row i

اسلاید ۱۱۳: Column-Major Mappinga b c de f g hi j k lآرایه فوق در یک آرایه یک بعدی قرار گرفته است بطوریکه هر عنصر آن یک ستون از آرایه فوق است و بعبارتی هر ستون آن