国产无码综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

<tfoot id="eozj9"></tfoot>

<del id="eozj9"><b id="eozj9"></b></del>

<del id="eozj9"><pre id="eozj9"></pre></del>

『初階數(shù)據(jù)結構 ? C語言』⑧ - 動態(tài)順序表詳解（附完整源碼）

2年前作者：花想云分類：Toy博客閱讀(24)違法舉報

這篇具有很好參考價值的文章主要介紹了『初階數(shù)據(jù)結構 ? C語言』⑧ - 動態(tài)順序表詳解（附完整源碼）。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。

動態(tài)順序表,新星計劃免費學習專欄·數(shù)據(jù)結構與算法,c++,c語言,開發(fā)語言,數(shù)據(jù)結構

本章內容

寫在前面

1.靜態(tài)與動態(tài)是指什么？

2.動態(tài)順序表結構的定義

3.動態(tài)順序表的函數(shù)接口實現(xiàn)

4.動態(tài)順序表的問題及思考

5.關于順序表的OJ題

6.OJ答案及解析

1.移除元素

2.刪除有序數(shù)組中的重復項

?3.合并兩個有序數(shù)組

7.動態(tài)順序表完整源碼

1.SeqList.h

2.SeqList.c

動態(tài)順序表,新星計劃免費學習專欄·數(shù)據(jù)結構與算法,c++,c語言,開發(fā)語言,數(shù)據(jù)結構 ?

?文章來源地址http://www.zghlxwxcb.cn/news/detail-600506.html

寫在前面

上一章我們學習了靜態(tài)順序表的增刪查改，并認識了靜態(tài)順序表的存儲結構與靜態(tài)順序表的在不同場景下的優(yōu)劣。靜態(tài)順序表與動態(tài)順序表都叫做順序表，只不過我們平時口頭所提的順序表指的是動態(tài)順序表。靜態(tài)順序表的局限性太高，無法應對各種復雜的情況所以我們幾乎不用它。本章我們就來學習動態(tài)順序表的實現(xiàn)。

1.靜態(tài)與動態(tài)是指什么？

靜態(tài)順序表：順序表的大小固定，存儲的數(shù)據(jù)個數(shù)有限。

#define N 5
typedef int SLDataType;

//靜態(tài)順序表
typedef struct SeqList
{
	SLDataType a[N];//定長數(shù)組
	int size;//記錄存儲多少個有效數(shù)據(jù)
}SeqList;

動態(tài)順序表：運用動態(tài)內存管理，可按需調整順序表的大小。

typedef int SLDataType;

//動態(tài)順序表
typedef struct SeqList
{
	SLDataType* a;
	int size;//記錄有多少個有效數(shù)據(jù)
	int capacity;//記錄順序表的容量大小
}SeqList;

2.動態(tài)順序表結構的定義

typedef int SLDataType;

//動態(tài)順序表
typedef struct SeqList
{
	SLDataType* a;
	int size;//記錄有多少個有效數(shù)據(jù)
	int capacity;//記錄順序表的容量大小
}SeqList;

3.動態(tài)順序表的函數(shù)接口實現(xiàn)

//初始化順序表
void SLInit(SeqList* ps);
//釋放空間
void SLDestroy(SeqList* ps);
//檢查順序表是否已滿
void CheakCapacity(SeqList* ps);
//動態(tài)順序表的尾插
void SLPushBack(SeqList* ps, SLDataType data);
//動態(tài)順序表的尾刪
void SLPopBack(SeqList* ps);
//動態(tài)順序表的頭插
void SLPushFront(SeqList* ps, SLDataType data);
//動態(tài)順序表的頭刪
void SLPopFront(SeqList* ps);
//pos位置插入數(shù)據(jù)
void SLInsert(SeqList* ps, int pos, SLDataType data);
//pos位置刪除數(shù)據(jù)
void SLErase(SeqList* ps, int pos);
//查找數(shù)據(jù)
int SLFind(SeqList* ps, SLDataType data, int begin);
//判斷數(shù)組是否已滿
bool IsFull(SeqList* ps);
//打印存儲的數(shù)據(jù)
void SLPrint(SeqList* ps);

以下是各個接口的實現(xiàn)：

