建站之星凡客_怎样制作网页超链接_企业培训平台_搜索指数在线查询

1.链表的概念

1.引入目的:顺序表的方便修改和查找，不方便插入和删除，插入的和删除的时间复杂度是O(n并且顺序表存在满的情况，顺序表是否用于数据量较小的情况，所以引出链表。

2.链表:线性表的链式存储，称为链表。

3.链表的分类:单向链表，单向循环链表，双向链表，双向循环链表

2单链表的具体操作

仅给出头文件、枚举，链表定义；函数声明自行给出。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef int datatype;
enum possible{SUCCESS,FALSE=-1};
//链表结构体定义
typedef struct Node
{datatype data;//数据域struct Node *next;//指针域}Node;
typedef Node* linklist;

2.1 单链表的结点创建

//创建
linklist create_node()
{//创建新节点linklist s=(linklist)malloc(sizeof(struct Node));if(s==NULL)return NULL;//初始化s->data=0;s->next=NULL;return s;
}

2.2 单链表的头插

//头插
linklist insert_head(linklist head,datatype element)
{//创建新节点linklist s=create_node();s->data=element;//判空if(head==NULL){head=s;}else{//链表中存在多个节点s->next=head;head=s;}return head;
}

2.3单链表遍历

//打印
void show_linklist(linklist head)
{if(head==NULL){printf("error");return;}linklist p=head;while(p!=NULL){       printf("%d,",p->data);printf("%p\n",&p->next);p=p->next;}
}

2.4 单链表的头删

//头删
linklist delete_head(linklist head)
{//1.判断链表是否为空if(NULL==head)return NULL;//2.实现头删else{linklist del=head;head=head->next;free(del);del=NULL;}return head;
}

2.5 单链表的尾插

//尾插
linklist insert_last(linklist head,datatype element)
{//创建新节点linklist s=create_node();s->data=element;//判空if(head==NULL){head=s;}else{linklist p=head;while(p->next!=NULL){p=p->next;}//链表中存在多个节点p->next=s;}return head;
}

2.6 单链表的尾删

//尾删
linklist delete_last(linklist head)
{//1.判断链表是否为空if(NULL==head)return NULL;//2.实现头删else if(head->next==NULL){free(head);head=NULL;}else{linklist del=head;while(del->next->next!=NULL){del=del->next;}free(del->next);del->next=NULL;}return head;
}

2.7 单链表按位置插入

//计算链表长度
int len_linklist(linklist head)
{       int i=0;while(head!=NULL){head=head->next;i++;}return i;
}

//下标插入
linklist insert_sub(linklist head,int sub,datatype element)
{int len=len_linklist(head);//1.判断插入位置是否合法if(sub<1||sub>len+1){printf("error");return head;}//2判断插入位置为1      if(sub==1){head=insert_head(head,element);}//3.插入位置大于1，且合法else{linklist p=head;for(int i=1;i<sub-1;i++){p=p->next;}//找到待插入位置的前一位linklist s=craete_node();s->data=element;//插入s->next=p->next;p->next=s;}return head;
}

2.8 单链表按位置删除

//下标删除
linklist delete_sub(linklist head,int sub)
{int len=len_linklist(head);//1.判断删除位置是否合法if(sub<1||sub>len+1){printf("error");return head;}//2判断删除位置为1      if(sub==1){head=delete_head(head);}//3.插入位置大于1，且合法else{linklist p=head;for(int i=1;i<sub-1;i++){p=p->next;}//找到待删除位置的前一位//删除linklist del=p->next;p->next=p->next->next;free(s);del->next=NULL;}return head;
}

2.9 单链表按位置修改

//下标修改
int revise_sub(linklist head,int sub,datatype element)
{int len=len_linklist(head);//1.判断查找位置是否合法if(sub<1||sub>len+1){printf("error");return FALSE;}linklist p=head;for(int i=1;i<sub-1;i++){p=p->next;}p->next->data=element;printf("%d",p->next->data);return SUCCESS;
}

2.10 单链表按位置查找

linklist locate_sub(linklist head,int sub)
{    int len=len_linklist(head);if(sub<1||sub>len){return NULL;}linklist p=head;for(int i=1;i<len;i++){p=p->next;   }printf("%d",p->data);return p;
}

2.11 单链表按元素查找

//按元素查找
linklist locate_element(linklist head,datatyment element)
{linklist p=head;int i=1;while(p->next!=NULL){if(p->data==element){printf("%d",i);return p;}p=p->next;i++;}printf("查找失败");return head;}

2.12 单链表按元素删除

//按元素删除
linklist delete_element(linklist head,datatype element)
{if(head->data=element)head=delete_head(head);else{linklist p=head;while(p->next!=NULL){if(p->next->data==element){linklist del=p->next;p=p->next->next;free(del);del=NULL;}}return head;}

2.13 单链表按元素修改

//按元素修改
void revise_element(linklist head,datatype element1,datatyment element2)
{linklist p=locate_element(head,element1);if(head==p){printf("修改失败");}p->data=element2;printf("修改成功");
}

2.14 单链表逆置

//单链表逆置
linklist revise_sum(linklist head)
{if(head==NULL){printf{"linklist 为空"};return NULL;}linklist p=head->next;head->next=NULL;while(p!=NULL){linklist s=p;p=p->next;s->next=head;head=s;}return head;
}

2.15 单链表查找倒数第n个节点

//查找倒数n个节点
int locate_node(linklist head,int n)
{int len=len_linklist(head);if(n<1||n>len){return FALSE;}else{linklist p=head;linklist s=head;for(int i=0;i<n;i++){p=p->next;}while(p->next!=NULL){p=p->next;s=s->next;}pritnf("%d",p->data);}return p->data;
}

2.16 单链表排序

void bubblesort_linklist(linklist head)
{if(head==NULL){printf("linklist 为空");}linklist p=head;linklist s=head;while(s->next!=NULL){int temp=0;while(p->next!=NULL){if(p->data<p->next->data){temp=p->next->data;p->next->data=p->data;p->data=temp;}p=p->next;}s=s->next;p=s;}show_linklist(head);
}

2.17 单链表释放内存

void free_list(linklist head) {linklist p;while (head != NULL) {p = head;head = head->next;free(p);}
}