成都php网站建设工程师,适合seo软件,四川大学毕业设计网站,天津房价定义顺序表是一种随机存储都结构#xff0c;其特点是表中的元素的逻辑顺序与物理顺序相同。假设线性表L存储起始位置为L(A)#xff0c;sizeof(ElemType)是每个数据元素所占的存储空间的大小#xff0c;则线性表L所对应的顺序存储如下图。顺序表的优缺点优点#xff1a;随机…定义顺序表是一种随机存储都结构其特点是表中的元素的逻辑顺序与物理顺序相同。假设线性表L存储起始位置为L(A)sizeof(ElemType)是每个数据元素所占的存储空间的大小则线性表L所对应的顺序存储如下图。顺序表的优缺点优点随机存储表中的任意元素其存储位置可以用一个简单、直观的公式来表示。存储密度高每个结点只存储数据元素。缺点在做插入或删除元素时需要移动大量元素。操作相对复杂必然导致空间的浪费。静态顺序表的构建在静态分配时由于数组的大小和空间事先已经固定好一旦空间占满再加入新的数据就会产生溢出进而导致进程崩溃。#define MaxSize 100 //顺序表可能达到的最大长度
typedef int ElemType;
typedef struct{ElemType data[MaxSize]; //顺序表的元素int length; //当前的长度
}List; //顺序表的类型定义注意线性表中元素的位置是从1开始的而数组中的元素的下标是从0开始的。动态顺表的构建#define MaxSize 100 //顺序表可能达到的最大长度
typedef int ElemType;
typedef struct{ElemType* data; //存储空间的基址int length; //当前的长度
}List; //顺序表的结构类型为ListC的初始动态分配语句list.data (ElemType*)malloc(sizeof(ElemType)*MaxSize); //动态开辟空间 c语言C的初始动态分配语句list.data new ElemType[MaxSize]; //动态开辟空间 (c)注意动态分配并不是链式存储它同样属于顺序存储结构物理结构没有变化依然是随机存储方式只是分配的空间大小可以在运行时动态决定。动态顺序表的常见操作插入插入新元素的图解void Insert(List *list, int index, int value){ //插入(在第index位置插入value)if (index 1 || index list-length 1){ //判断范围是否有效printf(插入失败位置输入错误\n);return;}if (list-length MaxSize){ //空间已满无法插入printf(插入失败顺序表已满\n);return;}for (int i list-length; i index; i--){ //将第index个元素及之后的元素后移list-data[i] list-data[i - 1];}list-data[index - 1] value; //将位置index放入valuelist-length; //线性表长度加一printf(插入成功\n);return;
}线性表插入算法的平均时间复杂度为O(N)。取值根据下标来查找元素void GetElem(List list, int index){ //取值(用下标找元素)if (index 0 index list.length){printf(要查找的第%d个元素是%d\n, index, list.data[index - 1]);}else{printf(输入的值有误\n);}
}查找根据所给的元素来遍历顺序表来寻找void LocateElem(List list, int value){ //查找(用值找下标)for (int i 0; i list.length; i){if (value list.data[i]){printf(%d是本表中的第%d元素\n, value, i 1);return;}}printf(找不到该元素\n);return;
}线性表按值查找算法的平均时间复杂度为O(N)。删除删除元素的图解void Delete(List *list, int index){ //删除(删除指定的第几个元素)if (index 1 || index list-length) { //判断index的范围是否有效printf(删除失败输入的数值有误\n);return;}for (int i index - 1; i list-length - 1; i){ //将第index个位置后的元素前移list-data[i] list-data[i 1];}list-length--; //线性表长度减一printf(删除成功\n);return;
}线性表删除算法的平均时间复杂度为O(N)。销毁void Clear(List *list){ //销毁list-length 0; //将顺序表的长度设为0free(list-data); //释放malloc申请的空间printf(顺序表已销毁\n);
}划分已第一个元素为界比它小的元素放在它的前面比它大的元素放在它的后面void ListSort(List *list){ //划分(已第一个元素为界前面比它小后面比它大)int i 0, j 0;int temp, k;temp list-data[0];for (i 1; i list-length; i){if (temp list-data[i]){k list-data[i];for (j i; j 0; j--){list-data[j] list-data[j - 1];}list-data[0] k;}}printf(划分成功\n);return;
}单值化单值化类似与去掉顺序表中重复的元素void DeleteSame(List *list){ //单值化(去掉重复的元素)int i 0;while (i list-length){for (int j i 1; j list-length; j)while (list-data[i] list-data[j]){for (int k j; k list-length; k)list-data[k] list-data[k 1];list-length--;}i;}printf(单值化完成\n);return;
}源码SeqList.h#include stdio.h
#include windows.h
#include malloc.h#define MaxSize 100
typedef int ElemType;
typedef struct{ElemType* data; //动态顺序表int length;
}List;void menu();
void PutList();
void GetElem();
void LocateElem();
void Insert();
void Delete();
void DeleteSame();
void ListSort();
void Clear();SeqList.c#include SeqList.hvoid PutList(List list){ //输出(遍历线性表)for (int i 0; i list.length; i){printf(%d , list.data[i]);}printf(\n);
}void GetElem(List list, int index){ //取值(用下标找元素)if (index 0 index list.length){printf(要查找的第%d个元素是%d\n, index, list.data[index - 1]);}else{printf(输入的值有误\n);}
}void LocateElem(List list, int value){ //查找(用值找下标)for (int i 0; i list.length; i){if (value list.data[i]){printf(%d是本表中的第%d元素\n, value, i 1);return;}}printf(找不到该元素\n);return;
}void Insert(List *list, int index, int value){ //插入(在第index位置插入value)if (index 1 || index list-length 1){printf(插入失败位置输入错误\n);return;}if (list-length MaxSize){printf(插入失败顺序表已满\n);return;}for (int i list-length; i index; i--){list-data[i] list-data[i - 1];}list-data[index - 1] value;list-length;printf(插入成功\n);return;
}void Delete(List *list, int index){ //删除(删除指定的第几个元素)if (index 1 || index list-length) {printf(删除失败输入的数值有误\n);return;}for (int i index - 1; i list-length - 1; i){list-data[i] list-data[i 1];}list-length--;printf(删除成功\n);return;
}void DeleteSame(List *list){ //单值化(去掉重复的元素)int i 0;while (i list-length){for (int j i 1; j list-length; j)while (list-data[i] list-data[j]){for (int k j; k list-length; k)list-data[k] list-data[k 1];list-length--;}i;}printf(单值化完成\n);return;
}void ListSort(List *list){ //划分(已第一个元素为界前面比它小后面比它大)int i 0, j 0;int temp, k;temp list-data[0];for (i 1; i list-length; i){if (temp list-data[i]){k list-data[i];for (j i; j 0; j--){list-data[j] list-data[j - 1];}list-data[0] k;}}printf(划分成功\n);return;}void Clear(List *list){ //销毁list-length 0;free(list-data);printf(顺序表已销毁\n);
}void menu(){ //菜单printf(顺序表操作 P-输出 G-取值 L-查找 I-插入 D-删除 S-单值化 F-划分 X-销毁 Q-退出 \n);
}Test.c#include SeqList.hint main(){List list;list.data (ElemType*)malloc(sizeof(ElemType)*MaxSize); //动态开辟空间 c语言//list.data new ElemType[MaxSize]; //动态开辟空间 (c)printf(线性表中元素的个数);int n 0;scanf(%d, n);list.length n;printf(请输入元素);for (int i 0; i n; i){int t 0;//cin list.data[i]; //c输入scanf(%d, t);list.data[i] t;}while (1){menu();char key;//cin key; //c输入int t 0;scanf(%c, key);switch (key){case P:PutList(list); //输出break;case G:printf(要查找第几个元素);scanf(%d, t);GetElem(list,t); //取值break;case L:printf(要查找元素的值为);scanf(%d, t);LocateElem(list,t); //查找break;case I:printf(输入要插入的位置和数值);int index, value;scanf(%d %d, index,value);Insert(list, index, value); //插入break;case D:printf(输入要删除第几个元素);scanf(%d, t);Delete(list, t); //删除break;case S:DeleteSame(list); //单值化break;case F:ListSort(list); //划分break;case X:Clear(list); //销毁break;case Q:exit(0); //退出break;}}system(pause);
}
