資料結構之順序表

前言
順序表
項目詳細配置設定.
- 定義順序表
- 順序表之初始化方法實作
- 順序表之列印方法
- 順序表之尾插方法實作
  - 順序表之檢查容量方法實作
- 順序表之頭插方法實作
- 順序表之尾删方法實作
- 順序表之頭删方法實作
- 順序表之查找元素操作
- 順序表之任意位置插入
- 順序表之任意位置擦除
- 線性表之檢視有多少元素
- 線性表之修改任意位置
- 線性表之銷毀空間
綜合
- SeqList.h檔案内容
- SeqList.c檔案内容

講完算法效率,就正式開始我們的資料結構了,而今天部落客講解的内容是順序表

何為順序表?即一個

數組

,在

邏輯結構

和

實體結構

上,它都是連續的,這裡有個概念:邏輯與實體結構.

邏輯結構: 人為所想出來的,實際并不存在.

實體結構: 實際存在,可以觀察得到的

怎麼了解這兩個概念呢?舉個例子,假設有

甲乙丙丁戊

五個人.

如果挨着順序站成一排,五個人依次報數,會報1 2 3 4 5.
- 邏輯上來講,他們五個人是連續的,因為依次報數1 2 3 4 5
- 實體上來講,他們五個人 是連續的 ,因為順序是甲乙丙丁戊
如果五個人随機站成一排,五個人同樣依次報數,會報1 2 3 4 5
- 不是連續的 ,因為順序不是甲乙丙丁戊,可能丙丁甲乙戊,可能......

順序表即如此,實體與邏輯結構都連續.

實體結構是他的存儲位址,位址連續
邏輯結構是我們邏輯認為他的資料是連接配接在一起的

而順序表有兩種: 分别是

靜态版

與

動态版

,我們着重講解的就是

動态版

,因為

靜态版

其實就完完全全是個普通數組,講解意義不大.

何為

動态版

順序表? 即數組是動态的,容量不受限制,支援資料插入,删除,修改等一系列操作,下面我們開始實作.

部落客使用的是

vs2019

就以

vs2019

為例子搭建順序表工程.

建立一個 SeqList.h 順序表頭檔案
SeqList.c 順序表方法檔案
test.c 測試檔案

解釋:

SeqList.h 頭檔案用來建立順序表,和一些函數方法的聲明
SeqList.c 檔案用來實作順序表函數的定義
test.c 檔案用來測試每次實作一個函數後是否成功

下面我們開始實作各細節

我們以整型順序表為例:

struct SeqList
{
    int* data;     //動态數組.
    int size;      //數組實際已存儲數量
    int capacity;  //數組真實容量
};

到此為止,順序表就定義完畢.

但是有一個小問題需要修改,那就是我們在以後如果不再需要整型,就需要去改int,但是不要忘記,以後大家都是要接觸各種項目的,在一個項目裡面我們用到結構體次數非常多,如果去修改結構體裡面的int,那麼在後面的程式就會挨個修改int.

有沒有很好的辦法解決呢? 有,那就是typedef.

修改如下:

typedef int SQDataType;

typedef struct SeqList
{
    SQDataType* data;    
    int size;      
    int capacity;  
}SLT;  //給結構體改個短名

這樣的話,以後如果不需要int型,我們就可以直接修改

typedef

定義的

int

,非常便捷

定義好後,我們該将這段程式放在哪裡呢? 沒錯,上面已經講解了,我們将它放在 SeqList.h 頭檔案中.

順序表定義完成,我們就需要對他初始化.即實作一個初始化函數,前面部落客講解三子棋等遊戲項目也做過類似事情

void SeqListInit(SLT ps)
{
	ps.a = NULL;
	ps.size = ps.capacity = 0;
}

程式定義完畢後,怎樣放?

SeqList.h 中放程式初始化聲明: void SeqListInit(SLT ps);

SeqList.c 中放上面的函數定義.

進行測試是否成功:

#include "SeqList.h"

int main()
{
	SLT plist = { 0 };

	SeqListInit(plist);

	return 0;
}

我們調試發現,

plist

根本沒有達到我們的要求,那是怎麼回事呢?大家細細思考一下~

其實這是部落客之前在c語言篇中講解的 函數參數傳遞 問題,這裡就涉及到了.因為實參與形參是同類型的
就相當于函數内的 ps 隻是 plist 的一份臨時拷貝,而一個拷貝量的改變會影響 plist 嗎?答案顯然,不會
那怎麼辦呢? 這就是我們的指針知識,是以我們需要傳遞 plist 的位址.

