王道考研数据结构

您所在的位置：网站首页 › 西柚减肥法原理 › 王道考研数据结构

王道考研数据结构

#王道考研数据结构| 来源: 网络整理| 查看: 265

1.前言

2.难点

2.1 C语言没有bool数据类型

2.2 顺序表的位序从1开始，而数组的位序从0开始

2.3符号&在函数中表示取地址返回

3.源代码（静态存储）

4.动态存储

4.1结构体编写

4.2初始化

4.3动态表可以增加表长

4.4源代码（静态+动态存储）

1.前言

日期：2023.6.20

书籍：2024年数据结构考研复习指导（王道考研系列）

内容：静态存储实现顺序表，及其基本操作，初始化，增加，删除，查找，判空和遍历输出。

InitList(SqList *L);//初始化 Length(SqList *L);//求表长 ListInsert(SqList *L,int i,Elemtype e);//插入操作 ListDelete(SqList *L,int i,Elemtype e);//删除操作 LocateElem(SqList *L,Elemtype e);//按值查找 GetElem(SqList *L,int i);//按位查找 OutputList(SqList L);//输出操作 2.难点

学习的语言多了，有些语法知识会搞混淆，c语言有些东西是没有的，一定要注意！！

2.1 C语言没有bool数据类型

老生常谈了，C语言没有直接定义好的bool类型，不过我们可以自己宏定义一个啊

#define bool char #define false 0 #define true 1 2.2 顺序表的位序从1开始，而数组的位序从0开始

顺序表第i个位置，表示为L->data[i-1]，最终代码里每个i代表什么意思我都已经标好了，一会儿之间看源代码吧

2.3符号&在函数中表示取地址返回

符号"&"，表示c++中的引用调用，在c语言中可以用指针达到一样的效果，比如：

SqList &L == SqList l; SqList *L=&l; 3.源代码（静态存储） #include #include //c语言宏定义bool操作 #define bool char #define true 1 #define false 0 //顺序表及数组长度 #define MaxSize 10 //数据元素数据类型 typedef int ElemType; //顺序表结构定义 typedef struct { ElemType data[MaxSize];//顺序表元素 int length;//顺序表长度 /* data */ }SqList; //基本操作1.初始化一个顺序表 void InitList(SqList *L){ for(int i=0;idata[i]=0; L->length=0; } } //基本操作2.插入一个数据元素 /* 在顺序表L的第i(1length>=MaxSize) return false; for(int j=L->length;j>=i;j--){ L->data[j]=L->data[j-1]; }//将i位置后面的元素从最后面向右推1 L->data[i-1]=e; L->length++; printf("当前表长是：%d\n",L->length); return true; }//后退从后开始 //基本操作3.删除操作 /* 删除i位置的元素，并且用e返回其值 */ bool ListDelete(SqList *L,int i,ElemType *e){ if(iL->length) return false; *e=L->data[i-1]; for(int j=i;jlength;j++){ L->data[j-1]=L->data[j]; } L->length--; return true; }//前推从前面开始 //基本操作4.1.按位查找 bool GetElem(SqList *L,int i){ if(iL->length){ printf("查找失败\n"); return false; } printf("顺序表第%d个元素是%d\n",i,L->data[i-1]); } //基本操作4.2.按值查找(顺序查找) int LocateElem(SqList *L,ElemType e){ for(int i=0;ilength;i++){ if(L->data[i]==e){ printf("查找元素%d位于第%d个\n",e,i+1); return i+1; } } return 0; } //基本操作5.遍历输出顺序表 bool OutputList(SqList *L){ //判空操作 if(L->length==0){ printf("顺序表是空的。\n"); return false; } int i=1; while (ilength){ printf("顺序表的第%d个元素是%d.\n",i,L->data[i-1]); i++; } return true; } void text1(){ printf("********************************************************\n"); printf("** 欢迎使用本数据表,请选择您的操作 **\n"); printf("** 1.插入新元素 **\n"); printf("** 2.插入元素 **\n"); printf("** 3.删除元素 **\n"); printf("** 4.输出顺序表 **\n"); printf("** 5.按位查找 **\n"); printf("** 6.按值查找 **\n"); printf("** 7.输出表长 **\n"); printf("** 0.退出程序 **\n"); printf("********************************************************\n"); } void text2(SqList *L){ int a; while(1){ text1(); scanf("%d",&a); switch (a){ case 0: exit(0); break; case 1:{ int x; printf("请输入你要插入的值（默认插入顺序表最后一位）：\n"); scanf("%d",&x); bool b = ListInsert(L,L->length+1,x); if(b) printf("插入成功!\n"); else printf("插入失败!\n"); break; } case 2:{ int x,y; printf("请输入您要插入的值:\n"); scanf("%d",&x); printf("请输入您要插入的位置:\n"); scanf("%d",&y); bool b = ListInsert(L,y,x); if(b) printf("插入成功!\n"); else printf("插入失败!\n"); break ; } case 3:{ int x,y; printf("请输入您要删除的值:\n"); scanf("%d",&x); bool b = ListDelete(L,x,&y); if(b) printf("删除成功!,删除的值为:%d\n",y); else printf("删除失败!\n"); break ; } case 4:{ OutputList(L); break; } case 5:{ int x; printf("请输入您要查看的位置:\n"); scanf("%d",&x); GetElem(L,x); break ; } case 6:{ int x; printf("请输入您要查找的元素的值:\n"); scanf("%d",&x); int b = LocateElem(L,x); if(b) printf("查找成功!,是第%d个元素\n",b); else printf("查找失败!没有这个元素\n"); break ; } case 7:{ printf("现在顺序表的长度是：%d\n",L->length); break; } default: printf("输入错误，请重新输入：\n"); break; }//of switch }//of while }//of text2 int main(){ SqList l; SqList *L=&l; InitList(L); text2(L); } 4.动态存储

