目錄

一.線性表

二.順序表

2.1概念及結構

1. 靜態順序表：使用定長數組存儲元素。

2. 動態順序表：使用動態開辟的數組存儲。

2.1按需申請?

2.2 接口實現：增刪查改

SeqList.h:

SeqList.c:

test.c

---

一.線性表

二.順序表

2.1概念及結構

1. 靜態順序表：使用定長數組存儲元素。

開少了不夠用開多了浪費

#define N 100
typedef int SLDateType;
struct Seqlist
{SLDateType a[N];int size;
};

2. 動態順序表：使用動態開辟的數組存儲。

2.1按需申請?

typedef int SLDateType;
struct Seqlist
{SLDateType *a;int size;//有效數據個數  這個個數跟空間大小一樣的時候就擴容int capacity;//空間的容量
};

2.2 接口實現：增刪查改

頭插尾插的時間復雜度都為o(1)

頭刪尾刪的時間復雜度都為o(n)

SeqList.h:

#ifndef SEQLIST_H
#define SEQLIST_H
#include <errno.h>
#include <stdlib.h>
#include<assert.h>
#include<stdio.h>
#define INIT_CAPACITY 10
typedef int SLDataType;
typedef struct Seqlist
{SLDataType* a;int size;       // 有效數據個數int capacity;  // 空間的容量
} SL;
//增刪改查
void SeqInit(SL* s);  // 初始化
void SLDestroy(SL* ps);//銷毀
void SLPushBack(SL* ps, SLDataType x);//插入 尾插
void SLPopBack(SL* ps);//刪除 尾刪
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 SLFind(SL* ps, SLDataType x);//查找x元素的下標
void SLEtdCapacity(SL* ps);//擴容
void SLPrint(SL* ps);//打印
#endif // SEQLIST_H

SeqList.c:

#include "SeqList.h"
//打印
void SLPrint(SL* ps)
{for (int i = 0; i < ps->size; i++){printf("%d ", ps->a[i]);}
}
//擴容
void SLEtdCapacity(SL* ps)
{//如果空間不夠，擴容if (ps->size == ps->capacity){SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) *  ps->capacity);if (tmp == NULL){perror("realloc fail");return;}ps->capacity *= 2;ps->a = tmp;}
}
//初始化
void SeqInit(SL* s)
{s->a = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);if (s->a == NULL){perror("malloc fail");return;}s->size = 0;s->capacity = INIT_CAPACITY;
}
//銷毀
void SLDestroy(SL* ps)
{free(ps->a);ps->a = NULL;ps->capacity = ps -> size = 0;
}
//尾插
void SLPushBack(SL* ps, SLDataType x)
{SLEtdCapacity(&ps);//擴容ps->a[ps -> size] = x;ps->size++;
}
//尾刪
void SLPopBack(SL* ps)
{assert(ps->size>0);ps->size--;
}
//頭插
void SLPushFront(SL* ps, SLDataType x)
{assert(ps);SLEtdCapacity(&ps);//擴容int end = ps->size - 1;while (end >= 0){ps->a[end + 1] = ps->a[end];--end;}ps->a[0] = x;ps->size++;
}
//頭刪
void SLPopFront(SL* ps)//刪除 頭刪
{assert(ps);assert(ps->size > 0);//表不能為空int begin = 1;while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];begin++;}ps->size--;
}
//在某個位置插入
void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);//如果pos等于size相當于尾插SLEtdCapacity(&ps);int end = ps->size - 1;while (end >= pos)//類似于頭插{ps->a[end + 1] = ps->a[end];end--;}ps->a[pos] = x;ps->size++;
}
//在某個位置刪除
void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);//刪除的時候不能等于sizeint begin = pos + 1;while (begin < ps->size){ps->a[begin-1] = ps->a[begin];begin++;}ps->size--;
}
//查找x元素的下標
int SLFind(SL* ps, SLDataType x)
{assert(ps);for (int i = 0; i < ps->size; i++){if (ps->a[i] == x){return i;}}return -1;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"
void TestSeqList1()
{SL s;SeqInit(&s);SLPushFront(&s, 1);SLPushFront(&s, 2);SLPushFront(&s, 3);SLPrint(&s);printf("\n");SLPopFront(&s);SLPopFront(&s);SLPrint(&s);
}
int main()
{TestSeqList1();return 0;
}