刚建设的网站多久能在百度查到,中国十大公司企业文化,湛江专业网站建设公司,高端网站开发价格线性表 目录 线性表定义和基本操作顺序表静态顺序表动态顺序表 链表单链表不带头结点#xff1a;带头结点#xff1a; 双链表循环链表循环单链表#xff1a;循环双链表#xff1a; 静态链表 顺序表链表比较逻辑结构#xff1a;存储结构#xff1a;基本操作#xff1a; 定…线性表 目录 线性表定义和基本操作顺序表静态顺序表动态顺序表 链表单链表不带头结点带头结点 双链表循环链表循环单链表循环双链表 静态链表 顺序表链表比较逻辑结构存储结构基本操作 定义和基本操作
线性表的定义线性表时具有相同数据类型的nn0个数据元素的有限序列其中n为表长当n0时线性表是一个空表。
L(a1,a2,a3…,an) a1为表头元素an为表尾元素除第一个元素外每个元素有且仅有一个直接前驱除最后一个元素每个元素有且仅有一个直接后继。
特点
元素个数有限元素具有逻辑上的顺序性表中元素有其先后次序元素都是数据元素每个元素都是单个元素元素数据类型相同占有相同大小的存储空间元素具有抽象性
线性表是一种逻辑结构表示元素之间一对一的相邻关系顺序表和链表是指存储结构。
线性表基本操作 总结 顺序表
线性表的顺序存储称为顺序表使用一组地址连续的存储单元依次存储线性表中的数据元素从而使得逻辑上相邻的两个元素在物理位置上也相邻。i为ai在线性表中的位序元素的逻辑顺序与其物理顺序相同。 线性表的顺序存储结构是一种随机存储的存储结构。
顺序表的特点
随机访问可以在O1时间内找到第i个元素 data[i-1]存储密度高每个结点智存初数据元素拓展容量不方便即使采用动态分配拓展长度时间复杂度仍较高插入、删除操作不方便需要移动大量元素
静态顺序表
一维数组可以静态分配也可以动态分配静态分配时数组大小和空间事先固定不可变。而动态顺序表则不需要为线性表一次性划分所有空间。
结构体
#define MaxSize 50typedef struct {int data[MaxSize];int length;
} SqList;初始化
//初始化
void InitList(SqList L) {for (int i 0; i MaxSize; i) {L.data[i] 0;//将所有元素的初始值默认设置为0//这一步其实可以省略但是省略之后有可能受到内存中脏数据的影响}L.length 0;
}判空
//判断是否为空
bool Empty(SqList L) {return (L.length 0);
}插入
//插入
bool ListInsert(SqList L, int i, int e) {//判断插入的位置是否合法if (i 1 || i L.length 1)return false;//判断表是否存满了if (L.length MaxSize)return false;//后面的元素后移for (int j L.length; j i; j--) {L.data[j] L.data[j - 1];}L.data[i - 1] e;L.length;return true;
}删除
//删除
bool ListDelete(SqList L, int i, int e) {//判断i的位置是否合法if (i 0 || i L.length) {return false;}//取出将要被删除的数e L.data[i - 1];//将其后的数据前移for (int j i; j L.length; j) {L.data[j - 1] L.data[j];}//线性表长度减一L.length--;return true;
}查找
//查找
//按位查找
int GetElem(SqList L, int i) {//判断是否越界if (i 0 || i L.length)return -1;return L.data[i - 1];
}
//按值查找
int LocateElem(SqList L, int e) {//循环出查找for (int i 0; i L.length; i) {if (L.data[i] e)return i 1; //返回位序}return -1;
}改值
//先查找后改值
//由此分为两种方式先按位查找后改值或先按值查找后改值
//先按值查找后改值
bool LocateChangeElem(SqList L, int e, int em) {//按值查找得到位序int bitOrder LocateElem(L, e);//改值if (bitOrder ! -1) {L.data[bitOrder] em;return true;}else {return false;}
}//先按位序查找后改值
bool getChangeElem(SqList L, int i, int em) {//给的位序,首先判断i是否合法if (i 0 || i L.length)return false;//由于是用数组实现的方式可以直接利用i查找L.data[i] em;return true;}打印
//打印整个顺序表
void PrintSqList(SqList L) {//循环打印printf(开始打印顺序表\n);for (int i 0; i L.length; i) {printf(Data[%d]%d\n, i, L.data[i]);}printf(打印结束\n);
}动态顺序表
一旦数据空间占满就另外开辟一块更大的存储空间用以替换原来的存储空间从而达到扩充存储空间的目的。
结构体
#define InitSize 100
typedef struct {int* data; //指示动态分配数组的指针int MaxSize;//顺序表的最大容量int length;//顺序表当前的长度
} SeqList;初始化
//初始化
bool InitList(SeqList L) {//用 malloc 函数申请一片连续的存储空间L.data (int*)malloc(InitSize * sizeof(int));if (L.data NULL)return false;//(int *) 是指针的强制类型转换L.length 0;L.MaxSize InitSize;return true;
}
判空
//判空
bool Empty(SeqList L) {return (L.length 0);
}判满
//判满
bool Full(SeqList L) {return (L.length L.MaxSize);
}扩展空间
//扩展空间
void IncreaseSize(SeqList L, int len) {int* p L.data;L.data (int*)malloc((InitSize len) * sizeof(int));for (int i 0; i L.length; i) {L.data[i] p[i];}L.MaxSize L.MaxSize len;free(p);//malloc 函数用于申请内存空间free 函数用于释放内存空间
}插入
//插入
bool ListInsert(SeqList L, int i, int e) {//判断插入的位置是否合法if (i 1 || i L.length 1)return false;//判断表是否存满了
// if (L.lengthL.MaxSize)
// return fals;if (Full(L))return false;//后面的元素后移for (int j L.length; j i; j--) {L.data[j] L.data[j - 1];}L.data[i - 1] e;L.length;return true;
}
按位查找
//按位查找
int GetElem(SeqList L, int i) {//判断是否越界if (i 0 || i L.length)return -1;return L.data[i - 1];
}
按值查找
//按值查找
int LocateElem(SeqList L, int e) {//循环出查找for (int i 0; i L.length; i) {if (L.data[i] e)return i 1; //返回位序}return -1;
}
删除
//删除
bool ListDelete(SeqList L, int i, int e) {//判断i的位置是否合法if (i 0 || i L.length) {return false;}//取出将要被删除的数e L.data[i - 1];//将其后的数据前移for (int j i; j L.length; j) {L.data[j - 1] L.data[j];}//线性表长度减一L.length--;return true;
}
销毁
//销毁
//由于动态分配方式使用malloc申请的内存空间故需要使用free函数手动释放空间
void DestroySqList(SeqList L) {free(L.data);L.data NULL;L.length 0;
}
打印
//打印整个顺序表
void PrintSqList(SeqList L) {if (L.data NULL || L.length 0)printf(这是一个空表);else {//循环打印printf(开始打印顺序表\n);for (int i 0; i L.length; i) {printf(Data[%d]%d\n, i, L.data[i]);}printf(打印结束\n);}
}
总结 链表
单链表
线性表的链式存储称为单链表它指通过一组任意的存储单元来存储线性表中的数据元素。每个链表结点存放元素自身的信息外还需要存放一个指向其后继的指针。 结构体
//结构体
typedef struct LNode {int data;struct LNode* next;
} LNode, * LinkList;
//等价于
//struct LNode{
// int data;
// struct LNode *next;
//};
//
//typedef struct LNode LNode;
//typedef struct LNode *LinkList;LinkList强调为单链表 LNode*强调为结点两者等价
不带头结点
初始化
//初始化
bool InitList(LinkList L) {L NULL;//空表暂时没有任何数据return true;
}判空
//判断是否为空
bool Empty(LinkList L) {return (L NULL);
}
//等价于
//bool Empty1(LinkList L){
// if (LNULL)
// return true;
// else
// return false;
//}插入
//在指定位置插入元素
bool ListInsert(LinkList L, int i, int e) {if (i 1)return false;//判断位序i是否合法//不带头节点时插入位置正好为表头时得单独处理if (i 1) {LNode* s (LNode*)malloc(sizeof(LNode));s-data e;s-next L;L s;return true;}LNode* p;//指针指向当前扫面到的节点int j 0;//记录p指向的节点的位序p L;//L指向头节点从头开始while (p ! NULL j i - 1) {//循环扫描p p-next;j;}if (p NULL) //i值超过来表长不合法return false;LNode* s (LNode*)malloc(sizeof(LNode));s-data e;//下面的顺序不可交换s-next p-next;p-next s;return true;
}
带头结点
初始化
//初试化(带有头节点)
bool InitList(LinkList L) {L (LNode*)malloc(sizeof(LNode));//分配一个头节点if (L NULL)return false;//头节点分配失败可能是内存不足L-next NULL;//头节点之后暂时没有节点头节点也不存放数据return true;
}判空
//判空
bool Empty(LinkList L) {return (L-next NULL);
}打印链表
void PrintList(LinkList L) {//循环打印整个链表LNode* p L-next;//扫描指针int j 0;if (p NULL)printf(这是一个空表\n);while (p ! NULL) {printf(LinkList[%d]%d\n, j, p-data);p p-next;j;}
}按位插入 //按位插入
bool ListInsert(LinkList L, int i, int e) {if (i 1)return false;//判断位序i是否合法LNode* p;//指针指向当前扫面到的节点int j 0;//记录p指向的节点的位序p L;//L指向头节点从头开始while (p ! NULL j i - 1) {//循环扫描p p-next;j;}if (p NULL) //i值超过来表长不合法return false;LNode* s (LNode*)malloc(sizeof(LNode));s-data e;//下面的顺序不可交换s-next p-next;p-next s; //将结点s连到p之后return true;
}
后插操作包含于之前的插入操作之中
//指定节点的后插操作
bool InsertNextNode(LNode* p, int e) {if (p NULL)return false;//判断指定节点是否存在LNode* s (LNode*)malloc(sizeof(LNode));if (s NULL)return false;//分配内存失败s-data e;s-next p-next;p-next s;return true;
}
前插操作由于难以获得前一个链表元素信息所以先完成后插再交换两者数据实现前插
//指定节点的前插操作
//先完成后插再交换数据以实现前插
bool InsertPriorNode(LNode* p, int e) {if (p NULL)return false;LNode* s (LNode*)malloc(sizeof(LNode));if (s NULL)return false;s-next p-next;p-next s;s-data p-data;p-data e;return true;
}按指定位序删除并返回值
//按指定位序删除节点并返回其值
bool ListDelete(LinkList L, int i, int e) {if (i 1)return false;LNode* p;int j 0;p L;while (p ! NULL j i - 1) {p p-next;j;}LNode* q p-next;e q-data;p-next q-next;free(q);return true;
}删除指定节点若p为最后一个元素则存在问题只能通过从头结点开始顺序找到其前序节点的方法来进行删除。 //删除指定节点
bool DeleteNode(LNode* p) {if (p NULL){return false;}LNode* q p-next;//令q指向*p的后续结点p-data p-next-data;//和后续结点交换数据域p-next q-next;//将*q结点从链中“断开”free(q);//释放后续结点的存储空间return true;
}
按值查找
//按值查找
LNode* LocateElem(LinkList L, int e)
{LNode* p L-next;//从第1个结点开始查找数据域为e的结点while (p ! NULL p-data ! e){p p-next;}return p;//找到后返回该结点指针否则返回NULL
}
按位查找
//按位查找
LNode* GetElem(LinkList L, int i)
{if (i 0){return NULL;}LNode* p;//指针p指向当前扫描到的结点int j 0;//当前p指向的是第几个结点p L;//L指向头结点头结点是第0个结点不存数据while (p ! NULL j i){p p-next;j;}return p;
}
求表长
//求表长
int Lnegth(LinkList L)
{int len 0;//统计表长LNode* p L;while (p-next ! NULL){p p-next;len;}return len;
}尾插法建表设置一个表尾指针方便直接在队尾进行尾插操作
//尾插法建立单链表正向建立单链表
LinkList List_TailInsert(LinkList L)
{int x;L (LinkList)malloc(sizeof(LNode));//建立头结点LNode* s, * r L;//r为表尾指针方便尾插scanf(%d, x);//输入结点的值while (x ! 9999)//输入9999表示结束{s (LNode*)malloc(sizeof(LNode));s-data x;r-next s;r s;//r指向新的表尾结点永远保持r指向最后一个结点避免重复操作scanf(%d, x);}r-next NULL;return L;
}头插法建立单链表(不断对头结点进行尾插操作
//头插法建立单链表(不断对头结点进行尾插操作
LinkList List_HeadInsert(LinkList L)//逆向建立单链表
{LNode* s;int x;L (LinkList)malloc(sizeof(LNode));//创建头结点L-next NULL;//初始为空链表scanf(%d, x);//输入结点的值while (x ! 9999)//输入9999表示结束{s (LNode*)malloc(sizeof(LNode));//创建新结点s-data x;s-next L-next;L-next s;//将新结点插入表中L为头指针scanf(%d, x);}return L;
}双链表
在单链表的基础上加入prior前驱指针使得插入、删除操作的时间复杂度变为O1可以很方便地找到前驱 结构体
typedef struct DNode {int data;//数据域struct DNode* prior, * next;//前指针和后指针
} DNode, * DLinkList;初始化
//初始化
bool InitDLinkList(DLinkList L) {L (DNode*)malloc(sizeof(DNode));//分配一个头节点if (L NULL)return false;L-prior NULL;//头节点前后指针都指向空L-next NULL;return true;
}
判空
//判空
bool Empty(DLinkList L) {return (L-next NULL);
}
后插
//指定节点的后插操作
bool InsertNextElem(DNode* p, DNode* s) {s-next p-next;if (p-next ! NULL){p-next-prior s;//防止出现p后面没有后继结点的情况}s-prior p;p-next s;
}
删除p后继结点
//删除P节点的后继节点
bool DeleteNextNode(DNode* p) {if (p NULL)return false;//p节点为空DNode* q p-next;if (q NULL)return false;//P节点没有后继p-next q-next;if (q-next ! NULL)//q不是最后一个节点q-next-prior p;free(q);//手动释放内存空间return true;
}
销毁整个表
//销毁整个表
bool DestroyList(DLinkList L) {//循环删除并释放每个节点while (L-next ! NULL)DeleteNextNode(L);free(L);//释放头节点L NULL;//头指针指向NULL
}
循环链表
循环链表的最后一个指针不是NULL而是改为指向头结点。
循环单链表
结构体
typedef struct LNode {int data;struct LNode* next;
}LNode, * LinkList;
初始化
//初始化一个循环单链表
bool InitRLinkList(LinkList L) {L (LNode*)malloc(sizeof(LNode));//分配一个头节点if (L NULL)return false;//内存不足分配失败L-next L;//头节点nex指向头节点以此形成循环链表return true;
}判空
bool Empty(LinkList L)
{if (L-next L)return true;elsereturn false;
}判尾
//判断P是不是表尾指针
bool IsTail(LinkList L, LNode* p) {return (p-next L);
}循环双链表
结构体
typedef struct DNode {int data;struct DNode* prior, * next;
}DNode, * DLinkList;初始化
//初始化
bool InitRDLinkList(DLinkList L) {L (DNode*)malloc(sizeof(DNode));//分配头节点if (L NULL)return false;L-prior L;L-next L;//循环抱住自己return true;
}判尾
//判断节点p是不是循环双链表的表尾节点
bool iTail(DLinkList L, DNode* p) {return (p-next L);
}插入
//在p节点之后插入s节点
bool InsertNextDNode(DNode* p, DNode* s) {s-next p-next;p-next-prior s;s-prior p;p-next s;return true;
}
删除
//删除操作
bool DeleteNextDNode(DLinkList L, DNode* p) {DNode* q p-next;p-next q-next;q-next-prior p;free(q);return true;
}静态链表
静态链表借助数组来描述线性表的线性存储结构这里的指针next记录的是结点的相对地址数组下标又称游标和顺序表一样静态链表也要预先分配一块连续的内存空间。 静态链表以next-1作为结束标志插入、删除操作与动态链表的相同只需要修改指针而不需要移动元素。
结构体
//第一种定义方法
struct Node0 {int data;//存储数据元素int next;//下一个元素的数组下标
};
typedef struct Node SLinkList[MaxSize];//第二种定义方法
typedef struct Node {int data;int next;
}SLinkList[MaxSize];优点增删操作不需要大量移动元素
缺点不能随机存取只能从头结点开始一次往后查找容量固定不可变
顺序表链表比较
逻辑结构
都属于线性表都是线性结构。
采用顺序存储时逻辑上相邻的元素物理存储位置也相邻采用链式存储时逻辑上相邻的元素物理存储位置不一定相邻逻辑关系通过指针链接表示。
存储结构 基本操作 总结 主要参考王道考研课程 后续会持续更新考研408部分的学习笔记欢迎关注。 github仓库含所有相关源码408数据结构笔记
