Data Structure HW1

Rubbish Code brings you great confidence.

#include <stdio.h>
#include <stdlib.h>
#define debug 0

typedef struct Lnode Lnode;
struct Lnode
{
	Lnode* prev, * next;
	int val;
};

Lnode* f[1001], * r[1001];
int llsize[1001];

Lnode* llinit(int sph, int v);
Lnode* lladdf(int sph, int v);
Lnode* _lladd(int sph, Lnode* ptr, int v);
Lnode* lladd(int sph, int p, int v);
Lnode* _llgetptr(Lnode* ptr, int n);
Lnode* llgetptr(int sph, int p);
int _llgetval(Lnode* ptr);
int llgetval(int sph, int p);
void _llswap(Lnode* ptr1, Lnode* ptr2);
void llswap(int sph, int p1, int p2);
int llpop(int sph, int p);
void llquicksort(int sph, int f, int r);

int main(int argc, const char* argv[])
{
	for (int i = 1; i < 6; ++i)
	{
		lladd(0, -1, i);
	}
	for (int i = 2; i < 11; i += 2)
	{
		lladd(1, -1, i);
	}
	for (int i = 0; i < llsize[0]; ++i)
	{
		lladd(2, -1, llgetval(0, i));
	}
	int tmp;
	for (int i = 0; i < llsize[1]; ++i)
	{
		tmp = 1;
		for (int j = 0; j < llsize[0]; ++j)
		{
			if (llgetval(0, j) == llgetval(1, i))
			{
				tmp = 0;
				break;
			}
		}
		if (tmp)lladd(0, -1, llgetval(1, i));
	}
	printf("Lb: ");
	for (int i = 0; i < llsize[1]; ++i)
	{
		printf("%d ", llgetval(1, i));
	}
	printf("\n");
	printf("old La: ");
	for (int i = 0; i < llsize[2]; ++i)
	{
		printf("%d ", llgetval(2, i));
	}
	printf("\n");
	printf("new La: ");
	for (int i = 0; i < llsize[0]; ++i)
	{
		printf("%d ", llgetval(0, i));
	}
	printf("\n");
	getchar();
	return 0;
}

Lnode* llinit(int sph, int v)
{
	Lnode* tmp = (Lnode*)malloc(sizeof(Lnode));
	if (tmp)
	{
		f[sph] = r[sph] = tmp->next = tmp->prev = tmp;
		tmp->val = v;
		llsize[sph] = 1;
		return tmp;
	}
	return NULL;
}

Lnode* lladdf(int sph, int v)
{
	Lnode* tmp = (Lnode*)malloc(sizeof(Lnode));
	if (tmp)
	{
		tmp->next = f[sph];
		tmp->prev = tmp;
		tmp->val = v;
		f[sph]->prev = tmp;
		f[sph] = tmp;
		llsize[sph]++;
		return tmp;
	}
	return NULL;
}

Lnode* _lladd(int sph, Lnode* ptr, int v)
{
	Lnode* tmp = (Lnode*)malloc(sizeof(Lnode));
	if (tmp)
	{
		tmp->next = ptr->next;
		tmp->prev = ptr;
		tmp->val = v;
		if (ptr->next != ptr)(ptr->next)->prev = tmp;
		else r[sph] = tmp, tmp->next = tmp;
		ptr->next = tmp;
		llsize[sph]++;
		return tmp;
	}
	return NULL;
}

Lnode* lladd(int sph, int p, int v)
{
	if (f[sph] && r && llsize)return _lladd(sph, llgetptr(sph, p), v);
	else return llinit(sph, v);
}

Lnode* _llgetptr(Lnode* ptr, int n)
{
	if (n == 0)return ptr;
	else if (n > 0)return _llgetptr(ptr->next, n - 1);
	else return _llgetptr(ptr->prev, n + 1);
}

Lnode* llgetptr(int sph, int p)
{
	if (p >= 0)return _llgetptr(f[sph], p);
	else return _llgetptr(r[sph], 1 + p);
}