void SLInit(SeqList* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

void SLDestroy(SeqList* ps)
{
	assert(ps);
	//若ps->a不為NULL，則釋放空間
	if (ps->a)
	{
		free(ps->a);
		ps->a = NULL;
		ps->capacity = ps->size = 0;
	}
}

void CheakCapacity(SeqList* ps)
{
	assert(ps);
	if (ps->capacity == ps->size)
	{
		//若是第一次擴容，則大小為4；
		//若不是第一次，則每次擴容為之前容量的2倍
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("malloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newCapacity;
	}
	//檢查是否做到擴容
	printf("擴容成功,現(xiàn)在的容量為:%d\n", ps->capacity);
}

void SLPushBack(SeqList* ps, SLDataType data)
{
	assert(ps);
	CheakCapacity(ps);
	//插入數(shù)據(jù)
	ps->a[ps->size] = data;
	ps->size++;
}

void SLPopBack(SeqList* ps)
{
	assert(ps);
	ps->size--;
}

void SLPushFront(SeqList* ps, SLDataType data)
{
	assert(ps);
	CheakCapacity(ps);
	//挪動數(shù)據(jù)
	for (int i = ps->size - 1; i >= 0; i--)
	{
		ps->a[i + 1] = ps->a[i];
	}
	//插入數(shù)據(jù)
	ps->a[0] = data;
	ps->size++;
}

void SLPopFront(SeqList* ps)
{
	assert(ps);
	assert(ps->size > 0);
	//挪動數(shù)據(jù)
	for (int i = 0; i < ps->size - 1; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
}

void SLInsert(SeqList* ps, int pos, SLDataType data)
{
	assert(ps);
	CheakCapacity(ps);
	//挪動數(shù)據(jù)
	for (int i = ps->size - 1; i >= pos; i--)
	{
		ps->a[i + 1] = ps->a[i];
	}
	//插入數(shù)據(jù)
	ps->a[pos] = data;
	ps->size++;
}

void SLErase(SeqList* ps, int pos)
{
	assert(ps);
	assert(ps->size > 0);
	//挪動數(shù)據(jù)
	for (int i = pos; i < ps->size - 1; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
}

int SLFind(SeqList* ps, SLDataType data, int begin)
{
	assert(ps);
	assert(begin < ps->size);
	for (int i = begin; i < ps->size; i++)
	{
		if (ps->a[i] == data)
		{
			return i;
		}
	}
	return -1;
}

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

4.動態(tài)順序表的問題及思考

動態(tài)順序表與靜態(tài)順序表的差別僅僅在與一個容量是固定的，一個可以按需擴容。

動態(tài)順序表看似靈活性有所提高但仍存在著空間浪費，特別是擴容次數(shù)越多，越容易造成空間浪費。那么有沒有其他的數(shù)據(jù)結構可以解決這個問題呢？答案是肯定的。這個神奇的數(shù)據(jù)結構叫做鏈表，它是一種基于節(jié)點的數(shù)據(jù)結構。下一章我們就會見到它。

動態(tài)順序表和靜態(tài)順序表都稱為順序表，它們的性能是相同的。關于順序表的性能優(yōu)劣我已經在上一章介紹過了，點擊小卡片即可跳轉。

靜態(tài)順序表詳解http://t.csdn.cn/zwU7I

5.關于順序表的OJ題

1.移除元素

原地移除數(shù)組中所有的元素val，要求時間復雜度為O(N)，空間復雜度為O(1)。?

移除元素https://leetcode.cn/problems/remove-element/

2.刪除有序數(shù)組中的重復項

刪除有序數(shù)組中的重復項https://leetcode.cn/problems/remove-duplicates-from-sorted-array/

3.合并兩個有序數(shù)組

合并兩個有序數(shù)組https://leetcode.cn/problems/merge-sorted-array/

6.OJ答案及解析

1.移除元素

題目要求不能開辟新的數(shù)組，所以我們的做法是遇到等于val的元素時，將數(shù)組末尾的元素依次倒著覆蓋掉等于val的元素。

代碼實現(xiàn);

int removeElement(int* nums, int numsSize, int val){
    int i=0;
    while(i<numsSize)
    {
        while(val==nums[i]&&i<numsSize)
        {
           nums[i]=nums[numsSize-1];
           numsSize--;
        }
        i++;
    }
    return numsSize;

}

以數(shù)組nums={3,2,5,6,3,5},val=3為例。

第一步，檢查索引為0處的值是否等于val；

動態(tài)順序表,新星計劃免費學習專欄·數(shù)據(jù)結構與算法,c++,c語言,開發(fā)語言,數(shù)據(jù)結構

?第二步，將索引為5處的值拷貝到索引為0處；動態(tài)順序表,新星計劃免費學習專欄·數(shù)據(jù)結構與算法,c++,c語言,開發(fā)語言,數(shù)據(jù)結構

?第三步，檢查索引為1處的值；動態(tài)順序表,新星計劃免費學習專欄·數(shù)據(jù)結構與算法,c++,c語言,開發(fā)語言,數(shù)據(jù)結構

第四步，檢查索引為2處的值；動態(tài)順序表,新星計劃免費學習專欄·數(shù)據(jù)結構與算法,c++,c語言,開發(fā)語言,數(shù)據(jù)結構

?第五步，檢查索引為3處的值；動態(tài)順序表,新星計劃免費學習專欄·數(shù)據(jù)結構與算法,c++,c語言,開發(fā)語言,數(shù)據(jù)結構

?第六步，檢查索引為4處的值；

動態(tài)順序表,新星計劃免費學習專欄·數(shù)據(jù)結構與算法,c++,c語言,開發(fā)語言,數(shù)據(jù)結構

?第七步，將索引為4處的值拷貝到索引為4處；

動態(tài)順序表,新星計劃免費學習專欄·數(shù)據(jù)結構與算法,c++,c語言,開發(fā)語言,數(shù)據(jù)結構

此時i已經大于numsSize，循環(huán)結束。?

2.刪除有序數(shù)組中的重復項

本題我采用的是雙指針的方式，p1來記錄當前位置，p2來尋找與p1處的值不相同的元素。

代碼實現(xiàn)：

int removeDuplicates(int* nums, int numsSize){
    int* p1=nums;
    int* p2=nums+1;
    int i=0;
    int returnSize=1;//至少有一個元素
    for(i=0;i<numsSize-1;i++)
    {
        if(*p1!=*(p2+i))
        {
            *(++p1)=*(p2+i);
            returnSize++;
        }
    }
    return returnSize;
}

以數(shù)組nums={0,0,1,1,1,2,2,3,3,4}為例。

動態(tài)順序表,新星計劃免費學習專欄·數(shù)據(jù)結構與算法,c++,c語言,開發(fā)語言,數(shù)據(jù)結構

動態(tài)順序表,新星計劃免費學習專欄·數(shù)據(jù)結構與算法,c++,c語言,開發(fā)語言,數(shù)據(jù)結構

3.合并兩個有序數(shù)組

這道題目我采用的是雙指針的方式。p1指向nums1，p2指向nums2。另外需要額外開辟一個數(shù)組arr，當合并完成之后再將arr里的內容拷貝到nums1中。

代碼實現(xiàn)：

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
    int i=0;
    int j=0;
    int arr[200]={0};
    int* p1=nums1;
    int* p2=nums2;
    int k=0;//記錄arr數(shù)組里元素的個數(shù)
    //檢查數(shù)組是否為空
    if(nums2Size==0)
        return;
    //將nums1或nums2任何一個數(shù)組拷貝完成之后就結束
    while(i<nums1Size-nums2Size&&j<nums2Size)
    {
        if(p1[i]<p2[j])
        {
            arr[k]=p1[i];
            i++;
        }
        else
        {
            arr[k]=p2[j];
            j++;
        }
        k++;
    }
    //如果nums1先結束，將nums2中剩余的元素全部拷貝到arr
    if(i==nums1Size-nums2Size)
    {
        for(;j<nums2Size;j++)
        {
            arr[k++]=p2[j];
        }
    }
    //如果nums2先結束，將nums1中剩余的元素全部拷貝到arr
    if(j==nums2Size)
    {
        for(;i<nums1Size-nums2Size;i++)
        {
            arr[k++]=p1[i];
        }
    }
    //將arr中的元素拷貝回nums1
    for(k=0;k<nums1Size;k++)
    {
        nums1[k]=arr[k];
    }
}

7.動態(tài)順序表完整源碼

1.SeqList.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>

typedef int SLDataType;

//動態(tài)順序表
typedef struct SeqList
{
	SLDataType* a;
	int size;//記錄有多少個有效數(shù)據(jù)
	int capacity;//記錄順序表的容量大小
}SeqList;

//初始化順序表
void SLInit(SeqList* ps);
//釋放空間
void SLDestroy(SeqList* ps);
//檢查順序表是否已滿
void CheakCapacity(SeqList* ps);
//動態(tài)順序表的尾插
void SLPushBack(SeqList* ps, SLDataType data);
//動態(tài)順序表的尾刪
void SLPopBack(SeqList* ps);
//動態(tài)順序表的頭插
void SLPushFront(SeqList* ps, SLDataType data);
//動態(tài)順序表的頭刪
void SLPopFront(SeqList* ps);
//pos位置插入數(shù)據(jù)
void SLInsert(SeqList* ps, int pos, SLDataType data);
//pos位置刪除數(shù)據(jù)
void SLErase(SeqList* ps, int pos);
//查找數(shù)據(jù)
int SLFind(SeqList* ps, SLDataType data, int begin);
//判斷數(shù)組是否已滿
bool IsFull(SeqList* ps);
//打印存儲的數(shù)據(jù)
void SLPrint(SeqList* ps);

2.SeqList.c

#define _CRT_SECURE_NO_DEPRECATE 1
#include"SeqList.h"

void SLInit(SeqList* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

void SLDestroy(SeqList* ps)
{
	assert(ps);
	//若ps->a不為NULL，則釋放空間
	if (ps->a)
	{
		free(ps->a);
		ps->a = NULL;
		ps->capacity = ps->size = 0;
	}
}

void CheakCapacity(SeqList* ps)
{
	assert(ps);
	if (ps->capacity == ps->size)
	{
		//若是第一次擴容，則大小為4；
		//若不是第一次，則每次擴容為之前容量的2倍
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("malloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newCapacity;
	}
	//檢查是否做到擴容
	printf("擴容成功,現(xiàn)在的容量為:%d\n", ps->capacity);
}

void SLPushBack(SeqList* ps, SLDataType data)
{
	assert(ps);
	CheakCapacity(ps);
	//插入數(shù)據(jù)
	ps->a[ps->size] = data;
	ps->size++;
}

void SLPopBack(SeqList* ps)
{
	assert(ps);
	ps->size--;
}

void SLPushFront(SeqList* ps, SLDataType data)
{
	assert(ps);
	CheakCapacity(ps);
	//挪動數(shù)據(jù)
	for (int i = ps->size - 1; i >= 0; i--)
	{
		ps->a[i + 1] = ps->a[i];
	}
	//插入數(shù)據(jù)
	ps->a[0] = data;
	ps->size++;
}

void SLPopFront(SeqList* ps)
{
	assert(ps);
	assert(ps->size > 0);
	//挪動數(shù)據(jù)
	for (int i = 0; i < ps->size - 1; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
}

void SLInsert(SeqList* ps, int pos, SLDataType data)
{
	assert(ps);
	CheakCapacity(ps);
	//挪動數(shù)據(jù)
	for (int i = ps->size - 1; i >= pos; i--)
	{
		ps->a[i + 1] = ps->a[i];
	}
	//插入數(shù)據(jù)
	ps->a[pos] = data;
	ps->size++;
}

void SLErase(SeqList* ps, int pos)
{
	assert(ps);
	assert(ps->size > 0);
	//挪動數(shù)據(jù)
	for (int i = pos; i < ps->size - 1; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
}

int SLFind(SeqList* ps, SLDataType data, int begin)
{
	assert(ps);
	assert(begin < ps->size);
	for (int i = begin; i < ps->size; i++)
	{
		if (ps->a[i] == data)
		{
			return i;
		}
	}
	return -1;
}

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

動態(tài)順序表,新星計劃免費學習專欄·數(shù)據(jù)結構與算法,c++,c語言,開發(fā)語言,數(shù)據(jù)結構

?

到了這里，關于『初階數(shù)據(jù)結構 ? C語言』⑧ - 動態(tài)順序表詳解（附完整源碼）的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！

本文來自互聯(lián)網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。如若轉載，請注明出處：如若內容造成侵權/違法違規(guī)/事實不符，請點擊違法舉報進行投訴反饋，一經查實，立即刪除！

分享到：

領支付寶紅包贊助服務器費用

【數(shù)據(jù)結構初階】二、線性表里的順序表（C語言實現(xiàn)順序表）
========================================================================= 相關代碼gitee自取： C語言學習日記: 加油努力 (gitee.com) ?========================================================================= 接上期：【數(shù)據(jù)結構初階】一. 復雜度講解_高高的胖子的博客-CSDN博客 ?=======================================
2024年02月08日
瀏覽(26)
初階數(shù)據(jù)結構之---順序表和鏈表（C語言）
線性表：線性表（linear list）是n個具有相同特性的數(shù)據(jù)元素的有限序列。線性表是一種在實際中廣泛使用的數(shù)據(jù)結構。線性表在邏輯上是線性結構，也就是說是連續(xù)的一條直線。但在物理上并不一定是連續(xù)的。線性表在物理上存儲時，通常以數(shù)組和鏈式結構的形式存儲。
2024年02月22日
瀏覽(96)
【數(shù)據(jù)結構初階】五、線性表中的棧（C語言 -- 順序表實現(xiàn)棧）
========================================================================= 相關代碼gitee自取： C語言學習日記: 加油努力 (gitee.com) ?========================================================================= 接上期：【數(shù)據(jù)結構初階】四、線性表里的鏈表（帶頭+雙向+循環(huán) 鏈表 -- C語言實現(xiàn)）_高高的胖子的博客
2024年02月08日
瀏覽(51)
【數(shù)據(jù)結構初階】七、非線性表里的二叉樹（堆的實現(xiàn) -- C語言順序結構）
========================================================================= 相關代碼gitee自取： C語言學習日記: 加油努力 (gitee.com) ?========================================================================= 接上期：【數(shù)據(jù)結構初階】六、線性表中的隊列（鏈式結構實現(xiàn)隊列）-CSDN博客 ?===========================
2024年02月08日
瀏覽(31)
詳解初階數(shù)據(jù)結構之順序表（SeqList）——單文件文件實現(xiàn)SeqList的增刪查改
目錄一、線性表二、順序表 2.1概念及結構 2.2接口實現(xiàn) 2.3動態(tài)順序表的創(chuàng)建 2.3動態(tài)順序表的初始化 2.3.1傳值初始化 2.3.2傳址初始化 2.4動態(tài)順序表的清空 2.5動態(tài)順序表的擴容 2.6動態(tài)順序表內容的打印三、動態(tài)順序表的使用 3.1尾插尾刪 3.1.1尾插 3.1.2尾刪 3.2頭插頭刪 3.2.1頭插
2024年02月09日
瀏覽(22)
【數(shù)據(jù)結構專欄】動態(tài)擴容順序棧詳解
? ?? 博客內容：順序棧的原理詳解 ?? 作??者：陳大大陳 ?? 個人簡介：一個正在努力學技術的準前段，專注基礎和實戰(zhàn)分享，歡迎私信！ ?? 歡迎大家：這里是CSDN，我總結知識和寫筆記的地方，喜歡的話請三連，有問題請私信 ?? ?? ?? 目錄順序棧的定義結構體定義
2023年04月09日
瀏覽(24)
【數(shù)據(jù)結構】順序表的動態(tài)分配(步驟代碼詳解）
??個人主頁：豌豆射手^ ??歡迎 ??點贊?評論?收藏 ??收錄專欄：數(shù)據(jù)結構 ??希望本文對您有所裨益，如有不足之處，歡迎在評論區(qū)提出指正，讓我們共同學習、交流進步！在計算機科學中，數(shù)據(jù)結構是組織和存儲數(shù)據(jù)的方式，它決定了數(shù)據(jù)如何被存儲、檢索和操作。
2024年04月12日
瀏覽(21)
C語言數(shù)據(jù)結構-----順序表(多功能動態(tài)順序表的代碼實現(xiàn))
本篇講述了順序表的相關知識，以及動態(tài)順序表的代碼實現(xiàn)。順序表和鏈表一般情況下都會叫他們線性表。線性表（linear list）是n個具有相同特性的數(shù)據(jù)元素的有限序列。線性表是一種在實際中廣泛使用的數(shù)據(jù)結構，常見的線性表：順序表、鏈表、棧、隊列、字符串… 線性
2024年02月07日
瀏覽(25)
數(shù)據(jù)結構（C語言）——順序表詳解
數(shù)據(jù)結構是計算機存儲和組織數(shù)據(jù)的方式。常用的數(shù)據(jù)結構有：數(shù)組（Array）、棧（Stack）、隊列（Queue）、鏈表（Linked List）、樹（Tree）、圖（Graph）、堆（Heap）等；而數(shù)據(jù)結構又可以通過邏輯結構與物理結構進行分類，邏輯結構是指數(shù)據(jù)元素之間的邏輯關系，也就是數(shù)據(jù)元
2024年04月16日
瀏覽(23)
[C語言][數(shù)據(jù)結構][動態(tài)內存空間的開辟]順序表的實現(xiàn)!
目錄零.必備知識 a.順序表的底層是數(shù)組. b.數(shù)組在內存中是連續(xù)存放的. c.動態(tài)內存空間的開辟(malloc,calloc,realloc). 一.順序表的定義與實現(xiàn)? ????????1.1 順序表的定義? ????????1.2 順序表的初始化? ????????1.3 順序表的銷毀? ????????1.4 順序表容量的檢查與調整
2024年04月09日
瀏覽(37)

<del id="t1lkl"><pre id="t1lkl"></pre></del>