模拟实现顺序表-动态的存储方式

不念不忘少年蓝@ 2022-08-22 15:27 241阅读 0赞

模拟实现顺序表-静态的方式

[http://blog.csdn.net/qq\_34328833/article/details/51494234][http_blog.csdn.net_qq_34328833_article_details_51494234]

我们知道静态的存储方式中数组Data的大小是固定的是100，也就是说我们最多只能存储100组信息数据，当要增加信息数据时我们就需要扩大数组Data的大小，是不是很麻烦呢？这就要提出我们今天要实现的版本 -动态的存储方式.

首先我们先来看顺序表的结构成员，实现代码如下：

typedef int DataType;  
    
    typedef struct SeqList  
    {  
        DataType *Data;  
        int size;  
    	int capacity;   //容量
    }SeqList,*pSeqList;

我们先给出程序的测试代码：

#include"SeqList_dyna.h"
    
    void text()
    {
    	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:  
                Bubble_Sort(&pSeq);  
                break;  
            case 9: 
    			Insertion_Sort(&pSeq);
                break;  
            case 10:  
    			Select_Sort(&pSeq);
    			break;
    		case 11:
    			Print_SeqList(&pSeq); 
    			break;
    		case 12:
    			printf("请输入一个你要查找的数据:");  
                scanf("%d",&x);  
                ret=Binary_Search(&pSeq,x);  
    			if(pSeq.Data[ret] == x)
    			{
    				printf("查找成功\n");
    			}
    			else
    			{
    				printf("查找失败\n");
    			}
    			break;
            case 0: 
    			Free_SeqList(&pSeq);
                break;  
            default:  
                printf("您的输入错误请重新选择\n");  
                break;  
            }  
        }  
    }
    
    int main()  
    {  
    	text();
        system("pause");  
        return 0;  
    }

既然要动态增加 存储信息的个数，malloc当然少不了啦！malloc用于给指针Data分配初始空间当顺序表长度增加到和顺序表的容量一致时，此时就需要realloc进行扩容工作了，当添加信息时就需要判断是否需要增加扩容了；分配空间和扩容的代码 实现如下：

分配空间：

void Init_SeqList(pSeqList pSeq)  
    {  
        //pSeq->size=0;  
        //memset(pSeq->Data,0,MAX*sizeof(DataType));  
    	pSeq->Data=(DataType *)malloc(sizeof(DataType)*MAX_INIT);
    	if(NULL == pSeq->Data)
    	{
    		printf("out of memory\n");
    		exit(EXIT_FAILURE);
    	}
    	pSeq->size=0;
    	pSeq->capacity=MAX_INIT;
    }

扩容：

void Judge_Full(pSeqList pSeq)    //判断容量是否满了
    {
    	if(pSeq->capacity == pSeq->size)
    	{
    		DataType *tmp=(DataType *)realloc(pSeq->Data,(pSeq->capacity+MAX_ADD)*sizeof(DataType));
    		if(NULL == pSeq->Data)
    		{
    			printf("out of memory\n");
    			exit(EXIT_FAILURE);
    		}
    		else
    		{
    			pSeq->Data=tmp;
    			pSeq->capacity+=MAX_ADD;
    		}
    	}
    }

SeqList\_dyna.h

#define _CRT_SECURE_NO_WARNINGS  
    #ifndef __SEQLIST_D_H__    //防止重复引入
    #define __SEQLIST_D_H__
    #include<stdio.h>  
    #include<stdlib.h>  
    #include<string.h>  
    #include<assert.h>  
    
    #define MAX 100  
    #define MAX_INIT 3
    #define MAX_ADD 3
    typedef int DataType;  
    
    typedef struct SeqList  
    {  
        DataType *Data;  
        int size;  
    	int capacity;   //容量
    }SeqList,*pSeqList;  
    
    void menu();
    void Print_SeqList(pSeqList pSeq);         //打印输出  
    void Init_SeqList(pSeqList pSeq);          //初始化  
    void Judge_Full(pSeqList pSeq);            //判断容量是否满了
    void Free_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 Bubble_Sort(pSeqList pSeq);            //冒泡排序 
    void Insertion_Sort(pSeqList pSeq);         //直接插入排序 
    void Select_Sort(pSeqList pSeq);            //选择排序
    int Find_NUM(pSeqList pSeq ,DataType x);               
    int Binary_Search(pSeqList pSeq,DataType x);          
    
    
    #endif //__SEQLIST_D_H__

