Demo entry 6645574

异质链表操作实现

   

Submitted by 黄怡璠 on Oct 11, 2017 at 03:47
Language: C. Code size: 14.5 kB.

/* 
   exercise 1.c
   Heterogenous linked list
   Written by Huang Yifan on 2017.10.10
   Copyright (c) 2017 Huang Yifan of ZJU
 */

#include <stdio.h>
#include <stdlib.h>

//statement of linklist
typedef struct Node
{
	void *data;
	int type;
	struct Node *Next;
}*List;
/*********************************************/

//datatype just enumerate 0. int 1. char 2. double 
enum{Int, Char, Double}; 

//define some numbers 
#define LENGTH_L2 3
#define ELEMENT_1 3
#define ELEMENT_2 4
#define ELEMENT_3 5
#define DATASIZE  20


//statement of functions
/*1.creat a linklist
  2.insert a node (head position, kth position, end position)
  3.delete a node (head node, kth node, end node)
  4.traverse and print the linklist
  5.destroy a linklist
  6.combine two linklists
  7.reverse a linklist 
  8.get the length of the linklist
*/
List Create();

List Insert_Head(List p0, List ptrL);
List Insert_kth(List p0, int k, List ptrL);
List Insert_End(List p0, List ptrL);

List Delete_Head(List ptrL);
List Delete_kth(int k, List ptrL);
List Delete_End(List ptrL);

void Print(List ptrL);

List Destroy(List ptrL);

List Combine(List ptrL1, List ptrL2);

List Reverse(List ptrL);

int Getlength(List ptrL);
/********************************************/

//main function 
int main()
{
	List L, L2, ptr, ptr2, p;
	void *position;
	int Idata[DATASIZE];     /* used for three enumerated datatypes */
    char Cdata[DATASIZE];    
    double Ddata[DATASIZE];  /* because we write this main function to realize 
                        the function of linklist, so we don't have to 
                        create much space for these datatypes */
    int i=0, j=0, q=0; /* used for different data */
    int flag=1; /* to break the main loop */
	int choice, kth, datatype;/* choice for different instruction */
	int size=sizeof(struct Node);
	int h, a[LENGTH_L2]={ELEMENT_1, ELEMENT_2, ELEMENT_3}; /* used for creating L2 */
	int length; /*used in Getlength function */
	L=NULL;
	L2=NULL;
	ptr=NULL;/* for create L2 */ 
	ptr2=NULL;/* for create L2 */ 
	/* for convenice of the combination of two linklist
	   I create L2 with just three simple nodes */
	for(h=0; h<LENGTH_L2; h++)
	{
		ptr=(List)malloc(size);
		ptr->data=&a[h];
		ptr->type=0;
		ptr->Next=NULL;
		if(L2==NULL)
		{
			L2=ptr;
			ptr2=L2;
		}
		else
		{
			ptr2->Next=ptr;
			ptr2=ptr;
		}
	}
	/* implement instructions of linklist */
	printf("  =======ATTENTION========\n\n");
	printf("  NO DUMY HEAD IN THE LINKLIST IN THIS PROJECT\n\n");
	do
	{
		printf("\n    Choose the operation : \n\n");
		printf("    1:create         2:insert(head)   3:insert(kth)   4:insert(end) \n\n");
		printf("    5:delete(head)   6:delete(kth)    7:delete(end)   8:print\n\n");
		printf("    9:destroy        10:combine       11:reverse      12:get length    0:Exit\n\n");
		scanf("%d", &choice);
		switch(choice)
		{
			case 1:
			        L=Create();
			        break;
			case 2:
			        printf("    Datatype:  0.int   1.char   2.double\n");
			        scanf("%d", &datatype);
			        switch(datatype)
			        {
			        	case (Int):
			        	        printf("    Input int: ");
			        	        scanf("%d", &Idata[i]);
			        	        position=&Idata[i];
			        	        i++;
			        	        break;
			        	case (Char):
			        	        printf("    Input char: ");
			        	        scanf("%s", &Cdata[j]);
			        	        position=&Cdata[j];
			        	        j++;
			        	        break;
			        	case (Double):
			        	        printf("    Input double: ");
			        	        scanf("%lf", &Ddata[q]);
			        	        position=&Ddata[q];
			        	        q++;
			        	        break;
			        }
			        p=(List)malloc(size);
	                p->data=position;
	                p->type=datatype;
	                p->Next=NULL;
			        L=Insert_Head(p, L);
			        break;
			case 3:
			        printf("    Enter kth (k>0): ");
			        scanf("%d",&kth);
			        printf("    Datatype:  0.int   1.char   2.double\n");
			        scanf("%d", &datatype);
			        switch(datatype)
			        {
			        	case (Int):
			        	        printf("    Input int: ");
			        	        scanf("%d", &Idata[i]);
			        	        position=&Idata[i];
			        	        i++;
			        	        break;
			        	case (Char):
			        	        printf("    Input char: ");
			        	        scanf("%s", &Cdata[j]);
			        	        position=&Cdata[j];
			        	        j++;
			        	        break;
			        	case (Double):
			        	        printf("    Input double: ");
			        	        scanf("%lf", &Ddata[q]);
			        	        position=&Ddata[q];
			        	        q++;
			        	        break;
			        }
			        p=(List)malloc(size);
	                p->data=position;
	                p->type=datatype;
	                p->Next=NULL;
			        L=Insert_kth(p, kth, L);
			        break;
			case 4:
			        printf("    Datatype:  0.int   1.char   2.double\n");
			        scanf("%d", &datatype);
			        switch(datatype)
			        {
			        	case (Int):
			        	        printf("    Input int: ");
			        	        scanf("%d", &Idata[i]);
			        	        position=&Idata[i];
			        	        i++;
			        	        break;
			        	case (Char):
			        	        printf("    Input char: ");
			        	        scanf("%s", &Cdata[j]);
			        	        position=&Cdata[j];
			        	        j++;
			        	        break;
			        	case (Double):
			        	        printf("    Input double: ");
			        	        scanf("%lf", &Ddata[q]);
			        	        position=&Ddata[q];
			        	        q++;
			        	        break;
			        }
			        p=(List)malloc(size);
	                p->data=position;
	                p->type=datatype;
	                p->Next=NULL;
			        L=Insert_End(p, L);
			        break;
			case 5:
			        L=Delete_Head(L);
			        break;
			case 6:
			        printf("    Enter kth (k>0): ");
			        scanf("%d",&kth);
			        L=Delete_kth(kth, L);
			        break;
			case 7:
			        L=Delete_End(L);
			        break;
			case 8:
			        Print(L);
			        break;
			case 9:
			        L=Destroy(L);
			        break;
			case 10:
			        L=Combine(L, L2);
			        break;
			case 11:
                    L=Reverse(L);
                    break;
            case 12:
                    length=Getlength(L);
                    printf("    %d\n",length);
                    break;
            case 0: 
			        flag=0;
					break;
            default:break;
		}

	}while(flag);

	return 0;                            

}

