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

c語(yǔ)言數(shù)據(jù)結(jié)構(gòu)與算法之順序表的定義實(shí)現(xiàn)詳解

 更新時(shí)間:2023年08月08日 09:15:38   作者:程序喵正在路上  
這篇文章主要介紹了c語(yǔ)言數(shù)據(jù)結(jié)構(gòu)與算法之順序表的定義實(shí)現(xiàn)詳解,用順序存儲(chǔ)的方式實(shí)現(xiàn)線性表順序存儲(chǔ),把邏輯上相鄰的元素存儲(chǔ)在物理位置上也相鄰的存儲(chǔ)單元中,元素之間的關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來(lái)體現(xiàn),需要的朋友可以參考下

順序表的定義

順序表 —— 用順序存儲(chǔ)的方式實(shí)現(xiàn)線性表順序存儲(chǔ)。

把邏輯上相鄰的元素存儲(chǔ)在物理位置上也相鄰的存儲(chǔ)單元中,元素之間的關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來(lái)體現(xiàn)

線性表是具有相同數(shù)據(jù)類(lèi)型的 n (n≥0) 個(gè)數(shù)據(jù)元素的有限序列,數(shù)據(jù)類(lèi)型相同說(shuō)明每個(gè)數(shù)據(jù)元素所占的空間是一樣大的

我們假設(shè)線性表第一個(gè)元素的存放位置(即首地址)是 LOC(L) ,LOClocation 的縮寫(xiě)

那么第二個(gè)元素的存放位置就是 LOC(L)+數(shù)據(jù)元素的大小

第三個(gè)元素的存放位置就是 LOC(L)+2*數(shù)據(jù)元素的大小,依此類(lèi)推…

那么,我們又怎么知道所存放的數(shù)據(jù)元素的大小呢?

學(xué)過(guò) C語(yǔ)言 的小伙伴肯定知道,C語(yǔ)言 中有一個(gè)函數(shù) sizeof() 可以幫上我們的忙,我們用 sizeof(ElemType) 這樣調(diào)用的方式就能得到對(duì)應(yīng)數(shù)據(jù)元素的大小,其中的 ElemType 就是你的順序表中存放的數(shù)據(jù)元素類(lèi)型,比如 sizeof(int) = 4B ,一個(gè)整型一般是 4 個(gè)字節(jié);此外,我們還可以傳自己定義的類(lèi)型進(jìn)去,比如,我們定義一個(gè) Customer 類(lèi)型

typedef struct {
	int num;	//號(hào)數(shù)
	int people; //人數(shù)
} Customer;

相應(yīng)地,我們使用 sizeof(Customer) 就可以得到這個(gè)數(shù)據(jù)類(lèi)型的大小為 8B

順序表的實(shí)現(xiàn) —— 靜態(tài)分配

#define MaxSize 10				//定義最大長(zhǎng)度
typedef struct {
	ElemType data[MaxSize];		//用靜態(tài)的 “數(shù)組” 存放數(shù)據(jù)元素
	int length;					//順序表的當(dāng)前長(zhǎng)度
} SqList;						//順序表的類(lèi)型定義(靜態(tài)分配方式)

ElemType data[MaxSize]; 會(huì)給各個(gè)數(shù)據(jù)元素分配連續(xù)的存儲(chǔ)空間,大小為 MaxSize*sizeof(ElemType)

Sq:sequence —— 順序,序列

#include <stdio.h>
#define MaxSize 10				//定義最大長(zhǎng)度
typedef int ElemType;
typedef struct {
	ElemType data[MaxSize];		//用靜態(tài)的 “數(shù)組” 存放數(shù)據(jù)元素
	int length;					//順序表的當(dāng)前長(zhǎng)度
} SqList;						//順序表的類(lèi)型定義
//基礎(chǔ)操作 —— 初始化一個(gè)順序表
void InitList(SqList &L) {
	for(int i = 0; i < MaxSize; i++) {
		L.data[i] = 0;		//將所有數(shù)據(jù)元素設(shè)置為默認(rèn)初始值
	}
	L.length = 0;
}
//主函數(shù)
int main() {
	SqList L;		//聲明一個(gè)順序表
	InitList(L);	//初始化順序表
	//其他操作
	return 0;
}

