模拟实现线性表-顺序存储方式

我会带着你远行 2022-08-22 04:53 189阅读 0赞

我们知道在数据的存储方式中有一种结构叫线性表，那仫什仫是线性表呢？相信大家从名字上就可以理解：线性表就是像线一样性质的表；就像这种结构一样，在我们排队的过程中，一个跟着一个排队，有一个打头，有一个收尾，这样就如同有一根线把他们串起来一样，就可以叫做线性表啦！![吐舌头][tongue.gif]说到线性表我们就不得不提出它的两种存储结构了： 顺序存储结构和链式存储结构 ，在这里我们只讨论线性表的顺序存储结构，有兴趣的同学可以自己下去研究链式存储结构.

线性表的顺序存储结构说白了就是通过占位的形式把一块内存给占了，然后把相同数据类型的数据元素依次存放在这块空地中，有了这个特性我们实现顺序表就可以用数组的形式啦！请看下面一个顺序表存储的结构代码：

#define MAX 100
    typedef int DataType;
    typedef struct SeqList
    {
    	DataType Data[MAX];
    	int size;
    }SeqList,*pSeqList;

通过这个简单地例子我们就可以知道顺序存储需要三个特性:

1.存储空间的起始位置:数组Data；

2.线性表的最大存储容量:数组长度MAX;

3.线性表的当前长度:size;

看到这里我们就有点疑惑了，数据长度和线性表的长度有什仫区别吗？下面让我细细道来：

数组的长度是存放线性表存储空间的长度，是不变的；线性表的长度是线性表中数据元素的个数，是变化的；在任意时刻，线性表的长度应该小于数组的长度；

说道这里大家是不是对顺序表有了一定的了解呢？下面就让我们来模拟顺序表的几个常见的功能：

SeqList.h

#define _CRT_SECURE_NO_WARNINGS
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<assert.h>
    #define MAX 100
    typedef int DataType;
    typedef struct SeqList
    {
    	DataType Data[MAX];
    	int size;
    }SeqList,*pSeqList;
    void Print_SeqList(pSeqList pSeq);         //顺序表打印输出
    void Init_SeqList(pSeqList pSeq);          //初始化
    void Push_Back(pSeqList pSeq,DataType x); //在顺序表尾部插入元素
    void Pop_Back(pSeqList pSeq);             //在顺序表尾部删除元素
    void Push_front(pSeqList pSeq,DataType x);//在顺序表头部插入元素
    void Pop_front(pSeqList pSeq);            //在顺序表头部删除元素
    void Insert_SeqList(pSeqList pSeq,int pos,DataType x); //在顺序表的指定位置插入指定的元素
    void Remove_SeqList(pSeqList pSeq,DataType x);         //删除特定的元素
    void RemoveAll_SeqList(pSeqList pSeq,DataType x);      //删除全部的特定元素
    void Sort_SeqList(pSeqList pSeq);                      //对顺序表排序
    int Binary_Search(pSeqList pSeq,DataType x);           //二分查找

text.c

