运用C语言建立循环单链表？

清疚 2022-05-11 04:38 236阅读 0赞

#include<stdio.h>
    #include<malloc.h>
    
    typedef char ElemType;
    typedef struct LNode
    {
    	ElemType data;
    	struct LNode *next;
    }DLinkList;

//首先对基本函数进行声明，以及后面方面在主函数中进行调用

void InitList(DLinkList *&L);
    void CreateList(DLinkList *&L);
    void DispList(DLinkList *L);
    bool ListEmpty(DLinkList *L);
    int ListLength(DLinkList *L);
    bool ListInsert(DLinkList *&L,int i,ElemType e);
    bool GetElem(DLinkList *L,int i,ElemType &e);
    int locateElem(DLinkList *L,ElemType e);
    bool ListDelete(DLinkList *&L,int i,ElemType &e);
    void DestroyList(DLinkList *&L);
    int main()
    {
    	DLinkList *L;
    	ElemType e;
    	InitList(L);
    	CreateList(L);
    	DispList(L);
    	//判断该单链表是否为空
    	if(ListEmpty(L)==1)
    		printf("该单链表为空\n");
    	else
    		printf("该单链表不为空\n");
    	ListInsert(L,2,'a');
    	ListInsert(L,1,'e');
    	DispList(L);
    	printf("该单链表的长度为：%d\n",ListLength(L));
    	if(GetElem(L,5,e)==1)
    		printf("%c\n",e);
    	else
    		printf("该元素不存在。");
    	printf("%d\n",locateElem(L,'d'));
    	ListDelete(L,1,e);
    	DispList(L);
    	DestroyList(L);
    	return 0;
    }

//初始化循环单链表

void InitList(DLinkList *&L)
    {
    	L=(DLinkList *)malloc(sizeof(DLinkList));//创建一个空的头结点
    	L->next=L;
    }

//运用尾插法对循环单链表进行建立

//创建新的循环单链表
    void CreateList(DLinkList *&L)
    {
    	DLinkList *p,*s;
    	ElemType i;
    	L=(DLinkList *)malloc(sizeof(DLinkList));
    	p=L;
    	p->next=L;
    	while(1)
    	{
    		scanf("%c",&i);
    		if(i=='z')
    			break;
    		s=(DLinkList *)malloc(sizeof(DLinkList));
    		s->data=i;
    		s->next=p->next;
    		p->next=s;
    		p=s;
    	}
    }

//输出循环单链表

//输出循环单链表
    void DispList(DLinkList *L)
    {
    	DLinkList *p;
    	p=L->next;
    	while(p!=L)
    	{
    		printf("%c",p->data);
    		p=p->next;
    	}
    	printf("\n");
    }

//判断单链表是否为空

bool ListEmpty(DLinkList *L)
    {
    	return (L->next==L);
    
    }

//求单链表的长度

int ListLength(DLinkList *L)
    {
    	int j=0;
    	DLinkList *p=L->next;
    	while(p!=L)
    	{
    		j++;
    		p=p->next;
    	
    	}
    	return j;
    }

//插入数据元素在循环单链表中

//插入数据元素
    bool ListInsert(DLinkList *&L,int i,ElemType e)
    {
    	int j=1;
    	DLinkList *p=L->next,*s;
    
    	while(p!=L&&j<i-1)//寻找第i-1个节点
    	{
    		p=p->next;
    		j++;
    	}	
    	if(i==1)
    	{
    		s=(DLinkList *)malloc(sizeof(DLinkList));
    		s->data=e;
    		s->next=p;
    		L->next=s;
    		return true;
    	}
    	else	if(j!=i-1)
    				return false;
    			else
    			{
    				s=(DLinkList *)malloc(sizeof(DLinkList));
    				s->data=e;
    				s->next=p->next;
    				p->next=s;
    				return true;
    			}
    	
    }

//寻找单链表中某个位置的元素值

bool GetElem(DLinkList *L,int i,ElemType &e)
    {
    	int j=1;
    	DLinkList *p=L->next;
    	while(j<i&&p!=L)
    	{
    		p=p->next;
    		j++;
    	
    	}
    	if(j!=i)
    		return false;
    	else
    	{
    		e=p->data;
    		return true;
    	}
    
    }

//按元素值查找该元素在该单链表中的位置

//按元素值查找
    int locateElem(DLinkList *L,ElemType e)
    {
    	int i=1;
    	DLinkList *p=L->next;
    	while(p!=L&&p->data!=e)
    	{
    		i++;
    		p=p->next;
    	}
    	if(p==L)
    		return 0;
    	else
    		return i;
    
    
    }

//删除循环单链表中某个元素值

bool ListDelete(DLinkList *&L,int i,ElemType &e)
    {
    	int j=1;
    	DLinkList *p=L->next,*q;
    	while(j<i-1&&p!=L)
    	{
    		j++;
    		p=p->next;
    	}
    	if(i==1)
    	{
    		q=L->next;
    		if(q==L)
    			return false;
    		e=q->data;
    		L->next=q->next;
    		free(q);
    		return true;
    	
    	}else if(j!=i-1)
    			return false;
    		  else
    		  {
    			q=p->next;
    			if(q==L)
    				return false;
    			e=q->data;
    			p->next=q->next;
    			free(q);
    			return true;
    		  }
    }

//销毁循环单链表

void DestroyList(DLinkList *&L)
    {
    	DLinkList *pre=L,*p=L->next;
    	while(p!=L)
    	{
    		free(pre);
    		pre=p;
    		p=pre->next;
    	}
    	free(pre);
    }