順序表和鏈表

1.線性表：

• 線性表是n個具有相同特性（相同邏輯結構，物理結構）的數據元素的有限序列。常見的線性表有：順序表，鏈表，棧，隊列，字符串…
• 線性表在邏輯上是線性結構，也就說是連續的一條直線。但在物理結構上不一定是連續的，線性表在屋里上存儲時，通常以數組和鏈式結構的形式存儲。
• 邏輯結構：抽象結構，人為想象。比如數組里有五個數據，我們抽象為一個長方形框；比如把排隊買東西的人抽象為一條直線
• 物理結構：存儲時分配的物理空間（數組物理結構是連續的，因為分配的空間是連續的）

2.順序表（邏輯結構：線性；物理結構：線性）

2.1 概念與結構

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

2.2 順序表與數組的區別：

順序表底層是數組，對數組實現封裝，實現了常用的增刪查改操作的接口（可以直接調用順序表中增刪查改相關方法）

2.3 順序表的分類

2.3.1 靜態順序表

• 使用定長數組存儲數據

//靜態順序表
typedef int SLDataType;
#define N 6
typedef struct SeqList
{SLDataType a[N];//定長數組int size;//有效數據個數,下圖有效數據個數為4，指向a[4]
}SL;

2.3.2 動態順序表

//動態順序表--運行時按需申請空間
typedef struct SeqList
{SLDataType* arr;int size;//有效數據個數int capacity;//空間容量
}SL;

//頭文件--SeqList.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
//定義動態順序表的結構
typedef int SLDataType;
typedef struct SeqList
{SLDataType* arr;//存儲數據int size;//有效數據個數int capacity;//空間容量大小
}SL;
void SLInit(SL* ps);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);//查找
int SLFind(SL* ps, SLDataType x);
//指定位置之前插?
void SLInsert(SL* ps, int pos, SLDataType x);
//在指定位置之后插入數據
void SLInsertAfter(SL* ps, int pos, SLDataType x);
//刪除pos位置的數據
void SLErase(SL* ps, int pos);

//實現文件--SeqList.c
#include"SeqList.h"
void SLInit(SL* ps)
{ps->arr = NULL;ps->size = ps->capacity = 0;}
void CheckCapacity(SL* ps)
{int Newcapacity = ps->capacity == 0?4 : 2 * ps->capacity;//如果空間大小為0，就分配四個字節空間if (ps->capacity == ps->size){SLDataType* tmp = (SLDataType*)realloc( ps->arr, Newcapacity * sizeof(SLDataType));//realloc分配成功返回void*//realloc的第二個參數是字節數，可以給數字，比如12，就代表十二個字節//若用來存儲12個int類型的數據，需要12*sizeof（int）//malloc(15)if (tmp == NULL){perror("error");exit(1);}ps->capacity = Newcapacity;ps->arr = tmp;;}
}
void SLPushBack(SL* ps, SLDataType x)//尾插
{assert(ps);//ps為指針變量，檢查指向的地址是否為空，與初始化ps->arr=NULL無關CheckCapacity(ps);//檢查空間是否足夠ps->arr[ps->size] = x;//不可以直接寫成size，訪問指針變量的結構體成員必須用箭頭ps->size++;
}
void SLPushFront(SL* ps, SLDataType x)//頭插
{assert(ps);CheckCapacity(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)//尾刪
{assert(ps && ps->size);ps->size--;//這就是刪除方法，之間減少數據的數量}
void SLPopFront(SL* ps)//頭刪
{for (int i = 1; i<ps->size; i++){ps->arr[i - 1] = ps->arr[i];}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 SLInsert(SL* ps, int pos, SLDataType x)//在指定位置之前插入數據
{assert(ps&&ps->size);CheckCapacity(ps);for (int i = ps->size; i >pos; i--){ps->arr[i] =ps-> arr[i - 1];}ps->arr[pos] = x;ps->size++;}
void SLInsertAfter(SL* ps, int pos, SLDataType x)//在指定位置之后插入數據
{assert(ps->size && ps);CheckCapacity(&ps);for (int i = ps->size; i > pos+1; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[pos + 1] = x;ps->size++;
}void SLPrint(SL* ps)//可以不用指針 ，用指針可以減少拷貝提高效率
{int i = 0;for (i = 0; i < ps->size; i++){printf("%d ", ps->arr[i]);}
}
void SLErase(SL* ps, int pos)//刪除指定位置的數據
{assert(ps && ps->size);if (pos >= ps->size){perror("該位置不存在");return 1;}for (int i = pos; i < ps->size-1; i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}
void SLDestroy(SL*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);SLPushFront(&sl, 8);SLPushFront(&sl, 9);SLPushFront(&sl, 10);/*SLPopBack(&sl);SLPopFront(&sl);SLPopFront(&sl);*//*int c=SLFind(&sl, 10);printf("%d\n", c);*/SLInsert(&sl, 1, 5);SLInsertAfter(&sl, 2, 7);/*SLErase(&sl, 2);*/SLPrint(&sl);SLDestroy(&sl);
}
int main()
{test01();return 0;}