順序表文章目錄

• 定義
• • 特點
  • 缺陷
  • 靜態(tài)順序表
  • 動態(tài)順序表
• 接口實現(xiàn)
• • 順序表初始化
  • 順序表銷毀
  • 順序表增容
  • 頭部的插入刪除
  • • 頭插
    • 頭刪
  • 尾部的插入刪除
  • • 尾插
    • 尾刪
  • 中間的插入刪除
  • • 中間插入
    • 中間刪除
  • 順序表查找
  • 順序表打印

創(chuàng)新互聯(lián)專業(yè)為企業(yè)提供阿榮網(wǎng)站建設(shè)、阿榮做網(wǎng)站、阿榮網(wǎng)站設(shè)計、阿榮網(wǎng)站制作等企業(yè)網(wǎng)站建設(shè)、網(wǎng)頁設(shè)計與制作、阿榮企業(yè)網(wǎng)站模板建站服務(wù)，10多年阿榮做網(wǎng)站經(jīng)驗，不只是建網(wǎng)站，更提供有價值的思路和整體網(wǎng)絡(luò)服務(wù)。定義

順序表是用一段物理地址連續(xù)的存儲單元依次存儲數(shù)據(jù)元素的線性結(jié)構(gòu)，一般情況下采用數(shù)組存儲。在數(shù)組上完成數(shù)據(jù)的增刪查改。
順序表一般可以分為：
1.靜態(tài)順序表：使用定長數(shù)組存儲元素
2.動態(tài)順序表：使用動態(tài)開辟的數(shù)組存儲。

特點

順序表的特點：
①隨機(jī)訪問，即可以在 O(1) 時間內(nèi)找到第 i 個元素。
②存儲密度高，每個節(jié)點只存儲數(shù)據(jù)元素
③拓展容量不方便（即便采用動態(tài)分配的方式實現(xiàn)，拓展長度的時間復(fù)雜度也比較高）
④插入、刪除操作不方便，需要移動大量元素

缺陷

1. 空間不夠，需要擴(kuò)容。擴(kuò)容是有代價的，并且會存在空間浪費。
2. 頭部或者中部的插入刪除，需要挪動數(shù)據(jù)，效率低。
   

靜態(tài)順序表

#define N 7
typedef int SLDataType;
typedef struct SeqList
{SLDataType arr[N];//定長數(shù)組
    size_t size;//有效數(shù)據(jù)的個數(shù)
}SeqList;

動態(tài)順序表

typedef int SLDataType;
typedef struct SeqList
{SLDataType* array;//指向動態(tài)開辟的數(shù)組
	size_t size;	 //有效數(shù)據(jù)個數(shù)	
	size_t capicity;//容量空間的大小
}SeqList;

接口實現(xiàn)

typedef int SLDataType;
// 順序表的動態(tài)存儲
typedef struct SeqList
{SLDataType* array;  // 指向動態(tài)開辟的數(shù)組
  size_t size ;       // 有效數(shù)據(jù)個數(shù)
  size_t capicity ;   // 容量空間的大小
}SeqList;

以下接口都以該類型實現(xiàn)。

順序表初始化

void SeqListInit(SeqList* psl)
{assert(psl);//斷言防止其為空指針
	psl->array=NULL;//講該指針置空
	psl->size = 0;//設(shè)置有效數(shù)據(jù)個數(shù)為0
	psl->capacity = 0;//設(shè)置空間容量為0
}

介紹一下assert這個函數(shù)。

assert的作用就是：求表達(dá)式的值，當(dāng)結(jié)果為假時，打印診斷消息并中止程序。

順序表銷毀

void SeqListDestory(SeqList* psl)
{assert(psl);
	//釋放動態(tài)開辟的空間
	if (psl->array)
	{free(psl->array);
		psl->array = NULL;
		psl->capacity = 0;
		psl->size = 0;
	}
}

順序表增容

想給一個表增容，最先做的就是先檢查順序表內(nèi)元素個數(shù)是否已達(dá)順序表容量上限。
若已達(dá)上限，那么我們就需要先對順序表進(jìn)行擴(kuò)容，然后才能增加數(shù)據(jù)。

