@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;
}