单链表的创建与操作（有头节点）

1.概念与特点

概念：        

        逻辑结构：线性结构 一对一

        存储结构：链式存储 内存中不一定是连续的

特点：

        在链表中 每个数据元素都是一个结点，以结构体的方式封装

        包含数据域和指针域

        数据域：用于存储数据元素的信息

        指针域：用于存储数据元素下一个结点的首地址

2.创建节点的结构体类型

typedef struct node{
int data;
//保存节点的数据(数据域)
struct node *next;
//保存下个节点的地址(指针域)
}link_list_t;

3.创建新节点的函数create_linklist()   

（1）定义一个结点类型的指针*L，并用malloc在堆空间分配内存；

（2）初始化结点数据，L->data=-1；L->next=NNULL；

（3）返回结点的首地址。

link_list_t *create_linklist(){
link_list_t *L=malloc(sizeof(link_list_t));//给结构体指针在堆内存上分配内存
if(NULL==L){
printf("创建链表失败n");
return NULL;
}
L->data=-1;
//初始化节点数据为-1
L->next=NULL;
//初始化节点next指向为空
return L;
}

4.创建头节点

 link_list_t *L=create_linklist();
//创建一个节点作为头节点

5.插入节点--头插法

int head_link(link_list_t *L,data_t value){//L单链表的头结点，value新节点的数据
if(NULL==L){
printf("参数有误n");
return -1;
}
link_list_t *N=create_linklist();
//创建一个新节点
N->data=value;
//初始化节点数据
N->next=L->next;
L->next=N;
return 0;
}

6.遍历单链表

（1）定义一个新的节点类型*q，初始化为q=L->next；

（2）循环条件q!=NULLL;

（3）循环体：q=q->next;

int show_link(link_list_t *L){
if(NULL==L){
printf("参数有误n");
return -1;
}
if(NULL==L->next){
printf("链表为空n");
return -1;
}
link_list_t *q=L->next;
//定义一个移动的节点类型的指针，用于遍历
while(q!=NULL){
//从首个有效的节点开始遍历
printf("%d ",q->data);
q=q->next;
}
puts("");
return 0;
}

7.任意位置删除节点

        思路：找到要删除位置的前一个节点。

        条件：pos大于等于0，且小于链表的长度

（1）定义一个动点*q=L；int i=0;

（2）循环q=q->next;直到定位到要删除节点的前一位；

（3）在循环时要判断p->next是否为空，如果为空则退出循环，表示pos位没有数据；

（4）当定位到要删除的前一个节点，定义另一个节点保存要删除节点的位置*p=q->next;

（5）令q->next=p->next;p->next=NULL;释放p指向的堆空间。

//删除时，要定位到要删除节点的前一个位置，以便删除
int pos_delete(link_list_t *L,int pos){
//pos位置信息
if(NULL==L){
printf("参数有误n");
return -1;
}
if(NULL==L->next){
printf("链表为空n");
return -1;
}
int i=0;
link_list_t *q=L;
for(i=0;i<pos;i++){
q=q->next;
if(q->next==NULL){
return -1;
}
}
link_list_t *p=q->next;
q->next=p->next;
free(p);
p=NULL;
return 0;
}

8.翻转单链表

链表翻转：

        现象：输出前---12345

        输出后---54321

        思路：将链表分为两个链表，从第一个有效数据后断开，前半部分为一个链表，后半部分 为 一个链表。对后半部分进行头删的同时将节点头插到前半部分，直到后半部分为空。

（1）定义一个节点类型的指针*q=L->next->next;

（2）拆分为两个链表分别为L和q，L->next->next=NULL;

（3）定义一个新的节点类型指针*p=NULL，指向要操作的节点；

（4）判断q是否为空，否的话令p=q;q=q->next;p->next=L->next;L->next=p;

（5）循环执行第4步，直到q==NULL。

//将单链表分为俩个单链表，分别进行头删和头插
int overturn_list(link_list_t *L){
if(NULL==L){
printf("参数有误n");
return -1;
}
if(NULL==L->next){
printf("链表为空n");
return -1;
}
link_list_t *p=L->next->next;
if(p==NULL){
printf("仅有一个元素n");
return -1;
}
L->next->next=NULL;
link_list_t *q=p;
while(q!=NULL){
p=q;
q=p->next;
p->next=L->next;
L->next=p;
}
return 0;
}

9.任意位置查找

data_t pos_find(link_list_t *L,int pos){
if(NULL == L || pos<0){
printf("输入参数有误n");
return -1;
}
if(NULL == L->next){
printf("表为空n");
return -1;
}
link_list_t *q=L;
int i=0;
for(;i<=pos;i++){
q=q->next;
if(NULL == q){
printf("输入的位置参数过大n");
return -1;
}
printf("%d位置的数据是%dn",pos,q->data);
return 0;
}
}

10.排序

        思路：只交换数据，不交换节点(冒泡排序)。

（1）定义两个移动的节点类型的指针q和p,一个用于交换数据的三方变量temp；

（2）判断L->next和L->next->next是否为空，成立的话，程序结束，表位空表或只有一个节点；

（3）上述不成立，则令q=L->next；

（4）令p=q->next;判断q->data是否大于p->data，成立，则交换数据；不成立，执行第5步；

（5）令p=p->next；判断p是否为空，不成立执行第4步；成立，执行第6步；

（6）令q=q->next；判断q是否为空，不成立，执行第4步，成立退出循环，程序结束。

//只交换数据
int sort_link(link_list_t *L){
if(NULL == L){
printf("输入参数有误n");
return -1;
}
if(NULL == L->next || NULL == L->next->next){
printf("表为空表或表中只有一个元素n");
return -1;
}
link_list_t *q=L->next;
link_list_t *p=NULL;
data_t temp=0;
while(NULL != q){
p=q->next;
while(NULL != p){
if(q->data>p->data){
temp = p->data;
p->data=q->data;
q->data=temp;
}
p=p->next;
}
q=q->next;
}
return 0;
}

最后

以上就是畅快蛋挞为你收集整理的单链表的创建与操作（有头节点）的全部内容，希望文章能够帮你解决单链表的创建与操作（有头节点）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。