[转载]链表操作&单向链表代码&创建&插入&删除
链表
链表概述

链表是一种常见的重要的数据结构。它是动态地进行存储分配的一种结构。它可以根据需要开辟内存单元。链表有一个“头指针”变量，以head表示，它存放一个地址。该地址指向一个元素。链表中每一个元素称为“结点”，每个结点都应包括两个部分：一为用户需要用的实际数据，二为下一个结点的地址。因此，head指向第一个元素：第一个元素又指向第二个元素；……，直到最后一个元素，该元素不再指向其它元素，它称为“表尾”，它的地址部分放一个“NULL”（表示“空地址”），链表到此结束。
单向链表

单向链表的每个结点中除信息域以外还有一个指针域，用来指出其后续结点，单向链表的最后一个结点的指针域为空(NULL)。单向链表由头指针唯一确定，因此单向链表可以用头指针的名字来命名，例如头指针名为head的单向链表称为表head，头指针指向单向链表的第一个结点。在用C语言实现时，首先说明一个结构类型，在这个结构类型中包含一个(或多个)信息成员以及一个指针成员：
#define NULL 0
typedef int DATATYPE
typedef struct node
{DATATYPE info；
node *
}LINKLIST;
 链表结构中包含指针型的结构成员，类型为指向相同结构类型的指针。根据C语
言的语法要求，结构的成员不能是结构自身类型，即结构不能自己定义自己，因为这样将导致一个无穷的递归定义，但结构的成员可以是结构自身的指针类型，通过指针引用自身这种类型的结构。
 链表的每个结点是lINKIST结构类型的一个变量。例如定义了个链表的头指针head
和两个指向链表结点的指针p，q：
 LINKLIST *head,*P，*q;

根据结构成员的引用方法，当p和q分别指向了链表的确定结点后，P-&info和p-&next分别是某个结点的信息分量和指针分量，LINKLIST结构的信息分量是整型，可以用常规的方法对这两个结点的信息分量分别赋值：
p-＞info＝20;
q-＞inFo＝30;

指针分量是指向LINKLIST类型变量的指针，指针中将存储链表的下一个结点的存储首地址，在链表尾部的最后一个结点的指针域中，指针的值为空(NULL)。
head＝p;
p-＞next＝q；
q-＞next＝NULL;
 经上列的赋值后，组成右图的一个链表。
 下面将以上述链表结点结构为例，给出单向链表的几种算法。
建立单向链表 单向链表中插入结点
单向链表中删除结点 编历链表
 建立单向链表

建立单向链表的算法写成为函数create()，该函数将顺序输人的一组数构造为一个首尾相接的单向链表，为将新结点放在当前链表的尾部，函数中定义了个尾指针tail，使其一直指向当前链表的尾结点。

例：建立单向链表的函数。 LINKLIST *create()
{DATATYPE

 LINKLIST *head, *tail,*

 head＝new(LINKLIST)；

 tail=

 scanf("%d",&data);

 while(data!=0);

 {node=new(LINKLIST);

 node-&info=

 tail-&next=

 tail=

 scanf("%d",&data);

 }

 tail-&next=NULL;



}

在函数中首先为Head申请了—个所指向的结点，该结点称为链表的首结点。开始链表的头指针和尾指针都指向头结点(见上图)，以后每输入一个数则申请一个结点，将输入的数放到结点的信息域后，由语句tail-&next＝node将该结点链接在链表的尾部。输入结束后，置链表最后一个结点的指针域为空，返回链表头指针。

 单向链表中插入结点

在单向链表中插入一个结点要引起插入位置前面结点的指针的变化、下图表示了向一个单向链表插人结点时指针的变化情况，虚线所示为变化后的指针。
例：在单向链表的p结点后面插入一个信息域的值为x的新结点。

 void insert(LINKLIST*p, DATATYPE x)

 {LINKLIST *newp＝new(LINKLIST);

 newp-＞info＝x;

 newp-＞next＝p-＞

 p-＞next＝

 }

