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

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

线性表ADT结构及相关函数

环境：Linux Ubuntu（云服务器）

工具：vim

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

list.h头文件

/*************************************************************************
	> File Name: list.h
	> Author: 
	> Mail: 
	> Created Time: Thu 05 Sep 2024 02:10:41 PM CST
 ************************************************************************/

#ifndef _LIST_H
#define _LIST_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 -3

typedef int Status;

#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10

typedef int ElemType;

typedef struct {
	ElemType *elem;
	int length;
	int listsize;
} List;

#define DATAFMT "%d"

Status InitList(List &L);

Status DestroyList(List &L);

Status ClearList(List &L);

Status ListEmpty(List L);

int ListLength(List L);

Status GetElem(List L, int i, ElemType &e);

int equal(ElemType a, ElemType b);

Status LocateElem(List L, ElemType e, int equal(ElemType, ElemType));

Status PriorElem(List L, ElemType cur_e, ElemType &pre_e);

Status NextElem(List L, ElemType cur_e, ElemType &next_e);

Status ListInsert(List &L, int i, ElemType e);

Status ListDelete(List &L, int i, ElemType &e);

Status visit(ElemType e);

Status ListTraverse(List L, Status visit(ElemType));

void InputList(List &L, int n);

void unionList(List &La, List Lb);

void MergeList(List La, List Lb, List &Lc);

#endif

list.c函数文件

