数据结构与算法

2024-05-17 15:40| 来源: 网络整理| 查看: 265

1. 顺序表的原理以及实现:

1.1 什么是顺序表：

顺序表是在计算机内存中以数组的形式保存的线性表，顺序表是简单的一种线性结构，逻辑上相邻的数据在计算机内的存储位置也是相邻的，可以快速定位第几个元素，中间不允许有空值，插入、删除时需要移动大量元素。

1.2 什么是线性表：

线性表是从逻辑结构的角度来说的，除了头和尾之外，它的每一个元素都只有一个前驱元素和一个后驱元素。各种队列（单向、双向、循环队列），栈等都是线性表的不同例子。而本文题目的顺序表也是线性表的一种。

1.3 顺序表与链表的区别：

首先，顺序表与链表均属于线性表，只是在逻辑结构和存储方式上有所不同。

顺序表：线性表采用顺序存储的方式存储就称之为顺序表，顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。

链表：线性表采用指针链接的方式存储就称之为链表。

1.4 线性表与数组的区别：

线性表是从逻辑结构的角度来说的，而数组是从物理存贮的角度来说的，线性表可以用数组存贮也可以用链表来存贮。同样的队列和栈也可以用数组和链表存贮，各有利弊。根据具体情况灵活选择。

在C语言中，数组长度不可变，线性表长度是动态可变的。

1.5 顺序表的三个要素：用elems 记录存储位置的基地址分配一段连续的存储空间size 用length 记录实际的元素个数，即顺序表的长度

结构体定义

#define MAX_SIZE 100 struct _SqList { ElemType *elems; // 顺序表的基地址 int length; // 顺序表的长度 int size; // 顺序表总的空间大小 }

顺序表的初始化

1 #define MAX_SIZE 100 2 typedef struct 3 { 4 int* elems; 　　// 顺序表的基地址 5 int length; 　　// 顺序表的长度 6 int size; 　　　　// 顺序表的空间 7 }SqList; 8 9 bool initList(SqList& L)　　　　 //构造一个空的顺序表L 10 { 11 L.elems = new int[MAX_SIZE]; //为顺序表分配Maxsize 个空间 12 if (!L.elems) return false; //存储分配失败 13 L.length = 0; //空表长度为0 14 L.size = MAX_SIZE; 15 return true; 16 }

2. 顺序表添加元素: 1 bool listAppend(SqList &L, int e) 2 { 3 　　if(L.length==MAX_SIZE) return false; //存储空间已满 4 　　L.elems[L.length] = e; 5 　　L.length++; 　　　　　　　　　　　　　　//表长增1 6 　　return true; 7 }

3. 顺序表插入元素 1 bool listInsert(SqList& L, int i, int e) 2 { 3 if (i < 0 || i >= L.length)return false; //i 值不合法 4 if (L.length == MAX_SIZE) return false; //存储空间已满 5 6 for (int j = L.length - 1; j >= i; j--) 7 { 8 L.elems[j + 1] = L.elems[j]; //从最后一个元素开始后移，直到第i 个元素后移 9 } 10 11 L.elems[i] = e; //将新元素e 放入第i 个位置 12 L.length++; //表长增1 13 14 return true; 15 }

4. 顺序表删除元素 1 bool listDelete(SqList& L, int i) 2 { 3 if (i < 0 || i >= L.length) return false; //不合法 4 if (i == L.length - 1) //删除最后一个元素，直接删除 5 { 6 L.length--; 7 return true; 8 } 9 for (int j = i; j < L.length - 1; j++) 10 { 11 L.elems[j] = L.elems[j + 1]; //被删除元素之后的元素前移 12 } 13 L.length--; 14 15 return true; 16 }

5. 顺序表销毁 1 void destroyList(SqList& L) 2 { 3 if (L.elems) delete[]L.elems; //释放存储空间 4 L.length = 0; 5 L.size = 0; 6 }

6. 完整实现 1 #include 2 3 using namespace std; 4 #define MAX_SIZE 100 5 6 typedef struct 7 { 8 int* elems; // 顺序表的基地址 9 int length; // 顺序表的长度 10 int size; // 顺序表的空间 11 }SqList; 12 13 bool initList(SqList& L) //构造一个空的顺序表L 14 { 15 L.elems = new int[MAX_SIZE]; //为顺序表分配Maxsize 个空间 16 if (!L.elems) return false; //存储分配失败 17 L.length = 0; //空表长度为0 18 L.size = MAX_SIZE; 19 return true; 20 } 21 22 /* 23 bool getElem(SqList &L,int i,int &e) 24 { 25 //防御性检查 26 if (iL.length) return false; 27 e=L.elems[i-1]; //第i-1 的单元存储着第i 个数据 28 return true; 29 } 30 */ 31 32 bool listAppend(SqList& L, int e) 33 { 34 if (L.length == MAX_SIZE) return false; //存储空间已8满979438401111 35 L.elems[L.length] = e; 36 L.length++; //表长增1 37 return true; 38 } 39 40 bool listInsert(SqList & L, int i, int e) 41 { 42 if (i < 0 || i >= L.length)return false; //i 值不合法 43 if (L.length == MAX_SIZE) return false; //存储空间已满 44 for (int j = L.length - 1; j >= i; j--) 45 { 46 L.elems[j + 1] = L.elems[j]; //从最后一个元素开始后移，直到第i 个元素后移 47 } 48 L.elems[i] = e; //将新元素e 放入第i 个位置 49 L.length++; //表长增1 50 return true; 51 } 52 53 bool listDelete(SqList & L, int i) 54 { 55 if (i < 0 || i >= L.length) return false; //不合法 56 if (i == L.length - 1) //删除最后一个元素，直接删除 57 { 58 L.length--; 59 return true; 60 } 61 for (int j = i; j < L.length - 1; j++) 62 { 63 L.elems[j] = L.elems[j + 1]; //被删除元素之后的元素前移 64 } 65 L.length--; 66 return true; 67 } 68 69 void listPrint(SqList & L) 70 { 71 cout count; 101 for (int i = 0; i < count; i++) { 102 cout > e; 104 if (listAppend(list, e)) { 105 cout > i >> e; 117 if (listInsert(list, i, e)) { 118 cout > i; 129 if (listDelete(list, i)) { 130 cout

【本文地址】

公司简介

联系我们