修改版本如下:

void SeqListInit(SLT* ps)
{
	assert(ps);  //一定要斷言,因為ps不能是空指針,記得在頭檔案引<assert.h>
	ps->a = NULL;
	ps->size = ps->capacity = 0;
}

再測試:

#include "SeqList.h"

int main()
{
	SLT plist = { 0 };

	SeqListInit(&plist);

	return 0;
}

成功!!!!!!!!!!!!

在

SeqList.h

檔案聲明

void SeqListPrint(SLT* ps);

SeqList.c

檔案定義

void SeqListPrint(SLT* ps)
{
    for(int i = 0;i<ps->size;i++)
    {
        printf("%d-->",ps->data[i]);
    }
    printf("\n");
}

顧名思義,尾插,即在最後面插入.那我們想想怎麼實作呢?

如果隻傳遞 plist 可以插進去嗎? 不會! 還是老話,臨時拷貝量的改變與實參 plist 無關,是以需要傳遞位址
還需要傳遞需要插入的資料
還需要檢查順序表是否還有容量

SeqList.h

void SeqListPushBack(SLT* ps,SQDataType elem);

SeqList.c

void SeqListPushBack(SLT* ps,SQDataType elem)
{
    assert(ps); //ps不可以是空指針
    
    SeqListCheckCapacity(ps);//檢查是否需要增容,後續會實作
    
    ps->data[ps->size] = elem; //插進
    
    ps->size++;//實際容量加1
}

SeqList.h

void SeqListCheckCapacity(ps);

怎麼定義這個函數呢? 我們先看他的功能:

首先檢查是否容量已經裝滿了

滿的條件是 ps->size == ps->capacity

如果滿足上述條件,并且 ps->capacity 不等于0,說明滿了,就增加容量,增加方式是2倍增加

ps->capacity 等于0,說明還是空容量,就增加4個空間

SeqList.c

void SeqListCheckCapacity(ps)
{
    if(ps->size == ps->capacity)
    {
        int newcapacity = (ps->capacity) ==  0 ? 4:(ps->capacity)*2;
        SQDataType* p = (SQDataType*)realloc(ps->data,sizeof(SLT)*newcapacity);
        //上面兩步是如果capacity為0就給他4個空間
        //如果容量不為0,說明空間滿了,需要增容,而我們進行2倍增容.
        if(p==NULL)
        {
            perror("錯誤原因:");
            return;
        }
        ps->data = p;
        ps->capacity = newcapacity;
   }
}

測試尾插是否成功:

成功!!!!!!

SeqList.h

void SeqListPushFront(SLT* ps,SQDataType elem);

頭插,即在最前面的地方進行插入,那怎麼進行實作呢?

先檢查容量,看是否足夠

然後挪動資料,給第一個位置空出來

然後在空出來的位置,插進去

SeqList.c

void SeqListPushFront(SLT* ps,SQDataType elem)
{
	assert(ps);    
    SeqListCheckCapacity(ps);
    
    for(int i= ps->size;i>0;i--)
    {
        ps->data[i] = ps->data[i-1];
    }
    
    ps->data[0] = elem;
    ps->size++;
}

測試頭插是否成功:

SeqList.h

void SeqListPopBack(SLT* ps);

尾删,即删除最後一個.

但是怎麼算删除呢? 把最後一個置為0嗎?恩,肯定不可以.因為如果最後一個本就是0呢

那怎麼辦??

其實我們就讓size減去1就行了.為什麼?因為他即使還存在,但是size已經少去1了,即實際存儲中已經沒有最後一個了,我們看不見他了. 這也是為啥我們的電腦資料可以恢複,因為并沒有真正的删除.

SeqList.c

void SeqListPopBack(SLT* ps)
{
    assert(ps->size > 0); //必須保證有資料可以删除
    ps->size--;
}

測試尾删是否成功:

可以看到,當成功錄入4個資料後,也成功删除了4個資料,因為最後一個1删除後,列印了一個空行.剛好符合我們定義的列印函數

在删除第五次時候,就報出了錯誤:

size <= 0

是以測試成功!!!!!

SeqList.h

void SeqListPopFront(SLT* ps);

