//
// main.c
// 02-线性表(链式存储)
//
// Copyright © 2017年 Mr.Young. All rights reserved.
//
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW 0
typedef int Status;
typedef int Bool;
typedef int ElemType;
struct LNode { // 结点类型
ElemType data;
struct LNode *next;
};
typedef struct LNode *Link;
typedef struct LNode *Position;
typedef struct { // 链表类型
Link head, tail; // 分别指向线性链表中的头结点和最后一个结点
int len; // 指向线性链表中数据元素的个数
}LinkList;
/**
分配由p指向的值为e的结点，并返回OK，若分配失败，则返回ERROR
*/
Status MakeNode(Link *p, ElemType e) {
*p = (Link)malloc(sizeof(struct LNode));
if (!(p)) {
printf("内存分配失败!\n");
}
(*p)->data = e;
return OK;
}
/**
释放p所指结点
*/
void FreeNode(Link *p) {
free(*p);
p = NULL;
}
/**
构造一个空的线性链表
*/
Status InitList(LinkList *L) {
Link p = (Link)malloc(sizeof(Link)); // 创建头结点
if (!p) {
printf("头结点内存分配失败！\n");
return ERROR;
}
p->next = NULL;
L->head = L->tail = p;
L->len = 0;
return OK;
}
/**
将线性链表L置为空表，并释放原链表的结点空间
*/
Status ClearList(LinkList *L) {
Link p, q;
if (L->head != L->tail) { // 线性链表不为空表
p = q = L->head->next;
while (p!=L->tail) {
p=q->next;
free(q);
q = p;
}
free(q);
L->tail = L->head;
L->len = 0;
return OK;
}
printf("链表为空，清空失败！\n");
return ERROR;
}
/**
销毁线性链表L，L不再存在
*/
Status DestroyList(LinkList *L) {
ClearList(L);
FreeNode(&L->head);
return OK;
}
/**
已知h指向线性链表的头结点，将s所指结点插入在第一个结点之前
*/
Status InsFirst(LinkList *L, Link h, Link s) {
s->next = h->next;
h->next = s;
if (h == L->tail) // 表尾
L->tail = h->next;
L->len++; // 链表长度加1
return OK;
}
/**
已知h指向线性链表的头结点，删除链表中的第一个结点并以q返回
*/
Status DelFirst(LinkList *L, Link h, Link *q) {
*q = h->next;
if (*q != NULL) { // 链表不为空
h->next = (*q)->next;
// free(h->next);
if (!h->next) //删除的是尾结点
L->tail = h; // 修改尾指针
L->len--; // 链表长度减1
return OK;
}
printf("该链表为空!\n");
return ERROR;
}
/**
将指针s所指(彼此以指针相链)的一串结点链接在线性链表L的最后一个结点之后，并改变链表L的尾指针指向新的尾结点
*/
Status Append(LinkList *L, Link s) {
int i = 1;
L->tail->next = s;
while (s->next) {
s = s->next;
i++;
}
L->tail = s;
L->len += i;
return OK;
}
/**
删除线性链表L中的尾结点并以q返回，改变链表L的尾指针指向新的尾结点
*/
Status Remove(LinkList *L, Link *q) {
Link p = L->head;
if (L->len == 0) { // 空表
q = NULL;
printf("该链表为空!\n");
return ERROR;
}
while (p->next != L->tail) {
p = p->next;
}
*q = L->tail;
p->next = NULL;
L->tail = p; // 修改尾指针
L->len--;
return OK;
}
/**
已知p指向线性链表L中的一个结点，返回p所指结点的直接前驱的位置，若无前驱，则返回NULL
*/
Position PriorPos(LinkList L, Link p) {
Link q = L.head->next;
if (q == p) { // 第一个结点
printf("第一个结点没有前驱结点!\n");
return NULL;
} else {
while (q->next != p)
q = q->next;
return q;
}
}
/**
已知p指向线性链表L中的一个结点，将s所指结点插入在p所指结点之前，并修改指针p指向新插入的结点
*/
Status InsBefore(LinkList *L, Link *p, Link s) {
if ((*L).len == 0 || (*L).head == (*L).tail) {
printf("该链表为空!\n");
return ERROR;
}
Link prior_p = PriorPos(*L, *p); // 找出(*p)的前驱
if (!prior_p) // *q无前驱
prior_p = L->head;
s->next = *p;
prior_p->next = s;
*p = s;
L->len++;
return OK;
}
/**
已知p指向线性链表L中的一个结点，将s所指结点插入在p所指结点之后，并修改指针p指向新插入的结点
*/
Status InsAfter(LinkList *L, Link *p, Link s) {
if ((*L).len == 0 || (*L).head == (*L).tail) {
printf("该链表为空!\n");
return ERROR;
}
if (*p == L->tail) // 在尾指针后插入s
L->tail = s; // 修改尾指针
s->next = (*p)->next;
(*p)->next = s;
*p = s;
L->len++; // 链表长度加1
return OK;
}
/**
创建一个具有n个结点的链表
*/
Status CreateList(LinkList *L, int n) {
for (int i = 0; i < n; i++) {
// printf("请输入第%d个结点的数据\n", i+1);
// ElemType e = 0;
// scanf("%d", &e);
Link p;
MakeNode(&p, i+1);
InsFirst(L, L->tail, p);
}
return OK;
}
/**
已知p指向线性链表L中的一个结点，用e更新p所指结点中数据元素的值
*/
Status SetCurElem(Link *p, ElemType e) {
(*p)->data = e;
return OK;
}
/**
已知p指向线性链表中的一个结点，返回p所指结点中数据元素的值
*/
ElemType GetCurElem(Link p) {
return p->data;
}
/**
若线性链表L为空表，则返回TRUE，否则返回FALSE
*/
Bool ListEmpty(LinkList L) {
return L.len==0;
}
/**
返回线性链表L中元素的个数
*/
int ListLength(LinkList L) {
return L.len;
}
/**
返回线性链表L中头结点的位置
*/
Position GetHead(LinkList L) {
return L.head;
}
/**
返回线性链表L中最后一个结点的位置
*/
Position GetLast(LinkList L) {
return L.tail;
}
/**
已知p指向线性链表L中的一个结点，返回p所指结点的直接后继的位置，若无后继，则返回NULL
*/
Position NextPos(Link p) {
return p->next;
}
/**
返回p指示线性链表L中第i个结点的位置并返回OK，i值不合法时返回ERROR
*/
Status LocatePos(LinkList L, int i, Link *p) {
if (i<1 || i>L.len) {
printf("访问的位置不存在!\n");
return ERROR;
}
int cur = 1;
*p = L.head->next;
while (cur!=i) {
cur++;
*p=(*p)->next;
}
return OK;
}
Bool compare(ElemType e1, ElemType e2) {
return e1 == e2;
}
/**
返回线性链表L中第1个与e满足函数compare()判定关系的元素的位置，若不存在这样的元素，则返回NULL
*/
Position LocateElem(LinkList L,ElemType e, Status (* compare)(ElemType, ElemType)) {
Link p = L.head->next;
while (p && !compare(e, p->data)) { // 没到表尾 并且 没找到符合条件的元素
p = p->next;
}
return p;
}
void print(ElemType e) {
printf("%d\n", e);
}
/**
依次对L的每个元素调用函数visit()。一旦visit()失败，则操作失败。
*/
Status ListTraverse(LinkList L, void(*visit)(ElemType)) {
if (L.len==0)
printf("该链表为空!");
Link p = L.head->next; // p指向链表中第一个结点
for (int i = 1; i <= L.len; i++) {
visit(p->data);
p=p->next;
}
printf("\n");
return OK;
}
int main(int argc, const char * argv[]) {
LinkList list;
// 初始化一个链表
InitList(&list);
// 创建一个链表
CreateList(&list, 10);
Link p;
LocatePos(list, 5, &p);
printf("num 5 pos = %p\n", p);
p = LocateElem(list, 5, compare);
printf("data 5 pos = %p\n", p);
ListTraverse(list, print);
DestroyList(&list);
return 0;
}
网友评论