首页 > 代码库 > 单链表的实现
单链表的实现
学习编程也有一段时间了，但是总是感觉，自己缺少一些什么东西。编程一味的学习照着别人写的习惯，没有自己的思想，是不能有质的提升的。总是感觉自己不能做什么，对待代码还是缺少基本的实现的能力，更不用说什么技巧算法了。还需要的大量的联系。
我打算好好把数据结构的算法，实现以下，总是感觉自己，看起来会了，但是实际动手机就写不出来了。
自己只有不断的总结，把该记住的东西理解了，才能得心应手。。。。
公共的头文件：#include "common.h"
#include<string.h>#include<ctype.h>#include<malloc.h> /* malloc()等 */#include<limits.h> /* INT_MAX等 */#include<stdio.h> /* EOF(=^Z或F6),NULL */#include<stdlib.h> /* atoi() */#include<io.h> /* eof() */#include<math.h> /* floor(),ceil(),abs() */#include<process.h> /* exit() *//* 函数结果状态代码 */#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1 //infeasible/* #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行 */typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */
#include "SingleList.h"
#pragma once#include "common.h"typedef int ElemType;//线性表的单链表存储结构struct LNode{ ElemType data; LNode* next;};typedef struct LNode* LinkList;class SingleList{public: SingleList(); ~SingleList();public: //基本操作12个 Status InitList(LinkList*); Status DestroyList(LinkList*); Status ClearList(LinkList); Status ListEmpty(LinkList); Status ListLength(LinkList); Status GetElem(LinkList, int i, ElemType* e); Status LocateElem(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType)); Status PriorElem(LinkList L, ElemType cur_e, ElemType* pre_e); Status NextElem(LinkList L, ElemType cur_e,ElemType* next_e); Status ListInsert(LinkList L,int i,ElemType e); Status ListDelete(LinkList L,int i,ElemType* e); Status ListTraverse(LinkList L,void(*vi)(ElemType));};
"SingleList.cpp"
#include "SingleList.h"SingleList::SingleList(){}SingleList::~SingleList(){}Status SingleList::InitList(LinkList* L){ /*操作结果：构造一个空的线性表L*/ *L = (LinkList)malloc(sizeof(LNode)); //产生头结点，并使L指向次头结点 if (!*L) { exit(OVERFLOW); } (*L)->next = nullptr;//指针域空 return OK;}Status SingleList::DestroyList(LinkList*L){ /*初始条件：线性表L已经存在。操作结果：销毁线性表*/ LinkList q; while (*L) { q = (*L)->next; free(*L); *L = q; } return OK;}Status SingleList::ClearList(LinkList L) /*不改变L*/{ /*初始条件：线性表L已经存在。操作结果：将L置为空表*/ LinkList p, q; p = L->next;/*p指向第一个结点*/ while (p) { q = p->next; //先记录下一结点，然后释放当前结点 free(p); p = q; } L->next = nullptr; /*头结点指针域为空*/ return OK;}Status SingleList::ListEmpty(LinkList L){ if (L->next==nullptr) { return OK; } else { return ERROR; }}Status SingleList::ListLength(LinkList L){ int length=0; LinkList q=L->next; while (q) { length++; q = q->next; } return length;}Status SingleList::GetElem(LinkList L, int i, ElemType* e){ /* L为带头结点的单链表的头指针。当第i个元素存在时,其值赋给e并返回OK,否则返回ERROR */ LinkList q; q = L->next; int j = 1; /* j为计数器 */ while (q&&j<i) /* 顺指针向后查找,直到p指向第i个元素或p为空 */ { j++; q = q->next; } if (!q || j>i) /*第i个元素不存在*/ { return ERROR; } *e = q->data; /*取第i个元素*/ return OK;}int SingleList::LocateElem(LinkList L, ElemType e, Status(*compare)(ElemType, ElemType)){ /* 初始条件: 线性表L已存在,compare()是数据元素判定函数(满足为1,否则为0) */ /* 操作结果: 返回L中第1个与e满足关系compare()的数据元素的位序。 */ /* 若这样的数据元素不存在,则返回值为0 */ int i = 0; LinkList p = L->next; while (p) { i++; if (compare(p->data, e)) /* 找到这样的数据元素 */ return i; p = p->next; } return 0;}Status SingleList::PriorElem(LinkList L, ElemType cur_e, ElemType *pre_e){ /* 初始条件: 线性表L已存在 */ /* 操作结果: 若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱, */ /* 返回OK;否则操作失败,pre_e无定义,返回INFEASIBLE */ LinkList q, p = L->next; /* p指向第一个结点 */ while (p->next) /* p所指结点有后继 */ { q = p->next; /* q为p的后继 */ if (q->data =http://www.mamicode.com/= cur_e) { *pre_e = p->data; return OK; } p = q; /* p向后移 */ } return INFEASIBLE;}Status SingleList::NextElem(LinkList L, ElemType cur_e, ElemType *next_e){ /* 初始条件：线性表L已存在 */ /* 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继， */ /* 返回OK;否则操作失败，next_e无定义，返回INFEASIBLE */ LinkList p = L->next; /* p指向第一个结点 */ while (p->next) /* p所指结点有后继 */ { if (p->data =http://www.mamicode.com/= cur_e) { *next_e = p->next->data; return OK; } p = p->next; } return INFEASIBLE;}Status SingleList::ListInsert(LinkList L, int i, ElemType e) /* 算法2.9。不改变L */{ /* 在带头结点的单链线性表L中第i个位置之前插入元素e */ int j = 0; LinkList p = L, s; while (p&&j<i - 1) /* 寻找第i-1个结点 */ { p = p->next; j++; } if (!p || j>i - 1) /* i小于1或者大于表长 */ return ERROR; s = (LinkList)malloc(sizeof(struct LNode)); /* 生成新结点 */ s->data = http://www.mamicode.com/e; /* 插入L中 */ s->next = p->next; p->next = s; return OK;}Status SingleList::ListDelete(LinkList L, int i, ElemType *e) /* 算法2.10。不改变L */{ /* 在带头结点的单链线性表L中，删除第i个元素,并由e返回其值 */ int j = 0; LinkList p = L, q; while (p->next&&j<i - 1) /* 寻找第i个结点,并令p指向其前趋 */ { p = p->next; j++; } if (!p->next || j>i - 1) /* 删除位置不合理 */ return ERROR; q = p->next; /* 删除并释放结点 */ p->next = q->next; *e = q->data; free(q); return OK;}Status SingleList::ListTraverse(LinkList L, void(*vi)(ElemType))/* vi的形参类型为ElemType，与bo2-1.c中相应函数的形参类型ElemType&不同 */{ /* 初始条件：线性表L已存在 */ /* 操作结果:依次对L的每个数据元素调用函数vi()。一旦vi()失败,则操作失败 */ LinkList p = L->next; while (p) { vi(p->data); p = p->next; } printf("\n"); return OK;}
测试main()
#include "common.h"#include "SingleList.h"Status comp(ElemType c1, ElemType c2){ //数据元素判定函数（相等为True,否则为FALSE） if (c1 == c2) { return TRUE; } else return FALSE;}void visit(ElemType c){ printf("%d", c);}int main(){ LinkList L; ElemType e, e0; Status i; int k; SingleList s; i = s.InitList(&L); for (int j = 1; j <= 5;j++) { i = s.ListInsert(L, 1, j); } printf("在L的表头依次插入1~5后：L="); s.ListTraverse(L, visit); i = s.ListEmpty(L); printf("L是否空：i=%d(1:是 0：否)\n", i); for (int j = 1; j <= 10;j++) { s.ListInsert(L,j+5,j); } printf("在L的表尾依次插入1~10后：L="); s.ListTraverse(L,visit); s.GetElem(L,5,&e); printf("第5个元素的值为：%d\n", e); for (int j = 0; j <= 1; j++) { k = s.LocateElem(L, j, comp); if (k) printf("第%d个元素的值为%d\n", k, j); else printf("没有值为%d的元素\n", j); } for (int j = 1; j <= 2; j++) /* 测试头两个数据 */ { s.GetElem(L, j, &e0); /* 把第j个数据赋给e0 */ i = s.PriorElem(L, e0, &e); /* 求e0的前驱 */ if (i == INFEASIBLE) printf("元素%d无前驱\n", e0); else printf("元素%d的前驱为：%d\n", e0, e); } for (int j = s.ListLength(L) - 1; j <= s.ListLength(L); j++)/*最后两个数据 */ { s.GetElem(L, j, &e0); /* 把第j个数据赋给e0 */ i = s.NextElem(L, e0, &e); /* 求e0的后继 */ if (i == INFEASIBLE) printf("元素%d无后继\n", e0); else printf("元素%d的后继为：%d\n", e0, e); } k = s.ListLength(L); /* k为表长 */ for (int j = k + 1; j >= k; j--) { i = s.ListDelete(L, j, &e); /* 删除第j个数据 */ if (i == ERROR) printf("删除第%d个数据失败\n", j); else printf("删除的元素为：%d\n", e); } printf("依次输出L的元素："); s.ListTraverse(L, visit); s.DestroyList(&L); printf("销毁L后：L=%u\n", L); return 0;}
单链表的实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。