---

1.線性表

• 線性表(linear list)是n個具有相同特性的數(shù)據(jù)元素的有限序列
• 線性表是一種在實際中廣泛使用的數(shù)據(jù)結(jié)構(gòu)，常見的線性表：順序表、鏈表、棧、隊列、字符串…
• 線性表在邏輯上是線性結(jié)構(gòu)，也就說是連續(xù)的一條直線。但是在物理結(jié)構(gòu)上并不一定是連續(xù)的，線性表在物理上存儲時，通常以數(shù)組和鏈式結(jié)構(gòu)的形式存儲

---

2.順序表 - SeqList

• 概念及結(jié)構(gòu)

  • 順序表是用一段物理地址連續(xù)的存儲單元依次存儲數(shù)據(jù)元素的線性結(jié)構(gòu)，一般情況下采用數(shù)組存儲。在數(shù)組上完成數(shù)據(jù)的增刪查改 (此數(shù)組必須從第一個位置開始，連續(xù)存儲)

  

• 動態(tài)順序表 – 使用動態(tài)開辟的數(shù)組存儲

---

3.實現(xiàn)

• 接口

typedef int SLDataType;//類型重命名，方便以后維護替換別的類型typedef struct SeqList
{SLDataType* arr;//指向動態(tài)數(shù)組指針int size;//有效數(shù)據(jù)個數(shù)int capacity;//容量 - 空間大小
}SL;//順序表初始化
void SLInit(SL* ps);
//銷毀順序表
void SLDestroy(SL* ps);
//打印順序表
void SLPrint(SL* ps);//檢測增容
void SLCheckCapacity();//增刪查改
//尾插/尾刪 - O(1)
void SLPushBack(SL* ps, SLDataType x);
void SLPopBack(SL* ps);//頭插/頭刪 - O(N)
void SLPushFront(SL* ps, SLDataType x);
void SLPopFront(SL* ps);//從任意位置插入/刪除
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);//查找和修改
int SLSearch(SL* ps, SLDataType x);
void SLModify(SL* ps, int pos, SLDataType x);

• 接口實現(xiàn)

void SLInit(SL* ps)
{assert(ps);ps->arr = NULL;ps->size = 0;ps->capacity = 0;
}void SLDestroy(SL* ps)
{assert(ps);if (ps->arr){free(ps->arr);ps->arr = NULL;ps->capacity = 0;ps->size = 0;}
}void SLPrint(SL* ps)
{assert(ps);int i = 0;for (i = 0; i < ps->size; i++){printf("%d ", ps->arr[i]);}printf("\n");
}void SLCheckCapacity(SL* ps)
{assert(ps);//檢查容量空間，滿了擴容if (ps->size == ps->capacity){ps->capacity = ps->capacity == 0 ? 4 : ps->capacity * 2; //最大容量擴容SLDataType* tmp = realloc(ps->arr, ps->capacity * sizeof(SLDataType));if (NULL == tmp){perror("realloc:");exit(1);}ps->arr = tmp;}
}void SLPushBack(SL* ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps);ps->arr[ps->size] = x;ps->size++;//SLInsert(ps, ps->size, x); //以上代碼可以用這個封裝替換了
}void SLPopBack(SL* ps)
{assert(ps);//暴力檢查 - 適用于調(diào)試階段assert(ps->size > 0);//溫柔檢查 - 適用于和用戶交互使用//if (0 == ps->size)//{//	printf("SeqList is empty\n");//	return;//}ps->size--;SLErase(ps, ps->size - 1); //以上代碼可以用這個封裝替換了
}void SLPushFront(SL* ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps);//挪動數(shù)據(jù)int end = ps->size - 1;while (end >= 0){ps->arr[end + 1] = ps->arr[end];end--;}ps->arr[0] = x;ps->size++;//SLInsert(ps, 0, x); //以上代碼可以用這個封裝替換了
}void SLPopFront(SL* ps)
{int begin = 1;while (begin < ps->size){ps->arr[begin - 1] = ps->arr[begin];begin++;}ps->size--;//SLErase(ps, 0); //以上代碼可以用這個封裝替換了
}void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size); //檢驗位置合法性SLCheckCapacity(ps);//挪動數(shù)據(jù)int end = ps->size - 1;while (end >= pos){ps->arr[end + 1] = ps->arr[end];end--;}ps->arr[pos] = x;ps->size++;
}void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);//挪動數(shù)據(jù)int begin = pos;while (begin < ps->size - 1){//后面的數(shù)據(jù)往前搬ps->arr[begin] = ps->arr[begin + 1];begin++;}ps->size--;
}int SLSearch(SL* ps, SLDataType x)
{assert(ps);int i = 0;for (i = 0; i < ps->size; i++){if (ps->arr[i] == x){return i;}}return -1;
}void SLModify(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos < ps->size);ps->arr[pos] = x;
}

---

4.順序表缺點

• 空間不夠，需要擴容。
  • 擴容有一定性能損耗
  • 一般擴容兩倍，存在一些空間浪費
• 頭部或者中間位置插入刪除效率低下 – 挪動數(shù)據(jù)
• 改善方案 – 鏈表 – 對順序表缺陷的優(yōu)化
  • 按需申請釋放空間
  • 頭部或者中間插入刪除，不需要挪動數(shù)據(jù)