July_One_Week—linked list

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 
  4 typedef struct linklist
  5 {
  6     unsigned int count;
  7     struct linklist *next;
  8 }linklist;
  9 
 10 linklist* CreatLinklist(int len)
 11 {
 12     linklist *head = NULL, *pre = NULL;
 13     head = (linklist*)malloc(sizeof(linklist));//头指针。
 14     pre = (linklist*)malloc(sizeof(linklist)); //pre-previous, 前一个;相对于head来说是后一个。
 15     printf("Please input the data:
");
 16     scanf("%u", &pre->count);
 17     head->next = pre; //head的后一个是pre。
 18     pre->next = NULL; //pre的next是NULL。
 19 
 20     for (int i = 1; i < len; i++)
 21     {
 22         linklist* tmp = (linklist*)malloc(sizeof(linklist));
 23         scanf("%u", &tmp->count);
 24         pre->next = tmp; //新加的节点放在pre后。
 25         tmp->next = NULL; //新加节点的next是NULL。
 26         pre = tmp; //新加的节点变成pre，等待下一个tmp。
 27     }
 28     return head;
 29 }
 30 
 31 int Outputlinklist(linklist *head)
 32 {
 33     printf("#### Output linklist.
");
 34     if (head != NULL)
 35     {
 36         while (head->next != NULL)
 37         {
 38             printf("%u
", head->next->count);
 39             head = head->next;
 40         }
 41     }
 42 }
 43 
 44 int Lenlinklist(linklist *head)
 45 {
 46     int len = 0;
 47     if (NULL == head->next)
 48         return len;
 49     len++;
 50     linklist *p = NULL;
 51     p = head->next;
 52     while(p->next != NULL)
 53     {
 54         len++;
 55         p = p->next;
 56     }
 57     return len;
 58 }
 59 
 60 int InsertLinklist(linklist *head, int index)
 61 {
 62     int len = 0;
 63     len = Lenlinklist(head);
 64     printf("the length of linklist:%d, the insert index:%d
", len, index);
 65     if (index < 1 || index > len)
 66         return -1;
 67     int cur_index = 1;
 68     linklist *p = NULL;
 69     p = head->next;
 70     while(cur_index < index)
 71     {
 72         p = p->next;
 73         cur_index++;
 74     }
 75     linklist *node = (linklist*)malloc(sizeof(linklist));
 76     printf("Please input the new node data:
");
 77     scanf("%u", &node->count);
 78     node->next = p->next;
 79     p->next = node;
 80     return 0;
 81 }
 82 
 83 int DeleteNode(linklist *head, int index)
 84 {
 85     int len = 0;
 86     len = Lenlinklist(head);
 87 
 88     if((index < 1) || (index > len))
 89         return -1;
 90 
 91     int cur_index = 1;
 92     linklist *p = NULL;
 93     linklist *q = NULL;
 94     p = head->next;
 95     while(cur_index < index)
 96     {
 97         p = p->next;
 98         cur_index++;
 99     }
100     q = p->next;
101     p->next = q->next;
102     free(q);
103     q = NULL;
104 }
105 
106 linklist *Reverselinklist(linklist *head)
107 {
108     linklist *p=NULL, *pre=NULL, *pnext=NULL;
109 
110     p = head->next;
111     while(p!=NULL)
112     {
113         pnext = p->next;
114         if(pnext == NULL)
115             head->next = p;
116         p->next = pre;
117         pre = p;
118         p = pnext;
119     }
120     return head;
121 }
122 
123 int main(void)
124 {
125     linklist *mylist = NULL;
126 
127     printf("#### Creat linklist.
");
128     mylist = CreatLinklist(5);
129     Outputlinklist(mylist);
130 
131     printf("#### Insert new node.
");
132     InsertLinklist(mylist, 2);
133     Outputlinklist(mylist);
134 
135     printf("#### Delete exist node.
");
136     DeleteNode(mylist, 4);
137     Outputlinklist(mylist);
138 
139     printf("#### Reverse Linklist.
");
140     Reverselinklist(mylist);
141     Outputlinklist(mylist);
142 
143     printf("Handle complete!");
144 }

1.线性表的链式存储和顺序存储的比较。

常见的数组就是线性表的顺序存储，各个结点之间被分配连续的物理内存，因此在查找上直接可以使用下标，速度很快，但是对于插入和删除操作需要在操作点之后执行移动操作，较为麻烦，并且数组在之前需要分配内存的大小，也就是需要我们知道结点的数量，这样就有一定的限制。
链表就是线性表的链式存储，各个结点之间在物理内存中是随机分配的，在查找时需要逐个遍历，但是在插入和删除操作时仅仅是局部性的指针切换，并且链表只有创建结点和删除结点时才会对内存进行操作，事先不需要知道结点数量。

2.单向链表属于线性表链式存储中最简单的一类，常见的操作包括：创建、删除、查找、插入、反序等。