数据结构整理 ——线性表

喜欢ヅ旅行 2022-04-12 04:23 153阅读 0赞

# **线性表**

--------------------

## 1.线性表是什么 ##

线性表是最常用且最简单的一种数据结构。简而言之，一个线性表是n个数据元素的有序序列。

## 个人理解，可以看做是我们平时经常用的数组。 ##

## 2.线性表的实现方式 ##

线性表的实现方式参照《数据结构》（严蔚敏，吴伟民编著版本）有两种：**顺序和链式**。

## 3.顺序线性表的优点 ##

跟我们平常使用数组一样，使用顺序线性表可以很方便的实现 **改变表中任意一个位置的元素的值** ，但是与之相对的，当我们想要删除其中一个节点或者在其中增添一个节点则会变得**异常困难**。具体我们会在代码中感受到

## 4.顺序线性表的实现 ##

#include <stdio.h>
    #include <stdlib.h>
    #include "init.h"//用来定义各种常量
    #define Init_Size_List 100//初始长度
    #define LISTINGREMENT 10//初始增加长度
    
    typedef int Elemtype;//适应变化可以随意更改
    typedef struct list
    {
    	Elemtype* elem;
    	int length;
    	int listsize;
    }sqlist;
    //线性表的顺序定义
    Status InitList(sqlist &L)
    {
    	L.elem=(Elemtype*)malloc(Init_Size_List*sizeof(Elemtype));
    	if(!L.elem)
    	return OVERFLOW;
    	L.length=0;
    	L.listsize=Init_Size_List;
    	return OK;
    }
    //线性表的初始化
    Status DestoryList(sqlist &L)
    {
    	free(L.elem);
    	L.elem=NULL;
    	L.length=0;
    	L.listsize=0;
    	return OK;
    }
    //摧毁线性表
    Status ClearList(sqlist &L)
    {
    	free(L.elem);
    	InitList(L);
    	return OK;
    }
    //清除线性表
    Status ListEmpty(sqlist &L)
    {
    	if(L.length>0)
    		return FALSE;
    	else
    		return TRUE;
    
    }
    //判断线性表是否为空
    Status ListLength(sqlist L)
    {
    	if(!ListEmpty(L))
    	{
    		return L.length;
    	}
    	else
    	{
    		return ERROR;
    	}
    }
    //给出线性表的长度
    Status GetElem(sqlist L,int i,Elemtype &e)
    {
    	if(i<=ListLength(L))
    	{
    		e=L.elem[i];
    		return OK;
    	}
    	else
    	{
    		return ERROR;
    	}
    }
    //得到线性表中第i个数的值
    Status LocateElem(sqlist L,Elemtype e)
    {
    	for(int i=1;i<=L.length;i++)
    	{
    		if(L.elem[i]==e)
    			return i;
    	}
    	return ERROR;
    }
    //定位线性表中元素e的位置
    Status PriorElem(sqlist L,Elemtype cur_e,Elemtype &pre_e)
    {
        int Station=LocateElem(L,cur_e);
    	if(Station==1)
    	{
    		return ERROR;
    	}
    	else if(Station==ERROR)
    	{
    		return ERROR;
    	}
    	for(int i=Station+1;i<=L.length;i++)
    	{
    		if(L.elem[i]==cur_e)
    		{
    			pre_e=Station;
    			return OK;
    		}
    	}
    	return ERROR;
    }
    //若cur_e是线性表中的元素，且不是第一个，用pre_e返回它的前驱
    Status NextElem(sqlist L,Elemtype cur_e,Elemtype &next_e)
    {
    	int Station=LocateElem(L,cur_e);
    	if(Station==L.length)
    		return ERROR;
    	else if(Station==ERROR)
    		return ERROR;
    	for(int i=Station+1;i<=L.length;i++)
    	{
    		if(L.elem[i]==cur_e)
    		{
    			next_e=i;
    			return OK;
    		}
    	}
    	return ERROR;
    }
    //若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱
    Status ListInsert(sqlist &L,int i,Elemtype e)
    {
    	if(i<=ListLength(L)+1&&i>=1)
    	{
    		if(ListLength(L)+1>=Init_Size_List)
    		{
    			Elemtype *newbase;
    			newbase=(Elemtype*)realloc(L.elem,(L.listsize+LISTINGREMENT)*sizeof(Elemtype));
    			if(!newbase)
    				exit(OVERFLOW);
    			L.elem=newbase;
    			L.listsize+=LISTINGREMENT;
    		}
    		int q=i;
    		for(int p=L.length;p>=q;--p)
    		{
    			L.elem[p+1]=L.elem[p];
    		}
    		L.elem[i]=e;
    		L.length++;
    	}
    	return ERROR;
    }
    //在第i个位置插入e元素
    Status ListDelete(sqlist &L,int i,Elemtype &e)
    {
    	if(ListEmpty(L))
    	return ERROR;
    	else
    	{
    		if(i>=1&&i<=ListLength(L))
    		{
    			int q=i;
    			e=L.elem[i];
    			for(int p=q;p<=L.length;p++)
    			{
    					L.elem[p]=L.elem[p+1];
    			}
    			L.length--;
    			return OK;
    		}
    		else
    		return ERROR;
    	}
    }
    //删除第i个位置的元素
    Status ListVisit(sqlist L)
    {
        for(int i=1;i<=L.length;i++)
        {
            printf("%d\n",L.elem[i]);
        }
        return OK;
    }
    //遍历输出数组
    int main()
    {
        sqlist a;
        InitList(a);
        for(int i=1;i<=5;i++)
        {
            a.elem[i]=i;
        }
        a.length=5;
        printf("%d\n",LocateElem(a,2));
        int c;
        GetElem(a,3,c);
        printf("%d\n",c);
        ListVisit(a);
        printf("%d\n",ListEmpty(a));
        ListInsert(a,3,4);
        ListVisit(a);
        int b;
        ListDelete(a,2,b);
        printf("%d\n",b);
        ListVisit(a);
        printf("%d\n",DestoryList(a));
        return 0;
    }//仅仅只是用来测试

困难所在  
每删除或者是增添一个元素我们都要将线性表中的每一个位置的值向后移或者是向前移，而在链式表中则相对地更为简单

附：  
书中有很多常量的定义，我将之放在了init.h的头文件中（偷一个小懒）具体如下

#define TRUE 1
    #define FALSE 0
    #define OK 1
    #define ERROR 0
    #define INFEASIBLE -1
    #define OVERFLOW -2
    typedef int Status;