德州网站建设推广价格,徐州seo建站,个人网站页脚设计,网站内优化怎么做顺序表与链表的比较 导言一、线性表二、线性表的存储结构三、顺序表和链表的相同点四、顺序表与链表之间的差异五、存储结构的选择六、静态顺序表的基本操作七、无头结点单链表的基本操作结语 导言
大家好#xff0c;很高兴又和大家见面啦#xff01;#xff01;#xff0… 顺序表与链表的比较 导言一、线性表二、线性表的存储结构三、顺序表和链表的相同点四、顺序表与链表之间的差异五、存储结构的选择六、静态顺序表的基本操作七、无头结点单链表的基本操作结语 导言
大家好很高兴又和大家见面啦
经过这段时间的学习与分享想必大家跟我一样都已经对线性表的相关内容比较熟悉了。为了更好的巩固线性表相关的知识点下面我们一起将线性表这个章节的内容梳理一遍吧。
一、线性表 线性表的相关概念 线性表时具有相同数据类型的 n ( n 0 ) n(n0) n(n0)个数据元素的有限序列其中 n n n为表长当 n 0 n0 n0时线性表是一个空表。
如果我们以 a i ( 1 i n ) a_i(1in) ai(1in)作为线性表的各个元素时元素 a 1 a_1 a1为线性表唯一的第一个元素称为表头元素元素 a n a_n an为线性表唯一的最后一个元素称为表尾元素。 线性表的逻辑特性是 除了表头元素外每个元素有且仅有一个直接前驱除了表尾元素外每个元素有且仅有一个直接后继。 线性表的特点是 表中元素的个数是有限的表中元素具有逻辑上的顺序性表中元素有其先后次序表中元素都是数据元素每个元素都是单个元素表中元素的数据类型都相同这意味着每个元素所占空间大小相同表中元素具有抽象性即仅讨论元素间的逻辑关系而不考虑元素的内容 线性表的基本操作 创建与销毁 InitList(L)初始化表。构造一个空的线性表DestroyList(L)销毁操作。销毁线性表并释放线性表L所占用的内存空间。 插入与删除 ListInSERT(L,i,e)插入操作。在表L中第i个位置插入指定元素eListDelete(L,i,e)删除操作。删除表L中第i个位置的元素并用e返回删除元素的值 查找 LocateElem(L,e)按值查找操作。在表L中查找具有给定关键字值的元素GetElem(L,i)按位查找操作。获取表L中第i个位置的元素的值 其它操作 Length(L)求表长。返回线性表L的长度即L中数据元素的个数PrintList(L)输出操作。按前后顺序输出线性表L的所有元素值Empty(L)判空操作。若L为空表则返回true否则返回false 复习完了线性表的相关知识点下面我们来看一下线性表的两种存储结构
二、线性表的存储结构
线性表的各元素在内存中存储时满足在逻辑上相邻也在物理位置上相邻这样的存储结构称为顺序存储又称为顺序表。通常用高级程序设计语言中的数组来表示顺序存储结构。
线性表中的各个元素在内存中存储时满足在逻辑上相邻在物理位置上不一定相邻元素与元素之间通过“链”建立起来的逻辑关系这样的存储结构称为链式存储又称为链表。 对于顺序表和链表它们又有哪些异同点呢
三、顺序表和链表的相同点
顺序表和链表的相同点都是建立在它们的本质上面的下面我们就来看看它们具有哪些相同点 顺序表和链表的元素个数都是有限的顺序表和链表的元素类型都是相同的顺序表和链表的元素都满足在逻辑上相邻顺序表和链表的元素都是数据元素且每个元素都是单一元素顺序表和链表的元素都满足只有一个唯一的表头元素和一个唯一的表尾元素顺序表和链表的逻辑特性都是 除了表头元素外每个元素都有且仅有一个直接前驱除了表尾元素外每个元素都有且仅有一个直接后继 循序表和链表都能进行创建、销毁、增删改查等基本操作顺序表和链表在金泰 因此我们可以得到结论
顺序表和链表的本质都是线性表只不过线性表强调的数据元素在内存上的逻辑结构而顺序表与链表强调的是数据元素在内存上的存储结构 介绍完了顺序表与链表的相同点接下来我们继续来看一看它们的不同点
四、顺序表与链表之间的差异 存取方式不同 顺序表是顺序存取结构同时也是随机存取结构链表是链式存取结构同时也是非随机存取结构
因此我们想要访问顺序表的各个元素时只需要知道元素的下标就可以直接查找到此时的时间复杂度是O(1)而链表想要访问第i个元素时需要从表头开始进行遍历此时的时间复杂度是O(n) 物理结构不同 顺序表的各个元素在物理位置上也是相邻的链表的各个元素在物理位置上不一定相邻
因此顺序表在存储时可以做到密集存储但是需要在内存中消耗一块连续的存储空间而链表在存储时是离散存储的但是需要消耗额外的空间来存放指向下一个结点的指针 创建方式不同 顺序表在创建时需要明确最大表长、当前表长、数据存放的空间链表在创建时需要明确数据域和指针域顺序表在初始化时可以只初始化当前表长链表在初始化时需要对头结点进行初始化链表的表长需要通过额外的计数器来确定
因此顺序表在创建后表的大小是固定的虽然可以通过malloc、calloc和realloc来申请新的空间达到修改表长的目的但是在申请完新的空间后还伴随着大量的复制操作此时的时间复杂度是O(n)而链表在创建时链表的大小是可以随时进行修改的只需要在插入新结点时修改对应结点的指针域就行此时的时间复杂度是O(1) 查找方式不同 顺序表在进行按位查找时可以直接通过位序查找到对应的元素链表在进行按位查找时需要通过从头结点往后进行遍历才能找到对应的元素顺序表在进行按值查找时可以通过不同的查找方式进行快速查找链表在进行按值查找时需要从头结点开始往后进行顺序查找
因此顺序表在进行按位查找时的时间复杂度是O(1)在进行按值查找时的最坏时间复杂度为O(n)而链表在进行按位查找与按值查找的时间复杂度都是O(n) 插入与删除方式不同 顺序表在进行插入与删除时需要移动大量的元素链表在进行插入与删除时只需要修改对应的指针域
因此顺序表的插入与删除操作的时间复杂度为O(n)而链表的插入与删除的时间复杂度为O(1) 空间分配不同 顺序表在进行动态分配时需要申请一块连续的空间且空间大小不能修改链表在进行动态分配时需要申请对应的结点的空间空间大小可以随时修改顺序表在修改表长时需要移动大量的元素链表在修改表长时只需要修改对应结点的指针域
因此顺序表在修改表长时对应的时间复杂度为O(n)而链表在修改表长时对应的时间复杂度为O(1) 在了解了顺序表与链表的异同点后我们又应该如何进行选择呢
五、存储结构的选择
我们在实际运用中要选择对应的存储结构就需要结合具体的情况进行分析。从前面的介绍中我们可以看到顺序表的优势是在查找元素的上面而链表的优势是在增加、删除上面。因此我们在选择时需要考虑以下几点
存储的考虑 在不确定线性表的长度与存储规模时宜采用链表 在确定线性表的表长且需要密集存储时宜采用顺序表 运算的考虑 在表长固定的情况下需要经常对表中元素进行按序号访问时宜采用顺序表 在表长需要进行增加、删除的操作时宜采用链表 环境的考虑 在不支持指针的计算机语言中虽然可以通过静态链表来实现链表但是顺序表会更加简单一点 在支持指针的计算机语言中就需要从存储与运算这两个方面的角度去考虑了。 总之两种存储结构各有长短选择哪一种还是得由实际情况来决定。通常较稳定的线性表选择顺从存储需要平方进行插入、删除操作的线性表选择链式存储。要想更加深刻的理解顺序存储与链式存储之间的优缺点还是需要熟练的掌握它们才行。
六、静态顺序表的基本操作
在前面我们只介绍了动态顺序表的基本操作今天我将补上静态顺序表基本操作其对应的的基本格式如下所示
//顺序表的静态创建
#define MaxSize 10//定义最大表长
typedef struct Sqlist {ElemType data[MaxSize];//存储数据元素的数组int length;//当前表长
}Sqlist;//重命名后的静态顺序表类型名
//顺序表的初始化
bool InitList(Sqlist* L){if (!L)return false;//指针L为空指针时返回falseL-length 0;//初始化当前表长return true;
}
//顺序表的按位查找
ElemType GetElem(Sqlist L, int i){if (i1 || iL.length)//位序小于1或者位序大于当前表长时表示位序不合理return -1;//位序不合理返回-1return L.data[i - 1];//位序合理返回下标为i-1的元素的值
}
//顺序表的按值查找
int LocateElem(Sqlist L, ElemType e) {for (int i 0; i L.length; i){if (L.data[i] e)return i 1;//找到对应的值返回位序i1}return -1;//没有对应的值返回-1
}
//顺序表的插入
bool ListInsert(Sqlist* L, int i, ElemType e) {if (i1 || iL-length 1)//位序小于1或者位序大于当前表长1时表示位序不合理return false;//位序不合理返回falseif (L-length MaxSize)return false;//当前线性表已存满返回falsefor (int j L-length; j i; j--) {L-data[j] L-data[j - 1];//元素往后移动}L-data[i - 1] e;//将元素e插入位序i的位置L-length;//当前表长1return true;//插入成功返回true
}
//顺序表的删除
bool ListDelete(Sqlist* L, int i, ElemType e) {if (i1 || iL-length)//位序小于1或者位序大于当前表长时位序不合理return false;//位序不合理返回falsee L-data[i - 1];for (int j i - 1; j L-length; j) {L-data[j] L-data[j 1];//元素往前移}L-length--;//当前表长-1return true;//删除成功返回true
}七、无头结点单链表的基本操作
前面的介绍中我只介绍了有头结点的单链表与双链表的基本操作这里给大家补上无头结点的单链表的基本操作其对应的格式如下所示
//无头结点单链表的基本操作
//单链表类型的声明
typedef struct LNode {ElemType data;//数据域struct LNode* next;//指针域
}LNode, * LinkList;//重命名后的结点类型与单链表类型名
//单链表的初始化
bool InistList(LinkList* L) {if (!L)return false;//L为空指针时返回falseL NULL;//头指针初始化为空指针return true;//初始化完返回true
}
//单链表的创建——头插法
LinkList List_HeadInsert(LinkList* L){if (!L)return NULL;//当L为空指针时返回NULLLNode* s NULL;//指向表头结点的指针ElemType x 0;//存放数据元素的变量……;//获取数据元素while (x ! EOF)//为创建过程设置一个终点{//头插操作if (!(*L))//单链表为空表时{*L (LNode*)calloc(1, sizeof(LNode));//创建表头结点assert(*L);//创建失败报错(*L)-data x;//将数据元素放入数据域中(*L)-next NULL;//表头结点指针域指向空指针}else {s (LNode*)calloc(1, sizeof(LNode));//创建新结点assert(s);//创建失败报错s-data x;//数据元素存放进数据域中s-next (*L)-next;//新结点指针域指向表头结点(*L)-next s;//头指针指向新结点}……;//获取新的数据元素}return *L;//返回创建好的单链表
}
//单链表的创建——尾插法
LinkList List_TailInsert(LinkList* L) {if (!L)return NULL;//当L为空指针时返回NULLLNode* r NULL;//指向表尾结点的指针LNode* s NULL;//指向新结点的指针ElemType x 0;//存放数据元素的变量……;//获取数据元素while (x ! EOF)//为创建过程设置一个终点{//尾插操作if (!(*L))//单链表为空表时{*L (LNode*)calloc(1, sizeof(LNode));//创建表头结点assert(*L);//创建失败报错(*L)-data x;//将数据元素放入数据域中(*L)-next NULL;//表头结点指针域指向空指针r (*L);//表尾指针指向表头结点此时的表头结点也是表尾结点}else {s (LNode*)calloc(1, sizeof(LNode));//创建新结点assert(s);//创建失败报错s-data x;//数据元素存放进数据域中s-next r-next;//新结点指针域指向表尾结点r-next s;//表尾结点的指针域指向新结点r s;//表尾指针指向新结点}……;//获取新的数据元素}return *L;//返回创建好的单链表
}
//单链表的按位查找
LNode* GetElem(LinkList L, int i) {if (!L)return NULL;//单链表为空表时返回NULLif (i 1)return NULL;//位序不合理时返回NULLint j 1;//单链表结点的位序LNode* s L-next;//指向查找结点的指针while (j i s)//当位序相等时结束查找当s为空指针时结束查找{s s-next;//向后遍历}return s;//查找结束返回当前结点
}
//单链表的按值查找
LNode* LocateElem(LinkList L, ElemType e) {if (!L)return NULL;//当表为空表时返回NULLLNode* s L-next;//指向查找结点的指针while (s-data e s)//当元素相等时结束查找当s为空指针时结束查找{s s-next;//向后遍历}return s;//查找结束返回当前结点
}
//单链表的前插操作——指定结点
bool InsertPriorNode(LNode* p, ElemType e) {if (!p)return false;//p为空指针返回falseLNode* s (LNode*)calloc(1, sizeof(LNode));//创建新结点assert(s);//创建失败报错s-data p-data;//p结点的数据元素放入新结点的数据域中p-data e;//插入的数据元素放入p结点的数据域中s-next p-next;//新结点的指针域指向p结点的后继结点p-next s;//p结点的指针域指向新结点完成插入操作return true;//插入成功返回true
}
//单链表的前插操作——指定位序
bool InsertPriorNode(LinkList* L, int i, ElemType e) {if (!L)return false;//L为空指针时返回falseif (!(*L))return false;//单链表为空表时返回falseif (i 1)return false;//位序不合理时返回falseLNode* p GetElem(*L, i - 1);//指向前驱结点的指针LNode* s (LNode*)calloc(1, sizeof(LNode));//创建新结点assert(s);//创建失败报错s-data e;//数据元素放入新结点的数据域中s-next p-next;//新结点的指针域指向p结点的后继结点p-next s;//p结点的指针域指向新结点完成插入操作return true;//插入成功返回true
}
//单链表的后插操作——指定结点
bool InsertNextNode(LNode* p, ElemType e) {if (!p)return false;//p为空指针返回falseLNode* s (LNode*)calloc(1, sizeof(LNode));//创建新结点assert(s);//创建失败报错s-data e;//数据元素放入新结点的数据域中s-next p-next;//新结点的指针域指向p结点的后继结点p-next s;//p结点的指针域指向新结点完成插入操作return true;//插入成功返回true
}
//单链表的后插操作——指点位序
bool InsertNextNode(LinkList* L, int i, ElemType e) {if (!L)return false;//L为空指针时返回falseif (!(*L))return false;//单链表为空表时返回falseif (i 1)return false;//位序不合理时返回falseLNode* p GetElem(*L, i);//指向位序i结点的指针if (!p)return false;//结点p为空指针时返回falseLNode* s (LNode*)calloc(1, sizeof(LNode));//创建新结点assert(s);//创建失败报错s-data e;//数据元素放入新结点的数据域中s-next p-next;//新结点的指针域指向p结点的后继结点p-next s;//p结点的指针域指向新结点完成插入操作return true;//插入成功返回true
}
//单链表的删除操作——指定位序
bool ListDelete(LinkList* L, int i, ElemType e) {if (!L)return false;//L为空指针时返回falseif (!(*L))return false;//单链表为空表时返回falseif (i 1)return false;//位序不合理时返回falseLNode* p GetElem(*L, i - 1);//位序i的前驱结点if (!p)return false;//结点p为空指针时返回falseLNode* q p-next;//需要删除的结点if (!q)return false;//结点q为空指针时返回falsee q-data;//需要删除的元素存放在变量e中p-next q-next;//前驱结点的指针域指向删除结点的后继结点free(q);//释放被删除的结点空间return true;//删除完成返回true
}
//单链表的删除操作——指定结点
bool ListDelete(LinkList* L,LNode* p, ElemType e) {if (!L)return false;//L为空指针时返回falseif (!(*L))return false;//单链表为空表时返回falseif (!p)return false;//p为空指针时返回falseLNode* q (*L)-next;//指向前驱结点的指针while (q-next ! p)//判断q是否为p的前驱结点{q q-next;//向后遍历}q-next p-next;//前驱结点指向删除结点的后继结点free(p);//释放删除结点的空间return true;//删除完成返回true
}结语
到这里咱们今天的内容就全部介绍完了线性表的相关知识点也全部介绍完了希望这些内容能帮助大家更好的学习线性表。 接下来我们将开始进入数据结构——栈、队列和数组的学习大家记得关注哦最后感谢各位的翻阅咱们下一篇再见