如果在初始化順序表中不給 data 數(shù)組賦值為 0,會(huì)怎么樣呢?

#include <stdio.h>
#define MaxSize 10				//定義最大長(zhǎng)度
typedef int ElemType;
typedef struct {
	ElemType data[MaxSize];		//用靜態(tài)的 “數(shù)組” 存放數(shù)據(jù)元素
	int length;					//順序表的當(dāng)前長(zhǎng)度
} SqList;						//順序表的類(lèi)型定義
//基礎(chǔ)操作 —— 初始化一個(gè)順序表
void InitList(SqList &L) {
	L.length = 0;
}
//主函數(shù)
int main() {
	SqList L;		//聲明一個(gè)順序表
	InitList(L);	//初始化順序表
	//嘗試“違規(guī)”打印整個(gè)數(shù)組
	for(int i = 0; i < MaxSize; i++) {
		printf("data[%d]=%d\n", i, L.data[i]);
	}
	return 0;
}

運(yùn)行這段代碼,你會(huì)看到很奇怪的數(shù)據(jù),或許和我的運(yùn)行結(jié)果不太一樣,這是正常的

在這里插入圖片描述

為什么會(huì)顯示這些奇怪的數(shù)據(jù)呢?

其實(shí)啊,程序在給我們這個(gè)數(shù)組分配內(nèi)存的時(shí)候,我們并不知道這塊內(nèi)存里面之前存儲(chǔ)過(guò)什么,如果我們不設(shè)置數(shù)據(jù)元素的默認(rèn)值,就會(huì)出現(xiàn)這樣的結(jié)果

其實(shí),我們這樣訪問(wèn)也是違規(guī)的,因?yàn)槌跏蓟樞虮淼臅r(shí)候 length 是為 0 的,我們要遍歷的條件應(yīng)該是 i < L.length; 才對(duì),所以數(shù)據(jù)元素的初始化是可以省略的,不過(guò) length 的初始化這一步驟就不能省略了

如果我們定義的 “數(shù)組” 存滿了,怎么辦呢?

建議直接放棄治療,順序表的表長(zhǎng)剛開(kāi)始確定后就無(wú)法更改了,因?yàn)槲覀兪庆o態(tài)分配空間

有小伙伴就說(shuō),那我一開(kāi)始就聲明一個(gè)很長(zhǎng)的順序表不就行了,但這樣的后果是會(huì)浪費(fèi)我們的內(nèi)存空間,從這里我們就可以看出來(lái)靜態(tài)分配的局限性了

順序表的實(shí)現(xiàn) —— 動(dòng)態(tài)分配

#define InitSize 10			//順序表的初始長(zhǎng)度
typedef struct {
	ElemType *data;			//指示動(dòng)態(tài)分配數(shù)組的指針
	int MaxSize;			//順序表的最大容量
	int length;				//順序表的當(dāng)前長(zhǎng)度
} SqList;					//順序表的類(lèi)型定義

C語(yǔ)言 中提供了 mallocfree 這兩個(gè)函數(shù)來(lái)讓我們動(dòng)態(tài)申請(qǐng)和釋放內(nèi)存空間

malloc 會(huì)申請(qǐng)一整片連續(xù)的存儲(chǔ)空間,然后返回一個(gè)指向這一片存儲(chǔ)空間開(kāi)始地址的指針,同時(shí)需要我們強(qiáng)制轉(zhuǎn)型為定義的數(shù)據(jù)元素類(lèi)型指針

malloc 函數(shù)的參數(shù),指明了要分配多大的連續(xù)內(nèi)存空間

L.data = (ElemType *) malloc(sizeof(ElemType) * InitSize);

如果你學(xué)習(xí)過(guò) C++,那你也可以使用 newdelete 這兩個(gè)函數(shù)來(lái)實(shí)現(xiàn)同樣的功能

