![]() Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ: ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву ![]() Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Линейный однонаправленный списокСодержание книги Поиск на нашем сайте
Так же как и в Паскале, используя указатели, в C++ можно создавать линейные динамические структуры – линейные списки. В качестве примера рассмотрим простейшую линейную динамическую структуру – линейный однонаправленный список. Базовый элемент для линейного однонаправленного списка должен содержать два поля: указательного типа (указатель на следующий базовый элемент) и информационное поле - для записи значения, помещаемого в список. Будем рассматривать списки, информационное поле которых имеет целый тип int. В этом случае базовый тип для линейного однонаправленного списка можно определить так: struct node { node * next; int el; }; Здесь структура node определена рекурсивно, при этом в явном виде указательный тип (указатель на node) не определен. Лучше определить базовую структуру node так, чтобы указатель на нее был также определен явно. При этом по аналогии с прототипом (предописанием) функции используют прототип структуры: struct node; //прототип структуры typedef node* ref; //явное определение указательного типа ref struct node{ //определение структуры ref next; int el; }; Такая базовая структура позволяет построить линейный однонаправленный список, поскольку содержит поле-указатель. Список может быть сформирован как с заглавным элементом, так и без заглавного элемента. Пусть теперь в программе объявлен указатель на структуру node и создана сама динамическая структура: ref a; a=new node; //динамическая структура Доступ к полям этой динамической структуры возможен с помощью операции разадресации: (*a).next – указатель на следующий элемент, (*a).el - информационное поле. Скобки здесь обязательны, поскольку в C++ действует мнемоническое правило: «суффикс всегда сильнее префикса», т.е. применительно к нашему примеру при отсутствии скобок сначала выполнялась бы точка, а затем - звездочка. Более кратко эти выражения записываются с помощью специального оператора ->, который предназначен для доступа к полям структуры через указатель: a->next – указатель на следующий элемент, a->el - информационное поле. В качестве примера рассмотрим операции формирования линейного однонаправленного списка с заглавным элементом с последующим выводом его на экран. Пример (формирование и вывод линейного однонаправленного списка):
#include <iostream.h> struct node; typedef node* ref; struct node{ ref next; int el; }; Void main() { ref list=NULL, cur=NULL; // указатели на первый и текущий элемент list=new node; //инициализация первого элемента cout <<"\ninput number: "; cin >>(* list).el; //ввод первого числа (*list).next=NULL; //указатель на следующий элемент cur=list; //указатель на текущий элемент списка while (a!=0) { // последнее число равно нулю – признак конца ввода (*cur).next=new node; //инициализация следующего элемента cur=(*cur).next; //перевод указателя на следующий элемент cout <<"\ninput number: "; cin >>(*cur).el; //ввод следующего числа } (*cur).next=NULL; //поле-указатель последнего элемента cur=list; //указатель на первый элемент while (cur!=NULL){ //элемент существует cout <<=(*cur).el <<' '; //вывод числа на экран cur=(*cur).next; //переход к следующему элементу списка } } Недостаток такой организации списка состоит в том, что первый элемент, содержащий данные в информационном поле el, формируется вне цикла. Избежать этого неудобства позволяет использование списка с заглавным элементом, в котором информационное поле формируемого вне цикла первого элемента остается свободным или используется для размещения некоторого идентификатора списка. Это позволяет все помещаемые в список данные обрабатывать однотипно внутри цикла. Списки с заглавным элементом во многих случаях более удобны для обработки и поэтому используются очень часто. В дальнейшем мы также в большинстве случаях будем рассматривать именно такие списки. Алгоритм формирования и вывода линейного однонаправленного списка с заглавным элементом может быть записан в следующем виде: #include <iostream.h> struct node; typedef node* ref; struct node{ ref next; int el; }; Void main() { ref list=NULL, cur=NULL; // указатели на заглавный и текущий элемент list=new node; //инициализация заглавного элемента cur=list; //указатель на текущий элемент списка (*list).next=NULL; //указатель на следующий элемент do{ (*cur).next=new node; //инициализация следующего элемента cur=(*cur).next; //перевод указателя на следующий элемент cout <<"\ninput number: "; cin >>(*cur).el; //ввод следующего числа } while (a!=0); // последнее число равно нулю – признак конца ввода (*cur).next=NULL; //поле-указатель последнего элемента cur=(*list).next; //указатель на первый элемент после заглавного while (cur!=NULL){ //элемент существует
cout <<(*cur).el <<' '; //вывод числа на экран cur=(*cur).next; //переход к следующему элементу списка } } Здесь использован цикл с постусловием, поскольку признак конца вводимой последовательности (число 0) входит в эту последовательность, т.е. является ее последним членом. Аналогично может быть определена любая операция над линейным однонаправленным списком: инициализация, поиск, вставка и удаление элемента. Будем обозначать эти операции InitList, SeekList, InsList и DelList соответственно. Будем рассматривать эти операции применительно к списку с заглавным элементом в предположении, что типы ref и node определены глобально. void InsertList(ref &cur, int a){ //вставка после cur значения a ref q; q=new node; //новый элемент q->el=a; //занесение значения a в новый элемент q->next=cur->next; cur->next=q; //включение нового элемента в список } Динамический стек
Пример (стек - помещение и выбор слова): #include <iostream.h> struct node; typedef node* ref; struct node{ ref next; char el; }; enum bool{false, true}; void InitStack(ref &top); bool CheckStack(ref top); void PutStack(ref &top, char a); char OutStack(ref &top); Void main() { ref Top; char a; InitStack(Top); cout <<"\ninput word: "; do{ cin >>a; PutStack(Top,a); } while (a!='.'); while (CheckStack(Top)==true){ a=OutStack(Top); cout <<a; } } void InitStack(ref &top){ top=NULL; } bool CheckStack(ref top){ if (top==NULL) return false; else return true; } void PutStack(ref &top, char a){ ref q; q=new node; (*q).el=a; (*q).next=top; top=q; } char OutStack(ref &top){ ref q; char a=(*top).el; q=top; top=(*top).next; delete q; return a; }
Оценка алгоритмов
Пример 1 (поиск максимального/минимального элемента массива): const int n; int mas[n]; …. int max=mas[0]; for (int i=1; i<n; i++) if (mas[i]>max) max=mas[i];
Пример 2 (поиск первого/последнего элемента по условию): const int n; int mas[n], a; …. int i=0; while ((i<n) && (mas[i]!=a)) i++; Пример 3 (замена каждого элемента суммой последующих): Вариант 1 const int n; int mas[n]; …. for (int i=0; i<n; i++){ mas[i]=0; for (int j=i+1; j<n; j++) mas[i]+=mas[j]; }
Вариант 2 const int n; int mas[n]; …. int sum=0; for (int i=n-1; i>=0; i--){ int p=sum; sum+=mas[i]; mas[i]=p; }
Пример 4 (умножение матриц): const int n; typedef array int[n][n]; array a,b,c; …. for (int i=0; i<n; i++) for (int j=0; j<n; j++){ c[i][j]=0; for (int k=0; k<n; k++) c[i][j]= c[i][j]+a[i][k]*b[k][j]; }
Рекурсия
Пример (факториал и НОД): #include <iostream.h> long int fact(int n); void fact(int n, long int &nfact); int NOD(int m, int n); Void main() { int m, n; long int k; cout <<"\ninput n: "; cin >>n; cout <<"\nFACT=" <<fact(n) <<'\n'; fact(n, k); cout <<"\nFACT=" <<k <<'\n'; cout <<"\ninput m n:"; cin >>m >>n; cout <<"\nNOD(" <<m <<',' <<n <<")=" <<NOD(m,n) <<'\n'; } long int fact(int n){ if (n<0) {cout <<"\nmistake "; return n;} else if (n==0) return 1; else return n*fact(n-1); } void fact(int n, long int &nfact){ long int m; if (n<0) {cout <<"\nmistake "; nfact=n;} else if (n==0) nfact=1; else {fact(n-1,m); nfact=n*m;} } int NOD(int m, int n){ if (m==n) return m; else if (m<n) return NOD(m, n-m); else return NOD(m-n, n); }
Пример (Ханойская башня): #include <iostream.h> void Hanoi(char x, char y, char z, int n); Void main() { int n; cout <<"\ninput n: "; cin >>n; Hanoi('A', 'B', 'C', n); } Void Hanoi(char x, char y, char z, int n) { if (n>0){ Hanoi(x, z, y, n-1); cout <<"\nfrom "<<x<<" to "<<y; Hanoi(z, y, x, n-1); } }
Пример (тур коня): #include <iostream.h> const n=8; int D[n][n]; void step(int i, int x, int y, int &q); Void main() { int i, j, x0, y0, q; for(i=0; i<n; i++) for(j=0; j<n; j++) D[i][j]=0; cout <<"input xo yo: "; cin >>x0,y0; D[x0][y0]=1; step(2,x0,y0,q); if(q==1) for(i=0; i<n; i++){ cout <<'\n'; for(j=0; j<n; j++) cout <<D[i][j] <<' '; } else cout <<" no result"; } void step(int i, int x, int y, int &q) { int u,v,k,q1; int dx[8]={2,1,-1,-2,-2,-1,1,2}, dy[8]={1,2,2,1,-1,-2,-2,-1}; k=-1; do{ k++; q1=0; u=x+dx[k]; v=y+dy[k]; if((D[u][v]==0) && (u>=0) && (u<n) && (v>=0) && (v<n)){
D[u][v]=i; if(i==n*n) q1=1; else{ step(i+1,u,v,q1); if (q1==0) D[u][v]=0; } } } while ((q1==0) && (k<7)); q=q1; }
Поиск
Пример (алгоритмы поиска):
Линейный поиск #include <iostream.h> const n=10, n1=11; int SeekLine(int* mas, int n, int a, int &ind); int SeekBar(int* mas, int n, int a, int &ind); Void main() { int num, a, m[n], m1[n1]; cout <<"\ninput "<<n<<" number: "; for(int i=0;i<n;i++){ cin >>m[i]; m1[i]=m[i]; } cout <<"input a: "; cin >>a; if (SeekLine(m, n, a, num)==0) cout <<"\nNO\n"; else cout <<'\n'<<num+1<<'\n'; num=0; if (SeekBar(m1, n, a, num)==0) cout <<"\nNO\n"; else cout <<'\n'<<num+1<<'\n'; } int SeekLine(int* mas, int n, int a, int &ind){ ind=0; while((mas[ind]!=a) && (ind<=n)) ind++; if(ind<n) return 1; else return 0; } int SeekBar(int* mas, int n, int a, int &ind){ mas[n]=a; ind=0; while(mas[ind]!=a) ind++; if(ind<n) return 1; else return 0; }
Двоичный поиск (дихотомия) #include <iostream.h> const n=10; int Dixotom(int* mas, int n, int a, int &ind); Void main() { int num, a, m[n]; cout <<"\ninput "<<n<<" number: "; for(int i=0; i<n; i++) cin >>m[i]; cout <<"input a: "; cin >>a; num=0; if (Dixotom(m, n, a, num)==0) cout <<"\nNO\n"; else cout <<'\n'<<num+1<<'\n'; } int Dixotom(int* mas, int n, int a, int &ind){ int l=0, r=n-1; do{ ind=(l+r)/2; if(mas[ind]<a) l=ind+1; else r=ind-1; } while((l<=r) && (mas[ind]!=a)); if(mas[ind]==a) return 1; else return 0; }
Сортировка
Пример (алгоритмы внутренней сортировки): #include <iostream.h> #include <cstdlib> #include <iostream> using namespace std; void IncludeSort(int* mas, int n); void SelectSort(int* mas, int n); void BubbleSort(int* mas, int n); void ModBubbleSort(int* mas, int n); void QuickSort(int* mas, int n); Int main() { const int n=10; int i; int a[n]; cout <<"\nВведите " <<n <<" чисел: "; for(i=0;i<n;i++) cin >>a[i]; cout <<"\nНомер алгоритма сортировки: "; cin >>i; switch(i){ case 1: IncludeSort(a,n); break; case 2: SelectSort(a,n); break; case 3: BubbleSort(a,n); break; case 4: ModBubbleSort(a,n); break; case 5: QuickSort(a,n); break; default: cout << "\nНекорректный номер\n"; } for(i=0;i<n;i++) cout <<' '<<a[i]; cout <<'\n'; system("PAUSE"); return EXIT_SUCCESS; } void IncludeSort(int* mas,int n){ int b; for (int i=1;i<n;i++){ b=mas[i]; int j=i-1; while ((j>=0) && (mas[j]>b)){ mas[j+1]=mas[j]; j--; } mas[j+1]=b; } } void SelectSort(int* mas, int n){ int m,b; for(int i=0;i<n-1;i++){ m=i; for(int j=i+1;j<n;j++) if(mas[j]<mas[m]) m=j; b=mas[i]; mas[i]=mas[m]; mas[m]=b; } } void BubbleSort(int* mas,int n){ int b; for(int i=1;i<n;i++) for(int j=n-1;j>=i;j--) if(mas[j]<mas[j-1]){ b=mas[j]; mas[j]=mas[j-1];mas[j-1]=b; } } void ModBubbleSort(int* mas,int n){ int b,sig=0; int i=1; while((i<n) && (sig==0)){ sig=1; for(int j=n-1;j>=i;j--) if(mas[j]<mas[j-1]){ b=mas[j];mas[j]=mas[j-1];mas[j-1]=b;sig=0; } i++; } } void Sort(int* mas,int n,int l,int r){ int i,j,b; i=l; j=r; int m=mas[(l+r)/2]; do{ while(mas[i]<m) i++; while(mas[j]>m) j--; if(i<=j){ b=mas[i]; mas[i]=mas[j]; mas[j]=b; i++; j--; } } while (i<=j); if(l<j) Sort(mas,n,l,j); if(i<r) Sort(mas,n,i,r); } void QuickSort(int* mas,int n){ Sort(mas,n,0,n-1); }
|
|||||||
Последнее изменение этой страницы: 2016-08-15; просмотров: 947; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.226.185.20 (0.007 с.) |