Java數(shù)據(jù)結(jié)構(gòu)之順序表詳解
一. 線性表
1.1 定義
線性表（linear list）是n個(gè)具有相同特性的數(shù)據(jù)元素的有限序列。 線性表是一種在實(shí)際中廣泛使用的數(shù)據(jù)結(jié)構(gòu)，常見(jiàn)的線性表：順序表、鏈表、棧、隊(duì)列、字符串… 線性表在邏輯上是線性結(jié)構(gòu)，也就說(shuō)是連續(xù)的一條直線。但是在物理結(jié)構(gòu)上并不一定是連續(xù)的，線性表在物理上存儲(chǔ)時(shí)，通常以數(shù)組和鏈?zhǔn)浇Y(jié)構(gòu)的形式存儲(chǔ)。
看這個(gè)定義 我們?cè)俾?lián)想前面的知識(shí)
是不是發(fā)現(xiàn)數(shù)組的使用和這個(gè)定義十分相似
沒(méi)錯(cuò) 其實(shí)順序表本質(zhì)上就是數(shù)組
但是它再數(shù)組上增加了一點(diǎn)內(nèi)容
1.2 特點(diǎn)
它分為靜態(tài)的和動(dòng)態(tài)的
這個(gè)特點(diǎn)是不是又發(fā)現(xiàn)和我們上面做的項(xiàng)目通訊錄十分相似
它是連續(xù)存儲(chǔ)的 不能跳過(guò)元素
二. 順序表
2.1 定義
順序表是用一段物理地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素的線性結(jié)構(gòu)，一般情況下采用數(shù)組存儲(chǔ)。在數(shù)組上完成數(shù)據(jù)的增刪查改。
2.2 代碼
struct SeqList
{
int a[100]; //數(shù)組
int size; //數(shù)組中存儲(chǔ)了多少個(gè)數(shù)字
};我們說(shuō)類似這個(gè)結(jié)構(gòu)的 就是一個(gè)順序表
但是呢 為了我們以后改變數(shù)字方便 我們可以把這里的100 定義成一個(gè)宏 這樣我們以后如果想修改順序
表的大小 只要改變宏就可以了
代碼表示如下
// 靜態(tài)順序表
#define N 100
struct SeqList
{
int a[N]; //數(shù)組
int size; //數(shù)組中存儲(chǔ)了多少個(gè)數(shù)字
};上面就是一個(gè)標(biāo)準(zhǔn)的靜態(tài)數(shù)據(jù)表 假如說(shuō) 我們想使用順序表來(lái)管理一個(gè)字符串
#define N 100
struct SeqList
{
char a[N]; //數(shù)組
int size; //數(shù)組中存儲(chǔ)了多少個(gè)數(shù)字
};我們可以改變int類型 變?yōu)閏har類型的數(shù)據(jù) 但是這樣每次改也太麻煩了 所以我們依舊可以再上面定義
一個(gè)宏變量
#define N 100
typedef char SLDateType
struct SeqList
{
int SLDateType[N]; //數(shù)組
int size; //數(shù)組中存儲(chǔ)了多少個(gè)數(shù)字
};我們說(shuō) 就可以使用這樣的格式 方便以后一次性改變所有的變量類型
但是呢 這樣子我們看整個(gè)結(jié)構(gòu)體還是有點(diǎn)麻煩 我們?cè)賹⑦@個(gè)結(jié)構(gòu)體簡(jiǎn)化一下
typedef struct SeqList
{
int SLDateType[N]; //數(shù)組
int size; //數(shù)組中存儲(chǔ)了多少個(gè)數(shù)字
}SL;這樣子就能得到一個(gè)相對(duì)完美的靜態(tài)順序表啦
2.3 功能需求
在創(chuàng)建好這個(gè)靜態(tài)表之后 我們要開(kāi)始大概創(chuàng)建它的一些功能啦
比如說(shuō)以下的一些功能
vovoid SeqListInit(SL* ps); void SeqListPushBack(SL* ps, SLDateType x); void SeqListPopBack(SL* ps); void SeqListPushFront(SL* ps, SLDateType x); void SeqListPopFront(SL* ps);
初始化 尾插 頭插等等
2.4 靜態(tài)順序表的特點(diǎn)以及缺點(diǎn)
特點(diǎn)： 如果滿了就不讓插入
缺點(diǎn)： 不知道給多少合適
2.5 動(dòng)態(tài)的順序表
typedef struct SeqList
{
SLDateType* a; //數(shù)組
int size; //數(shù)組中存儲(chǔ)了多少個(gè)數(shù)字
int capacity;
}SL;是不是跟我們的通訊錄特別相似
其實(shí)原理本質(zhì)上都是一樣的 這里只是命名更加規(guī)范了
2.6 動(dòng)態(tài)順序表接口的實(shí)現(xiàn)
初始化
void SeqListInit(SL* ps)
{
ps->a = NULL;
ps->size = ps->capacity = 0;
}尾插
我們先寫(xiě)空間足夠的情況
void SeqListPushBack(SL* ps, SLDateType x)
{
ps->a[ps->size] = x;
ps->size++;
}代碼表示如上
那么我們接下來(lái)我們寫(xiě)上面的兩種情況
這里我們要注意的是 一開(kāi)始我們將指針置空 占用的空間為0
所以說(shuō)我們一開(kāi)始至少要開(kāi)始4個(gè)數(shù)據(jù)的空間 這里可以使用一個(gè)三目操作符解決
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
養(yǎng)成良好的習(xí)慣 代碼加注釋
void SeqListPushBack(SL* ps, SLDateType x)
{
// 如果沒(méi)有空間或者空間不足 我們就擴(kuò)容
// 擴(kuò)容失敗就報(bào)錯(cuò)
if ((ps->size)==(ps->capacity))
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
SLDateType* tmp =(SLDateType*)realloc(ps->a, newcapacity * sizeof(SLDateType));
if (tmp==NULL)
{
perror("pushback realloc");
}
}
ps->a[ps->size] = x;
ps->size++;
}這里我們使用一個(gè)打印函數(shù)看看整個(gè)數(shù)據(jù)的內(nèi)容
void SeqListPrint(SL* ps)
{
int i = 0;
for ( i = 0; i < ps->size; i++)
{
printf("%d ", ps->a[i]);
}
printf("\n");
}打印出結(jié)果如下
在使用完成之后我們還需要一個(gè)借口函數(shù)來(lái)釋放我們的動(dòng)態(tài)開(kāi)辟的內(nèi)存 從而避免內(nèi)存泄漏的問(wèn)題
void SeqListDestory(SL* ps)
{
free(ps->a);
ps->a == NULL;
ps->capacity = ps->size = 0;
}接下來(lái)我們看尾刪函數(shù)
void SeqListPopBack(SL* ps)
{
ps->size--;
}尾刪的話其實(shí)我們只要將size-- 就可以
但是這里我們要注意一點(diǎn) 當(dāng)size為0的時(shí)候 這里就不可以再刪除了 所以我們還需要完善以下上面的代碼
void SeqListPopBack(SL* ps)
{
if (ps->size==0)
{
perror("SeqListPopBack");
}
ps->size--;
}接下來(lái)我們看前插
void SeqListPushFront(SL* ps, SLDateType x)
{
// 考慮擴(kuò)容問(wèn)題
if ((ps->size) == (ps->capacity))
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
ps->capacity = newcapacity;
SLDateType* tmp = (SLDateType*)realloc(ps->a, newcapacity * sizeof(SLDateType));
if (tmp == NULL)
{
perror("pushback realloc");
}
ps->a = tmp;
}
// 頭插
int end = ps->size - 1;
while (end>=0)
{
ps->a[end + 1] = ps->a[end];
}
ps->a[0] = x;
ps->size++;
}接下來(lái)我們來(lái)看頭刪
這就要求我們定義一個(gè)bejin 然后從前往后依次挪數(shù)據(jù)
代碼表示如下
void SeqListPopFront(SL* ps)
{
int bejin = 0;
while (bejin<ps->size-1)
{
ps->a[bejin] = ps->a[bejin + 1];
bejin++;
}
ps->size--;
}
這里我們基本實(shí)現(xiàn)了順序表的所有接口函數(shù)啦
三. 代碼
頭文件
#pragma once
#define N 100
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLDateType;
typedef struct SeqList
{
SLDateType* a; //數(shù)組
int size; //數(shù)組中存儲(chǔ)了多少個(gè)數(shù)字
int capacity;
}SL;
void SeqListInit(SL* ps);
void SeqListDestory(SL* ps);
void SeqListPushBack(SL* ps, SLDateType x);
void SeqListPopBack(SL* ps);
void SeqListPushFront(SL* ps, SLDateType x);
void SeqListPopFront(SL* ps);
void SeqListPrint(SL* ps);
// .
//...主文件
#define _CRT_SECURE_NO_WARNINGS 1
#include "seqlist.h"
void SeqListInit(SL* ps)
{
ps->a = NULL;
ps->size = ps->capacity = 0;
}
void SeqListPrint(SL* ps)
{
int i = 0;
for ( i = 0; i < ps->size; i++)
{
printf("%d ", ps->a[i]);
}
printf("\n");
}
void SeqListPushBack(SL* ps, SLDateType x)
{
// 如果沒(méi)有空間或者空間不足 我們就擴(kuò)容
// 擴(kuò)容失敗就報(bào)錯(cuò)
if ((ps->size)==(ps->capacity))
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
ps->capacity = newcapacity;
SLDateType* tmp =(SLDateType*)realloc(ps->a, newcapacity * sizeof(SLDateType));
if (tmp==NULL)
{
perror("pushback realloc");
}
ps->a = tmp;
}
ps->a[ps->size] = x;
ps->size++;
}
void SeqListDestory(SL* ps)
{
free(ps->a);
ps->a = NULL;
ps->capacity = ps->size = 0;
}
void SeqListPopBack(SL* ps)
{
if (ps->size==0)
{
perror("SeqListPopBack");
}
ps->size--;
}
void SeqListPushFront(SL* ps, SLDateType x)
{
// 考慮擴(kuò)容問(wèn)題
if ((ps->size) == (ps->capacity))
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
ps->capacity = newcapacity;
SLDateType* tmp = (SLDateType*)realloc(ps->a, newcapacity * sizeof(SLDateType));
if (tmp == NULL)
{
perror("pushback realloc");
}
ps->a = tmp;
}
// 頭插
int end = ps->size - 1;
while (end >= 0)
{
ps->a[end + 1] = ps->a[end];
end--;
}
ps->a[0] = x;
ps->size++;
}
void SeqListPopFront(SL* ps)
{
int bejin = 0;
while (bejin<ps->size-1)
{
ps->a[bejin] = ps->a[bejin + 1];
bejin++;
}
ps->size--;
}測(cè)試文件
#define _CRT_SECURE_NO_WARNINGS 1
#include "seqlist.h"
int main()
{
SL a1;
SeqListInit(&a1);
SeqListPushBack(&a1, 1);
SeqListPushBack(&a1, 2);
SeqListPushBack(&a1, 3);
SeqListPushBack(&a1, 4);
SeqListPushBack(&a1, 5);
SeqListPrint(&a1);
SeqListPopBack(&a1);
SeqListPrint(&a1);
SeqListPopFront(&a1);
SeqListPrint(&a1);
SeqListDestory(&a1);
return 0;
}到此這篇關(guān)于Java數(shù)據(jù)結(jié)構(gòu)之順序表詳解的文章就介紹到這了,更多相關(guān)Java順序表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
SQL注入攻擊及其在SpringBoot中使用MyBatisPlus的防范策略的方法
本文介紹了如何使用SpringBoot整合JavaDeeplearning4j構(gòu)建一個(gè)文本摘要生成系統(tǒng),該系統(tǒng)能夠自動(dòng)從長(zhǎng)篇文本中提取關(guān)鍵信息,生成簡(jiǎn)潔的摘要,幫助用戶快速了解文本的主要內(nèi)容,系統(tǒng)使用LSTM神經(jīng)網(wǎng)絡(luò)模型進(jìn)行訓(xùn)練,并通過(guò)SpringBoot創(chuàng)建RESTful?API進(jìn)行調(diào)用2024-11-11
這篇文章主要介紹了在idea 中添加和刪除模塊Module操作，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2020-08-08
SpringBoot+Vue.js實(shí)現(xiàn)前后端分離的文件上傳功能
這篇文章主要介紹了SpringBoot+Vue.js實(shí)現(xiàn)前后端分離的文件上傳功能,需要的朋友可以參考下2018-06-06
將SpringBoot項(xiàng)目無(wú)縫部署到Tomcat服務(wù)器的操作流程
SpringBoot 是一個(gè)用來(lái)簡(jiǎn)化 Spring 應(yīng)用初始搭建以及開(kāi)發(fā)過(guò)程的框架,我們可以通過(guò)內(nèi)置的 Tomcat 容器來(lái)輕松地運(yùn)行我們的應(yīng)用,本文給大家介紹 SpringBoot 項(xiàng)目部署到獨(dú)立 Tomcat 服務(wù)器的操作流程,需要的朋友可以參考下2024-05-05
SpringBoot集成tomcat詳解實(shí)現(xiàn)過(guò)程
采用spring boot之后，一切變得如此簡(jiǎn)單，打包->java-jar->運(yùn)維，只需要一個(gè)jar包便可以隨意部署安裝。這篇文章，將對(duì) spring boot集成tomcat的源碼進(jìn)行分析，探索其內(nèi)部的原理2023-02-02
Java實(shí)現(xiàn)隨機(jī)出題，10道10以內(nèi)加減法計(jì)算代碼實(shí)例
這篇文章主要介紹了Java實(shí)現(xiàn)隨機(jī)出題，10道10以內(nèi)加減法計(jì)算，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2019-04-04
springCloud gateWay 統(tǒng)一鑒權(quán)的實(shí)現(xiàn)代碼
這篇文章主要介紹了springCloud gateWay 統(tǒng)一鑒權(quán)的實(shí)現(xiàn)代碼，統(tǒng)一鑒權(quán)包括鑒權(quán)邏輯和代碼實(shí)現(xiàn)，本文給大家介紹的非常詳細(xì),需要的朋友可以參考下2022-02-02
本篇文章主要介紹了淺談Java中的Filter過(guò)濾器，小編覺(jué)得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2017-02-02
你所不知道的Spring的@Autowired實(shí)現(xiàn)細(xì)節(jié)分析
這篇文章主要介紹了你所不知道的Spring的@Autowired實(shí)現(xiàn)細(xì)節(jié)分析，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2020-08-08
這篇文章主要給大家介紹了關(guān)于Java集合List相關(guān)面試題整理的相關(guān)資料,下面將提供一些常見(jiàn)的Java集合類面試題及其解答,幫助讀者更好地準(zhǔn)備面試,需要的朋友可以參考下2024-01-01