1.动态顺序表

第一章 自测&关键词回顾

视频链接: 鹏哥数据结构

第二章 手撕开始

• SeqList.h
• SeqList.c
• test.c

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int SeqDataType;

typedef struct SeqList {
	SeqDataType* p;
	int size;
	int capacity;
} SeqList;

// 初始化线性表
SeqList SeqListInit();
// 扩容
void checkCapacity(SeqList* ps);
// 销毁
void SeqListDestroy(SeqList* ps);
// 尾插
void SeqListPushBack(SeqList* ps, SeqDataType x);
// 尾删
void SeqListPopBack(SeqList* ps);
// 头插
void SeqListPushFront(SeqList* ps, SeqDataType x);
// 头删
void SeqListPopFront(SeqList* ps);
// 找到返回目标数据x,位置的下标,否则返回-1
int SeqListFind(SeqList* ps, SeqDataType x);
// 在pos下标位置插入
void SeqListInsert(SeqList* ps, int pos, SeqDataType x);
// 删除pos位置的数据
void SeqListErase(SeqList* ps, int pos);

#include "SeqList.h"

// 初始化线性表
SeqList SeqListInit() {
	struct SeqList newSqList;
	newSqList.p=NULL; //  建议显示置空
	newSqList.size=newSqList.capacity=0;
	return newSqList;
}
// 扩容
void checkCapacity(SeqList* ps) {
	if(ps->size==ps->capacity) {
		int newCapacity = !ps->capacity?4:ps->capacity*2;
		SeqDataType* newP=(SeqDataType*)realloc(ps->p, newCapacity*sizeof(SeqDataType));
		if(newP!=NULL) {
			ps->p=newP;
			ps->capacity=newCapacity;
		} else {
			printf("realloc failed");
			assert(-1);
		}

	}
}
// 销毁
void SeqListDestroy(SeqList* ps) {
	free(ps->p);
	ps->p=NULL; //  建议显示置空
	ps->size=ps->capacity=0;
}
// 遍历
void SeqListtraverse (SeqList* ps) {
	for(int i=0; i<ps->size; i++) {
		printf("%d->",ps->p[i]);
	}
	printf("end size:%d  capacity%d\n", ps->size, ps->capacity);
}
// 尾插
void SeqListPushBack(SeqList* ps, SeqDataType x) {
	checkCapacity(ps);
	ps->p[ps->size++]=x;
}
// 尾删
void SeqListPopBack(SeqList* ps) {
	if(ps->size==0) {
		printf("SeqList is empty!");
		assert(-1);
	}
	ps->size--;
}
// 头插
void SeqListPushFront(SeqList* ps, SeqDataType x) {
	checkCapacity(ps);
	int end = ps->size++; // 后置++
	while(end>0) {
		ps->p[end]=ps->p[end-1];
		end--;
	}
	ps->p[0]=x;
}
// 头删
void SeqListPopFront(SeqList* ps) {
	if(ps->size==0) {
		printf("SeqList is empty!");
		assert(0);
	}
	for(int i=0; i<ps->size-1; i++) { // TODO:一定要确保循环中最大值不越界
		ps->p[i]=ps->p[i+1];
	}
	ps->size--;
}
// 找到返回目标数据x,位置的下标,否则返回-1
int SeqListFind(SeqList* ps, SeqDataType x) {
	for(int i=0; i<ps->size; i++) {
		if(ps->p[i]==x) {
			return i;
		}
	}
	return -1;
}
// 在pos下标位置插入
void SeqListInsert(SeqList* ps, int pos, SeqDataType x) {
	checkCapacity(ps);
	if(pos<0 || pos>ps->size) {
		printf("insert pos is illegal!");
		assert(0);
	}
	int end = ps->size++;
	while(end>pos) {
		ps->p[end]=ps->p[end-1];
		end--;
	}
	ps->p[pos]=x;

}
// 删除pos位置的数据
void SeqListErase(SeqList* ps, int pos) {
	// 删除位置是否合法
	if(pos<0 || pos>=ps->size ) {
		printf("delete pos is illegal!");
		assert(0);
	}
	// 判空
	if(ps->size==0) {
		printf("SeqList is empty!");
		assert(0);
	}

	for(int i=pos; i<ps->size-1; i++) { // TODO:
		ps->p[i]=ps->p[i+1];
	}
	ps->size--;
}

#include "SeqList.h"

void testAll() {
	printf("=== 开始接口测试 ===\n");

	// 测试初始化
	SeqList list = SeqListInit();
	assert(list.size == 0 && list.capacity == 0 && list.p == NULL);
	printf("初始化测试通过\n");
	SeqListtraverse(&list);

	// 测试尾插
	for(int i=1; i<=5; i++) SeqListPushBack(&list, i);
	assert(list.size ==5 && list.p[4]==5);
	printf("尾插测试通过\n");
	SeqListtraverse(&list);

	// 测试头插
	SeqListPushFront(&list, 0);
	assert(list.size==6 && list.p[0]==0 && list.p[5]==5);
	printf("头插测试通过\n");
	SeqListtraverse(&list);

	// 测试中间插入
	SeqListInsert(&list, 3, 99);
	assert(list.p[3]==99 && list.size==7);
	printf("中间插入测试通过\n");
	SeqListtraverse(&list);

	// 测试查找
	int pos = SeqListFind(&list, 99);
	assert(pos ==3);
	printf("查找测试通过\n");
	SeqListtraverse(&list);
	// 测试头删
	SeqListPopFront(&list);
	assert(list.p[0]==1 && list.size==6);
	printf("头删测试通过\n");
	SeqListtraverse(&list);

	// 测试尾删
	SeqListPopBack(&list);
	assert(list.size==5 && list.p[2]==99);
	printf("尾删测试通过\n");
	SeqListtraverse(&list);

	// 测试中间删除
	SeqListErase(&list, 2);
	assert(list.p[2]==3 && list.size==4);
	printf("中间删除测试通过\n");

	// 测试销毁
	SeqListDestroy(&list);
	assert(list.size==0 && list.capacity==0 && list.p==NULL);
	printf("销毁测试通过\n");

	printf("=== 所有接口测试完成 ===\n");
}
int main() {
	testAll();
	return 0;
}

第三章 相关应用

第四章 上手真题

第五章 比赛怎么用