昨天我们说了,单链表如何进行初始化操作。初始化之后,我们就创建了一个单链表了,接下来,我们要往这个链表里填充数据,也就是常说的,插入操作。

-
假设存储元素e的结点为s,要实现结点p、p->next和s之间逻辑关系的变化,只需将结点s插入到结点p和p->next之间即可。可如何插入呢?
-
插入操作正是链表的优势操作之一。根本用不着惊动其他结点,只需要让s->next和p->next的指针做一点改变即可。你看一下这幅图你就明白了。

先把结点s的指针next指向ai+1,即 s->next = p->next. 然后再把ai的指针next指向s,即 p->next = s. 用代码描述则为:
s->next = p->next; p->next = s;
-
也就是说让p的后继结点变成s的后继结点,而不再是p的后继,相当于砍断了p与其后继结点的关联。然后再把结点s变成 p的后继结点,s也就变成了 p->next。那么这两句的顺序可不可以交换一下呢?
如果先p->next=s;再s->next=p->next;会怎么样?此时第一句会使得将p->next给覆盖成s的地址了。那么s->next=p->next,其实就等于s->next=s,这样真正的拥有ai+1数据元素的结点就没了上级。这样的插入操作就是失败的,造成了临场掉链子的尴尬局面。所以这两句是无论如何不能反的,这点初学者一定要注意。
单链表第i个数据插入结点的算法思路:
- 声明一结点p指向链表第一个结点,初始化j从1开始;
- 当j < i时,就遍历链表,让p的指针向后移动,不断指向下一结点,j累加1;
- 若到链表末尾p为空,则说明第i个元素不存在;
- 否则査找成功,在系统中生成一个空结点s;
- 将数据元素e賦值给s->data;
- 单链表的插入标准语句s->next=p->next; p->next=s;
- 返回成功。
函数设计如下:
/* 初始条件:顺序线性表L已存在,1≤i≤ListLength(L), */ /* 操作结果:在L中第i个位置之前插入新的数据元素e,L的长度加1 */ Status ListInsert(LinkList *L,int i,ElemType e) { int j; LinkList p,s; p = *L; /* 声明一个结点 p,指向头结点 */ j = 1; while (p && j < i) /* 寻找第i个结点 */ { p = p->next; ++j; } if (!p || j > i) return ERROR; /* 第i个元素不存在 */ s = (LinkList)malloc(sizeof(Node)); /* 生成新结点(C语言标准函数) */ s->data = e; s->next = p->next; /* 将p的后继结点赋值给s的后继 */ p->next = s; /* 将s赋值给p的后继 */ return OK; }
附:完整的程序。
#include "stdio.h" #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define MAXSIZE 20 /* 存储空间初始分配量 */ typedef int Status;/* Status是函数的类型,其值是函数结果状态代码,如OK等 */ typedef int ElemType;/* ElemType类型根据实际情况而定,这里假设为int */ typedef struct Node { ElemType data; struct Node *next; }Node; /* 定义LinkList */ typedef struct Node *LinkList; /* 初始化顺序线性表 */ Status InitList(LinkList *L) { *L=(LinkList)malloc(sizeof(Node)); /* 产生头结点,并使L指向此头结点 */ if(!(*L)) /* 存储分配失败 */ { return ERROR; } (*L)->next=NULL; /* 指针域为空 */ return OK; } /* 初始条件:顺序线性表L已存在。操作结果:返回L中数据元素个数 */ int ListLength(LinkList L) { int i=0; LinkList p=L->next; /* p指向第一个结点 */ while(p) { i++; p=p->next; } return i; } /* 初始条件:顺序线性表L已存在 */ /* 操作结果:依次对L的每个数据元素输出 */ Status ListTraverse(LinkList L) { LinkList p=L->next; while(p) { visit(p->data); p=p->next; } printf("\n"); return OK; } Status visit(ElemType c) { printf("-> %d ",c); return OK; } /* 初始条件:顺序线性表L已存在,1≤i≤ListLength(L), */ /* 操作结果:在L中第i个位置之前插入新的数据元素e,L的长度加1 */ Status ListInsert(LinkList *L,int i,ElemType e) { int j; LinkList p,s; p = *L; /* 声明一个结点 p,指向头结点 */ j = 1; while (p && j < i) /* 寻找第i个结点 */ { p = p->next; ++j; } if (!p || j > i) return ERROR; /* 第i个元素不存在 */ s = (LinkList)malloc(sizeof(Node)); /* 生成新结点(C语言标准函数) */ s->data = e; s->next = p->next; /* 将p的后继结点赋值给s的后继 */ p->next = s; /* 将s赋值给p的后继 */ return OK; } int main() { LinkList L; Status i; int j,k; char opp; i=InitList(&L); printf("链表L初始化完毕,ListLength(L)=%d\n",ListLength(L)); printf("\n1.遍历操作 \n2.插入操作 \n0.退出 \n请选择你的操作:\n"); while(opp != '0'){ scanf("%c",&opp); switch(opp){ case '1': ListTraverse(L); printf("\n"); break; case '2': srand((unsigned)time(NULL)); for(j=1;j<=10;j++) { i=ListInsert(&L,1,rand()%100); } printf("在L的表头依次插入10个随机数后:"); ListTraverse(L); printf("\n"); break; case '0': exit(0); } } }
延伸阅读
此文章所在专题列表如下:
- 第01话:线性表的概念与定义
- 第02话:线性表的抽象数据类型ADT定义
- 第03话:线性表的顺序存储结构
- 第04话:线性表的初始化
- 第05话:线性表的遍历、插入操作
- 第06话:判断线性表是否为空与置空操作
- 第07话:线性表的查找操作
- 第08话:线性表删除某个元素
- 线性表顺序存储的优缺点
- 线性表链式存储结构的由来与基本概念
- 单链表的头指针、头结点与首元结点
- 单链表的结构体定义与声明
- 单链表的初始化
- 单链表的插入与遍历操作
- 单链表的删除某个元素的操作
- 获取单链表中的指定位置的元素
- 查找某数在单链表中的位置
- 用头插法实现单链表整表创建
- 用尾插法实现单链表整表创建
- 将单链表重置为空表
- 单链表反转/逆序的两种方法
- 单链表反转/逆序的第三种方法
- 求单链表倒数第N个数
- 用标尺法快速找到单链表的中间结点
- 如何判断链表是否有环的存在
- 单链表建环,无环链表变有环
- 删除单链表中的重复元素
本文地址:http://www.nowamagic.net/librarys/veda/detail/2223,欢迎访问原出处。