数据结构C //线性表（链表）ADT结构及相关函数

数据结构（C语言版）严蔚敏 吴伟民

线性表（链表）ADT结构及相关函数

环境：Linux Ubuntu（云服务器）

工具：vim

 

代码块（头文件，函数文件，主文件）

linklist.h头文件

/*************************************************************************> File Name: linklist.h> Author: > Mail: > Created Time: Thu 12 Sep 2024 10:37:03 AM CST************************************************************************/#ifndef _LINKLIST_H
#define _LINKLIST_H#include <stdio.h>
#include <stdlib.h>#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define NOEXIST -3typedef int Status;
typedef int ElemType;typedef struct LNode{ElemType data;int length;struct LNode *next;
}LNode, *LinkList;#define DATAFMT "%d"void CreateList_L(LinkList &L, int n);Status DestroyList_L(LinkList &L);Status ListEmpty_L(LinkList L);Status GetElem_L(LinkList L, int i, ElemType &e);int equal(ElemType a, ElemType b);Status LocateElem_L(LinkList L, ElemType e, int equal(ElemType, ElemType));Status PriorElem_L(LinkList L, ElemType cur_e, ElemType &pre_e);Status NextElem_L(LinkList L, ElemType cur_e, ElemType &next_e);Status ListInsert_L(LinkList &L, int i, ElemType e);Status ListDelete_L(LinkList &L, int i, ElemType &e);Status ClearList_L(LinkList &L);Status visit(ElemType e);Status ListTraverse_L(LinkList L, Status visit(ElemType));void unionList_L(LinkList &La, LinkList Lb);void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc);#endif

linklist.c函数文件

/*************************************************************************> File Name: linklist.c> Author: > Mail: > Created Time: Thu 12 Sep 2024 10:40:09 AM CST************************************************************************/#include <stdio.h>
#include <stdlib.h>
#include "linklist.h"void CreateList_L(LinkList &L, int n) {printf("Enter ");printf(DATAFMT, n);printf(" elem list: ");L = (LinkList)malloc(sizeof(LNode));L->next = NULL;int i;LNode *q = L;for(i = n; i > 0; --i) {LNode *p = (LinkList)malloc(sizeof(LNode));scanf(DATAFMT, &p->data);p->next = q->next;q->next = p;q = p;}L->length = n;
}//CreateList_LStatus DestroyList_L(LinkList &L) {free(L);return OK;
}//DestroyList_LStatus ListEmpty_L(LinkList L) {return L->length == 0 ? TRUE : FALSE;
}//ListEmpty_LStatus GetElem_L(LinkList L, int i, ElemType &e) {if(i < 1 || i > L->length) {return ERROR;}LinkList p = L->next;int j = 1;while(p && j < i) {p = p->next;++j;}if(!p || j > i) {return ERROR;}e = p->data;return OK;
}//GetElem_Lint equal(ElemType a, ElemType b) {return a == b ? TRUE : FALSE;
}//equalStatus LocateElem_L(LinkList L, ElemType e, int equal(ElemType, ElemType)) {int i;LNode *p = L->next;for(i = 1; p != NULL; i++, p = p->next) {if(equal(e, p->data)) {return i;}}return FALSE;
}//LocateElem_LStatus PriorElem_L(LinkList L, ElemType cur_e, ElemType &pre_e) {LNode *p = L->next;LNode *q = NULL;while(p && p->data != cur_e) {q = p;  // Store the previous nodep = p->next;}if (!q) {return ERROR;  // If q is still NULL, it means the current element is the first one}if (!p) {return NOEXIST;  // If the current element is not found, return NOEXIST}pre_e = q->data;return OK;
}//PriorElem_LStatus NextElem_L(LinkList L, ElemType cur_e, ElemType &next_e) {LNode *p = L->next;while (p && p->data != cur_e) {p = p->next;}if (!p) {return NOEXIST;  // If current element is not found, return NOEXIST}if (!p->next) {return ERROR;  // If there is no next element, return ERROR}next_e = p->next->data;return OK;
}//NextElem_LStatus ListInsert_L(LinkList &L, int i, ElemType e) {LinkList p = L;int j = 0;while(p && j < i - 1) {p = p->next;++j;}if(!p || j > i - 1) {return ERROR;}LNode *s = (LinkList)malloc(sizeof(LNode));s->data = e;s->next = p->next;p->next = s;L->length++;return OK;
}//ListInsert_LStatus ListDelete_L(LinkList &L, int i, ElemType &e) {LinkList p = L;int j = 0;while(p->next && j < i - 1) {p = p->next;++j;}if(!(p->next) || j > i - 1) {return ERROR;}LNode *q = p->next;p->next = q->next;e = q->data;free(q);L->length--;return OK;
}//ListDelete_LStatus ClearList_L(LinkList &L) {ElemType e;while(L->length != 0) {ListDelete_L(L, 1, e);}return OK;
}//ClearList_LStatus visit(ElemType e) {if(!e) return ERROR;printf(DATAFMT, e);printf(" ");return OK;
}//visitStatus ListTraverse_L(LinkList L, Status visit(ElemType)) {printf("List traverse: ");LinkList p;for(p = L->next; p != NULL; p = p->next) {if(!visit(p->data)) {return FALSE;}}printf("\n");return OK;
}//ListTraverse_Lvoid unionList_L(LinkList &La, LinkList Lb) {int La_len = La->length;int Lb_len = Lb->length;int i;ElemType e;for(i = 1; i <= Lb_len; i++) {GetElem_L(Lb, i, e);if(!LocateElem_L(La, e, equal)) {ListInsert_L(La, ++La_len, e);}}
}//unionList_Lvoid MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc) {LNode *pa = La->next;LNode *pb = Lb->next;LNode *pc;Lc = pc = La;while(pa && pb) {if(pa->data <= pb->data) {pc->next = pa;pc = pa;pa = pa->next;}else {pc->next = pb;pc = pb;pb = pb->next;}}pc->next = pa ? pa : pb;free(Lb);
}//MergeList_L