int _llgetval(Lnode* ptr)
{
	return ptr->val;
}

int llgetval(int sph, int p)
{
	return llgetptr(sph, p)->val;
}

void _lldel(Lnode* ptr)
{
	ptr->prev->next = ptr->next;
	ptr->next->prev = ptr->prev;
	if (ptr->prev == ptr)ptr->next->prev = ptr->next;
	if (ptr->next == ptr)ptr->prev->next = ptr->prev;
	free(ptr);
}

void lldel(int sph, int p)
{
	llsize[sph]--;
	Lnode* tmp = llgetptr(sph, p);
	if (tmp == f[sph])
	{
		f[sph] = tmp->next;
	}
	else if (tmp == r[sph])
	{
		r[sph] = tmp->prev;
	}
	_lldel(tmp);
}

int llpop(int sph, int p)
{
	llsize[sph]--;
	int tmp=llgetval(sph, p);
	_lldel(llgetptr(sph, p));
	return tmp;
}

void _llswap(Lnode* ptr1, Lnode* ptr2)
{
	int tmp = ptr1->val;
	ptr1->val = ptr2->val;
	ptr2->val = tmp;
	/*
	if (ptr1->next == ptr2 || ptr1->prev == ptr2)
	{
		if (ptr1->prev != ptr1) ptr1->prev->next = ptr2;
		if (ptr1->next != ptr1) ptr1->next->prev = ptr2;
		if (ptr2->prev != ptr2) ptr2->prev->next = ptr1;
		if (ptr2->next != ptr2) ptr2->next->prev = ptr1;
		ptr1->prev = ptr2->prev == ptr2 ? ptr1 : ptr2->prev;
		return;
	}
	//still need to be optimized
	Lnode* tmpp = ptr1->prev, * tmpn = ptr1->next;
	if (ptr1->prev != ptr1) ptr1->prev->next = ptr2;
	if (ptr1->next != ptr1) ptr1->next->prev = ptr2;
	if (ptr2->prev != ptr2) ptr2->prev->next = ptr1;
	if (ptr2->next != ptr2) ptr2->next->prev = ptr1;
	ptr1->prev = ptr2->prev == ptr2 ? ptr1 : ptr2->prev;
	ptr1->next = ptr2->next == ptr2 ? ptr1 : ptr2->next;
	ptr2->prev = tmpp == ptr1 ? ptr2 : tmpp;
	ptr2->next = tmpn == ptr1 ? ptr2 : tmpn;
	*/
}

void llswap(int sph, int p1, int p2)
{
	if (debug)printf("Swaping %d %d\n", p1, p2);
	if (p1 == p2)return;
	//still need to be optimized
	//Lnode* F=llgetptr(sph, p1), * S=llgetptr(sph, p2);
	//f[sph] = F == f[sph] ? S : S == f[sph] ? F : f[sph];
	//r[sph] = F == r[sph] ? S : S == r[sph] ? F : r[sph];
	_llswap(llgetptr(sph, p1), llgetptr(sph, p2));
}

void llquicksort(int sph, int f, int r) //quick sort for linkedlist
{
	if (debug)
	{
		printf("Sorting: ");
		for (int i = f; i < r; ++i)
		{
			printf("%d ", llgetval(sph, i));
		}
		printf("\n");
	}
	if ((r - f) <= 1)return;
	if ((r - f) == 2)
	{
		llgetval(sph, f) <= llgetval(sph, r) ? 0 : llswap(sph, f, r);
		return;
	}
	int it=0;
	for (int i = f+1; i < r; i++)
	{
		if (llgetval(sph, i) <= llgetval(sph, f))
		{
			llswap(sph, i, f + it + 1);
			it++;
		}
	}
	//llswap(sph, f, f + it);
	lladd(sph, f + it, llgetval(sph, f));
	if (debug)printf("adding %d at %d to %d\n", llgetval(sph, f), f + it, sph);
	lldel(sph, f);
	llquicksort(sph, f, f + it + 1);
	llquicksort(sph, f + it+1, r);
}

