Линейные списки (Си)

[omg_fap_fap]

Составить и отладить программу на языке Си для обработки линейного списка заданной организации с отображением на динамические структуры. Навигацию по списку следует реализовать с применением итераторов. Тип элементов списка — целый.

Вид списка - кольцевой однонаправленный.
Доп. действие: Выполнить попарный обмен значениями элементов списка.


Кольцевой отличается от линейного тем, что последний элемент содержит указатель на первый.

[omg_fap_fap]

Кольцевой двунаправленный:

#include "stdio.h"
#include "stdlib.h"

#define FAIL 0
#define OK 1//кольцевой двун

typedef struct NODE {
  int value;
  struct NODE *next;
  struct NODE *prev;
} Node;

typedef struct LIST {
  Node* head;
  Node* last;
  int length;
} List;

Node* CreateNode(int a_value) {
  Node* res = (Node *) malloc(sizeof(Node));
  res->value = a_value;
  res->next = NULL;
  res->prev = NULL;
  return res;
}

List* CreateList() {
  List* list = (List *) malloc(sizeof(List));
  list->head = NULL;
  list->last = NULL;
  list->length = 0;
  return list;
}

void AddNode(List *a_list, int a_value) {
  Node* node = CreateNode(a_value);
  //printf("%d\n", node->value);
  if(a_list->head == NULL) {
      a_list->head = node;
      a_list->last = node;
    }
  else {
      a_list->last->next = node;
    }
  node->prev = a_list->last;
  a_list->last = node;
  a_list->last->next = a_list->head;
  a_list->head->prev = a_list->last;
  a_list->length++;
}

int InsertNode(List *a_list, int pos, int a_value) {
    Node* node = CreateNode(a_value);
    Node* iter = a_list->head;
    int counter;
    if(pos >= a_list->length)
        return FAIL;
    for(counter = 0; counter < pos; counter++)
        iter = iter->next;
    node->prev = iter->prev;
    node->next = iter;
    iter->prev->next = node;
    iter->prev = node;
    if(pos == 0) {
        a_list->head = node;
        //a_list->last->next = node;
    }
    a_list->length++;
    return OK;
}

int ExtendList(List *a_list, int s, int value) {
    int i;
    if(a_list->length >= s) {
        return FAIL;
    }
    else {
        for(i = a_list->length; i < s; i++)
            AddNode(a_list, value);
        return OK;
    }
}

void PrintList(List* a_list) {
  Node *iter = NULL;
  if(a_list->length == 0)
    printf("List is empty\n");
  else {
      printf("List:\n");
      iter = a_list->head;
      for(;;) {
            printf("%d ", iter->value);
            iter = iter->next;
            if(iter == a_list->head)
                break;
        }
      printf("\n");
    }
}

int DeleteNode(List* a_list, int a_value) {
  Node* iter = NULL, *prev_iter;
  if(a_list->length == 0)
    return FAIL;
  iter = a_list->head;
  while(iter->value != a_value)
    {
      prev_iter = iter;
      iter = iter->next;
      if(iter == a_list->head)
            return FAIL;
    }
  if(a_list->length == 1)
    {
      free(iter);
      a_list->head = a_list->last = NULL;
    }
  else if(iter == a_list->head)
    {
      a_list->head = a_list->head->next;
      a_list->head->prev = a_list->last;
      a_list->last->next = a_list->head;
      free(iter);
    }
  else if(iter == a_list->last)
    {
      a_list->last = prev_iter;
      free(iter);
      a_list->last->next = a_list->head;
      a_list->head->prev = a_list->last;
    }
  else
    {
      prev_iter->next = iter->next;
      iter->next->prev = prev_iter;
      free(iter);
    }

  a_list->length --;
  return OK;
}

int get_number(int* target)
{
    int c;
    for(;;)
    {
        c = getchar();
        if(c >= '0' && c <= '9')
        {
            ungetc(c, stdin);
            scanf("%d", target);
            //printf("%d\n", *target);
            return OK;
        }
        else if(c == 's')
            return FAIL;
    }
}

int main() {
    List* l = CreateList();
    int c, arg1, arg2;
    printf("(a)ppend (i)nsert (p)rint (f)unction (e)xit (d)elete \n");
    for(;;) {
        c = getchar();
        switch(c) {
            case 'a': {
                if(1 == scanf("%d", &arg1))
                    AddNode(l, arg1);
				else	{
					printf("Incorrect\n");
					return 1;
				}
                break;
            }
            case 'i': {
                if(l->length == 0) {
                	if(1 == scanf("%d", &arg1))
                        AddNode(l, arg1);
					else {
						printf("Incorrect\n");
						return 1;
					}
                }
                else {
                    if(2 == scanf("%d %d", &arg1, &arg2))
                        InsertNode(l, arg1, arg2);
					else {
						printf("Incorrect\n");
						return 1;
					}
                }
                break;
            }
            case 'p': {
                PrintList(l);
                break;
            }
            case 'd': {
               	if(1 == scanf("%d", &arg1))
                   !DeleteNode(l, arg1);
				else {
					printf("Incorrect\n");
					return 1;
				}
                break;
            }
            case 'l':
            {
                printf("%d\n", l->length);
                break;
            }
            case 'e': {
                return 0;
            }
            case 'f': {
                if(2 == scanf("%d %d", &arg1, &arg2))
                    ExtendList(l, arg1, arg2);
				else	{
						printf("Incorrect\n");
						return 1;
					}
                break;
            }
        }
    }
}

