Java數(shù)據(jù)結(jié)構(gòu)之順序表詳解
一. 線性表
1.1 定義
線性表（linear list）是n個(gè)具有相同特性的數(shù)據(jù)元素的有限序列。 線性表是一種在實(shí)際中廣泛使用的數(shù)據(jù)結(jié)構(gòu)，常見的線性表：順序表、鏈表、棧、隊(duì)列、字符串… 線性表在邏輯上是線性結(jié)構(gòu)，也就說是連續(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è)定義十分相似
沒錯(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ǔ)的 不能跳過元素
二. 順序表
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ù)字
};我們說類似這個(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ù)表 假如說 我們想使用順序表來管理一個(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ù)字
};我們說 就可以使用這樣的格式 方便以后一次性改變所有的變量類型
但是呢 這樣子我們看整個(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)表之后 我們要開始大概創(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)順序表的特點(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;
}尾插
我們先寫空間足夠的情況
void SeqListPushBack(SL* ps, SLDateType x)
{
ps->a[ps->size] = x;
ps->size++;
}代碼表示如上
那么我們接下來我們寫上面的兩種情況
這里我們要注意的是 一開始我們將指針置空 占用的空間為0
所以說我們一開始至少要開始4個(gè)數(shù)據(jù)的空間 這里可以使用一個(gè)三目操作符解決
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
養(yǎng)成良好的習(xí)慣 代碼加注釋
void SeqListPushBack(SL* ps, SLDateType x)
{
// 如果沒有空間或者空間不足 我們就擴(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ù)來釋放我們的動(dòng)態(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--;
}尾刪的話其實(shí)我們只要將size-- 就可以
但是這里我們要注意一點(diǎn) 當(dāng)size為0的時(shí)候 這里就不可以再刪除了 所以我們還需要完善以下上面的代碼
void SeqListPopBack(SL* ps)
{
if (ps->size==0)
{
perror("SeqListPopBack");
}
ps->size--;
}接下來我們看前插
void SeqListPushFront(SL* ps, SLDateType x)
{
// 考慮擴(kuò)容問題
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++;
}接下來我們來看頭刪
這就要求我們定義一個(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)
{
// 如果沒有空間或者空間不足 我們就擴(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ò)容問題
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)文章
SpringBoot接收參數(shù)所有方式總結(jié)
這篇文章主要介紹了SpringBoot接收參數(shù)所有方式總結(jié),文中通過代碼示例和圖文結(jié)合的方式給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作有一定的幫助,需要的朋友可以參考下2024-07-07
詳解JAVA中的Collection接口和其主要實(shí)現(xiàn)的類
這篇文章主要介紹了JAVA中的Collection接口和其主要實(shí)現(xiàn)的類，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-03-03
隨著網(wǎng)絡(luò)信息化的快速發(fā)展，Java培訓(xùn)受到越來越多人的青睞，目前Java工程師的薪資水平在不斷攀升，但是有好多企業(yè)還是招不到合適的人才，為什么呢2017-04-04
Java并發(fā)編程之synchronized底層實(shí)現(xiàn)原理分析
這篇文章主要介紹了Java并發(fā)編程之synchronized底層實(shí)現(xiàn)原理,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2024-02-02
前提是centos6.3系統(tǒng)已經(jīng)安裝好，在這里以64位系統(tǒng)為例，下面是jdk，tomcat，mysql下載安裝步驟，有需要的小伙伴可以參考下2016-10-10
Java如何通過ssh遠(yuǎn)程連接主機(jī)并執(zhí)行命令
這篇文章主要介紹了Java如何通過ssh遠(yuǎn)程連接主機(jī)并執(zhí)行命令問題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2023-07-07
詳解SpringBoot+Mybatis實(shí)現(xiàn)動(dòng)態(tài)數(shù)據(jù)源切換
這篇文章主要介紹了詳解SpringBoot+Mybatis實(shí)現(xiàn)動(dòng)態(tài)數(shù)據(jù)源切換，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-05-05
這篇文章主要介紹了Java中List集合去重的幾種方式詳細(xì)解析,在日常的業(yè)務(wù)開發(fā)中,偶爾會(huì)遇到需要將 List 集合中的重復(fù)數(shù)據(jù)去除掉的場(chǎng)景,那么今天我們來看看幾種LIst集合去重的方式,需要的朋友可以參考下2023-11-11
本文給大家分享一篇教程關(guān)于java線程順序執(zhí)行問題，如何保證線程的順序執(zhí)行呢？今天通過實(shí)例代碼給大家詳細(xì)講解下，感興趣的朋友跟隨小編一起看看吧2021-05-05
這篇文章主要介紹了Java中的Kafka攔截器詳解,Producer?攔截器(interceptor)是在?Kafka?0.10?版本被引入的,主要用于實(shí)現(xiàn)?clients?端的定制化控制邏輯,需要的朋友可以參考下2023-11-11