目錄

1. 線性表

2. 順序表

?2.1 概念與結構

2.2 分類

?2.2.1 靜態順序表

2.2.2 動態順序表?

2.3 動態順序表的實現

---

1. 線性表

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

2. 順序表

?2.1 概念與結構

概念：順序表是??段物理地址連續的存儲單元依次存儲數據元素的線性結構，?般情況下采?數組 存儲。

?順序表和數組的區別？ 順序表的底層結構是數組，對數組的封裝，實現了常?的增刪改查等接?

2.2 分類

?2.2.1 靜態順序表

概念：使?定?數組存儲元素

靜態順序表缺陷：空間給少了不夠?，給多了造成空間浪費 ?

2.2.2 動態順序表?

2.3 動態順序表的實現

SeqList.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//定義動態順序表的結構
typedef int SLDataType;
typedef struct SeqList
{SLDataType* arr;int size;      //有效數據個數int capacity;  //空間容量
}SL;//typedef struct SeqList SL;void SLPrint(SL* ps);
//初始化
void SLInit(SL* ps);
//銷毀
void SLDestroy(SL* ps);//尾插
void SLPushBack(SL* ps, SLDataType x);
//頭插
void SLPushFront(SL* ps, SLDataType x);
//尾刪
void SLPopBack(SL* ps);
//頭刪
void SLPopFront(SL* ps);//指定位置之前插?數據
void SLInsert(SL* ps, int pos, SLDataType x);
// 刪除POS位置的數據
void SLErase(SL* ps, int pos);
//查找
int SLFind(SL* ps, SLDataType x);

SeqList.c

#include"SeqList.h"//初始化
void SLInit(SL* ps)
{ps->arr = NULL;ps->size = ps->capacity = 0;
}void SLCheckCapacity(SL* ps)
{if (ps->size == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//增容//realloc第二個參數，單位是字節SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));if (tmp == NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}
}//尾插
void SLPushBack(SL* ps, SLDataType x)
{assert(ps);//判斷空間是否足夠SLCheckCapacity(ps);//空間足夠的情況下ps->arr[ps->size++] = x;
}//頭插
void SLPushFront(SL* ps, SLDataType x)
{//溫柔的處理方式//if (ps == NULL)//{//	return;//}assert(ps != NULL);//判斷空間是否足夠SLCheckCapacity(ps);//將順序表中所有數據向后挪動一位for (int i = ps->size; i > 0; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[0] = x;++ps->size;
}//尾刪
void SLPopBack(SL* ps)
{//ps：限制參數不能直接給NULL//ps->size：順序表為空assert(ps && ps->size);--ps->size;
}void SLPrint(SL* ps)
{for (int i = 0; i < ps->size; i++){printf("%d ", ps->arr[i]);}printf("\n");
}
//頭刪
void SLPopFront(SL* ps)
{assert(ps && ps->size);for (int i = 0; i < ps->size-1; i++){ps->arr[i] = ps->arr[i + 1];}--ps->size;
}//指定位置之前插?數據
void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);SLCheckCapacity(ps);//pos及之后的數據整體向后挪動一位for (int i = ps->size; i > pos; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[pos] = x;++ps->size;
}
// 刪除POS位置的數據
void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);//pos之后的數據整體向前挪動一位for (int i = pos; i < ps->size-1; i++){ps->arr[i] = ps->arr[i + 1];}--ps->size;
}
//查找
int SLFind(SL* ps, SLDataType x)
{for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x){//找到了return i;}}//未找到return -1;
}
//銷毀
void SLDestroy(SL* ps)
{assert(ps);if (ps->arr)free(ps->arr);ps->arr = NULL;ps->size = ps->capacity = 0;
}

test.c

#include"SeqList.h"void test01()
{SL sl;SLInit(&sl);SLPushBack(&sl, 1);SLPushBack(&sl, 2);SLPushBack(&sl, 3);SLPushBack(&sl, 4);SLPrint(&sl);//SLPushBack(&sl, 5);//SLPushFront(&sl, 1);//SLPushFront(&sl, 2);//SLPushFront(&sl, 3);//SLPushFront(&sl, 4);//4 3 2 1//SLPushFront(NULL, 1);////SLPopBack(&sl);//SLPrint(&sl);//SLPopBack(&sl);//SLPrint(&sl);//SLPopBack(&sl);//SLPrint(&sl);//SLPopBack(&sl);//SLPrint(&sl);//SLPopBack(&sl);
////SLPopFront(&sl);//SLPrint(&sl);//SLPopFront(&sl);//SLPrint(&sl);//SLPopFront(&sl);//SLPrint(&sl);//SLPopFront(&sl);//SLPrint(&sl);//SLPopFront(&sl);//SLPrint(&sl);
////SLInsert(&sl, 4, 100);//SLPrint(&sl);//SLErase(&sl, 3);//SLPrint(&sl);//int find = SLFind(&sl, 22222);//if (find != -1)//{//	printf("找到了！\n");//}//else {//	printf("未找到！\n");//}SLDestroy(&sl);
}int main()
{test01();return 0;
}

?