成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

數(shù)據(jù)結(jié)構(gòu) | 數(shù)組模擬實現(xiàn)順序表

OldPanda / 2418人閱讀

摘要:常見的線性表順序表鏈表棧隊列字符串順序表順序表是用一段物理地址連續(xù)的存儲單元依次存儲數(shù)據(jù)元素的線性結(jié)構(gòu),一般情況下采用數(shù)組存儲。

代碼已經(jīng)放在Gitee上,需要可以小伙伴可以去看看

用C語言數(shù)組模擬實現(xiàn)順序表

Gitee

線性表和順序表

線性表

線性表(linear list)是n個具有相同特性的數(shù)據(jù)元素的有限序列,這是我們廣泛使用的數(shù)據(jù)結(jié)構(gòu)。

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

常見的線性表:順序表、鏈表、棧、隊列、字符串…

順序表

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

一般可以分為:

  1. 靜態(tài)順序表:使用定長數(shù)組來存儲元素
  2. 動態(tài)順序表:使用動態(tài)開辟的數(shù)組來儲存元素

靜態(tài)順序表

//定義靜態(tài)數(shù)組的大小,方便后續(xù)修改#define MAX_SIZE 50//重命名數(shù)組的數(shù)據(jù)類型,方便后續(xù)修改typedef int SLDataType;//定義結(jié)構(gòu)體//成員變量為數(shù)組和記錄當前數(shù)據(jù)個數(shù)的變量//重命名結(jié)構(gòu)體數(shù)據(jù)類型,方便書寫typedef struct SeqList {	SLDataType arr[MAX_SIZE];	int size;}SL;//-----------------------------------------------------------------------------//以下是一些常見的接口的聲明//順序表初始化//利用結(jié)構(gòu)體類型創(chuàng)建一個靜態(tài)順序表變量后,可以對其進行初始化void SLInit(SL* psl);//打印順序表//把順序表的值按照先后順序打印出來void SLPrint(SL* psl);//檢查順序表是否已滿//每次進行加入數(shù)據(jù)的操作的時候需要先檢查是否已經(jīng)滿了,如果滿了就不能夠插入了void SLCheck(SL* psl);//順序表的尾插//在順序表的尾部在插入一個元素//由于是數(shù)組加入數(shù)據(jù)很方便,直接使用數(shù)組下標就可以訪問到void SLPushBack(SL* psl, SLDataType data);//順序表的尾刪//刪除順序表尾部的數(shù)據(jù)void  SLPopBack(SL* psl);//順序表的頭插//在順序表的開頭加入一個數(shù)據(jù)void SLPushFront(SL* psl, SLDataType data);//順序表的頭刪//把順序表第一位數(shù)據(jù)刪除void SLPopFront(SL* psl);//順序表查找某個數(shù)據(jù)//查找順序表中是否存在某個數(shù)據(jù),如果有就返回對應的下標//如果找不到就返回-1int SLFind(SL* psl, SLDataType x);//順序表在pos位置插入x//在指定下標位置插入數(shù)據(jù)x,原來x位置的數(shù)據(jù)以及后面的數(shù)據(jù)往后移動void SLInsert(SL* psl, size_t pos, SLDataType x);//順序表刪除在pos位置的數(shù)據(jù)void SLErase(SL* psl, size_t pos);//順序表某一位置數(shù)據(jù)的修改void SLModify(SL* psl, size_t pos, SLDataType x);

以下是這些接口的具體實現(xiàn)

