Yan-英杰的主頁
悟已往之不諫 知來者之可追
目錄
1.線性表
2.順序表
??????? 2.1 靜態(tài)順序表
??????? 2.2 動態(tài)順序表
??????? 2.3移除元素
1.線性表
??????? 線性表（linear list）是n個具有相同特性的數(shù)據(jù)元素的有限序列。 線性表是一種在實際中廣泛使用的數(shù)據(jù)結構，常見的線性表：順序表、鏈表、棧、隊列、字符串...
????????線性表在邏輯上是線性結構，也就說是連續(xù)的一條直線。但是在物理結構上并不一定是連續(xù)的，線性表在物理上存儲時，通常以數(shù)組和鏈式結構的形式存儲。
2.順序表
????? ??? 2.1 靜態(tài)順序表
???????? ????????注:靜態(tài)順序表有個很大的缺點，空間分配多了浪費，分配少了不夠用,我們通常使用動態(tài)順序表
??????? ????????typedef和define的區(qū)別？
??????????????? typedef通常用來定義類型名稱，define通常用來定義常量
//define通常用來定義常量
#define N 10
//typedef通常用來定義類型名稱
typedef int SLDataType;
//靜態(tài)順序表
//缺點:空間開少了不夠用，開多了不夠用
struct SeqList
{
SLDataType a[N];
SLDataType size;
};
?????? ?? 2.2 動態(tài)順序表
??????????????? 優(yōu)點:當內存堆內存不夠用時,我們可以進行申請
??????????????? 函數(shù)定義
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#define INIT_CAPACITY 4
typedef int SLDataType;
typedef struct SeqList
{
int capacity;
int size;
SLDataType* a;
}SL;
//初始化結構體
void SLInit(SL* ps);
//銷毀結構體
void DestorySL(SL* ps);
//擴容
void CheckCapacity(SL* ps);
//頭插
void SLPushFront(SL* ps, SLDataType x);
//頭刪
void SLPopFront(SL* ps);
//尾插
void SLPushBack(SL* ps,SLDataType x);
//尾刪
void SLPopBack(SL* ps);
//打印
void SLPrint(SL* ps);
//查找
void FindSL(SL* ps);
??????? 函數(shù)實現(xiàn)
#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"
void SLInit(SL* ps)
{
ps->a = (SLDataType*)malloc(sizeof(SLDataType)* INIT_CAPACITY);
if (ps->a == NULL)
{
perror("fail malloc:");
return;
}
ps->size = 0;
ps->capacity = INIT_CAPACITY;
}
void DestorySL(SL* ps)
{
free(ps->a);
ps->a = NULL;
ps->capacity = 0;
ps->size = 0;
}
//擴容
void CheckCapacity(SL* ps)
{
SLDataType* tmp = (SLDataType*)realloc(ps->a,sizeof(INIT_CAPACITY)*ps->capacity*2);
if (tmp == NULL)
{
perror("fail:realloc");
return;
}
ps->a = tmp;
ps->capacity *= 2;
}
//頭插
void SLPushFront(SL* ps,SLDataType x)
{
assert(ps);
CheckCapacity(ps);
int i = 0;
for (i=ps->size; i>=0; i--)
{
ps->a[i] = ps->a[i - 1];
}
ps->a[0] = x;
ps->size++;
}
//頭刪
void SLPopFront(SL * ps)
{
assert(ps);
int i = 0;
for (i=0; i<ps->size; i++)
{
ps->a[i] = ps->a[i + 1];
}
ps->size--;
}
//尾插
void SLPushBack(SL* ps,SLDataType x)
{
//斷言
assert(ps);
CheckCapacity(ps);
ps->a[ps->size] = x;
ps->size++;
}
//尾刪
void SLPopBack(SL* ps)
{
assert(ps);
ps->size--;
}
//打印
void SLPrint(SL* ps)
{
assert(ps);
int i = 0;
for (i=0; i<ps->size; i++)
{
printf("%d ",ps->a[i]);
}
}
//查找指定位置的數(shù)字
void FindSL(SL* ps,int x)
{
assert(ps);
int i = 0;
printf("%d", ps->a[x - 1]);
}
??????? 函數(shù)調用
#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"
void SeqListTest()
{
SL s;
SLInit(&s);
SLPushBack(&s, 1);
SLPushBack(&s, 2);
SLPushBack(&s, 3);
SLPushBack(&s, 4);
SLPushBack(&s, 4);
SLPushFront(&s, 4);
SLPushFront(&s, 4);
SLPrint(&s);
FindSL(&s, 4);
}
int main()
{
SeqListTest();
return 0;
}??????? ??2.3移除元素
????????給你一個數(shù)組 nums 和一個值 val，你需要 原地 移除所有數(shù)值等于 val 的元素，并返回移除后數(shù)組的新長度。
????????不要使用額外的數(shù)組空間，你必須僅使用 O(1) 額外空間并 原地 修改輸入數(shù)組。
????????元素的順序可以改變。你不需要考慮數(shù)組中超出新長度后面的元素。
說明:
????????為什么返回數(shù)值是整數(shù)，但輸出的答案是數(shù)組呢?
????????請注意，輸入數(shù)組是以「引用」方式傳遞的，這意味著在函數(shù)里修改輸入數(shù)組對于調用者是可見的。
????????你可以想象內部操作如下:
// nums 是以“引用”方式傳遞的。也就是說，不對實參作任何拷貝
int len = removeElement(nums, val);
// 在函數(shù)里修改輸入數(shù)組對于調用者是可見的。
// 根據(jù)你的函數(shù)返回的長度, 它會打印出數(shù)組中 該長度范圍內 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}示例 1：
輸入：nums = [3,2,2,3], val = 3
輸出：2, nums = [2,2]
解釋：函數(shù)應該返回新的長度 2, 并且 nums 中的前兩個元素均為 2。你不需要考慮數(shù)組中超出新長度后面的元素。例如，函數(shù)返回的新長度為 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也會被視作正確答案。
示例 2：
輸入：nums = [0,1,2,2,3,0,4,2], val = 2
輸出：5, nums = [0,1,4,0,3]
解釋：函數(shù)應該返回新的長度 5, 并且 nums 中的前五個元素為 0, 1, 3, 0, 4。注意這五個元素可為任意順序。你不需要考慮數(shù)組中超出新長度后面的元素。
提示：
0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100解析：文章來源：http://www.zghlxwxcb.cn/news/detail-404000.html
int removeElement(int* nums, int numsSize, int val){
int src = 0, dst = 0;
while (src < numsSize)
{
if (nums[src] != val)
{
nums[dst++] = nums[src++];
}
else
{
src++;
}
}
return dst;
}????????文章來源地址http://www.zghlxwxcb.cn/news/detail-404000.html
到了這里，關于【數(shù)據(jù)結構】線性表和順序表的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
