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