数据结构------单向链表。

一.实现单向链表的头插，头删，尾插，尾删，按位置插，按位置删，按位置修改，按元素查找，按元素修改，按元素删除，单链表的逆置，查找倒数第几个元素，释放内存。

头文件:head.h

#ifndef __HEAD_H__ #define __HEAD_H__ #include <stdio.h> #include <string.h> #include <stdlib.h> typedef int datatype; enum passble{success,false=-1}; typedef struct Node { datatype data; struct Node* next; }*Linklist; Linklist Create_Node(); Linklist head_insert(Linklist head,datatype element); void show(Linklist head); Linklist head_delete(Linklist head); Linklist tail_insert(Linklist head,datatype element); Linklist tail_delete(Linklist head); int getlen(Linklist head); Linklist pos_insert(Linklist head,int pos,datatype element); Linklist delete_index(Linklist head,int pos); Linklist change_index(Linklist head,int pos,datatype element); int find_index(Linklist head,int pos); int value(Linklist head,datatype element); Linklist change_value(Linklist head,datatype element,datatype data1); Linklist delete_value(Linklist head,datatype element); int find_value(Linklist head,int pos); Linklist swap(Linklist head); void free_list(Linklist head); #endif

测试文件（test.c）

#include"head.h" //创建节点 Linklist Create_Node() { Linklist s=(Linklist)malloc(sizeof(struct Node)); if(NULL==s) return NULL; s->data=0; s->next=NULL; return s; } //头插 Linklist head_insert(Linklist head,datatype element) { Linklist s=Create_Node(); s->data=element; if(NULL==head) head=s; else { s->next=head; head=s; } return head; } //头删 Linklist head_delete(Linklist head) { if(NULL==head) return NULL; Linklist p=head; head=head->next; free(p); p=NULL; return head; } //尾插 Linklist tail_insert(Linklist head,datatype element) { Linklist s=Create_Node(); s->data=element; if(NULL==head) { head=s; } { Linklist p=head; while(p->next) { p=p->next; } p->next=s; } return head; } //尾删 Linklist tail_delete(Linklist head) { if(NULL==head) return NULL; else if(head->next==NULL) { free(head); head=NULL; } else { Linklist p=head; while(p->next->next!=NULL) { p=p->next; } free(p->next); p->next=NULL; } return head; } //计算链表的长度 int getlen(Linklist head) { int count=0; Linklist p=head; while(p) { count++; p=p->next; } return count; } //按位置插入值 Linklist pos_insert(Linklist head,int pos,datatype element) { Linklist s=Create_Node(); s->data=element; Linklist p=head; if(pos<1||pos>getlen(head)+1) return head; if(pos==1) { head=head_insert(head,element); return head; } for(int i=1;i<pos-1;i++) { p=p->next; } s->next=p->next; p->next=s; return head; } //按位置删除 Linklist delete_index(Linklist head,int pos) { if(pos<1||pos>getlen(head)) return head; if(pos==1) { head=head_delete(head); return head; } Linklist p=head; for(int i=1;i<pos-1;i++) { p=p->next; } Linklist del=p->next; p->next=del->next; free(del); del=NULL; return head; } //按位置修改 Linklist change_index(Linklist head,int pos,datatype element) { //判断修改的位置是否合法 if(pos<1||pos>getlen(head)) { return head; } Linklist p=head; for(int i=1;i<pos;i++) { p=p->next; } p->data=element; return head; } //按位置查找返回值 int find_index(Linklist head,int pos) { if(NULL==head) return 0; if(pos<1||pos>getlen(head)) { return 1 ; } Linklist p=head; for(int i=1;i<pos;i++) { p=p->next; } return p->data; } //按值查找返回位置 int value(Linklist head,datatype element) { if(NULL==head) return 0; Linklist p=head; for(int i=1;i<=getlen(head);i++) { if(p->data==element) { return i; } p=p->next; } return 0; } //按值修改 Linklist change_value(Linklist head,datatype element,datatype data1) { int j=value(head,element); head=change_index(head,j,data1); return head; } //按值删除 Linklist delete_value(Linklist head,datatype element) { int j=value(head,element); head=delete_index(head,j); return head; } //查找倒数第几个元素的值 int find_value(Linklist head,int pos) { if(NULL==head) return 0; if(pos<1||pos>getlen(head)) return 1; Linklist p=head; Linklist q=head; for(int i=1;i<pos;i++) { p=p->next; } while(p->next) { p=p->next; q=q->next; } return q->data; } //单链表的逆置 Linklist swap(Linklist head) { if(NULL==head) return head; if(getlen(head)==1) return head; Linklist p=head->next; head->next=NULL; while(p) { Linklist s=p; p=p->next; s->next=head; head=s; } return head; } //释放内存 void free_list(Linklist head) { Linklist s=head; while(s) { s=s->next; head=head_delete(head); } return ; } //输出 void show(Linklist head) { if(NULL==head) { return; } Linklist p=head; while(p!=NULL) { printf("%d\t",p->data); p=p->next; } putchar(10); }

主文件（main.c）

#include"head.h" int main(int argc, const char *argv[]) { //头插 Linklist head=NULL; int n; datatype element; printf("请输入头插要插入几个数据："); scanf("%d",&n); for(int i=0;i<n;i++) { printf("请输入头插插入的数据："); scanf("%d",&element); head=head_insert(head,element); } head=head_delete(head); //头删 show(head); //尾插 printf("请输入尾插要插入几个数据："); scanf("%d",&n); for(int i=0;i<n;i++) { printf("请输入尾插插入的数据："); scanf("%d",&element); head=tail_insert(head,element); } head=tail_delete(head); //尾删 show(head); int pos; //任意位置插 printf("请输入要插入数据的位置："); scanf("%d",&pos); printf("请输入插入的数据："); scanf("%d",&element); head=pos_insert(head,pos,element); show(head); /* //任意位置删 printf("请输入要删除数据的位置："); scanf("%d",&pos); head=delete_index(head,pos); show(head); //任意位置修改 printf("请输入要修改数据的位置："); scanf("%d",&pos); printf("请输入修改后的值："); scanf("%d",&element); head=change_index(head,pos,element); show(head); //按位置查找 printf("请输入要查找的位置："); scanf("%d",&pos); datatype data=find_index(head,pos); if(data==0) { printf("链表为空\n"); } else if(data==1) { printf("输入不合理\n"); } else{ printf("查找位置的值为：%d\n",data); } //按值查找返回位置 printf("请输入要查找的值："); scanf("%d",&element); pos=value(head,element); if(pos==0) { printf("没有这个元素\n"); } else{ printf("要查找的值的位置为：%d\n",pos); } //按值修改 datatype data1;//修改后的值 printf("请输入要修改的元素："); scanf("%d",&element); printf("请输入修改后的值："); scanf("%d",&data1); head=change_value(head,element,data1); show(head); */ //按值删除 printf("请输入要删除的元素："); scanf("%d",&element); head=delete_value(head,element); show(head); //查找倒数第几个元素的值 printf("请输入倒数的位置："); scanf("%d",&pos); int k=find_value(head,pos); if(k==0) { printf("链表不存在"); } else if(k==1) { printf("输入的位置不合理"); } else { printf("%d\n",k); } //单链表的逆置 head=swap(head); printf("链表逆置后的结果为：\n"); show(head); //释放内存 free_list(head); return 0; }

运行结果：