在插入一个结点时首先要由new(LINKLIST)向系统申请一个存储LINKLIST类型变量的空间，并将该空间的首地址赋给指向新结点的指针newp，在为该新结点的信息域赋值后，先要将该结点插入位置后面一个结点的指针赋给该结点的指针域，然后才能将指向该结点的指针赋给其前一个结点的指针域，这样来完成上图的插入过程。
 单向链表中删除结点

在单向链表中删除个结点同样要引起删除结点的前面结点的指针的变化，下图形象地表示了从单向链表中删除一个结点时指针的变化情况，虚线所示为变化后的指针。
例：删除单向链表结点*p后面结点。
 void delete(LINKLIST *p)

 {LINKKLIST *temp；

 temp＝p-＞next；

 p-＞next=P-＞next-＞next；

 delet(temp)；

 }

将指向被删除结点的指针保存在一个同类型的指针变量中，然后将其前一个结点的指针调整到指向该结点的后一个结点，最后将被删除的结点释放给系统。
 编历链表

由于链表是一个动态的数据结构，链表的各个结点由指针链接在起，访问链表元素时通过每个链表结点的指针逐个找到该结点的下一个结点，—直找到链表尾，链表的最后一个结点的指针为空。
例：编历链表函数。

 void outputlist(LINKLIST *head)

 LINKLIST *current＝head-＞

 while(current！＝NULL)

 {printf("%dn",current-&info);

 current=current-&

 }



 }
双向链表

每个结点中只包括一个指向下个结点的指针域，这种链表称为单向链表。如果要在单向链表一个指针所指的当前位置插入一个新结点，就必须从链表头指针开始逐个遍历直到当前指针所指结点的前一结点，修改这个结点的指针。双向链表的每个结点中包括两个指针域，分别指向该结点的前一个结点和后一个结点。在双向链表中由任何一个结点都很容易找到其前面的结点和后面的结点，而不需要在上述的插入(及删除)操作中由头结点开始寻找。定义双向链表的结点结构为

typedef struct node

{ DATATYPE info；

 node *priv, *

}DINKLIST；

 下面给出双向链表中插入删除一个结点的函数。操作过程见下图：
 例:将一个结点插入到双向链表指定结点之后。

insertafter(DINKLIST *current，DINKLIST *new)

{new-&next=current-&

new-＞priv＝

current-＞next-＞priv＝

current-＞next-＞

}

 例:将一个结点插入到双向链表指定结点之前。

insertbefor(DINKLIST *current，DINKLIST *new)

{new-＞next＝

 new-&priv=current-&　

 current-＞priv=current-&

 current-＞priv=

}

 例:在双向链表中删除一个指定结点。

deleteelement(DINKLIST *current)

{current-＞next-&priv=current-&priv


current-＞priv-&next=current-&

 delete(current);

}
循环链表

单向链表的最后一个结点的指针域为空（NULL）。如果将这个指针里利用起来，以指向单向链表的第一个结点，就组成一个单向循环链表。如下图所示：

 对双向链表做类似的处理可构造一个双向循环链表。


以下是单向链表的代码
#include "stdio.h"
#include
typedef struct linklist
{
 int data_
 struct linklist *
}LINKLIST;

LINKLIST *creat();
LINKLIST *insert(LINKLIST *p,int data);
LINKLIST *del(LINKLIST *P);
void printf_link_list(LINKLIST *head);

int main()
{

 LINKLIST *
 head=creat();
 printf_link_list(head);
 printf("input the data which will be inserted:");
 scanf("%d",&data);
 insert(head,data); //在单项链表中的节点p插入一个新的节点，插入节点的数据信息为data；
 printf("the inserted linklist:n");
 printf_link_list(head);
 del(head); //删除单项链表中节点p后面的节点；
 printf("the deleted linklist:n");
 printf_link_list(head);
 return 0;
}