/*************************************************************************
	> File Name: list.c
	> Author: 
	> Mail: 
	> Created Time: Thu 05 Sep 2024 02:16:38 PM CST
 ************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include "list.h"

Status InitList(List &L) {
	L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
	if(!L.elem) exit(OVERFLOW);
	
	L.length = 0;
	L.listsize = LIST_INIT_SIZE;
	
	return OK;
}//InitList

Status DestroyList(List &L) {
	free(L.elem);
	
	return OK;
}//DestroyList

Status ClearList(List &L) {
	for(int i = 0; i < L.listsize; i++) {
		L.elem[i] = 0;
	}
	
	L.length = 0;
	
	return OK;
}//ClearList

Status ListEmpty(List L) {
	return L.length == 0 ? TRUE : FALSE;
}//ListEmpty

int ListLength(List L) {
	return L.length;
}//ListLength

Status GetElem(List L, int i, ElemType &e) {
	if(i < 1 || i > ListLength(L)) {
		return ERROR;
	}

	e = L.elem[i-1];
	
	return OK;
}//GetElem

int equal(ElemType a, ElemType b) {
	return a == b ? TRUE : FALSE;
}//equal

Status LocateElem(List L, ElemType e, int equal(ElemType, ElemType)) {
	for(int i = 0; i < ListLength(L); i++) {
		if(equal(e, L.elem[i])) {
			return i + 1;
		}
	}

	return FALSE;
}//LocateElem

Status PriorElem(List L, ElemType cur_e, ElemType &pre_e) {
	if(L.elem[0] == cur_e) {
		return ERROR;
	}

	int i;
	for(i = 0; i < ListLength(L); i++) {
		if(L.elem[i] == cur_e) {
			break;
		}
	}
	if(i == ListLength(L)) {
		return NOEXIST;
	}

	pre_e = L.elem[i-1];
	
	return OK;
}//PriorElem

Status NextElem(List L, ElemType cur_e, ElemType &next_e) {
	if(L.elem[L.length-1] == cur_e) {
		return ERROR;
	}

	int i;
	for(i = 0; i < ListLength(L); i++) {
		if(L.elem[i] == cur_e) {
			break;
		}
	}
	if(i == ListLength(L)) {
		return NOEXIST;
	}

	next_e = L.elem[i+1];

	return OK;
}//NextElem

Status ListInsert(List &L, int i, ElemType e) {
	if(i < 1 || i > L.length + 1) {
		return ERROR;
	}
	if(L.length >= L.listsize) {
		ElemType *newbase = (ElemType *)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(ElemType));
		if(!newbase) exit(OVERFLOW);
		L.elem = newbase;
		L.listsize += LISTINCREMENT;
	}
	ElemType *q = &(L.elem[i-1]);
	for(ElemType *p = &(L.elem[L.length-1]); p >= q; --p) {
		*(p + 1) = *p;
	}
	*q = e;
	++L.length;
	return OK;
}//ListInsert

Status ListDelete(List &L, int i, ElemType &e) {
	if(i < 1 || i > L.length) {
		return ERROR;
	}
	ElemType *p = &(L.elem[i-1]);
	e = *p;
	ElemType *q = &(L.elem[L.length - 1]);
	for(++p; p <= q; ++p) {
		*(p - 1) = *p;
	}
	--L.length;
	return OK;
}//ListDelete

Status visit(ElemType e) {
	if(!e) return ERROR;
	printf(DATAFMT, e);
	printf(" ");
	return OK;
}//visit

Status ListTraverse(List L, Status visit(ElemType)) {
	printf("List traverse: ");
	for(int i = 0; i < L.length; i++) {
		if(!visit(L.elem[i])) {
			return FALSE;
		}
	}
	printf("\n");
	return OK;
}//ListTraverse

void InputList(List &L, int n) {
	if(n >= L.listsize) {
		ElemType *newbase = (ElemType *)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(ElemType));
		if(!newbase) exit(OVERFLOW);
		L.elem = newbase;
		L.listsize += LISTINCREMENT;
	}
	printf("Enter %d List Elem: ", n);
	for(int i = 0; i < n; i++) {
		scanf(DATAFMT, &L.elem[i]);
	}
	L.length = n;
}//InputList

void unionList(List &La, List Lb) {
	int La_len = ListLength(La);
	int Lb_len = ListLength(Lb);
	int i;
	ElemType e;
	for(i = 1; i <= Lb_len; i++) {
		GetElem(Lb, i, e);
		if(!LocateElem(La, e, equal)) {
			ListInsert(La, ++La_len, e);
		}
	}
}//unionList

void MergeList(List La, List Lb, List &Lc) {
	InitList(Lc);

	int i = 1, j = 1, k = 0;
	int La_len = ListLength(La);
	int Lb_len = ListLength(Lb);

	ElemType ai, bj;
	while((i <= La_len) && (j <= Lb_len)) {
		GetElem(La, i, ai);
		GetElem(Lb, j, bj);
		if(ai <= bj) {
			ListInsert(Lc, ++k, ai);
			++i;
		}
		else {
			ListInsert(Lc, ++k, bj);
			++j;
		}
	}
	while(i <= La_len) {
		GetElem(La, i++, ai);
		ListInsert(Lc, ++k, ai);
	}
	while(j <= Lb_len) {
		GetElem(Lb, j++, bj);
		ListInsert(Lc, ++k, bj);
	}
}//MergeList

main.c主文件

/*************************************************************************
	> File Name: main.c
	> Author: 
	> Mail: 
	> Created Time: Thu 05 Sep 2024 02:18:11 PM CST
 ************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include "list.h"
#include "list.c"

int main() {
	List L;
	//Initialize the list
	InitList(L);

	//Input the list and traverse it
	InputList(L, 10);
	ListTraverse(L, visit);

	//Determine whether the list is empty
	if(ListEmpty(L)) {
		printf("List is empty!\n\n");
	}
	else {
		printf("List is not empty!\n\n");
	}

	//Clear the list
	printf("Prepare clear the list...\n");
	if(ClearList(L)) {
		printf("List is clear!\n");
	}
	else {
		printf("List is not clear!\n");
	}
	//After clearing the list, check whether the list is empty
	if(ListEmpty(L)) {
		printf("List is empty!\n\n");
	}
	else {
		printf("List is not empty!\n\n");
	}

	//Input the list again
	InputList(L, 10);
	printf("\n");

	//Input the number of the element you want to get
	//Here is 3.
	int num1;
	printf("Enter the number of the element you want to get: ");
	scanf("%d", &num1);
	ElemType e1;
	GetElem(L, num1, e1);
	printf("No.%d Elem is ", num1);
	printf(DATAFMT, e1);
	printf(".\n\n");

	//Input the location of the element you want to get
	//Here is 99
	ElemType elem;
	printf("Enter the element you want to locate: ");
	scanf(DATAFMT, &elem);
	if(LocateElem(L, elem, equal)) {
		printf("The position of the element ");
		printf(DATAFMT, elem);
		printf(" is %d\n\n", LocateElem(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 element
	//Here is 5
	ElemType num2, e2;
	printf("Enter the element for which you want to get the priority element: ");
	scanf(DATAFMT, &num2);
	if(PriorElem(L, num2, e2)) {
		printf("The prior elem of ");
		printf(DATAFMT, num2);
		printf(" is ");
		printf(DATAFMT, e2);
		printf(".\n\n");
	}
	else if(PriorElem(L, num2, e2) == -3) {
		printf("The elem ");
		printf(DATAFMT, num2);
		printf(" dosen't exist!\n\n");
	}
	else {
		printf("The elem %d doesn't have prior elem.\n\n", num2);
	}

	//Input the element for which you want to get the next element
	//Here is 9
	ElemType num3, e3;
	printf("Enter the element for which you want to get the next element: ");
	scanf(DATAFMT, &num3);
	if(NextElem(L, num3, e3)) {
		printf("The next elem of ");
		printf(DATAFMT, num3);
		printf(" is ");
		printf(DATAFMT,  e3);
		printf(".\n\n");
	}
	else if(NextElem(L, num3, e3) == -3) {
		printf("The elem ");
		printf(DATAFMT, num3);
		printf(" dosen't exist!\n\n");
	}
	else {
		printf("The elem %d doesn't have next elem.\n\n", num3);
	}

	//Input the element and the location you want to insert
	//Here is 18 and 6
	int 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);
	printf("Insert elem %d to postion %d...\n", e4, num4);
	ListInsert(L, num4, e4);
	ListTraverse(L, visit);
	printf("\n");

	//Input the number of the element you want to delete
	//Here is 2
	int num5;
	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, num5, e5);
	printf("The delete elem is ");
	printf(DATAFMT, e5);
	printf(".\n");
	ListTraverse(L, visit);
	printf("\n");

	//Destroy the list
	printf("Prepare destroy the list...\n");
	if(DestroyList(L)) {
		printf("List is destroyed!\n");
	}
	else {
		printf("List is not destroyed!\n");
	}

    //Use unionList Methods
	List La1, Lb1;
	InitList(La1);
	InitList(Lb1);

	InputList(La1, 5);
	ListTraverse(La1, visit);
	InputList(Lb1, 5);
	ListTraverse(Lb1, visit);

	printf("\nUnion List La1 and Lb1...\n");
	unionList(La1, Lb1);
	ListTraverse(La1, visit);
	printf("\n");

	//Use MergeList Methods
	List La2, Lb2, Lc;
	InitList(La2);
	InitList(Lb2);

	InputList(La2, 5);
	ListTraverse(La2, visit);
	InputList(Lb2, 5);
	ListTraverse(Lb2, visit);

	printf("\nMerge List La2 and Lb2...\n");
	MergeList(La2, Lb2, Lc);
	ListTraverse(Lc, visit);

	return 0;
}