Ja w sumie mam już napisaną całą listę
no może jeszcze można by dodać zapis i odczyt z pliku
Mam takie funkcje
Kod: Zaznacz cały
// funkcje do obsługi stosu i kolejki
Funkcja sprawdzają czy lista jest pusta
Funkcja dodająca węzeł na początek listy
Funkcja dodająca węzeł na koniec listy
Funkcja zdejmująca pierwszy węzeł listy
// funkcje dodające i usuwające węzły
Funkcja dodająca węzeł za węzłem o danym kluczu
Funkcja dodająca węzeł przed węzłem o danym kluczu
Funkcja usuwająca węzeł o danym kluczu
Funkcja usuwająca wszystkie węzły z listy
// funkcje dodatkowe
Funkcja zwracająca liczbę węzłów
Funkcja wyszukująca węzeł o danym kluczu
Funkcja sortująca listę przez scalanie
Funkcja wypisująca dane zawarte w węzłach listy
Plik nagłówkowy
Kod: Zaznacz cały
#ifndef _LISTA_H_
#define _LISTA_H_
struct Node {
int data;
struct Node* next;
};
int isEmpty(struct Node*);
void pushFront(struct Node**,int);
void pushBack(struct Node**,int);
int pop(struct Node**);
void insertNodeBefore(struct Node**,int,int);
void insertNodeAfter(struct Node** ,int ,int );
void deleteNode(struct Node**,int);
void deleteList(struct Node**);
void saveToFile(struct Node* head,char* path);
void loadFromFile(struct Node** head,char* path);
struct Node* findNode(struct Node*,int);
void reverse(struct Node**);
int size(struct Node*);
void printList(struct Node*);
void split(struct Node*,struct Node**,struct Node**);
void merge(struct Node**,struct Node*,struct Node*);
void mergesort(struct Node**);
#endif
Plik z funkcjami obsługującymi listę
Kod: Zaznacz cały
#include<stdio.h>
#include<stdlib.h>
#include "lista.h"
int isEmpty(struct Node* head)
{
return (head==NULL);
}
void pushFront(struct Node** head,int n)
{
struct Node* newNode;
if((newNode=(struct Node*)malloc(sizeof(struct Node)))==NULL)
{
printf("Brak pamieci na wezel
");
return;
}
newNode->data=n;
newNode->next=(*head);
(*head)=newNode;
}
void pushBack(struct Node** head,int n)
{
struct Node* newNode;
struct Node* temp;
if((newNode=(struct Node*)malloc(sizeof(struct Node)))==NULL)
{
printf("Brak pamieci na wezel
");
return;
}
newNode->data=n;
newNode->next=NULL;
if(isEmpty((*head)))
{
(*head)=newNode;
}
else
{
temp=(*head);
while(temp->next!=NULL)
temp=temp->next;
temp->next=newNode;
}
}
int pop(struct Node** head)
{
int val=0;
struct Node* temp;
if(!isEmpty((*head)))
{
temp=(*head);
val=temp->data;
(*head)=(*head)->next;
free(temp);
}
else printf("Struktura jest pusta
");
return val;
}
void deleteNode(struct Node** head,int n)
{
struct Node* aux;
struct Node* previous;
if(isEmpty((*head)))
{
printf("Lista jest pusta
");
}
else
{
aux=(*head);
previous=NULL;
while(aux!=NULL&&aux->data!=n){
previous=aux;
aux=aux->next;
}
if(aux==NULL){
printf("Liczby nie znaleziono na liscie
");
}
else
{
if(previous==NULL)
{
(*head)=(*head)->next;
}
else
{
previous->next=aux->next;
}
free(aux);
}
}
}
void printList(struct Node* head)
{
struct Node* temp;
temp=head;
while(temp!=NULL)
{
printf("%d
",temp->data);
temp=temp->next;
}
}
void deleteList(struct Node** head)
{
while(!isEmpty((*head)))
{
deleteNode(head,(*head)->data);
}
}
struct Node* findNode(struct Node* head,int n)
{
struct Node* temp;
temp=head;
while(temp!=NULL&&temp->data!=n)
temp=temp->next;
return temp;
}
void insertNodeBefore(struct Node** head,int x1,int x2)
{
struct Node* newNode;
struct Node* save;
struct Node* pred;
if((newNode=(struct Node*)malloc(sizeof(struct Node)))==NULL)
{
printf("Brak pamieci na wezel
");
}
newNode->data=x2;
if((*head)==NULL)
{
printf("Wezla nie znaleziono
");
}
else
{
save=(*head);
while(x1!=save->data&&save->next!=NULL)
{
pred=save;
save=save->next;
}
if(save->data==x1)
{
if((*head)==save)
{
newNode->next=save;
(*head)=newNode;
}
else
{
newNode->next=save;
pred->next=newNode;
}
}
else
{
printf("Wezla nie znaleziono
");
}
}
}
void insertNodeAfter(struct Node** head,int x1,int x2)
{
struct Node* newNode;
struct Node* save;
struct Node* pred;
if((newNode=(struct Node*)malloc(sizeof(struct Node)))==NULL)
{
printf("Brak pamieci na wezel
");
return;
}
newNode->data=x2;
if((*head)==NULL)
{
printf("Wezla nie znaleziono
");
}
else
{
save=(*head);
while((x1!=save->data)&&(save->next!=NULL))
{
pred=save;
save=save->next;
}
if(save->data==x1)
{
newNode->next=save->next;
save->next=newNode;
}
else
{
printf("Wezla nie znaleziono
");
}
}
}
void reverse(struct Node ** head)
{
struct Node * temp;
struct Node * curr;
if(!isEmpty((*head)))
{
curr=(*head);
while(curr->next!=NULL)
{
temp=curr->next;
curr->next=temp->next;
temp->next=(*head);
(*head)=temp;
}
}
}
void saveToFile(struct Node* head,char* path)
{
FILE* fp;
struct Node* temp;
if ((fp = fopen(path, "wt"))
== NULL)
{
fprintf(stderr, "Cannot open output file.
");
return ;
}
temp=head;
while(temp!=NULL)
{
fprintf(fp,"%d",temp->data);
temp=temp->next;
}
fclose(fp);
}
void loadFromFile(struct Node** head,char* path)
{
FILE* fp;
int value;
if ((fp = fopen(path, "rt"))
== NULL)
{
fprintf(stderr, "Cannot open input file.
");
return ;
}
while(!feof(fp))
{
fscanf(fp,"%d",&value);
pushFront(head,value);
}
fclose(fp);
}
int size(struct Node* head)
{
int no=0;
struct Node* temp;
temp=head;
while(temp!=NULL)
{
no++;
temp=temp->next;
}
return no;
}
void split(struct Node* head,struct Node** front,struct Node** back)
{
struct Node* slow;
struct Node* fast;
if(head==NULL||head->next==NULL)
{
(*front)=head;
(*back)=NULL;
}
else
{
slow=head;
fast=head->next;
while(fast!=NULL)
{
fast=fast->next;
if(fast!=NULL)
{
slow=slow->next;
fast=fast->next;
}
}
(*front)=head;
(*back)=slow->next;
slow->next=NULL;
}
}
void merge(struct Node** head,struct Node* list1,struct Node* list2)
{
struct Node* tmp;
if(list1==NULL) (*head)=list2;
if (list2==NULL) (*head)=list1;
if(list1->data<=list2->data)
{
(*head)=list1;
}else{
(*head)=list2;
list2=list1;
list1=(*head);
}
while((list1->next!=NULL)&&(list2!=NULL))
{
if(list1->next->data<=list2->data){
list1=list1->next;
}else{
tmp=list1->next;
list1->next=list2;
list2=tmp;
}
}
if(list1->next==NULL) list1->next=list2;
}
void mergesort(struct Node** head)
{
struct Node* h1=NULL;
struct Node* h2=NULL;
if((*head)!=NULL&&(*head)->next!=NULL)
{
split((*head),&h1,&h2);
mergesort(&h1);
mergesort(&h2);
merge(head,h1,h2);
}
}
Powinna działać chociaż lepiej aby typem danych był
