链表的创建及相应操作 C语言

àì夳堔傛蜴生んèń 2022-12-11 15:05 226阅读 0赞

## 数据结构c语言 链表 ##

通过上篇对线性表顺序存储表示的了解，今天进一步对线性表的链式表示进行尝试。本人小白，不喜勿喷。如有错误之处，还请原谅！  
**完整代码如下：**

#include <stdio.h> 
    #include <stdlib.h>
    #include <string.h> 
    
    typedef struct LNode
    { 
    	int data;//结点的数据域 
    	struct LNode *next;//结点的指针域 
    }LNode,*LinkList;//LinkList为指向结构体LNode的指针类型 
    
    void Interrupt(void)//创建一个中断函数 
    { 
    	while(1) //用于检测换行符，使函数脱离scanf的连续输出 
    		if(getchar()=='\n')
    			break;
    }
    
    bool InitList(LinkList &L)//初始化链表 构建一个空的线性表 
    { 
    	L = (LNode *)malloc(sizeof(LNode));
    	if (L == NULL)
            return false;
        L->next = NULL;//定义头结点 
        return true;
    }
    
    bool Empty(LinkList L)//判断链表是否为空 
    { 
        if (L->next == NULL)//若L为空，返回true，否则返回false 
            return true;
        return false;
    }
    
    LinkList CreatList1(LinkList &L)//尾插法创建链表 
    { 
    	int a,b,i;
    	L = (LinkList)malloc(sizeof(LNode));//创建一个链表头结点 
    	LNode *s,*r=L;
    	printf("请输入要创建链表的长度："); 
    	scanf("%d",&a);//输入要插入的链表长度 
    	Interrupt();//中断scanf 
    	L->next = NULL;//使其成为头结点 ，头结点条件 
    	printf("请输入链表数据：");
    	for( i = 0; i < a; i++ )
    	{ 
    		scanf("%d",&b);//输入要链表数据 
    		s = (LNode *)malloc(sizeof(LNode));//创建一个结点 
    		s->data = b;
    		r->next = s;
    		r = s; 
    	}
    	r->next = NULL;
    	Interrupt();
    	printf("\n");
    	return L;
    }
    
    LinkList CreatList2(LinkList &L)//头插法创建链表 
    { 
    	int a,b,i;
    	LNode *p;
    	L = (LinkList)malloc(sizeof(LNode));//创建一个链表头结点
    	L-> next = NULL;//使其成为头结点 
    	printf("请输入要创建链表的长度：");
    	scanf("%d",&a);//输入要插入的链表长度 
    	Interrupt();
    	printf("请输入链表数据：");
    	for(i=0;i<a;i++)
    	{ 
    		scanf("%d",&b);//输入要链表数据 
    		p = (LNode *)malloc(sizeof(LNode));
    		p -> data = b;
    		p->next = L->next;
    		L->next = p;
    	}
    	Interrupt();
    	printf("\n");
    	return L;
    }
    
    void traverseLNode(LinkList L)//遍历链表，并输出链表 
    { 
    	LNode *p=L->next;//创建一个结点并指向头结点的下一个结点 
    	while(1)//建立一个死循环，链表最后一个结点指向NULL，以此为判断break循环条件 
    	{ 
    		printf("%d ",p->data);//输出p结点中的数据 
    		if(p->next==NULL)
    		{ 
    			printf("\n");
    			break;
    		}	
    		p = p->next;//使p结点指向p的下一个结点 
    	}
    }
    
    int Length(LinkList L)//求链表长度 
    { 
    	int j=0;
    	LNode *p = L;
    	while(1)//建立死循环，以尾结点指向NULL为判断条件，使循环break 
    	{ 
    		p = p->next;
    		j++;
    		if(p->next==NULL)
    			break;
    	}
    	return j;//返回链表长度 
    }
    void LocateElem(LinkList L,int e)//按值查找操作。在表L中查找具有给定关键字值的元素 
    { 
    	int i;
    	scanf("%d",&e);//要查找的值 
    	Interrupt();
    	LNode *p = L;//创建一个结点并指向头结点 
    	bool a = true;//利用bool类型，来判断链表中是否存在要查找的值 
    	while(1) //建立死循环，以尾结点指向NULL为判断条件，使循环break 
    	{ 
    		p = p->next;
    		i++;
    		if(p->data==e)
    		{ 
    			printf("第 %d 位\n",i);
    			a = false;
    		}
    			
    		if(p->next==NULL)
    			break;
    	}
    	if(a)//链表中没有要查找的值 
    		printf("没找到！\n");
    }
    int GetElem(LinkList L,int i)//按位查找操作 
    { 
    	LNode *p = L;//创建一个结点并指向头结点 
    	scanf("%d",&i);//输入要查找第几位 
    	Interrupt();
    	int j;
    	if(i<1 || i>Length(L))//判断输入的i值是否合理 
    	{ 
    		printf("ERROR!");
    		return false; 
    	}
    	else
    	{ 
    		for(j=0;j<i;j++)//利用循环，是p结点指向第i位 
    			p = p->next;
    		printf("%d\n",p->data);//输出第i位的值 
    		return true;
    	}
    }
    int ListInsert(LinkList &L,int i,int e)//插入操作 
    { 
    	int j;
    	LNode *p=L;//创建一个结点并指向头结点 
    	scanf("%d %d",&i,&e);//输入要插入链表的位置，和值 
    	Interrupt();
    	if(i<1 || i>Length(L)+1)//判断插入链表的位置是否合理 
    	{ 
    		printf("ERROR!\n");
    		return 0;
    	}
    	else
    	{ 
    		for(j=1;j<i;j++)//利用循环，是p结点指向第i-1位 
    			p = p->next;
    		LNode *s=(LNode*)malloc(sizeof(LNode));//创建一个新结点 
    		s->data = e;
    		s->next = p->next;
    		p->next = s;
    		printf("插入成功！\n");
    		return 0;
    	}
    }
    int ListDelete(LinkList &L,int i)//删除操作 
    { 
    	LNode *p = L;//创建一个结点并指向头结点 
    	scanf("%d",&i);//输入要删除链表的结点位置 
    	Interrupt();
    	int j;
    	if(i<1||i>Length(L))//判断删除的结点位置是否合理 
    	{ 
    		printf("ERROR!\n");
    		return 0;
    	}
    	else
    	{ 
    		for(j=1;j<i;j++)//利用循环，是p结点指向第i-1位 
    			p = p->next;
    		LNode *s = (LNode*)malloc(sizeof(LNode));//创建一个新结点 
    		s = p->next;//新结点被赋值为p的下一个结点 
    		printf("删除成功！删除值为： %d\n",s->data);
    		p->next = s->next;	
    		return 0;	
    	}
    }
    int main()
    { 
    	int a,b,i=0; 
    	char c;
    	LinkList L;//将L定义为LinkList类型的变量，便于直接引用 
    	InitList(L);
    	printf("输入0为尾插法（其他为头插法）："); 
    	scanf("%d",&b);
    	Interrupt();
    	if(b==0)
    		CreatList1(L);//尾插法 
    	else
    		CreatList2(L);//头插法 
    	traverseLNode(L);
    	printf("操作输入序号选择：\n 1：遍历链表\n 2:链表的按位查找\n 3:删除链表元素\n 4:插入链表元素\n 5:链表的按值查找\n 6：表长\n输入#退出\n");	
    	while(1)
    	{ 
    		int f = 0;
    		printf("请选择："); 
    		scanf("%c",&c);
    		Interrupt();
    		switch(c)
    		{ 
    			case '1': printf("遍历并输出链表： ");traverseLNode(L); break;
    			case '2': printf("链表的按位查找（取值位置）： ");GetElem(L,a); break;
    			case '3': printf("删除并返回要删除的元素（删除的位置）： ");ListDelete(L,a); break;
    			case '4': printf("插入元素（位置 插入的元素）： ");ListInsert(L,a,a); break;
    			case '5': printf("链表的按值查找（输入要查找的元素）： ");LocateElem(L,a); break;
    			case '6': a = Length(L);printf("%d",a); break;
    			case '#': f = 1; break;
    			default: printf("ERROR\n");
    		}
    		if (f == 1) 
    		{ 
    			printf("已正常退出!\n");
    			break;
    		}
    	}
    	free(L); 
    	return 0;
    }

**（完）**