上海网站建设好处,百度怎么收录自己的网站,零壹网站建设,汇款账号 网站建设各位CSDN的uu们你们好呀#xff0c;今天小雅兰的内容是数据结构与算法里面的顺序表啦#xff0c;在我看来#xff0c;数据结构总体上是一个抽象的东西#xff0c;关键还是要多写代码#xff0c;下面#xff0c;就让我们进入顺序表的世界吧 线性表
顺序表 线性表 线性表今天小雅兰的内容是数据结构与算法里面的顺序表啦在我看来数据结构总体上是一个抽象的东西关键还是要多写代码下面就让我们进入顺序表的世界吧 线性表
顺序表 线性表 线性表linear list是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构常见的线性表顺序表、链表、栈、队列、字符串... 线性表在逻辑上是线性结构也就说是连续的一条直线。但是在物理结构上并不一定是连续的 线性表在物理上存储时通常以数组和链式结构的形式存储。 顺序表 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储。在数组上完成数据的增删查改。 顺序表就是数组但是在数组的基础上它还要求数据是从头开始连续存储的不能跳跃间隔 顺序表一般可以分为 静态顺序表使用定长数组存储元素。 #define _CRT_SECURE_NO_WARNINGS 1
#define N 7
#includeSeqList.h
typedef int SLDateType;
typedef struct SeqList
{SLDateType arr[N];//定长数组size_t size;//表示数组中存储了多少数据
}SL; 动态顺序表使用动态开辟的数组存储。 #define _CRT_SECURE_NO_WARNINGS 1
#define N 7
#includeSeqList.h
typedef int SLDateType;
typedef struct SeqList
{SLDateType* arr;//指向动态开辟的数组size_t size;//表示数组中存储了多少数据size_t capicity;//数组实际能存储数据的空间容量是多大
}SL; 静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了空间开多了浪费开少了不够用。所以现实中基本都是使用动态顺序表根据需要动态的分配空间大小所以下面我们实现动态顺序表。 在这里所有函数命名风格都是跟着STL走的方便小雅兰日后的学习 顺序表的初始化 void SeqListInit(SL* ps)//顺序表的初始化
{ps-arr NULL;ps-size ps-capacity 0;
}注意在这里不可以使用传值调用的方式只能使用传址调用的方式 void SeqListInit(SL ps)//顺序表的初始化
{ps.arr NULL;ps.size ps.capacity 0;
}万万不能使用这样的方式初始化因为在函数传参的时候形参是实参的一份临时拷贝对形参的修改并不会影响实参 顺序表的打印 void SeqListPrint(SL* ps)//顺序表的打印
{int i 0;for (i 0; i ps-size; i){printf(%d , ps-arr[i]);}printf(\n);
} 扩容 void SeqListCheckCapacity(SL* ps)//检查空间如果满了进行扩容
{//如果没有空间或者空间不足那么我们就扩容if (ps-size ps-capacity){int newcapacity ps-capacity 0 ? 4 : ps-capacity * 2;SLDateType* tmp (SLDateType*)realloc(ps-arr, newcapacity * sizeof(SLDateType));if (tmp NULL){printf(realloc fail!\n);exit(-1);}ps-arr tmp;ps-capacity newcapacity;}
} 顺序表销毁 void SeqListDestroy(SL* ps)//顺序表销毁
{free(ps-arr);ps-arr NULL;ps-capacity ps-size 0;
} 尾插 void SeqListPushBack(SL* ps, SLDateType x)//尾插
{SeqListCheckCapacity(ps);ps-arr[ps-size] x;ps-size;
} 尾删 void SeqListPopBack(SL* ps)//尾删
{assert(ps-size 0);ps-size--;
} 头插 void SeqListPushFront(SL* ps, SLDateType x)//头插
{SeqListCheckCapacity(ps);//挪动数据int end ps-size - 1;while (end 0){ps-arr[end 1] ps-arr[end];end--;}ps-arr[0] x;ps-size;
} 头删 void SeqListPopFront(SL* ps)//头删
{assert(ps-size 0);//挪动数据int begin 0;while (begin ps-size-1){ps-arr[begin] ps-arr[begin1];begin;}ps-size--;
} 另一种写法 void SeqListPopFront(SL* ps)//头删
{assert(ps-size 0);//挪动数据int begin 1;while (begin ps-size){ps-arr[begin - 1] ps-arr[begin];begin;}ps-size--;
} 顺序表查找 //顺序表查找
//找到了返回x位置的下标没有找到返回-1
int SeqListFind(SL* ps, SLDateType x)
{int i 0;for (i 0; i ps-size; i){if (ps-arr[i] x){return i;}}return -1;
} 指定pos下标位置插入 // 顺序表指定pos下标位置插入x
void SeqListInsert(SL* ps, size_t pos, SLDateType x)
{温柔的写法//if (pos ps-size || pos 0)//{// printf(pos invalid!\n);//}//粗暴的写法assert(pos ps-size || pos 0);SeqListCheckCapacity(ps);//挪动数据int end ps-size - 1;while (end pos){ps-arr[end 1] ps-arr[end];end--;}ps-arr[pos] x;ps-size;
} 然后写出了这个函数的功能之后我们发现可以对之前写的头插和尾插搞一些事情下面我们开始搞事情 头插和尾插 void SeqListPushBack(SL* ps, SLDateType x)//尾插
{SeqListInsert(ps, ps-size, x);
}
void SeqListPushFront(SL* ps, SLDateType x)//头插
{SeqListInsert(ps, 0, x);
} 删除pos位置的数据 //顺序表删除pos位置的数据
void SeqListErase(SL* ps, size_t pos)
{assert(pos ps-size || pos 0);int begin pos 1;while (begin ps-size){ps-arr[begin - 1] ps-arr[begin];begin;}ps-size--;
}写出这个函数的功能之后我们又可以搞事情啦 头删和尾删 void SeqListPopBack(SL* ps)//尾删
{SeqListErase(ps, 0);
}
void SeqListPopFront(SL* ps)//头删
{SeqListErase(ps, ps-size - 1);
}菜单 void menu()
{printf(#############################################\n);printf(\n);printf(###################1.头插#####################\n);printf(\n);printf(###################2.头删#####################\n);printf(\n);printf(###################3.尾插######################\n);printf(\n);printf(###################4.尾删######################\n);printf(\n);printf(###################5.打印#####################\n);printf(\n);printf(###################0.exit#####################\n);printf(\n);printf(##############################################\n);
} 其实最好不要一上来就写菜单先写单元测试菜单不方便调试 测试菜单函数 void MenuTest()
{SL s1;SeqListInit(s1);int input 0;int x;while (input ! -1){menu();scanf(%d, input);switch (input){case 1:printf(请输入你要头插的数据以-1结束);while (x ! -1){SeqListPushFront(s1, x);scanf(%d, x);}break;case 2:SeqListPopFront(s1);break;case 3:printf(请输入你要尾插的数据以-1结束);while (x ! -1){SeqListPushBack(s1, x);scanf(%d, x);}break;case 4:SeqListPopBack(s1);break;case 5:SeqListPrint(s1);break;case 0:printf(退出程序\n);break;default:printf(输入错误请重新输入\n);}}
} 源代码如下
SeqList.h的内容
#pragma once
#includestdio.h
#define _CRT_SECURE_NO_WARNINGS 1
#includestdlib.h
#includeassert.h
#define N 7
typedef int SLDateType;
//顺序表的动态存储
typedef struct SeqList
{SLDateType* arr;//指向动态开辟的数组size_t size;//表示数组中存储了多少数据size_t capacity;//数组实际能存储数据的空间容量是多大
}SL;
//基本增删查改接口
void SeqListInit(SL* ps);//顺序表的初始化
void SeqListPrint(SL* ps);//顺序表的打印
void SeqListCheckCapacity(SL* ps);//检查空间如果满了进行扩容
void SeqListDestroy(SL* ps);//顺序表销毁
void SeqListPushBack(SL* ps, SLDateType x);//尾插
void SeqListPopBack(SL* ps);//尾删
void SeqListPushFront(SL* ps, SLDateType x);//头插
void SeqListPopFront(SL* ps);//头删
//顺序表查找
//找到了返回x位置的下标没有找到返回-1
int SeqListFind(SL* ps, SLDateType x);
//顺序表指定pos下标位置插入x
void SeqListInsert(SL* ps, size_t pos, SLDateType x);
//顺序表删除pos位置的数据
void SeqListErase(SL* ps, size_t pos);SeqList.c的内容
#define _CRT_SECURE_NO_WARNINGS 1
#includeSeqList.h
void SeqListInit(SL* ps)//顺序表的初始化
{ps-arr NULL;ps-size ps-capacity 0;
}
void SeqListPrint(SL* ps)//顺序表的打印
{int i 0;for (i 0; i ps-size; i){printf(%d , ps-arr[i]);}printf(\n);
}
void SeqListCheckCapacity(SL* ps)//检查空间如果满了进行扩容
{//如果没有空间或者空间不足那么我们就扩容if (ps-size ps-capacity){int newcapacity ps-capacity 0 ? 4 : ps-capacity * 2;SLDateType* tmp (SLDateType*)realloc(ps-arr, newcapacity * sizeof(SLDateType));if (tmp NULL){printf(realloc fail!\n);exit(-1);}ps-arr tmp;ps-capacity newcapacity;}
}
void SeqListDestroy(SL* ps)//顺序表销毁
{free(ps-arr);ps-arr NULL;ps-capacity ps-size 0;
}
void SeqListPushBack(SL* ps, SLDateType x)//尾插
{SeqListCheckCapacity(ps);ps-arr[ps-size] x;ps-size;
}
void SeqListPopBack(SL* ps)//尾删
{assert(ps-size 0);ps-size--;
}
void SeqListPushFront(SL* ps, SLDateType x)//头插
{SeqListCheckCapacity(ps);//挪动数据int end ps-size - 1;while (end 0){ps-arr[end 1] ps-arr[end];end--;}ps-arr[0] x;ps-size;
}
void SeqListPopFront(SL* ps)//头删
{assert(ps-size 0);//挪动数据int begin 1;while (begin ps-size){ps-arr[begin - 1] ps-arr[begin];begin;}ps-size--;
}
//顺序表查找
//找到了返回x位置的下标没有找到返回-1
int SeqListFind(SL* ps, SLDateType x)
{int i 0;for (i 0; i ps-size; i){if (ps-arr[i] x){return i;}}return -1;
}
// 顺序表指定pos下标位置插入x
void SeqListInsert(SL* ps, size_t pos, SLDateType x)
{温柔的写法//if (pos ps-size || pos 0)//{// printf(pos invalid!\n);//}//粗暴的写法assert(pos ps-size || pos 0);SeqListCheckCapacity(ps);//挪动数据int end ps-size - 1;while (end pos){ps-arr[end 1] ps-arr[end];end--;}ps-arr[pos] x;ps-size;
}
//顺序表删除pos位置的数据
void SeqListErase(SL* ps, size_t pos)
{assert(pos ps-size || pos 0);int begin pos 1;while (begin ps-size){ps-arr[begin - 1] ps-arr[begin];begin;}ps-size--;
} 好啦小雅兰今天的内容就到这里啦数据结构的的确确是一个麻烦的东西还要加油呀
