实现单链表各种基本运算的算法

男娘i 2022-05-05 10:58 172阅读 0赞

编写一个头文件LinkList.h，实现单链表的各种基本运算，并在此基础上设计一个主程序（exp2\_2.cpp）完成如下功能：

1.  初始化单链表h
2.  依次采用尾插法插入a,b,c,d,e元素
3.  输出单链表h
4.  输出单链表h的长度
5.  判断单链表h是否为空
6.  输出单链表h的第3个元素
7.  输出元素a的位置
8.  在第4个元素位置上插入f元素
9.  输出单链表h
10. 删除h的第3个元素
11. 输出单链表h
12. 释放单链表h

**头文件：**

/*文件名：LinkList.h*/
    # include<stdio.h>
    # include<malloc.h>
    # include<stdlib.h>
    
    
    # define TRUE 1
    # define FALSE 0
    # define OK 1
    # define ERROR 0
    # define INFEASIBLE -1
    # define OVERFLOW -2
    
    
    typedef int Status;
    typedef char ElemType;
    
    
    //定义单链表的存储结构
    typedef struct LNode
    {
    	ElemType date;
    	struct LNode *next; 
    }LNode , *LinkList;
    
    
    //构造一个单链表
    Status InitList(LinkList &L)
    {
    	L=(LinkList)malloc(sizeof(LNode));//生成结点
    	if(!L)
    	{
    		return OVERFLOW;
    	}
    	L->next = NULL;
    	return OK;
    }
    
    
    //销毁单链表
    Status DestroyList(LinkList &L)
    {
    	LinkList q = L;
    	while(q != NULL)
    	{
    		LinkList p = q;
    		q = q->next;
    		free(p);
    		p = NULL;
    	}
    	return OK;
    }
    
    
    
    //判断是否为空，为空返回ture,否则返回false
    Status ListEmpty(LinkList L)
    {
    	if(!L->next)//为空
    	{
    		return TRUE;
    	}
    	else
    		return FALSE;
    }
    
    
    //返回单链表的长度
    Status ListLength(LinkList L)
    {
    	int i = 0;
    	LNode * p;
    	p = L->next;
    	while(p != NULL)
    	{
    		i++;
    		p = p->next;
    	}
    	return i;
    }
    
    
    //打印单链表中的元素
    void DispList(LinkList &L)
    {
      LinkList p;
      p = L->next;
      while(p != NULL)
      {
    	  printf("%c" , p->date);
    	  p = p->next;
      }
      printf("\n");
    }
    
    
    //从单链表L中查找第i个元素，由参数e返回其元素的值
    Status GetElem(LinkList L , int i , ElemType &e)
    {
    	int j = 1; 
    	struct LNode *p = L->next;
    	while(p && j<i)
    	{
    		p = p->next;
    		++j;
    	}
    	if(!p || j>i) //第i个元素不存在
    	{
    	  return ERROR;
    	}
    	e = p->date;  //取第i个元素
    	return OK;
    }
    
    
    
    //在单链表L中查找元素e的位置，不存在则返回0
    Status LocateElem(LinkList L, ElemType e)
    {
    	int i = 0;
    	LinkList p = L->next;
    	while (p)
    	{
    		i++;
    		if (p->date == e)
    		{
    			return i;
    		}
    		p = p->next;
    	}
    	return 0;
    
    }
    
    
    
    //在单链表L中第i个位置之前插入元素e
    Status ListInsert(LinkList &L, int i, ElemType e)
    {
    	int j = 0;
    	LinkList p = L, s;
    	while (p && j<i-1)
    	{ 
    		p = p->next;
    		++j;
    	}
    	if (!p || j>i-1)
    	{
    		return ERROR;
    	}
    	s = (LinkList)malloc(sizeof(LNode));//生成新节点
    	s->date = e;
    	s->next = p->next; //把所有元素向后移一位
    	p->next = s;
    	return OK;
    }
    
    
    
    //单链表L中删除第i个元素，并由e返回其值
    Status ListDelete(LinkList &L, int i, ElemType &e)
    {
    	int j = 0;
    	LinkList p = L, q;
    	while (p->next && j<i-1)
    	{
    		p = p->next;
    		++j;
    	}
    	if (!(p->next) || j>i-1)
    	{
    		return ERROR;
    	}
    	q = p->next;
    	p->next = q->next;
    	e = q->date;
    	free(q);
    		return OK;
    }

**主函数：**

#include "LinkList.h"  
    int main()  
    {  
        int l;  
        LinkList(L);  
        ElemType e;  
        printf("初始单链表L\n");  
        InitList(L);  
        printf("依次采用尾插法插入a , b , c , d , e元素\n");  
        ListInsert(L , 1 , 'a');  
        ListInsert(L , 2 , 'b');  
        ListInsert(L , 3 , 'c');  
        ListInsert(L , 4 , 'd');  
        ListInsert(L , 5 , 'e');  
        printf("输出单链表L:");  
        DispList(L);  
        l=ListLength(L);  
        printf("单链表长度l=%d\n" , l);  
        printf("单链表L为%s\n" , (ListEmpty(L)?"空":"非空"));  
        GetElem(L , 3 , e);  
        printf("单链表的第3个元素=%c\n" , e);  
        printf ("元素a的位置=%d\n" , LocateElem(L , 'a'));  
        printf("在第4个元素位置上插入f元素\n");  
        ListInsert(L , 4 , 'f');  
        printf("单链顺序表L:");  
        DispList(L);  
        printf("删除L的第3个元素\n");  
        ListDelete(L , 3 , e);  
        printf("输出单链表L:");  
        DispList(L);  
        printf("释放单链表L\n");  
        free(L);  
      
    return 0;   
    }

结果：

![70][]

[70]: /images/20220505/14bd18266c9a4f489d535ccb4858da93.png