单链表不带头标准c语言实现

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表。

下面给出不带头的单链表标准实现：

  1. #include <stdio.h>
  2. #include <stdlib.h>
  4. typedef struct node
  5. {
  6.     int data;
  7.     struct node *next;
  8. } Node;
  10. void pushBackList(Node *list, int data) //尾插
  11. {
  12.     Node *head = list;
  13.     Node *newNode = (Node *)malloc(sizeof(Node)); //申请空间
  14.     newNode->data = data;
  15.     newNode->next = NULL;
  16.     if (list == NULL) //为空
  17.         list = newNode;
  18.     else //非空
  19.     {
  20.         while (head->next != NULL)
  21.             head = head->next;
  22.         head->next = newNode;
  23.     }
  24. }
  26. /* 初始条件：链式线性表L已存在。操作结果：返回L中数据元素个数 */
  27. int sizeList(Node *list)
  28. {
  29.     int i = 0;
  30.     Node *p = list->next; /* p指向第一个结点 */
  31.     while (p)
  32.     {
  33.         i++;
  34.         p = p->next;
  35.     }
  36.     return i;
  37. }
  39. int insertList(Node *list, int index, int data) //插入
  40. {
  41.     int n;
  43.     int size = sizeList(list); //获取链表长度
  45.     Node *head = list;
  46.     Node *newNode, *temp;
  47.     if (index < 0 || index > size)
  48.         return 0;                           //非法，要插入的位置小于0，大于链表长度
  49.     newNode = (Node *)malloc(sizeof(Node)); //创建新节点
  50.     newNode->data = data;
  51.     newNode->next = NULL;
  52.     if (index == 0) //头插
  53.     {
  54.         newNode->next = head;
  55.         list = newNode;
  56.         return 1;
  57.     }
  58.     for (n = 1; n < index; n++) //非头插
  59.         head = head->next;
  60.     if (index != size)
  61.         newNode->next = head->next;
  62.     //链表尾部next不需指定
  63.     head->next = newNode;
  64.     return 1;
  65. }
  67. void deleteList(Node *list, int data) //按值删除
  68. {
  69.     Node *head = list;
  70.     Node *temp;
  71.     while (head->next != NULL)
  72.     {
  73.         if (head->next->data != data)
  74.         {
  75.             head = head->next;
  76.             continue;
  77.         }
  78.         temp = head->next;
  79.         if (head->next->next == NULL) //尾节点删除
  80.             head->next = NULL;
  81.         else
  82.             head->next = temp->next;
  83.         free(temp);
  84.     }
  85.     head = list;
  86.     if (head->data == data) //头结点删除
  87.     {
  88.         temp = head;
  89.         list = head->next;
  90.         head = head->next;
  91.         free(temp);
  92.     }
  93. }
  95. int printList(Node *list) //打印
  96. {
  97.     if (list->next == NULL)
  98.     {
  99.         printf("打印 \n");
  100.         return 0;
  101.     }
  102.     Node *temp = list->next;
  103.     for (; temp != NULL; temp = temp->next)
  104.         printf("%d ", temp->data);
  105.     printf("\n");
  107.     return 1;
  108. }
  110. int freeList(Node *list) //清空
  111. {
  112.     /*
  113.     暂时未知
  114.     */
  115.     // Node *head = list;
  116.     // Node *temp = NULL;
  117.     // printf("666");
  118.     // while (head != NULL) //依次释放
  119.     // {
  120.     //     temp = head;
  121.     //     head = head->next;
  122.     //     free(temp);
  123.     // }
  124.     list->next = NULL; //置空
  125.     printf("清空\n");
  126.     return 0;
  127. }
  130. int main(void) //测试
  131. {
  132.     Node *head;
  133.     for (int i = 0; i < 10; i++)
  134.     {
  135.         pushBackList(head, i);
  136.     }
  137.     insertList(head, 10, 10);
  139.     insertList(head, 5, 10);
  141.     printList(head);
  143.     deleteList(head,10);
  145.     printList(head);
  147.     int a = freeList(head);
  149.     printf("%d \n", a);
  151.     printList(head);
  152. }

运行结果

  1. 0 1 2 3 10 4 5 6 7 8 10 
  2. 0 1 2 3 4 5 6 7 8 
  3. 清空
  4. 0 
  5. 打印

别的也没啥了，都是基本操作 有些代码要分情况，很麻烦，可读性较强吧

单链表不带头压缩c语言实现

