@TOC
一、线性表
## 1.线性表的概念
具有n个相同特性的数据元素的有限序列，顺序表，链表 ，栈和队列都是
常见的线性表
在这里插入图片描述
2.顺序表的概念
顺序表是物理地址连续的储存单元依次存储数据元素的线性结构，
一般采用数组储存，在数组上完成增删查改。
分为静态与动态两种：
静态：使用定长数组实现
动态:使用动态开辟的数组实现
这两者跟之前的通讯录的有点相似
可以看这里 ：通讯录
3.顺序表的优缺点
1.优点
1.支持随机访问
2.缺点
1.中间插入或者头插时,会很慢，要挪动数据，时间复杂度为O(N)
2.虽然说动态顺序表已经做出优化，但扩容时，依旧会造成一定的空间浪费
二、顺序表的实现
1.函数的定义和结构体的创建--contact.h
#include<stdlib.h> #include<stdio.h> typedef int type; struct s { type* data;//动态开辟 int size;//记录数量 int cap;//容量大小 }; void SeqListinit(struct s* p); void SeqListpushBack(struct s* p, int x); void SeqListprint(struct s* p); void SeqListpopBack(struct s* p); void SeqListpushFront(struct s* p,int x); void SeqListpopFront(struct s* p); void checkcap(struct s* p); int search(struct s* p, int pos); void SeqListInsert(struct s* p, int pos, int x); void SeqListErase(struct s* p, int pos); void seqListdestory(struct s* p);
2.函数的调用---test.c
#include"contact1.h" int main() { struct s p; SeqListinit(&p); SeqListpushBack(&p, 1); SeqListpushBack(&p, 2); SeqListpushBack(&p, 3); SeqListpushBack(&p, 4); SeqListprint(&p); SeqListpopBack(&p); SeqListprint(&p); SeqListpushFront(&p, 5); SeqListprint(&p); SeqListpopFront(&p); SeqListprint(&p); int pos=search(&p, 3); SeqListInsert(&p, pos, 5); SeqListprint(&p); int pos2= search(&p, 5); SeqListErase(&p, pos2); SeqListprint(&p); seqListdestory(&p); return 0; }
3.动态顺序表的接口
1.尾插
void seqlistpushback(struct s*p,int x) { if(p->size==p->cap)//如果此时的数量等于容量 { type*str=(type*)malloc(sizeof(type)*2*p->cap);//扩容2倍 if(str!=NULL) { p->data=str; p->cap=2*p->cap; } } p->data[p->size]=x; p->size++; }
2.尾删
void SeqListpopBack(struct s* p)//尾删 { p->size--; }
3.头插
void SeqListpushFront(struct s* p, int x)//同理在物理上是连续的 {//所以在头插入数据，就必须将所有数据向后移 int i = 0; if (p->size == p->cap)//扩容 { type* str = (type*)realloc(p->data, sizeof(type) * 2 * p->cap); if (str != NULL) { p->data = str; p->cap = 2 * p->cap; } } for (i = p->size; i >=0; i--)//数据向后移 { p->data[i + 1] = p->data[i]; } p->data[0] = x; p->size++; }
4.头删
void SeqListpopFront(struct s* p)//头删 { int i = 0;//直接将第二个数据赋值给第一个数据即可 for (i = 0; i < p->size-1; i++) { p->data[i] = p->data[i + 1]; } p->size--; }
5.查找指定位置
int search(struct s* p, int pos)//查找指定位置 { int i = 0; for (i = 0; i < p->size; i++)//如果找到这个数 返回这个数的下标 { if (p->data[i] == pos) { return i ; } } }
6.指定插
void SeqListInsert(struct s* p, int pos, int x)//指定插 { if (p->size == p->cap)//扩容 { type* str = (type*)realloc(p->data, sizeof(type) * 2 * p->cap); if (str != NULL) { p->data = str; p->cap = 2 * p->cap; } } int i = 0; for (i = p->size; i >=pos; i--)//从后往前找这个数，并将数依次向后移 { p->data[i + 1] = p->data[i]; } p->data[pos] = x; p->size++; }
7.指定删
void SeqListErase(struct s* p, int pos)//指定删 { int i = 0; for (i = pos; i < p->size-1; i++)//从前往后，从要删除的数开始，把后面的数赋值给前面的数 { p->data[i] = p->data[i + 1]; } p->size--; }
8.初始化
void SeqListinit(struct s* p)//初始化 { p->cap= 5;//假设容量为5 p->size = 0; p->data= (type*)malloc(p->cap*sizeof(type)); }
9.内存销毁
void seqListdestory(struct s* p)//内存销毁 { free(p->data);//动态开辟要记得销毁 ，否则会造成内存泄漏 p->data = NULL; p->size = 0; p->cap = 0; }