void SeqListCheckCapacity(SeqList* psl)
{assert(psl);

	if (psl->size == psl->capacity)
	{int newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
		SeqListDataType* tmp = (SeqListDataType*)realloc(psl->array, newCapacity * sizeof(SeqListDataType));
		if (tmp == NULL)
		{	perror("realloc fail");
			exit(-1);
		}

		psl->array = tmp;
		psl->capacity = newCapacity;
	}
}

頭部的插入刪除

頭插

void SeqListPushFront(SeqList* psl, SeqListDataType x)
{assert(psl);
	SeqListCheckCapacity(psl);
	int end = psl->size - 1;
	while (end >= 0)
	{psl->array[end + 1] = psl->array[end];
		end--;
	}
    //或者用for循環(huán)
    //	for (int i = psl->size - 1; i >= 0; i--)  
    //順序表中[0,size-1]的元素依次向后挪動一位
	//{//	psl->array[i + 1] = psl->array[i];
	//}
	psl->array[0] = x;
	psl->size++;
}

void SeqListPushFront(SeqList* psl, SeqListDataType x)
{SeqListInsert(psl, 0, x);
}

頭刪

void SeqListPopFront(SeqList* psl)
{assert(psl);  //斷言
    assert(psl->size>0);//防止數(shù)據(jù)為0時還刪數(shù)據(jù)
	assert(psl->size >0);  //順序表不能為空
	int begin = 1;
    while(beginsize)
    {psl->array[begin-1]=psl->array[begin];
        begin++;
    }
//	int i = 0;
//	for (i = 1; i< psl->size; i++)  //順序表中[1,size-1]的元素依次向前挪動一位
//	{//		psl->array[i - 1] = psl->array[i];
//	}
	psl->size--;  //有效數(shù)據(jù)個數(shù)-1
}

void SeqListPopFront(SeqList* psl)
{SeqListErase(psl, 0);
}

尾部的插入刪除

尾插

void SeqListPushBack(SeqList* psl, SeqListDataType x)
{assert(psl);
	SLCheckCapacity(psl);
	psl->array[psl->size] = x;
	psl->size++;
}

void SeqListPushBack(SeqList*psl,SeqListDataType X)
{SLInsert(psl, ps->size, x);
}

尾刪

void SeqListPopBack(SeqList* psl)
{assert(ps);
	assert(ps->size >0);
	psl->array[ps->size - 1] = 0;
	psl->size--;
}

void SeqListPopBack(SeqList*psl)
{SeqListErase(psl, psl->size-1);
}

中間的插入刪除

中間插入

void SeqListInsert(SeqList* psl, int pos, SeqListDataType x)
{assert(psl);
	assert(pos >= 0);
	assert(pos<= psl ->size);

	SeqListCheckCapacity(psl);
	int end = psl->size - 1;
	while (end >= pos)
	{psl->array[end + 1] = psl->array[end];
		end--;
	}

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

中間刪除

void SeqListErase(SeqList* psl, int pos)
{ss
	assert(psl);
	assert(pos >= 0);
	assert(pos< psl->size);
	int begin = pos + 1;
	while (begin< psl->size)
	{psl->array[begin - 1] = psl->array[begin];
		begin++;
	}
	psl->size--;
}

順序表查找

int SeqListFind(SeqList* psl, SeqListDataType x, int begin)
{assert(psl);
	for (int i = begin; i< psl->size; i++)
	{if (ps->array[i] == x)
		{	return i;
		}
	}
	return -1;
}

順序表打印

void SeqListPrint(SeqList* psl)
{assert(psl);
	if (psl->size == 0)
	{printf("空表");
		return;
	}
	for (int i = 0; i< psl->size; i++)
	{printf("%d ", psl->array[i]);
	}
	printf("\n");
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

當(dāng)前文章：【數(shù)據(jù)結(jié)構(gòu)】順序表—純C實現(xiàn)順序表-創(chuàng)新互聯(lián)
網(wǎng)站鏈接：http://jinyejixie.com/article38/dedosp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供做網(wǎng)站、面包屑導(dǎo)航、網(wǎng)站設(shè)計公司、靜態(tài)網(wǎng)站、企業(yè)網(wǎng)站制作、定制開發(fā)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)