单链表(重点)

71 阅读 0 评论 47 点赞

我是靠谱客的博主妩媚仙人掌，最近开发中收集的这篇文章主要介绍单链表(重点)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

#ifndef __LINKLIST__
#define __LINKLIST__
#include<stdio.h>
#include<stdlib.h>
//节点数据域类型重命名
typedef int data_t;
//声明节点数据类
typedef struct node{
data_t data;
struct node *next;
}link_list_t;
//创建链表
link_list_t*create_link_linklist(void);
//头部插入数据
int head_insert(link_list_t*L,data_t value);
//遍历链表
int show_linklist(link_list_t*L);
//尾部插入数据
int tail_insert(link_list_t*L,data_t value);
//释放链表
int free_linklist(link_list_t**L);
//任意位置插入
int pos_insert(link_list_t*L,int pos,data_t value);
//头部删除
int head_delete(link_list_t*L);
//尾部删除
int tail_delete(link_list_t*L);
//任意位置删除
int pos_delete(link_list_t*L,int pos);
//翻转链表
int overturn_list(link_list_t*L);
//根据位置查找
data_t pos_find(link_list_t*L,int pos)
//根据数据查找
data_t data_find(link_list_t*L,data_t value);
//链表排序
int sort_link_list(link_list_t*L);
#endif

#include"link_list.h"
int main(int argc, const char *argv[])
{
//创建链表
link_list_t*L=create_link_linklist();
if(NULL==L){
return -1;
}
data_t i =0;
while(1){
scanf("%d",&i);
if(i==-1){
break;
}
//头部插入数据
//	head_insert(L,i);
//尾部插入数据 
tail_insert(L,i);
}
//遍历链表
show_linklist(L);
sort_link_list(L);
//任意位置插入
//	pos_insert(L,2,520);
show_linklist(L);
//	pos_insert(L,3,560);
show_linklist(L);
//释放链表
free_linklist(&L);
return 0;
}

