顺序表的基本概念与基本操作（一） |
您所在的位置：网站首页 › 动态顺序表的实现实验报告 › 顺序表的基本概念与基本操作（一） |
顺序表的基本概念与基本操作（一）
|
欢迎各位大佬观看此文
1.*线性表*2.*顺序表*2.1概念与结构2.1.1. 静态顺序表：使用定长数组存储元素。2.1.2 动态顺序表：使用动态开辟的数组进行存储。
阅读建议：
该文详细介绍了静态顺序表和动态顺序表的相关知识与操作代码，适合基础薄弱的同学们应先观看静态顺序表，在此基础之上可以学习动态顺序表的相关知识。
1.线性表
线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的， 线性表在物理上存储时，通常以数组和链式结构的形式存储。
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存 储。在数组上完成数据的增删查改。 顺序表一般可以分为： 2.1.1. 静态顺序表：使用定长数组存储元素。 #include #include #include #define MAXSIZE 100//使用宏可以方便更改数组空间 //定义结构体 typedef int datatype; typedef struct { datatype data[MAXSIZE];//通过静态的数组存储数据 int length;//标记顺序表的长度 }SeqList, * PSeqList; //创建一个顺序表，入口参数无，返回一个指向顺序表的指针，指针值为零表示分配空间失败 PSeqList Init_SeqList(void) { PSeqList PL; PL = (PSeqList)malloc(sizeof(SeqList)); if (PL) PL->length = 0; else { printf("内存分配失败\n"); exit(-1); } return (PL); } //销毁顺序表，入口参数：为要销毁的顺序表指针地址，无返回值 void Destroy_SeqList(PSeqList* PL) { if (*PL) free(*PL); *PL = NULL; printf("顺序表已销毁\n"); return; } //数据输入 PSeqList Input_SeqList(PSeqList L) { int i; for (i = 1; i data[i - 1] = i + 3; L->length = i - 1; return L; } //读取顺序表的当前长度 int Length_SeqList(PSeqList L) { if (!L) { printf("无PL指针，退出程序\n"); exit(-1); } return (L->length); } //在顺序表上检索，入口参数为顺序表，检索元素，返回元素位置，0表示查找失败 int Location_SeqList(PSeqList L, int x) { int i = 0; while (i length && L->data[i] != x) i++; if (i >= L->length) return 0; else return (i + 1); } /*在顺序表的第i个元素之前插入x，入口参数为顺序表指针，插入位置，插入元素， 返回标志，1表示成功，0标志插入位置不合法，-1表示溢出，-2表示不存在*/ int Insert_SeqList(PSeqList PL, int i, int x) { if (!PL) { printf("表不存在"); return -2; } else if (i = PL->length) { printf("插入位置不合法"); return 0; } else if (PL->length >= MAXSIZE) { printf("溢出"); return -1; } else { for (int j = PL->length - 1; j >= i; j--) { PL->data[j + 1] = PL->data[j]; } PL->data[i - 1] = x; PL->length++; return 1; } //请同学们自己实现 } //删除顺序表第i个元素，入口参数：顺序表指针，删除元素位置，返回标志1表示成功，0表示删除位置不合法，-1表示表不存在 int Delete_SeqList(PSeqList PL, int i) { if (!PL) { printf("表不存在"); return -1; } else if (iPL->length) { printf("删除位置不合法"); return 0; } else { for (int j = i; j length; j++) { PL->data[j - 1] = PL->data[j]; } PL->length--; return 1; } } //顺序表整体输出 void Output_SeqList(PSeqList PL) { int i; for (i = 0; i length; i++) printf("%3d", PL->data[i]); printf("\n顺序表当前的长度:%d\n", Length_SeqList(PL)); } int main(void) { PSeqList PL; PL = Init_SeqList(); PL = Input_SeqList(PL); printf("获取顺序表当前的长度为：%d\n", Length_SeqList(PL)); printf("数据10在顺序表中的位置是：%d\n", Location_SeqList(PL, 10)); Output_SeqList(PL); Insert_SeqList(PL,4,29); Insert_SeqList(PL,-1,34); Insert_SeqList(PL,7,34); Insert_SeqList(PL,13,23); Output_SeqList(PL); Delete_SeqList(PL,3); printf("删除第3个数后的结果:\n"); Output_SeqList(PL); Delete_SeqList(PL,4); printf("删除第4个数后的结果:\n"); Output_SeqList(PL); Destroy_SeqList(&PL); return 0; }缺点：由于创建数组时只能创建固定的空间，从而造成了创建多了浪费空间，创建少了则空间不够的尴尬局面，故此静态顺序表的使用往往存在着一定的局限性，故此接下来我们会介绍动态顺序表来解决这样的问题 2.1.2 动态顺序表：使用动态开辟的数组进行存储。基本知识讲解 通过引用库函数来调用malloc函数来申请内存，从而实现用多少而申请多少的目的。
动态顺序表基本操作的实现 以下是动态顺序表的代码实现，其中包含的基本操作有： 1.Init_SeqList(SeqList* S)顺序表初始化 2.Destroy_SeqList(SeqList* S)顺序表的销毁 3.SeqList_check(SeqList* S)顺序表已满的判断 4.SeqList_PushBack(SeqList* S, datatype x)顺序表的尾插 5.SeqList_print(SeqList* S)顺序表的遍历 #define _CRT_SECURE_NO_WARNINGS #include #include //定义结构体 typedef int datatype; typedef struct { datatype* a; int length;//存储的有效数据的个数 int capacity;//容量 }SeqList, * PseqList; //奇思妙想:是否可以用柔性数组呢？(留给读者自行思考) //初始化顺序表 void Init_SeqList(SeqList* S) { S->a = (datatype*)malloc(sizeof(datatype) * 4); if (S->a == NULL) { perror("malloc fail"); return; } S->length = 0; S->capacity = 4; } //销毁链表 void Destroy_SeqList(SeqList* S) { free(S->a); S->a = NULL; S->length = 0; S->capacity = 0; } //判断数据个数是否超过容量大小 void SeqList_check(SeqList* S) { if (S->length >= S->capacity) { datatype* tmp = (datatype*)malloc(sizeof(datatype) * S->capacity * 2); if (tmp == NULL) { perror("realloc fail"); return; } S->a = tmp; S->capacity *= 2; } } //顺序表的遍历 void SeqList_print(SeqList* S) { for (int i = 0; i length; i++) { printf("%d", S->a[i]); } printf("\n"); } //链表的尾插 void SeqList_PushBack(SeqList* S, datatype x) { SeqList_check(S); S->a[S->length] = x; S->length++; } int main() { SeqList S; int x = 5; Init_SeqList(&S); SeqList_PushBack(&S, x); SeqList_print(&S); Destroy_SeqList(&S); return 0; }对顺序表的总结： 1、随机访问，即可以在 O(1) 时间内找到第 i 个元素。（代码实现：data[i-1];静态分配、动态分配都一样 ） 2、存储密度高，每个节点只存储数据元素 3、拓展容量不方便（即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高） 4、插入、删除操作不方便，需要移动大量元素. 感谢每位读者的观看，如有错误和建议可以与作者交流。 |
【本文地址】
今日新闻 |
推荐新闻 |