#include <stdio.h>
#include <stdlib.h>				//使用 malloc 和 free 函數(shù)所需的頭文件
#define InitSize 10				//默認(rèn)最大長(zhǎng)度
typedef int ElemType;			//方便我們改變類(lèi)型
typedef struct {
	ElemType *data;				//指示動(dòng)態(tài)分配數(shù)組的指針
	int MaxSize;				//順序表的最大容量
	int length;					//順序表的當(dāng)前長(zhǎng)度
} SqList;						//順序表的類(lèi)型定義
//初始化順序表
void InitList(SqList &L);
//增加動(dòng)態(tài)數(shù)組的長(zhǎng)度
void IncreaseSize(SqList &L, int len);
//主函數(shù)
int main() {
	SqList L;			//聲明一個(gè)順序表
	InitList(L);		//初始化順序表
	IncreaseSize(L, 5);
	return 0;
}
//初始化順序表
void InitList(SqList &L) {
	//用 malloc 函數(shù)申請(qǐng)一片連續(xù)的存儲(chǔ)空間
	L.data = (ElemType *)malloc(sizeof(ElemType)* InitSize);
	L.length = 0;
	L.MaxSize = InitSize;
}
//增加動(dòng)態(tài)數(shù)組的長(zhǎng)度
void IncreaseSize(SqList &L, int len) {
	ElemType *p = L.data;				//將L數(shù)據(jù)存儲(chǔ)起來(lái)
	L.data = (ElemType *)malloc(sizeof(ElemType)* (L.MaxSize + len));
	for (int i = 0; i < L.length; i++) {
		L.data[i] = p[i];				//將數(shù)據(jù)復(fù)制到新區(qū)域
	}
	L.MaxSize = L.MaxSize + len;		//順序表最大長(zhǎng)度增加 len
	free(p);							//釋放臨時(shí)的內(nèi)存空間
}

注意:realloc 函數(shù)也可以實(shí)現(xiàn),但建議初學(xué)者使用 mallocfree 更能理解背后的過(guò)程

順序表的特點(diǎn):

  • 隨機(jī)訪問(wèn),既可以在 O(1) 時(shí)間內(nèi)找到第 i 個(gè)元素,代碼實(shí)現(xiàn)為 data[i - 1]
  • 存儲(chǔ)密度高,每個(gè)節(jié)點(diǎn)只存儲(chǔ)數(shù)據(jù)元素
  • 拓展容量不方便,即便采用動(dòng)態(tài)分配的方式實(shí)現(xiàn),拓展長(zhǎng)度的時(shí)間復(fù)雜度也比較高
  • 插入、刪除操作不方便,需要移動(dòng)大量元素