#include"link_list.h"
//创建链表
link_list_t*create_link_linklist(void)
{
link_list_t*L=NULL;
//申请链表头节点空间
L=(link_list_t*)malloc(sizeof(link_list_t));
if(NULL==L){
puts("创建链表失败");
return NULL;
}
//初始化链表头节点
L->data = -1;//头节点数据域不适用　可以给任意值
L->next = NULL;//链表头节点指针域，置NULL是方便操作单链表
//返回链表头节点首地址
return L;
}
//头部插入数据
int head_insert(link_list_t*L,data_t value)
{
if(NULL==L){
puts("传入参数非法");
return -1;
}
//创建新节点
link_list_t*N=(link_list_t*)malloc(sizeof(link_list_t));
if(N==NULL){
printf("创建新节点失败");
return -1;
}
//初始化新节点
N->data = value;
N->next = NULL;
//头部插入数据
link_list_t *q=L;
N->next = q->next;
q->next = N;
}
//遍历链表
int show_linklist(link_list_t*L)
{
if(NULL==L){
puts("传入的参数非法");
return -1;
}
if(NULL==L->next){
puts("表为空表,无数据可遍历");
return -1;
}
link_list_t*q=L->next;
while(NULL!=q){
printf("%d",q->data);
q=q->next;
}
return 0;
}
//尾部插入数据
int tail_insert(link_list_t*L,data_t value)
{
if(NULL==L){
puts("传入的参数非法");
return -1;
}
//创立新节点
link_list_t*N=(link_list_t*)malloc(sizeof(link_list_t));
if(NULL==N){
printf("创建新节点失败");
return -1;
}
N->data=value;
N->next=NULL;
//	尾部插入数据
link_list_t *q=L;
while(NULL!=q->next){
q = q->next;
}
q->next=N;
return 0;
}
//释放链表
int free_linklist(link_list_t **L)
{
if(NULL==L||NULL==*L){
puts("传入参数非法");
return -1;
}
link_list_t *q=*L;
while(*L!=NULL){
q = q->next;
printf("%d即将被释放",(*L)->data);
free(*L);
*L=q;
}
*L=NULL;
return 0;
}
//任意位置插入
int pos_insert(link_list_t*L,int pos,data_t value)
{
if(L==NULL){
puts("传入的参数非法");
return -1;
}
if(pos<0){
puts("传入参数非法应大于0");
return -1;
}
//创建新节点
link_list_t *N=(link_list_t*)malloc(sizeof(link_list_t));
if(NULL==N){
puts("创建新节点失败");
return -1;
}
//初始化新节点
N->data=value;
N->next=NULL;
//插入
link_list_t*p=L;
int i=0;
for(i=0;i<pos;i++){
p=p->next;
if(p==NULL&&pos>0){
printf("表为空表，位置参数必须为０");
return -1;
}
if(NULL==p->next&&i<pos-1){
printf("传入位置参数超过链表长度，传入应大于０小于等于%dn",i+1);
}
}
N->next=p->next;
p->next =N;
return 0;
}
//头部删除
int head_delete(link_list_t*L)
{
if(NULL==L){
puts("传入参数非法");
return 0;
}
if(NULL==L->next){
puts("表为空表，无数据删除");
return -1;
}
link_list_t*q=L->next;
L->next=q->next;
q->next=NULL;
free(q);
q=NULL;
return 0;
}
//尾部删除
int tail_delete(link_list_t*L)
{
if(NULL==L){
puts("传入参数非法");
return 0;
}
if(NULL==L->next){
puts("表为空表，无数据删除");
return -1;
}
link_list_t*q=L;
link_list_t*p=NULL;
while(NULL!=q->next->next){
q=q->next;
}
p=q->next;
q->next=NULL;
free(p);
p=NULL;
return 0;
}
//任意位置删除
int pos_delete(link_list_t*L,int pos)
{
if(NULL==L){
puts("传入参数非法");
return 0;
}
if(NULL==L->next){
puts("表为空表，无数据删除");
return -1;
}
if(pos<0){
puts("位置参数必须大于０");
}
int i=0;
link_list_t*q=L;
for(i=0;i<pos;i++){
q=q->next;
if(NULL==q->next&&pos>0){
printf("表只有一个元素，只可以删除一个位置节点");
}
if(NULL==q->next->next&&i<pos-1){
printf("位置参数超越表长");
return -1;
}
}
//删除操作
link_list_t*p=q->next;
q->next=q->next->next;
printf("%d将要被删除",p->data);
p->next=NULL;
free(p);
return 0;
}
//翻转链表
int overturn_list(link_list_t*L)
{
if(NULL==L){
printf("传入的表参数非法");
return -1;
}
if(NULL==L->next||NULL==L->next->next){
printf("表为空表或只有一个元素");
return -1;
}
//翻转链表
//将原表分为２个
link_list_t*q=L->next->next;
L->next->next=NULL;
//将Ｐ表中的节点一次进行头部插入
link_list_t*p=q;
while(q!=NULL){
p=q;
q=p->next;
//插入
p->next=L->next;
L->next=p;
}
return 0;
}
//根据位置查找
data_t pos_find(link_list_t*L,int pos)
{
if(NULL==L){
printf("传入的表参数非法");
return -1;
}
if(NULL==L->next){
printf("表为空表");
return -1;
}
link_list_t*q=L;
int i;
for(i=0;i<pos;i++){
q=q->next;
if(NULL==q){
puts("传入位置参数非法");
return -1;
}
}
printf("%d位置上的数据是%dn",pos,q->data);
return 0;
}
//根据数据查找
data_t data_find(link_list_t*L,data_t value)
{
if(NULL==L){
printf("传入的表参数非法");
return -1;
}
if(NULL==L->next){
printf("表为空表");
return -1;
}
link_list_t*q=L->next;
while(q!=NULL){
if(value==q->data){
printf("%d数据存在",value);
return q->data;
}
q=q->next;
}
printf("%d数据不存在",value);
return 0;
}
//链表排序
int sort_link_list(link_list_t*L)
{
if(NULL==L){
printf("传入的表参数非法");
return -1;
}
if(NULL==L->next||NULL==L->next->next){
printf("表为空表或只有一个元素");
return -1;
}
link_list_t*q;
link_list_t*p;
q=L;
data_t mind;
while(q->next!=NULL){
q=q->next;
p=q->next;
while(p!=NULL){
if(q->data>p->data){
mind=q->data;q->data=p->data;p->data=mind;
}
p=p->next;
}
}
return 0;
}