目錄

1. 順序表的概念

2. 實現的功能

3. 順序表的定義

4.順序表的實現

4.1?seqlist.c

4.2 seqlist.h

4.3 test.c

5. 順序表的優缺點

5.1優點

5.2缺點

---

1. 順序表的概念

用一段物理地址連續的內存依次存儲數據元素的線性結構

本質就是數組，在數組基礎上要求數據是連續存儲的，不能有跳躍間隔。我們可以提前規劃好順序表的容量(靜態順序表)，還可以根據添加數據動態增容(動態順序表)

2. 實現的功能

1. void Seqlistpirnt(SL* ps);//順序表打印
2. void SeqlistDestroy(SL* ps);//銷毀接口
3. void SeqlistCheckCapacity(SL* ps);//擴容函數
4. void SeqlistInit(SL* ps);//順序表初始化
5. void SeqlistPushBack(SL* ps, SLdatatype x);//尾插
6. void SeqlistPopBack(SL* ps);//尾刪
7. void SeqlistPushFront(SL* ps, SLdatatype x);//頭插
8. void SeqlistPopFront(SL* ps);//頭刪
9. int SeqlistFind(SL* ps, SLdatatype x);//找到x位置返回下標，沒找到返回-1

10. void SeqlistInsert(SL* ps, int pos, SLdatatype x);//制定pos下標位置插入
11. void SeqlistErase(SL* ps, int pos);//刪除pos位置的數據

3. 順序表的定義

需要三個參數

1. a：指向動態內存開辟的空間

2. size：數組中的有效數據

3. capacity：存儲的容量可動態增加

//#define N 100
//typedef int SLdatatype;
//
靜態順序表
//typedef struct Seqlist
//{
//    SLdatatype a[N];
//	int size;//表示數組中存儲了多少個有效數據
//
//}Seqlist;typedef int SLdatatype;
//動態順序表
typedef struct Seqlist
{SLdatatype* a;//指向存儲數組的空間int size;//表示數組中存儲了多少個有效數據int capacity;//容量}SL;

4.順序表的實現

分為三個文件

4.1?seqlist.c

實現函數的功能

#define _CRT_SECURE_NO_WARNINGS h
#include"seqlist.h"//動態增容
void SeqlistCheckCapacity(SL* ps)
{if (ps->size == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;SLdatatype* tmp = (SLdatatype*)realloc(ps->a, newcapacity * sizeof(SLdatatype));if (tmp == NULL){exit(-1);}ps->a = tmp;ps->capacity = newcapacity;}
}
//打印輸出順序表
void Seqlistpirnt(SL* ps)
{for (int i = 0; i < ps->size; i++)printf("%d", ps->a[i]);printf("\n");
}
//銷毀順序表
void SeqlistDestroy(SL* ps)
{free(ps->a);ps->a = NULL;ps->capacity = ps->size = 0;
}
//順序表初始化
void SeqlistInit(SL* ps)
{ps->a = NULL;ps->capacity = ps->size = 0;
}
//尾部插入
void SeqlistPushBack(SL* ps, SLdatatype x)
{//SeqlistCheckCapacity(ps);//ps->a[ps->size] = x;//ps->size++;SeqlistInsert(ps, ps->size, x);
}
//尾部刪除
void SeqlistPopBack(SL* ps)
{ps->a[ps->size - 1] = 0;//if(ps->size>0)//溫柔的處理方式//ps->size--;assert(ps->size>0);//暴力的處理方式SeqlistErase(ps, ps->size);}
//頭部插入
void SeqlistPushFront(SL* ps, SLdatatype x)
{		//SeqlistCheckCapacity(ps);//for (int i = ps->size-1; i >= 0; i--)//{//	ps->a[i+1] = ps->a[i];//}//ps->a[0] = x;//ps->size++;SeqlistInsert(ps, 0, x);
}
//頭部刪除
void SeqlistPopFront(SL* ps)
{//if(ps->size>0)//{//	for (int i = 0; i < ps->size; i++)//	{//		ps->a[i] = ps->a[i + 1];//	}//	ps->size--;//}SeqlistErase(ps, 0);}
//查找特定的數
int SeqlistFind(SL* ps, SLdatatype x)
{for (int i = 0; i < ps->size; i++){if (ps->a[i] == x)return i;}return -1;
}
//插入數據到指定位置
void SeqlistInsert(SL* ps, int pos, SLdatatype x)
{	SeqlistCheckCapacity(ps);//assert(pos >= 0 && pos <= ps->size);if (pos > ps->size || pos < 0){printf("越界了\n");return;}ps->size++;for (int i = ps->size - 1; i > pos; i--){ps->a[i] = ps->a[i - 1];}ps->a[pos] = x;
}
//刪除指定位置的數
void SeqlistErase(SL* ps, int pos)
{if (pos == ps->size - 1){ps->size--;return;}for (int i = pos; i < ps->size-1; i++){ps->a[i] = ps->a[i + 1];}ps->size--;
}

4.2 seqlist.h

方便調用函數

#define _CRT_SECURE_NO_WARNINGS h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int SLdatatype;//動態順序表
typedef struct Seqlist
{SLdatatype* a;int size;//表示數組中存儲了多少個有效數據int capacity;}SL;
void Seqlistpirnt(SL* ps);
void SeqlistDestroy(SL* ps);//銷毀接口
void SeqlistCheckCapacity(SL* ps);//擴容函數
void SeqlistInit(SL* ps);
void SeqlistPushBack(SL* ps, SLdatatype x);
void SeqlistPopBack(SL* ps);
void SeqlistPushFront(SL* ps, SLdatatype x);
void SeqlistPopFront(SL* ps);
int SeqlistFind(SL* ps, SLdatatype x);//找到x位置返回下標，沒找到返回-1void SeqlistInsert(SL* ps, int pos, SLdatatype x);//制定pos下標位置插入
void SeqlistErase(SL* ps, int pos);//刪除pos位置的數據

4.3 test.c

進行測試，使用

#define _CRT_voidSECURE_NO_WARNINGS h
#include"seqlist.h"void TestSeqList1()
{SL s1;SeqlistInit(&s1);SeqlistPushBack(&s1, 1);SeqlistPushBack(&s1, 2);SeqlistPushBack(&s1, 3);SeqlistPushBack(&s1, 4);SeqlistPushBack(&s1, 5);Seqlistpirnt(&s1);SeqlistPopBack(&s1);SeqlistPopBack(&s1);Seqlistpirnt(&s1);SeqlistDestroy(&s1);
}void TestSeqList2()
{SL s1;SeqlistInit(&s1);SeqlistPushFront(&s1, 1);SeqlistPushFront(&s1, 2);SeqlistPushFront(&s1, 3);SeqlistPushFront(&s1, 4);SeqlistPushFront(&s1, 5);Seqlistpirnt(&s1);SeqlistPopFront(&s1);SeqlistPopFront(&s1);Seqlistpirnt(&s1);//int t = SeqlistFind(&s1, 2);//printf("%d\n", t);//int pos;//scanf("%d", &pos);//SeqlistInsert(&s1, pos, 6);//Seqlistpirnt(&s1);//scanf("%d", &pos);//SeqlistErase(&s1, pos);//Seqlistpirnt(&s1);SeqlistPopFront(&s1);//SeqlistPopFront(&s1);//Seqlistpirnt(&s1);SeqlistDestroy(&s1);
}
void TestSeqList3()//
{SL s1;int t = SeqlistFind(&s1, 2);}
int main()
{TestSeqList1();TestSeqList2();
}

5. 順序表的優缺點

5.1優點

1.支持隨機訪問（用下標訪問）需要隨機訪問結構，支持算法可以更好適用

2.cpu高速緩存命中率(連續存儲)

5.2缺點

1.頭部中部插入刪除時間效率低O(N)

2.連續的物理空間，空間不夠了以后需要增容

增容有一定程度的消耗

為了避免增容一般都按倍數去增容，用不完可能存在浪費

---

這篇到這里就結束了，希望可以幫到你

（づ￣3￣）づ╭?～