LINKLIST *creat()
{
 LINKLIST *head,*tail,*
 int data,n=0;
 head=(LINKLIST *)malloc(sizeof(LINKLIST));
 tail=
 printf("input a integer:");
 scanf("%d",&data);
 while(data!=0)
 {
 if(n==0)
 {
 head-&data_info=
 ++n;
 }
 else
 {
 temp=(LINKLIST *)malloc(sizeof(LINKLIST));
 temp-&data_info=
 tail-&next=
 tail=
 ++n;
 }
 printf("input a integer:");
 scanf("%d",&data);
 }
 tail-&next=NULL;

}

LINKLIST *insert(LINKLIST *p,int data)
{
 LINKLIST *node=(LINKLIST *)malloc(sizeof(LINKLIST));
 node-&data_info=
 node-&next=p-&
 p-&next=

}

LINKLIST *del(LINKLIST *p)
{
 LINKLIST *
 node=p-&

p-&next=(p-&next)-&
 free(node);

}

void printf_link_list(LINKLIST *head)
{
 LINKLIST *p=
 if(head!=NULL)
 do
 {
 printf("data_info=%dn",p-&data_info);
 p=p-&
 }while(p!=NULL);
 else
 printf("the link list is null!n");
}
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。C语言历年真题题库
本试题来自：（2011年C语言历年真题，）二、填空题(将答案填写在答题纸的相应答题号内,每个答案只占一行,共30分)函数deletelist的功能：在head指向的单向链表中查找是否出现多个x值相同的结点。如果发现存在这样的结点,则保留第一个结点,删除其他重复出现的结点。
typedef struct point
/*链表结点数据结构定义*/
struct point*
} ___(27)___
POT *deletelist(POT *head)
POT *p,*p1,*p2;
p=___(28)___;
while(p->next!=NULL)
while(p2!=NULL)
if(p2->x==p->x)
{p1->next=___(29)___;
p=___(30)___;
正确答案：
(29)p2->next
(30)p->next
您可能感兴趣的试题
填空题：（)fun函数的功能是删除s指向的链表中满足以下条件的结点:该结点的编号值是奇数且存放的字母ASCII编码值也为奇数(提示:a的ASCII编码是97);将删除的结点添加到t指向的链表尾部。试完善fun函数以达到要求的功能。
例如,若删除前的s链表为:
则删除后的s链表为:
struct node
/* 存放结点的编号 */
/* 存放一个字母的ASCII编码 */
struct node *
struct node *t=NULL:
struct node *fun(struct node *s)
{struct node *p,*q;struct node *r;
while(p!=NULL)
{if(((pài)%2)&&((pàc)%2))
if(t==NULL)
r->next=p;
if(t!=NULL)
答案：有，填空题：（)以下程序在3-50范围内验证:大于等于3的两个相邻素数的平方之间至少有4个素数。例如,3和5是相邻素数,3^2～5^2之间有素数11、13、17、19、23。试完善程序以达到要的功能。
#include<stdlib.h)
int prime(int n)
for(i=2;i<=sqrt(n);i++)
) return 0;
void main()
{int i,j,k=0,m,n,c,a[30]={0};
for(i=3;i<50;i++)
if(prime(i))
for(i=0;i<k-1;i++)
m=a[i]*a[i];
n=a[i+1]*a[i+1];
for(j=m+1;j=4)
printf("\n
%d*%d-%d*%d:%d",a[i],a[i],a[i+1],a[i+1],c);
else{printf("Error");exit(0);}
答案：有，
C语言历年真题最新试卷
C语言历年真题热门试卷2935人阅读
我们假设单向链表的节点如下：
template&&typename&T&
class&list_node
list_node&*&
这个题目算是考察数据结构的最基础的题目了，有两种方法可以解此题：
&&&&void&reverse(node*&&head)
&&&&&&&&if&(&(head&==&<span style="color:#)&||&(head-&next&==&<span style="color:#)&)&return;//&边界检测
&&&&&&&&node*&pNext&=&<span style="color:#;
&&&&&&&&node*&pPrev&=&//&保存链表头节点
&&&&&&&&node*&pCur&=&head-&//&获取当前节点
&&&&&&&&while&(pCur&!=&<span style="color:#)
&&&&&&&&&&&&pNext&=&pCur-&//&将下一个节点保存下来
&&&&&&&&&&&&pCur-&next&=&pP//&将当前节点的下一节点置为前节点
&&&&&&&&&&&&pPrev&=&pC//&将当前节点保存为前一节点
&&&&&&&&&&&&pCur&=&pN//&将当前节点置为下一节点
这是一般的方法，总之就是用了几个临时变量，然后遍历整个链表，将当前节点的下一节点置为前节点。
&&&&&&& 链表反转最好画个图，光看代码对于新新手来说，确实是一个迷糊。
&&&&&&& 链表正常的顺序是前一个节点的NEXT指向后一个节点。反转就是要将后一个节点的next指向前一个节点，
&&&&&& 所以pCur-&next = 完成了这一个功能。但这只是完成了两个节点的反转，所以对应的要将当前
节点的next保存下来pNext = pcur-&，用来当作下一次的当前节点PCur = P在下一次反转中，当前节点
就变成了下一次反转中的前节点。pPrev = pC
一直到当前节点为NULL，也就是全部转化为止;
&&&&node*&reverse(&node*&pNode,&node*&&head)
&&&&&&&&if&(&(pNode&==&<span style="color:#)&||&(pNode-&next&==&<span style="color:#)&)&//&递归跳出条件
&&&&&&&&&&&&head&=&pN&//&将链表切断，否则会形成回环
&&&&&&&&&&&&return&pN
&&&&&&&&node*&temp&=&reserve(pNode-&next,&head);//&递归
&&&&&&&&temp-&next&=&pN//&将下一节点置为当前节点，既前置节点
&&&&&&&&return&pN//&返回当前节点
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：141856次
积分：1956
积分：1956
排名：第7791名
原创：19篇
转载：212篇
评论：12条
(5)(6)(1)(5)(3)(5)(2)(8)(19)(3)(4)(1)(5)(19)(7)(4)(9)(7)(18)(5)(26)(23)(5)(5)(1)(4)(5)(24)(2)(1)建立一个有5个结点的单向链表。每个结点包含姓名、年龄和工资。编写两个函数，一个用于建立链表，另一个用_百度知道
建立一个有5个结点的单向链表。每个结点包含姓名、年龄和工资。编写两个函数，一个用于建立链表，另一个用
另一个用于输出链表。要求：1 建立链表的函数名为creat，数据输入和链表建立在函数中实现；
2 输出链表的函数名为output，用以实现creat建立的链表数据的输出；
3 在main函数中调用creat函数和output函数。模版：（这个不对，只是参考，尽量用这种方法）#include&stdio.h&#include&malloc.h&#define LEN sizeof(struct Student)struct Student{
struct Student *};struct Student *creat(){
struct Student *
struct Student *p1, *p2;
p1 = p2 = ( struct Student * ) malloc(LEN);
scanf(&%ld,%f&, &p1-&num,&p1-&score);
head = NULL;
while(p1-&num != 0)
n = n + 1；
if(n == 1)head = p1;
else p2-&next = p1;
p1 = (struct Student *)malloc(LEN);
scanf(&%ld, %f&, &p1-&num,&p1-&score);
p2-&next = NULL;
return(head); }void print(struct Student head){
strcut Student *p;
printf(&&#92;nNow,These %d records are :&#92;n&,n);
if(head != NULL)
printf(&%d %5.lf&#92;n&,p-&num,p-&score);
}while(p != NULL);}void main(){
struct Student *
head = creat();
print(head);}
提问者采纳
//就在原来的基础上改了一点，按你的模版的话，输入必须int,float的形式（两个数之间有逗号，如果不想要的话，就把输入那儿中间的逗号去掉）//例如/*13,89.9089,34.3478,670，0*/最后0结尾#include&stdio.h&#include&malloc.h&#define LEN sizeof(struct Student)struct Student{
struct Student *};struct Student *creat(){
struct Student *head = NULL;
struct Student *p1, *p2;
p1 = ( struct Student * ) malloc(LEN);
scanf(&%d , %f&, &p1-&num,&p1-&score);
while(p1-&num != 0)
if(n == 1)head = p1;
else p2-&next = p1;
p1 = (struct Student *)malloc(LEN);
scanf(&%d , %f&, &p1-&num,&p1-&score);
p2-&next = NULL;}void print(struct Student *head){
struct Student *p =
printf(&&#92;nNow,These %d records are :&#92;n&,n);
while (p != NULL)
printf(&%d %.5f&#92;n&,p-&num,p-&score);
}}int main(){
struct Student *
head = creat();
print(head);
return 0;}
提问者评价
其他类似问题
单向链表的相关知识
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁温馨提示！由于新浪微博认证机制调整，您的新浪微博帐号绑定已过期，请重新绑定！&&|&&
昨天夜里这里下过雨么？
雨后的竹笋更加青翠了。
LOFTER精选
阅读(598)|
用微信&&“扫一扫”
将文章分享到朋友圈。
用易信&&“扫一扫”
将文章分享到朋友圈。
历史上的今天
loftPermalink:'',
id:'fks_',
blogTitle:'两个单向链表，找出它们的第一个公共结点',
blogAbstract:'题目：两个单向链表，找出它们的第一个公共结点。链表的结点定义为：',
blogTag:'',
blogUrl:'blog/static/',
isPublished:1,
istop:false,
modifyTime:0,
publishTime:7,
permalink:'blog/static/',
commentCount:2,
mainCommentCount:1,
recommendCount:1,
bsrk:-100,
publisherId:0,
recomBlogHome:false,
currentRecomBlog:false,
attachmentsFileIds:[],
groupInfo:{},
friendstatus:'none',
followstatus:'unFollow',
pubSucc:'',
visitorProvince:'',
visitorCity:'',
visitorNewUser:false,
postAddInfo:{},
mset:'000',
remindgoodnightblog:false,
isBlackVisitor:false,
isShowYodaoAd:false,
hostIntro:'昨天夜里这里下过雨么？\n雨后的竹笋更加青翠了。',
hmcon:'1',
selfRecomBlogCount:'0',
lofter_single:''
{list a as x}
{if x.moveFrom=='wap'}
{elseif x.moveFrom=='iphone'}
{elseif x.moveFrom=='android'}
{elseif x.moveFrom=='mobile'}
${a.selfIntro|escape}{if great260}${suplement}{/if}
{list a as x}
推荐过这篇日志的人：
{list a as x}
{if !!b&&b.length>0}
他们还推荐了：
{list b as y}
转载记录：
{list d as x}
{list a as x}
{list a as x}
{list a as x}
{list a as x}
{if x_index>4}{break}{/if}
${fn2(x.publishTime,'yyyy-MM-dd HH:mm:ss')}
{list a as x}
{if !!(blogDetail.preBlogPermalink)}
{if !!(blogDetail.nextBlogPermalink)}
{list a as x}
{if defined('newslist')&&newslist.length>0}
{list newslist as x}
{if x_index>7}{break}{/if}
{list a as x}
{var first_option =}
{list x.voteDetailList as voteToOption}
{if voteToOption==1}
{if first_option==false},{/if}&&“${b[voteToOption_index]}”&&
{if (x.role!="-1") },“我是${c[x.role]}”&&{/if}
&&&&&&&&${fn1(x.voteTime)}
{if x.userName==''}{/if}
网易公司版权所有&&
{list x.l as y}
{if defined('wl')}
{list wl as x}{/list}