目录

1.线性表

2.顺序存储结构(顺序表)

2.1顺序表一般可以分为：

 1. 静态顺序表：使用定长数组存储元素

  1.1静态顺序表:顺序表的大小是确定的,容量是固定的.

       结论:静态顺序表不是很常量,了解就行.

2. 动态顺序表：使用动态开辟的数组存储。(重要)

2.1优点:我们可以根据实际情况,对内存进行自由分配,从而不造成内存分配浪费!

2.2顺序表的定义

2.3顺序表的初始化

2.4顺序表增容:

2.5顺序表的删除

          思路  :

2.6顺序表的查找:   

        思路:

2.7顺序表的打印

2.8顺序表的释放

2.9顺序表的插入

2.10顺序表的头插头删

2.11顺序表的尾插尾删

---

1.线性表

2.顺序存储结构(顺序表)

顺序存储结构(顺序表)的定义:线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素

2.1顺序表一般可以分为：

 1. 静态顺序表：使用定长数组存储元素

  1.1静态顺序表:顺序表的大小是确定的,容量是固定的.

#define N 10000//运用宏定义,可以方便修改容量的大小
tyPEdef int SLDataType;//运用宏定义,可以根据情况改变存储类型

// 静态顺序表
typedef struct SeqList
{
	SLDataType a[N];
	int size; // 表示数组中存储了多少个数据
}SL;

       结论:静态顺序表不是很常量,了解就行.

2. 动态顺序表：使用动态开辟的数组存储。(重要)

2.1优点:我们可以根据实际情况,对内存进行自由分配,从而不造成内存分配浪费!

2.2顺序表的定义

typedef int sldatatype;//根据实际情况,可以改变存储的类型

typedef struct {
	sldatatype* a;//开辟数组a
	int size;//多少个数据
	int capacITy;//容量是多大

}sl;

 2.3顺序表的初始化

        //顺序表初始化
		void SeqListInit(SL* ps)
		{
			ps->a = NULL;
			ps->size = ps->capacity = 0;//赋值0
		}
        //指针设为空指针,ps指向的容量和数据都赋值0

 2.4顺序表增容:

                        请记住:两种情况都要扩容:

                                内存还未开辟

                                内存满了开辟

                       代码如下 

		void SeqListCheckCapacity(SL* ps)//顺序表扩容
		{
			// 如果没有空间或者空间不足，那么我们就扩容
			if (ps->size == ps->capacity)
			{
				int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity*sizeof(SLDataType));
				if (tmp == NULL)
				{
					PRintf("realloc failn");
					exit(-1);//扩容都要这种判断是否成功
				}
		
				ps->a = tmp;
				ps->capacity = newcapacity;
			}
}

 

2.5顺序表的删除

		// 删除pos位置的数据
		void SeqListErase(SL* ps, int pos)
		{
			assert(pos >= 0 && pos < ps->size);//防止越界
		
			int begin = pos + 1;//遍历从0开始,要加1//取出要删掉的数字
			while (begin < ps->size)
			{
				ps->a[begin - 1] = ps->a[begin];//删掉的元素的位置后面每个元素都要往前挪.
				++begin;
			}
		
			ps->size--;
		}

          思路  :

                        1.取出要删掉的数字;

                        2.删掉的元素的位置后面每个元素都要往前挪.

2.6顺序表的查找:   

//输入你要查找的数据，找到这个数据就返回数据的下标，找不到就返回-1.
			int SeqListFind(SL* ps, SLDataType x)
			{
				for (int i = 0; i < ps->size; i++)
				{
					if (ps->a[i] == x)
					{
						return i;//查找对应那个数据的下标
					}
				}
			
				return -1;
            }

        思路:

               1.查找你要找的数据

               2.找得到,就返回该数据的下标

               3.找不到就返回-1

2.7顺序表的打印

       

		void SeqListPrint(SL* ps)
		{
			for (int i = 0; i < ps->size; ++i)
			{
				printf("%d ", ps->a[i]);
			}
			printf("n");
        }

2.8顺序表的释放

	顺序表释放://扩容就要释放//但只能有一个
		void SeqListDestory(SL* ps)
		{
			free(ps->a);
			ps->a = NULL;
			ps->capacity = ps->size = 0;//释放都要这样
		}

 2.9顺序表的插入

	//顺序表插入
		// 指定pos下标位置插入
		void SeqListInsert(SL* ps, int pos, SLDataType x)
		{
			// 温柔的处理方式
			/*if (pos > ps->size || pos < 0)
			{
				printf("pos invalidn");
				return;
			}*///防止越界
			// 粗暴的方式
			assert(pos >= 0 &amp;& pos <= ps->size);

            //两种方式都可以,但推荐粗暴的方式
		
			SeqListCheckCapacity(ps);
		
			// 挪动数据
			int end = ps->size - 1;
			while (end >= pos)
			{
				ps->a[end + 1] = ps->a[end];//增加位置,把前面的都推到后面去
				--end;
			}
		
			ps->a[pos] = x;
			ps->size++;

2.10顺序表的头插头删

	顺序表头插
	void SeqListPushFront(SL* ps, SLDataType x)
	{
		SeqListCheckCapacity(ps);//扩容

		//挪动数据
		int end = ps->size - 1;
		while (end >= 0)
		{
			ps->a[end + 1] = ps->a[end];
			--end;
		}
		ps->a[0] = x;
		ps->size++;
	
		//SeqListInsert(ps, 0, x);其实用插入就足够了
	}

	顺序表头删
	void SeqListPopFront(SL* ps)
	{
		assert(ps->size > 0);
	
	//挪动数据
			int begin = 0;
			while (begin < ps->size-1)
			{
				ps->a[begin] = ps->a[begin+1];
				++ begin;
			}
	
			int begin = 1;
			while (begin < ps->size)
			{
				ps->a[begin-1] = ps->a[begin];
				++begin;
			}
	
		ps->size--;

		//SeqListErase(ps, 0);用这个删除就足够了
	}
	

2.11顺序表的尾插尾删

	//顺序表尾插
	void SeqListPushBack(SL* ps, SLDataType x)
	{
		/*SeqListCheckCapacity(ps);
	
		ps->a[ps->size] = x;
		ps->size++;*/
		SeqListInsert(ps, ps->size, x);//用插入就可以代替
	}
	
	//顺序表尾删
	void SeqListPopBack(SL* ps)
	{
		// 温柔处理方式
		//if (ps->size > 0)
		//{
		//	//ps->a[ps->size - 1] = 0;
		//	ps->size--;
		//}
	
		// 暴力处理方式
		/*assert(ps->size > 0);
		ps->size--;*/
	
		SeqListErase(ps, ps->size-1);//用删除就可以删除
	}