宁波建设局网站,html怎么做多个网页,wordpress营销型主题,茂名网站建设优化#x1f525;Go for it!#x1f525; #x1f4dd;个人主页#xff1a;按键难防 #x1f4eb; 如果文章知识点有错误的地方#xff0c;请指正#xff01;和大家一起学习#xff0c;一起进步#x1f440; #x1f4d6;系列专栏#xff1a;数据结构与算法 #x1f52… Go for it! 个人主页按键难防 如果文章知识点有错误的地方请指正和大家一起学习一起进步 系列专栏数据结构与算法 如果感觉博主的文章还不错的话还请 点赞收藏⭐️ 留言支持 一下博主哦 目录
一.线性表
①顺序表(顺序存储)
具体操作
1.顺序表插入元素
2.顺序表删除元素
3.遍历查找按值
②链表链式存储
1.单链表
①单链表定义
②头插法
③尾插法
具体操作
①按位查找遍历
②按值查找
③插入元素
④删除操作 一.线性表 定义由n(n≥0)个相同类型的元素组成的有序集合。La1, a2, … , ai , ai1, … , an
线性表中元素个数n称为线性表的长度。当n0时为空表。 a1是唯一的第一个数据元素an是唯一的“最后一个”数据元素。 ai-1为a的直接前驱ai1为a的直接后继。 特点
表中元素的个数是有限的。
表中元素的数据类型都相同。意味着每一个元素占用相同大小的空间 表中元素具有逻辑上的顺序性在序列中各元素排序有其先后顺序
线性表第一个元素的位序是1下标是0。 线性表是逻辑结构表示元素之间一对一的相邻关系用存储结构实现线性表就是顺序表或链表。 ①顺序表(顺序存储)
用顺序存储的方式实现线性表
定义方法静态版本
#define MaxSize 50 //定义线性表的长度
typedef int ElemType;//重定义线性表中每个元素的类型便于修改
typedef struct{ElemType data[MaxSize];//顺序表int len;//记录顺序表的当前长度
}SqList;//顺序表的类型定义
优点可以随机存取根据表头元素地址和序号表中任意一个元素。存储密度高每个结点只存储数据元素。
缺点 插入和删除操作需要移动大量元素。线性表变化较大时难以确定存储空间的容量。存储分配需要一整段连续的存储空间不路灵活。 具体操作
1.顺序表插入元素
#define MaxSize 50 //定义线性表的长度
typedef int ElemType;//重定义线性表中每个元素的类型便于修改
typedef struct{ElemType data[MaxSize];//顺序表int len;//记录顺序表的当前长度
}SqList;//顺序表的类型定义
bool ListInsert(SqList L, int i, ElemType e)
{//判断i的范围是否有效if (i1 || iL.len 1){return false;}if (L.lenMaxSize) //当前存储空间已满不能插入 {return false;}for (int j L.len; j i; j--){ //将第i个元素及其之后的元素后移L.data[j] L.data[j - 1];}L.data[i - 1] e; //在位置i处放入eL.len; //长度加1return true;
}
void PrintfList(SqList L)
{int i 0;for (i 0; i L.len; i){printf(%d,L.data[i]);}printf(\n);
}
int main()
{SqList L;bool ret;//布尔类型返回值L.data[0] 1;L.data[1] 2;L.data[2] 3;L.data[3] 4;L.data[4] 5;L.len 5;//记录顺序表的当前长度ret ListInsert(L,2,60);//在第二个元素位置插入60if (ret){printf(插入成功\n);PrintfList(L);}else{printf(插入失败\n);}return 0;
} 2.顺序表删除元素
#includestdio.h
#define MaxSize 50 //定义线性表的长度
typedef int ElemType;//重定义线性表中每个元素的类型便于修改
typedef struct{ElemType data[MaxSize];//顺序表int len;//记录顺序表的当前长度
}SqList;//顺序表的类型定义
bool ListDelete(SqList L, int i, ElemType e)
{ //e是为了将删去的值赋给e//判断i的范围是否有效int j 0;if (i1 || iL.len){return false;}e L.data[i - 1]; //将被删除的元素赋值给efor (ji; jL.len; j){ //将第i个后的元素前移L.data[j - 1] L.data[j];}L.len--; //长度减1return true;
}
void PrintfList(SqList L)
{int i 0;for (i 0; i L.len; i){printf(%d,L.data[i]);}printf(\n);
}
int main()
{SqList L;bool ret;//布尔类型返回值L.data[0] 1;L.data[1] 2;L.data[2] 3;L.data[3] 4;L.data[4] 5;L.len 5;//记录顺序表的当前长度ElemType del;//存储删去的元素ret ListDelete(L,1,del);//删除第一个元素if (ret){printf(删除成功\n);PrintfList(L);}else{printf(删除 失败\n);}return 0;
} 3.遍历查找按值
#includestdio.h
#define MaxSize 50 //定义线性表的长度
typedef int ElemType;//重定义线性表中每个元素的类型便于修改
typedef struct{ElemType data[MaxSize];//顺序表int len;//记录顺序表的当前长度
}SqList;//顺序表的类型定义
int LocateElem(SqList L, ElemType e)
{int i 0;for (i 0; i L.len; i)//遍历查找{if (L.data[i] e)return i 1;}//数组下标为i的元素值等于e返回其位序i1return 0;//退出循环说明查找失败
}
void PrintfList(SqList L)
{int i 0;for (i 0; i L.len; i){printf(%d , L.data[i]);}printf(\n);
}
int main()
{SqList L;int ret;//布尔类型返回值L.data[0] 1;L.data[1] 2;L.data[2] 3;L.data[3] 60;L.data[4] 5;L.len 5;//记录顺序表的当前长度ret LocateElem(L,60);if (ret){printf(查找成功\n);printf(位序是%d\n, ret);}else{printf(查找失败\n);}return 0;
} 动态版本 #define MaxSize 50 //定义线性表的长度
typedef struct{ElemType* data;//顺序表的元素int len;//顺序表的当前长度
}SqList;//顺序表的类型定义
L.data(ElemType*)malloc(sizeof(ElemType)*InitSize)
//malloc函数申请一片连续的存储空间大小为sizeof(ElemType)*InitSize
//用完要用free函数释放原来的内存空间 ②链表链式存储
用链式存储的方式实现线性表。
1.单链表 头指针链表中第一个结点的存储位置用来标识单链表。
头结点在单链表第一个结点之前附加的一个结点为了操作上的方便。
若链表有头结点则头指针永远指向头结点没有头结点则指向第一个结点不论链表是否为空头指针均不为空头指针是链表的必须元素他标识一个链表.
头结点是为了操作的方便而设立的其数据域一般为空或者存放链表的长度
有头结点后对在第一结点前插入和删除第一结点的操作就统一了不需要频繁重置头指针但头节点不是必须的。 优点
插入和删除操作不需要移动元素只需要修改指针。不需要大量的连续存储空间。
缺点
单链表附加指针域。也存在浪费存储空间的缺点。查找操作时需要从表头开始遍历依次查找不能随机
①单链表定义
typedef int ElemType;//重定义链表表中每个元素的类型便于修改
typedef struct LNode//定义单链表结点类型
{ElemType data; //数据域struct LNode *next;//指针域指向下一个结点。
}LNode, *LinkList;
解释typedef重命名了两个数据类型
分别是将struct LNode重命名为LNode将struct LNode*重命名为LinkList
前者是个结构体后者是个指向该结构体的指针
用LNode创建变量就是创建一个结构体
用LinkList创建变量就是指向这个结构体的指针②头插法 重点在灵活变化头结点的指针域插进来一个我就把头结点指针域原值赋给插进来结点的指针域然后头结点的指针域改为新插进来结点的指针。
#includestdio.h
#includestdlib.h
#define MaxSize 50 //定义线性表的长度
typedef int ElemType;//重定义链表表中每个元素的类型便于修改
typedef struct LNode//定义单链表结点类型
{ElemType data; //数据域struct LNode* next;//指针域指向下一个结点结构体)。
}LNode, *LinkList;
LinkList list_head_insert(LinkList L)
{L (LinkList)malloc(sizeof(LNode));//用动态内存开辟初始化头指针指向头结点L-next NULL;ElemType x;//头结点不存数据,随机初始化即可scanf(%d, x);LinkList s;//结构体指针用来指向申请的新节点swhile (x! 9999)//输入9999停止{s (LinkList)malloc(sizeof(LNode));//为新节点申请空间s-data x;//存数据s-next L-next;L-next s;//将插入的节点与头节点连接起来scanf(%d, x);}return L;//链表建立完毕返回头指针
}
void printf_list(LinkList L)
{LL-next;while (L! NULL){printf(%3d , L-data);LL-next;}printf(\n);
}
int main()
{LinkList L;//L是链表头指针此时没初始化还没指向头结点list_head_insert(L);printf_list(L);//链表打印return 0;
} ③尾插法 r一直在充当中转站的角色。
#include stdio.h
#include stdlib.h
typedef int ElemType;
typedef struct LNode{ElemType data;struct LNode *next;//指向下一个结点
}LNode, *LinkList;
//尾插法新建链表
LinkList list_tail_insert(LinkList L)
{L (LinkList)malloc(sizeof(LNode));//带头节点的链表L-next NULL;ElemType x;scanf(%d, x);LinkList s, r L;//s是指向新结点r始终指向链表尾部。while (x ! 9999){s (LNode*)malloc(sizeof(LNode));s-data x;r-next s;//让尾部结点指向新结点r s;//rs是确保r指向的是新的表尾结点scanf(%d, x);}r-next NULL;//尾结点的 next 指针赋值为 NULLreturn L;
}
//打印链表中每个结点的值
void print_list(LinkList L)
{L L-next;while (L ! NULL){printf(%3d , L-data);//打印当前结点数据L L-next;//指向下一个结点}printf(\n);
}
int main()
{LinkList L;//链表头是结构体指针类型list_tail_insert(L);//输入数据可以为 3 4 5 6 7 9999print_list(L);//链表打印return 0;
} 具体操作
①按位查找遍历
单链表只能从前往后查找
L的位置是0
#include stdio.h
#include stdlib.h
#include string.h
typedef int ElemType;
typedef struct LNode
{ElemType data;struct LNode *next;//指向下一个结点
}LNode, *LinkList;
//尾插法新建链表
LinkList list_tail_insert(LinkList L)
{L (LinkList)malloc(sizeof(LNode));//带头节点的链表L-next NULL;ElemType x;scanf(%d, x);LinkList s, r L;//s是指向新结点r始终指向链表尾部。while (x ! 9999){s (LNode*)malloc(sizeof(LNode));s-data x;r-next s;//让尾部结点指向新结点r s;//r 指向新的表尾结点scanf(%d, x);}r-next NULL;//尾结点的 next 指针赋值为 NULLreturn L;
}
//打印链表中每个结点的值
void print_list(LinkList L)
{L L-next;while (L ! NULL){printf(%3d , L-data);//打印当前结点数据L L-next;//指向下一个结点}printf(\n);
}
LinkList GetElem(LinkList L, int i)
{int j 0; if (i 0){return NULL;} for(j0; Lji;j){L L-next;}return L;//返回查找到的结点
}
int main()
{LinkList L, search;//链表头是结构体指针类型list_tail_insert(L);print_list(L);//链表打印search GetElem(L, 2);if (search ! NULL){printf(按序号查找成功\n);printf(该序号的值为%d\n, search-data);return 0;}
} ②按值查找
#include stdio.h
#include stdlib.h
#include string.h
typedef int ElemType;
typedef struct LNode
{ElemType data;struct LNode *next;//指向下一个结点
}LNode, *LinkList;
//尾插法新建链表
LinkList list_tail_insert(LinkList L)
{L (LinkList)malloc(sizeof(LNode));//带头节点的链表L-next NULL;ElemType x;scanf(%d, x);LinkList s, r L;//s是指向新结点r始终指向链表尾部。while (x ! 9999){s (LNode*)malloc(sizeof(LNode));s-data x;r-next s;//让尾部结点指向新结点r s;//r 指向新的表尾结点scanf(%d, x);}r-next NULL;//尾结点的 next 指针赋值为 NULLreturn L;
}
//打印链表中每个结点的值
void print_list(LinkList L)
{L L-next;while (L ! NULL){printf(%3d , L-data);//打印当前结点数据L L-next;//指向下一个结点}printf(\n);
}
LinkList LocateElem(LinkList L, ElemType e)
{while (L){if (L-data e)//如果相等直接返回那个结点{return L;}L L-next;}
}
int main()
{LinkList L, search;//链表头是结构体指针类型list_tail_insert(L);print_list(L);//链表打印search LocateElem(L, 6);//按值查询if (search ! NULL){printf(按值查找成功\n);printf(%d\n, search-data);}
} ③插入元素
在第i个节点插入某元素那我就借助先按位查找到第i-1个节点然后将i-1的指针域赋给要插入的指针域将i-1节点的指针域改为新插入节点的位置
#include stdio.h
#include stdlib.h
#include string.h
typedef int ElemType;
typedef struct LNode
{ElemType data;struct LNode *next;//指向下一个结点
}LNode, *LinkList;
//尾插法新建链表
LinkList list_tail_insert(LinkList L)
{L (LinkList)malloc(sizeof(LNode));//带头节点的链表L-next NULL;ElemType x;scanf(%d, x);LinkList s, r L;//s是指向新结点r始终指向链表尾部。while (x ! 9999){s (LNode*)malloc(sizeof(LNode));s-data x;r-next s;//让尾部结点指向新结点r s;//r 指向新的表尾结点scanf(%d, x);}r-next NULL;//尾结点的 next 指针赋值为 NULLreturn L;
}
//打印链表中每个结点的值
void print_list(LinkList L)
{L L-next;while (L ! NULL){printf(%3d , L-data);//打印当前结点数据L L-next;//指向下一个结点}printf(\n);
}
//按位查找
LinkList GetElem(LinkList L, int i)
{int j 0;if (i 0){return NULL;}for(j0; Lji;j){L L-next;}return L;//返回查找到的结点
}
//插入操作
bool ListFrontInsert(LinkList L, int i, ElemType e)
{LinkList p GetElem(L, i - 1);if (NULL p){return false;}LinkList s (LNode*)malloc(sizeof(LNode));//为新插入的结点申请空间s-data e;s-next p-next;p-next s;return true;
}
int main()
{LinkList L, search;//链表头是结构体指针类型list_tail_insert(L);print_list(L);//链表打印ListFrontInsert(L, 2, 99);//新结点插入第2个位置,值为99print_list(L);
}
④删除操作
删除第i个节点借助按位查找找到第i-1个然后将该节点的指针域赋给中间变量便于后续释放然后将第i个节点的指针域赋给i-1
#include stdio.h
#include stdlib.h
#include string.h
typedef int ElemType;
typedef struct LNode
{ElemType data;struct LNode *next;//指向下一个结点
}LNode, *LinkList;
//尾插法新建链表
LinkList list_tail_insert(LinkList L)
{L (LinkList)malloc(sizeof(LNode));//带头节点的链表L-next NULL;ElemType x;scanf(%d, x);LinkList s, r L;//s是指向新结点r始终指向链表尾部。while (x ! 9999){s (LNode*)malloc(sizeof(LNode));s-data x;r-next s;//让尾部结点指向新结点r s;//r 指向新的表尾结点scanf(%d, x);}r-next NULL;//尾结点的 next 指针赋值为 NULLreturn L;
}
//打印链表中每个结点的值
void print_list(LinkList L)
{L L-next;while (L ! NULL){printf(%3d , L-data);//打印当前结点数据L L-next;//指向下一个结点}printf(\n);
}
//按位查找
LinkList GetElem(LinkList L, int i)
{int j 0;if (i 0){return NULL;}for(j0; Lji;j){L L-next;}return L;//返回查找到的结点
}
//删除操作
bool ListFrontInsert(LinkList L, int i, ElemType e)
{LinkList p GetElem(L, i - 1);if (NULL p){return false;}LinkList q;//用来存储删除的节点便于释放动态空间qp-next;p-nextq-next;//断链freeq//释放对应节点的空间return true;
}
int main()
{LinkList L, search;//链表头是结构体指针类型list_tail_insert(L);print_list(L);//链表打印ListDelete(L,4);print_list(L);//链表打印
}
