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

C語言實現(xiàn)順序表的基本操作的示例詳解

 更新時間：2022年11月03日 08:34:08   作者：蝸牛牛啊  
順序表是用一段物理地址連續(xù)的存儲單元依次存儲數(shù)據(jù)元素的線性結(jié)構(gòu)，一般情況下采用數(shù)組存儲。本文將通過示例為大家講解一下順序表的基本操作，需要的可以參考一下

一、認識順序表

1.線性表

線性表是n個具有相同特性的數(shù)據(jù)元素的有限序列，線性表是一種在實際中廣泛使用的數(shù)據(jù)結(jié)構(gòu)，常見的線性表有順序表、鏈表、棧、隊列、字符串……線性表在邏輯上是線性結(jié)構(gòu)，也就是說是一條連續(xù)的直線。但是在物理結(jié)構(gòu)上并不一定是連續(xù)的，線性表在物理上存儲時，通常以數(shù)組和鏈式結(jié)構(gòu)的形式來存儲。

2.順序表的概念及結(jié)構(gòu)

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

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

#define MAX 10
typedef int SLDataType;//當存儲數(shù)據(jù)類型改變時，方便修改
typedef struct SeqList
{
    SLDataType arr[MAX];//用來存儲數(shù)據(jù)
    int size;//用來記錄數(shù)組中存儲有效數(shù)據(jù)元素的個數(shù)
}SL;

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

//動態(tài)順序表
typedef int SLDataType;//當存儲數(shù)據(jù)類型改變時，方便修改
typedef struct SeqList
{
    SLDataType* arr;//指向動態(tài)開辟的數(shù)組
    int size;//用來記錄數(shù)組中存儲有效數(shù)據(jù)元素的個數(shù)
    int capacity;//用來記錄容量大小
}SL;

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

二、順序表的基本操作（接口實現(xiàn)）

1.初始化順序表

void SLInit(SL* ps)
{
    assert(ps);
    ps->arr = NULL;
    ps->size = ps->capacity = 0;
}

初始化時設(shè)置其有效數(shù)據(jù)個數(shù)和容量都為0，指針指向NULL。

2.打印順序表

void SLPrint(SL* ps)
{
    int i = 0;
    for (i = 0; i < ps->size; i++)
    {
        printf("%d ", ps->arr[i]);
    }
    printf("\n");
}

3.尾插

void SLPushBack(SL* ps, SLDataType x)
{
    assert(ps);
    if (ps->size == ps->capacity)
    {
        int NewCapacity =ps->capacity == 0 ? 4 : 2 * ps->capacity;//判斷剛開始是否有空間
        SLDataType* tmp = (SLDataType*)realloc(ps->arr,sizeof(SLDataType) * NewCapacity);
        if (tmp == NULL)
        {
            perror("realloc");
            exit(-1);
        }
        ps->arr = tmp;
        ps->capacity = NewCapacity;
    }
    ps->arr[ps->size] = x;
    ps->size++;
}

尾插就是在尾部插入數(shù)據(jù)，因為剛開始的時候沒有給數(shù)組分配空間，所以要考慮當沒有空間時要去申請空間，realloc函數(shù)是擴容函數(shù)，在指針為空的情況下作用和malloc相同，int NewCapacity =ps->capacity == 0 ? 4 : 2 * ps->capacity判斷當前容量大小并確定要開辟的空間大小。

SLDataType* tmp = (SLDataType*)realloc(ps->arr,sizeof(SLDataType) * NewCapacity)，用來在堆內(nèi)存中開辟空間，realloc之后注意將其強制轉(zhuǎn)化成SLDataType*類型。當成功開辟空間之后賦給ps->arr，同時注意將NewCapacity賦給ps->capacity。

4.尾刪

void SLPopBack(SL* ps)
{
    assert(ps);
    //暴力的檢查
    assert(ps->size > 0);//判斷ps->size是否大于0，當?shù)扔?時再刪的話ps->size就會變?yōu)?1，越界
    //溫柔的檢查
    //if (ps->size == 0)
    //{
    //    return;
    //}
    ps->size--;
}

當ps->size等于0時直接返回，如果不返回，造成ps->size為負數(shù)，造成數(shù)組越界，當我們再次插入數(shù)據(jù)的時候可能會出現(xiàn)報錯，同時當越界時可能不會報錯，但是可能會在free時候報錯。所以要用assert(ps->size > 0)檢查ps->size大小，等于0時直接退出，并提示。

擴展：free時候報錯可能的錯誤原因有兩種，一是free時候指針不正確，可能是野指針，同時釋放的時候必須從起始位置釋放。二是越界時候free會報錯。當越界讀數(shù)組的時候基本不會被檢查出來報錯，但是改變它的值的時候就可能會報錯，是一種抽查行為，是在運行時檢查。

