Линейный однонаправленный список

Так же как и в Паскале, используя указатели, в 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);

}