Runtime screenshot:

#include <stdio.h>
#include <stdlib.h>
#define debug 0

typedef struct Lnode Lnode;
struct Lnode
{
	Lnode* prev, * next;
	int val;
};

Lnode* f[1001], * r[1001];
int llsize[1001];

Lnode* llinit(int sph, int v);
Lnode* lladdf(int sph, int v);
Lnode* _lladd(int sph, Lnode* ptr, int v);
Lnode* lladd(int sph, int p, int v);
Lnode* _llgetptr(Lnode* ptr, int n);
Lnode* llgetptr(int sph, int p);
int _llgetval(Lnode* ptr);
int llgetval(int sph, int p);
void _llswap(Lnode* ptr1, Lnode* ptr2);
void llswap(int sph, int p1, int p2);
int llpop(int sph, int p);
void llquicksort(int sph, int f, int r);

int main(int argc, const char* argv[])
{
	for (int i = 1; i < 6; ++i)
	{
		lladd(0, -1, i);
	}
	for (int i = 2; i < 11; i += 2)
	{
		lladd(1, -1, i);
	}
	printf("La: ");
	for (int i = 0; i < llsize[0]; ++i)
	{
		printf("%d ", llgetval(0, i));
	}
	printf("\n");
	printf("Lb: ");
	for (int i = 0; i < llsize[1]; ++i)
	{
		printf("%d ", llgetval(1, i));
	}
	printf("\n");
	for (int i = 0; i < llsize[0]; ++i)
	{
		lladd(2, -1, llgetval(0, i));
	}
	for (int i = 0; i < llsize[1]; ++i)
	{
		lladd(2, -1, llgetval(1, i));
	}
	//printf("old Lc: ");
	//for (int i = 0; i < llsize[2]; ++i)
	//{
	//	printf("%d ", llgetval(2, i));
	//}
	//printf("\n");
	llquicksort(2, 0, llsize[2]);
	printf("Lc: ");
	for (int i = 0; i < llsize[2]; ++i)
	{
		printf("%d ", llgetval(2, i));
	}
	printf("\n");
	getchar();
	return 0;
}

Lnode* llinit(int sph, int v)
{
	Lnode* tmp = (Lnode*)malloc(sizeof(Lnode));
	if (tmp)
	{
		f[sph] = r[sph] = tmp->next = tmp->prev = tmp;
		tmp->val = v;
		llsize[sph] = 1;
		return tmp;
	}
	return NULL;
}

Lnode* lladdf(int sph, int v)
{
	Lnode* tmp = (Lnode*)malloc(sizeof(Lnode));
	if (tmp)
	{
		tmp->next = f[sph];
		tmp->prev = tmp;
		tmp->val = v;
		f[sph]->prev = tmp;
		f[sph] = tmp;
		llsize[sph]++;
		return tmp;
	}
	return NULL;
}

Lnode* _lladd(int sph, Lnode* ptr, int v)
{
	Lnode* tmp = (Lnode*)malloc(sizeof(Lnode));
	if (tmp)
	{
		tmp->next = ptr->next;
		tmp->prev = ptr;
		tmp->val = v;
		if (ptr->next != ptr)(ptr->next)->prev = tmp;
		else r[sph] = tmp, tmp->next = tmp;
		ptr->next = tmp;
		llsize[sph]++;
		return tmp;
	}
	return NULL;
}

Lnode* lladd(int sph, int p, int v)
{
	if (f[sph] && r && llsize)return _lladd(sph, llgetptr(sph, p), v);
	else return llinit(sph, v);
}

Lnode* _llgetptr(Lnode* ptr, int n)
{
	if (n == 0)return ptr;
	else if (n > 0)return _llgetptr(ptr->next, n - 1);
	else return _llgetptr(ptr->prev, n + 1);
}

Lnode* llgetptr(int sph, int p)
{
	if (p >= 0)return _llgetptr(f[sph], p);
	else return _llgetptr(r[sph], 1 + p);
}

int _llgetval(Lnode* ptr)
{
	return ptr->val;
}