5.擴容

void SLCheckCapacity(SL* ps)
{
    assert(ps);
    //檢查是否需要擴容
    if (ps->size == ps->capacity)
    {
        int NewCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
        SLDataType* tmp = (SLDataType*)realloc(ps->arr, sizeof(SLDataType) * NewCapacity);
        if (tmp == NULL)
        {
            perror("realloc");
            exit(-1);
        }
        ps->capacity = NewCapacity;
        ps->arr = tmp;
    }
}

擴容函數(shù)，用于檢查數(shù)組空間大小是否適合繼續(xù)插入，當數(shù)組空間不足時進行擴容，定義此函數(shù)之后可以對上面尾插函數(shù)進行簡化，如下：

void SLPushBack(SL* ps, SLDataType x)
{
    SLCheckCapacity(ps);
    
    ps->arr[ps->size] = x;
    ps->size++;
}

6.頭插

void SLPushFront(SL* ps, SLDataType x)
{
    SLCheckCapacity(ps);
    int end = ps->size;
    //挪動數(shù)據(jù)
    while (end > 0)
    {
        ps->arr[end] = ps->arr[end-1];
        end--;
    }
    ps->arr[0] = x;
    ps->size++;
}

利用擴容函數(shù)對其檢查，注意控制循環(huán)結(jié)束條件。

7.頭刪

void SLPopFront(SL* ps)
{
    assert(ps);
    assert(ps->size > 0);
    int begin = 0;
    while (begin < ps->size-1)
    {
        ps->arr[begin] = ps->arr[begin + 1];
        begin++;
    }
    ps->size--;
}

注意判斷當ps->size等于0時不能再進行ps->size--，要加上一條判斷語句assert(ps->size > 0)。

8.任意位置插入

void SLInsert(SL* ps, int pos, SLDataType x)//任意位置插入
{
    assert(ps);
    assert(pos >= 0);
    assert(pos <= ps->size);
    SLCheckCapacity(ps);
    int end = ps->size;
    while (end>pos)
    {
        ps->arr[end] = ps->arr[end - 1];
        end--;
    }
    ps->arr[pos] = x;
    ps->size++;
}

pos是數(shù)組下標，同時注意判斷pos的范圍。

9.任意位置刪除

void SLErase(SL* ps, int pos)//任意位置刪除
{
    assert(ps);
    assert(pos >= 0);
    assert(pos < ps->size);
    while (pos < ps->size-1)
    {
        ps->arr[pos] = ps->arr[pos + 1];
        pos++;
    }
    ps->size--;
}

pos表示的是數(shù)組下標，有assert(pos >= 0)和assert(pos <= ps->size)兩個判斷條件之后不用再加assert(ps->size>0)，因為當ps->size等于0時，assert(pos <= ps->size)會報錯。

10.查找某個數(shù)的位置

int SLFind(SL* ps, SLDataType x)//返回類型為int,是數(shù)組下標
{
    assert(ps);
    int i = 0;
    for (i = 0; i < ps->size; i++)
    {
        if (ps->arr[i] == x)
            return i;
    }
    return -1;
}

返回值是數(shù)組下標。

思考：當我們想刪除某個值時應(yīng)該怎么做？當被刪除的值有多個時又要怎么做呢？

我們可以通過下面的代碼實現(xiàn)：

int SLNFind(SL* ps, SLDataType x, int begin)//begin是開始查找的位置
{
    assert(ps);
    int i = 0;
    for (i = begin; i < ps->size; i++)
    {
        if (ps->arr[i] == x)
            return i;
    }
    return -1;
}

三、順序表演示及代碼（含源碼）

1.演示效果