到此這篇關(guān)于c語(yǔ)言數(shù)據(jù)結(jié)構(gòu)與算法之順序表的定義實(shí)現(xiàn)詳解的文章就介紹到這了,更多相關(guān)c語(yǔ)言順序表的定義內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • QT中幾種常用的排序函數(shù)用法總結(jié)

    QT中幾種常用的排序函數(shù)用法總結(jié)

    Qt是目前最先進(jìn)、最完整的跨平臺(tái)C++開(kāi)發(fā)工具,下面這篇文章主要給大家介紹了關(guān)于QT中幾種常用的排序函數(shù)用法的相關(guān)資料,文中通過(guò)代碼介紹的非常詳細(xì),需要的朋友可以參考下
    2024-01-01
  • C語(yǔ)言項(xiàng)目小學(xué)生數(shù)學(xué)考試系統(tǒng)參考

    C語(yǔ)言項(xiàng)目小學(xué)生數(shù)學(xué)考試系統(tǒng)參考

    今天小編就為大家分享一篇關(guān)于C語(yǔ)言項(xiàng)目小學(xué)生數(shù)學(xué)考試系統(tǒng)參考,小編覺(jué)得內(nèi)容挺不錯(cuò)的,現(xiàn)在分享給大家,具有很好的參考價(jià)值,需要的朋友一起跟隨小編來(lái)看看吧
    2019-02-02
  • C語(yǔ)言實(shí)現(xiàn)求最大公約數(shù)的三種方法

    C語(yǔ)言實(shí)現(xiàn)求最大公約數(shù)的三種方法

    最大公因數(shù),也稱最大公約數(shù)、最大公因子,指兩個(gè)或多個(gè)整數(shù)共有約數(shù)中最大的一個(gè)。本文將為大家介紹三種方法來(lái)實(shí)現(xiàn)求解兩個(gè)正整數(shù)的最大公約數(shù),需要的可以參考一下
    2021-12-12
  • Qt自定義控件實(shí)現(xiàn)線條型加載條

    Qt自定義控件實(shí)現(xiàn)線條型加載條

    這篇文章主要為大家詳細(xì)介紹了Qt自定義控件實(shí)現(xiàn)線條型加載條,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2019-12-12
  • VSCode遠(yuǎn)程開(kāi)發(fā)調(diào)試服務(wù)器c/c++代碼

    VSCode遠(yuǎn)程開(kāi)發(fā)調(diào)試服務(wù)器c/c++代碼

    語(yǔ)音相關(guān)的好多項(xiàng)目要在linux上跑,但代碼開(kāi)發(fā)大多是在PC機(jī)上,本篇簡(jiǎn)單介紹一下怎么在個(gè)人電腦上用VSCode遠(yuǎn)程開(kāi)發(fā)調(diào)試服務(wù)器上的c/c++代碼。感興趣的朋友跟隨小編一起看看吧
    2020-04-04
  • C語(yǔ)言深入講解函數(shù)參數(shù)的使用

    C語(yǔ)言深入講解函數(shù)參數(shù)的使用

    函數(shù)的參數(shù)分為形參和實(shí)參兩種。形參出現(xiàn)在函數(shù)定義中,在整個(gè)函數(shù)體內(nèi)都可以使用,離開(kāi)該函數(shù)則不能使用。實(shí)參出現(xiàn)在主調(diào)函數(shù)中,進(jìn)入被調(diào)函數(shù)后,實(shí)參變量也不能使用
    2022-04-04
  • C語(yǔ)言函數(shù)指針詳解

    C語(yǔ)言函數(shù)指針詳解

    本文主要介紹 C語(yǔ)言函數(shù)指針的知識(shí),這里整理了詳細(xì)的資料及示例代碼以便大家學(xué)習(xí)參考,有需要學(xué)習(xí)此部分知識(shí)的朋友可以參考下
    2021-09-09
  • C++中為何推薦要把基類(lèi)析構(gòu)函數(shù)設(shè)置成虛函數(shù)

    C++中為何推薦要把基類(lèi)析構(gòu)函數(shù)設(shè)置成虛函數(shù)

    這篇文章主要介紹了C++中為何推薦要把基類(lèi)析構(gòu)函數(shù)設(shè)置成虛函數(shù)問(wèn)題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2022-12-12
  • C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)順序表的進(jìn)階講解

    C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)順序表的進(jìn)階講解

    程序中經(jīng)常需要將一組數(shù)據(jù)元素作為整體管理和使用,需要?jiǎng)?chuàng)建這種元素組,用變量記錄它們,傳進(jìn)傳出函數(shù)等。一組數(shù)據(jù)中包含的元素個(gè)數(shù)可能發(fā)生變化,順序表則是將元素順序地存放在一塊連續(xù)的存儲(chǔ)區(qū)里,元素間的順序關(guān)系由它們的存儲(chǔ)順序自然表示
    2022-04-04
  • 使用C語(yǔ)言實(shí)現(xiàn)掃雷游戲

    使用C語(yǔ)言實(shí)現(xiàn)掃雷游戲

    這篇文章主要為大家詳細(xì)介紹了使用C語(yǔ)言實(shí)現(xiàn)掃雷游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2022-08-08

最新評(píng)論