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 --------
struct node
{
int data;
struct node* next;
struct node* prev;
};
typedef struct node NODE;
NODE * DCreate(int sayi);
void DPrint(NODE * list,int sayi);
NODE * DCutHead(NODE * head);
------ dllist.c---------
#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---------
#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 :)
mkarabulut
09/11/2002, 14:28
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 .... :)
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 :)
// 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.. :)
Forum Yazılımı : vBulletin v3.6.8, Copyright ©2000-2008, Jelsoft Enterprises Ltd.