C语言版本：单链表的实现

slist.h

 #ifndef __SLIST_H__

 #define __SLIST_H__

 #include<cstdio>

 #include<malloc.h>

 #include<assert.h>

 typedef int ElemType;

 typedef struct Node { //定义单链表中的结点信息

     ElemType data; //结点的数据域

     struct Node *next; //结点的指针域

 }Node,*PNode;

 typedef struct List { //定义单链表的链表信息

     PNode first; //first指向单链表中的第一个结点

     PNode last; //last指向单链表中的最后一个结点

     size_t size; //记录单链表中的结点个数

 }List;

 void InitList(List *list);//初始化单链表

 void push_back(List *list, ElemType x);//在单链表的末尾插入元素

 void push_front(List *list, ElemType x);//在单链表的头部插入元素

 void show_list(List *list);//打印单链表

 void pop_back(List *list);//删除单链表的最后一个元素

 void pop_front(List *list);//删除单链表的第一个元素

 void insert_val(List *list, ElemType val);//将数据元素插入到单链表中（要求此时单链表中的数据元素顺序排列）

 Node* find(List *list, ElemType x);//查找单链表中数据值为x的结点

 int length(List *list);//求单链表的长度

 void delete_val(List *list, ElemType x);//按值删除单链表中的某个数据元素

 void sort(List *list);//对单链表进行排序

 void reverse(List *list);//逆置单链表

 void clear(List *list);//清除单链表

 void destroy(List *list);//摧毁单链表

 #endif //__SLIST_H__

slist.cpp

 #include"slist.h"

 void InitList(List *list) {

     list->first = list->last = (Node*)malloc(sizeof(Node)); //头结点

     assert(list->first != NULL);

     list->first->next = NULL;

     list->size = ;

 }

 void push_back(List *list, ElemType x) {

     //step 1：创建一个新的结点

     Node *s = (Node*)malloc(sizeof(Node));

     assert(s != NULL);

     s->data = x;

     s->next = NULL;

     //step 2：将新结点插入单链表的表尾

     list->last->next = s;

     list->last = s;

     //step 3：更新单链表的长度

     list->size++;

 }

 void push_front(List *list, ElemType x) {

     //step 1：创建一个新的结点

     Node *s = (Node*)malloc(sizeof(Node));

     assert(s != NULL);

     s->data = x;

     s->next = NULL;

     //step 2：将新结点插入单链表的表头

     s->next = list->first->next;

     list->first->next = s;

     //step 3：判断插入的结点是否是单链表的第一个结点，若是更新链表的尾指针

     if (list->size == )

         list->last = s;

     //step 4：更新单链表的长度

     list->size++;

 }

 void show_list(List *list) {

     //step 1：指针p指向单链表的第一个结点

     Node *p = list->first->next;

     //step 2：循环打印结点的信息

     while (p != NULL) {

         printf("%d->", p->data);

         p = p->next;

     }

     printf("Nul.\n");

 }

 void pop_back(List *list) {

     //step 1：判断单链表是否为空

     if (list->size == ) return;

     //step 2：定义指针p使其指向目标结点的前一个结点

     Node *p = list->first;//从头结点开始

     while (p->next != list->last)

         p = p->next;

     //step 3：删除目标结点

     free(list->last);

     list->last = p;

     list->last->next = NULL;

     //step 4：更新单链表的长度

     list->size--;

 }

 void pop_front(List *list) {

     //step 1：判断单链表是否为空

     if (list->size == ) return;

     //step 2：定义指针p使其指向目标结点的前一个结点

     Node *p = list->first->next;

     //step 3：删除目标结点

     list->first->next = p->next;

     free(p);

     //step 4：判断删除的结点是否是单链表的最后一个结点，若是则更新单链表的尾指针

     if (list->size == )

         list->last = list->first;

     //step 4：更新单链表的长度

     list->size--;

 }

 void insert_val(List *list, ElemType x) {

     //step 1：创建一个新的结点

     Node *s = (Node*)malloc(sizeof(Node));

     assert(s != NULL);

     s->data = x;

     s->next = NULL;

     //step 2：定义指针p使其指向待插入位置的前一个结点

     Node *p = list->first;//从头结点开始

     while (p->next != NULL && p->next->data < s->data)

         p = p->next;

     //step 3：判断结点的待插入位置是否是表尾，若是则更新单链表的尾指针

     if (p->next == NULL)

         list->last = s;

     //step 4：插入结点

     s->next = p->next;

     p->next = s;

     //step 5：更新单链表长度

     list->size++;

 }

 Node* find(List *list, ElemType x) {

     //step 1：指针p指向单链表的第一个结点

     Node *p = list->first->next;

     //step 2：按照循环顺序查找链表结点

     while (p != NULL && p->data != x)

         p = p->next;

     return p;

 }

 int length(List *list) {

     return list->size;

 }

 void delete_val(List *list, ElemType x) {

     //step 1：判断单链表是否为空

     if (list->size == ) return;

     //step 2：确定结点在单链表中的位置，并判断其是否存在于单链表中

     Node *p = find(list, x);

     if (p == NULL) {

         printf("要删除的数据不存在！\n");

         return;

     }

     //step 3：判断结点位置是否是表尾

     if (p == list->last)//是表尾

         pop_back(list);

     else {//不是表尾

         Node *q = p->next;

         p->data = q->data;

         p->next = q->next;

         free(q);

         list->size--;

     }

 }

 void sort(List *list) {

     //step 1：判断单链表中的结点数是否为0或1

     if (list->size ==  || list->size == ) return;

     //step 2：将单链表中第一个结点之后的链表部分截出，方便重新按顺序插入链表之中

     Node *s = list->first->next; // 指针s指向单链表的第一个节点

     Node *p = s->next;//q指向s后面的结点

     list->last = s;//单链表的尾指针指向单链表的第一个结点

     list->last->next = NULL;//截断链表

     //step 3：将截出的链表中的结点根据其数据域大小重新插入到原来链表中

     while (p != NULL) {

         s = p;

         p = p->next;

         Node *q = list->first;

         while (q->next != NULL && q->next->data < s->data)

             q = q->next;

         if (q->next == NULL)//判断q此时指向的是否是单链表的最后一个结点，若是则更新链表的尾指针

             list->last = s;

         //将结点重新插入链表

         s->next = q->next;

         q->next = s;

     }

 }

 void reverse(List *list) {

     //step 1：判断单链表中的结点数是否为0或1

     if (list->size ==  || list->size == ) return;

     //step 2：将单链表中第一个结点之后的链表部分截出，然后将截出的链表中的结点按头插法重新插入到原链表中

     Node *p = list->first->next;

     Node *q = p->next;

     list->last = p;

     list->last->next = NULL;

     while (q != NULL) {

         p = q;

         q = q->next;

         p->next = list->first->next;

         list->first->next = p;

     }

 }

 void clear(List *list) {

     //step 1：判断单链表是否为空

     if (list->size == ) return;

     //step 2：释放单链表中的每一个结点

     Node *p = list->first->next;

     while (p != NULL) {

         list->first->next = p->next;

         free(p);

         p = list->first->next;

     }

     //step 3：头指针和尾指针重新都指向头结点

     list->last = list->first;

     //step 4：更新链表长度

     list->size = ;

 }

 void destroy(List *list) {

     //step 1：清空单链表

     clear(list);

     //step 2：释放头结点

     free(list->first);

     //step 3：头指针和尾指针都赋值为空

     list->first = list->last = NULL;

 }

