数据结构-链表-拓冰建站

实现功能：

1. 定义结构体

typedef int data_t;typedef struct note
{data_t data;struct note *next;
}listnote, *linklist;

data_t data;：定义了一个名为data的字段，其类型为data_t；

struct note *next;：定义了一个名为next的指针字段，该指针指向与当前结构体相同

类型的下一个结构体

listnote是struct note的别名

linklist是一个指向struct note的指针的别名

2. 创建一个空链表

linklist list_create(){linklist H;//1. 申请内存H = (linklist)malloc(sizeof(listnote));if(H ==NULL){printf("malloc failed\n");}//2. 赋初值H->data = 0;H->next = NULL;//3. 返回值return H;
}

3. 尾部插入和遍历

尾部插入分为三步：1. 建立一个新节点

①malloc

②赋初值

2. 找尾节点

3. 实现尾部插入

int list_tail_insert(linklist H,data_t value){if (H == NULL){printf("H is NULL\n");return -1;}//1.new a notelinklist p;linklist q;if ((p=(linklist)malloc(sizeof(listnote)))== NULL){printf("malloc is failed\n");return -1;}p->data = value;p->next = NULL;//2. find tail listq = H;while (q->next != NULL){q = q->next;}//3. fail insertq->next = p;return 0;
}
int list_show(linklist H){if (H == NULL){printf("H is NULL\n");return -1;}linklist p;p = H;while (p->next != NULL){printf("%d ",p->next->data);p = p->next;}puts("");}

//main函数
#include <stdio.h>
#include "linklist.h"int main(int argc, char const *argv[])
{linklist H;int value;H = list_create();if(H == NULL){return -1;}printf("input:");while (1){scanf("%d",&value);if(value == -1){break;}list_tail_insert(H,value);printf("input:");}return 0;
}

遍历：

int list_show(linklist H){if (H == NULL){printf("H is NULL\n");return -1;}linklist p;p = H;while (p->next != NULL){printf("%d ",p->next->data);p = p->next;}puts("");}

4. 通过序号查找值

linklist list_get(linklist H,int pos){int i =-1;linklist p;p = H;if(pos == -1){return H;}while (i < pos){p = p->next;if (p == NULL){printf("pos is invalid\n");return NULL;}i++;}return p;
}

    //main函数p =list_get(H, 2);if (p != NULL){printf("value = %d\n",p->data);}

5. 在某一位置插入元素

int list_insert(linklist H,data_t value,int pos){linklist p;linklist q;if (H == NULL){printf("H is NULL\n");return -1;}// 1. 定位节点 p （pos-1）p =list_get(H,pos-1);if (p == NULL){printf("p is NULL\n");return -1;}// 2. 新节点q申请内存，赋初值if ((q = (linklist)malloc(sizeof(listnote)))== NULL){printf("malloc failed\n");return -1;}q->next = NULL;q->data = value;//3.完成插入操作q->next = p->next;p->next = q;return 0;
}

6. 链表删除某个元素

1. 检查链表的入口参数

2. 找前驱

3. 更新链表

4. 释放删除的内存

int list_del(linklist H,int pos){linklist p;linklist q;//1. if(H == NULL){printf("H is NULL\n");return -1;}//2.p = list_get(H,pos-1);if(p == NULL){return -1;}if(p->next == NULL){printf("delete pos invalid\n");return -1;}//3.q = p->next;p->next = q->next;//4.printf("free = %d\n",q->data);free(q);q = NULL;return 0;
}

7. 释放链表内存

linklist list_free(linklist H){linklist p;if (H == NULL){return NULL;}p = H;printf("free:");while (H != NULL){p = H;printf("%d ",p->data);H = H->next;free(p);}puts("");return NULL;
}

8. 链表反转

int list_inver(linklist H){linklist p;linklist q;if (H == NULL){printf("H is NULL\n");return -1;}if (H->next == NULL ||H->next->next == NULL){return 0;}p = H->next->next;H->next->next = NULL;while (p != NULL){q = p;p =p->next;q->next = H->next;H->next = q;}return 0;
}

9. 求相邻结点最大值

//linklist.c 部分
linklist list_adjmax(linklist H,data_t *value){linklist p , q, r;data_t sum = 0;if (H == NULL){printf("H is NULL\n");return NULL;}if(H->next == NULL ||H->next->next == NULL || H->next->next->next == NULL){return H;}q = H->next;p = q->next;r = q;sum = p->data + q->data;while (p->next != NULL){p = p->next;q = q->next;if (sum < p->data + q->data){sum =p->data + q->data;r = q;}}*value = sum;return r;  
}

//main
linklist r;
int sum;r = list_adjmax(H,&sum);if (r != NULL && r != H){printf("data=%d,sum=%d\n",r->data,sum);}

10. 合并两个有序链表

//linklist.c
int list_merge(linklist H,linklist R){linklist p,q,r;if (H == NULL){printf("H is NULL\n");return -1;}if (R == NULL){printf("R is NULL\n");return -1;}p = H->next;q = R->next;r = H;H->next = NULL;R->next = NULL;while (p && q){if (p->data <= q->data){r->next = p;p = p->next;r = r->next;r->next = NULL;}else{r->next = q;q = q->next;r = r->next;r->next = NULL;}if (q == NULL){r->next = p;}else{r->next = q;}}return 0;
}

//main.c
#include <stdio.h>
#include "linklist.h"int listmerge();int main(int argc, char const *argv[])
{   linklist H,R;int a[]={1,3,5,7,9,243};int b[]={2,4,8,13};int i;H = list_create();if(H == NULL){return -1;}R = list_create();if(R == NULL){return -1;}for ( i = 0; i < sizeof(a)/sizeof(int); i++){list_tail_insert(H,a[i]);}for ( i = 0; i < sizeof(b)/sizeof(int); i++){list_tail_insert(R,b[i]);}list_show(H);list_show(R);list_merge(H,R);list_show(H);list_free(H);list_free(R); return 0;
}