listedlist.cpp

用C语言编写实现数据结构方面的例子

#include <stdio.h>
#include <malloc.h>

typedef struct LNode
{
	int data;
	struct LNode *next;
}; 

void LNodeSetNull(struct LNode **p);
int LNodeLength(struct LNode **p);
void LNodeGet(struct LNode **p,int i);//取第i个元素
int LNodeLocate(struct LNode **p,int x);//元素定位 
void LNodeInsert(struct LNode **p,int x,int i);//第i位置插入x
void LNodeDelete(struct LNode **p,int i);//第i数删除
void LNodeDisplay(struct LNode **p);
struct LNode *LNodeCreate();
struct LNode *LNodeCreate1();

int  main()
{
	struct LNode *head;
	int flag=1;
	char ch;
	int select;//
	int n;
	int i;
	int y;
	int length;
	int m,get;
	int e,locate;
	int g;
	
    LNodeSetNull(&head);


//	head=LNodeCreate1();
	printf("请输入数据长度:");
	scanf("%d",&n);

	for (i=1;i<=n;i++)
	{
		printf("将数据插入到单链表中:");
		scanf("%d",&y);
		LNodeInsert(&head,y,i);//插入数据到链表
		
	}
	LNodeDisplay(&head);/*显示链表所有数据*/

	while (flag)
	{
		
		printf("\n");
		printf("1 求长度 LNodeLength()       2 取结点 LNodeGet()\n");
		printf("3 求值查找 LNodeLocate()     4 删除结点 LNodeDelete()\n");
		printf("input your select: ");
		scanf("%d",&select);
		switch(select)
		{
		case 1:
			{
				length=LNodeLength(&head);
				printf("输出单链表的长度%d\n",length);
				LNodeDisplay(&head);
				
			}
			break;
		case 2:
			{
				printf("请输入要取得结点号: ");
				scanf("%d",&m);
				LNodeGet(&head,m);
			//	printf("结点数:%d\n",get);
				LNodeDisplay(&head);
			}
			break;
		case 3:
			{
				printf("请输入要查找的数据: ");
				scanf("%d",&e);
				locate=LNodeLocate(&head,e);
				printf("位置:%d\n",locate);
				LNodeDisplay(&head);
			}
			break;
		case 4:
			{
				printf("请输入要删除的结点: ");
				scanf("%d",&g);
				LNodeDelete(&head,g);
				LNodeDisplay(&head);
			}
			break;
		}


		printf("继续操作(Y|N):");
		getchar();
		ch=getchar();

		if (ch=='N' || ch=='n')
		{
			flag=0;
		}
		else
	        flag=1;

	}

	return 0;
}

void LNodeSetNull(struct LNode **p)
{//建立一个空的单链表

	*p=NULL;
}

int LNodeLength(struct LNode **p) //长度
{
	int n=0;
	struct LNode *q;
	q=*p;

	while (q!=NULL)
	{
		n++;
		q=q->next;
	}
 	return(n);

}

void LNodeGet(struct LNode **p,int i)//取第i个元素
{
	int j=1;
	struct LNode *q=*p;

	if (i<1)
	{
		printf("参数错误");
	}
	while (j<i && q!=NULL)
	{
		j++;
		q=q->next;
	}
	if (q!=NULL)
	{
		printf("元素：%d",q->data);
	}
	else
		printf("位置参数不正确!\n");

}

int LNodeLocate(struct LNode **p,int x)//元素定位 
{
	struct LNode *q;
	q=*p;
	int i=1;

	while (q!=NULL && q->data!=x)
	{
		q=q->next;
		i++;
	}

	if(q==NULL)
	{
		return 0;

	}
	else
		return i;
/*	if (q->data==x)
	{
		return i;
	}
	else
		return 0;*/

}

void LNodeInsert(struct LNode **p,int x,int i)//第i位置插入x
{
	int j=1;
	struct LNode *s,*q;
	
	s=(LNode *)malloc(sizeof(LNode));
	s->data=x;

	q=*p;

	if (i==1)
	{
		s->next=q;
		*p=s;
		
	}
	else
	{
		while (j<i-1 && q->next!=NULL )
		{
			q=q->next;
			j++;
		}
		if (j==i-1)
		{
			s->next=q->next;
			q->next=s;	
		}
		else
			printf("参数错误!");
	}
}

void LNodeDelete(struct LNode **p,int i)//第i数删除
{
	int j=1;
	struct LNode *q,*t;
	
	q=*p;

	if (i==1)
	{
		q=q->next;
		*p=q;
	}
	else
	{
		while (j<i-1 && q->next!=NULL)
		{
			j++;
			q=q->next;
		}

		if (q->next!=NULL && j==i-1)
		{
			t=q->next;
			q->next=t->next;
			printf("删除成功");
		}
		else
			printf("参数错误!");
	}

	if (t==NULL)
	{
		free(t);
	}
}

void LNodeDisplay(struct LNode **p)
{
	struct LNode *q;
	q=*p;

	printf("单链表:");
 
	if (q==NULL)
	{
		printf("链表为空");
	}
	else if (q->next==NULL)
	{
		printf("%d",q->data);
	}
	else
	{
		while (q->next!=NULL)
		{
			printf("%d->",q->data);
			q=q->next;
		}
		printf("%d->",q->data);
	}
}


//尾插法建立带头结点的
struct LNode *LNodeCreate()
{
	struct LNode *p,*r;
	int x;

	p=(LNode *)malloc(sizeof(LNode));
	p->next=NULL;
	r=p;

	printf("将数据插入到单链表中(0为结束标志):");
	scanf("%d",&x);
	
	while (x!=0)
	{
		struct LNode *L=(LNode *)malloc(sizeof(LNode));
		L->data=x;
		L->next=r->next;
		r->next=L;
	    r=L;

		printf("将数据插入到单链表中:");
		scanf("%d",&x);
	}
	return p;

}

//尾插法建立不带头结点的
struct LNode *LNodeCreate1()
{
	struct LNode *p,*r;
	int x;

	p=(LNode *)malloc(sizeof(LNode));
	p->next=NULL;
	r=p;

	printf("将数据插入到单链表中(0为结束标志):");
	scanf("%d",&x);
	
	while (x!=0)
	{
		struct LNode *L=(LNode *)malloc(sizeof(LNode));
		L->data=x;

		if (p==NULL)//第一个结点的处理
		{
			p=L;
		}
		else
		r->next=L;
	    r=L;

		printf("将数据插入到单链表中:");
		scanf("%d",&x);
	}

	if (r!=NULL)//对于非空表，最后结点的指针放空指针
	{
		r->next=NULL;
	}
	return p;

}