[omg_fap_fap]

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

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

typedef struct NODE{
  struct NODE* next;
  double value;
}Node;

typedef struct LIST{
  Node* head;
  Node* last;
  int size;
}List;


Node* CreateNode(double a_value){
  Node* res = (Node *)malloc(sizeof(Node));
  res->value = a_value;
  res->next = NULL;
  return res;
}

List* CreateList(){
  List* list = (List *)malloc(sizeof(List));
  list->head = NULL;	
  list->last = NULL;
  list->size =0;
  return list;
}

void AddNode(List* a_list,double a_value){  //vstavka v konec
  Node* node = CreateNode(a_value);
  if(a_list->head == NULL){
    a_list->head = node;
  }
  else{
    a_list->last->next = node;
    a_list->last = node;
    a_list->size++;
  }
}


//vstavka po indeksu
void Insert(List* a_list,int index,double a_value){ 
  if(index > a_list->size)
    index = a_list->size;
  if(index == 0){	
    Node* node = CreateNode(a_value);
    if(a_list->head == NULL){
      a_list->head = node;
    }
    else{
      node->next = a_list->head;
      a_list->head = node;
    }
    a_list->size++;
  }	
  else{
    Node* node = CreateNode(a_value);
    Node* current = a_list->head;
    int i;
    for(i = 0;i < index-1 && current->next != NULL; i++)
      current = current->next;
      node->next = current->next;
      current->next = node;
      a_list->size++;
  }
}

void PrintList(List* a_list){
  Node* iter = NULL;
  if(a_list->size == 0)
  printf("List is empty\n");
  else{
    printf("List:\n");
    iter = a_list->head;
    while(iter!= NULL){
      printf("%lf ",iter->value);
      iter = iter->next;
    }
    printf("\n");
  }
}

Node* Prev(Node* iter, List* a_list);
int DeleteNode(List* a_list,Node* iter){
  if (a_list->size == 0){
    return 0;
  }
  if(iter == NULL){
    return 0;
  }
  if(a_list->size == 1){
    free(iter);
    a_list->head = a_list->last = NULL;
  }
  else if (iter == a_list->head){
	a_list->head = a_list->head->next;
		free(iter);
		}
	else if(iter == a_list->last){
		a_list->last = Prev(iter, a_list);
		free(iter);
		a_list->last->next = NULL;
		}
	else {
		Prev(iter, a_list)->next = iter->next;
		free(iter);
	}

	a_list->size--;
	return 1;
}

Node* Prev(Node* iter,List* a_list){
	if (iter == a_list->head)
		return NULL;
	Node* tmp = a_list->head;
	while(tmp !=a_list->last && tmp->next != iter){
	tmp = tmp->next;	
	}
return tmp;
}

Node* search(List* a_list, double value){
	Node* iter = a_list->head;
	if (a_list->size == 0)
		return NULL;
	while (iter != NULL)
		if (iter->value == value)
			return iter;
	return NULL;	
}


bool function(List* a_list,double a_value)
{

	if(a_list->size == 0 || a_list->size == 1)
		return false;
	
	Node* iter;
	Node* m[250];
	int k = 0;
	int i;
	iter = a_list->head;
	while (iter != NULL){
		if (iter->value == a_value){	
			if(iter->next != NULL){
				m[k] = iter->next;
				k++;
			}
			bool f = false;
			int p;
			if(Prev(iter,a_list) != NULL){
			 for (p = 0; p<k; p++)
				f = f || (m[p] == Prev(iter, a_list));
			if (!f){
				m[k] = Prev(iter,a_list);
				k++;
				}
			  }
			}
		iter = iter->next;
		}
		for(i = 0;i<k;i++){
			DeleteNode(a_list,m[i]);
			}
	return true;
}
void instructions(void){
	printf("Please,enter your choice:\n"
		"1 to print list.\n"
		"2 to insert an element into the list.\n"
		"3 to delete an element from the list.\n"
		"4 function.\n");
}

int main(){

	List* l = CreateList();
	int code;
	int index;
	char key[100];
	double item;
	instructions();	
	while(scanf("%d",&code) !=1){
		scanf("%s",&key[0]);
		printf("Error!");
		}
		while(code !=-1){
			switch(code){
				case 1:
					PrintList(l);
					while(scanf("%d",&code) != 1){
						scanf("%s",&key[0]);
						printf("Error!");
					}
					break;
				case 2:
					printf("add: ");
					scanf("%d",&index);
					scanf("%lf",&item);
					Insert(l,index,item);
					while(scanf("%d",&code) !=1){
						scanf("%s",&key[0]);
						printf("Error!");
						}
					break;
				case 3:
					printf("Delete: ");
					scanf("%lf",&item);
					Node* item_ptr = search(l, item);
					if (item_ptr)
						DeleteNode(l,item_ptr);
					else
						printf("Not found\n");
					while(scanf("%d",&code)!=1){
						scanf("%s",&key[0]);
						printf("Error!");
						}
					break;
				case 4:
					printf("function\n");
					printf("Vvedite znachenie uzla: ");
					scanf("%lf",&item);
					 function(l,item);
					while(scanf("%d",&code) != 1){
						scanf("%s",&key[0]);
						printf("error!");
						}
					break;
				default:
					printf("Command is missing\n");
					printf("Enter the correct code: ");
					scanf("%s",&key[0]);
					scanf("%d",&code);
					break;
				}

	}						
}