单链表

发表于 更新于 分类于 Disqus： 本文字数： 1.7k 阅读时长 ≈ 3 分钟

2-3 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用什么存储方式最节省运算时间？ (2分)b

  1. 单链表
  2. 仅有尾指针的单循环链表
  3. 仅有头指针的单循环链表
  4. 双链表

c虽然可以直接获得第一个元素，但是想要获得最后一个元素却需要遍历整个链表。而b给出的是带有尾结点的单循环链表，这样就可以直接得到最后一个元素，想要得到第一个元素只需要再遍历一个元素就可以，所以选择b

1-22下列函数试图求链式存储的线性表的表长，是否正确？

1
2
3
4
5
6
7
8
9
int  Length ( List  *PtrL )
{    List  *p = PtrL;      
     int  j = 0;
     while ( p ) { 
           p++; 
           j++;                 
     }   
     return  j;
}

F p++不能指向后一个元素

2-4

若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用哪种存储方式最节省运算时间？ (2分)

  1. 单链表
  2. 双链表
  3. 单循环链表
  4. 带头结点的双循环链表

D 头结点上一个就是最后一个节点

这道题的逻辑，简单来说，就是地址存放你当前元素的地址，链接地址是指向当前元素的下一个元素的地址。 因此，我们来看没插入f之前时，链表的顺序，由于头元素是c（地址1008H），由C开始，C的链接地址是1000H，也就是指向元素a（地址1000H），之后a的链接地址是1010H，也就是指向元素e。。。 按照上面这个思路遍历，我们可以得到链表的遍历顺序c（1008H）->a（1000H）->e（1010H）->b（1004H）->d（100CH）->null。 由于f逻辑上位于a和e之间，因此也就是说将f插入到ae之间，因此只需要修改a的链接地址（也就是指向下一个元素的地址）为f的地址（1014H），然后将f的链接地址修改为e的地址。
链表插入不影响其他元素，所以其他元素链接地址不变。

不带表头结点，头指针直接指向数据

在m之后

在一个长度为 n （ n>1 ）的单链表上，设有头和尾两个指针，执行 操作与链表的长度有关。

  • 删除单链表中的第一个元素
  • 删除单链表中的最后一个元素
  • 在单链表第一个元素前插入一个新元素
  • 在单链表最后一个元素后插入一个新元素

A
头指针是指向第一个元素（结点）的指针。 当删除单链表中的第一个元素时只需要将头指针指向第二个元素，然后释放第一个元素储存空间申请的内存。与链表长度无关。

123

ListNode *temp = head->next;``head->next = temp->next;``free``(temp);

B
尾指针是指向最后一个元素（结点）的指针，与头指针类似。 当删除单链表中的最后一个元素时 由于不是双向链表，所以要从头指针开始，一直遍历直到倒数第二个元素，将倒数第二个元素（结点）指向NULL，释放原末端元素（结点）空间后，将尾指针等于新的末端元素（结点）。所以与链表长度有关。

12345

ListNode *p = head;``while``(p->next != rear) p = p->next;``p->next = NULL;``free``(r);``r = p;

C 在单链表第一个元素前插入一个新元素时，只需要把新的元素（结点）指向原来的第一个元素（结点），然后使头指针指向新的元素（结点）。与链表长度无关。

12

new_point->next = head->next;``head->next = new_point;

D 在单链表最后一个元素后插入一个新元素时，只需先将新结点指向NULL，然后将尾指针指向的原末端结点指向新的元素（结点），最后将尾指针指向新的元素（结点）。与链表长度无关。

123

new_point->next = NULL;``rear->next = new_point;``rear = new_point;

静态链表:数组的每一个下标都对应一个data和一个cur。数据域data用来存放数据元素，；而游标cur相当于单链表中的next指针，

存放该元素的后继在数组中的下标。