C語言線性表中順序表超詳細理解

2022-03-29 19:00:40

一、本章重點

1.線性表和順序表的概念

2.動態和靜態順序表介面實現

3.線上0j訓練

二、線性表

滿足下列條件的即為線性表：

線性表（linear list）是n個具有相同特性的資料元素的有限序列。
線性表在邏輯上是線性結構，但是在物理結構上並不一定是連續的。（這裡的物理結構一般指實體地址空間）。

三、順序表

滿足下列條件的即為順序表：

是線性表
物理結構上是連續的

順序表一般可以分為：

靜態順序表：使用定長陣列儲存。
動態順序表：使用動態開闢的陣列儲存。

四、靜態順序表介面實現

4.1順序表初始化

void SeqListInint(SeqList* s)
{
	assert(s);
	memset(s->a, 0, sizeof(SeqListDataType) * MAXSIZE);
	s->size = 0;
}

還有一種簡單初始化的方式：

在建立順序表s的時候直接賦值0，即SeqList s = { 0 };

4.2順序表列印

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

傳順序表的地址，使用for迴圈語句，逐步列印陣列元素。

4.3順序表尾插

void SeqListPushBack(SeqList* s, int x)
{
	assert(s);
	if (s->size == MAXSIZE)
	{
		printf("當前空間已滿，無法繼續新增n");
		exit(1);
	}
	s->a[s->size] = x;
	s->size++;
}

先檢查s是否位空，如果為空則報錯，再檢查是否滿了，如果滿了，則提示已滿並結束程式。

4.4順序表尾刪

void SeqListPopBack(SeqList* s)
{
	assert(s);
	if (s->size == 0)
	{
		printf("當前順序表為空，無法刪除n");
		exit(1);
	}
	s->size--;
}

直接s->size--即可，不需要把最後的元素置為0.

4.5順序表頭插

void SeqListPushFront(SeqList* s, int x)
{
	if (s->size == MAXSIZE)
	{
		printf("空間已滿，無法繼續新增n");
		exit(1);
	}
	if (s->size == 0)
	{
		s->a[s->size] = x;
		s->size++;
		return;
	}
	else
	{
		int j = 0;
		for (j = s->size - 1; j >= 0; j--)
		{
			s->a[j + 1] = s->a[j];
		}
		s->a[0] = x;
		s->size++;
	}
}

先將元素往後移動，移動完之後再放入要插入的元素。

4.6順序表頭刪

void SeqListPopFront(SeqList* s)
{
	if (s->size == 0)
	{
		printf("當前順序表為空，無法刪除n");
		exit(1);
	}
	int j = 0;
	for (j = 1; j <s->size; j++)
	{
		s->a[j - 1] = s->a[j];
	}
	s->size--;
}

使用移動元素的方式，覆蓋前面的內容，達到刪除的目的。

4.7順序表任意位置插入

void SeqListInsert(SeqList* s, int pos, int x)
{
	if (s->size == MAXSIZE)
	{
		printf("當前空間已滿，無法繼續新增n");
		exit(1);
	}
	if (pos < 0||pos>s->size)
	{
		printf("插入位置有誤，無法插入n");
		exit(1);
	}
	if (pos == s->size)
	{
		s->a[s->size] = x;
		s->size++;
		return;
	}
	for (int j = s->size - 1; j >= pos; j--)
	{
		s->a[j + 1] = s->a[j];
	}
	s->a[pos] = x;
	s->size++;
}

找到元素位置，移動元素，再將要插入的元素放入。

4.8順序表任意位置刪除

void SeqListErase(SeqList* s, int pos)
{
	assert(s);
	if (s->size == 0)
	{
		printf("順序表為空，刪除失敗n");
		exit(1);
	}
	if (pos >= s->size || pos < 0)
	{
		printf("刪除位置不存在n");
		exit(1);
	}
	int j = 0;
	for (j = pos; j < s->size-1; j++)
	{
		s->a[j] = s->a[j + 1];
	}
	s->size--;
}

找到要刪除的位置，通過移動覆蓋要刪除的元素。

五、動態順序表介面實現

5.1順序表的初始化

void SeqListInint(SeqList* s)
{
	assert(s);
	s->a = (DataType*)malloc(10 * sizeof(DataType));
	s->size = 0;
	s->capacity = 10;
}

將元素個數size置為0

開闢a的空間

初始容量設定為10

5.2順序表列印

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

5.3順序表尾插

void SeqListPushBack(SeqList* s, DataType x)
{
	assert(s);
	SeqListCheckCapacity(s);
	s->a[s->size] = x;
	s->size++;
}

5.4順序表尾刪

void SeqListPopBack(SeqList* s)
{
	assert(s);
	if (s->size == 0)
	{
		printf("當前順序表為空，刪除失敗n");
		exit(1);
	}
	s->size--;
}

