一、顺序表
【顺序表是什么/数组与顺序表的区别】
1、数组和顺序表的区别在哪里?
答
:顺序表体现了数据元素之间的线性关系,即一对一的关系,以及对数据元素定义的一组运算操作,所以操作起来比数组更容易实现、方便操作,而数组只是物理区域上的一组连续的存储单元,它是具有相同类型的若干元素按无序的形式组织起的一种形式。
二、链表
【头指针与头结点的区别】
1、说明在线性表的链式存储结构中,头指针与头结点之间的根本区别,头结点与首元结点的关系。
答
:①头指针具有标识作用,常用头指针代指链表的名称,同时可以防止链表为空;头结点的设置可以使插入或删除操作统一起来并且方便。
②首元结点是第一个元素结点,即头结点后的第一个结点。
【带头结点的单链表】
2、单链表设置头结点的作用是?
答
:①防止单链表为空,若单链表为空时,则为一个空链表,即头结点L→next=NULL;
②保证了插入元素和删除元素操作的统一性,带有头结点的单链表,其存储位置存放在头结点L的指针域中,指向单链表的第一个结点。
【链表的分类】
3、链表可以通过指针分为哪些类别?
答
:根据线性表的链式存储结构中每一个结点包含的指针个数,可将线性链表分成单链表和双链表,而又根据指针的连接方式,链表又可分成静态链表和(动态)链表。
三、顺序表与链表的对比
【顺序表和链表存储方式的区别】
1、简述顺序表和链表存储方式的特点。
答
:①顺序表实现简单,可以随机存取,其存储密度大,但是执行插入、删除操作需要移动大量元素,效率低,另外其存储空间需事先分配,容易造成空间浪费或溢出。
②链表不支持随机存取,只能顺序存取,通过指针来体现元素之间的逻辑关系,存储密度比顺序表小,其执行插入、删除操作不需要移动元素,只需修改指针,效率高,另外它还支持动态分配存储空间,不会造成空间浪费或溢出。
【不同存储结构中数据元素之间的逻辑关系】
2、顺序存储结构和链式存储结构分别是通过什么来表示数据元素之间的逻辑关系的?
答
:顺序存储结构是通过物理上相邻的地址来表示逻辑关系,而链式存储结构是通过指针来表示逻辑关系。
【线性表存储结构的选用】
3、若线性表插入和删除操作比较频繁,则宜采用什么存储结构?为什么?
答
:链式存储结构,采用该结构在执行插入、删除操作时不需移动大量元素,只需修改指针,且可以支持存储空间的动态分配。
四、循环链表
【循环单链表的优点】
1、循环单链表最大的优点是什么?
答
:循环单链表中从任一结点出发都可以访问到链表中的每一个元素。
五、静态链表
【静态链表的概念】
1、简述静态链表的定义以及其优缺点。
答
:静态链表借助数组来描述链式结构,每个数组元素有两个分量,一是数据元素的值,二是指针,指针指向下一个元素在数组中的位置 (下标)。静态链表插入和删除操作时只需修改指针,而不需要不移动数据,但是静态链表不能随机存取。另外,若定义的数组太大,有可能浪费较多的存储空间。
六、单链表的插入删除代码
【单链表的插入】
1、单链表中,在指针 *p 所指向的结点之后插入结点 *q,写出关键代码。
答
:先将 *q与原本 *p的指针域指向的结点,再与p相连【先连后,再连前】,代码如下:
q->next=p->next;
p->next=q;
2、在单链表中在 *p的前插入一个 *q指向的新结点,以temp为中间变量,写出关键代码。
答
:通过中间变量temp来交换数据域data的代码部分,【先后插,再交换】,代码如下:
q->next=p->next;
p->next=q;
temp=p->data; //交换数据域
p->data=q->data;
q->data=temp;
【单链表的删除】
1、在单链表中删除一个以前驱*p,*q指向的结点,写出关键代码。
答
:查找后删除的步骤可概括为【先定位,后断开释放】,将*q指针指向要删除的结点,p为其前驱结点,代码如下:
q=p->next; //先定位,定位删除位置
p->next=q->next; //断开q与p的连接,p与下一个结点连接
free(q); //通过free()函数进行释放
2、在单链表中删除*p指向的结点,写出关键代码。
答
:通过交换两个指针的数据域,交换两个指针的数据域,然后通过free()函数删除后继结点,代码如下:
q=p->next; //先定位,定位删除位置
p->data=p->next->data; //与后继结点交换数据域data
p->next=q->next; //断开q与p的连接,p与下一个结点连接
free(q); //通过free()函数进行释放
七、双链表的插入删除代码
【双链表的插入】
1、双链表中,在指针 *p 所指向的结点之后插入结点 *q,写出关键代码。
答
:双链表的插入操作可以概括为【先连后,后连前】,代码如下:
q->next=p->next;
p->next->prior=q;
q->prior=p;
p->next=q;
【双链表的删除】
1、双链表中,删除指针 *p 所指向的结点之后的结点 *q,写出关键代码。
答
:代码如下:
p->next=q->next;
q->next->prior=p;
free(q);
八、循环单链表的插入删除代码
【循环单链表的插入】
1、循环单链表中,在指针 *p 所指向的结点之后插入结点 *q,写出关键代码。
答
:循环单链表的插入操作与单链表类似,也是【先连后,再连前】,代码如下:
q->next=p->next; //先连后
p->next=q; //再连前
【循环单链表的删除】
1、循环单链表中,在指针 *p 所指向的结点之后插入结点 *q,写出关键代码。
答
:循环单链表的删除操作也与单链表类似,删除的步骤可概括为【先定位,后断开释放】,代码如下:
q=p->next; //先定位,定位删除位置
p->next=q->next; //断开q与p的连接,p与下一个结点连接
free(q); //free()函数释放结点
九、循环双链表的插入删除代码
【循环双链表的插入】
1、循环双链表中,在指针 *p 所指向的结点之后插入结点 *q,写出关键代码。
答
:p结点为新结点q的前驱结点,代码如下:
q->next=p->next;
p->next->prior=q;
q->prior=p;
p->next=q;
【循环双链表的删除】
1、循环双链表中,删除*p指向的结点,写出关键代码。
答
:将*p指针指向要删除的结点,代码如下:文章来源:https://www.toymoban.com/news/detail-738105.html
p->next->prior=p->prior;
p->prior->next=p->next;
free(p);
文章来源地址https://www.toymoban.com/news/detail-738105.html
到了这里,关于【数据结构】——线性表简答题模板的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!