该例程包含了单链表的声明,创建,顺序插入,反序排列,
查找节点,删除节点的功能,并在 main 函数中一一得到了验证。
- /*
- * 实现链表的存储需要下列机制
- * 1、一种定义节点结构点机制,节点结构含有所有的域。
- * 2、一种在需要时创建节点的方法,可由 malloc 函数完成。
- * 3、一种删除不再需要节点的方法,可由 free 函数完成。
- *
- * 该例程包含了单链表的声明,创建,顺序插入,反序排列,查找节点,删除节点的功能,
- * 并在 main 函数中一一得到了验证。
- */
- #include<stdlib.h>
- #include<stdio.h>
- #include<assert.h>
- #define FALSE 0
- #define TRUE 1
- #define IS_FULL(ptr) ((!ptr))
- /* Node 为类型名,NODE 为标签名 */
- typedef struct NODE {
- int value;
- struct NODE *link;
- }Node;
- /* 创建一个单向节点 */
- struct NODE *creat1()
- {
- Node *first;
- first = (Node *)malloc(sizeof(Node));
- first->link = NULL;
- first->value = 5;
- return first;
- }
- /*
- * 总是在单链表起始端插入一个新值。
- */
- int sll_insert1(Node **rootp, int new_value)
- {
- Node *current, *new;
- current = *rootp;
- new = (Node *)malloc(sizeof(Node));
- if (new == NULL)
- return FALSE;
-
- new->link = current;
- *rootp = new;
- return TRUE;
- }
- /*
- * 总是在单链表末尾插入一个新值。
- */
- int sll_insert4(Node **rootp, int new_value)
- {
- Node *previous, *current, *new;
- previous = NULL;
- current = *rootp;
- while (current != NULL) {
- previous = current;
- current = current->link;
- }
- new = (Node *)malloc(sizeof(Node));
- if (new == NULL)
- return FALSE;
-
- new->link = current;
- previous->link = new;
- }
- /*
- * 插入到一个有序的单链表,按从小到大顺序。
- * 第一个参数是一个指向链表根指针的指针,第二个参数是需要插入的新值。
- * 起始位置、中间位置、末尾均可插入值。
- */
- int sll_insert2(Node **rootp, int new_value)
- {
- Node *previous, *current, *new;
- previous = NULL;
- current = *rootp;/* 获取第一个节点的指针 */
- while (current != NULL && current->value < new_value) {
- previous = current;
- current = current->link;
- }
- new = (Node*)malloc(sizeof(Node));
- if (new == NULL) {
- return FALSE;
- }
- new->value = new_value;
- new->link = current;
- if (previous == NULL) {/* 插入到起始位置 */
- *rootp = new;
- }
- else {/* 中间位置或者末尾 */
- previous->link = new;
- }
- return TRUE;
- }
- /*
- * 插入到一个有序的单链表。
- * 第一个参数是一个指向链表第一个节点link字段的指针,第二个参数是需要插入的新值。
- * 起始位置、中间位置、末尾均可插入值。
- * 要理解好指向当前节点的指针和指向当前节点 link 字段的指针,一个指向的是节点,另一个
- * 指向的是节点里面的值。
- */
- int sll_insert3(register Node **linkp, int new_value)
- {
- register Node *current, *new;
- current = *linkp;
- while (current != NULL && current->value < new_value) {
- linkp = ¤t->link;
- current = *linkp;
- }
-
- /*while ((current = *linkp) != NULL && current->value < new_value) {
- linkp = ¤t->link;
- }*/
- new = (Node*)malloc(sizeof(Node));
- if (new == NULL) {
- return FALSE;
- }
- new->value = new_value;
- new->link = current;
- *linkp = new;
- return TRUE;
- }
- /*
- * 计算一个单链表的节点数
- */
- int count_node(Node *root)
- {
- int count;
- for (count = 0; root != NULL; root = root->link)
- count += 1;
-
- return count;
- }
- /* 在一个无序单链表中寻找一个特定的值 */
- struct NODE *find_value(Node *root, int value)
- {
- while (root != NULL) {
- if (root->value == value)
- return root;
- root = root->link;
- }
- return NULL;
- }
- /*
- * 反序排列一个单链表的所有节点。当链表重排之后,返回一个指向新链表的头节点的指针。
- * 不使用额外的内存。
- */
- struct NODE *sin_reverse(Node *current)
- {
- Node *previous = NULL, *next;
- /*for (previous = NULL; current != NULL; current = next) {
- next = current->link;
- current->link = previous;
- previous = current;
- }*/
- /* 三个指针的位置为:previous,current,next */
- while (current != NULL) {
- next = current->link; //保存下一节点指针
- current->link = previous; //将节点的箭头反向
- previous = current; //一个节点的箭头反向后previous向后移动一步
- current = next; //一个节点的箭头反向后current 向后移动一步
- }
- return previous;
- }
- /*
- * 从单链表中移除一个节点。
- */
- int sin_remove(Node **linkp, Node *delete)
- {
- register Node *current;
- current = *linkp;
- assert(delete != NULL);
- while (current != NULL && current != delete) {
- linkp = ¤t->link;
- current = *linkp;
- }
-
- if (current == delete) {
- *linkp = current->link; //指向delete后面的节点
- free(current);
- return TRUE;
- }
- else return FALSE;
- }
- int main()
- {
- Node *root, *ptr;
- int count;
- //test the function sll_insert1
- /*root = creat1();//5
- sll_insert2(&root, 3);
- sll_insert2(&root, 4);
- printf("the sin_link contains :");
- for (ptr = root; ptr != NULL; ptr = ptr->link) {
- printf("%4d", ptr->value);
- }
- printf("\n");
- //test the function sll_insert4
- root = creat1();//5
- sll_insert2(&root, 6);
- sll_insert2(&root, 7);
- printf("the sin_link contains :");
- for (ptr = root; ptr != NULL; ptr = ptr->link) {
- printf("%4d", ptr->value);
- }
- printf("\n");
- //test the function sll_insert2
- root = creat1();//5
- sll_insert2(&root, 3);
- sll_insert2(&root, 6);
- sll_insert2(&root, 10);
- printf("the sin_link contains :");
- for (ptr = root; ptr != NULL; ptr = ptr->link) {
- printf("%4d", ptr->value);
- }
- printf("\n");*/
- //test the function sll_insert3,find_value ,count_node,sin_reverse
- root = creat1();//5
- sll_insert3(&root, 3);
- sll_insert3(&root, 6);
- sll_insert3(&root, 10);
- ptr = find_value(root, 10);
- printf("find_value=%d \n", ptr->value);
- count = count_node(root);
- printf("count_node=%d \n", count);
- ptr = sin_reverse(root);
- printf("the sin_link contains :");
- for (; ptr != NULL; ptr = ptr->link) {
- printf("%4d", ptr->value);
- }
- printf("\n");
- exit(0);
- }
阅读(2772) | 评论(0) | 转发(1) |