#include"SeqList_dyna.h"
    void menu()  
    {  
        printf("***********************************************\n");  
        printf("*****0.exit**1.Push_Back**2.Pop_Back***********\n");  
        printf("*****3.Push_front*********4.Pop_front**********\n");  
        printf("*****5.Insert_SeqList*****6.Remove_SeqList*****\n");  
        printf("*****7.RemoveAll_SeqList**8.Sort_SeqList*******\n");  
        printf("*****9.Print_SeqList******10. Binary_Search****\n");  
        printf("***********************************************\n");  
    } 
    
    int main()  
    {  
        int x=0;  
        int input=1;  
        int pos=0;  
    	int ret=0;
        SeqList pSeq;  
        Init_SeqList(&pSeq);  
        while(input)  
        {  
            menu();  
            printf("请选择一个你要进行的操作:");  
            scanf("%d",&input);  
            switch(input)  
            {  
            case 1:  
                printf("请输入一个你要插入的数据:");  
                scanf("%d",&x);  
                Push_Back(&pSeq,x);  
                break;  
            case 2:  
                 Pop_Back(&pSeq);  
                 break;  
            case 3:  
                printf("请输入一个你要插入的数据:");  
                scanf("%d",&x);  
                Push_front(&pSeq,x);  
                break;  
            case 4:  
                Pop_front(&pSeq);  
                break;  
            case 5:  
                printf("请输入一个你要插入的数据:");  
                scanf("%d",&x);  
                printf("请输入你要插入的位置:");  
                scanf("%d",&pos);  
                Insert_SeqList(&pSeq,pos,x);  
                break;  
            case 6:  
                printf("请输入一个你要删除的数据:");  
                scanf("%d",&x);  
                Remove_SeqList(&pSeq,x);  
                break;  
            case 7:  
                printf("请输入一个你要删除的数据:");  
                scanf("%d",&x);  
                RemoveAll_SeqList(&pSeq,x);  
                break;  
            case 8:  
                Sort_SeqList(&pSeq);  
                break;  
            case 9:  
                Print_SeqList(&pSeq);  
                break;  
            case 10:  
    			printf("请输入一个你要查找的数据:");  
                scanf("%d",&x);  
                ret=Binary_Search(&pSeq,x);  
    			if(pSeq.Data[ret] == x)
    			{
    				printf("查找成功\n");
    			}
    			else
    			{
    				printf("查找失败\n");
    			}
            case 0:  
                break;  
            default:  
                printf("您的输入错误请重新选择\n");  
                break;  
            }  
        }  
        system("pause");  
        return 0;  
    }

SeqList.c