5.5順序表頭插

void SeqListPushFront(SeqList* s, DataType x)
{
	assert(s);
	SeqListCheckCapacity(s);
	if (s->size == 0)
	{
		s->a[0] = x;
		s->size++;
	}
	else
	{
		int end = s->size - 1;
		while (end >= 0)
		{
			s->a[end + 1] = s->a[end];
			end--;
		}
		s->a[0] = x;
		s->size++;
	}
}

5.6順序表頭刪

void SeqListPopFront(SeqList* s)
{
	assert(s);
	if (s->size == 0)
	{
		printf("當前順序表為空，無法刪除n");
		exit(1);
	}
	if (s->size == 1)
	{
		s->size--;
		return;
	}
	else
	{
		int i = 0;
		for (i = 0; i <=s->size-2 ; i++)
		{
			s->a[i] = s->a[i + 1];
		}
		s->size--;
	}
}

5.7順序表任意位置插入

void SeqListInsert(SeqList* s, int pos, DataType x)
{
	assert(s);
	SeqListCheckCapacity(s);
	if (pos<0 || pos>s->size)
	{
		printf("插入位置不存在n");
		exit(1);
	}
	else if(pos==s->size)
	{
		s->a[s->size] = x;
		s->size++;
	}
	else
	{
		int i = 0;
		for (i = s->size - 1; i >= pos; i--)
		{
			s->a[i + 1] = s->a[i];
		}
		s->a[pos] = x;
		s->size++;
	}
}

5.8順序表任意位置刪除

void SeqListErase(SeqList* s, int pos)
{
	assert(s);
	if (s->size == 0)
	{
		printf("當前順序表為空，刪除失敗n");
		exit(1);
	}
	if (pos<0||pos>s->size-1)
	{
		printf("要刪除的位置不存在n");
		exit(1);
	}
	else
	{
		int i = 0;
		for (i = pos; i <= s->size - 2; i++)
		{
			s->a[i] = s->a[i + 1];
		}
		s->size--;
	}
}

六、線上0j練習

一、移除元素（力扣）

給你一個陣列 nums 和一個值 val，你需要原地移除所有數值等於 val 的元素，並返回移除後陣列的新長度。

不要使用額外的陣列空間，你必須僅使用 O(1) 額外空間並原地修改輸入陣列。

元素的順序可以改變。你不需要考慮陣列中超出新長度後面的元素。

例一：

輸入：nums = [0,1,2,2,3,0,4,2], val = 2 輸出：5, nums = [0,1,4,0,3] 解釋：函數應該返回新的長度 5, 並且 nums 中的前五個元素為 0, 1, 3, 0, 4。注意這五個元素可為任意順序。你不需要考慮陣列中超出新長度後面的元素。

思路：用兩個指標，一個用來遍歷陣列，另一個指向你要存資料的地方。

如果可以申請額外的空間的話，一般來說，我們可以這樣做：申請一個新的陣列空間，用來存放非val值的資料。其實這個新的空間我們可以直接把nums陣列原空間直接當做新空間使用，我們只需遍歷一遍nums陣列即可。

int removeElement(int* nums, int numsSize, int val)
{
    int i = 0;
    int j = 0;
    for(i=0;i<numsSize;i++)
    {
        if(nums[i]!=val)
        {
            nums[j]=nums[i];
            j++;
        }
    }
    return j;
}

二、合併兩個有序陣列（力扣）

給你兩個按非遞減順序排列的整數陣列 nums1 和 nums2，另有兩個整數 m 和 n ，分別表示 nums1 和 nums2 中的元素數目。

請你合併 nums2 到 nums1 中，使合併後的陣列同樣按非遞減順序排列。

注意：最終，合併後陣列不應由函數返回，而是儲存在陣列 nums1 中。為了應對這種情況，nums1 的初始長度為 m + n，其中前 m 個元素表示應合併的元素，後 n 個元素為 0 ，應忽略。nums2 的長度為 n

例一

輸入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 輸出：[1,2,2,3,5,6] 解釋：需要合併 [1,2,3] 和 [2,5,6] 。合併結果是 [1,2,2,3,5,6] ，其中斜體加粗標註的為 nums1 中的元素。

思路：從後往前放，nums1和nums2中較大的數。（參考一）

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
    int end1 = m-1;
    int end2 = n-1;
    int k = m + n -1;
    while(end1>=0 && end2>=0)
    {
        if(nums1[end1] >= nums2[end2])
        {
            nums1[k]=nums1[end1];
            k--;
            end1--;
        }
        else
        {
            nums1[k]=nums2[end2];
            k--;
            end2--;
        }
    }
    while(end2>=0)
    {
        nums1[k]=nums2[end2];
        k--;
        end2--;
    }
}

到此這篇關於C語言線性表中順序表超詳細理解的文章就介紹到這了,更多相關C語言順序表內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！