赞
踩
严奶奶版数据结构,我用C写一直报错,后来发现C中没有引用,只有指针。为了还原原版的味道.这里创建了.cpp的文件,加上了#include<cstdio>和#include<cstdlib>两个头文件,来还原原汁原味的严奶奶版数据结构中的算法。
- /*#include<cstdio>
- #include<cstdlib>
- 创建c++文件,这两个头加上
- 严奶奶的书中又有引用又有指针,由于c语言只有引用没有指针,所以如果是.c的文件会报错
- 加上这两个头文件就可以使用C语言的语法规测了*/
- #include<cstdio>
- #include<cstdlib>
-
- #define LIST_INIT_SIZE 100
- #define LISTINCREMENT 10
- #define ElemType int //定义ElemType为int型(贴合教材)
- #define Status int //定义ElemType为int型(贴合教材)
-
- typedef struct {
- ElemType* elem; //储存空间基地址
- int length; //当前长度
- int listsize; //当前分配的储存容量(以sizeof(ElemType)为单位)
- }SqList;
初始化线性表L
- Status InitList_Sq(SqList& L) {
- L.elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType));
- if (!L.elem)exit(OVERFLOW);//储存分配失败
- L.length = 0; //空表长度为0
- L.listsize = LIST_INIT_SIZE;//初始存储容量
- return 1; //线性表L创建成功返回 1;(将书中的OK改为1,ERROR 改为0)
- }
创造线性表L
- Status CreatList_Sq(SqList& L, int n) {
- InitList_Sq(L);
- if (n >= L.listsize) {
- int* newbase = (ElemType*)realloc(L.elem, (n) * sizeof(ElemType));
- if (!newbase) return 0;
- L.elem = newbase;//新基址
- L.listsize = n;//增加储存容量
- }
- int* q;
- q = L.elem; //q为初始位置
- //遍历输入数组元素
- for (int i = 1; i <= n; i++) {//遍历输入数组元素
- int e;
- scanf_s("%d", &e);
- printf("添加新元素:%d 成功\n", e);
- *q = e;
- q++;
- L.length++;
- }
- }
在第i个元素之前插入新元素e
- Status ListInsert_Sq(SqList& L, int i, ElemType e) {
- if (i<1 || i>L.length + 1) return 0;//插入元素不合法
- if (L.length >= L.listsize) {
- int* newbase = (ElemType*)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(ElemType));
- if (!newbase) printf("新基址分配失败");return 0;
- L.elem = newbase;
- L.listsize += LISTINCREMENT;
- }
- int* q;
- int* p;
- q =&(L.elem[i-1]);
- for (p = &(L.elem[L.length - 1]); p >= q; p--) {
- *(p + 1) = *p;
- }
- *q = e;//插入e
- L.length++;
- printf("插入元素:%d 成功\n", e);
- return 1;
- }
删除第i个元素,并用e返回其值
- Status ListDelete_Sq(SqList& L, int i, ElemType e) {
- if ((i < L.length) || (i > L.length)) printf("i值不合法"); return 0;
- int* p;//p为被删除元素的位置
- int* q;//表尾元素的位置
- p = &(L.elem[i - 1]);//被删除的元素赋值给e
- e = *p;
- q = L.elem + L.length - 1;
- for (++q; p <= q; ++p) *(p - 1) = *p;//被删除的元素左移
- --L.length; //表长减1
- return 1;
- }
查找线性表L中第i个数的值
- Status GetElem(SqList& L, int i, ElemType e) {
- if (i<1 || i>L.length) printf("输入的值不合法!"); return 0;
-
- int* p;
- p = L.elem;
- while (i <= L.length && *p != e) {
- i++;
- *p++;
- }
- if (i <= L.length) {
- printf("次序为:%d\n", i);
- return 0;
- }
- else {
- printf("线性表L中查无此值");
- }
- }
La和Lb按照非递减排列,组合表La和Lb组成新的表Lc并且Lc也按照非递减排列
- Status MergeList_Sq(SqList La, SqList Lb, SqList& Lc) {
- int* pa, * pb,* pc;
- pa = La.elem; pb = Lb.elem;
- Lc.listsize = Lc.length = La.length + Lb.length;
- pc = Lc.elem = (ElemType*)malloc(Lc.listsize * sizeof(ElemType));
- if (!Lc.elem) exit(OVERFLOW);
- int* pa_last, * pb_last;
- pa_last = La.elem + La.length - 1;
- pb_last = Lb.elem + Lb.length - 1;
- while (pa < pa_last && pb < pb_last) {
- if (*pa <= *pb) *pc++ = *pa++;
- else *pc++ = *pb++;
- /*说明:这里*pc++ = *pb++;由于=的优先级高于++,所以原式等价于 *pc=*pb;*pc++;*pb++;*/
- }
- while (pa < pa_last) *pc++ = *pa++;//插入La的剩余元素
- while (pb < pb_last) *pc++ = *pb++;//插入Lb的剩余元素
- }
销毁线性表L
- Status DestoryList_Sq(SqList &L) {
- free(L.elem);//释放内存
- L.elem = NULL;//基地址为空
- L.length = 0;//长度为空
- L.listsize = 0;//存储空间为空
- printf("顺序表L销毁成功!\n");
- return 0;
- }
将顺序表L置为空表
- Status ClearList_Sq(SqList& L) {
- L.length = 0;
- printf("顺序表L已置为空表!\n");
- return 0;
- }
判断表L是否为空表,用TRUE和FALSE返回
- bool ListEmpty_Sq(SqList L) {
- if (L.length = 0) return true;
- else return false;
- return 0;
- }
返回顺序表L中的元素个数
- Status ListLength_Sq(SqList& L) {
- //使用L.lemgth即可
- return L.length;
- }
使用pre_e返回cur_e的前驱
- Status PriorElem(SqList& L, ElemType cur_e, ElemType pre_e) {
- int* p;
- p = L.elem;
- if (cur_e = *p) printf("ERROR!! 在顺序表中第一个元素没有前驱 \n");
- for (int i = 2; i < L.length; i++) {
- pre_e = *p;
- *p++;
- if (cur_e == *p) {
- printf("元素%d的前驱为:%d\n", cur_e, pre_e);
- break;
- }
- }
- return 0;
- }
//查找cur_e元素的后继元素并用next_e返回
- Status NextElem_Sq(SqList& L, ElemType cur_e, ElemType next_e) {
- int* p;
- p = &(L.elem[L.length - 1]);//取最后一个元素的地址 && p = L.elem + L.length - 1;
- if (cur_e == *p) { //从后向前查找后继
- printf("ERROR!!在顺序表中最后一个元素没有后继");
- }
- while (p > L.elem) {
- next_e = *p;
- *p--;
- if (*p = cur_e)
- printf("元素%d的后继为:%d", cur_e, next_e);
- break;
- }
- return 0;
- }
- int main() {
- /*此处省略10000字...*/
- }
main交给各位写了,我实现了没有问题的,有问题的请联系我。
学艺不精,若有错误还请多多指教,谢谢。
p.s.在使用Visual Studio编译器的时候输入scanf()方法要用scanf_s()
更多内容请移步公众号 手撕算法。谢谢
算法爱好者协会群:940100543,加入学习讨论。
所使用编译器为:Visual Studio2019 链接:https://pan.baidu.com/s/1eg8CNrqrP1jn7GRzHfYXxA
提取码:1234
推荐新手使用dev cpp 链接:https://pan.baidu.com/s /1XZp_8lVE7X6tMLmvXRbYhw
提取码:1234
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。