顺序表的构造及功能
定义
顺序表是一种随机存储都结构，其特点是表中的元素的逻辑顺序与物理顺序相同。
假设线性表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.h"void 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.h"int 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");
}