main.cpp

 #include"slist.h"

 void main() {

     List mylist;

     InitList(&mylist);

     ElemType item;

     Node *p = NULL;

     int select = ;

     while (select) {

         printf("*******************************************\n");

         printf("*[1]  push_back        [2]  push_front    *\n");

         printf("*[3]  show_list        [4]  pop_back      *\n");

         printf("*[5]  pop_front        [6]  insert_val    *\n");

         printf("*[7]  find             [8]  length        *\n");

         printf("*[9]  delete_val       [10] sort          *\n");

         printf("*[11] reverse          [12] clear         *\n");

         printf("*[13*] destroy         [0] quit_system    *\n");

         printf("*******************************************\n");

         printf("请选择：>>");

         scanf("%d", &select);

         if (select == ) break;

         switch (select) {

         case :

             printf("请输入要插入的数据（-1结束）:>");

             while (scanf("%d", &item), item != -) {

                 push_back(&mylist, item);

             }

             break;

         case :

             printf("请输入要插入的数据（-1结束）:>");

             while (scanf("%d", &item), item != -) {

                 push_front(&mylist, item);

             }

             break;

         case :

             show_list(&mylist);

             break;

         case :

             pop_back(&mylist);

             break;

         case :

             pop_front(&mylist);

             break;

         case :

             printf("请输入要插入的数据:>");

             scanf("%d", &item);

             insert_val(&mylist, item);

             break;

         case :

             printf("请输入要查找的数据:>");

             scanf("%d", &item);

             p = find(&mylist, item);

             if (p == NULL)

                 printf("要查找的数据在单链表中不存在！\n");

             break;

         case :

             printf("单链表的长度为%d\n", length(&mylist));

             break;

         case :

             printf("请输入要删除的值:>");

             scanf("%d", &item);

             delete_val(&mylist, item);

             break;

         case :

             sort(&mylist);

             break;

         case :

             reverse(&mylist);

             break;

         case :

             clear(&mylist);

             break;

             //case 13:

             //destroy(&mylist);

             //break;

         default:

             printf("选择错误,请重新选择！\n");

             break;

         }

     }

     destroy(&mylist); //程序结束，摧毁链表

 }

巴特西

C语言版本：单链表的实现

最新文章

热门文章