一、線性表
線性表（linear list）是n個具有相同特性的資料元素的有限序列， 線性表是一種在實際中廣泛使用的資料結構，常見的線性表：順序表、鏈表、堆疊、佇列、字串…
線性表在邏輯上是線性結構，也就說是連續的一條直線，但是在物理結構上并不一定是連續的，線性表在物理上存盤時，通常以陣列和鏈式結構的形式存盤，
二、順序表
順序表：本質是陣列，動態增長，并且要求里面存盤的資料必須是從左到右連續的，
順序表的缺陷：1、動態增容有性能消耗
2、需要頭部插入資料，需要挪動資料
3、邏輯結構和物理結構不一致
#pragma once
#include<stdio.h>
typedef int SeqDataType;
struct SeqList
{
SeqDataType *a;//指向動態開辟的陣列
int size;//有效資料的個數
int capacity;//容量的大小
};
功能是記憶體中管理資料的結構增刪查改的介面，
初始化和銷毀
void SeqListInit(SeqList seq)
{
seq.a = NULL;
seq.size = seq.capacity = 0;
}
void TestSeqList1()
{
SeqList s;
SeqListInt(&s);
}
int main()
{
TestSeqList1();
return 0;
}
在這里我們傳的是結構體的地址否則無法初始化，
void SeqListInit(SeqList* pq)
{
pq->a = NULL;
pq->size = pq->capacity = 0;
}
void SeqListDestory(SeqList* pq)
{
assert(pq);
free(pq->a);
pq->a = NULL;
pq->capacity = pq->size = 0;
}
頭插和尾插
尾插
void SeqListPushBack(SeqList* pq, SeqDataType x)
{
assert(pq);
//滿了，需要增容
if (pq->size == pq->capacity)
{
int newcapacity = pq->capacity==0 ? 4:pq->capacity * 2;
SeqDataType* newA = relloc(pq->a, sizeof(SeqDataType)*newcapacity);
if (newA == NULL)
{
printf("realloc fail\n");
exit(-1);
}
pq->a = newA;
pq->capacity = newcapacity;
}
pq->a[pq->size] = x;
pq->size++;
}
插入資料的時候我們要先判斷容量是否夠用，不夠用的話要動態開辟空間，
頭插
void SeqListPushFront(SeqList* pq, SeqDataType x)
{
int end = pq->size - 1;
while (end >= 0)
{
pq->a[end + 1] = pq->a[end];
--end;
}
pq->a[0] = x;
pq->size++;
}
要從頭部插入資料，就要先把資料往后移，否則會覆寫后面的資料，
頭刪
void SeqListPopFront(SeqList* pq)
{
assert(pq);
assert(pq->size > 0);
int begin = 0;
while (begin < pq->size - 1)
{
pq->a[begin] = pq->a[begin+1];
}
}
要從頭部洗掉資料，只能用后面的數將前面的數替換形成頭刪
從中間插入
void SeqListInsert(SeqList*pq, int pos, SeqDataType x)
{
assert(pq);
assert(pos >= 0 && pos < pq->size);
int end = pq->size - 1;
while (end>=pos)
{
pq->a[end + 1] = pq->a[end];
--end;
}
pq->a[pos] = x;
pq->size++;
}
注意容量空間，要進行擴容，
從中間洗掉
void SeqListErase(struct SeqList* pq, int pos)
{
assert(pq);
assert(pos >= 0 && pos < pq->size);
int begin = pos;
while (begin <= pq->size - 1)
{
pq->a[begin] = pq->a[begin + 1];
++begin;
}
pq->size--;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/274782.html
標籤：其他
上一篇：【C語言學習筆記——2】
下一篇：分布式事務