//順序表初始化void SLInit(SL* psl) {	psl->arr[0] = 0;//此處只能初始化一個元素	psl->size = 0;}//打印順序表void SLPrint(SL* psl) {	int i = 0;	if (psl->size) {		for (i = 0; i < psl->size; i++) {			//輸出格式,記得根據(jù)SLDataTyped的類型來修改			printf("%d ", psl->arr[i]);		}		printf("/n");	}	else {		printf("Null/n");	}}/*//檢查順序表是否已滿void SLCheck(SL* psl) {	if (psl->size == MAX_SIZE) {		printf("順序表已滿,無法進行后續(xù)操作");	}}*///順序表的尾插void SLPushBack(SL* psl, SLDataType data) {	//插入數(shù)據(jù)要先檢查空間是否已滿	//實現(xiàn)方法一不夠好	/*	if (psl->size == MAX_SIZE) {		printf("空間已滿/n");		return;	}	else {		psl->arr[psl->size] = data;		psl->size++;	}*/	//實現(xiàn)方法二,簡單明了	assert(psl->size != MAX_SIZE);	psl->arr[psl->size] = data;	psl->size++;}//順序表的尾刪void  SLPopBack(SL* psl) {	//判斷是否還有元素可以刪除	assert(psl->size);	psl->size--;}//順序表的頭插void SLPushFront(SL* psl, SLDataType data) {	assert(psl->size != MAX_SIZE);	//src用來后移數(shù)據(jù)	int src = psl->size;	while (src >= 1) {		psl->arr[src] = psl->arr[src - 1];		src--;	}	psl->arr[src] = data;	psl->size++;}//順序表的頭刪void SLPopFront(SL* psl) {	//判斷是否還有數(shù)據(jù)可以刪除	assert(psl->size);	int src = 0;	while (src < psl->size - 1) {		psl->arr[src] = psl->arr[src + 1];		src++;	}	psl->size--;}//順序表查找某個數(shù)據(jù)int SLFind(SL* psl, SLDataType x) {	int i = 0;	for (i = 0; i < psl->size; i++) {				if (psl->arr[i] == x) {			//找到了就返回該數(shù)據(jù)在順序表中的位置			return  i;		}	}	//找不到就返回-1	return -1;}//順序表在pos位置插入xvoid SLInsert(SL* psl, size_t pos, SLDataType x) {	assert(psl->size < MAX_SIZE);	assert(pos >= 0 && pos <= psl->size);//pos=0或者pos=size的時候,相當于頭插,尾插	int end = psl->size;	while (end > pos) {		psl->arr[end] = psl->arr[end - 1];		end--;	}	psl->arr[pos] = x;	psl->size++;}//順序表刪除在pos位置的數(shù)據(jù)void SLErase(SL* psl, size_t pos) {	assert(psl->size);	assert(pos >= 0 && pos < psl->size);	int start = pos + 1;	while (start < psl->size) {		psl->arr[start - 1] = psl->arr[start];		start++;	}	psl->size--;}//順序表某一位置數(shù)據(jù)的修改void SLModify(SL* psl, size_t pos, SLDataType x) {	assert(psl->size);	assert(pos >= 0 && pos < psl->size);	psl->arr[pos] = x;}

上面代碼的測試,我放在了Gitee上,需要的小伙伴可以參考一下

動態(tài)順序表

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

//重命名SL的數(shù)據(jù)類型,方便后續(xù)修改typedef int SLDataType;//定義結(jié)構(gòu)體//成員變量為指向動態(tài)順序表的指針,數(shù)據(jù)的個數(shù),順序表的容量//capacity用來管理數(shù)組的總大小,如果size與capacity相等了,就表示數(shù)組已經(jīng)滿了需要擴容//重定義結(jié)構(gòu)體類型名稱,方便操作typedef struct SeqList {	SLDataType* p;	int size;	int capacity;}SL;//----------------------------------------------------------------------//一下是一些常用的接口,與靜態(tài)順序表差不多//SL初始化void SLInit(SL* ps);//SL空間檢查//如若size與capacity相等表示數(shù)組已經(jīng)滿了,需要擴容void SLCheckCapacity(SL* ps);//SL打印void SLPrint(SL* ps);//SL銷毀//因為數(shù)組是動態(tài)開辟的,所以在最后不使用的數(shù)組的時候要釋放空間void SLDestory(SL* ps);//SL尾插void SLPushBack(SL* ps,SLDataType x);//SL尾刪void SLPopBack(SL* ps);//SL頭插void SLPushFront(SL* ps, SLDataType x);//SL頭刪void SLPopFront(SL* ps);//SL查找某個數(shù)據(jù)//如果能找到,返回該數(shù)據(jù)在順序表中下標int SLFind(SL* ps, SLDataType x);//SL在pos位置插入xvoid SLInsert(SL* ps, size_t pos, SLDataType x);//SL刪除pos位置的值void SLErase(SL* ps, size_t pos);//SL修改某一位置的數(shù)據(jù)void SLModity(SL* ps, size_t pos, SLDataType x);

以下是具體的實現(xiàn)