int llgetval(int sph, int p)
{
	return llgetptr(sph, p)->val;
}

void _lldel(Lnode* ptr)
{
	ptr->prev->next = ptr->next;
	ptr->next->prev = ptr->prev;
	if (ptr->prev == ptr)ptr->next->prev = ptr->next;
	if (ptr->next == ptr)ptr->prev->next = ptr->prev;
	free(ptr);
}

void lldel(int sph, int p)
{
	llsize[sph]--;
	Lnode* tmp = llgetptr(sph, p);
	if (tmp == f[sph])
	{
		f[sph] = tmp->next;
	}
	else if (tmp == r[sph])
	{
		r[sph] = tmp->prev;
	}
	_lldel(tmp);
}

int llpop(int sph, int p)
{
	llsize[sph]--;
	int tmp=llgetval(sph, p);
	_lldel(llgetptr(sph, p));
	return tmp;
}

void _llswap(Lnode* ptr1, Lnode* ptr2)
{
	int tmp = ptr1->val;
	ptr1->val = ptr2->val;
	ptr2->val = tmp;
	/*
	if (ptr1->next == ptr2 || ptr1->prev == ptr2)
	{
		if (ptr1->prev != ptr1) ptr1->prev->next = ptr2;
		if (ptr1->next != ptr1) ptr1->next->prev = ptr2;
		if (ptr2->prev != ptr2) ptr2->prev->next = ptr1;
		if (ptr2->next != ptr2) ptr2->next->prev = ptr1;
		ptr1->prev = ptr2->prev == ptr2 ? ptr1 : ptr2->prev;
		return;
	}
	//still need to be optimized
	Lnode* tmpp = ptr1->prev, * tmpn = ptr1->next;
	if (ptr1->prev != ptr1) ptr1->prev->next = ptr2;
	if (ptr1->next != ptr1) ptr1->next->prev = ptr2;
	if (ptr2->prev != ptr2) ptr2->prev->next = ptr1;
	if (ptr2->next != ptr2) ptr2->next->prev = ptr1;
	ptr1->prev = ptr2->prev == ptr2 ? ptr1 : ptr2->prev;
	ptr1->next = ptr2->next == ptr2 ? ptr1 : ptr2->next;
	ptr2->prev = tmpp == ptr1 ? ptr2 : tmpp;
	ptr2->next = tmpn == ptr1 ? ptr2 : tmpn;
	*/
}

void llswap(int sph, int p1, int p2)
{
	if (debug)printf("Swaping %d %d\n", p1, p2);
	if (p1 == p2)return;
	//still need to be optimized
	//Lnode* F=llgetptr(sph, p1), * S=llgetptr(sph, p2);
	//f[sph] = F == f[sph] ? S : S == f[sph] ? F : f[sph];
	//r[sph] = F == r[sph] ? S : S == r[sph] ? F : r[sph];
	_llswap(llgetptr(sph, p1), llgetptr(sph, p2));
}

void llquicksort(int sph, int f, int r) //quick sort for linkedlist
{
	if (debug)
	{
		printf("Sorting: ");
		for (int i = f; i < r; ++i)
		{
			printf("%d ", llgetval(sph, i));
		}
		printf("\n");
	}
	if ((r - f) <= 1)return;
	if ((r - f) == 2)
	{
		llgetval(sph, f) <= llgetval(sph, r) ? 0 : llswap(sph, f, r);
		return;
	}
	int it=0;
	for (int i = f+1; i < r; i++)
	{
		if (llgetval(sph, i) <= llgetval(sph, f))
		{
			llswap(sph, i, f + it + 1);
			it++;
		}
	}
	//llswap(sph, f, f + it);
	lladd(sph, f + it, llgetval(sph, f));
	if (debug)printf("adding %d at %d to %d\n", llgetval(sph, f), f + it, sph);
	lldel(sph, f);
	llquicksort(sph, f, f + it + 1);
	llquicksort(sph, f + it+1, r);
}

Runtime screenshot: