模拟實作線性表-順序存儲方式

我們知道在資料的存儲方式中有一種結構叫線性表，那仫什仫是線性表呢？相信大家從名字上就可以了解：線性表就是像線一樣性質的表；就像這種結構一樣，在我們排隊的過程中，一個跟着一個排隊，有一個打頭，有一個收尾，這樣就如同有一根線把他們串起來一樣，就可以叫做線性表啦！

模拟實作線性表-順序存儲方式

說到線性表我們就不得不提出它的兩種存儲結構了：順序存儲結構和鍊式存儲結構，在這裡我們隻讨論線性表的順序存儲結構，有興趣的同學可以自己下去研究鍊式存儲結構.

線性表的順序存儲結構說白了就是通過占位的形式把一塊記憶體給占了，然後把相同資料類型的資料元素依次存放在這塊空地中，有了這個特性我們實作順序表就可以用數組的形式啦！請看下面一個順序表存儲的結構代碼：

#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，可是如果是在不是頭和尾的位置插入或删除呢？

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

我們可以來類比我們插隊的行為（當然這是不好的行為了

模拟實作線性表-順序存儲方式

），在原來一個已經排好隊的隊伍中要插入，此時是不是在這個位置之後的人都要向後挪一個位置，此時你要插的位置就空下來了，當然就可以插隊啦！順序表中的插入和這個類似，在這裡我總結為以下四個步驟：

1.如果線性表長度大于或者等于數組長度，則順序表已滿不能繼續插入；

2.從最後一個位置開始向前周遊到第pos個位置，分别将它們都向後挪動一個位置；

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

4.表的長度加1；

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

同樣我們可以用排隊來類比，如果有一個人不想繼續排隊了離開了，此時這個位置是不是就空下來了呢？當然後面排隊的人都會從這個位置往前挪一個位置.在這裡我總結了以下四個步驟：

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

2.找到删除元素，在這裡設定Find_NUM函數來傳回該元素的下标；

3.從删除元素開始周遊到最後一個元素位置分别将它們向前挪動一個位置；

4.表的長度減1；

看到這裡大家是不是對順序表的插入和删除有了更加深入的了解呢？相信是可以的，相信自己！

在最後用一句話勉勵自己：隻要你想，隻要你做，沒有什仫是不能完成的，加油！

模拟實作線性表-順序存儲方式

繼續閱讀

樹的基本概念(定義、基本術語、性質)

GSL--GNU Scientific Library

D5|哈希表，善用資料結構

如何成為一名.net 工程師?

BMP檔案結構及圖像每行位元組計算方法

D. Ehab the Xorcist(構造+思維)

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

[轉]ISUP信令的IAM消息詳細内容

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器