#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef int Status; //用作函数值类型,表示函数结果状态
typedef int ElemType;
typedef int KeyType; //关键字类型为整数类型
/*单链表默认是带头结点*/
typedef struct LNode {
ElemType data; //数据域
struct LNode *next; //指针域
}LNode, *LinkList;
/*函数接口*/
/*1.构建一个空的单链表L*/
Status InitList_L(LinkList &L);
/*2.销毁单链表L*/
Status DestroyList_L(LinkList &L);
/*3.将单链表L重置为空表*/
Status ClearList_L(LinkList &L);
/*4.单链表L为空表时返回TRUE,否则FALSE*/
Status ListEmpty_L(LinkList L);
/*5.求单链表L的表长*/
int ListLength_L(LinkList L);
/*6.查找。返回单链表L中第一个数据域值为e的结点地址,若不存在则返回NULL*/
LNode* Search_L(LinkList &L, ElemType e);
/*7.返回p结点的直接后继结点的指针,若p结点是尾元结点则返回NULL*/
LNode* NextElem_L(LNode *p);
/*8.构建元素e的结点,返回指向该结点的指针*/
LNode* MakeNode_L(ElemType e);
/*9.在p结点之后插入q结点*/
Status InsertAfter_L(LNode *p, LNode *q);
/*10.删除p结点的直接后继结点,用e返回结点值,若p空或指向尾元指针则操作失败*/
Status DeleteAfter_L(LNode *p, ElemType &e);
/*11.遍历单链表L*/
void ListTraverse_L(LinkList L, Status(*visit)(ElemType e));
/*12.建立一个长度为n的单链表,数组A[]提供n个元素值*/
Status CreatList_L(LinkList &L, int n, ElemType *A);
/*1.构建一个空的单链表L*/
Status InitList_L(LinkList &L) {
if (NULL == (L = (LNode*)malloc(sizeof(LNode)))) // 生成新结点
return OVERFLOW;
L->next = NULL;
return OK;
}
/*2.销毁单链表L*/
Status DestroyList_L(LinkList &L) {
LNode *p;
while (L) {
p = L->next;
free(L);
L = p;
}
return OK;
}
/*3.将单链表L重置为空表*/
Status ClearList_L(LinkList &L) {
LNode *p, *q;
p = L->next;
while (p) {
q = p->next;
free(p);
p = q;
}
L->next = NULL;
return OK;
}
/*4.单链表L为空表时返回TRUE,否则FALSE*/
Status ListEmpty_L(LinkList L){
if (NULL == L->next)
return TRUE;
else
return FALSE;
}
/*5.求单链表L的表长*/
int ListLength_L(LinkList L) {
LNode *p;
int count = 0;
p = L->next;
while (p) {
count++;
p = p->next;
}
return count;
}
/*6.查找。返回单链表L中第一个数据域值为e的结点地址,若不存在则返回NULL*/
LNode* Search_L(LinkList L, ElemType e) {
LNode *p;
if (NULL == L->next) //L是空表
return NULL;
p = L->next;
while (p != NULL && p->data != e) { //查找值为e的结点
p = p->next;
}
return p; //若p=NULL则返回NULL,否则p->data==e,查找成功
}
/*7.返回p结点的直接后继结点的指针,若p结点是尾元结点则返回NULL*/
LNode* NextElem_L(LNode *p) {
if (NULL == p->next)
return NULL;
return p->next;
}
/*8.构建元素e的结点,返回指向该结点的指针*/
LNode* MakeNode_L(ElemType e) {
LNode *p;
p = (LNode *)malloc(sizeof(LNode)); //分配结点空间
if (NULL != p) {
p->data = e;
p->next = NULL;
}
return p;
}
/*9.在p结点之后插入q结点*/
Status InsertAfter_L(LNode *p, LNode *q) {
if (NULL == p || NULL == q)
return ERROR; //参数不合理
q->next = p->next; //修改q的指针域
p->next = q; //修改p的指针域
return OK;
}
/*10.删除p结点的直接后继结点,用e返回结点值,若p空或指向尾元指针则操作失败*/
Status DeleteAfter_L(LNode *p, ElemType &e) {
LNode *q;
if (NULL == p || NULL == p->next)
return ERROR; //删除位置不合理
q = p->next;
p->next = q->next; //修改被删结点q的指针域
e = q->data;
free(q); //释放结点q
return OK;
}
/*11.遍历单链表L*/
void ListTraverse_L(LinkList L, Status(*visit)(ElemType e)) {
LNode *p;
ElemType e;
p = L;
while (NULL != p) {
e = p->data;
visit(e);
p = p->next;
}
}
/*12.建立一个长度为n的单链表,数组A[]提供n个元素值*/
Status CreatList_L(LinkList &L, int n, ElemType *A) {
LNode *p, *q;
int i;
if (OVERFLOW == InitList_L(L))
return OVERFLOW;
p = L;
for(i=0; i<n; i++){ //依次在表尾插入n个结点
q = MakeNode_L(A[i]);
InsertAfter_L(p, q); //令p指向新插入结点
p = q;
}
return OK;
}
单链表.cpp
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
- 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
推荐阅读更多精彩内容
- 最近在复习数据结构时,感触颇深。 推荐程序员们有时间都可以复习下, 数据结构不仅仅是一门课程, 它更能理清我们开发...