本文共 10615 字,大约阅读时间需要 35 分钟。
线性表是具有相同数据类型的 n 个数据元素的有限序列
,n 即为表长。L=(a1,a2,a3,...,an)
,其中 a1 为第一个元素称为表头元素,an 为最后一个元素称为表尾元素;除表头元素外,线性表的每个元素有且仅有一个直接前驱
,除表尾元素,每个元素有且只有一个直接后继
。一个数据结构的基本操作是指其最核心、最基本的操作
,其他操作都可以通过这些基本操作的有限次复合来完成。线性表的基本操作有增上改查、排序以及求表长、初始化线性表等。 1)create():构造一个空的线性表。 2)InitList():初始化线性表。 3)getLength():返回线性表表长。 4)getValue():返回指下标的值。 5)getIndex():返回指定值的下标。 6)add():线性表追加元素。 7)Insert():线性表插入元素。 8)Change():修改线性表指定下标元素。 9)DelValue():删除指定值的元素。 10)DelIndex():删除指定下标的元素。 11)Sort():排序元素。 12)Display():输出线性表元素。 13)Empty():判断线性表是否为空。 14)Destroy():销毁线性表。#pragma once#includeusing namespace std;constexpr auto Initsize = 20;typedef struct { int* data; int Maxsize, length;}SeqList;// 以 20 为长度创建线性表,数组最大长度由参数指定SeqList create(int maxsize = 20){ SeqList list; list.data = new int[Initsize]; list.length = 20; list.Maxsize = maxsize; return list;}// 初始化线性表void initList(SeqList& list, int arr[], int len){ if (len <= list.length) { for (int i = 0; i < len; i++) { list.data[i] = arr[i]; } list.length = len; } else { if (list.Maxsize >= len) { delete[] list.data; list.data = new int[len]; list.length = len; for (int i = 0; i < len; i++) { list.data[i] = arr[i]; } } else { cout << "Error! The length of the arr is so long that the Maxsize of sqelist could not hold."; } }}// 追加元素void AddValue(SeqList& list, int value){ list.data[list.length] = value; list.length += 1;}// 插入元素void InsertValue(SeqList& list, int value, int index){ if (index > list.length) { cout << "Error! the index is invaild!" << endl;; return; } if (index == list.length) AddValue(list, value); else { for (int i = list.length; i >= index - 1; i--) { list.data[i] = list.data[i - 1]; } list.data[index - 1] = value; list.length += 1; }}// 查找元素int getValue(SeqList list, int index){ if (index >= list.length) return NAN; return list.data[index - 1];}// 查找下标int getIndex(SeqList list, int value){ int i = 0; for (i = 0; i < list.length; i++) if (list.data[i] == value) break; if (i >= list.length) return NAN; return i + 1;}int getPreByValue(SeqList list, int value){ int cur = getIndex(list, value); if (cur == 0) { cout << "The value is no exist!" << endl; return NAN; } return list.data[cur - 2];}int getLastByVlue(SeqList list, int value){ int cur = getIndex(list, value); if (cur == 0) { cout << "The value is no exist!" << endl; return NAN; } return list.data[cur];}// 修改指定下标的元素void change(SeqList& list, int index, int value){ if (index > list.length) { cout << "Error! the index is invaild!"; return; } list.data[index - 1] = value;}// 根据元素值删除下标void delValue(SeqList& list, int value){ int cur = getIndex(list, value); if (cur != 0) { for (int i = cur - 1; i < list.length - 1; i++) list.data[i] = list.data[i + 1]; list.length -= 1; } else cout << "What you want delete is no exist in this seqList!" << endl;}// 根据下标删除元素void delIndex(SeqList& list, int index){ if (index > list.length) { cout << "Error! The index is invalid!" << endl; return; } for (int i = index - 1; i < list.length - 1; i++) { list.data[i] = list.data[i + 1]; } list.length -= 1;}// 升序排序void AscSort(SeqList& list){ for (int i = 0; i < list.length; i++) for (int j = i + 1; j < list.length; j++) { if (list.data[i] > list.data[j]) { int temp = list.data[i]; list.data[i] = list.data[j]; list.data[j] = temp; } }}// 降序排序void DesSort(SeqList& list){ for (int i = 0; i < list.length; i++) for (int j = i + 1; j < list.length; j++) { if (list.data[i] < list.data[j]) { int temp = list.data[i]; list.data[i] = list.data[j]; list.data[j] = temp; } }}void display(SeqList list){ for (int i = 0; i < list.length; i++) cout << list.data[i] << " "; cout << endl;}bool empty(SeqList list){ if (list.length == 0) return true; return false;}void destroy(SeqList& list){ delete[] list.data; list.length = 0; list.Maxsize = 0;}
顺序表指采用顺序存储结构进行实现的线性表。
,即在内存中用一组连续的存储单元存储线性表中的数据元素,从而使逻辑上相邻的元素在物理位置上也相邻,即彪总的元素的逻辑顺序与物理顺序相同,这也是顺序表的特点。静态分配和动态分配
。ElemType data[size]
。ElemType *data
list.data = new ElemType[initsize];
增删改查与遍历
,这是所有顺序表的其他诸如排序等操作的基础。追加和插入
。最显著的区别就是追加元素不影响已有元素的下标,而插入则会影响插入位置之后的元素的下标
。O(n)
。插入操作移动节点的平均次数为: 判断下标是否合法的语句
。O(n)
,因为需要将指定下标后的元素都迁移一位,也就是说顺序表的删除就是用后一个存储单元中的内容覆盖当前存储单元的内容,所以移动元素之后一定记得更新顺序表的长度值,即更新为原来长度值减一。2O(n)
,因为进行删除之前还需要遍历顺序表元素以进行比较操作,从而找出指定值的元素的位置,然后再将该位置之后的元素都迁移一位。以下的改和查步骤都需要这一步
。给出指定元素的下标,然后更改该元素的值
。由于顺序表的特性,可以直接根据下标确定元素的物理位置,因此此操作的时间复杂度都是常数阶。根据元素值找出下标
。其具体实现就是元素遍历和元素值比较
,也即是说要获得指定值的下标,需要从顺序表表头元素开始到表尾元素结束,将每个元素都与指定值比较,若是第一次遇到相等的,就返回该下标。O(1)
。O(n)
。O(n)
。冒泡排序
,该算法的原理就是”打擂台“,将当前元素与之后的每一元素进行大小比较,在降序排序的情况下,若其后的元素大于自身则与其互换值。bool DelMin(SeqList& L, int& value){ if (L.length == 0) { cout << "顺序表为空!" << endl; return false; } value = L.data[0]; int pos = 0; for (int i = 1; i < L.length; i++) { if (L.data[i] < value) { value = L.data[i]; pos = i; } } L.data[pos] = L.data[L.length - 1]; L.length--; return true;}
void reverse(SeqList& L){ int temp; for (int i = 0; i < L.length / 2; i++) { temp = L.data[i]; L.data[i] = L.data[L.length - i - 1]; L.data[L.length - i - 1] = temp; }}
void delAllX(SeqList& l, int x){ // 记录不等于 x 的元素个数 int k = 0; for (int i = 0; i < l.length; i++) { if (l.data[i] != x) { l.data[k] = l.data[i]; k++; } } l.length = k;}
bool DelInS2T(SeqList& l, int s, int t){ int i, k = 0; if (l.length == 0 || s >= t) return false; for (i = 0; i < l.length; i++) { if (l.data[i] >= s && l.data[i] <= t) k++; else l.data[i - k] = l.data[i]; } l.length -= k; return true;}
bool DeleteSame(SeqList& l){ if (l.length == 0) return false; // 存储第一个不相同的元素 int i; // 工作指针 int j; for (i = 0, j = 1; j < l.length; j++) { // 查找下一个与上一个元素值不同的元素 if (l.data[i] != l.data[j]) { // 找到后,将元素前移 l.data[++i] = l.data[j]; } } l.length = i + 1; return true;}
bool merge(SeqList A, SeqList B, SeqList& C){ if (A.length + B.length > C.length) return false; int i = 0, j = 0, k = 0; while (i < A.length && j < B.length) { if (A.data[i] <= B.data[j]) C.data[k++] = A.data[i++]; else C.data[k++] = B.data[j++]; } while (i < A.length) C.data[k++] = A.data[i++]; while (j < B.length) C.data[k++] = B.data[j++]; return true;}
void SearchExchangeInsertASC(SeqList& l, int x){ // 顺序表下界 int low = 0; // 顺序表上界 int high = l.length - 1; int mid; while (low <= high) { mid = (low + high) / 2; if (l.data[mid] == x)break; else if (l.data[mid] < x)low = mid + 1; else if (l.data[mid] > x) high = mid - 1; } if (l.data[mid] == x && mid != l.length - 1) { int t = l.data[mid]; l.data[mid] = l.data[mid + 1]; l.data[mid + 1] = t; } if (low > high) { int i = l.length - 1; for (; i > high; i--)l.data[i + 1] = l.data[i]; l.data[i + 1] = x; l.length += 1; }}
void SearchExchangeInsertDSC(SeqList& l, int x){ // 顺序表下界 int low = 0; // 顺序表上界 int high = l.length - 1; int mid; while (low <= high) { mid = (low + high) / 2; if (l.data[mid] == x)break; else if (l.data[mid] < x)high = mid - 1; else if (l.data[mid] > x) low = mid + 1; } if (l.data[mid] == x && mid != l.length - 1) { int t = l.data[mid]; l.data[mid] = l.data[mid + 1]; l.data[mid + 1] = t; } if (low > high) { int i = l.length - 1; for (; i > high; i--)l.data[i + 1] = l.data[i]; l.data[i + 1] = x; l.length += 1; }}
void reverse(int R[], int from, int to){ int i, t; for (i = 0; i < (to - from + 1) / 2; i++) { t = R[from + i]; R[from + i] = R[to - i]; R[to - i] = t; }}void converse(int R[], int n, int p){ reverse(R, 0, p - 1); reverse(R, p, n - 1); reverse(R, 0, n - 1);}
int MSearch(int A[], int B[], int n){ // 分别表示序列A和B的首位数、末位数、中位数 int s1 = 0, d1 = n - 1, m1, s2 = 0, d2 = n - 1, m2; while (s1 != d1 || s2 != d2) { m1 = (s1 + d1) / 2; m2 = (s2 + d2) / 2; if (A[m1] == B[m2]) return A[m1]; if (A[m1] < B[m2]) { if ((s1 + d1) % 2 == 0) { s1 = m1; d2 = m2; } else { s1 = m1 + 1; d2 = m2; } } if (A[m1] > B[m1]) { if ((s2 + d2) % 2 == 0) { d1 = m1; s2 = m2; } else { d1 = m1; s2 = m2 + 1; } } } return A[s1] < B[s2] ? A[s1] : B[s2];}
int Majority(int A[], int n){ // t 用于存储候选主元素 int t; int i; // count 用于计数 int count = 1; t = A[0]; for (i = 1; i < n; i++) { if (A[i] == t) count++; else { if (count > 0) count--; else { t = A[i]; count = 1; } } } if (count > 0) { for (i = count = 0; i < n; i++) { if (A[i] == t) count++; } } if (count > n / 2) return t; else return -1;}
int findMissMin(int a[], int n){ int i; // 标记数组 int* b = new int[n]; memset(b, 0, sizeof(int) * n); for (i = 0; i < n; i++) if (a[i] > 0 && a[i] <= n) b[a[i] - 1] = 1; for (i = 0; i < n; i++) if (b[i] == 0)break; return i + 1;}
转载地址:http://pqqgn.baihongyu.com/