//Create a linklist:

 /* INSTRUCTION:
  * this function is used to create a null linklist,
    the linklist don't have a dumy head
  * return: the head of the null linklist
*/
List Create()
{
	List ptrL;
	ptrL=NULL;
	return ptrL;
}
/*******************************************************************/


//Insert a node in the head position
/* INSTRUCTION:
 * p0: new node
 * return: the head of the linklist
 */
List Insert_Head(List p0, List ptrL)
{
	p0->Next=ptrL; /* p0 becomes the new head */
	return p0;
}
/*********************************************************************/

//Insert a node in the Kth position
/* INSTRUCTION:
 * p0: new node
 * K:this integer is the position we want to insert
 * ptrL: the head of old linklist
 * return: the head of new linklist
 * this function use the function Getlength in order to
   let the k make sense
 */
List Insert_kth(List p0, int k, List ptrL)
{
	int d; /* length of linklist */
	List pres;/* pres is uesd to reserve the head of linklist */
	pres=ptrL; 
	d=Getlength(ptrL);
	if(k==1)
	{
		ptrL=Insert_Head(p0, ptrL); /* use function Insert_head */ 
		return ptrL;
	}
	else if(k==(d+1))
	{
		ptrL=Insert_End(p0, ptrL); /*use function Insert_End */
		return ptrL;
	}
	else if((k>(d+1))||(k<1))
	{
		printf("    Illegal k!\n");
		return ptrL;
	}
	else 
	{
		while(k-2) /* we must find k-1 node */ 
		{
			ptrL=ptrL->Next;
			k=k-1;
		}
	    p0->Next=ptrL->Next;
	    ptrL->Next=p0;
	    return pres;
	}
	

}
/********************************************************/

//Insert a node in the end
/* INSTRUCTION:
 * p0: new node
 * ptrL: the head of  old linklist
 * return: the head of new linklist
 * although we insert the node in the end, we don't call 
   Getlength function. Only  one loop in this function
   is enough.
 */
List Insert_End(List p0, List ptrL)
{
	List pres; /* pres is uesd to reserve the head of linklist */
	pres=ptrL;
	while(ptrL->Next)
	{
		ptrL=ptrL->Next;
	}
	ptrL->Next=p0;
	return pres;
}
/****************************************************************/

//Delete the head node
/* INSTRUCTION:
 * ptrL: the head of old linklist
 * return: head of new linklist
 */
List Delete_Head(List ptrL)
{
	List pfree; /* use to point to the node which will be free */
	pfree=ptrL; /* record the head */
	if(ptrL==NULL) /* the linklist is NULL we have nothing to delete*/
	{
		return ptrL;
	}
	else
	{
		ptrL=ptrL->Next;
		free(pfree);
		return ptrL;
	}
}
/***************************************************************/

//Delete the kth node
/* INSRUCTION:
 * k: the positon of the node which we will delete
 * ptrL: the head of old linklist
 * this function will call Getlength in order to judge whether 
   the node can be delete
 */
