1.单链表的插入 头插中间插尾插 2.单链表的删除链表长度计算链表查找数值带头节点的单链表 头插尾插

1.单链表的插入

头插

中间插

尾插

2.单链表的删除

bool Remove(LinkList& first, int i, dataType& x) { //在链表中删除第 i 个结点。如果要删除表中第 1 个 //结点，需要改变表头指针，所以 first 定义为引用 //型，被删元素的值通过引用型参数 x 返回 LinkNode *p, *q; int k; if (i == 0) return false; //无效的删除位置 if (i == 1) { q = first; first = first->link; } else { //删除链中或链尾结点 p = first; int k = 1; //找第 i-1个结点 while (p != NULL && k < i - 1) { p = p->link; k++; } if (p == NULL || p->link == NULL) { printf(“无效的删除位置!\n”); return false; //链太短，没有删除结点 } else { //删除结点p->link q = p->link; //重新链接, 摘下*q p->link = q->link; } x = q->data; free(q); //删除*q return true; } }

链表长度计算

int Length(LinkList first) { LinkNode *p = first->link; //检测指针 p 跳过表头结点指示首元结点 int count = 0; while (p != NULL) { //逐个结点计数 p = p->link; count++; } return count; }

链表查找数值

LinkNode *Search ( LinkList first, DataType x ) { //在链表中从头搜索其数据值为 x 的结点 LinkNode * p = first->link; //p为检测指针 while ( p != NULL && p->data != x ) p = p->link; return p; }

while ( p != NULL && p->data != x ) 这个条件不能写成while(p->data != x && p != NULL) 因为前面为假 && 就不再判断后面了，见《c陷阱和缺陷》

带头节点的单链表

头结点位于表的最前端，本身不带数据，仅标志表头。

目的： 1.统一空表与非空表的操作 2.简化链表操作的实现。

头插

void insertFront(LinkList& first, DataType endTag) { DataType val; LinkNode *s; scanf(“%d”, &val); //读入一数据 while (val != endTag) //若不是endTag { s = (LinkNode *)malloc(sizeof(LinkNode)); s->data = val; //创建新结点 s->link = first->link; //插入到表前端 first->link = s; scanf(“%d”, &val); //读入下一数据 } }

尾插

void insertRear(LinkList& first, DataType endTag) { DataType val; LinkNode *s, *rear = first; //rear指向表尾 scanf(“%d”, &val); //读入一数据 while (val != endTag) { s = (LinkNode *)malloc(sizeof(LinkNode)); s->data = val; //创建新结点并赋值 rear->link = s; rear = s; //插入到表尾 scanf(“%d”, &val); //读入下一数据 } rear->link = NULL; //表收尾 }