单链表问题解答
1、链式结构的特点:
用一组任意的存储单元存储线性表的数据元素,这组存储单元可以是连续的,也可以是不连续的。这就意味着,这可以存在内存未被占用的任意位置。
2、在链式结构中如何存储元素:
表示每个数据元素ai与其直接后继数据元素aM之间的逻辑关系,对 数据元素ai来说,除了存储其本身的信息之外,还需存储一个指示其直接后继的信息 (即直接后继的存储位置)。我们把存储数据元素信息的域称为数据域,把存储直接后 继位置的域称为指针域。指针域中存储的信息称做指针或链。这两部分信息组成数据 元素ai的存储映像,称为结点(Node)。
3、头指针和头结点的定义和区别?
把链表中第一个结点的存储位置叫做头指针;
在单链表的第一个结点前附设一个结点,称为头结点。
区别:
(1)头指针是指链表指向第一个结点的指针,若链表有头结点,则是指向头结点的指针;头结点是为了操作的统一和方便而设立的,放在第一元素的结点之前,其数据域一般无意义(也可存放链表的长度)。
(2)头指针具有标识作用,所以常用头指针冠以链表的名字;有了头结点,对在第一元素结点前插入结点和删除第一结点,其操作与其他结点的操作就统一了。
(3)无论链表是否为空,头指针均不为空。头指针是链表的必要元素;头结点不一定是链表必须元素。
4、单链表
简单链表:
带头结点的单链表:
空链表:
5、 获得链表第i个数据的算法思路:
① 声明一个结点p指向链表第一个结点,初始化j从1开始;
② 当j<i时,就遍历链表,让p的指针向后移动,不断指向下一结点,j累加1;
③ 若到链表末尾p为空,则说明第i个元素不存在;
④ 否则查找成功,返回结点p的数据。
6、单链表如何插入结点?
(1)声明一结点P指向链表第一个结点,初始化j从1开始;
(2)当j < i时,就遍历链表,让p的指针向后移动,不断指向下一结点,j累加1;
(3)若到链表末尾p为空,则说明第i个元素不存在;
(4)否则查找成功,在系统中生成个空结点s;
(5)将数据元素e赋值给s->data;
(6)单链表的插入标准语句s->next=p->next,p->next=s;
(7)返回成功。
7、单链表第i个数据删除结点的算法思路:
1. 声明一结点P指向链表第一个结点,初始化j从1开始;
2.当j<i时,就遍历链表,让p的指针向后移动,不断指向下一个结点,j累加 1;
3.若到链表末尾p为空,则说明第i个元素不存在;
4.则查找成功,将欲删除的结点p->next賦值给q;
5. 单链表的删除标准语句p->next=q->next;
6.将q结点中的数据赋值给e,作为返回;
7.释放q结点。
8、单链表的整表创建的实现
(1)声明一结点p和计数器变量i;
(2)初始化一空链表L;
(3)让L的头结点的指针指向NULL,即建立一个带头结点的单链表;
(4)循环:
<1> 生成一新结点赋值给p;
<2> 随机生成一数字赋值给p的数据域p->data;
<3> 将p插入到头结点与前一新结点之间。
9、单链表结构与顺序存储结构分别有什么优缺点?
(1)存储分配方式:顺序存储结构用一段连续的存储单元依次存储线性表的数据元素;单链表采用链式存储结构,用一组任意的存储单元存放线性表的元素。
(2)时间性能:查找;顺序存储结构0(1);单链表0(n);插入和删除;顺序存储结构需要平均移动表长一半的元素,时间为0(n);单链表在线出某位置的指针后,插入和删除时间仅为0(1)。
(3)空间性能:顺序存储结构需要预分配存储空间,分大了,浪费,分小了易发生上溢;单链表不需要分配存储空间,只要有就可以分配,元素个数也不受限制。
10、应用中,单链表结构与顺序表结构应当如何选择?
(1)若线性表需要频繁查找,很少进行插入和删除操作时,宜采用顺序存储结构。若需要频繁插入和删除时,宜采用单链表结构;
(2)当线性表中的元素个数变化较大或者根本不知道有多大时,最好用单链表结构,这样可以不需要考虑存储空间大小问题;而若事先知道线性表的大致长度,用顺序存储结构效率较高。