实验1-1-3.zip

#include <stdio.h> #include <stdlib.h> #define OK 1 #define TRUE 1 #define FALSE 0 #define ERROR 0 #define OVERFLOW -1 typedef int Status; typedef int ElemType; struct LinkedListNode { int value; int length; struct LinkedListNode *next; }; typedef struct LinkedListNode List; typedef struct LinkedListNode *PtrList; Status InitList(List *); void DestroyList(List *); void ClearList(List *); Status ListEmpty(List); int ListLength(List); Status GetElem(List, int, ElemType *); int LocateElem(List, ElemType); Status ListInsert(List *, int, ElemType); Status ListDelete(List *, int, ElemType *); Status ListAppend(List *, ElemType); void ListTraverse(List); Status CreateSet(List *); Status SetUnion(List *, List); void SetIntersect(List *, List); void SetSubtract(List *, List); List *RetPriorAdd(List *t, int); Status InitList(List *LinkedList) { if (!LinkedList) return ERROR; LinkedList->next = NULL; LinkedList->length = 0; return OK; } void DestroyList(List *LinkedList) { if (!LinkedList) return; ClearList(LinkedList); } void ClearList(List *LinkedList) { if (!LinkedList) return; ElemType buf; while (!ListEmpty(*LinkedList)) ListDelete(LinkedList, 1, &buf); LinkedList->next = NULL; } Status ListEmpty(List list) { return list.length == 0; } int ListLength(List list) { return list.length; } Status GetElem(List list, int n, ElemType *bufData) { if (n > list.length || n < 1) return ERROR; PtrList PtrToNode = RetPriorAdd(&list, n); if (!bufData || !PtrToNode) return ERROR; *bufData = PtrToNode->next->value; return OK; } int LocateElem(List list, ElemType bufData) { int i = 0; PtrList PtrToNode = list.next; while (PtrToNode) { i++; if (PtrToNode->value == bufData) return i; PtrToNode = PtrToNode->next; } return 0; } List *RetPriorAdd(List *LinkedList, int n) { if (!LinkedList) return ERROR; if (n < 1 || n > LinkedList->length + 1) return ERROR; PtrList PtrToNode = LinkedList; int i = 0; while (PtrToNode->next && i < n - 1) { PtrToNode = PtrToNode->next; i++; } return PtrToNode; } Status ListInsert(List *LinkedList, int n, ElemType bufData) { if (!LinkedList) return ERROR; if (n < 1 || n > LinkedList->length + 1) return ERROR; PtrList PtrToNode = RetPriorAdd(LinkedList, n); PtrList PtrNewNode = (PtrList)malloc(sizeof(List)); if (!PtrNewNode) return OVERFLOW; PtrNewNode->value = bufData; PtrNewNode->next = PtrToNode->next; PtrToNode->next = PtrNewNode; (LinkedList->length)++; return OK; } Status ListDelete(List *LinkedList, int n, ElemType *bufData) { if (!LinkedList) return ERROR; if (n < 1 || n > LinkedList->length) return ERROR; PtrList PtrToNode_a, PtrToNode = RetPriorAdd(LinkedList, n); PtrToNode_a = PtrToNode->next; PtrToNode->next = PtrToNode_a->next; *bufData = PtrToNode_a->value; free(PtrToNode_a); (LinkedList->length)--; return OK; } Status ListAppend(List *LinkedList, ElemType bufData) { if (!LinkedList) return ERROR; Status Result = ListInsert(LinkedList, ListLength(*LinkedList) + 1, bufData); if (Result == OK) return OK; else if (Result == OVERFLOW) return OVERFLOW; else return ERROR; } void ListTraverse(List list) { printf("{ "); ElemType bufData; for (int i = 1; i <= list.length; i++) { GetElem(list, i, &bufData); printf("%d ", bufData); } printf("}"); } Status CreateSet(List *LinkedList) { if (!LinkedList) return ERROR; int n; ElemType data; ClearList(LinkedList); scanf("%d", &n); if (n < 0) return OK; for (int i = 1; i <= n && (scanf("%d", &data) != EOF); i++) { if (!LocateElem(*LinkedList, data)) { Status res; res = ListAppend(LinkedList, data); if (res == OVERFLOW) return OVERFLOW; } } return OK; } // Status CreateSet(List *LinkedList) // { // if (!LinkedList) // return ERROR; // int n; // ElemType data; // PtrList PtrToNode = LinkedList->next; // scanf("%d", &n); // if (n < 0) // return ERROR; // for (int i = 1; i <= n && (scanf("%d", &data) != EOF); i++) // { // if (PtrToNode) // { // PtrToNode->value = data; // PtrToNode = PtrToNode->next; // } // else // { // Status res; // res = ListAppend(LinkedList, data); // if (res == OVERFLOW) // return OVERFLOW; // } // } // return OK; // } Status SetUnion(List *LinkedList, List list) { if (!LinkedList) return ERROR; ElemType Data; int len_b = ListLength(list), position = 0; for (int i = 1; i <= len_b; i++) { GetElem(list, i, &Data); position = LocateElem(*LinkedList, Data); if (position != 0) ; else { ListAppend(LinkedList, Data); } } return OK; } void SetIntersect(List *LinkedList, List list) { ElemType data; int position = 0; for (int i = 1; i <= ListLength(*LinkedList);) { GetElem(*LinkedList, i, &data); position = LocateElem(list, data); if (position == 0) { ListDelete(LinkedList, i, &data); continue; } i++; } } void SetSubtract(List *LinkedList, List list) { ElemType data; int position = 0; for (int i = 1; i <= ListLength(*LinkedList);) { GetElem(*LinkedList, i, &data); position = LocateElem(list, data); if (position != 0) { ListDelete(LinkedList, i, &data); continue; } i++; } } int main() { List linkedlist, linkedlist_a, linkedlist_b; InitList(&linkedlist); InitList(&linkedlist_a); InitList(&linkedlist_b); ClearList(&linkedlist); CreateSet(&linkedlist); ListTraverse(linkedlist); printf("\n"); ElemType data = 100; ListAppend(&linkedlist, data); ListTraverse(linkedlist); printf("%d\n", ListLength(linkedlist)); ClearList(&linkedlist); ListTraverse(linkedlist); printf("%d\n", ListLength(linkedlist)); ListTraverse(linkedlist_a); DestroyList(&linkedlist); ListTraverse(linkedlist_a); printf("\n"); // SetIntersect(&linkedlist, linkedlist_a); // ListTraverse(linkedlist); system("pause"); return 0; }