SeqList\_dyna.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.Bubble_Sort********\n");  
    	printf("*****9.Insertion_Sort*****10.Select_Sort*******\n"); 
        printf("****11.Print_SeqList******12.Binary_Search*****\n");  
        printf("***********************************************\n");  
    } 
    
    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));  
    	pSeq->Data=(DataType *)malloc(sizeof(DataType)*MAX_INIT);
    	if(NULL == pSeq->Data)
    	{
    		printf("out of memory\n");
    		exit(EXIT_FAILURE);
    	}
    	pSeq->size=0;
    	pSeq->capacity=MAX_INIT;
    }  
    
    void Judge_Full(pSeqList pSeq)    //判断容量是否满了
    {
    	if(pSeq->capacity == pSeq->size)
    	{
    		DataType *tmp=(DataType *)realloc(pSeq->Data,(pSeq->capacity+MAX_ADD)*sizeof(DataType));
    		if(NULL == pSeq->Data)
    		{
    			printf("out of memory\n");
    			exit(EXIT_FAILURE);
    		}
    		else
    		{
    			pSeq->Data=tmp;
    			pSeq->capacity+=MAX_ADD;
    		}
    	}
    }
    
    void Push_Back(pSeqList pSeq,DataType x)    
    {  
        assert(pSeq);   
    	Judge_Full(pSeq);
        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);  
    	Judge_Full(pSeq);
        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);  
    	Judge_Full(pSeq);
        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= Find_NUM(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 Bubble_Sort(pSeqList pSeq)   //冒泡排序  
    {  
        int i=0;  
        int j=0; 
    	int m=0;
        DataType tmp=0;  
        int flag=0;
    	int k=pSeq->size-1;
        assert(pSeq);  
        for(i=0;i<pSeq->size-1;i++)  
        {  
    		m=0;
            flag=0;                                 //对冒泡排序的优化  
            for(j=0;j<k;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;  
    				m=j;       //用来记录最后一次交换的位置
                }  
            }  
            if(flag == 0)  
                break; 
    		k=m;      //将k置成最后一次交换的位置
        }  
    }  
    
    void Insertion_Sort(pSeqList pSeq)         //直接插入排序 
    {
    	int i=0;
    	int j=0;
    	int k=0;
    	DataType tmp=0;
    	for(i=1;i<pSeq->size;i++)   //选取第一个元素为有序的将其他数字插入它的两边
    	{
    		tmp=pSeq->Data[i];
    		for(j=i-1;j>=0;j--)
    		{
    			if(pSeq->Data[i] >= pSeq->Data[j])   //升序排列
    			{
    				break;
    			}
    		}
    		for(k=i-1;k>j;k--)   //移位,空出位置插入tmp,也可以交换
    		{
    			pSeq->Data[k+1]=pSeq->Data[k];
    		}
    		pSeq->Data[j+1]=tmp;
    	}
    }
    
    void Select_Sort(pSeqList pSeq)            //选择排序，升序排列
    {
    	int i=0;
    	int j=0;
    	int min=0;
    	for(i=0;i<pSeq->size-1;i++)
    	{
    		min=i;
    		for(j=i+1;j<pSeq->size;j++)
    		{
    			if(pSeq->Data[j] < pSeq->Data[min])   //找到i后面所有数据的最小值
    			{
    				min=j;
    			}
    		}
    		if(i != min)    //找到的最小值的下标和初始的i值不同,交换
    		{
    			DataType tmp=pSeq->Data[i];
    			pSeq->Data[i]=pSeq->Data[min];
    			pSeq->Data[min]=tmp;
    		}
    	}
    }
    
    int Binary_Search(pSeqList pSeq,DataType x)  
    {  
        int left=0;  
        int mid=0;  
        int right=pSeq->size-1;  
        assert(pSeq);  
        Bubble_Sort(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;  
    }  
    
    void Free_SeqList(pSeqList pSeq)
    {
    	free(pSeq->Data);
    	pSeq->Data=NULL;
    	exit(0);
    }

text.c

在程序的实现过程中排序使用了三种方法:冒泡排序，直接插入排序和选择排序，实现可参见上述SeqList\_dyna代码块中的函数实现。

[http_blog.csdn.net_qq_34328833_article_details_51494234]: http://blog.csdn.net/qq_34328833/article/details/51494234