注：单追求代码简洁，所以写法可能有点不标准。

  1. //第一次拿c开始写数据结构，因为自己写的，追求代码量少，和学院ppt不太一样。有错请指出
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <string.h>
  5. typedef struct node//定义节点
  6. {
  7.     int data;
  8.     struct node * next;
  9. }Node;
  11. //函数介绍
  12. void printlist(Node * head);//打印链表
  13. int lenlist(Node * head);//返回链表长度
  14. void insertlist(Node ** list,int data,int index);//插入元素
  15. void pushback(Node ** head,int data);//尾部插入
  16. void freelist(Node ** head);//清空链表
  17. void deletelist(Node ** list,int data);//删除元素
  18. Node * findnode(Node ** list,int data);//查找
  19. void change(Node ** list,int data,int temp);//改变值
  21. void printlist(Node * head)//打印链表
  22. {
  23.     for(;head!=NULL;head=head->next) printf("%d ",head->data);
  24.     printf("\n");//为了其他函数打印，最后换行
  25. }
  27. int lenlist(Node * head)//返回链表长度
  28. {
  29.     int len;
  30.     Node * temp = head;
  31.     for(len=0; temp!=NULL; len++) temp=temp->next;
  32.     return len;
  33. }
  35. void insertlist(Node ** list,int data,int index)//插入元素，用*list将head指针和next统一表示
  36. {
  37.     if(index<0 || index>lenlist(*list))return;//判断非法输入
  38.     Node * newnode=(Node *)malloc(sizeof(Node));//创建
  39.     newnode->data=data;
  40.     newnode->next=NULL;
  41.     while(index--)list=&((*list)->next);//插入
  42.     newnode->next=*list;
  43.     *list=newnode;
  44. }
  46. void pushback(Node ** head,int data)//尾插，同上
  47. {
  48.     Node * newnode=(Node *)malloc(sizeof(Node));//创建
  49.     newnode->data=data;
  50.     newnode->next=NULL;
  51.     while(*head!=NULL)head=&((*head)->next);//插入
  52.     *head=newnode;
  53. }
  55. void freelist(Node ** head)//清空链表
  56. {
  57.     Node * temp=*head;
  58.     Node * ttemp;
  59.     *head=NULL;//指针设为空
  60.     while(temp!=NULL)//释放
  61.     {
  62.         ttemp=temp;
  63.         temp=temp->next;
  64.         free(ttemp);
  65.     }
  66. }
  68. void deletelist(Node ** list,int data)//删除链表节点
  69. {
  70.     Node * temp;//作用只是方便free
  71.     while((*list)->data!=data && (*list)->next!=NULL)list=&((*list)->next);
  72.     if((*list)->data==data){
  73.         temp=*list;
  74.         *list=(*list)->next;
  75.         free(temp);
  76.     }
  77. }
  79. Node * findnode(Node ** list,int data)//查找，返回指向节点的指针，若无返回空
  80. {
  81.     while((*list)->data!=data && (*list)!=NULL) list=&((*list)->next);
  82.     return *list;
  83. }
  85. void change(Node ** list,int data,int temp)//改变
  86. {
  87.     while((*list)->data!=data && (*list)->next!=NULL)list=&((*list)->next);
  88.     if((*list)->data==data)(*list)->data=temp;
  89. }
  91. int main(void)//测试
  92. {
  93.     Node * head=NULL;
  94.     Node ** gg=&head;
  95.     int i;
  96.     for(i=0;i<10;i++)pushback(gg,i);
  97.     printf("链表元素依次为: ");
  98.     printlist(head);
  99.     printf("长度为%d\n",lenlist(head));
  100.     freelist(gg);
  101.     printf("释放后长度为%d\n",lenlist(head));
  102.     for(i=0;i<10;i++)pushback(gg,i);
  103.     deletelist(gg,0);//头
  104.     deletelist(gg,9);//尾
  105.     deletelist(gg,5);
  106.     deletelist(gg,100);//不存在
  107.     printf("再次创建链表，删除节点后\n");
  108.     printlist(head);
  109.     freelist(gg);
  110.     for(i=0;i<5;i++)pushback(gg,i);
  111.     insertlist(gg,5,0);//头
  112.     insertlist(gg,5,5);
  113.     insertlist(gg,5,7);//尾
  114.     insertlist(gg,5,10);//不存在
  115.     printlist(head);
  116.     printf("找到%d\n把3变为100",*findnode(gg,5));
  117.     change(gg,3,100);
  118.     change(gg,11111,1);//不存在
  119.     printlist(head);
  120. }

运行结果

  1. 链表元素依次为: 0 1 2 3 4 5 6 7 8 9 
  2. 长度为10
  3. 释放后长度为0
  4. 再次创建链表，删除节点后
  5. 1 2 3 4 6 7 8 
  6. 5 0 1 2 3 5 4 5 
  7. 找到6422000
  8. 把3变为1005 0 1 2 100 5 4 5