头插法生成的链表中,结点的次序和输入数据的顺序不一致。若希望两者次序一致,则需要尾插法。
该方法是将新结点逐个插入到当前链表的表尾上,为此必须增加一个尾指针r, 使其始终指向当前链表的尾结点,代码如下:
//尾插法建立单链表
LinkedListLinkedListCreatT(){
Node*L;
L=(Node*)malloc(sizeof(Node));//申请头结点空间
L->next=NULL;//初始化一个空链表
Node*r;
r=L;//r始终指向终端结点,开始时指向头结点
intx;//x为链表数据域中的数据
while(scanf("%d",&x)!=EOF){
Node*p;
p=(Node*)malloc(sizeof(Node));//申请新的结点
p->data=x;//结点数据域赋值
r->next=p;//将结点插入到表头L-->|1|-->|2|-->NULL
r=p;
}
r->next=NULL;
returnL;
}
遍历单链表如打印、修改
从链表的头开始,逐步向后进行每一个元素的访问,称为遍历。
对于遍历操作,我们可以衍生出很多常用的数据操作,比如查询元素,修改元素,获取元素个数,打印整个链表数据等等。
进行遍历的思路极其简单,只需要建立一个指向链表L的结点,然后沿着链表L逐个向后搜索即可,代码如下:
//便利输出单链表
voidprintList(LinkedListL){
Node*p=L->next;
inti=0;
while(p){
printf("第%d个元素的值为:%d\n", i,p->data);
p=p->next;
}
}
对于元素修改操作,以下是代码实现:
//链表内容的修改,在链表中修改值为x的元素变为为k。
LinkedListLinkedListReplace(LinkedListL,intx,intk){
Node*p=L->next;
inti=0;
while(p){
if(p->data==x){
p->data=k;
}
p=p->next;
}
returnL;
}
简单的遍历设计的函数只需要void无参即可,而当涉及到元素操作时,可以设计一个LinkedList类型的函数,使其返回一个操作后的新链表。
插入操作链表的插入操作主要分为查找到第i个位置,将该位置的next指针修改为指向我们新插入的结点,而新插入的结点next指针指向我们i 1个位置的结点。
其操作方式可以设置一个前驱结点,利用循环找到第i个位置,再进行插入。
如图,在DATA1和DATA2数据结点之中插入一个NEW_DATA数据结点:
从原来的链表状态
到新的链表状态:
代码实现如下:
//单链表的插入,在链表的第i个位置插入x的元素
LinkedListLinkedListInsert(LinkedListL,inti,intx){
Node*pre;//pre为前驱结点
pre=L;
inttempi=0;
for(tempi=1;tempi<i;tempi ){
pre=pre->next;//查找第i个位置的前驱结点
}
Node*p;//插入的结点为p
p=(Node*)malloc(sizeof(Node));
p->data=x;
p->next=pre->next;
pre->next=p;
returnL;
}
删除操作
删除元素要建立一个前驱结点和一个当前结点,当找到了我们需要删除的数据时,直接使用前驱结点跳过要删除的结点指向要删除结点的后一个结点,再将原有的结点通过free函数释放掉。如图所示:
代码如下:
//单链表的删除,在链表中删除值为x的元素
LinkedListLinkedListDelete(LinkedListL,intx){
Node *p,*pre;//pre为前驱结点,p为查找的结点。
p=L->next;
while(p->data!=x){//查找值为x的元素
pre=p;
p=p->next;
}
pre->next = p->next;//删除操作,将其前驱next指向其后继。
free(p);
returnL;
}
双向链表双向链表的简介以及概念
单链表是指结点中只有一个指向其后继的指针,具有单向性,但是有时需要搜索大量数据的时候,就需要多次进行从头开始的遍历,这样的搜索就不是很高效了。
在单链表的基础上,对于每一个结点设计一个前驱结点,前驱结点与前一个结点相互连接,构成一个链表,就产生了双向链表的概念了。
双向链表可以简称为双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。