Java數據結構之順序表詳解

更新時間：2023年07月20日 10:07:53 作者：學習同學

這篇文章主要介紹了Java數據結構之順序表詳解，線性表在邏輯上是線性結構，也就說是連續(xù)的一條直線。但是在物理結構上并不一定是連續(xù)的，線性表在物理上存儲時，通常以數組和鏈式結構的形式存儲,需要的朋友可以參考下

一. 線性表

1.1 定義

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

看這個定義我們再聯想前面的知識

是不是發(fā)現數組的使用和這個定義十分相似

沒錯其實順序表本質上就是數組

但是它再數組上增加了一點內容

1.2 特點

它分為靜態(tài)的和動態(tài)的

這個特點是不是又發(fā)現和我們上面做的項目通訊錄十分相似

它是連續(xù)存儲的不能跳過元素

二. 順序表

2.1 定義

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

2.2 代碼

struct SeqList
{
	int a[100]; //數組
	int size; //數組中存儲了多少個數字 
};

我們說類似這個結構的就是一個順序表

但是呢為了我們以后改變數字方便我們可以把這里的100 定義成一個宏這樣我們以后如果想修改順序

表的大小只要改變宏就可以了

代碼表示如下

// 靜態(tài)順序表
#define N 100
struct SeqList
{
	int a[N]; //數組
	int size; //數組中存儲了多少個數字 
};

上面就是一個標準的靜態(tài)數據表假如說我們想使用順序表來管理一個字符串

#define N 100
struct SeqList
{
	char a[N]; //數組
	int size; //數組中存儲了多少個數字 
};

我們可以改變int類型變?yōu)閏har類型的數據但是這樣每次改也太麻煩了所以我們依舊可以再上面定義

一個宏變量

#define N 100
typedef char SLDateType
struct SeqList
{
	int SLDateType[N]; //數組
	int size; //數組中存儲了多少個數字 
};

我們說就可以使用這樣的格式方便以后一次性改變所有的變量類型

但是呢這樣子我們看整個結構體還是有點麻煩我們再將這個結構體簡化一下

typedef struct SeqList
{
	int SLDateType[N]; //數組
	int size; //數組中存儲了多少個數字 
}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; //數組
	int size; //數組中存儲了多少個數字 
	int capacity;
}SL;

是不是跟我們的通訊錄特別相似

其實原理本質上都是一樣的這里只是命名更加規(guī)范了

2.6 動態(tài)順序表接口的實現

初始化

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個數據的空間這里可以使用一個三目操作符解決

int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;

養(yǎng)成良好的習慣代碼加注釋

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++;
}

這里我們使用一個打印函數看看整個數據的內容

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

打印出結果如下

在這里插入圖片描述

在使用完成之后我們還需要一個借口函數來釋放我們的動態(tài)開辟的內存從而避免內存泄漏的問題

void SeqListDestory(SL* ps)
{
	free(ps->a);
	ps->a == NULL;
	ps->capacity = ps->size = 0;
}

接下來我們看尾刪函數

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 然后從前往后依次挪數據

代碼表示如下

void SeqListPopFront(SL* ps)
{
	int bejin = 0;
	while (bejin<ps->size-1)
	{
		ps->a[bejin] = ps->a[bejin + 1];
		bejin++;
	}
	ps->size--;
}

在這里插入圖片描述

這里我們基本實現了順序表的所有接口函數啦

三. 代碼

頭文件

#pragma once
#define N 100
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLDateType;
typedef struct SeqList
{
	SLDateType* a; //數組
	int size; //數組中存儲了多少個數字 
	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;
}

到此這篇關于Java數據結構之順序表詳解的文章就介紹到這了,更多相關Java順序表內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

您可能感興趣的文章:

SpringBoot接收參數所有方式總結
這篇文章主要介紹了SpringBoot接收參數所有方式總結,文中通過代碼示例和圖文結合的方式給大家介紹的非常詳細,對大家的學習或工作有一定的幫助,需要的朋友可以參考下
2024-07-07
詳解JAVA中的Collection接口和其主要實現的類
這篇文章主要介紹了JAVA中的Collection接口和其主要實現的類，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧
2019-03-03
Java軟件編程培訓機構靠譜嗎
隨著網絡信息化的快速發(fā)展，Java培訓受到越來越多人的青睞，目前Java工程師的薪資水平在不斷攀升，但是有好多企業(yè)還是招不到合適的人才，為什么呢
2017-04-04
Java并發(fā)編程之synchronized底層實現原理分析
這篇文章主要介紹了Java并發(fā)編程之synchronized底層實現原理,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教
2024-02-02
centos上安裝配置java WEB環(huán)境
前提是centos6.3系統(tǒng)已經安裝好，在這里以64位系統(tǒng)為例，下面是jdk，tomcat，mysql下載安裝步驟，有需要的小伙伴可以參考下
2016-10-10
Java如何通過ssh遠程連接主機并執(zhí)行命令
這篇文章主要介紹了Java如何通過ssh遠程連接主機并執(zhí)行命令問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教
2023-07-07
詳解SpringBoot+Mybatis實現動態(tài)數據源切換
這篇文章主要介紹了詳解SpringBoot+Mybatis實現動態(tài)數據源切換，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧
2021-05-05
Java中List集合去重的幾種方式詳細解析
這篇文章主要介紹了Java中List集合去重的幾種方式詳細解析,在日常的業(yè)務開發(fā)中,偶爾會遇到需要將 List 集合中的重復數據去除掉的場景,那么今天我們來看看幾種LIst集合去重的方式,需要的朋友可以參考下
2023-11-11
Java中保證線程順序執(zhí)行的操作代碼
本文給大家分享一篇教程關于java線程順序執(zhí)行問題，如何保證線程的順序執(zhí)行呢？今天通過實例代碼給大家詳細講解下，感興趣的朋友跟隨小編一起看看吧
2021-05-05
Java中的Kafka攔截器詳解
這篇文章主要介紹了Java中的Kafka攔截器詳解,Producer?攔截器(interceptor)是在?Kafka?0.10?版本被引入的,主要用于實現?clients?端的定制化控制邏輯,需要的朋友可以參考下
2023-11-11