Duyuruyu Kapat
Facebook Gözat
Twitter Gözat

Basit bir double linked list uygulaması

Konu, 'C / C++' kısmında RaiST tarafından paylaşıldı.

  1. RaiST

    RaiST Daimi Üye

    Kayıt:
    24 Temmuz 2002
    Mesajlar:
    1,932
    Beğenilen Mesajlar:
    0
    Meslek:
    linuxrocker
    Şehir:
    krynn
    lab derslerinde c ile yazmıs oldugum basit bir link list uygulaması..

    not: sadece lab dersinde hocaya gostermek amacıyla yazılmıs olup :) hata kontrolu, iyi programlama amacı gutmemektedır. amac hata kontrolu , iyi programla gibi seylerle urasmadan olabildigince hızlı yazıp eve gidebilmektir.. :D

    belki yardımcı olur bir baslangic ornegi olur diye buraya yazdım..

    ------- dllist.h --------



    PHP:
    struct node
    {
    int data;
    struct nodenext;
    struct nodeprev;
    };

    typedef struct node NODE;

    NODE DCreate(int sayi);
    void DPrint(NODE * list,int sayi);
    NODE DCutHead(NODE head);

    ------ dllist.c---------

    PHP:

    #include <stdio.h>
    #include <conio.h>
    #include <malloc.h>
    #include "dllist.h"

    NODE DCreate(int sayi)
    {
    NODE * list;
    NODE temp;
    NODE previous;
    int i;
    list=(
    NODE *)malloc(sizeof(NODE));
    temp=list;
    previous=NULL;
    for(
    i=1;i<=sayi;i++)
    {
    temp->data=i;
    temp->next=(NODE *)malloc(sizeof(NODE));
    temp->prev=previous;
    previous=temp;
    temp=temp->next;
    }
    return list;
    }

    void DPrint(NODE* list,int sayi)
    {
    int i;
    printf("list->next kullanarak dump\n");
    for (
    i=1;i<=sayi-1;i++)
    {
     
    printf("listenin %d. eleman=%d\n",i,list->data);
    list=list->
    next;
    }
     
    printf("listenin %d. eleman=%d\n",sayi,list->data);


    printf("list->prev kullanarak dump\n");

    for (
    i=1;i<=sayi;i++)
    {
     
    printf("listenin %d. eleman=%d\n",i,list->data);
    list=list->
    prev;
    }
    }

    NODE DCutHead(NODE head)
    {


    NODE prev;
    NODE next;

    prev=head->prev;
    next=head->next;

    prev->next=next;
    next->prev=prev;

    return 
    head;

    }
    -------test.c---------
    PHP:

    #include <stdio.h>
    #include <conio.h>
    #include "dllist.c"

    void main()
    {


    NODE * list;

    clrscr();
    list=
    DCreate(5);
    DPrint(list,5);
    DCutHead(list->next);
    DPrint(list,4);



    getch();
    }
    ehehe php hightlight rulz.. bos zamanım olunca comment yazarız :)
     
  2. mkarabulut

    mkarabulut Misafir

    isteriz isteriz
    DSort(NODE *list,int limit)
    DfindAndReplace(int val1,int val2)
    fonksiyonlarınıda isteriz

    Zaten yaparsın, listelerde biraz daha zor olan şeyler bunlardır,hem veri yapıları ve C ile ilgilenen kişiler için de daha faydalı olur sanırım .... :)
     
  3. ee++

    ee++ Daimi Üye

    Kayıt:
    25 Temmuz 2002
    Mesajlar:
    1,122
    Beğenilen Mesajlar:
    0
    Şehir:
    Ankara
    Lab ödevinden bol ne var :)

    Benden de Binary Search Tree ornegi:

    Program, icerigi ornegin asagidaki gibi bir kutuk ile is goruyor:
    6(5(1(4(3(2)))),12(8(7,11(9(10))),13(15(14))))

    Bu bir Binary Search Tree gosterimi. Program bu agaci olusturuyor ve kullaniciya bir komut kabugu sunuyor. Girilen komutlara gore agac uzerinde islemler yapiliyor. En can alici islemler ise farkli algoritmalara gore silme islemleri. Tabi agacin yukaridaki gibi istendigi zaman yazdirilmasi da mumkun. Cok iyi hatirlamiyorum programin islevlerini ama zaten goruluyor, isteyene hazirladigim raporu da gonderebilirim, onda daha acik seciktir her sey. Bu arada programi yazali bir seneden fazla oldu, bicimsel hatalarimin kusuruna bakmayin :)

    Kod:
    // Bil 236 Programming Laboratory - Experiment 2
    // 9920235 - Ersin ER
    
    #include <stdio.h>
    #include <conio.h>
    #include <string.h>
    #include <stdlib.h>
    
    FILE *inputFile, *outputFile;
    
    typedef struct treeNode *treeNodePointer;
    struct treeNode{ // the structure used for holding nodes and constructing tree
    	int data;
    	treeNodePointer leftChild; // pointer to left child node
    	treeNodePointer rightChild; // pointer to right child node
    };//treeNode
    
    // This function allocates memory for a new node.
    treeNodePointer getNewNode(int data){
    	treeNodePointer newNode = (treeNodePointer)malloc(sizeof(struct treeNode));
    	if(!newNode){
    		printf("\nError : Memory is not enough to complete the process.\n");
    		exit(1);
    	}//if
    	newNode->data = data;
    	newNode->leftChild = newNode->rightChild = NULL;
    	return newNode;
    }//getNewNode()
    
    // This function recursively searches for a node with given data in the tree whose root pointer is given.
    treeNodePointer findNode(treeNodePointer node, int data){
    	if(node){
    		if(data == node->data)
    			return node;
    		else if(data < node->data)
    			return findNode(node->leftChild, data);
    		else // if(data > node->data)
    			return findNode(node->rightChild, data);
    	}//if
    	return NULL;
    }//findNode()
    
    // This function recursively searches for a node that is parent of the node with given data.
    treeNodePointer findParent(treeNodePointer node, int data){
    	if(node){
    		if(data < node->data)
    			return (data == (node->leftChild)->data) ? node : findParent(node->leftChild, data);
    		else if(data > node->data)
    			return (data == (node->rightChild)->data) ? node : findParent(node->rightChild, data);
    		else
    			return NULL;
    	}//if
    	return NULL;
    }//findParent()
    
    // This function recursively searches for a node that is needed to be the parent of a new node with given data.
    treeNodePointer findParentForNewNode(treeNodePointer node, int data){
    	if(data < node->data){
    		if(!(node->leftChild))
    			return node;
    		else
    			return findParentForNewNode(node->leftChild,data);
    	}//if
    	else{
    		if(!(node->rightChild))
    			return node;
    		else
    			return findParentForNewNode(node->rightChild,data);
    	}//else
    }//findParentForNewNode()
    
    // This function inserts a node with given data to the tree.
    void insertNode(treeNodePointer *root, int data){
    	treeNodePointer newNode = NULL, parent = findParentForNewNode(*root, data);
    	if(parent || (!(*root))){
    		newNode = getNewNode(data); // allocate memory for the new node
    		if(*root){ // if the tree has at least one element
    			if(data < parent->data)
    				parent->leftChild = newNode;
    			else
    				parent->rightChild = newNode;
    		}//if
    		else // if the tree is empty
    			*root = newNode; // assign new node to be the root node
    	}//if
    }//insertNode()
    
    // This function reads the data of nodes of tree from the input file and constructs the tree using them.
    void readDataAndConstructTree(treeNodePointer *root){
    	int count, data;
    	char ch, number[6];
    	if(!(inputFile = fopen("TREE.INP", "r"))){
    		printf("\nError: TREE.INP could not be opened for reading.\n");
    		exit(1);
    	}//if
    	do{
    		ch = fgetc(inputFile);
    		count = 0;
    		// read an integer data of node till getting an '(' or (,) or ')' character
    		while((ch >= '0') && (ch <= '9')){
    			number[count++] = ch;
    			ch = fgetc(inputFile);
    		}//while
    		number[count] = '\0';
    		if(strlen(number) > 0){ // if any integer data is read in to the 'number' variable
    			sscanf(number, "%d", &data); // read the data from 'number' again
    			insertNode(root, data); // call the insertion function to insert a new node with the data read
    		}//if
    	}while((ch != '\n') && (ch != EOF)); // execute the loop for one line in the input file
    }//readDataAndConstructTree()
    
    // This function recursively traverses the tree via pre-order and prints it to screen in the required format.
    void printTreeToScreen(treeNodePointer node){
    	if(node){
    		printf("%d", node->data);
    		if(node->leftChild || node->rightChild) // if the node has a child
    			printf("(");
    		printTreeToScreen(node->leftChild);
    		if(node->leftChild && node->rightChild) // if the node has a left and a right child
    			printf(",");
    		printTreeToScreen(node->rightChild);
    		if(node->leftChild || node->rightChild) // if the node has a child
    			printf(")");
    	}//if
    }//printTreeT/Screen()
    
    // This function recursively traverses the tree via pre-order and prints it to output file in the required format.
    void printTreeToFile(treeNodePointer node){
    	if(node){
    		fprintf(outputFile, "%d", node->data);
    		if(node->leftChild || node->rightChild)
    			fprintf(outputFile, "(");
    		printTreeToFile(node->leftChild);
    		if(node->leftChild && node->rightChild)
    			fprintf(outputFile, ",");
    		printTreeToFile(node->rightChild);
    		if(node->leftChild || node->rightChild)
    			fprintf(outputFile, ")");
    	}//if
    }//printTreeToFile()
    
    // This function searches for a node that has the greatest data in the left branch of given node.
    treeNodePointer findBiggestOfLeftBranch(treeNodePointer node){
    	node = node->leftChild;
    	while(node->rightChild) // find the rightmost node in the branch
    		node = node->rightChild;
    	return node;
    }//findBiggestOfLeftBranch()
    
    // This function searches for a node that has the smallest data in the right branch of given node.
    treeNodePointer findSmallestOfRightBranch(treeNodePointer node){
    	node = node->rightChild;
    	while(node->leftChild)
    		node = node->leftChild;
    	return node;
    }//findSmallestOfRightBranch()
    
    // This function deletes a node that has not a left branch.
    void deleteWithoutLeftBranch(treeNodePointer *root, treeNodePointer parentOfNode, treeNodePointer node){
    	if(node == *root)	// if the node to be deleted is the root node
    		*root = node->rightChild;
    	else{ // else if the node to be deleted is any node except the root without a left branch
    		// determine if the node to be deleted is the left or right child of its parent
    		// and update the child link of its parent
    		if(parentOfNode->leftChild == node) // if the node to be deleted is the left child of its parent
    			parentOfNode->leftChild = node->rightChild;
    		else // if the node to be deleted is the right child of its parent
    			parentOfNode->rightChild = node->rightChild;
    	}//else
    	free(node);
    }//deleteWithoutLeftBranch()
    
    // This function deletes a node that has not a right branch.
    void deleteWithoutRightBranch(treeNodePointer *root, treeNodePointer parentOfNode, treeNodePointer node){
    	if(node == *root)
    		*root = node->rightChild;
    	else{
    		if(parentOfNode->leftChild == node)
    			parentOfNode->leftChild = node->leftChild;
    		else
    			parentOfNode->rightChild = node->leftChild;
    	}//else
    	free(node);
    }//deleteWithoutRightBranch()
    
    // This function deletes a node obeying the left biggest rule.
    void deleteNodeViaLeftBiggestRule(treeNodePointer *root,int data){
    	treeNodePointer node = findNode(*root, data), // find the node to be deleted
    						 parentOfNode , leftBiggest , parentOfLeftBiggest;
    	if(node){ // if a node with given data exists in the tree
    		parentOfNode = findParent(*root, node->data);
    		if(node->leftChild){ // if the node to be deleted has a left branch
    			leftBiggest = findBiggestOfLeftBranch(node);
    			parentOfLeftBiggest = findParent(*root, leftBiggest->data);
    			// determine if 'leftBiggest' the left or right child of its parent
    			// and update the child link so that 'leftBiggest' is seperated from its parent
    			if(parentOfLeftBiggest->leftChild == leftBiggest)
    				parentOfLeftBiggest->leftChild = leftBiggest->leftChild;
    			else
    				parentOfLeftBiggest->rightChild = leftBiggest->leftChild;
    			// replace 'node' with 'leftBiggest' by updating child links
    			leftBiggest->leftChild = node->leftChild;
    			leftBiggest->rightChild = node->rightChild;
    			if(node == *root) // if the node to be deleted is the root node
    				*root = leftBiggest; // assign the replaced node to be the root node
    			else{ // if the node to be deleted is not the root node
    				// determine if the node to be deleted is the left or right child of its parent
    				// and update the parent link of replaced node so that it becomes the child of parent of the node to be deleted
    				if(parentOfNode->leftChild == node)
    					parentOfNode->leftChild = leftBiggest;
    				else
    					parentOfNode->rightChild = leftBiggest;
    			}//else
    			free(node); // deallocate the memory allocated for the node to be deleted
    		}//if
    		else // if the node to be deleted has not a left branch
    			deleteWithoutLeftBranch(root, parentOfNode, node);
    	}//if
    	else // if there is not any node with given data in the tree
    		printf(" No such node with data '%d' in the tree.\n", data);
    }//deleteNodeViaLeftBiggestRule()
    
    // This function deletes a node obeying the right smallest rule.
    void deleteNodeViaRightSmallestRule(treeNodePointer *root, int data){
    	treeNodePointer node = findNode(*root,data),
    						 parentOfNode , rightSmallest , parentOfRightSmallest;
    	if(node){ // if the element exists
    		parentOfNode = findParent(*root, node->data);
    		if(node->rightChild){ // if the node has a right branch
    			rightSmallest = findSmallestOfRightBranch(node);
    			parentOfRightSmallest = findParent(*root, rightSmallest->data);
    			// determine if 'rightSmallest' the left or right child of its parent
    			// and update the child link so that 'rightSmallest' is seperated from its parent
    			if(parentOfRightSmallest->leftChild == rightSmallest)
    				parentOfRightSmallest->leftChild = rightSmallest->rightChild;
    			else
    				parentOfRightSmallest->rightChild = rightSmallest->rightChild;
    			// replace 'node' with 'rightSmallest'
    			rightSmallest->leftChild = node->leftChild;
    			rightSmallest->rightChild = node->rightChild;
    			if(node == *root) // if the node that is to be deleted is 'root'
    				*root = rightSmallest; // then update 'root'
    			else{
    				// determine the place of the 'node' and update its parents link
    				// so that 'node' is seperated from the tree and 'rightSmallest' is linked to the 'nodes's parent
    				if(parentOfNode->leftChild == node)
    					parentOfNode->leftChild = rightSmallest;
    				else
    					parentOfNode->rightChild = rightSmallest;
    			}//else
    			free(node); // deallocate the memory allocated for the node to be deleted
    		}//if
    		else // if the 'node' has no right branch
    			deleteWithoutRightBranch(root, parentOfNode, node);
    	}//if
    	else // if there is not any node with given data in the tree
    		printf(" No such node with data '%d' in the tree.\n", data);
    }//deleteNodeViaRightSmallestRule()
    
    // This function deletes a node obeying the left child rule.
    void deleteNodeViaLeftChildRule(treeNodePointer *root, int data){
    	treeNodePointer node = findNode(*root, data),
    						 parentOfNode, leftBiggest;
    	if(node){ // if the element exists in the tree
    		parentOfNode = findParent(*root, node->data);
    		if(node->leftChild){ // if 'node' has left branch
    			leftBiggest = findBiggestOfLeftBranch(node); // find the element with the biggest value in the left branch
    			// update the right child link of 'leftBiggest' to protect the binary tree structure
    			leftBiggest->rightChild = node->rightChild;
    			if(node == *root) // if the 'node' to be deleted is 'root'
    				*root = node->leftChild; // update the 'root'
    			else{ // if the node to be deleted is any node other than root node
    				// determine the place of the 'node' according to its parent
    				// and update parent's link with its left child
    				if(parentOfNode->leftChild == node)
    					parentOfNode->leftChild = node->leftChild;
    				else
    					parentOfNode->rightChild = node->leftChild;
    			}//else
    			free(node); // deallocate the memory allocated for the node to be deleted
    		}//if
    		else // if the 'node' has no left branch
    			deleteWithoutLeftBranch(root, parentOfNode, node);
    	}//if
    	else // if there is not any node with given data in the tree
    		printf(" No such node with data '%d' in the tree.\n", data);
    }//deleteNodeViaLeftChildRule()
    
    // This function deletes a node obeying the right child rule.
    void deleteNodeViaRightChildRule(treeNodePointer *root, int data){
    	treeNodePointer node = findNode(*root, data),
    						 parentOfNode, rightSmallest;
    	if(node){ // if the element exists in the tree
    		parentOfNode = findParent(*root, node->data);
    		if(node->rightChild){ // if the 'node' has right branch
    			rightSmallest = findSmallestOfRightBranch(node); // find the smallest value in the right branch
    			// update the left child link of 'rightSmallest' to protect the binary tree structure
    			rightSmallest->leftChild = node->leftChild;
    			if(node == *root) // if the 'node' is 'root' then
    				*root = node->rightChild; // update 'root'
    			else{
    				// determine the place of the 'node' according to its parent
    				// and update parent's link with its right child
    				if(parentOfNode->leftChild == node)
    					parentOfNode->leftChild = node->rightChild;
    				else
    					parentOfNode->rightChild = node->rightChild;
    			}//else
    			free(node); // deallocate the memory allocated for the node to be deleted
    		}//if
    		else // if 'node' has no right branch
    			deleteWithoutRightBranch(root, parentOfNode, node);
    	}//if
    	else // if there is not any node with given data in the tree
    		printf(" No such node with data '%d' in the tree.\n", data);
    }//deleteNodeViaRightChildRule()
    
    // This function gets user commands and calls appropriate functions to execute them.
    void getAndExecuteCommands(treeNodePointer *root){
    	int data;
    	char command[3] = { 0 }, lineCommand[15] = { 0 }, fileName[13] = { 0 };
    	clrscr();
    	gotoxy(1,25);
    	do{
    		printf(">");
    		gets(lineCommand);
    		if(((lineCommand[0] == 'l') || (lineCommand[0] == 'r')) && ((lineCommand[2] == ' ') || (lineCommand[2] == '\0'))){
    			// commands 'lb', 'rs', 'rc', 'lc' are handled
    			if((sscanf(lineCommand, "%s %d", command, &data)) != 2){
    				printf(" Wrong or missing parameter in the command.\n");
    				continue;
    			}//if
    			if(*root){ // if the tree is not empty
    				// call approprite function due to read command
    				if(!strcmp(command, "lb"))
    					deleteNodeViaLeftBiggestRule(root, data);
    				else if(!strcmp(command, "rs"))
    					deleteNodeViaRightSmallestRule(root, data);
    				else if(!strcmp(command, "lc"))
    					deleteNodeViaLeftChildRule(root, data);
    				else if(!strcmp(command, "rc"))
    					deleteNodeViaRightChildRule(root, data);
    			}//if
    			else // if the tree is empty
    				printf("Tree is empty.");
    		}//if
    		else if((lineCommand[0] == 'w') && ((lineCommand[1] == ' ') || (lineCommand[1] == '\0'))){
    			// commands 'w' and 'w <output file name>' are handled
    			if(strlen(lineCommand) == 1){
    				printf(" ");
    				if(*root){ // if the tree is not empty
    					printf("Tree is: ");
    					printTreeToScreen(*root); // display the tree on the screen
    				}//if
    				else
    					printf("Tree is empty.");
    				printf("\n");
    			}//if
    			else{ // if 'w <output file name>' command is read
    				if((sscanf(lineCommand, "%*c%*c%s", fileName)) != 1)
    					printf(" Input file name is missing while you placed a space after \"w\" command.\n");
    				else{
    					if(!(outputFile = fopen(fileName, "a"))){ // open output file
    						printf("\nError: Output file %s could not be opened for writing.\n", fileName);
    						exit(1);
    					}//if
    					if(*root) // if the tree is not empty
    						printTreeToFile(*root); // display tree into the file
    					else // if the tree is empty
    						fprintf(outputFile, "Tree is empty.");
    					fprintf(outputFile, "\n");
    					fclose(outputFile); // close output file
    				}//else
    			}//else
    		}//else if
    		else if(strcmp(lineCommand, "q") != 0)
    			printf(" \"%s\" is not a valid command to execute.\n", lineCommand);
    	} while(strcmp(lineCommand, "q") != 0); // while command is not 'quit'
    }//getAndExecuteCommands()
    
    // This function recursively traverses the tree via post-order and deallocates the memory of remaining nodes.
    void destructTree(treeNodePointer node){
    	if(node){
    		destructTree(node->leftChild);
    		destructTree(node->rightChild);
    		free(node);
    	}//if
    }//destructTree()
    
    void main(void){
    	treeNodePointer root = NULL;
    	readDataAndConstructTree(&root);
    	getAndExecuteCommands(&root);
    	destructTree(root);
    }//main()
    Cok pis main yazarim da.. :)

    Aslinda fena yazmamisim, global degisken filan neredeyse yok gibi.. :)