C++: Односвязный список в консольном приложении

На самом деле, тема уже фигурировала много где - раз, два, три, четыре... Просто здесь - почти законченный пример, делающий следующее: описать структуру, сформировать динамический односвязный список структур; реализовать просмотр списка, добавление элементов в начало и конец, удаление (по ключу или номеру записи), сортировку. Организовать меню для выбора операций над списком.

В начале работы программы список пуст, так что надо добавить записи с клавиатуры. Проверено в Visual C++, работает.

#include <conio.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

struct person { //описание структуры
 char f[30]; //фамилия
 char d[30]; //должность
 float zp,pr; //зарплата, премия
 char prof; //профсоюз
 person *next; //указатель на следующего в списке
}; 

person vvesti() { //ввод элемента с клавиатуры
 person p;
 printf ("\nFIO?"); fflush (stdin); scanf ("%s",p.f);
 printf ("\nDolgnost?"); fflush (stdin); scanf ("%s",p.d);
 printf ("\nZP?"); fflush (stdin); scanf ("%f",&p.zp);
 printf ("\nPremia?"); fflush (stdin); scanf ("%f",&p.pr);
 printf ("\nProf (+/-)?"); fflush (stdin); scanf ("%c",&p.prof);
 return p;
}

int show (person *head) { //показ всего списка с определением количества элементов
 int count=0;
 if (head) while (1) {
  printf ("\n%s %s %.2f+%.2f %c", head->f,head->d,head->zp,head->pr,head->prof);  
  count++;
  if (head->next == NULL) break;
  head = head->next;
 }
 printf ("\nAll=%d",count);
 return count;
}
void search (person *head, char *st) { //поиск в списке строки st
 if (head==NULL) return;
 person *next = head;
 do {
  char *find = strstr (next->f, st);
  if (find!=NULL) printf ("\n%s",next->f);
  if (next->next==NULL) break;
  next = next->next;
 } while (1);
}

void copy1 (person *to, person *from) { //копирование одной записи
 strcpy (to->f, from->f); 
 strcpy (to->d, from->d);
 to->zp = from->zp; to->pr = from->pr; to->prof =  from->prof;
}

person *add1 (person *head, person *st) { //добавление элемента st в начало списка
 //*st уже заполнен данными
 person *current = new person;
 copy1 (current, st); //копирует 1 запись
 if (head==NULL) current->next = NULL;
 else {
  current->next = head;
  head = current;
 }
 return current;
}

person *add2 (person *head, person *st) { //добавление элемента st в конец списка
 person *last = NULL;
 if (head!=NULL) {
  last=head;
  while (last->next!=NULL) last=last->next;
 }
 person *current = new person;
 copy1 (current,st);
 current->next = NULL;
 if (last) last->next = current;
 return current;
}

person *delete1 (person *head0, int n) { //удаление элемента по номеру 1..N
 // удалит элемент номер n и вернет указ.на нач.
 person *head = head0;
 if (head==NULL) return NULL;
 if (n==1) { //удаляем первый
  person *ptr = head->next;
  delete head;
  return ptr;
 }
 person *prev = NULL, *start = head; int i=1;
 while (i<n) { //Ищем n-ый элемент
  prev = head; head = head->next;
  if (head==NULL) return start;
  i++;
 }
 person *ptr = head->next;
 delete head; 
 
 prev->next = ptr;
 return start;
}

person *sort (person *ph) { //сортировка списка методом вставок
 person *q, *p, *pr, *out=NULL;
 while (ph != NULL) {
  q = ph; ph = ph->next; //исключить эл-т
  //ищем, куда его включить:
  for (p=out,pr=NULL ; p!=NULL &&
    strcmp(q->f,p->f)>0; pr=p,p=p->next) ;
    //или ваш критерий, когда переставлять!
  if (pr==NULL) { q->next=out;out=q; } //в нач.
  else { q->next=p; pr->next=q; } //после пред.
 }
 return out;
}

void main() { //меню и главная программа
 person *head = NULL;
 while (1) {
  printf ("\n 1. Show all \
           \n 2. Add in head \
           \n 3. Add in tail \
           \n 4. Delete by number \
	       \n 5. Sort by name \
           \n 0. Exit ");
  fflush (stdin);
  char c;
  scanf ("%c",&c);
  person p;
  person *cur;
  int n, all;
  switch (c) {
   case '1': show (head);
   break;
   case '2': p = vvesti(); head=add1(head,&p);
   break;
   case '3': p = vvesti();
	   cur = add2 (head,&p);
	   if (head==NULL) head=cur;
   break;
   case '4':
    all = show(head);
    while (1) {
     printf ("\nVvedi nomer (1-%d): ",all);
     fflush (stdin); scanf("%d",&n);
     if (n>=1 && n<=all) break;
    }
    head = delete1 (head,n);
   break;
   case '5': head = sort (head);
   break;
   case '0': exit (0); break;
  }
 }
}

---

теги: алгоритм c++ studio

---

07.03.2015, 13:27; рейтинг: 13084