单链表：1、逻辑上连续，位置上可以不连续的存储方式。
2、单链表由无数个结点组成，每个结点由数据段和指针域组成，数据段存储数据，指针域存储后继的地址。
3、每个结点最多有一个前继和一个后继。
4、其中第一个结点没有前继，所以我们通常建立一个头结点来保存他的位置，其中头结点的数据段我们不关注。
5、最后一个结点没有后继，所以我们将最后一个结点的指针域赋为NULL.
//函数声明："linklist.h"#define _CRT_SECURE_NO_WARNINGS 1#include#include typedef int ElemType;typedef struct linknode{ ElemType data; struct linknode *next;}node;void judgement_memory(node * p); //判断动态内存是否开辟成功node* creat_order(); //正向建立链表，尾插法node * creat_reverse(); //反向建立链表，头插法void insert(node *head, int i, ElemType x); //在i位置上插入值为x的结点void delete_place(node *head, int i); //删除i结点int delete_element(node *head, ElemType const x); //删除第一个值为x的结点void delete_all_element(node *ret, ElemType x); //删除所有值为x的结点void find_element(node *head, ElemType const x); //寻找所有值为x的结点位置void find_place(node *head, int i); //寻找i结点上的元素void length_list(node *head);void output(node *head); //打印链表node* inits_linklist(node *head); //释放链表void sortrank(node *head); //对链表进行排序int means();//函数实现:"linklist.c"#include"linklist.h"void judgement_memory(node * p) //判断开辟内存是否成功{ if (NULL == p) { perror("out of memory:"); exit(EXIT_FAILURE); }}node* creat_order() //建立一个具有头结点单链表，顺序插入（尾插法）{ printf("开始建立："); node *head, *p, *r; int x = 0; head = (node *)malloc(sizeof(node)); //建立头结点 judgement_memory(head); r = head; while (1) { scanf("%d", &x); if (x != 0) //以0作为链表结束标志 { p = (node *)malloc(sizeof(node)); judgement_memory(p); p->data = x; r->next = p; r = p; } else break; } r->next = NULL; printf("创建成功\n"); return head;}node * creat_reverse() //建立一个具有头结点的单链表，逆序输入（头插法）{ printf("开始建立："); node *head, *p, *r, *q; int x = 0; head = (node *)malloc(sizeof(node)); judgement_memory(head); p = (node *)malloc(sizeof(node)); //开辟最后一个结点 judgement_memory(p); p->next = NULL; scanf("%d", &x); p->data = x; r = head; q = p; r->next = q; while (1) { scanf("%d", &x); if (x!= 0) { p = (node *)malloc(sizeof(node)); judgement_memory(p); p->data = x; r->next = p; p->next = q; q = p; } else break; } printf("创建成功\n"); return head;}void insert(node *head, int i, ElemType x) //插入一个结点{ node *r; node *s = (node *)malloc(sizeof(node)); judgement_memory(s); s->data = x; while (NULL != head&&i>1) //要在第i个结点上插入，则先找到第i-1个结点 { i--; head = head->next; } if (NULL != head&&i!=0) //判断是不是头结点和结点是否存在 { r = head->next; head->next = s; s->next = r; printf("插入成功\n"); } else printf("结点不存在\n");}void delete_place(node *head, int i) //删除链表中一个指定位置的结点{ node *p; if (NULL == head) { printf("链表下溢\n"); } else { while (NULL != head&&i>1) //找到第i-1个结点 { i--; head = head->next; } if (NULL == head||i==0) printf("没有该位置\n"); else { p = head->next; head->next = p->next; free(p); p = NULL; printf("删除成功\n"); } }}int delete_element(node *head, ElemType const x) //删除链表中一个指定的x元素{ node *p, *q; if (head == NULL) //链表下溢，-1 return -1; if (x == head->data) //判断第一个结点的数据是不是x { p = head; head = head->next; free(p); p = NULL; return 0; } else { while (NULL != head&&head->data != x) //在链表剩下的元素中寻找x { q = head; head = head->next; } if (NULL == head) //没找到返回 0 return 0; else { p = head; q->next = p->next; free(p); p = NULL; } } return 1; //删除成功返回1}void delete_all_element(node *ret, ElemType x) //根据元素删除，将这个链表里面的这个元素的结点全部删除{ int m = 0; int count = 0; while (1) { m = delete_element(ret, x); if (m == 0 || m == -1) break; count++; } if (m == 0) { if (count == 0) printf("没有此元素\n"); else printf("删除成功\n"); } else printf("链表下溢\n");}void find_element(node *head, ElemType const x) //通过元素查找链表中该元素的位置找到返回结点{ head = head->next; //head是头结点，head->next指向下一个结点 int count = 0; int i = 0; while (head) { count++; if (head->data == x) //如果找到输出count { i++; printf("元素位置：%d\n", count); } head = head->next; } if (i == 0) //如果没有输出count，说明没有x，所以i==0; printf("查询无果\n"); else printf("\n");}void find_place(node *head, int i) //通过位置来查找该链表中位于此位置的元素{ head = head->next; while (i>1) { //如果要找第i个结点的元素，则要先找到第i-1个结点 i--; head = head->next; if (head->next == NULL) break; } if (i == 1) printf("结点元素：%d\n", head->data); else printf("查询无果\n");}void length_list(node *head) //求链表长度{ head = head->next; int count = 0; while (head) { count++; head = head->next; } printf("链表长度：%d\n", count);}void output(node *head) //打印链表{ head = head->next; //让头结点指向下一个结点 printf("输出链表："); while (head != NULL) { printf("%d ", head->data); head = head->next; } printf("\n");}node* inits_linklist(node *head) //初始化链表{ node *p,*r; p = head; while (p != NULL) { r = p; p = p->next; free(r); r = NULL; } head = NULL; p = NULL; printf("初始化成功\n"); return head;}void sortrank(node *head) //对链表进行排序{ node *p, *r; p = head->next; ElemType tmp; while (p != NULL) { r = head->next; while (r->next != NULL) { if ((r->data) > (r->next->data)) { tmp = r->data; r->data = r->next->data; r->next->data = tmp; } r = r->next; } p = p->next; } printf("排序成功\n");}int means() //选择方式{ int means = 0; while (1) { printf("请选择的方式："); scanf("%d", &means); if (means == 1 || means == 2) break; else printf("选择无效，请重新输入\n"); } return means;}//函数测试：#include"linklist.h"int main(){ printf("*****************************************\n"); printf("*****************************************\n"); printf("**1.Creat_LinkList 2.Insert_Element **\n"); printf("**3.Find 4.Delete_Element **\n"); printf("**5.Length_LinkList 6.Output_LinkList**\n"); printf("*7.InitsLinkLinst 8.Sortrank **\n"); printf("*0.Exit *******************\n\n\n"); node *ret=NULL; ElemType x; int i=0; int n = 0; while (1) //循环起来，直到选择0结束 { printf("请选择功能："); scanf("%d", &n); if (n == 0) { free(ret); exit(1); } if (n == 1 && ret == NULL) { //选择正序建立链表还是逆序建立链表，并且链表以0作为结束标志 printf("**1.creat_order 2.creat_reverse **\n"); if (means() == 1) ret = creat_order(); else ret = creat_reverse(); } else if (n != 1&& ret == NULL) //必须先建立链表，才能进行其他操作 printf("请建立链表\n"); else if (ret!=NULL&&n!=1) { switch (n) { case 2: printf("请输入要插入的位置和要插入的元素\n"); scanf("%d", &i); scanf("%d", &x); insert(ret, i, x); break; case 3: //选择根据位置查找还是根据元素查找 { printf("**1.find_place 2.find_element **\n"); if (means() == 1) { printf("请输入要查找的位置："); scanf("%d", &i); find_place(ret, i); } else { printf("请输入要查找的元素："); scanf("%d", &x); find_element(ret, x); } } break; case 4: //选择根据位置删除还是根据元素删除 { printf("**1.delete_place 2.delete_element **\n"); if (means() == 1) { printf("请输入要删除的位置："); scanf("%d", &i); delete_place(ret, i); } else { printf("请输入要删除的元素："); scanf("%d", &x); delete_all_element(ret, x); //根据元素删除，将这个链表里面的这个元素的结点全部删除 } } break; case 5: length_list(ret); break; case 6: //打印链表 output(ret); break; case 7: //初始化链表,将链表制为空 ret = inits_linklist(ret); break; case 8: sortrank(ret); break; default: printf("选择无效，请重新选择\n"); break; } } } system("pause"); return 0;}