2.完整源代碼

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
//動態(tài)順序表
typedef int SLDataType;//當存儲數(shù)據(jù)類型改變時，方便修改
typedef struct SeqList
{
	SLDataType* arr;//指向動態(tài)開辟的數(shù)組
	int size;//用來記錄數(shù)組中存儲有效數(shù)據(jù)元素的個數(shù)
	int capacity;//用來記錄容量大小
}SL;
void SLInit(SL* ps)//初始化順序表
{
	assert(ps);
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}
void SLCheckCapacity(SL* ps)//檢查是否需要擴容
{
	assert(ps);
	//檢查是否需要擴容
	if (ps->size == ps->capacity)
	{
		int NewCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, sizeof(SLDataType) * NewCapacity);
		if (tmp == NULL)
		{
			perror("realloc");
			exit(-1);
		}
		ps->capacity = NewCapacity;
		ps->arr = tmp;
	}
}
void SLPushBack(SL* ps, SLDataType x)//尾插
{
	SLCheckCapacity(ps);//檢查是否需要擴容
	//assert(ps);
	//if (ps->size == ps->capacity)
	//{
	//	int NewCapacity =ps->capacity == 0 ? 4 : 2 * ps->capacity;//判斷剛開始是否有空間
	//	SLDataType* tmp = (SLDataType*)realloc(ps->arr,sizeof(SLDataType) * NewCapacity);
	//	if (tmp == NULL)
	//	{
	//		perror("realloc");
	//		exit(-1);
	//	}
	//	ps->arr = tmp;
	//	ps->capacity = NewCapacity;
	//}
	ps->arr[ps->size] = x;
	ps->size++;
}
void SLPrint(SL* ps)//打印
{
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arr[i]);
	}
	printf("\n");
}
void SLDestroy(SL* ps)//銷毀
{
	assert(ps);
	if (ps->arr != NULL)
	{
		free(ps->arr);
		ps->arr = NULL;
	}
	ps->size = ps->capacity = 0;
}
void SLPopBack(SL* ps)//尾刪
{
	assert(ps);
	//暴力的檢查
	assert(ps->size > 0);//判斷ps->size是否大于0，當?shù)扔?時再刪的話ps->size就會變?yōu)?1，越界
	//溫柔的檢查
	if (ps->size == 0)
	{
		return;
	}
	ps->size--;
}
void SLPushFront(SL* ps, SLDataType x)//頭插
{
	SLCheckCapacity(ps);
	int end = ps->size;
	//挪動數(shù)據(jù)
	while (end > 0)
	{
		ps->arr[end] = ps->arr[end - 1];
		end--;
	}
	ps->arr[0] = x;
	ps->size++;
}
void SLPopFront(SL* ps)//頭刪
{
	assert(ps);
	assert(ps->size > 0);
	int begin = 0;
	while (begin < ps->size - 1)
	{
		ps->arr[begin] = ps->arr[begin + 1];
		begin++;
	}
	ps->size--;
}
void SLInsert(SL* ps, int pos, SLDataType x)//任意位置插入
{
	assert(ps);
	assert(pos >= 0);
	assert(pos <= ps->size);
	SLCheckCapacity(ps);
	int end = ps->size;
	while (end > pos)
	{
		ps->arr[end] = ps->arr[end - 1];
		end--;
	}
	ps->arr[pos] = x;
	ps->size++;
}
void SLErase(SL* ps, int pos)//任意位置刪除
{
	assert(ps);
	assert(pos >= 0);
	assert(pos < ps->size);
	while (pos < ps->size - 1)
	{
		ps->arr[pos] = ps->arr[pos + 1];
		pos++;
	}
	ps->size--;
}
int SLFind(SL* ps, SLDataType x)//查找某個數(shù)并返回下標
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
			return i;
	}
	return -1;
}
int SLNFind(SL* ps, SLDataType x, int begin)//從begin開始查找某個數(shù)
{
	assert(ps);
	int i = 0;
	for (i = begin; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
			return i;
	}
	return -1;
}
void menu()//菜單函數(shù)
{
	printf("********************************\n");
	printf("**   1.尾插      2.尾刪       **\n");
	printf("**   3.頭插      4.頭刪       **\n");
	printf("**   5.任意位置插入           **\n");
	printf("**   6.任意位置刪除           **\n");
	printf("**   7.查找某個數(shù)并返回其下標 **\n");
	printf("**   8.刪除某個數(shù)             **\n");
	printf("**   9.打印                   **\n");
	printf("**   0.退出程序               **\n");
}
int main()
{
	int input = 0;
	int ret = 0;
	int pos = 0;
	SL sl;
	SLInit(&sl);
	do {
		menu();
		printf("請選擇：");
		scanf("%d", &input);
		switch (input)
		{
		case 1:
			printf("請輸入你要尾插的值，以-1結(jié)束：");
			scanf("%d", &ret);
			while (ret != -1)
			{
				SLPushBack(&sl, ret);
				scanf("%d", &ret);
			}
			printf("尾插成功！\n");

			break;
		case 2:
			SLPopBack(&sl);
			printf("尾刪成功！\n");
			break;
		case 3:
			printf("請輸入你要頭插的值，以-1結(jié)束：");
			scanf("%d", &ret);
			while (ret != -1)
			{
				SLPushFront(&sl, ret);
				scanf("%d", &ret);
			}
			printf("頭插成功！\n");
			break;
		case 4:
			SLPopFront(&sl);
			printf("頭刪成功！\n");
			break;
		case 5:
			printf("請輸入你想插入的位置和數(shù)值：");
			scanf("%d%d", &pos, &ret);
			SLInsert(&sl, pos - 1, ret);
			printf("插入成功！\n");
			break;
		case 6:
			printf("請輸入你想刪除的位置：");
			scanf("%d", &pos);
			SLErase(&sl, pos - 1);
			printf("刪除成功！\n");
			break;
		case 7:
			printf("請輸入你想要查找的數(shù)：");
			scanf("%d", &ret);
			int s = SLFind(&sl, ret);
			printf("查找的數(shù)的數(shù)組下標為:%d！\n", s);
			break;
		case 8:
			printf("請輸入你要刪除的數(shù)值：");
			scanf("%d", &ret);
			int tmp = SLNFind(&sl, ret, 0);
			while (tmp != -1)
			{
				SLErase(&sl, tmp);
				tmp = SLNFind(&sl, ret, tmp);
			}
			printf("刪除成功！\n");
			break;
		case 9:
			SLPrint(&sl);
			break;
		default:
			printf("請重新選擇！\n");
			break;
		}
	} while (input);
	SLDestroy(&sl);
	return 0;
}

