C语言数据结构-线性链表LinkList

waitwolf 2020-06-27

1. 头结点表示链表中第一个结点的存储位置

2. 最后一个结点的存储位置为空(NULL);

#ifndef __LINKLLIST_H__
#define __LINKLLIST_H__


#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLF -1
#define OVERFLOW -2

#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10

typedef int Status;

typedef int ElemType;

typedef struct LNode{
	ElemType data;
	struct LNode *next;
}LNode, *LinkList;

#endif

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


void CreateList_L(LinkList &L, int n) {
	L = (LinkList)malloc(sizeof(LNode));
	L -> next = NULL;

	for(ElemType i = n; i > 0; i --) {
		LinkList p = (LinkList)malloc(sizeof(LNode));
		p -> data = i;
		p -> next = L -> next;
		L -> next = p;
	}
}

Status GetElem_L(LinkList &L, int i, ElemType &e) {
	LNode *p = L -> next;
	ElemType j = 1;
	while(p && j < i) {
		p = p -> next;
		++j;
	}

	if(!p || j > i) {
		return ERROR;
	}

	e = p -> data;
	return OK;
}

void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc) {
	LNode *pa = La -> next;
	LNode *pb = Lb -> next;

	LinkList 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);
}


Status ListDelete_L(LinkList &L, int i, ElemType &e) {
	LinkList p = L;
	ElemType 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);
	return OK;
}

Status ListInsert_L(LinkList &L, int i, ElemType e) {
	LinkList p = L;
	ElemType j = 0;

	while(p && j < i - 1) {
		p = p -> next;
		++j;
	}

	if(!(p -> next) || j < i -1) {
		return ERROR;
	}

	LinkList s = (LinkList)malloc(sizeof(LNode));
	s -> data = e;
	s -> next = p -> next;
	p -> next = s;

	return OK;
}

Status pShow(LinkList &L) {
	if(L == NULL) {
		exit(OVERFLOW);
	}

	printf("========== LinkList ===========\n");

	ElemType i = 0;
	LNode *p;
	for(LNode *p = L -> next; p != NULL; p = p -> next) {
		printf("index %d, %d\n", i, p -> data);
		i++;
	}

	return OK;
}

int main() {

	ElemType e;

	LinkList L;
	CreateList_L(L, 5);

	LinkList A;
	CreateList_L(A, 5);
	pShow(L);

	GetElem_L(L, 1, e);
	printf("index 0, value = %d\n", e);


	LinkList Lc;
	MergeList_L(L, A, Lc);
	pShow(Lc);

	ListDelete_L(Lc, 5, e);
	pShow(Lc);

	ListInsert_L(Lc, 5, 10);
	pShow(Lc);
	return OK;
}

相关推荐