基本操作和静态存储差不多，差异在于结构体，初始化和增加表长。

4.1结构体编写 //顺序表数据元素结构体(静态分配) typedef struct SqList { //[1]用静态的“数组”存放数据元素 Elemtype data[MaxSize]; //[2]顺序表的当前长度 int length; }SqList;//顺序表的类型定义（静态分配方式） //顺序表数据元素结构体(动态分配) typedef struct SeqList { //[1]指示动态分配数组的指针 Elemtype *data; //[2]顺序表的当前长度 int length; //[3]顺序表的最大容量 int maxsize; }SeqList;//顺序表的类型定义（动态分配方式） 4.2初始化 //基本操作----初始化一个静态顺序表 bool InitsqList(SqList *L){ //[1]将所有数据元素设为默认初始值 for(int i = 0; i < MaxSize; i++){ L->data[i] = 0; } /* 1.本步骤其实可以省略 2.之所以赋初值是因为内存中会有遗留的"脏数据" 3.但是常规操作下,用户无法访问大于当前表长的数据元素,所以可以在需要时再赋值 */ //[2]顺序表初始长度设为0 L->length = 0; return true; } //基本操作----初始化一个动态顺序表 bool InitseqList(SeqList *L){ //[1]用malloc函数申请一片连续的存储空间 L->data = (Elemtype *)malloc(sizeof(Elemtype) * InitSize); //[2]表长和默认最大长度初始化 L->length = 0; L->maxsize = InitSize; return true; } 4.3动态表可以增加表长 //动态顺序表的加长 bool IncreaseSize(SeqList *L,int len) { //[1]生成指向原来顺序表存储位置的指针 int *p = L->data; //[2]为顺序表开辟一片比原来更大的空间 L->data = (Elemtype *)malloc((L->maxsize + len) * sizeof(Elemtype)); //[3]转移数据 for (int i = 0; i < L->length; i++){ L->data[i] = p[i]; } //[4]修改顺序表的最大长度,为其增加len L->maxsize = L->maxsize + len; //[5]释放原来的存储空间 free(p); return true; } 4.4源代码（静态+动态存储） //[1]定义顺序表最大长度和动态数组初始默认的最大容量 #define MaxSize 10 //静态顺序表的最大长度 #define InitSize 10 //动态顺序表的初始最大长度 //需要包含的头文件 #include #include //C语言自定义bool变量 #define bool char #define true 1 #define false 0 //自定义数据元素的数据类型 typedef int Elemtype; //顺序表数据元素结构体(静态分配) typedef struct SqList { //[1]用静态的“数组”存放数据元素 Elemtype data[MaxSize]; //[2]顺序表的当前长度 int length; }SqList;//顺序表的类型定义（静态分配方式） //顺序表数据元素结构体(动态分配) typedef struct SeqList { //[1]指示动态分配数组的指针 Elemtype *data; //[2]顺序表的当前长度 int length; //[3]顺序表的最大容量 int maxsize; }SeqList;//顺序表的类型定义（动态分配方式） //基本操作----初始化一个静态顺序表 bool InitsqList(SqList *L) { //[1]将所有数据元素设为默认初始值 for(int i = 0; i < MaxSize; i++) { L->data[i] = 0; } /* 1.本步骤其实可以省略 2.之所以赋初值是因为内存中会有遗留的"脏数据" 3.但是常规操作下,用户无法访问大于当前表长的数据元素,所以可以在需要时再赋值 */ //[2]顺序表初始长度设为0 L->length = 0; return true; } //基本操作----初始化一个动态顺序表 bool InitseqList(SeqList *L) { //[1]用malloc函数申请一片连续的存储空间 L->data = (Elemtype *)malloc(sizeof(Elemtype) * InitSize); //[2]表长和默认最大长度初始化 L->length = 0; L->maxsize = InitSize; return true; } //动态顺序表的加长 bool IncreaseSize(SeqList *L,int len) { //[1]生成指向原来顺序表存储位置的指针 int *p = L->data; //[2]为顺序表开辟一片比原来更大的空间 L->data = (Elemtype *)malloc((L->maxsize + len) * sizeof(Elemtype)); //[3]转移数据 for (int i = 0; i < L->length; i++) { L->data[i] = p[i]; } //[4]修改顺序表的最大长度,为其增加len L->maxsize = L->maxsize + len; //[5]释放原来的存储空间 free(p); return true; } //基本操作----顺序表的插入 //[1]静态顺序表的插入 bool SqListInsert(SqList *L,int i,Elemtype e) { //[1]判断i的合法性 if(i < 1 || i > L->length + 1) { printf("The position of the element to be inserted is invalid!\n"); return false; } if(L->length >= MaxSize) { printf("This sequence table is full!\n"); return false; } //[2]将第i个元素及之后的元素都后移 for(int j = L->length; j >= i; j--) { L->data[j] = L->data[j-1]; //第i个元素对应数组下标为i-1的数组元素 } //[3]在正确的位置插入新元素 L->data[i-1] = e; //[4]顺序表长+1(注意:顺序表的最大长度不变) L->length++; //[5]插入成功,返回成功信号 return true; } //[2]动态顺序表的插入 bool SeqListInsert(SeqList *L,int i,Elemtype e) { //[1]判断i的合法性 if(i < 1 || i > L->length + 1) { printf("The position of the element to be inserted is invalid!\n"); return false; } if(L->length >= L->maxsize) { printf("This sequence table is full!\n"); return false; } //[2]将第i个元素及之后的元素都后移 for(int j = L->length; j >= i; j--) { L->data[j] = L->data[j+1]; //第i个元素对应数组下标为i-1的数组元素 } //[3]在正确的位置插入新元素 L->data[i-1] = e; //[4]顺序表长+1(注意:顺序表的最大长度不变) L->length++; //[5]插入成功,返回成功信号 return true; } //基本操作----顺序表的元素删除 //[1]静态顺序表的元素删除 bool SqListDelete(SqList *L, int i, Elemtype *e) { //[1]判断i的合法性 if(i < 1 || i > L->length + 1) { printf("The position of the element to be delected is invalid!\n"); return false; } if(L->length data[i-1]; //[3]将第i个元素及之后的元素都前移 for(int j = i; j length; j++) { L->data[j-1] = L->data[j]; //第i个元素对应数组下标为i-1的数组元素 } //[4]顺序表长-1(注意:顺序表的最大长度不变) L->length--; //[5]插入成功,返回成功信号 return true; } //[2]动态顺序表的元素删除 bool SeqListDelete(SeqList *L,int i,Elemtype *e) { //[1]判断i的合法性 if(i < 1 || i > L->length + 1) { printf("The position of the element to be delected is invalid!\n"); return false; } if(L->length data[i-1]; //[3]将第i个元素及之后的元素都前移 for(int j = i; j length; j++) { L->data[j-1] = L->data[j]; //第i个元素对应数组下标为i-1的数组元素 } //[4]顺序表长-1(注意:顺序表的最大长度不变) L->length--; //[5]插入成功,返回成功信号 return true; } //基本操作----按值查找 //[1]静态顺序表的按值查找 int SqListLocateElem(SqList L, Elemtype e) { int i; for(i = 0; i < L.length; i++) { if (L.data[i] == e) { return i+1; } } return 0; } //[2]动态顺序表的按值查找 int SeqListLocateElem(SeqList L, Elemtype e) { int i; for(i = 0; i < L.length; i++) { if (L.data[i] == e) { return i+1; } } return 0; } //额外操作----顺序表的打印 //[1]静态顺序表的输出 bool SqListPrint(SqList L) { //[1]判空 if(L.length == 0) { printf("This sequence table is empty!\n"); return false; } //[2]输出 printf("SqList:\n"); for(int i = 0;i < L.length;i++) { printf("%d-->",L.data[i]); } printf("end\n"); } //[2]动态顺序表的输出 bool SeqListPrint(SeqList L) { //[1]判空 if(L.length == 0) { printf("This sequence table is empty!\n"); return false; } //[2]输出 printf("SeqList:\n"); for(int i = 0;i < L.length;i++) { printf("%d-->",L.data[i]); } printf("end\n"); } int main() { /*【1】生成顺序表*/ //[1]静态分配的顺序表L1 SqList L1; //[2]动态分配的顺序表L2 SeqList L2; /*【2】顺序表的初始化*/ //[1]静态顺序表L1的初始化 InitsqList(&L1); //[2]动态顺序表L2的初始化 InitseqList(&L2); /*【3】顺序表插入新元素*/ int e; SqListInsert(&L1,1,1); SqListInsert(&L1,2,2); SqListInsert(&L1,3,3); SqListInsert(&L1,4,4); SqListInsert(&L1,5,5); SqListDelete(&L1,3,&e); SqListInsert(&L1,5,6); SeqListInsert(&L2,1,1); SeqListInsert(&L2,2,2); SeqListInsert(&L2,3,3); SeqListInsert(&L2,4,4); SeqListInsert(&L2,5,5); SeqListDelete(&L2,2,&e); SeqListInsert(&L2,5,6); IncreaseSize(&L2,5); SqListPrint(L1); SeqListPrint(L2); printf("%d\n",L2.maxsize); printf("SqListLocateElem(4) = %d\n",SqListLocateElem(L1,4)); printf("SeqListLocateElem(6) = %d\n",SeqListLocateElem(L2,6)); return 0; }

【本文地址】

王道考研数据结构

王道考研数据结构

今日新闻

推荐新闻