【数据结构】C语言实现顺序链表

这是在上数据结构课程时候的练习，以后拿过来随时用。

#include <stdio.h>
#include <malloc.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

typedef int elemtype;

#define TRUE 0
#define FALSE 1
#define OK 1
#define ERROR 0
#define INFEASIBLE -1


#if(1)

typedef struct LNode
{
	struct LNode *next;
	int date;
}*LinkList;

//typedef LNode *LinkList;

#endif

#if(0)

typedef struct LNode
{
	struct LNode *next;

	elemtype data;
};

#endif

void InitList(LinkList L)
{
	L = (LinkList)malloc(sizeof(struct LNode));
	if(!L)
	{
		exit(-1);
	}
	L->next = NULL;
}

void DestroyList(LinkList L)
{
	LinkList q;
	while(L)
	{
		q = L->next;
		free(L);
		L = q;
	}
}

void ClearList(LinkList L)
{
	LinkList p,q;
	p = L->next;          //p = L的话就销毁了链表相当于DestroyList
	while(p)
	{
		q = p->next;
		free(p);
		p = q;
	}

	L->next = NULL;
}

int ListEmpty(LinkList L)
{
	if(L->next)
	{
		return FALSE;
	}

	return TRUE;
}

int ListLength(LinkList L)
{
	int i = 0;
	LinkList p = L->next;        //应该设立一个新的指针代替L，

	while(p)
	{
		i++;
		p = p->next;
	}

	return i;
}

int GetElem(LinkList L,int i,elemtype *e)
{
	int j;
	LinkList p;
	p = L;

	for(j = 0; j < i; j++)
	{
		p = p->next;
	}

	if(!p)
	{
		return ERROR;
	}

	*e = p->date;

	return OK;

}

int LocateElem(LinkList L,elemtype *e)
{
	int i = 0;
	LinkList p;
	p = L->next;

	while(p)
	{
		i++;

		if(p->date == *e)
		{
			return i;
		}

		p = p->next;
	}

	return 0;
}

int PriorElem(LinkList L,elemtype cur_e,elemtype *pre_e)
{
	LinkList p,q;

	p = L->next;

	while(p->next)
	{
		q = p->next;

		if(q->date == cur_e)
		{
			*pre_e = p->date;

			return OK;

		}

		p = q;
	}

	return INFEASIBLE;
}

int NextElem(LinkList L,elemtype *next_e)
{
	LinkList p;               //remember it

	p = L->next;

	while(p->next)
	{

		if(p->date == cur_e)
		{
			*next_e = p->next->date;
			return OK;
		}

		p = p->next;

	}

	return INFEASIBLE;

}

int ListInsert(LinkList L,elemtype e)
{
	int j = 1;
	LinkList p = L,s;

	if(i < 1)
	{
		return ERROR;
	}
	s = (LinkList)malloc(sizeof(struct LNode));
	s->date = e;
	if(i == 1)
	{
		s->next = L;

		L = s;
	}
	else
	{
		while(p && j < i - 1)
		{
			p = p->next;
			j++;
		}
		if(!p)
		{
			return ERROR;

		}
		s->next = p->next;
		p->next = s;
	}
	return OK;

}

int ListDelete(LinkList L,elemtype *e)
{
	int j = 1;
	LinkList p = L->next;
	LinkList q = L;

	while(j < i)
	{
		p = p->next;
		q = q->next;
		j++;
	}

	if(!p || j >= i)
	{
		return ERROR;
	}

	q->next = p->next;
	*e = p->date;
	free(p);

	return OK;
}

void ListTraverse(LinkList L)
{
	LinkList q = L;
	while(q)
	{
		printf("%d ",q->date);
		q = q->next;
	}

	//printf("nn");
}


#if(0)

void main()
{ // 除了几个输出语句外，主程序和main2-1.cpp很像
	LinkList L = NULL; // 与main2-1.cpp不同
	elemtype e,e0;
	int i;
	int j,k;

	InitList(L);

	for(j=1; j<=5; j++)
	{
		i = ListInsert(L,1,&j);
	}

	printf("在L的表头依次插入1～5后：L=");

	ListTraverse(L); // 依次对元素调用print()，输出元素的值

	i = ListEmpty(L);

	printf("L是否空：i=%d(1:是0:否)n",i);

	ClearList(L);

	printf("清空L后：L=");

	ListTraverse(L);
	i = ListEmpty(L);

	printf("L是否空：i=%d(1:是0:否)n",i);

	for(j=1; j<=10; j++)
	{
		ListInsert(L,j,&j);
	}

	printf("在L的表尾依次插入1～10后：L=");

	ListTraverse(L);
	GetElem(L,5,&e);

	printf("第5个元素的值为%dn",e);
	for(j=0; j<=1; j++)
	{
		k = LocateElem(L,&j);
		if(k)
		{
			printf("第%d个元素的值为%dn",k,j);
		}
		else
		{
			printf("没有值为%d的元素n",j);
		}
	}
	for(j=1;j<=2;j++) // 测试头两个数据
	{
		GetElem(L,&e0); // 把第j个数据赋给e0
		i = PriorElem(L,e0,&e); // 求e0的前驱
		if(i == INFEASIBLE)

			printf("元素%d无前驱n",e0);
		else
			printf("元素%d的前驱为%dn",e);
	}
	for(j=ListLength(L)-1; j<=ListLength(L); j++) // 最后两个数据
	{
		GetElem(L,&e0); // 把第j个数据赋给e0
		i=NextElem(L,&e); // 求e0的后继
		if(i == INFEASIBLE)
		{
			printf("元素%d无后继n",e0);
		}
		else
		{
			printf("元素%d的后继为%dn",e);
		}
	}
	k = ListLength(L); // k为表长

	for(j=k+1; j>=k; j--)
	{
		i = ListDelete(L,&e); // 删除第j个数据
		if(i == ERROR)
		{
			printf("删除第%d个元素失败n",j);
		}
		else
		{
			printf("删除第%d个元素成功，其值为%dn",e);
		}
	}
	printf("依次输出L的元素：");

	ListTraverse(L);
	DestroyList(L);

	printf("销毁L后：L=%un",L);
}

#endif

void main()
{
	LinkList L = NULL;
	int i,j;
	InitList(L);

	for(j=1; j<=5; j++)
	{
		i = ListInsert(L,j);
	}

	printf("在L的表头依次插入1～5后：L=");

	ListTraverse(L); // 依次对元素调用print()，输出元素的值
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!