ДС17о06-абстрактные-типы-данных-С++ (1238901)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Carnegie MellonАбстрактныетипы данных С++Алгоритмыи алгоритмические языкиgoo.gl/c8pyqxЛекция6,10 октября,2017Лектор:ДмитрийСеверов,кафедраинформатики608КПМdseverov@mail.mipt.ruhttp://cs.mipt.ru/wp/?page_id=60771Пример4:односвязныйсписок¢¢Определениеформатаузласпискаstruct node { My_type item;struct node *next; };typedef struct node *link;Выделениепамятидляузла спискаlink x = (link)malloc(sizeof(struct node));¢ Инициализацияэлементовузла(*x).item = …; x->next = NULL;x->itemx………x->next2Объединениеэлементоввсписок (1)¢Вставкаузлаt затекущимузломхt->next = x->next; x->next = t;xyt………………………¢Удалениеузла,следующегозаxt = x->next; x->next=t->next; free(t);x………t………………3Объединениеэлементоввсписок (1)¢Вставкаузлаt затекущимузломхt->next = x->next; x->next = t;xyt………………………¢Удалениеузла,следующегозаxt = x->next; x->next=t->next; free(t);x………………4«ЧТОПОЗВОЛЕНОЮПИТЕРУ…»#include <stdio.h>#define N …int a[N],b[N];int main() {…a=b;// ошибка…return 0; }#include <stdio.h>#define N …struct { int a[N];} a,b;int main() {…a=b;//разрешено…return 0; }56Объединениеэлементоввсписок (2)¢¢Вставкаузлаt передтекущимузломхlinkg=newnode;*g=*x;//дубльхx->next=g;x->item=t->item;t………Удалениетекущегоузлаlinkp=x->next;*x =*x->next;deletep;x………p………x………y………………7Объединениеэлементоввсписок (2)¢¢Вставкаузлаt передтекущимузломхlinkg=newnode;*g=*x;//дубльхx->next=g;x->item=t->item;t………Удалениетекущегоузлаlinkp=x->next;*x =*x->next;deletep;x………x………g………y………………89ВведениеПочемутипы«абстрактные»?¢ Реализациимассивамииструктурами¢10СПИСОК, ОЧЕРЕДЬ,СТЕКОчередьFIFO– FirstInFirstOutСтекLIFO– LastInFirstOutСписокCasualInCasualOut11РЕАЛИЗАЦИЯМАССИВАМИ12Стек.Компоненты#include <stdio.h>#include <malloc.h>#include <stdlib.h>typedef int T;typedef struct Stack *Link_Stack;inline void ERR(const char* s) {fputs(s,stderr); exit(1); }13Стек.

