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

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

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

Carnegie MellonАбстрактныетипы данных С++Алгоритмыи алгоритмические языкиgoo.gl/c8pyqxЛекция 6, 12 октября, 2018Лектор:Дмитрий Северов, кафедра информатики 608 КПМdseverov@mail.mipt.ruhttp://cs.mipt.ru/wp/?page_id=60771«ЧТО ПОЗВОЛЕНО ЮПИТЕРУ …»#include <stdio.h>#define N …struct { int a[N];} a,b;int main() {…a=b;//разрешено…return 0; }#include <stdio.h>#define N …int a[N],b[N];int main() {…a=b;// ошибка…return 0; }23Пример 4: односвязный список¢¢Определение формата узла спискаstruct node {My_type item;struct node *next;x->item};typedef struct node *link;x………x->nextВыделение памяти для узла спискаlink x = (link)malloc(sizeof(struct node));¢Инициализация элементов узла(*x).item = … , x->next = NULL;4Объединение элементов в список (1)¢Вставка узла t за узлом хt->next = x->next, x->next = t;xt………………………¢Удаление узла t за узлом xt = x->next; x->next=t->next; free(t);x………t………………5Объединение элементов в список (1)¢Вставка узла t за текущим узлом хt->next = x->next, x->next = t;xt………………………¢Удаление узла, следующего за xt = x->next, x->next=t->next, free(t);x………t………6Объединение элементов в список (2)Вставка узла t перед текущим узлом х со сменой текущегоlink g = new node;// новый узел g*g = *x;// g дубль х, перед yt…x->next = g;// g после хx………x->item = t->item;// содержимое t в x……………¢ Удаление узла х со сменой текущего¢link p = x->next;*x = *x->next;delete p;x………p………// к удалению// перенос значения// удаление………7Объединение элементов в список (2)¢¢Вставка узла t перед текущим узлом х со сменой текущегоlink g = new node;// новый узел g*g = *x;// g дубль х, перед yt… x->next = g;// g после хx…… x->item = t->item;…// содержимое t в x……………gУдаление текущего узла х со сменой текущего…link p = x->next;// к удалению……*x = *x->next;// перенос значенияdelete p;// удалениеx………p………89ВведениеПочему типы «абстрактные»?¢ Реализации массивами и структурами¢10СПИСОК, ОЧЕРЕДЬ, СТЕКОчередьFIFO – First In First OutСтекLIFO – Last In First OutСписокCasual In Casual Out11РЕАЛИЗАЦИЯ МАССИВАМИ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*y180class point {int x,y;public:point(int a=0,int b=0) { x=a; y=b; }friend ostream& operator<< ( ostream& a, const point& b) {return a << '(' << b.x << ',' << b.y << ')'; }friend istream& operator>> ( istream& a, point& b) {return a >> b.x >> b.y; }bool operator> (const point& b) {if (x==b.x) return y>b.y; else return x>b.x; }bool operator!= (const point& b) { return x!=b.x || y!=b.y; }bool operator== (const point& b) { return x==b.x && y==b.y; }point operator! () { return point(y,x); }int operator[](int i) { return i==1?x:y; }};81int main() {List<point> Sx, Sy;point a,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--; else i++; 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--; else i++; a=!Sy[i]; s+=a[1]*a[2];} while(a!=b);cout << "S= " << s << endl;return 0; }828384Типы данныхБазовые¢Указатели¢Составные§ Массивы, строки,§ Структуры, объединения, перечисления¢Абстрактные§ Списки§ Очереди§ Стеки…¢85.

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

Тип файла PDF

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

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

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