以上就是C語言實現(xiàn)順序表的基本操作的示例詳解的詳細內(nèi)容，更多關(guān)于C語言順序表的資料請關(guān)注腳本之家其它相關(guān)文章！

相關(guān)文章

  • C++中判斷成員函數(shù)是否重寫

    C++中判斷成員函數(shù)是否重寫

    這篇文章主要介紹了C++中判斷成員函數(shù)是否重寫的相關(guān)資料,需要的朋友可以參考下
    2017-04-04
  • C++深度探索虛函數(shù)覆蓋示例

    C++深度探索虛函數(shù)覆蓋示例

    虛函數(shù)主要通過V-Table虛函數(shù)表來實現(xiàn),該表主要包含一個類的虛函數(shù)的地址表,可解決繼承、覆蓋的問題,下面這篇文章主要給大家介紹了如何通過一篇文章帶你掌握C++虛函數(shù)的來龍去脈,需要的朋友可以參考下
    2022-12-12
  • Reactor反應(yīng)器的實現(xiàn)方法詳解

    Reactor反應(yīng)器的實現(xiàn)方法詳解

    本篇文章是對Reactor反應(yīng)器的實現(xiàn)方法進行了詳細的分析介紹，需要的朋友參考下
    2013-05-05
  • C++約瑟夫環(huán)問題詳解

    C++約瑟夫環(huán)問題詳解

    大家好，本篇文章主要講的是C++約瑟夫環(huán)問題詳解 ，感興趣的同學趕快來看一看吧，對你有幫助的話記得收藏一下，方便下次瀏覽
    2022-01-01
  • C語言實現(xiàn)二叉樹遍歷的迭代算法

    C語言實現(xiàn)二叉樹遍歷的迭代算法

    這篇文章主要介紹了C語言實現(xiàn)二叉樹遍歷的迭代算法,包括二叉樹的中序遍歷、先序遍歷及后序遍歷等,是非常經(jīng)典的算法,需要的朋友可以參考下
    2014-09-09
  • C++的STL中accumulate函數(shù)的使用方法

    C++的STL中accumulate函數(shù)的使用方法

    這篇文章主要介紹了C++的STL中accumulate的使用方法，accumulate作用是累加求和即自定義類型數(shù)據(jù)處理，下文具體的操作方法需要的小伙伴可以參考一下
    2022-03-03
  • Visual C++ 常用數(shù)據(jù)類型轉(zhuǎn)換方法詳解

    Visual C++ 常用數(shù)據(jù)類型轉(zhuǎn)換方法詳解

    本文純粹是總結(jié)一下有關(guān)類型轉(zhuǎn)換的貼子,需要的朋友可以參考下
    2017-06-06
  • C++深入分析回顧函數(shù)重載

    C++深入分析回顧函數(shù)重載

    C++ 允許多個函數(shù)擁有相同的名字，只要它們的參數(shù)列表不同就可以，這就是函數(shù)的重載（Function Overloading），借助重載，一個函數(shù)名可以有多種用途
    2022-06-06
  • C/C++?判斷計算機存儲器字節(jié)序（端序）的幾種方式

    C/C++?判斷計算機存儲器字節(jié)序（端序）的幾種方式

    字節(jié)序是計算機存儲數(shù)據(jù)的格式,主存儲器（主存）的字節(jié)序?qū)Τ绦虻囊浦残院图嫒菪灾陵P(guān)重要,利用聯(lián)合體、指針、位移和掩碼等方法可以檢測和處理字節(jié)序問題,對于內(nèi)存數(shù)據(jù)操作重要,也關(guān)系到跨平臺和網(wǎng)絡(luò)通信的數(shù)據(jù)處理
    2024-10-10
  • C語言中堆空間的生成與釋放詳解

    C語言中堆空間的生成與釋放詳解

    以下是對C語言中堆空間的生成與釋放進行了詳細的分析介紹，需要的朋友可以過來參考下
    2013-08-08

最新評論