頭删之前,我們想想尾删是怎麼操作的.

嗯,沒錯,他直接size減1

那麼頭删呢? 需要把第一個置為什麼嗎?? 嗯,不需要,直接挨個把資料向前挪進行覆寫,然後size減一

SeqList.c

void SeqListPopFront(SLT* ps)
{
    assert(ps->size > 0);
    
	for(int i= 0;i<ps->size-1;i++)
    {
        ps->data[i] = ps->data[i+1];
    }
    ps->size--;
}

測試頭删是否成功:

成功!!!

要求:

給一個元素,查找是否在順序表内,如果在,傳回下标.

如果不在,傳回小于0的數字

SeqList.h

int SeqListFind(SLT* ps,SQDataType elem);

SeqList.c

int SeqListFind(SLT* ps,SQDataType elem)
{
    assert(ps->size > 0);
    assert(ps);
    for(int i= 0;i<ps->size;i++)
    {
        if(ps->data[i] == elem)
            return i;
    }
    return -1;
}

測試SeqListFind是否成功:

成功!!!!!

輸入指定下标, 想要插入的元素,就在此下标位置插入

實作方法: 輸入的下标位置及其後,所有資料都往後面挪.

然後插入資料,size加1

SeqList.h

void SeqListInsert(SLT* ps,size_t index,SQDataType elem);

size_t 是無符号整型

SeqList.c

void SeqListInsert(SLT* ps,size_t index,SQDataType elem)
{
    assert(ps);
    assert(ps->size >= index); //索引位置必須小于等于size

	SeqListCheckCapacity(ps); //看看容量是否足夠
	
    for(int i = ps->size;i>index;i--)
    {
        ps->a[i] = ps->a[i-1];
    }
    ps->a[index] = elem;
    ps->size++;
}

另一種實作版本:

void SeqListInsert(SLT* ps,size_t index,SQDataType elem)
{
    assert(ps);
	for(int i = ps->size-1;i>=index;i--)     
	{										 
		ps->a[i+1] = ps->a[i];
	}
    ps->size++;
}

**大家想想,這種寫法會有什麼問題??? **

沒錯,當這種寫法,順序表為空時候,就會陷入死循環,因為

index

是

size_t

類型,i就會發生整型提升

測試是否成功

成功!!

怎麼操作? 我們想想頭删

頭删就是直接覆寫,然後size-1

SeqList.h

void SeqListErease(SLT* ps,size_t index);

SeqList.c

void SeqListErease(SLT* ps,size_t index)
{
    assert(ps->size > 0);//必須有元素可以删除
    
    for(int i = index;i< ps->size-1;i++)
    {
        ps->data[i] = ps->data[i+1];
    }
    ps->size--;
}

測試是否成功:

SeqList.h

size_t SeqListSize(SLT* ps) ;

SeqList.c

size_t SeqListSize(SLT* ps) 
{
	assert(ps);
	return ps->size;
}

SeqList.h

void SeqListAt(SLT* ps, size_t index, SQDataType elem);

SeqList.c

void SeqListAt(SLT* ps, size_t index, SQDataType elem)
{
	assert(ps);
	assert(index < ps->size);
	ps->a[index] = elem;
}

測試:

SeqList.h

void SeqListDestroy(SLT* ps);

SeqList.c

void SeqListDestroy(SLT* ps)
{
    assert(ps);
    if(ps->data != NULL)
    {
        free(ps->data);
        ps->data = NULL;        
    }
    ps->size = ps->capacity = 0;
}

#pragma once 
#include <stdlib.h>
#include <assert.h>
#include <stdio.h>
typedef int SQDataType;

typedef struct SeqList
{
	SQDataType* a;
	int size;
	int capacity;
}SLT;


//開始增删查改


//初始化操作與銷毀空間操作
void SeqListInit(SLT* ps);
void SeqListDestroy(SLT* ps);
void SeqListPrint(SLT* ps);
void SeqListCheckCapacity(SLT* ps); // 增容檢查

//增加和删除操作
void SeqListPushBack(SLT* ps,SQDataType elem); 
void SeqListPushFront(SLT* ps,SQDataType elem);
void SeqListPopBack(SLT* ps);
void SeqListPopFront(SLT* ps);

//查找操作
int SeqListFind(SLT* ps,SQDataType elem);

//其他部位插入操作
void SeqListInsert(SLT* ps,size_t index,SQDataType elem);

