C语言数据结构线性表（2）

谁借莪１个温暖的怀抱￠ 2022-12-13 11:22 131阅读 0赞

首先通过一段代码回顾一下前天学习的知识吧！  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center]  
该代码表示的是从线性表的顺序存储结构中删除一个元素。

线性表的插入元素和删除元素同通过代码实现了，现在分析一下插入和删除的时间复杂度：

**最好的情况**：插入和删除操作刚好要求在最后一个位置操作，因为不需要移动任何元素，所以此时的时间复杂度为O（1）。

**最坏的情况**：如果要插入和删除的位置是第一个元素，那就意味着要移动所有的元素向后或向前，所以这个时间复杂度为O（n）其中n为线性表中元素的个数。

**至于平均情况**，就取中间值O（（n-1）/2）  
根据之前所说的计算时间复杂度的规律，平均复杂度简化后还是O（n）。

**总结**：线性表的顺序存储结构，在存、读取数据时，不管是哪一个位置，时间复杂度都  
O（1）。而在插入或删除时，时间复杂度都是O（n）。从这里可以看出顺序存储结构它比较适合元素个数比较稳定，不经常插入和删除元素，而更多的操作是存取数据的应用。

**线性表的优缺点：**  
优点：  
——不必为表示表中元素之间的逻辑关系而增加额外的存储空间。  
——可以快速的存取表中任意位置的元素。  
缺点：  
——插入和删除元素需要大量移动元素。  
——当线性表长度变化较大时，难以确定存储空间的容量。

**线性表的链式存储结构**  
线性表的链式存储结构的特点是：用一组任意的存储单元存储线性表的数据元素，这组存储单元可以存在内存中未被占用的任意位置。其次，链式存储结构每一个结点包括**数据域**和**指针域**，数据域存储他本身的信息，指针域存储它的后继元素的存储地址。如果每一个结点只包含一个指针域，就叫做单链表。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 1]  
线性表都是有头有尾的，我们把链表中的第一个结点的存储位置叫做头指针，最后一个结点指针为空（NULL）。

**头指针与头结点的异同**：  
头指针：  
——头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针。  
——头指针具有标识作用，所以 通常头指针冠以链表的名字（指针变量的名字）。  
——无论链表是否为空，头指针均不为空。  
——头指针是链表的必要元素。  
头结点：  
——头结点是为了操作的统一和方便而设立的，放在第一个元素的结点之前，其数据域一般无意义  
——有了头结点，对在第一元素结点前插入结点和删除第一结点的操作与其他结点的操作就统一了。  
——头结点不一定是链表的必须元素。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 2]  
![在这里插入图片描述][20201011093042769.png_pic_center]  
在链式存储结构中，数据的读取相比顺序存储结构就比较复杂，获得链表第i个数据的一般步骤是：  
——声明一个结点p指向链表第一个结点，初始化j从1开始；  
——当j<i时，就遍历链表，让p的支支唔向后移动，不断指向一下结点，j+1；  
——若到链表末尾p为空，则说明第i个元素不存在；  
——若查找成功，则返回结点p的数据。

**单链表的插入：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 3]  
![在这里插入图片描述][20201011094352439.png_pic_center]**这两个代码是绝对不可以弄反的！！！**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 4]  
单链表的插入代码实现：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 5]

**单链表的删除：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 6]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 7]  
代码实现：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 8]  
从上面分析可以看出，对于插入或删除越频繁的操作，单链表的效率优势就越是明显。  
下次开始学习线性表7！！！！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/9f735593af274d8ba013fd470b9ee9da.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/3fd6ca15cee847c8aaa0d8db05da70e4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/7f92f57f5bfa452b8a1a2ffca7a3ef12.png
[20201011093042769.png_pic_center]: /images/20221123/4b1a1d2354654c05a1dd7147deb87d65.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/5253ce58a9a64594b343f895c2bb2c68.png
[20201011094352439.png_pic_center]: /images/20221123/0d5b69e7c54b410188f129aa227ae329.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221123/56c544ab77b842ae8bef1542a227face.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221123/2ae8e94a41d543bda5180b7b57e02e28.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221123/a13f35c8b601426db1a0afbb1198342b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221123/bb307e4a49054a6d812c26cab9fe5724.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20221123/26c57220cefd474989171b1bd06a9959.png