一、线性表
线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串等…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储.
二、顺序表
概念:
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表一般分为;两种:1.静态顺序表 2.动态顺序表
静态顺序表实际作用不大,本篇主要讲解动态顺序表.
2.1 静态顺序表简单介绍:
静态顺表是指顺序表的容量是固定的,如果看过c语言实现通讯录的友友们,对于静态顺序表可以轻松拿捏.
2.2 动态顺序表:
三、顺序表的常见操作(接口)
3.1 顺序表的类型声明:
//动态版 typedef int DataType; #define MAX 10 typedef struct SQList { DataType* data;//指向一段连续的内存空间 int size;//代表当前顺序表的长度 int capacity;//表示最大容量 }SQL;
3.2 顺序表的初始化
动态顺序表虽然容量没有限制,会自动扩容,但是也要设置初始值,当达到初始值的最大限制时,才会去动态扩容.
SQL SL;//用顺序表类型创建一个SL顺序表 InitSQL(&SL);
顺序表的初始化是需要修改顺序表中的成员的,所以需要传址调用,否则形参不会影响实参.
void InitSQL(SQL* SL) { assert(SL);//防止传入空指针 SL->capacity = MAX; SL->size = 0;//顺序表初始状态,当前数据量为0 SL->data = (DataType*)malloc(sizeof(DataType) * MAX);//初始化顺序表大小 if (SL->data == NULL) { printf("初始化申请空间失败.\n"); } }
3.3 "增容"函数
当顺序表需要增容时,increase函数利用realloc函数对data指针指向的空间,重新分配合适大小.
DataType* increase(SQL* SL) { assert(SL); SL->capacity *= 2;//增容扩大为原来的两倍,这里根据情况,可自由选择每次扩容的增量 DataType* ret=(DataType*)realloc(SL->data,sizeof(DataType) * SL->capacity);//重新申请一段增容后大小的空间. assert(ret);//如果增容失败,则报错. return ret; }
3.4 顺序表的"插入"操作:
顺序表的"尾插"
顺序表的尾插很简单,size为当前顺序表的数据个数,将其作为下标,刚好可以指向新的位置(尾部的下一个位置),将新元素插入后,size自增1,可完成顺序表的尾插操作.
尾插:
- 插入操作之前都需要先判断顺序表是否已满.
- 以size作为下标,将新元素插入进数组.
- size++,顺序表长度+1.
注意:
执行插入操作之前,要先判断目前的顺序表是否已经达到最大容量(capacity),如果顺序表已满,则需要调用增容函数(increase),对函数进行增容.
代码:
//顺序表的尾插 void PushBack(SQL* SL, DataType x) { assert(SL); if (SL->size == SL->capacity)// { SL->data = increase(SL);//调用增容函数,进行动态扩容 } SL->data[SL->size] = x; SL->size++; }
顺序表的"头插"
顺序表的头插就显得稍微复杂一些,效率不高,需要移动数据.
头插:
- 插入操作之前都需要先判断顺序表是否已满.
- 将所有的原有数据向后移动一个位置. (这里只能从最后一个位置开始往后移,如果从前面开始移动数据,会将后面的数据覆盖,导致数据出错.)
- 将新数据插入进数组首位置.
- size+1,表示顺序表长度+1
//顺序表的头插 void PushFront(SQL* SL, DataType x) { assert(SL); //同样在进行插入操作之前,要先判断是否. if (SL->size == SL->capacity) { SL->data = increase(SL); } for (int i = SL->size; i > 0; i--)//将原来数据往后移 { SL->data[i] = SL->data[i - 1]; } //将新的数据插入到数组首位置 SL->data[0] = x; SL->size++; }
3.5 顺序表的"判空"
size=0时,表示顺序表中没有元素,即顺序表为空.
顺序表如果为空,则返回"真"
顺序表不为空,则返回"假".
//判断是否为空顺序表 bool Empty(SQL* SL) { assert(SL); if (SL->size == 0) { return true; } else return false; }
3.6 顺序表的删除操作
顺序表的"尾删"
顺序表的尾删也是很舒服的.
尾删:
- 判空:进行删除元素的操作之前,我们应当先对顺序表进行"判空"操作,如果顺序表为空,则不能删除
- .size–,即长度-1.
顺序表的尾删操作没有必要真的将最后一个数据删除,只需要调整size的值,那样我们就不能访问到已经删除的元素,这也就等于删除了.
代码:
void PopBack(SQL* SL) { assert(SL); assert(!Empty(SL)); SL->size--; }
顺序表的"头删"
顺序表的头删效率不高,需要将数据从第二个元素开始,往后的所有元素(包括第二个元素)向前移动一个位置.
//顺序表的头删 void PopFront(SQL* SL) { assert(SL); assert(!Empty(SL)); for (int i = 0; i < SL->size-1; i++)//将后面的数据向前覆盖 { SL->data[i] = SL->data[i + 1]; } SL->size--; }
3.7 顺序表的指定位置"插入"
//函数声明.h //指定位置插入元素,位置是下标+1 void SLInsert(SQL* SL, int pos, DataType x);
提供给该函数要插入的元素及其要被插入的位置.
步骤:
- 判断插入的位置是否合法.
- 插入操作之前都需要先判断顺序表是否已满.
- 将数据从最后一个元素开始到pos位置结束(包括pos处的元素),向后移动一个元素.
- 将数据插入到pos位置处.
- size++,顺序表的长度+1
该函数主要注意点有两个:
- pos位置的合法判断.
pos的取值范围应该是,[1,size+1].
不理解时可以举个例子:
- 需要移动的元素的下标的确定.
理解完这两点,代码就不难写了.
代码:
//指定位置的插入 void SLInsert(SQL* SL, int pos, DataType x) { assert(SL); assert(!(pos < 0 || pos > SL->size+1));//这里可以在最后一个位置的后面插入,例如:size=5时,可以在6号位置插入 //老样子,插入之前先检查顺序表是否已满 if (SL->size == SL->capacity) { SL->data = increase(SL); } int i = 0; //移动数据 for ( i = SL->size; i > pos - 1; i--) { SL->data[i] = SL->data[i - 1]; } SL->data[pos-1] = x; SL->size++; }
图解:
此时我们不妨可以利用SLInsert函数来简写尾插和头插.
尾插:
之所以是size+1,是因为位置是坐标+1
void PushBack(SQL* SL, DataType x) { SLInsert(SL, SL->size+1, x); }
头插:
之所以是0+1,也是因为位置是坐标+1
//顺序表的头插 void PushFront(SQL* SL, DataType x) { SLInsert(SL, 0 + 1, x); }
3.8 顺序表的指定位置"删除"
看到这里,相信对于pos的位置范围应该不难判断了吧.
/指定位置删除 void SLErase(SQL* SL, int pos) { assert(SL); assert(!Empty(SL)); assert(!(pos<0 || pos>SL->size));//删除只能在[1-size]范围 for (int i = pos - 1; i < SL->size-1; i++) { SL->data[i] = SL->data[i + 1]; } SL->size--; }
修改后的头删:
//顺序表的头删 void PopFront(SQL* SL) { SLErase(SL, 0 + 1); }
修改后的尾删:
void PopBack(SQL* SL) { SLErase(SL, SL->size); }
3.9 顺序表的"打印"
void PrintSQL(SQL* SL)//最好是传指针,保证接口的统一性,传指针的时候记得断言 { if (SL->size == 0) { printf("该顺序表为空.\n"); return; } for (int i = 0; i < SL->size; i++) { printf("%d ", SL->data[i]); } printf("\n"); }
3.10 顺序表的"查找"
要查找顺序表中的某个值,只需要遍历这个顺序表,依次比较即可.(如果数据有重复,该函数只返回第一次遇到的目标值)
//查找函数 //查找成功返回元素的下标. //查找失败,返回-1.(因为下标不可能为负数). int Find(SQL SL, DataType x) { for (int i = 0; i < SL.size; i++) { if (SL.data[i] == x) { return i; } } //遍历完顺序表都没找到时. return -1; }
3.11 顺序表的"销毁"
顺序表的销毁及其简单.
1.将data指针释放并置空.
2.将capacity和size设置为0.
//顺序表的销毁后记得要将顺序表置空,该函数不会置空操作. void DestorySQL(SQL* SL) { assert(SL); free(SL->data); SL->data = NULL; SL->size = 0; SL->capacity = 0; }
