C语言实现单链表的创建及基本操作 |
您所在的位置：网站首页 › 创建链表以输入-1结束 › C语言实现单链表的创建及基本操作 |
C语言实现单链表的创建及基本操作
|
C语言实现单链表的创建及基本操作
往期文章：C语言实现顺序表的创建及基本操作 这次主要是分享一下数据结构中单链表的创建及基本操作，这一部分也是属于比较基础的内容。但是越基础的东西我们越要投入精力去学习，不能眼高手低。我在编写这一部分的内容时就出现了许多错误，这也算是一次查漏补缺的博客吧，下面我们正式开始。 单链表的结构定义首先我们先来看一下常规定义的单链表，一般情况下会包含数据域和指针域。例如： typedef struct node{//单链表的结构定义 int data;//定义int类型的数据域 struct node *next; //定义指针域 }node，*linklist;这个地方会出现两个让人比较迷的东西：结构指针node和linklist。本质上而言，这两种类型是等价的。通常用linklist说明指针变量，强调它是某个单链表的头指针变量，定义为linklist L,L表示头指针。node用来定义单链表中结点的指针，例如node *p，p为结点的指针变量，p也可以定义为头结点。但是在方法的编写时，这两种定义会混合使用，非常容易迷惑我们的思维。所以我接下来的所有方法都只使用node来定义。 单链表的初始化 node *startlist(node *l){//初始化单链表 并设置为空表 l=(node *)malloc(sizeof(node)); l->next=NULL;//使头结点的指针域为空，建立一个空的单链表 return l; }我这里有一个错误点，在方法体内为头结点分配内存空间的时候要注意，必须要返回指针，否则分配的内存在本方法运行结束后就会释放，相当于没分配内存。当然你也可以使用下面的方法，并在主函数中分配内存。 void startlist(node *l){//初始化单链表 并设置为空表 l->next=NULL;//使头结点的指针域为空，建立一个空的单链表 } int main(){ node *l,*m; l=(node *)malloc(sizeof(node));//建立一个头结点 并动态分配存储空间 return 0; } 头插法建立单链表 void creatfromhead(node *l) {//利用头插法建立单链表 node *p;//新建一个结点指针 int i=1; int j; while(i!=0){ scanf("%d",&j); if(j!=-1){ p=(node *)malloc(sizeof(node)) ;//新建一个结点 p->data=j;//把输入的值赋值给新结点的指针域 p->next=l->next;//把新结点插入到表头 l->next=p;//头结点要始终放在最前面 } else { i=0;//如果输入-1则结束单链表的输入 } } } 尾插法建立单链表 void creatfromtail(node *l){//利用尾插法建立单链表 node *p;//新建一个结点指针 node *r;//再建立一个尾指针 int i=1; int j; r=l;//很重要的一步，令尾指针r指向头结点l,便于做尾插入 while(i!=0) { scanf("%d",&j); if(j!=-1){ p=(node *)malloc(sizeof(node)) ;//建立一个新结点 p->data=j; r->next=p;//尾指针的指针域指向新结点p r=p;//再让尾指针放在p后面，尾指针永远在最后 } else { i=0;//输入-1则结束 r->next=NULL;//尾指针的指针域设置为空，表示链表的结束 } } } 按序号查找在单链表中查找第i个结点 找到则返回存储位置 。 node *search1(node *l,int i){//在单链表中查找第i个结点 找到则返回存储位置 node *p;//新建一个结点指针 int j=0;//建立一个计数器 if(inext!=NULL&&jnext;//指向下一结点 j++;//计数 } if(i==j) return p;//找到了就返回p指针 else return NULL; } 按值查找在单链表中查找值为e的结点 找到返回结点 。 node *search2(node *l,int e){//在单链表中查找值为e的结点 找到返回结点 node *p;//新建一个结点指针 p=l->next ;//从第一个结点开始，既头结点后面那个 while(p!=NULL){ if(p->data!=e)p=p->next;//指向下个结点 else break;//找到则退出循环 } return p;//返回p指针 } 求单链表的长度这个没什么好说的，比较简单。 int length(node *l){//求单链表的长度 node *p;//新建一个结点指针 p=l->next; int j=0; while(p!=NULL){ p=p->next; j++; } return j;//返回长度 } 单链表的插入操作 void enterlist(node *l,int i,int e){//单链表的插入 在第i个位置 插入值为e的数据元素 node *p,*s;//新建两个结点指针 int k=0; if(idata=e; s->next=p->next;// 因为p时第i-1个结点 故 s的指针域应该指向第i个结点 p->next=s; printf("插入成功！\n"); } 单链表的删除操作 void dellist(node *l,int i){//单链表删除操作 删除第i个元素 node *p,*r; int k=0; p=l; while(p->next!=NULL&&knext; k++; } if(p->next==NULL){ printf("删除位置不合法！\n"); } r=p->next; p->next=r->next;//修改指针删除结点 printf("删除的元素是%d\n",r->data); free(r);//释放内存空间 } 单链表的打印 void printlist(node *l){//对单链表进行打印 printf("该链表的内容为："); while(l->next!=NULL){ printf("%d ",l->next->data); l=l->next; } printf("\n"); } 主函数 int main(){ node *l,*m; l=startlist(l); //l=(node *)malloc(sizeof(node));//建立一个头结点 并动态分配存储空间 //m=(node *)malloc(sizeof(node));//建立一个头结点 并动态分配存储空间 m=startlist(m); printf("单链表已初始化\n"); printf("用头插法插入链表l：\n") ; creatfromhead(l); printlist(l); printf("用尾插法插入链表m：\n") ; creatfromtail(m); printlist(m); printf("查找链表m的第一个结点\n"); node *s; s=search1(m,1); printf("该结点的值为%d\n",s->data); printf("在链表m的第二个位置 插入1\n"); enterlist(m,2,1); printlist(m) ; printf("删除链表m第二个位置的值\n"); dellist(m,2); return 0; }运行截图： 写博客是指一种良好的习惯，可以促进并深化我们对知识的了解与运用。代码这种东西还是熟能生巧，养成良好的学习习惯才能让我们在求学之路上走的更远，加油加油！下期可能会写循环链表或者是栈，慢慢来吧。。。 |
【本文地址】