欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C語言數(shù)據(jù)結(jié)構(gòu)深入探索順序表

 更新時間：2022年03月25日 11:14:32   作者：天影云光  
順序表，全名順序存儲結(jié)構(gòu)，是線性表的一種，線性表用于存儲邏輯關(guān)系為“一對一”的數(shù)據(jù)，順序表自然也不例外，不僅如此，順序表對數(shù)據(jù)的物理存儲結(jié)構(gòu)也有要求，跟隨下文來具體了解吧

1.線性表

線性表（linear list）是n個具有相同特性的數(shù)據(jù)元素的有限序列。 線性表是一種在實際中廣泛使用的數(shù)據(jù)結(jié)構(gòu)，常見的線性表：順序表、鏈表、棧、隊列、字符串…

線性表在邏輯上是線性結(jié)構(gòu)，也就說是連續(xù)的一條直線。但是在物理結(jié)構(gòu)上并不一定是連續(xù)的，線性表在物理上存儲時，通常以數(shù)組和鏈式結(jié)構(gòu)的形式存儲

2.順序表

2.1概念及結(jié)構(gòu)

順序表是用一段物理地址連續(xù)的存儲單元依次存儲數(shù)據(jù)元素的線性結(jié)構(gòu)，一般情況下采用數(shù)組存儲。在數(shù)組上完成數(shù)據(jù)的增刪查改。

順序表一般可以分為：

靜態(tài)順序表：使用定長數(shù)組存儲元素。

動態(tài)順序表：使用動態(tài)開辟的數(shù)組存儲

2.2 接口實現(xiàn)

靜態(tài)順序表只適用于確定知道需要存多少數(shù)據(jù)的場景。靜態(tài)順序表的定長數(shù)組導致N定大了，空間開多了浪費，開少了不夠用。所以現(xiàn)實中基本都是使用動態(tài)順序表，根據(jù)需要動態(tài)的分配空間大小，所以下面我們實現(xiàn)動態(tài)順序表。

#pragma once
#include<stdio.h>
#include<assert.h>
typedef int SLDataType;
typedef struct SeqList
{
	int* a;
	int size;	 //存儲數(shù)據(jù)個數(shù)
	int capacity;//存儲空間大小
}SeqList;

void SeqListInit(SeqList* psl);//初始化
void SeqListDestroy(SeqList* psl);//銷毀

void SeqListPrint(SeqList* psl);//打印

void SeqListCheckCapacity(SeqList* psl);//檢查容量

int SeqListFind(SeqList* psl, SLDataType x);//查找

//時間復雜度是O（1）
void SeqListPushBack(SeqList* psl, SLDataType x);//尾插
void SeqListPopBack(SeqList* psl);//尾刪

//時間復雜度是O（N）
void SeqListPushFront(SeqList* psl, SLDataType x);//頭插
void SeqListPopFront(SeqList* psl);//頭刪

//時間復雜度是O（N）
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);//在pos位置插入
void SeqListErase(SeqList* psl, size_t pos);//在pos位置刪除

2.2.1初始化

就是將元素分別初始化。

//初始化
void SeqListInit(SeqList* psl)
{
	assert(psl);
	psl->a = NULL;
	psl->size = 0;
	psl->capacity = 0;
}

2.2.2 檢查容量

初始化時容量為0，想要放數(shù)據(jù)得增加容量，每次插入數(shù)據(jù)也得保證容量充足，為了方便，我們先寫一個用于檢查容量并增容的函數(shù)。

//檢查容量
void SeqListCheckCapacity(SeqList* psl)
{
	assert(psl);

	//如果滿了，就要擴容
	if (psl->size == psl->capacity)
	{
		size_t newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;//防止一開始capacity=0無法*2增容
		SLDataType* tmp = realloc(psl->a, sizeof(SLDataType) * newCapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			psl->a = tmp;
			psl->capacity = newCapacity;
		}
	}
}

2.2.3 順序表打印

就是遍歷一次把所有元素打印出來，這樣可以檢查函數(shù)寫的是否正確，及時訂正。

//打印
void SeqListPrint(SeqList* psl)
{
	assert(psl);

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

}

2.2.4 順序表尾插

請?zhí)砑訄D片描述

//尾插
void SeqListPushBack(SeqList* psl, SLDataType x)
{
	assert(psl);

	//如果滿了，就要擴容
	SeqListCheckCapacity(psl);

	psl->a[psl->size] = x;
	psl->size++;
}

2.2.5 順序表尾刪

