2. it
  3. 数据结构顺序表

数据结构顺序表

mac2022-06-30  31

大二开始学习数据结构了 用的是严蔚敏的教材 写点东西做一下巩固和总结，第一次写博客 有人看的话如果发现问题希望能提出来*(´；ω；`)

在学习中代码参考自这里

要实现的功能

创建和初始化1插入和删除元素2顺序表的遍历表是否为空/满3求某位置元素的前驱和后继取某位置的值线性表的清空和销毁求两个线性表的交集和并级4 代码大部分按照自己的想法写的 可能会有不是很好的地方或者不完善的地方 。。。。QAQ == 我是用VS2019写的代码 好几把烦每次都会敲出各种小错误耽误大量时间MLGB #include <iostream> #include <stdlib.h> //提供malloc、realloc、free、exit函数 #define LIST_INIT_SIZE 100 //初始化时的大小 #define LISTINCREASE 10 //顺序表存满后扩充的大小 using namespace std; typedef struct { int *data; int length; //顺序表长度 int listsize; //可以存放的数据数量 }SeqList; int InitList(SeqList* L); //初始化 int InsertList(SeqList* L, int i, int e); //插入 int ListDelete(SeqList* L, int i); //删除 void TraverseList(SeqList* L); //遍历 bool ListEmpty(SeqList* List); //空？ bool ListFull(SeqList* List); //满？ int PriorElem(SeqList* List, int i); //前驱 int NextElem(SeqList* List, int i); //后继 int GetElme(SeqList* List, int i); //获取位置i的元素 返回元素的值 void ClearList(SeqList* List); //清空 void DestroyList(SeqList* List); //销毁 void Union(SeqList *L1, SeqList L2); //求L1∪L2 void Merge(SeqList *L1, SeqList L2); //求L1∩L2 int LocateElem(SeqList L, int e, int Compare(int, int)); //判断表L内的元素和e是否满足compare关系 int Equal(int a, int b); //判定是否相等 int main() { cout<<"数据结构好难"<<endl; int e; SeqList List,List2,List3; InitList(&List); InitList(&List2); InitList(&List3); InsertList(&List, 1, 1); InsertList(&List, 2, 2); InsertList(&List, 3, 3); InsertList(&List, 4, 4); InsertList(&List, 5, 5); InsertList(&List, 6, 6); InsertList(&List2, 1, 4); InsertList(&List2, 2, 5); InsertList(&List2, 3, 6); InsertList(&List2, 4, 7); InsertList(&List2, 5, 8); InsertList(&List2, 6, 9); cout << "List1:" << endl; TraverseList(&List); cout << "List2:" << endl; TraverseList(&List2); //cout << "List1 U List2:" << endl; //Union(&List, List2); //TraverseList(&List); cout << "List1 ∩ List2:" << endl; Merge(&List, List2); TraverseList(&List); return 0; } /*初始化*/ int InitList(SeqList* L) { L->data = (int*)malloc(LIST_INIT_SIZE * sizeof(SeqList)); //分配存储数据的内存空间 if (!(L->data)) { cout << "内存非配失败" << endl; exit(1); } else { L->length = 0; L->listsize = LIST_INIT_SIZE; } return 1; } /*插入*/ int InsertList(SeqList* L, int i, int e) //i为插入位置，e为插入的元素 { if (i > L->listsize + 1 || i < 1) //插入位置是否合适 return 0; int* newbase; int* p, * q; //q为插入位置 if (L->length >= L->listsize) //判断插入时线性表是否已满 { newbase = (int*)realloc(L->data, sizeof(SeqList) * (L->listsize + LISTINCREASE)); if (!newbase) { cout << "内存分派失败" << endl; exit(1); } L->listsize += LISTINCREASE; L->data = newbase; } q = &L->data[i - 1]; //p = &L->data[L->length - 1]; for (p = &L->data[L->length - 1]; p >= q; --p) * q = *(q + 1); *q = e; L->length++; return 1; } /*删除元素*/ int ListDelete(SeqList* L, int i) //i为要删除的元素的位置 { if (i<1 || i>L->length) return 0; int* p, * q; //q为删除位置 q = &L->data[i - 1]; p = &L->data[L->length - 1]; for (++q; q <= p; ++q) * (q - 1) = *q; //删除位置后的元素左移 L->length--; return 1; } /*遍历线性表*/ void TraverseList(SeqList* L) { for (int i = 0; i < L->length; i++) cout << L->data[i] << " "; cout << endl; } /*空和满*/ bool ListEmpty(SeqList* List) { if (List->length == List->listsize) return true; else return false; } bool ListFull(SeqList* List) { if (List->length == 0) return true; else return false; } /*前驱和后继*/ int PriorElem(SeqList* List, int i) { if (i<1 || i>List->length) { cout << "元素位置输入不合法" << endl; return 0; } if (i == 1) { cout << "无前驱" << endl; return 0; } return List->data[i - 2]; } int NextElem(SeqList* List, int i) { if (i<1 || i>List->listsize) { cout << "元素位置输入不合法" << endl; exit(-1); } if (i == List->length) { cout << "无后继" << endl; exit(-1); } return List->data[i]; } /*获取i位置的元素值*/ int GetElme(SeqList* List, int i) { return List->data[i - 1]; } /*清空和销毁*/ void ClearList(SeqList* List) { List->length = 0; cout << "已清空" << endl; } void DestroyList(SeqList* List) { free(List->data); List->data = NULL; List->listsize == 0; List->length = 0; cout << "已销毁" << endl; } /*求并集*/ void Union(SeqList *L1, SeqList L2 ) { int L1_length = L1->length; //这里需要把原始长度进行保存 因为在后面循环里长度会随着插入和删除变化 int L2_length = L2.length; int e; for (int i = 1; i <= L2.length; i++) { e = GetElme(&L2, i); //遍历表L2的值 if (!LocateElem(*L1, e, Equal)) //！L1中是否有和e相等的值？ 若没有则插入 InsertList(L1, L1->length+1, e); } } /*求交集*/ void Merge(SeqList *L1, SeqList L2) //思路是把求并集的函数复制过来然后全TM反过来 { int L1_length = L1->length; int L2_length = L2.length; int e; for (L1_length; L1_length >= 1; L1_length--) { e = GetElme(L1, L1_length); if (!LocateElem(L2, e, Equal)) ListDelete(L1, L1_length); } } int LocateElem(SeqList L, int e, int(Compare)(int, int)) { int i = 1; while (i <= L.length && !Compare(e, L.data[i - 1])) i++; if (i <= L.length) return i; else return 0; } int Equal(int a, int b) { if (a == b) return 1; else return 0; }

初始化首先要给结构体里的指针分配内存空间，然后初始化顺序表可以储存的数据数量和已存在的数据数量 ↩︎

插入和删除时要注意元素的位置不要超出初始化时的范围，如果顺序表满了要用realloc函数扩充 ↩︎

表长=0为空 表长=listsize为满 ↩︎

将第二个表中的元素和第一个表中的元素进行对比 求并集时把B中存在且不与A集合中元素重合的元素放进A中 实现对比需要创建 LocateElem(SeqList L,int e,int Compare(int ,int)) 函数把表中元素和要插入的元素按照Compare规则进行对比 ↩︎

最新回复(0)