//其他部位删除操作
void SeqListErease(SLT* ps, size_t index);

size_t SeqListSize(SLT* ps);

void SeqListAt(SLT* ps,size_t index,SQDataType elem);

#include "SeqList.h"

void SeqListInit(SLT* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->size = ps->capacity = 0;
}

void SeqListDestroy(SLT* ps)
{
	assert(ps);
	if (ps->a != NULL)
	{
		free(ps->a);
		ps->a = NULL;
	}
	ps->size = ps->capacity = 0;
}

void SeqListCheckCapacity(SLT* ps)
{
	if (ps->size == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;  //為什麼有這一步 ?? 防止給了0
		SQDataType* p = (SQDataType*)realloc(ps->a, newcapacity * sizeof(SLT));
		if (!p)
		{
			perror("增容失敗原因");
			return;
		}
		ps->a = p;
		ps->capacity = newcapacity;
	}
}

void SeqListPrint(SLT* ps)
{
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d-->",ps->a[i]);
	}
	printf("\n");
}

/**********************************************      增加與删除操作     **************************************/
void SeqListPushBack(SLT* ps, SQDataType elem)//尾插
{
	//assert(ps);
	//SeqListCheckCapacity(ps);
	//ps->a[ps->size] = elem;
	//ps->size++;

	SeqListInsert(ps,ps->size,elem);
}


void SeqListPushFront(SLT* ps, SQDataType elem)//頭插
{
	//assert(ps);
	//SeqListCheckCapacity(ps);
	//for (int i = ps->size; i > 0; i--)
	//{
	//	ps->a[i] = ps->a[i - 1];
	//}
	//ps->a[0] = elem;
	//ps->size++;

	SeqListInsert(ps, 0, elem);
}

void SeqListPopBack(SLT* ps)//尾删
{
	assert(ps->size > 0); //因為如果沒有資料,就無法删除了
	/*ps->size--;*/
	SeqListErease(ps,ps->size-1);
}

void SeqListPopFront(SLT* ps)
{
	assert(ps->size > 0); //因為如果沒有資料,就無法删除了
	//for (int i = 0; i < ps->size-1; i++)
	//{
	//	ps->a[i] = ps->a[i + 1];
	//}
	//ps->size--;
	SeqListErease(ps,0);
}

/*********************************************************************************************************/


int SeqListFind(SLT* ps, SQDataType elem)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
		if (ps->a[i] == elem)
			return i;
	return -1;
}

void SeqListInsert(SLT* ps,size_t index,SQDataType elem)
{
	assert(ps);
	assert(index <= ps->size);//必須有等号,因為如果插末尾,
	SeqListCheckCapacity(ps);

	for (int i = ps->size; i > index; i--)
	{
		ps->a[i] = ps->a[i - 1];   //注意這裡哦,這種寫法是最好的.比如下面的循環就會出問題
	}

	/*
	for(int i = ps->size-1;i>=index;i--)     這種寫法,如果size等于0或者index等于0時,會發現死循環.因為是無符号的
	{										 即避免 "有符号" 因為 提升導緻變成無符号而異常的大 
		ps->a[i+1] = ps->a[i];
	}
	*/
	ps->a[index] = elem;
	ps->size++;
}

void SeqListErease(SLT* ps,size_t index)
{
	assert(ps);
	assert(index < ps->size);
	for (int i = index; i < ps->size - 1; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
}

size_t SeqListSize(SLT* ps)  //通路結構體成員最好用函數去通路. 為什麼???想想
{
	assert(ps);
	return ps->size;
}

void SeqListAt(SLT* ps, size_t index, SQDataType elem)
{
	assert(ps);
	assert(index < ps->size);
	ps->a[index] = elem;
}

資料結構之順序表

繼續閱讀

FZU 1978 Repair the brackets

UVA 10344- 23 out of 5

ZOJ 3935 2016

POJ 2115 C Looooops

HDU 5381 The sum of gcd

ZOJ 1104 Leaps Tall Buildings

ZOJ 3700 Ever Dream

HDU 2821 Pusher

ZOJ 1199 Point of Intersection

UVA 1401 Remember the Word

UVA 620 Cellular Structure

ZOJ 2748 Free Kick

CSU 1567 Reverse Rot

UVA 519 Puzzle (II)

C++實作簡單順序表

詳解STM32單片機的堆棧