只需要把size-1這樣的話下一個數(shù)據(jù)就會把尾部數(shù)據(jù)覆蓋掉，達到刪除的效果。

//尾刪
void SeqListPopBack(SeqList* psl)
{
	assert(psl);

	if (psl->size > 0)
	{
		psl->size--;
	}
}

2.2.6 順序表頭插

//頭插
void SeqListPushFront(SeqList* psl, SLDataType x)
{
	assert(psl);

	//如果滿了，就要擴容
	SeqListCheckCapacity(psl);

	//挪動數(shù)據(jù),騰出頭部位置
	int end = psl->size - 1;
	while (end >= 0)
	{
		psl->a[end + 1] = psl->a[end];
		end--;
	}
	psl->a[0] = x;
	psl->size++;

}

2.2.7 順序表頭刪

將第一個位置覆蓋掉，然后用尾刪的思路將最后一個數(shù)據(jù)刪除。

//頭刪
void SeqListPopFront(SeqList* psl)
{
	assert(psl);

	//挪動數(shù)據(jù)覆蓋第一個
	if(psl->size>0)
	{
		int begin = 1;
		while (begin < psl->size)
		{
			psl->a[begin - 1] = psl->a[begin];
			begin++;
		}
	}
	psl->size--;
}

2.2.8 順序表在pos位置插入x

思路跟頭插很像,但內(nèi)含陷阱！

//在pos位置插入
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x)
{
	assert(psl);

	//如果滿了，就要擴容
	SeqListCheckCapacity(psl);

	溫和檢測
	//if (pos > psl->size)
	//{
	//	printf("pos越界：%d\n", pos);
	//	return;
	//}
	//暴力檢測
	assert(pos <= psl->size);

	//pos=0的時候由于無符號整型判斷時的整型提升，會出問題
	//size_t end = psl->size - 1;
	//while (end >= pos)
	//{
	//	psl->a[end + 1] = psl->a[end];
	//	end--;
	//}
	//psl->a[pos] = x;
	//psl->size++;

	//這樣寫才不會有問題
	size_t end = psl->size;
	while (end > pos)
	{
		psl->a[end] = psl->a[end - 1];
		--end;
	}

	psl->a[pos] = x;
	psl->size++;
}

2.2.9 順序表刪除pos位置的值

思路跟頭刪很像

//在pos位置刪除
void SeqListErase(SeqList* psl, size_t pos)
{
	assert(psl);
	assert(pos < psl->size);

	size_t begin = pos + 1;
	while (begin < psl->size)
	{
		psl->a[begin - 1] = psl->a[begin];
		++begin;
	}

	psl->size--;
}

2.2.10 尾插、尾刪、頭插、頭刪的改進

有了上面兩個通常情況下的增刪函數(shù)，我們就能改進尾插、尾刪、頭插、頭刪。這樣能夠快速寫完順序表

//尾插
void SeqListPushBack(SeqList* psl, SLDataType x)
{
	assert(psl);
	SeqListCheckCapacity(psl);
	SeqListInsert(psl, psl->size, x);//在size位置插入數(shù)據(jù)
}

//尾刪
void SeqListPopBack(SeqList* psl)
{
	assert(psl);
	SeqListErase(psl, psl->size-1);//在size-1位置刪除數(shù)據(jù)
}

//頭插
void SeqListPushFront(SeqList* psl, SLDataType x)
{
	assert(psl);
	SeqListCheckCapacity(psl);
	SeqListInsert(psl, 0, x);//在0位置插入數(shù)據(jù)
}

//頭刪
void SeqListPopFront(SeqList* psl)
{
	assert(psl);
	SeqListErase(psl, 0);//在0位置刪除數(shù)據(jù)
}

2.2.11 順序表查找

遍歷一遍，一個個找

int SeqListFind(SeqList* psl, SLDataType x)
{
	assert(psl);

	for (int i = 0; i < psl->size; ++i)
	{
		if (psl->a[i] == x)
		{
			return i;
		}
	}

	return -1;
}

2.2.12 順序表銷毀

最后的最后，一定要養(yǎng)成好習慣，不要忘記銷毀之前申請的空間，防止內(nèi)存泄漏。

//銷毀
void SeqListDestroy(SeqList* psl)
{
	free(psl->a);
	psl->a = NULL;
	psl->capacity = 0;
	psl->size = 0;
}

2.3 數(shù)組相關(guān)面試題

刪除排序數(shù)組中的重復項。26. 刪除有序數(shù)組中的重復項.