//動態(tài)順序表的實現(xiàn)#include"DynamicSeqList.h"//SL初始化void SLInit(SL* ps) {	ps->p = NULL;	ps->capacity = 0;	ps->size = 0;}//SL空間檢查void SLCheckCapacity(SL* ps) {	if (ps->size == ps->capacity) {		ps->capacity = (ps->capacity == 0) ? 5 : 2 * ps->capacity;		SLDataType* tmp = (SLDataType*)realloc(ps->p, (ps->capacity) * sizeof(SLDataType));		if (tmp == NULL) {			printf("realloc fail/n");			exit(-1);		}		ps->p = tmp;	}}//SL打印void SLPrint(SL* ps) {	if (ps->size == 0) {		printf("順序表為空/n");	}	else {		int i = 0;		for (i = 0; i < ps->size; i++) {			//打印格式記得根據(jù)SLDataType的類型來修改			printf("%d ", ps->p[i]);		}		printf("/n");	}}//SL銷毀//這里并沒有完全銷毀結(jié)構(gòu)體s,只是把成員變量都賦值為0void SLDestory(SL* ps) {	free(ps->p);	ps->p = NULL;	ps->size = ps->capacity = 0;}//SL尾插void SLPushBack(SL* ps, SLDataType x) {	SLCheckCapacity(ps);	ps->p[ps->size] = x;	ps->size++;}//SL尾刪void SLPopBack(SL* ps) {	//刪除數(shù)據(jù)需要判斷一下順序表是否為空	assert(ps->size > 0);	ps->size--;}//SL頭插void SLPushFront(SL* ps, SLDataType x) {	SLCheckCapacity(ps);	int end = ps->size;	while (end > 0) {		ps->p[end] = ps->p[end - 1];		end--;	}	ps->p[end] = x;	ps->size++;}//SL頭刪void SLPopFront(SL* ps) {	//刪除數(shù)據(jù)需要判斷一下順序表是否為空	assert(ps->size > 0);	int start = 0;	while (start < ps->size - 1) {		ps->p[start] = ps->p[start + 1];		start++;	}	ps->size--;}//SL查找某個數(shù)據(jù)int  SLFind(SL* ps, SLDataType x) {	//需要判斷順序表是否為空,可以用assert,也可以用if判斷	assert(ps->size);	int i = 0;	for (i = 0; i < ps->size; i++) {		if (x == ps->p[i]) {			return i;		}	}	return -1;}//SL在pos位置插入x//當pos為0或者pos為size時,相當于頭插、尾插void SLInsert(SL* ps, size_t pos, SLDataType x) {	SLCheckCapacity(ps);	assert(pos >= 0 && pos <= ps->size);	int end = ps->size;	while (end > pos) {		ps->p[end] = ps->p[end - 1];		end--;	}	ps->p[end] = x;	ps->size++;}//SL刪除pos位置的值void SLErase(SL* ps, size_t pos) {	//判斷要刪除的位置是否在size之內(nèi)	assert(pos >= 0 && pos < ps->size);	int start = pos + 1;	while (start < ps->size) {		ps->p[start - 1] = ps->p[start];		start++;	}	ps->size--;}//SL修改某一位置的數(shù)據(jù)void SLModity(SL* ps, size_t pos, SLDataType x) {	//判斷要修改的位置是否在size之內(nèi)	assert(pos >= 0 && pos < ps->size);	ps->p[pos] = x;}

同樣的,我自己寫的一些小測試也在Gitee上,需要的小伙伴可以去看看

文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址:http://systransis.cn/yun/123957.html

相關(guān)文章

  • PHP面試之四:邏輯與算法

    摘要:數(shù)據(jù)結(jié)構(gòu)常見數(shù)據(jù)結(jié)構(gòu)數(shù)組是最簡單而且應用最廣泛的數(shù)據(jù)結(jié)構(gòu)特征使用連續(xù)內(nèi)存空間來存儲存放相同類型或著衍生類型的元素數(shù)組比較特別,可以存放八種數(shù)據(jù)類型通過下標來訪問集合特征保存不重復的元素字典特征就是關(guān)聯(lián)數(shù)組,以形式存儲棧,與隊列相似特征存儲數(shù) 數(shù)據(jù)結(jié)構(gòu) 常見數(shù)據(jù)結(jié)構(gòu) Array 數(shù)組是 最簡單 而且 應用最廣泛 的數(shù)據(jù)結(jié)構(gòu) 特征: 1、使用連續(xù)內(nèi)存空間來存儲 2、存放相同類型或著衍生類型...

    smartlion 評論0 收藏0
  • 重新詳盡的理解HasMap

    摘要:根據(jù)的重新計算值。如果這兩個的通過比較返回,新添加的將覆蓋集合中原有的,但不會覆蓋。如果這兩個的通過比較返回,新添加的將與集合中原有形成鏈,而且新添加的位于鏈的頭部具體說明繼續(xù)看方法的說明。 關(guān)于hashCode hashCode的存在主要是用于查找的快捷性,如Hashtable,HashMap等,hashCode是用來在散列存儲結(jié)構(gòu)中確定對象的存儲地址的. 1.hashcode是用來...

    maxmin 評論0 收藏0
  • 計算機二級考試-數(shù)據(jù)結(jié)構(gòu)-模擬試題

    摘要:數(shù)據(jù)結(jié)構(gòu)試題前言這里是數(shù)據(jù)結(jié)構(gòu)系列文章,主要介紹計算機二級考試中的涉及到數(shù)據(jù)結(jié)構(gòu)的知識點數(shù)據(jù)結(jié)構(gòu)在計算機科學中處處都有存在,例如編譯系統(tǒng)要使用棧散列表語法樹等操作系統(tǒng)要使用隊列存儲管理表目錄樹等等。 數(shù)據(jù)結(jié)構(gòu) 試題前言這里是 數(shù)據(jù)結(jié)構(gòu) 系列文章,主要介紹計算機二級考試中的涉及到數(shù)據(jù)結(jié)構(gòu)的知識點 /數(shù)據(jù)結(jié)構(gòu)在計算...

    不知名網(wǎng)友 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<