#include"SeqList.h"
    void  Print_SeqList(pSeqList pSeq)
    {
    	int i=0;
    	assert(pSeq);
    	for(i=0;i<pSeq->size;i++)
    	{
    		printf("%d ",pSeq->Data[i]);
    	}
    	printf("\n");
    }
    
    void Init_SeqList(pSeqList pSeq)
    {
    	pSeq->size=0;
    	memset(pSeq->Data,0,MAX*sizeof(DataType));
    }
    
    void Push_Back(pSeqList pSeq,DataType x)  
    {
    	assert(pSeq);
    	if(pSeq->size == MAX)
    	{
    		printf("顺序表已满\n");
    		return ;
    	}
    	pSeq->Data[pSeq->size]=x;
    	pSeq->size++;
    }
    
    void Pop_Back(pSeqList pSeq)
    {
    	assert(pSeq);
    	if(pSeq->size == 0)
    	{
    		printf("顺序表已空\n");
    		return ;
    	}
    	pSeq->size--; 
    }
    
    void Push_front(pSeqList pSeq,DataType x)  //在顺序表的前面添加元素
    {
    	int i=0;
    	assert(pSeq);
    	if(pSeq->size == MAX)
    	{
    		printf("顺序表已满\n");
    		return ;
    	}
    	for(i=pSeq->size-1;i>=0;i--)
    	{
    		pSeq->Data[i+1]=pSeq->Data[i];
    	}
    	pSeq->Data[0]=x;
    	pSeq->size++;
    }
    
    void Pop_front(pSeqList pSeq)
    {
    	int i=0;
    	assert(pSeq);
    	for(i=0;i<pSeq->size;i++)
    	{
    		pSeq->Data[i]=pSeq->Data[i+1];
    	}
    	pSeq->size--;
    }
    
    void Insert_SeqList(pSeqList pSeq,int pos,DataType x)  //在指定指定位置插入元素x，pos是下标
    {
    	int i=0;
    	assert(pSeq);
    	if(pSeq->size == MAX)
    	{
    		printf("顺序表已满\n");
    		return ;
    	}
    	for(i=pSeq->size-1;i>=pos;i--)
    	{
    		pSeq->Data[i+1]=pSeq->Data[i];
    	}
    	pSeq->Data[pos]=x;
    	pSeq->size++;
    }
    
    void Remove_SeqList(pSeqList pSeq,DataType x)   //删除指定元素
    {
    	int i=0;
    	int ret=0;
    	ret=Binary_Search(pSeq,x);
    	assert(pSeq);
    	if(ret == -1)
    	{
    		printf("顺序表中没有此元素\n");
    		return ;
    	}
    	else
    	{
    		for(i=ret;i<pSeq->size;i++)
    		{
    			pSeq->Data[i]=pSeq->Data[i+1];
    		}
    	}
    	pSeq->size--;
    	printf("删除成功\n");
    }
    
    int Find_NUM(pSeqList pSeq ,DataType x)            //查找函数
    {
    	int i=0;
    	for(i=0;i<pSeq->size;i++)
    	{
    		if(pSeq->Data[i] == x)
    			return i;
    	}
    	return -1;
    }
    
    void RemoveAll_SeqList(pSeqList pSeq,DataType x)  //删除所有指定元素
    {
    	int i=0;
    	int j=0;
    	int ret=0;
    	assert(pSeq);
    	while(ret < pSeq->size)
    	{
    		ret=Find_NUM(pSeq,x);
    		if(ret == -1)
    		{	
    			printf("顺序表中没有此元素\n");
    			return ;
    		}
    		else
    		{
    			for(i=ret;i<pSeq->size;i++)
    			{
    				pSeq->Data[i]=pSeq->Data[i+1];
    			}
    		}
    		pSeq->size--;
    		ret++;
    	}
    	printf("删除成功\n");
    }
    
    void Sort_SeqList(pSeqList pSeq)   //冒泡排序
    {
    	int i=0;
    	int j=0;
    	DataType tmp=0;
    	int flag=0;
    	assert(pSeq);
    	for(i=0;i<pSeq->size-1;i++)
    	{
    		flag=0;                                 //对冒泡排序的优化
    		for(j=0;j<pSeq->size-1-i;j++)
    		{
    			if(pSeq->Data[j] > pSeq->Data[j+1])  //默认升序排列
    			{
    				tmp=pSeq->Data[j];
    				pSeq->Data[j]=pSeq->Data[j+1];
    				pSeq->Data[j+1]=tmp;
    				flag=1;
    			}
    		}
    		if(flag == 0)
    			break;
    	}
    }
    
    int Binary_Search(pSeqList pSeq,DataType x)
    {
    	int left=0;
    	int mid=0;
    	int right=pSeq->size-1;
    	assert(pSeq);
    	Sort_SeqList(pSeq);     //二分查找必须是有顺序的一组元素
    	while(left < right)
    	{
    		mid=(left+right)/2;
    		if(pSeq->Data[mid] < x)
    		{
    			left=mid;
    		}
    		else if(pSeq->Data[mid] > x)
    		{
    			right=mid;
    		}
    		else
    		{
    			return mid;
    		}
    	}
    	return -1;
    }

我们可以看到在代码的插入和删除操作中，不管是在头插还是尾插都是只需要变化线性表的当前长度size，可是如果是在不是头和尾的位置插入或删除呢？

在顺序表的指定位置插入指定元素:

我们可以来类比我们插队的行为（当然这是不好的行为了![尴尬][awkward.gif]），在原来一个已经排好队的队伍中要插入，此时是不是在这个位置之后的人都要向后挪一个位置，此时你要插的位置就空下来了，当然就可以插队啦！顺序表中的插入和这个类似，在这里我总结为以下四个步骤：

1.如果线性表长度大于或者等于数组长度，则顺序表已满不能继续插入；

2.从最后一个位置开始向前遍历到第pos个位置，分别将它们都向后挪动一个位置；

3.将要插入的元素填入位置pos;

4.表的长度加1；

在顺序表中删除指定元素：

同样我们可以用排队来类比，如果有一个人不想继续排队了离开了，此时这个位置是不是就空下来了呢？当然后面排队的人都会从这个位置往前挪一个位置.在这里我总结了以下四个步骤：

1.如果顺序表已空当然是不需要删除什仫元素的啦！

2.找到删除元素，在这里设定Find\_NUM函数来返回该元素的下标；

3.从删除元素开始遍历到最后一个元素位置分别将它们向前挪动一个位置；