单链表的定义及基本操作

梦里梦外; 2022-08-10 00:56 187阅读 0赞

# 建立单链表，完成链表（带表头结点）的基本操作：建立链表、插入、删除、输出 #

#include<stdio.h>
    #include<malloc.h>
    #include<stdlib.h>
    #define OK 1
    #define ERROR 0
    typedef int Status;
    typedef int ElemType;
    typedef struct LNode
    {
    	ElemType data;
    	struct LNode *next;
    }LNode,*LinkList;
    //头插法建立单链表
    void CreateList_L(LinkList &L,int n)
    {//逆位序输入n个元素的值，建立带表头结点的单链线性表L
    	int i;
    	LinkList p;
    	L=(LinkList)malloc(sizeof(LNode));//建立头结点
    	L->next=NULL;
    	for(i=n;i>0;--i)
    	{
    		p=(LinkList)malloc(sizeof(LNode));//建立新的结点
            scanf("%5d",&p->data);
    		p->next=L->next;//插入到表头
    		L->next=p;
    	}
    }
    Status ListInsert_L(LinkList &L,int i,ElemType e)
    {//在带头结点的单链线性表L中第i个位置之前插入元素e
    	LinkList p,s;
    	int j;
    	p=L;
    	j=0;
    	while(p&&j<i-1)
    	{
    		p=p->next;++j;
    	}//寻找第i-1个结点
    	if(!p||j>i-1)//i小于1或者大于表长加1
    		return ERROR;
    	s=(LinkList)malloc(sizeof(LNode));//生成新结点
    	s->data=e;
    	s->next=p->next;//插入L中
    	p->next=s;
    	return OK;
    }
    Status ListDelete_L(LinkList &L,int i,ElemType &e)
    {//在带头结点的单链线性表L中，删除第i个元素，并由e返回其值
        LinkList p,q;
    	int j;
     	p=L;
    	j=0;
        while(p->next&&j<i-1)
    	{//寻找第i个结点，并令p指向其前驱
    		p=p->next;++j;
    	}
    	if(!(p->next)||j>i-1)
    		return ERROR;//删除位置不合理
    	q=p->next;p->next=q->next;
    	e=q->data;free(q);//删除并释放结点
    	return OK;
    }
    void ListShow_L(LinkList &L)
    {//输出链表的元素
    	LinkList p;
    	p=L->next;
    	while(p)
    	{
    		printf("%5d",p->data);
    		p=p->next;
    	}
    	printf("\n");
    }
    int main()
    {
    	int n,i;
    	LinkList L;
    	ElemType e,a;
    	printf("创建链表的表长为：");
    	scanf("%d",&n);
    	printf("\n");
    	printf("输入表中元素为：");
    	CreateList_L(L,n);
    	ListShow_L(L);
    	printf("\n输入要插入的元素位置和值：");
    	scanf("%d %d",&i,&e);
    	if(ListInsert_L(L,i,e))
    	{
    		ListShow_L(L);
    	}
    	else
    	    printf("输入不合法，失败\n");
    	printf("\n输入要删除的元素位置：");
    	scanf("%d",&i);
    	if(ListDelete_L(L,i,a))
    	{
    		printf("删除元素的值为：%d\n",a);
    		ListShow_L(L);
    	}
    	else
    		printf("输入不合法，失败\n");
    	return 0;
    }