前言：
順序表是一種常見的數(shù)據(jù)結(jié)構(gòu)，今天就讓我來帶領(lǐng)大家一起學(xué)習(xí)一下吧！
不會再休息，一分一毫了，OK，let’s go！
一、線性表
- 線性表（linear list）是n個(gè)具有相同特性的數(shù)據(jù)元素的有限序列。 線性表是一種在實(shí)際中廣泛使
用的數(shù)據(jù)結(jié)構(gòu)，常見的線性表：順序表、鏈表、棧、隊(duì)列、字符串… - 線性表在邏輯上是線性結(jié)構(gòu)，也就說是連續(xù)的一條直線。但是在物理結(jié)構(gòu)上并不一定是連續(xù)的，
線性表在物理上存儲時(shí)，通常以數(shù)組和鏈?zhǔn)浇Y(jié)構(gòu)的形式存儲。
二、順序表
1.順序表的概念及結(jié)構(gòu)：
順序表是用一段物理地址連續(xù)的存儲單元依次存儲數(shù)據(jù)元素的線性結(jié)構(gòu)，一般情況下采用數(shù)組存
儲。在數(shù)組上完成數(shù)據(jù)的增刪查改。
2.順序表的分類：
順序表一般可以分為：
- 靜態(tài)順序表：使用定長數(shù)組存儲元素。
//順序表的靜態(tài)存儲
#define N 7
typedef int SLDataType;
typedef struct SeqList
{
SLDataType array[N];//定長數(shù)組
size_t size;//有效數(shù)據(jù)的個(gè)數(shù)
}SeqList;
2. 動態(tài)順序表：使用動態(tài)開辟的數(shù)組存儲。
typedef struct SeqList
{
SLDataType* array;//指向動態(tài)開辟的數(shù)組
size_t size;//有效數(shù)據(jù)的個(gè)數(shù)
size_t capacity;//容量
}SeqList;
3.順序表缺陷：
- 順序表缺陷：
（1）動態(tài)增容有性能消耗。
（2）當(dāng)頭部插入數(shù)據(jù)時(shí)，需要挪動數(shù)據(jù)
三、順序表的代碼實(shí)現(xiàn)：
1.頭文件：
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLDataType;
typedef struct SeqList
{
SLDataType* s;//順序表的名稱（頭指針?。?/span>
int size;//儲存的有效個(gè)數(shù)！
int capacity;//整塊空間的大??！
}SL;
//初始化
void SLInit(SL* ps);
//銷毀
void SLDestory(SL* ps);
//打印
void SLPrint(SL* ps);
//管理數(shù)據(jù)：增刪查改
//尾插
void PushBack(SL* ps, SLDataType x);
//頭插
void PushFront(SL* ps, SLDataType x);
//尾刪
void PopBack(SL* ps);
//頭刪
void PopFront(SL* ps);
//判斷是否擴(kuò)容
void SLCheckCapacity(SL* ps);
//在pos位置之前插入數(shù)據(jù)
void SLInsert(SL* ps, int pos, SLDataType x);
2.函數(shù)文件：
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include "SeqList.h"
//初始化函數(shù)
void SLInit(SL* ps)
{
assert(ps);
//創(chuàng)建空間
ps->s = (SLDataType*)malloc(sizeof(SLDataType)*4);
if (ps->s == NULL)
{
perror("malloc fail");
exit(-1);
}
ps->size = 0;
ps->capacity = 4;
}
//銷毀函數(shù)
void SLDestory(SL* ps)
{
free(ps);
ps->s = NULL;
ps->size = ps->capacity = 0;
}
//打印函數(shù)
void SLPrint(SL* ps)
{
int i = 0;
for (i = 0; i < ps->size; i++)
{
printf("%d ", ps->s[i]);
}
printf("\n");
}
//判斷是否擴(kuò)容
void SLCheckCapacity(SL* ps)
{
assert(ps);
if (ps->size == ps->capacity)
{
//需要擴(kuò)容
SLDataType* tmp = (SLDataType*)realloc(ps->s, sizeof(SLDataType) * ps->capacity * 2);//擴(kuò)大了原來容量的二倍。
//SLDataType* tmp = (SLDataType*)realloc(ps->s, 2 * ps->capacity);標(biāo)準(zhǔn)的錯(cuò)誤寫法！
//如果空間不夠用，要對一些元素進(jìn)行擴(kuò)容。我們擴(kuò)容的標(biāo)準(zhǔn)：就是為這些元素申請它 自身大小 整數(shù)倍 的空間！所以說為什么要sizeof(數(shù)據(jù)類型)，然后再乘以擴(kuò)大的容量的倍數(shù)
if (tmp == NULL)
{
perror("realloc fail");
exit(-1);
}
ps->s = tmp;
ps->capacity *= 2;
}
}
//尾插
void PushBack(SL* ps, SLDataType x)
{
//檢查容量
SLCheckCapacity(ps);
ps->s[ps->size] = x;
ps->size++;
}
//尾刪
void PopBack(SL* ps)
{
assert(ps);
ps->size--;
}
//頭插（利用一個(gè)end指針從后往前拷貝?。?/span>
void PushFront(SL* ps, SLDataType x)
{
assert(ps);
//檢查容量
SLCheckCapacity(ps);
int end = ps->size - 1;
while (end >= 0)
{
ps->s[end+1] = ps->s[end];
end--;
}
ps->s[0] = x;
ps->size++;
}
//頭刪
void PopFront(SL* ps)
{
assert(ps);
int begin = 0;
while (begin < ps->size-1)
{
ps->s[begin] = ps->s[begin + 1];
begin++;
}
ps->size--;
}
//在pos位置之前插入數(shù)據(jù)
void SLInsert(SL* ps, int pos, SLDataType x)
{
assert(ps);
assert(pos >= 0 && pos < ps->size);
SLCheckCapacity( ps);
int end = ps->size - 1;
while (end >= pos)
{
ps->s[end+1] = ps->s[end];
end--;
}
ps->s[pos] = x;
ps->size++;
}
3.測試文件：
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include "SeqList.h"
void test1()
{
SL s1;
SLInit(&s1);
PushFront(&s1, 1);
PushFront(&s1, 2);
PushFront(&s1, 3);
PushFront(&s1, 4);
PushFront(&s1, 5);
SLPrint(&s1);
PopFront(&s1);
PopFront(&s1);
PopFront(&s1);
SLPrint(&s1);
}
void test2()
{
SL s2;
SLInit(&s2);
PushBack(&s2,1);
PushBack(&s2,2);
PushBack(&s2,3);
PushBack(&s2,4);
PushBack(&s2,5);
SLPrint(&s2);
PopBack(&s2);
PopBack(&s2);
PopBack(&s2);
SLPrint(&s2);
}
void test3()
{
SL s2;
SLInit(&s2);
PushBack(&s2, 1);
PushBack(&s2, 2);
PushBack(&s2, 3);
PushBack(&s2, 4);
PushBack(&s2, 5);
SLPrint(&s2);
SLInsert(&s2, 3, 6);//在下標(biāo)為3的數(shù)據(jù)之前插入一個(gè)6
SLPrint(&s2);
}
int main()
{
//test1();//測試頭插，頭刪
//test2();//測試尾插 尾刪
test3();//測試在pos位置之前插入數(shù)據(jù)！
return 0;
}
四、順序表的相關(guān)OJ題：
（1）原地移除數(shù)組中所有的元素val：
1.題目描述：
1.原地移除數(shù)組中所有的元素val，要求時(shí)間復(fù)雜度為O(N)，空間復(fù)雜度為O(1)。OJ鏈接：OJ鏈接
2.思路表述：
3.代碼實(shí)現(xiàn):
int removeElement(int* nums, int numsSize, int val)
{
int src=0;
int dst=0;
while(src<numsSize)
{
if(nums[src]!=val)
{
nums[dst++]=nums[src++];
}
else
{
src++;
}
}
return dst;//返回的是：新數(shù)組的長度，因?yàn)樽詈笠徊匠鲅h(huán)的時(shí)候，dst已經(jīng)++了，所以說直接返回dst就行了
}
（2）刪除有序數(shù)組中的重復(fù)項(xiàng)
1.題目描述：
2.思路表述：
還使用雙下標(biāo)法：
3.代碼實(shí)現(xiàn)：
int removeDuplicates(int* nums, int numsSize)
{
int dst=1;
int src=0;
while(dst<numsSize)
{
if(nums[dst]!=nums[src])
{
//nums[++src]=nums[dst++];//這里的src一定要是前置++,先++，然后再賦值。
src++;
nums[src]=nums[dst];
dst++;
}
else
{
dst++;
}
}
return src+1;
}
（3）合并兩個(gè)有序數(shù)組
1.題目描述：
2.思路表述：
使用3下標(biāo)法：
3.代碼實(shí)現(xiàn)：
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
int end1=m-1;
int end2=n-1;
int end=m+n-1;
while(end1>=0&&end2>=0)
{
if(nums1[end1]>nums2[end2])
{
nums1[end--]=nums1[end1--];
}
else
{
nums1[end--]=nums2[end2--];
}
}
//因?yàn)橛胣ums1的初始長度是m+n，所以不會擔(dān)心數(shù)組大小不夠用。
//下面這個(gè)循環(huán)是針對:比如說nums1中的所有數(shù)字都插到自己數(shù)組后面了，但是因?yàn)閮蓚€(gè)數(shù)組都是有序的，所以我只需要把nums2中的全部數(shù)字依次放到nums1前面就行了。
while(end2>=0)
{
nums1[end--]=nums2[end2--];
}
}
好了，今天的分享就到這里了
如果對你有幫助，記得點(diǎn)贊??+關(guān)注哦！
我的主頁還有其他文章，歡迎學(xué)習(xí)指點(diǎn)。關(guān)注我，讓我們一起學(xué)習(xí)，一起成長吧！文章來源：http://www.zghlxwxcb.cn/news/detail-756864.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-756864.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】順序表---C語言版的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
