顺序表的构造及功能

定义

顺序表是一种随机存储都结构，其特点是表中的元素的逻辑顺序与物理顺序相同。

假设线性表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;               //顺序表的结构类型为List

C的初始动态分配语句

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");
}