链表的基本运算，插入，删除和输出

心已赠人 2022-05-06 13:28 223阅读 0赞

【问题描述】

设计并实现线性表的单链表存储和运算。

【基本要求】

实现单链表的插入、删除和遍历运算，每种操作用一个函数实现。 插入操作：将一个新元素插入表中指定序号的位置。 删除操作：将指定序号的元素从表中删除。 遍历操作：从表头按次序输出所有元素的值，若是空表，则输出信息“empty list!”。

【实现提示】

1.  程序运行时，首先在 main 函数中创建空的、带头结点的单链表。然后多次调用实现插入操作的函数（每次都将元素在序号 1 位置上插入），将元素依次插入表中，最后调用实现遍历操作的函数输出所有元素。之后再多次调用实现删除操作的函数将表还原为空表（每次都删除第 1 个元素，每删除 一个元素后，将表中剩余元素都输出一次）。
2.  单链表结点类型定义：
3.  typedef int ElemType;     //为简化起见，元素类型定义为整型
4.  typedef struct Node\{

ElemType data; struct Node \*next;

\}Node, \*LinkList;

5.为了简化指针参数传递，使用 c++的引用参数，存储**源程序**时注意后缀名应为 **cpp**。 （其他实 验题目在此处的处理相同）

6.创建链表时，可以多次调用插入函数（插入函数的功能是在链表的第 i 个元素结点前插入一个 新结点），通过不断地在链表中增加结点来实现，也可以定义一个专门创建链表的函数，调用一次该函 数就完成链表中所有结点的创建（当然，此后需要在链表中插入一个新结点时调用前述的插入函数即 可）。

/****************
    链表的基本运算***
    插入删除和输出***
    by凉柒_lq    ***
    ****************/
    #include<stdio.h>
    #include<stdlib.h>
    
    typedef int Elemtype;
    typedef struct LNode
    {
    	Elemtype data;
    	struct LNode* next;
    }LNode;
    typedef LNode* Linklist;
    typedef int Status;
    
    #define overflow -2
    #define true  1
    #define false 0
    #define ok 1
    #define error 0
    
    /*表头插入法*/
    Status Createlist(Linklist &L, int n)
    {
    	int i;
    	Linklist p;
    	Status ListTravel(Linklist &L);
    	L = (Linklist)malloc(sizeof(LNode));
    	if (!L)
    		exit(overflow);
    	L->next = NULL;
    
    	for (i = n; i>0; i--)
    	{
    		p = (Linklist)malloc(sizeof(LNode));
    		if (!p)
    			exit(overflow);
    		scanf("%d", &p->data);
    		p->next = L->next;
    		L->next = p;
    	}
    	    printf("\n");
    	    ListTravel(L);
    	  return ok;
    }
    
    /*空表判断函数*/
    /*链表存在且只有头结点*/
    Status ListEmpty(Linklist &L)
    {
    	if (L != NULL && L->next == NULL)
    	{
    		printf("empty list!\n");
    		return true;
    	}
    	else
    		return false;
    }
    
    /*头结点删除函数*/
    Status Topdellist(Linklist &L)
    {
    	Status Listlength(Linklist &L);
    	Status ListTravel(Linklist &L);
    	int j; Linklist p;
    	int b = Listlength(L);
            for (j = 0; j<b; j++)
    	{
    		p = L;
    		p = p->next;
    		L->next = p->next;
    		free(p);
    		ListTravel(L);
    	}
    	if(ListEmpty(L))
    	   return ok;
    }
    
    
    /*链表长度函数*/
    Status Listlength(Linklist &L)
    {
    	Linklist p;
    	int i;
    	if (L)
    	{
    		i = 0;
    		p = L->next;
    		while (p)
    		{
    			i++;
    			p = p->next;
    		}
    	}
    	return i;
    }
    
    
    /*遍历并输出,调用visit函数*/
    Status ListTravel(Linklist &L)
    {
    	void Visit(Linklist &p);
    	Linklist p;
    	if (!L)
    		return 0;
    	else
    		p = L->next;
    	while (p)
    	{
    		Visit(p);
    		p = p->next;
    	}
    	if(L->next!=NULL)
    	  printf("\n\n");
    	return ok;
    }
    
    /*visit函数*/ 
    void Visit(Linklist &p)
    {
         printf("%d ",p->data);
    }
    
    
    /*主函数*/
    int main()
    {
    	Linklist L;
    	Createlist(L, 5);
    	Topdellist(L);
    	return 0;
    }

运行结果截图：

![70][]

代码不难，细看就可以看懂，明天会更新第二种方法。

原创，转载注明出处。

[70]: /images/20220506/fd017ad15c60436586a6e57884bec06b.png