main.c主文件

/*************************************************************************> File Name: main.c> Author: > Mail: > Created Time: Thu 12 Sep 2024 10:41:49 AM CST************************************************************************/#include <stdio.h>
#include <stdlib.h>
#include "linklist.h"
#include "linklist.c"int main() {LinkList L;//Input the list and traverse itCreateList_L(L, 10);ListTraverse_L(L, visit);//Determine whether the list is emptyif(ListEmpty_L(L)) {printf("List is empty!\n\n");}else {printf("List is not empty!\n\n");}//Clear the listprintf("Prepare clear the list...\n");if(ClearList_L(L)) {printf("List is clear!\n");}else {printf("List is not clear!\n");}ListTraverse_L(L, visit);//After clearing the list, check whether the list is emptyif(ListEmpty_L(L)) {printf("List is empty!\n\n");}else {printf("List is not empty!\n\n");}//Input the list againCreateList_L(L, 10);printf("\n");//Input the number of the element you want to getint num1;printf("Enter the number of the element you want to get: ");scanf("%d", &num1);ElemType e1;if(GetElem_L(L, num1, e1)) {printf("No.%d Elem is ", num1);printf(DATAFMT, e1);printf(".\n\n");}else {printf("The number is error!\n\n");}//Input the element you want to locateElemType elem;printf("Eneter the element you want to locate: ");scanf(DATAFMT, &elem);if(LocateElem_L(L, elem, equal)) {printf("The position of the element ");printf(DATAFMT, elem);printf(" is %d.\n\n", LocateElem_L(L, elem, equal));}else {printf("The list doesn't have the elem!\n\n");}//Input the element for which you want to get the priority elementElemType num2, e2;printf("Enter the element for which you want to get the priority element: ");scanf(DATAFMT, &num2);if(PriorElem_L(L, num2, e2) == -3) {printf("The elem ");printf(DATAFMT, num2);printf(" doesn't exist!\n\n");}else if(PriorElem_L(L, num2, e2) == 0) {printf("The elem ");printf(DATAFMT, num2);printf(" doesn't have prior elem.\n\n");}else {printf("The prior elem of ");printf(DATAFMT, num2);printf(" is ");printf(DATAFMT, e2);printf(".\n\n");}//Input the element for which you want to get the next elementElemType num3, e3;printf("Enter the element for which you want to get the next element: ");scanf(DATAFMT, &num3);if(NextElem_L(L, num3, e3) == -3) {printf("The elem ");printf(DATAFMT, num3);printf(" dosen't exist!\n\n");}else if(NextElem_L(L, num3, e3) == 0) {printf("The elem ");printf(DATAFMT, num3);printf(" dosen't have next elem.\n\n");}else {printf("The next elem of ");printf(DATAFMT, num3);printf(" is ");printf(DATAFMT, e3);printf(".\n\n");}//Input the element and the location you want to insertint num4;ElemType e4;printf("Enter the element you want to insert: ");scanf(DATAFMT, &e4);printf("Enter the location you want to insert: ");scanf("%d", &num4);while(num4 < 1 || num4 > L->length) {printf("Error Location! Retry!\n");printf("Enter the location you want to insert: ");scanf("%d", &num4);}printf("Insert elem ");printf(DATAFMT, e4);printf(" to position %d...\n", num4);ListInsert_L(L, num4, e4);ListTraverse_L(L, visit);printf("\n");//Input the number of the element you want to deleteint num5;printf("Enter the number of the element you want to delete: ");scanf("%d", &num5);while(num5 < 1 || num5 > L->length) {printf("Error Number! Retry!\n");printf("Enter the number of the element you want to delete: ");scanf("%d", &num5);}ElemType e5;printf("Prepare delete the No.%d elem...\n", num5);ListDelete_L(L, num5, e5);printf("The delete elem is ");printf(DATAFMT, e5);printf(".\n");ListTraverse_L(L, visit);printf("\n");//Destroy the listprintf("Prepare destroy the list...\n");if(DestroyList_L(L)) {printf("List is destroyed!\n\n");}else {printf("List is not destroyed!\n\n");}//Use unionList_L methodsLinkList La1, Lb1;CreateList_L(La1, 5);ListTraverse_L(La1, visit);CreateList_L(Lb1, 5);ListTraverse_L(Lb1, visit);printf("\nUnion List La1 and Lb1...\n");unionList_L(La1, Lb1);ListTraverse_L(La1, visit);printf("\n");//Use MergeList_L methodsLinkList La2, Lb2, Lc;CreateList_L(La2, 5);ListTraverse_L(La2, visit);CreateList_L(Lb2, 5);ListTraverse_L(Lb2, visit);printf("\nMerge List La2 and Lb2...\n");MergeList_L(La2, Lb2, Lc);ListTraverse_L(Lc, visit);return 0;
}

运行结果显示如下：