日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

C語言數據結構順序表的進階講解_C 語言

作者：Fighting陽! ? 更新時間： 2022-06-12 編程語言

前言

在學習鏈表之前先掌握順序表

什么是順序表？

順序表是用一段物理地址連續的存儲單元依次存儲數據元素的線性結構一般情況下采用數組存儲，在數組上完成數據的增刪查改。

順序表一般可分為：

  • 1.靜態順序表：使用定長數組存儲。
  • 2.動態順序表：使用動態開辟的數組存儲。

提示：由于靜態功能有限，這里主要討論動態順序表

一、順序表的構造VS功能

1.順序表的構造

示例：

typedef int SeqDataType
// 順序表的動態存儲
typedef struct SeqList
{
 SeqDataType* a; // 指向動態開辟的數組
 size_t size ; // 有效數據個數
 size_t capicity ; // 容量空間的大小
}SeqList;

這里使用SeqDataType定義是由于我們不知道a是什么類型的數組，因此我們要靈活運用功能就要事先定義SeqDataType的類型（此例為int），以便后續結構類型改變時容易操作

在這里插入圖片描述

2.接口實現（功能）

// 基本增刪查改接口
// 順序表初始化
void SeqListInit(SeqList* psl, size_t capacity);
// 順序表銷毀
void SeqListDestory(SeqList* psl);
// 順序表打印
void SeqListPrint(SeqList* psl);
// 檢查空間，如果滿了，進行增容
void CheckCapacity(SeqList* psl);
// 順序表尾插
void SeqListPushBack(SeqList* psl, SLDataType x);
// 順序表尾刪
void SeqListPopBack(SeqList* psl);
// 順序表頭插
void SeqListPushFront(SeqList* psl, SLDataType x);
// 順序表頭刪
void SeqListPopFront(SeqList* psl);
// 順序表查找
int SeqListFind(SeqList* psl, SLDataType x);

二、功能具體分析

1.初始化

在實現具體項目功能之前，要事先做好準備，即初始化，將其置空，assert函數下文講解

代碼如下（示例）：

void SeqListInit(SeqList* pq)//初始化
{
	assert(pq);//斷言，判斷是否可以執行1/0
	pq->a = NULL;
	pq->size = 0;
	pq->capacity = 0;
}

2.銷毀

銷毀是在結束之后需要進行的操作，因為這里是動態，需要考慮空間釋放，以免造成空間泄露。（先提到銷毀是因為其與初始化為首位）

代碼如下（示例）：

void SeqListDestory(SeqList* pq)
{
	assert(pq);
	free(pq->a);
	pq->a = NULL;
	pq->capacity = pq->size = 0;
}

3.檢查size與capacity是否溢出

動態進行就是根據輸入的數據改變自身數組的大小，故我們需要對溢出的情況進行正確的規避，至于為什么會溢出，因為我們在初始化的時候將其空間為0，無論第一次輸入多少數據都會溢出。

void SeqCheckCapacity(SeqList* pq)
{
	if (pq->size == pq->capacity)//滿了，需要增容
	{
		int newcapacity = pq->capacity == 0 ? 4 : pq->capacity * 2;
	//SeqDataType* newA = malloc(sizeof(SeqDataType) * newcapacity);
	  SeqDataType* newA  =realloc(pq->a,sizeof(SeqDataType)* newcapacity);//或者直接擴容
		if (newA == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		pq->a = newA;
		pq->capacity = newcapacity;
	}
}

習慣上在擴容時我們習慣將其放大二倍的操作，由于realloc擴容分為兩種情況（這里暫時不討論），故如果擴容失敗我們需要截止，并打印錯誤。

4.尾增功能（實現）

先上代碼：

void SeqListPushBack(SeqList* pq, SeqDataType x)
{
	assert(pq);
	SeqCheckCapacity(pq);
	pq->a[pq->size] = x;
	pq->size++;
}

顧名思義就是在尾部增添內容，size正對應有效數組下標的下一位，對該位置進行賦值，最后有效數組size應+1，由于尾增之前我們不知道其capacity是否等于size

故我們需要進行檢查seqCheckCapacity，如果相等，則需要擴容。

5.打印

void SeqListPrint(SeqList* pq)
{
	assert(pq);
	for (int i = 0; i < pq->size; ++i)
	{
		printf("%d ", pq->a[i]);
	}
	printf("\n");
}

這里具體就沒什么了，只是為了保證程序功能能夠具體完整實現

其他功能看下面代碼

三、實現具體功能代碼頁（SeqList.c）

#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"
#include<assert.h>
void SeqListInit(SeqList* pq)//初始化
{
	assert(pq);//斷言，判斷是否可以執行1/0
	pq->a = NULL;
	pq->size = 0;
	pq->capacity = 0;
}
void SeqListDestory(SeqList* pq)
{
	assert(pq);
	free(pq->a);
	pq->a = NULL;
	pq->capacity = pq->size = 0;
}
void SeqCheckCapacity(SeqList* pq)
{
	if (pq->size == pq->capacity)//滿了，需要增容
	{
		int newcapacity = pq->capacity == 0 ? 4 : pq->capacity * 2;
	//SeqDataType* newA = malloc(sizeof(SeqDataType) * newcapacity);
	  SeqDataType* newA  =realloc(pq->a,sizeof(SeqDataType)* newcapacity);//或者直接擴容
		if (newA == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		pq->a = newA;
		pq->capacity = newcapacity;
	}
}
void SeqListPushBack(SeqList* pq, SeqDataType x)
{
	assert(pq);
	SeqCheckCapacity(pq);
	pq->a[pq->size] = x;
	pq->size++;
}

void SeqListPrint(SeqList* pq)
{
	assert(pq);
	for (int i = 0; i < pq->size; ++i)
	{
		printf("%d ", pq->a[i]);
	}
	printf("\n");
}
void SeqListPushFront(SeqList* pq, SeqDataType x)
{
	assert(pq);
	SeqCheckCapacity(pq);
	int end = pq->size - 1;
	while (end >= 0)
	{
		pq->a[end + 1] = pq->a[end];	
		end--;
	}
	pq->a[0] = x;
	pq->size++;

}
void SeqListPopBack(SeqList* pq)
{
	assert(pq);
	assert(pq->size > 0);
	--pq->size;
}
void SeqListPopFront(SeqList* pq);//尾刪暫時不實現

test.c主函數代碼頁

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include"SeqList.h"

void TestSeqList1()
{
	SeqList s;
	SeqListInit(&s);//?
	SeqListPushBack(&s, 1);
	SeqListPushBack(&s, 2);
	SeqListPushBack(&s, 3);
	SeqListPushBack(&s, 4);
	SeqListPushBack(&s, 5);
    SeqListPushFront(&s, 0);
    SeqListPushFront(&s, 0);
    SeqListPushFront(&s, 0);
    SeqListPushFront(&s, 0);
	SeqListPrint(&s);
	SeqListPopBack(&s);
	SeqListPrint(&s);
	SeqListPopBack(&s);
	SeqListPrint(&s);
	SeqListDestory(&s);//
}
int main()
{
	TestSeqList1();
	return 0;
}

在這里插入圖片描述

四.總結

順序表類型實現通訊錄后期會更，此目的是為了捋清楚如何構造各項結構與結構之間的關系->數據結構，尾刪，首刪，首增功能都較為容易，可以看上部分SeqList.c。此外，assert函數為斷言，目的是防止出現錯誤卻找不到并且執行的情況，其引用的頭文件為：assert.h。

原文鏈接：https://blog.csdn.net/NEFUT/article/details/123975644

欄目分類
最近更新