Lista jednokierunkowa
Mariusz:
Mam napisaną listę jednokierunkową w c dla liczb całkowitych
Plik nagłówkowy
#ifndef LISTAH_
#define LISTAH_
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ę
#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\n");
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\n");
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\n");
return val;
}
void deleteNode(struct Node** head,int n)
{
struct Node* aux;
struct Node* previous;
if(isEmpty((*head)))
{
printf("Lista jest pusta\n");
}
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\n");
}
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\n",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\n");
}
newNode−>data=x2;
if((*head)==NULL)
{
printf("Wezla nie znaleziono \n");
}
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\n");
}
}
}
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\n");
return;
}
newNode−>data=x2;
if((*head)==NULL)
{
printf("Wezla nie znaleziono\n");
}
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\n");
}
}
}
void reverse(struct Node ** head)
{
struct Node * prev=NULL;
struct Node * current=(*head);
struct Node * next=NULL;
while(current!=NULL)
{
next=current−>next;
current−>next=prev;
prev=current;
current=next;
}
(*head)=prev;
}
void saveToFile(struct Node* head,char* path)
{
FILE* fp;
struct Node* temp;
if ((fp = fopen(path, "wt"))
== NULL)
{
fprintf(stderr, "Cannot open output file.\n");
return ;
}
temp=head;
while(temp!=NULL)
{
fprintf(fp,"%d\n",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.\n");
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);
}
}
Co zmienić w kodzie aby typem danych był void*
26 mar 20:23
jc: Zamień napis int na napis void*
26 mar 20:44
Mariusz:
Czy ja wiem czy to będzie działać ?
Wydaje mi się że to nie jest aż takie łatwe
26 mar 21:44