List Delete_kth(int k, List ptrL)
{
	int d; /* d is the length of linklist */
	List pres; /* pres is uesd to reserve the head of linklist */
	List pfree; /* use to point to the node which will be free */
	pres=ptrL;
	pfree=NULL;
	d=Getlength(ptrL);
	if(k==1) /*call Delete_Head function to delete head */
	{
		ptrL=Delete_Head(ptrL);
		return ptrL;
	}
	else if(k==d) /*call Delete_End function do delete end node */
	{
		ptrL=Delete_End(ptrL);
		return ptrL;
	}
	else if((k>(d+1))||(k<1))
	{
		printf("    Illegal k!\n");
		return ptrL;
	}
	else
	{
		while(k-2) /* we must find k-1 node */
		{
			ptrL=ptrL->Next;
			k--;
		}
		pfree=ptrL->Next;
		ptrL=pfree->Next;
		free(pfree);
		return pres;
	}
}
/****************************************************************/

//Delete the end node
/* INSTRUCTION
 * ptrL: the head of old linklist
 * return: the head of new linklist
 * although we delete the node in the end, we don't call 
   Getlength function. Only  one loop in this function
   is enough.
 */
List Delete_End(List ptrL)
{
	List pres; /* pres is uesd to reserve the head of linklist */
	List pfree; /* use to point to the node which will be free */
	pres=ptrL;
	pfree=NULL;
	if(ptrL==NULL) /* we have nothing to delete in a null linklist*/
	{
		return ptrL;
	}
	else if((ptrL->Next)==NULL) /* only one node in linklist */
	{
		pfree=ptrL;
		free(pfree);
		ptrL=NULL;
		return ptrL;
	}
	while((ptrL->Next)->Next)
	{
		ptrL=ptrL->Next;
	}
	pfree=ptrL->Next;
	ptrL->Next=NULL;
	free(pfree);
	return pres;
}
/***********************************************************************/

// Traverse and print the linklist
/* INSTRUCTION
 * ptrL: the head of linklist
 * this funciton will get the type of different data to print the data
   correctly
 */
void Print(List ptrL)
{
	printf("\n    Linklist: ");
	while(ptrL)
	{
		switch(ptrL->type)
		{
			case (Int):
			           printf("%d->", (*(int*)ptrL->data));
			           break;
			case (Char):
			           printf("%c->", (*(char*)ptrL->data));
			           break;
			case (Double):
			           printf("%lf->", (*(double*)ptrL->data));
			           break;
			default:   break;
		}
		ptrL=ptrL->Next;
	}
	printf("NULL\n\n");
}
/*********************************************************/

//Destroy the linklist
/* INSTRUCTION
 * ptrl: the head of old linklist
 * return: get the linklist after destroy
 */
List Destroy(List ptrL)
{
	List pres; /* pres is uesd to reserve the head of linklist */
	List pfree; /* use to point to the node which will be free */
	pres=ptrL;
	pfree=ptrL;
	while(ptrL)
	{
		pfree=ptrL;
		ptrL=ptrL->Next;
		free(pfree);
	}
	return pres;
}
/*******************************************************************/

//Combine two linklists
/* INSTRUCTION
 * ptrL1: the head of one linklist
 * ptrL2: the head of another linklist
 * return: the head of new linklist
 * we make the ptrl1 be the first linklist, so which linklist you want to
   place firstly, you should put the pointer at first
 */
List Combine(List ptrL1, List ptrL2)
{
	List pres; /* pres is uesd to reserve the head of linklist */
	pres=ptrL1;
	if(ptrL1==NULL) /* if L1 is NULL, return L2 */
	{
		return ptrL2;
	}
	while(ptrL1->Next)
	{
		ptrL1=ptrL1->Next;
	}
	ptrL1->Next=ptrL2; /* connect L1 and L2 */
	return pres;
}
/*******************************************************************/

// reverse the linklist
/* INSTRUCTION
 * ptrL: the head of old linklist
 * return: the head of new linklist
 * this function reverse the linklist on itself
   so note that after calling this function, we
   can't reserve the old function
 */
List Reverse(List ptrL)
{
	List pNext; /* to keep the next node */
	List ptrL2; /* use to exhange the node */
	List pres; /* pres is uesd to reserve the head of old linklist */
	pres=ptrL;
	pNext=ptrL->Next;
	ptrL2=ptrL;
	if((ptrL==NULL)||((ptrL->Next)==NULL))
	{
		return ptrL;
	}
	else
	{
		while(pNext)
		{
			ptrL2=ptrL; /* change the pointer */
			ptrL=pNext;
			pNext=ptrL->Next;
			if(ptrL2==pres) /* get the end of new linklist */
			{
				ptrL2->Next=NULL;
			}
			ptrL->Next=ptrL2; /* exchange the position */
		}
		return ptrL;
	}
}
/***************************************************************/

//Get the length of linklist
/* INSTRUCTION
 * ptrL: the head of linklist
 * return: the length of linklist
 */
int Getlength(List ptrL)
{
	int d; /* record the length of linklist */
	d=0;
	while(ptrL)
	{
		ptrL=ptrL->Next;
		d++;
	}
	return d;
}
/*****************************************************************/

This snippet took 0.03 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).