Конструкцияstruct Stack { int NumEl, Size; T Items[]; };Link_Stack Stack_ini(int N) {Link_Stack a = (Link_Stack)malloc(sizeof(struct Stack) + N*sizeof(T));a->NumEl=0; a->Size=N; return a; }Link_Stack Stack_free(Link_Stack a) {free(a); return NULL; }14Стек.Состояниеint Stack_Is_Empty(Link_Stack a) {return a->NumEl==0; }int Stack_ Is_Full(Link_Stack a) {return a->NumEl==a->Size; }15Стек.Действияvoid Stack_push(Link_Stack a, T New_el) {if(Stack_Is_Full(a))ERR("Stack::push: stack is full");a->Items[a->NumEl++]=New_el; }T Stack_pop(Link_Stack a) {if(Stack_Is_Empty(a))ERR("Stack::pop: stack is empty");return a->Items [--a->NumEl]; }161718Очередь.Компоненты#include <stdio.h>#include <malloc.h>#include <stdlib.h>typedef int T;typedef struct Queue *Link_Queue;inline void ERR(const char* s) {fputs(s,stderr); exit(1); }19Очередь.Конструкцияstruct Queue { int NumEl, Size, P; T Items[]; };Link_Queue Queue_ini(int N) { Link_Queue a =(Link_Queue)malloc(sizeof(struct Queue) + N*sizeof(T));a->Size=N; a->NumEl=a->P=0; return a; }Link_Queue Queue_free(Link_Queue a) { free(a);return NULL; }20Очередь.Состояниеint Queue_Is_Empty(Link_Queue a) {return a->NumEl==0; }int Queue_Is_Full(Link_Queue a) {return a->NumEl==a->Size; }21Очередь.Действияvoid Queue_put(Link_Queue a, T New_el) {if(Queue_Is_Full(a))ERR("Queue::put: queue is full");a->Items[a->P++]=New_el; a->NumEl++;if(a->P==a->Size) a->P=0; }T Queue_get(Link_Queue a) {if(Queue_Is_Empty(a))ERR("Queue::get: queue is empty");return a->Items[a->P - a->NumEl-- +(a->P <= a->NumEl?a->Size:0)]; }222324252627РЕАЛИЗАЦИЯСТРУКТУРАМИ28Компоненты#include <stdlib.h>#include <malloc.h>typedeftypedeftypedeftypedefstructstructstructstructitem *Link_Item;list *Link_List;stack *Link_Stack;queue *Link_Queue;void ERR(const char* s) {fputs(s,stderr); exit (1); }29Узел.Конструкцияtypedef struct item { T node; Link_Item next; }Item;Link_Item Item_Create(T elem, Link_Item n) {Link_Item rab =(Link_Item)calloc(1,sizeof(Item));rab->node=elem; rab->next=n; return rab; }void Item_Delete(Link_Item a) { free(a); }30Узел.ДействияT Item_get_node(const Link_Item a) {return a->node; }Link_Item Item_get_next(Link_Item a) {return a->next; }31Стек.Конструкцияисостояниеtypedef struct stack { Link_Item Top; } Stack;Link_Stack Stack_ini(Link_Stack a) {return a =(Link_Stack)calloc(1,sizeof(Stack)); }Link_Stack Stack_Delete(Link_Stack a) {free(a); return NULL; }int Stack_Is_Empty(const Link_Stack a) {return a->Top==NULL; }32Стек.Действияvoid Stack_push(Link_Stack a, T elem) {a->Top=Item_Create(elem,a->Top); }T Stack_pop(Link_Stack a) {if(Stack_Is_Empty(a))ERR("Stack::pop: empty stack");Link_Item p = a->Top;T rab = Item_get_node(p);a->Top = Item_get_next(p);Item_Delete(p);return rab;}33Очередь.Конструкцияисостояниеtypedef struct queue {Link_Item Head; Link_Item Tail; } Queue;Link_Queue Queue_ini(Link_Queue a) { return a =(Link_Queue)calloc(1,sizeof(struct Queue));}Link_Queue Queue_Delete(Link_Queue a) {free(a); return NULL; }int Queue_Is_Empty(const Link_Queue a) {return a->Head==NULL; }34Очередь.Действияvoid Queue_put(Link_Queue a, T elem) {if(Queue_Is_Empty(a))a->Tail=a->Head=Item_Create(elem,NULL);еlse a->Tail =(a->Tail->next = Item_Create(elem,NULL)); }T Queue_get(Link_Queue a) {if(Queue_Is_Empty(a))ERR("Queue::get: gueue is empty");Link_Item p = a->Head;T rab = Item_get_node(p);a->Head = Item_get_next(p);Item_Delete(p);if(Queue_Is_Empty(a)) a->Tail=NULL;return rab; }35Список.Конструкцияисостояниеtypedef struct list {Link_Item Front;Link_Item Back;} List;Link_List List_ini(Link_List a) {return a = (Link_List)calloc(1,sizeof(List));}int List_Is_Empty(Link_List a) {return a->Front==NULL; }36Список.Операции.ПоискLink_Item List_Find(Link_List a,Link_Item *F,T key ) {if(List_Is_Empty(a)) return (*F=NULL);Link_Item ptr = *F = a->Front;if(Item_get_node(*F)==key) return NULL;while((*F=Item_get_next(ptr))!=NULL) {if(Item_get_node(*F)==key) break; ptr=*F; }return ptr; }37Список.Операции.Добавление 1void List_Insert_front(Link_List a, T elem) {a->Front = Item_Create(elem,a->Front);if(a->Back==NULL) a->Back = a->Front; }int List_Insert_back(Link_List a, T elem) {if(List_Is_Empty(a))a->Front = a->Back = Item_Create(elem,NULL);elsea->Back =(a->Back->next =Item_Create(elem,NULL)); }38Список.Операции.Добавление 2int List_Insert_after(Link_List a,T elem,T after) {Link_Item c;List_Find(a,&c,after);if(c==NULL) return 0;c->next=Item_Create(elem,Item_get_next(c));return 1; }39Список.Операции.Удаление1T List_Remove_front(Link_List a) {if(List_Is_Empty(a))ERR("List::Remove_front: list is empty");Link_Item p=a->Front; T rab=Item_get_node(p);a->Front=Item_get_next(p); Item_Delete(p);if(a->Front==NULL) a->Back=NULL; return rab; }int List_Remove(Link_List a, T key) {Link_Item b; Link_Item c;b=List_Find(a,&c,key);if(c==NULL) return 0;if(b==NULL) a->Front=Item_get_next(a->Front);else b->next=Item_get_next(c);Item_Delete(c); return 1; }40Список.Операции.Удаление2T List_Remove_back(Link_List a) {if(List_Is_Empty(a))ERR("List::Remove_back: list is empty");Link_Item p=a->Front;T rab = Item_get_node(a->Back);if(a->Front==a->Back)a->Front = a->Back = NULL;else { while(p->next!=a->Back) p=p->next;a->Back=p; p=p->next; a->Back->next=NULL; }Item_Delete(p); return rab; }41Список.Операции.Разворотvoid List_Revers(Link_List a) {Link_Item p=NULL;while(a->Front!=NULL)p=Item_Create(List_Remove_front(a),p);a->Front=p;while(Item_get_next(p)!=NULL)p=Item_get_next(p);a->Back=p; }42Список.Операции.Сортировкаvoid List_Sort (Link_List a,int (*f)(const T a, const T b)) {Link_Item F=0;while(a->Front!=NULL){Link_Item p = a->Front;T rab = Item_get_node(p);while(p=Item_get_next(p))if(f(p->node,rab)>0)rab=Item_get_node(p);F=Item_Create(rab,F); List_Remove(a,rab); }a->Front = F;while(F->next) F=F->next;a->Back=F;}43SQL.H(1)44SQL.H(2)45SQL.H(3)46t_int.c (1)47t_int.c (2)48t_int.c (3)49t_str.c (1)50t_str.c (2)51t_str.c (3)52t_str.c (4)53ЕщёпонятияПолиморфизм¢ Шаблонфункции¢ Инкапсуляция¢ Класс¢ Шаблонкласса¢54Полиморфизмразныефункциисодинаковымименемиразличнымипараметрамиint abs(int a) { return a>=0?a:-a; }double abs(double a) { return a>=0?a:-a; }55Шаблоныфункцийtemplate<typename T> T abs(T a) {return a>=0?a:-a; }int x; …y = abs(x); // int abs(int);float u; … v = abs(u); // float abs(float);56Инкапсуляцияcomplex a, b(1.,2.);struct complex { float Re,Im;complex() { Re = Im = 0; }complex(float R, float I) { Re=R; Im=I; }float abs() { return sqrt(Re*Re + Im*Im); }complex operator+(complex a) {return complex(Re+a.Re, Im+a.Im);}};ostream& operator<<(ostream& a,const complex& b){return a << ′(′ << b.Re << ′,′ << b.Im << ′)′<< endl; }a.abs();a.operator+(b); // a+b;57Классclass complex { float Re,Im;public:complex() { Re = Im = 0; }complex(float R, float I) { Re=R; Im=I; }float abs() { return sqrt(Re*Re + Im*Im); }complex operator+(complex a) {return complex(Re+a.Re, Im+a.Im); }friend ostream& operator<<(ostream& a, const complex& b) {return a << ′(′ << b.Re << ′,′ << b.Im << ′)′<< endl; }};58Шаблонклассаtemplate<typename T> class complex {T Re,Im;public:complex(T R=0, T I=0) { Re=R; Im=I; }T abs() { return sqrt(Re*Re + Im*Im); }complex operator+(complex a) {return complex(Re+a.Re, Im+a.Im); }friend ostream& operator<<(ostream& a, constcomplex& b) {return a << ′(′ << b.Re << ′,′ << b.Im <<′)′;}};59Использованиешаблонакласса#include <iostream>using namespace std;#include "complex.h"int main() {complex<double> a(1.,2.),b,c(2.,2.);b = a + c;cout << "|b|= " << b.abs() << endl;return 0; }60Шаблонузланабораданныхtemplate <typename T> class Item {T node; Item* next;public:Item(const T& elem, Item* n=0) {node=elem; next=n;}T& get_node() { return node; }Item* &get_next() { return next; }};61ШаблонклассаStacktemplate <typename T> class Stack {Item<T> *top; T rab;public:Stack() { top = 0; }void push(const T& elem) {top=new Item<T>(elem,top); }T& pop() {if(!top) ERR("Stack::pop: empty stack");rab = top->get_node(); Item<T> *p=top;top = p->get_next(); delete p; return rab; }bool empty() {return top == 0; }};62ШаблонклассаQueue (1)template <typename T> class Queue {Item<T> *head,*tail; T rab;public:Queue() { tail = head =0; }bool empty() { return head == 0;}void put(const T& elem) {if(tail==0) tail = head = new Item<T>(elem);else tail = (tail->get_next() =new Item<T>(elem));}63ШаблонклассаQueue (2)T& get() {if(!head) ERR("Queue::get: queue is empty");Item<T> *p=head;rab = head->get_node();head=head->get_next();delete p;if(head==0) tail=0;return rab;}}; // template <typename T> class Queue64ШаблонклассаList (1)template <typename T> class List {Item<T> *front,*back; T rab;Item<T>* find(Item<T>* &F, const T& k) {if(front==NULL) return (F=NULL);Item<T> *ptr=F=front;if(front->get_node()==k) return 0;while((F=ptr->get_next())!=NULL) {if(F->get_node()==k) break; ptr=F; }return ptr;}65ШаблонклассаList (2)public:List() { front = back =0; }bool empty() { return front==0; }void push_back(const T& elem) {if(back==0) front = back = new Item<T>(elem);else back = (back->get_next() = newItem<T>(elem)); }66ШаблонклассаList (3)T& pop_back() {if(back==0)ERR("List::pop_back: list is empty");rab=back->get_node();Item<T> *p=front;if(front==back) front = back = 0;else {while(p->get_next()!=back) p=p->get_next();back=p;p=p->get_next();back->get_next()=0;}delete p;return rab; }67ШаблонклассаList (4)bool insert_after(const T& k,const T& after){Item<T> *c;find(c,after);if(c==0) return 0;c->get_next()=new Item<T>(k,c->get_next());return 1;}68ШаблонклассаList (5)bool remove(const T& k) {Item<T> *b,*c;b=find(c,k);if(c==NULL) return 0;if(b==NULL) {front=front->get_next(); delete (c); }else {b->get_next()=c->get_next(); delete(c); }return 1;}void push_front(const T& elem) {front = new Item<T>(elem,front);if(back==0) back = front; }69ШаблонклассаList (6)T& pop_front() {if(front==0)ERR("List::pop_front: list is empty");Item<T> *p=front; rab = p->get_node();front=p->get_next(); delete p;if(front==0) back=0;return rab; }70ШаблонклассаList (7)void sort() { Item<T> *D=0;while(front!=0) {Item<T> *p=front; rab = front->get_node();while(p=p->get_next())if(p->get_node()>rab)rab=p->get_node();D = new Item<T>(rab,D); remove(rab); }front = D; back = front;while(back->get_next()!=0)back=back>get_next();}71ШаблонклассаList (8)void revers() { Item<T> *D=0;while(front!=0) D = newItem<T>(pop_front(),D);front = D; back=front;while(back->get_next()!=0)back=back>get_next();}72ШаблонклассаList (9)T& operator[](int i) {Item<T>* p=front;while(i-- && p) p=p->get_next();if(p) return p->get_node();ERR("LIST::operator[]: end of List appear");}friend ostream& operator<<(ostream& out, const List<T>& a) {Item<T>* p=a.front;while(p) {out << p->get_node() << ' ';p=p->get_next(); }return out; }}; // template <typename T> class List73Пример 17475767778Пример2:вычислениеплощадипрямоугольнойфигуры,заданнойпроизвольнымперечислениемкоординатвершин#include <iostream>#include <fstream>#include “SQL.h» /* Файл с описанием шаблоновСтека, Очереди и Cписка*/using namespace std;79(X2,Y2)(X1,Y1)Вычислениеплощадифигуры(X3,Y3)(X4,Y4)S= +x3*y3- x4*y4- x2*y2+x1*y180classpoint{int x,y;public:point(int a=0,intb=0){x=a;y=b;}friendostream&operator<<(ostream&a,constpoint&b){returna<<'('<<b.x <<','<<b.y <<')';}friendistream&operator>>(istream&a,point&b){returna>>b.x >>b.y;}bool operator>(constpoint&b){if(x==b.x)returny>b.y;elsereturnx>b.x;}bool operator!=(constpoint&b){returnx!=b.x ||y!=b.y;}bool operator==(constpoint&b){returnx==b.x &&y==b.y;}pointoperator!(){returnpoint(y,x);}int operator[](int i){returni==1?x:y;}};81int main(){List<point>Sx, Sy;pointa,b; int i,k,s=0;ifstream in("test_sq.dat");while(in>>a){Sx.push_front(a);Sy.push_front(!a);}Sx.sort(); Sy.sort(); a=b=Sx[0];do{for(i=k=0;Sx[i][1]<a[1];i++);while(a[1]==Sx[i][1]&&Sx[i][2]<a[2])i++,k++;if(k%2)i--;elsei++;a=!Sx[i];s-=a[1]*a[2];for(i=k=0;Sy[i][1]<a[1];i++);while(a[1]==Sy[i][1]&&Sy[i][2]<a[2])i++,k++;if(k%2)i--;elsei++;a=!Sy[i];s+=a[1]*a[2];}while(a!=b);cout << "S="<<s<<endl;return0;}828384ТипыданныхБазовые¢Указатели¢Составные§ Массивы,строки,§ Структуры,объединения,перечисления¢Абстрактные§ Списки§ Очереди§ Стеки…¢85.

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций