目錄
SeqList.h?
SeqList.c?
?頭插尾插復用任意位置插入
頭刪尾刪復用任意位置刪除
SLtest.c?
測試示例
?順序表優劣分析
SeqList.h?
//SeqList.h#pragma once#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#define IN_CY 3typedef int SLdataType;typedef struct SeqList
{SLdataType* a;int size;int capacity;
}SeqList;//初始化函數
void SeqListInit(SeqList* ps);
//銷毀函數
void SeqListDestory(SeqList* ps);
//尾插
void SeqListPushBack(SeqList* ps, SLdataType x);
//尾刪
void SeqListPopBack(SeqList* ps);
//打印函數
void print(SeqList* ps);
//頭插
void SeqListPushFront(SeqList* ps, SLdataType x);
//頭刪
void SeqListPopFront(SeqList* ps);// 順序表在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, SLdataType x);
// 順序表刪除pos位置的值
void SeqListErase(SeqList* ps, int pos);SeqList.c?
//SeqList.C#include "SeqList.h"//初始化順序表
void SeqListInit(SeqList* ps)
{assert(ps);ps->size = 0;ps->capacity = 3;ps->a = (SLdataType*)malloc(sizeof(SLdataType) * ps->capacity);//申請空間失敗if (ps->a == NULL){perror("SeqListInit");exit(-1);}
}//銷毀順序表
void SeqListDestory(SeqList* ps)
{assert(ps);ps->size = 0;ps->capacity = 0;free(ps->a);ps->a = NULL;
}//容量檢查
void SLCheckCapacity(SeqList* ps)
{assert(ps);if (ps->size == ps->capacity){ps->capacity += IN_CY;SLdataType* tmp = (SLdataType*)realloc(ps->a, sizeof(SLdataType) * ps->capacity);//申請空間失敗if (tmp == NULL){perror("SLCheckCapacity");exit(-1);}ps->a = tmp;}
}//尾插
void SeqListPushBack(SeqList* ps, SLdataType x)
{assert(ps);SLCheckCapacity(ps);ps->a[ps->size++] = x;
}//尾刪
void SeqListPopBack(SeqList* ps)
{assert(ps);assert(ps->size);ps->size--;
}//打印順序表
void print(SeqList* ps)
{assert(ps);int i;for (i = 0; i < ps->size; i++){printf("%d ", ps->a[i]);}printf("\n");
}//頭插
void SeqListPushFront(SeqList* ps, SLdataType x)
{assert(ps);SLCheckCapacity(ps);int end = ps->size;while (end--){ps->a[end + 1] = ps->a[end];}ps->size++;ps->a[0] = x;
}//頭刪
void SeqListPopFront(SeqList* ps)
{assert(ps);assert(ps->size);int i;for (i = 0; i < ps->size - 1; i++){ps->a[i] = ps->a[i + 1];}ps->size--;
}// 順序表在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, SLdataType x)
{assert(ps);//下標合法檢查assert(pos>= 0 && pos <= ps->size);SLCheckCapacity(ps);int end = ps->size;while (end >= pos){ps->a[end + 1] = ps->a[end];end--;}ps->size++;ps->a[pos] = x;
}// 順序表刪除pos位置的值
void SeqListErase(SeqList* ps, int pos)
{assert(ps);//下標合法檢查assert(pos >= 0 && pos < ps->size);int i;for (i = pos; i < ps->size - 1; i++){ps->a[i] = ps->a[i + 1];}ps->size--;
}?頭插尾插復用任意位置插入
// 順序表在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, SLdataType x)
{assert(ps);//下標合法檢查assert(pos>= 0 && pos <= ps->size);SLCheckCapacity(ps);int end = ps->size;while (end >= pos){ps->a[end + 1] = ps->a[end];end--;}ps->size++;ps->a[pos] = x;
}//頭插
void SeqListPushFront(SeqList* ps, SLdataType x)
{SeqListInsert(ps, 0, x);
}//尾插
void SeqListPushBack(SeqList* ps, SLdataType x)
{SeqListInsert(ps, ps->size, x);
}頭刪尾刪復用任意位置刪除
// 順序表刪除pos位置的值
void SeqListErase(SeqList* ps, int pos)
{assert(ps);//下標合法檢查assert(pos >= 0 && pos < ps->size);int i;for (i = pos; i < ps->size - 1; i++){ps->a[i] = ps->a[i + 1];}ps->size--;
}//頭刪
void SeqListPopFront(SeqList* ps)
{SeqListErase(ps, 0);
}//尾刪
void SeqListPopBack(SeqList* ps)
{SeqListErase(ps, ps->size - 1);
}SLtest.c?
//SLtest.c#include "SeqList.h"void SLtest1()
{SeqList s1;SeqListInit(&s1);SeqListPushBack(&s1, 1);SeqListPushBack(&s1, 2);SeqListPushBack(&s1, 3);print(&s1);SeqListPushBack(&s1, 4);SeqListPushBack(&s1, 5);print(&s1);SeqListPopBack(&s1);SeqListPopBack(&s1);SeqListPopBack(&s1);SeqListPopBack(&s1);SeqListPopBack(&s1);print(&s1);SeqListDestory(&s1);
}void SLtest2()
{SeqList s1;SeqListInit(&s1);SeqListPushFront(&s1, 1);SeqListPushFront(&s1, 2);SeqListPushFront(&s1, 3);print(&s1);SeqListPushFront(&s1, 4);SeqListPushFront(&s1, 5);print(&s1);//SeqListPopFront(&s1);//SeqListPopFront(&s1);SeqListPopFront(&s1);print(&s1);SeqListPopFront(&s1);print(&s1);SeqListPopFront(&s1);print(&s1);SeqListPopFront(&s1);print(&s1);SeqListDestory(&s1);
}void SLtest3()
{SeqList s1;SeqListInit(&s1);SeqListInsert(&s1, 0, 1);SeqListInsert(&s1, 0, 2);SeqListInsert(&s1, 0, 3);print(&s1);SeqListInsert(&s1, s1.size, 4);SeqListInsert(&s1, s1.size, 5);SeqListInsert(&s1, s1.size, 6);print(&s1);SeqListInsert(&s1, 1, 7);print(&s1);SeqListErase(&s1, s1.size - 1);print(&s1);}
int main()
{//測試尾插尾刪//SLtest1();//測試頭插頭刪//SLtest2();//測試任意位置插入刪除SLtest3();return 0;
}測試示例
尾插：
尾刪：
頭插：
頭刪：
任意位置插入：
任意位置刪除：
?順序表優劣分析
? ? ? ? 由于順序表是一塊連續的空間，因此可以直接通過下標訪問而無需遍歷尋找，所以在需要大量訪問的程序中具有優勢，對緩存的利用率高。而當空間不夠擴容時一般是呈2倍的增長，勢必會有一定的空間浪費。例如當前容量為100，滿了以后增容到200，我們再繼續插入了5個數據，后面沒有數據插入了，那么就浪費了95個數據空間。且對于異地擴容需要申請新空間，拷貝數據，釋放舊空間。會有不小的消耗。
? ? ? ? 尾插和尾刪的時間復雜度為O(1)，因此適用于只需要尾插尾刪的場景。而頭插頭刪和任意位置插入刪除為了保證數據的順序性需要一個一個挪動數據，時間復雜度為0(n)，因此對于需要大量隨機存取的程序來說開銷較大。
? ? ? ? 因此順序表通常應用于元素高效存儲+頻繁訪問的場景。
)
)
