typedef struct LNode { int data; struct LNode *next; }LNode, *LinkList;
带头结点的按位序插入：
//在第i个位置插入元素e bool ListInsert(LinkList &L, int i, char e) { if (i < 1) return false; LNode *p; //p指向当前扫描到的结点 int j = 0; //当前p指向的是第几个结点 p = L; //L指向头结点,第0个结点 while (p != NULL && j < i - 1) { //循环找到要插入结点的前一个结点 p = p->next; j++; } if (p == NULL) //i值不合法（最后一个结点指向NULL，这是要在NULL的后边插入） return false; LNode *s = （LNode *）malloc（sizeof(LNode)）; //新结点 s->data = e; s->next = p->next; p->next = s; return true; }
不带头结点的按位序插入：（对于插入第一个结点时需要特殊处理，其他部分与带头结点的一样）
bool ListInsert(LinkList &L, int i, char e) { if (i == 1) { LNode *s = （LNode *）malloc（sizeof(LNode)）; s->data = e; s->next = L; L = s; return true } if (i < 1) return false; LNode *p; //p指向当前扫描到的结点 int j = 0; //当前p指向的是第几个结点 p = L; //L指向头结点,第0个结点 while (p != NULL && j < i - 1) { //循环找到要插入结点的前一个结点 p = p->next; j++; } if (p == NULL) //i值不合法（最后一个结点指向NULL，这是要在NULL的后边插入） return false; LNode *s = （LNode *）malloc（sizeof(LNode)）; //新结点 s->data = e; s->next = p->next; p->next = s; return true; }
指定结点的后插操作：
//在p结点之后插入元素e bool InsertNextNode(LNode *p, char e) { if (p == NULL) return false; LNode *s = （LNode *）malloc（sizeof(LNode)）; if (s == NULL) return false; //内存分配失败 s->data = e; s->next = p->next; p->next = s; return true; }
这里的后插操作其实就相当于已经找到了p，和按位序插入while循环后边的代码一样了，所以按位序插入后边部分可以调用这个函数：
//在第i个位置插入元素e bool ListInsert(LinkList &L, int i, char e) { if (i < 1) return false; LNode *p; //p指向当前扫描到的结点 int j = 0; //当前p指向的是第几个结点 p = L; //L指向头结点,第0个结点 while (p != NULL && j < i - 1) { //循环找到要插入结点的前一个结点 p = p->next; j++; }
return InsertNextNode(p,e);
}
指定结点的前插操作：
如果给了头指针的话，只需要循环查找到要插入结点的前一个结点，然后插入即可
//在p结点之前插入元素e bool InsertPriorNode(LinkList L, LNode *p, char e)
然而如果不给头指针的话，就需要偷天换日一下，把新结点插入到p结点后边，然后把新结点的数据元素和和p结点互换，逻辑上实现同样的效果
//在p结点之前插入元素e bool InsertPriorNode(LNode *p, char e) { if (p == NULL) return false; LNode *s = （LNode *）malloc（sizeof(LNode)）; if (s == NULL) return false; //内存分配失败 s->next = p->next; p->next = s; s->data = p->data; p->data = e; return true; }
如果是直接传入了结点s，道理是一样的；
//在p结点之前插入结点s bool InsertPriorNode(LNode *p, LNode *s) { if (p == NULL || s == NULL) return false; s->next = p->next; p->next = s; char temp = p->data; p->data = s->data; s->data = temp; return true; }
按位序删除（带头结点）：
前半部分与插入结点一样，先循环查找p
//删除表L中第i个位置的元素，并用e返回删除元素的值 bool ListDelete(LinkList &L, int i, char &e) { if (i < 1) return false; LNode *p; //p指向当前扫描到的结点 int j = 0; //当前p指向的是第几个结点 p = L; //L指向头结点,第0个结点 while (p != NULL && j < i - 1) { p = p->next; j++; } if (p == NULL) return false; if (p->next == NULL) return false; LNode *q = p->next; //令q指向被删除的结点 e = q->data; //用e返回被删的值 p->next = q->next; //断开连接 free(q); //释放被删结点空间 return true; }
指定结点的删除：
删除结点p，需要修改其前驱 结点的next指针
方法1：传入头指针，循环寻找p的前驱结点
方法2：偷天换日（类似于结点前插的实现）
下面是方法2的代码实现：
//删除指定结点p bool DeleteNode(LNode *p) { if (p == NULL) return false; LNode *q = p->next; //令q指向*p的后继结点 p->data = p->next->data; p->next = q->next; free(q); return true; }
如果p是最后一个结点就只能从表头开始依次寻找p的前驱...