做外包网站搭建,长沙网站定制公司,wordpress+移动端编辑器,托者设计吧官网声明单链表的结构体成员
struct LNode {int data;struct LNode *next;
};typedef struct LNode LNode;// 或者: 两者是等价的
typedef struct LNode {int data;struct LNode *next;
}LNode;按位序插入元素e#xff1a;就是在第i个位置插入新结点#xff0c;数据域为e
以下带…声明单链表的结构体成员
struct LNode {int data;struct LNode *next;
};typedef struct LNode LNode;// 或者: 两者是等价的
typedef struct LNode {int data;struct LNode *next;
}LNode;按位序插入元素e就是在第i个位置插入新结点数据域为e
以下带头结点的
思路在第i个位置插入就要找到第i-1个位置然后在它的后面分配存储空间创建新结点再改变新结点以及其左右结点的指针指向完成插入
由于单链表不具有随机存取的特点不能想找i就找i只能从头开始依次遍历也就是从头指针L开始即第0个结点因为一开始的时候L是指向第一个i1结点的就要用到循环由于有条件判断就用了while循环单链表具有指针域声明的L头指针是指向链表的第一个实际元素的但是L的指向不能动它必须指向链表的第一个元素所以就要再声明一个新的指针变量p让它初始化指向单链表的第一个结点即让pL以此实现从头开始遍历遍历到第i-1个位置就可以停止在其后面创建结点分配存储空间怎么能用代码表示新结点一定是在i-1结点的后面呢让新结点的指针域指向i-1的指向再让i-1的指针域指向新结点通过指针完成再给新结点的数据域赋值e新结点就插入完成了注意为了代码的健壮性在执行上述代码时我觉得有几个要注意的地方:
首先要确保查找的位序是合法的不然就不要执行了会报错的位序i从1开始最多只能在第1 个位置插入新结点1肯定不合法其次如果查找的位序根本就不存在当前的单链表中那么while循环走到最后p指针应该是指向NULL指向NULL的时候就不要再继续循环了因为后面以及没有结点了最后由于是动态声明的单链表可以动态分配存储空间就不存在空间满了不能插入的情况可以不做这个兼容
代码
bool ListInsert(LinkList L, int i, int e) {LNode *p;int j0;pL;if(i1) {return false; // 位序不合法返回false停止指向插入操作}while(p!NULL ji-1) {pp-next; // p结点的指针域存储的下一结点的地址赋值给p结点表示p结点此时就走到了原p的下一节点此时的P的指针域存的就是原p下一结点的指针域存的结点地址// 不能写成p-nextp,因为p-nextp表示p指针域指向的元素是p结点就是自己指向自己了j;}// 如果循环完整个单链表都没有找到要找的位序最后p应该是指向null如果p指向null就不应该再指向插入操作了if(pNULL) {// 我感觉p最后会走向NULL说明要找的位序都超过单链表的长度了其实也可以在i1的时候加个条件判断iL.length也可以吧return false;}// 找到i-1,跳出循环此时p指针指向i-1// 假设原顺序是p-q-r现在想在p和q之间插入s值为eLNode *s (LNode *)malloc(sizeof(LNode));s-datae;s-nextp-next; // p-nextp结点的指针域存储下一结点的地址即q结点的地址// s-nexts结点的指针域存储下一结点的地址 // 将p结点的下一结点地址即q结点的地址赋值给s结点的指针域存储也就是说此时s指向的下一结点是qp-nexts; // s表示新结点p-next表示p的指针域存储下一结点的地址// s赋值给p-next就是说p指向的下一节点是s即形成了p-s-q-rreturn true;
}分析一下时间复杂度
最好时间复杂度i1时循环0次O(1)最坏时间复杂度插在表尾in循环n-1次O(n)平均时间复杂度插在除表头和表尾之外的任意位置他们的概率都是一样的p1/(n-1) 平均循环次数总次数*概率(123…n-1)*1/(n-1)n(n-1)/2 * 1/(n-1) n/2O(n)
以下是不带头结点的
请注意头指针L和头结点是两个东西一个单链表它可以没有头结点但它一定有头指针头指针指向链表的第一个结点如果链表带头结点头指针L就指向头结点头结点不存储数据如果链表不带头结点头指针L就指向链表的第一个实际结点
思路在第i个位置插入结点就要找到第i-1个结点在它的后面创建新结点给新结点分配存储空间然后通过改变指针指向来实现与带头结点的步骤一致。
只是有一点此时考虑的是不带头结点的单链表所以L指向第一个实际结点在位序i1的位置插入结点时找i-1的位置就找不到因为原先是把头结点当作位序为0的位置做插入的。所以此时就要单独考虑i1时的情况。
i1时第一个结点前面是头指针L应该让头指针L指向新插入的i1的结点让新插入的i1的结点的指针域存储原i1的结点的地址也就是原先头指针L存储的地址原先带头结点的单链表查找i是从0开始遍历的因为头结点可看作位序为0的结点在第1个位置插入就是在头结点后面插所以要从i-00开始遍历。现在没有头结点i1的位置单独写逻辑了只要考虑从第二个位置开始之后的也就是从i-11开始遍历
bool inserList_Nohead(LinkList L, int i, int e) {if(i1) {return false;}if(i1) {LNode *s(LNode *)malloc(sizeof(LNode));s-datae;s-nextL;Ls;}int j1;LNode *p;pL;// 以下这段和上面带头结点的插入其实是一样的可以用一个函数调用就不要写那么多代码了while(p!NULL ji-1) {pp-next; // p-next:p结点的指针域存储下一结点的地址赋值给p结点就表示此时p结点变成了下一节点// 如果写成p-nextp就表示p结点的指针域存储的结点是p结点就是自己指向自己这个链表就断了j;}if(pNULL) {return false;}LNode *s(LNode *)malloc(sizeof(LNode));s-datae;s-nextp-next;p-nexts;return true;
}