原地移除數(shù)組中所有的元素val，要求時間復雜度為O(N)，空間復雜度為O(1)。27. 移除元素.

合并兩個有序數(shù)組。88. 合并兩個有序數(shù)組.

2.4 順序表的問題及思考

問題：

  • 中間/頭部的插入刪除，時間復雜度為O(N)
  • 增容需要申請新空間，拷貝數(shù)據(jù)，釋放舊空間。會有不小的消耗。
  • 增容一般是呈2倍的增長，勢必會有一定的空間浪費。例如當前容量為100，滿了以后增容到200，我們再繼續(xù)插入了5個數(shù)據(jù)，后面沒有數(shù)據(jù)插入了，那么就浪費了95個數(shù)據(jù)空間。

思考：如何解決以上問題呢？下期會給出了鏈表的結(jié)構(gòu)，現(xiàn)在大家可以想想鏈表會如何解決這些問題。

到此這篇關(guān)于C語言數(shù)據(jù)結(jié)構(gòu)深入探索順序表的文章就介紹到這了,更多相關(guān)C語言 順序表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

相關(guān)文章

  • 樹形結(jié)構(gòu)的3中搜索方式示例分享

    樹形結(jié)構(gòu)的3中搜索方式示例分享

    樹的3中常見搜索方式，包括二叉樹方式（每一層只有0和1）、滿m叉樹（每一層都有0 到m - 1）、子集樹，也稱為全排列樹,需要的朋友可以參考下
    2014-02-02
  • Opencv實現(xiàn)輪廓提取功能

    Opencv實現(xiàn)輪廓提取功能

    這篇文章主要為大家詳細介紹了Opencv實現(xiàn)輪廓提取功能，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
    2019-05-05
  • C語言實現(xiàn)自動發(fā)牌程序

    C語言實現(xiàn)自動發(fā)牌程序

    這篇文章主要為大家詳細介紹了C語言實現(xiàn)自動發(fā)牌程序，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
    2020-04-04
  • Qt實現(xiàn)繪制一個簡單多邊形的示例代碼

    Qt實現(xiàn)繪制一個簡單多邊形的示例代碼

    QT提供了圖形繪制接口QPainter，通過該接口可以繪制多種圖形，包括多邊形。本文就來利用它實現(xiàn)繪制一個簡單的多邊形，感興趣的可以嘗試一下
    2022-11-11
  • C++?vector與數(shù)組轉(zhuǎn)換寫入/讀出文件方式

    C++?vector與數(shù)組轉(zhuǎn)換寫入/讀出文件方式

    這篇文章主要介紹了C++?vector與數(shù)組轉(zhuǎn)換寫入/讀出文件方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教
    2022-11-11
  • vs運行時報C4996代碼錯誤的問題解決

    vs運行時報C4996代碼錯誤的問題解決

    C4996錯誤的意思：是VS覺得strcpy這函數(shù)不安全,建議你使更安全的函數(shù),那么如何解決呢,本文主要介紹了vs運行時報C4996代碼錯誤的問題解決,感興趣的可以了解一下
    2024-01-01
  • 基于Matlab實現(xiàn)離散系統(tǒng)分岔圖的繪制

    基于Matlab實現(xiàn)離散系統(tǒng)分岔圖的繪制

    這篇文章主要介紹了如何利用Matlab實現(xiàn)離散分岔圖的繪制，文中的示例代碼講解詳細，對我們學習Matlab有一定的幫助，需要的可以參考一下
    2022-04-04
  • 簡單實現(xiàn)C++復數(shù)計算器

    簡單實現(xiàn)C++復數(shù)計算器

    這篇文章主要為大家詳細介紹了C++簡單實現(xiàn)復數(shù)計算器的的相關(guān)代碼，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
    2016-06-06
  • C語言實現(xiàn)學生宿舍信息管理系統(tǒng)

    C語言實現(xiàn)學生宿舍信息管理系統(tǒng)

    這篇文章主要為大家詳細介紹了C語言實現(xiàn)學生宿舍信息管理系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
    2022-03-03
  • C++ 將數(shù)據(jù)轉(zhuǎn)為字符串的幾種方法

    C++ 將數(shù)據(jù)轉(zhuǎn)為字符串的幾種方法

    這篇文章主要介紹了C++ 將數(shù)據(jù)轉(zhuǎn)為字符串的幾種方法，十分的實用，有需要的小伙伴可以參考下。
    2015-06-06

最新評論