《数据结构》(C语言版)——线性表的单链表存储结构

2018-01-27 10:27:11来源:网络收集作者:咖啡不加糖人点击

分享
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
//用到的库文件
#include //printf() ;scanf()
#include //exit()
#include //malloc()
#include //srand((unsigned)time(NULL)) ;
//函数结果状态代码
#define TRUE1
#define FALSE0
#define OK1
#define ERROR0
#define INFEASIBLE-1
#define OVERFLOW-2
//Status是函数的类型,其值是函数结果状态代码
typedef int Status ;
//#define ElemType int//也可以用宏定义确定ElemType类型
typedef int ElemType ;
//-----线性表的单链表存储结构-----
typedef structLNode {//自定义数据类型
ElemType data ;//数据域
struct LNode *next ;//指针域
} LNode, *LinkList ;
// 操作结果:构造一个空的线性表L。
Status InitList_L(LinkList &L) {
L = (LinkList)malloc(sizeof(LNode)) ;
if(!L) {//存储分配失败
printf("初始化失败") ;
exit(OVERFLOW) ;//exit(-1)程序异常退出
}
L->next = NULL ;// 先建立一个带头结点的单链表,并使头结点的指针域为NULL
return OK ;
}// InitList_L
// 初始条件:线性表L已存在。
// 操作结果:销毁线性表L。
Status DestroyList_L(LinkList &L) {
free(L) ;//释放线性表头结点指针域
return OK ;
}// DestroyList_L
// 初始条件:线性表L已存在。
// 操作结果:将L重置为空表。
Status ClearList_L(LinkList &L) {
LinkList p = L->next, ptmp ;//p指向线性表头结点
while(p) {//释放每个结点的指针域
ptmp = p->next ;
free(p) ;
p = ptmp ;
}
L->next = NULL ;//头结点指针域为空
return OK ;
}// ClearList_L
// 初始条件:线性表L已存在。
// 操作结果:若L为空表,返回TRUE,否则返回FALSE
Status ListEmpty_L(LinkList L) {
return L->next ? FALSE : TRUE ;
}// ListEmpty_L
// 初始条件:线性表L已存在。
// 操作结果:返回L中数据元素个数。
int ListLength_L(LinkList L) {
int nElem = 0 ;
LinkList p = L->next ;//p指向第一个结点
while(p) {
nElem ++ ;
p = p->next ;
}
return nElem ;
}// ListLength
// 初始条件:线性表L已存在,1≤i≤ListLength(L) 。
// 操作结果:用e返回L中第i个数据元素的值。
Status GetElem_L(LinkList L, int i, ElemType &e) {
LinkList p = L->next ;//初始化,p指向第一个结点
int j = 1 ;//j为计数器
while ( p && jp = p->next ;
++ j ;
}
if ( !p || j>i )
return ERROR ;//第i个元素不存在
e = p->data ;//取第i个元素
return OK ;
}// GetElem_L 算法2.8
// 初始条件:线性表L已存在,compare()是数据元素判定函数。
// 操作结果:返回L中第1个与e满足compare()的数据元素的位序,若这样的数据元素不存在,则返回值为0。
Status compare(ElemType listElem, ElemType e) {
return listElem == e ? TRUE : FALSE ;
}// Compare
int LocateElem_L(LinkList L, ElemType e, Status (*pfn_compare)(ElemType, ElemType)) {
int pos = 1 ;
LinkList p = L->next ;//p指向链表第1个元素
while(p && !(*pfn_compare)(p->data, e)) {
++ pos ;
p = p->next ;//指针后移p->next = NULL时 意味着找到表尾元素了
}
if(pos<=ListLength_L(L))//pos的值在线性表中,返回元素的位序
return pos ;
else
return 0 ;
}// LocateElem_L
// 初始条件:线性表L已存在。
// 操作结果:若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱,否则操作失败,pre_e无定义。
Status PriorElem_L(LinkList L, ElemType cur_e, ElemType &pre_e) {
int i = LocateElem_L(L, cur_e, compare) ;
if(i==0 || i==1) return ERROR ;
GetElem_L(L, i-1, pre_e) ;
return OK ;
}// PriorElem_L
// 初始条件:线性表L已存在。
// 操作结果:若cur_e是L的数据元素,且不是最后一个,则用next_e返回它的后继,否则操作失败,pre_e无定义。
Status NextElem_Sq(LinkList L, ElemType cur_e, ElemType &next_e) {
int i = LocateElem_L(L, cur_e, compare) ;
if(i==0 || i==ListLength_L(L)) return ERROR ;
GetElem_L(L, i+1, next_e) ;
return OK ;
}// NextElem_Sq
// 初始条件:线性表L已存在,1≤pos≤ListLength(L)+1。
// 操作结果:在L中第pos个位置之前插入新的元素e,L的长度加1。
Status ListInsert_L(LinkList &L, int pos, ElemType e) {
LinkList p = L ;//定义一个结构体指针变量p,指向线性表起始位置(头结点)L。
int j = 0 ;
while (p && jp = p->next ;//p非空,且j++j ;
}
if (!p || j>pos-1)//插入位置是否合法(第i个结点存在,插入的位置在表内)
return ERROR ;
LinkList s = (LinkList) malloc(sizeof(LNode)) ;// 生成新结点
s->data = e ;// 将插入的元素值赋给 新生成结点的数据域
s->next = p->next ;// 新生成结点的指针域 指向下一个结点 (即将结点i-1中指向第i个元素的指针域p->next,赋给新结点的指针域s->next)
p->next = s ;// 结点i-1的指针域 指向新生成的结点(即将指向新生成结点的指针s,赋给第i-1个元素的指针域p->next)
printf("插入的元素:%d, 插入的位置:%d/n", e, pos) ;
return OK ;
}// ListInsert_L 算法2.9
// 初始条件:线性表L已存在且非空,1≤pos≤ListLength(L)。
// 操作结果:删除L的第pos个数据元素,并用e返回其值,L的长度减1。
Status ListDelete_L(LinkList &L, int pos, ElemType &e) {
LinkList p = L ;//定义一个结构体指针变量p,指向线性表起始位置(头结点)L。
int j = 0 ;
while (p->next && jp = p->next ;
++j ;
}
if (!(p->next) || j>pos-1)// 删除位置是否合法(结点存在,删除的位置在表内)
return ERROR ;
LinkList q = p->next ;//使q指向i-1结点(将结点i-1中指向结点i的指针域,赋给指针变量q)
p->next = q->next ;//(将结点i中指向结点i+1的指针域,赋给结点i-1的指针域
e = q->data ;//要删除结点的数据域,赋给e
free(q) ;//释放指针变量q
printf("删除的元素:%d, 删除的位置:%d/n", e, pos) ;
return OK ;
}// ListDelete_L 算法2.10
// 初始条件:线性表L已存在。
// 操作结果:依次对L的每个数据元素调用函数visit()。一旦vistit()失败,刚操作失败。
Status visit(ElemType e) {
printf("%d ",e) ;
return OK ;
}
Status ListTraverse_L(LinkList L, Status (*pfn_visit)(ElemType)) {
LinkList p = L->next ;//指针重新指向头结点
if(!p){
printf("线性表未初始化。/n") ;
return ERROR ;
}
while(p) {
visit(p->data) ;
p = p->next ;
}
printf("/n") ;
return OK ;
}// ListTraverse
// 创建随机表,包含10个随机数(头插法)。
Status CreateList(LinkList &L) {
srand((unsigned)time(NULL)) ;
//生成链表
L = (LinkList)malloc(sizeof(LNode)) ;
if(!L) {//存储分配失败
printf("初始化失败") ;
exit(OVERFLOW) ;//exit(-1)程序异常退出
}
for (int i=0 ; i<10 ; i++) {// 生成新结点
LinkList p = (LinkList)malloc(sizeof(LNode)) ;
//scanf("%d", &p->data) ;//输入元素值 赋给新生成结点的数据域
p->data = rand()%100 ;
p->next = L->next ;//插入到表头
L->next = p ;
printf("%d ", p->data) ;// 查看是否插入了新的元素
}
return OK ;
}// 个人整合
// 逆位序输入(随机产生)n个元素的值,建立带表头结点的单链线性表L(头插法)。
void CreateList_L(LinkList &L, int n) {
srand((unsigned)time(NULL)) ;//初始化随机数种子
L = (LinkList)malloc(sizeof(LNode)) ;
L->next = NULL ;//先建立一个带头结点的单链表
for (int i=n ; i>0 ; --i) {
LinkList p = (LinkList)malloc(sizeof(LNode)) ;//生成新结点
//scanf("%d", &p->data) ;//输入元素值
//随机生成100以内的数字
p->data = rand()%100 ;//将生成的元素值赋给新生成结点的数据域
//插入到表头
p->next = L->next ;//使新结点的指针域指向表尾(将表尾结点的指针域赋给新结点的指针域)
L->next = p ;//上一个结点的指针域指向新生成的结点(将指向新结点的指针p赋给上一个结点的指针域)
}
}// CreateList_L 算法2.11
// 顺位序输入(随机产生)n个元素的值,建立带表头结点的单链线性表L(尾插法)。
void CreateListTail(LinkList &L, int n) {
srand((unsigned)time(NULL)) ;//初始化随机数种子
L = (LinkList)malloc(sizeof(LNode)) ;
L->next = NULL ;//先建立一个带头结点的单链表
for (int i=0 ; iLinkList p = (LinkList)malloc(sizeof(LNode)) ;
//scanf("%d", &p->data) ;//输入元素值
p->data = rand()%100 ;//随机生成100以内的数字,将生成的元素值赋给新生成结点的数据域
//插入到表尾
L->next = p ;//上一结点的指针域指向新生成的结点(将新生成结点的指针域赋给上一结点的指针的指针域)
p->next = NULL ;//将新结点的指针域置空
}
}
// 初始化菜单
void initMenu() {
printf("/n/t/t*****************************************/n") ;
printf("/n/t/t/t线性表的链式表示和实现/n") ;
printf("/n/t/t1.创建随机表/t/t2.构造空线性表/n/t/t3.销毁线性表/t/t4.清空线性表/n/t/t5.线性表是否为空/t6.线性表的长度") ;
printf("/n/t/t7.查找表中元素/t8.插入新元素/n/t/t9.删除某个元素/t 10.遍历线性表/n/t/t 11.回到主菜单/t/t0.退出") ;
}
// 回到主菜单
void mainMenu() {
printf("/n/t/t*****************************************/n") ;
printf("/n/t/t/t 欢迎回到主菜单/n") ;
printf("/n/t/t1.创建随机表/t/t2.构造空线性表/n/t/t3.销毁线性表/t/t4.清空线性表/n/t/t5.线性表是否为空/t6.线性表的长度") ;
printf("/n/t/t7.查找表中元素/t8.插入新元素/n/t/t9.删除某个元素/t 10.遍历线性表/n/t/t 11.回到主菜单/t/t0.退出") ;
}
int main() {
LinkList L ;
InitList_L(L) ;
initMenu() ;
int select = -1 ;
while(select != 0) {
printf("/n请选择你的操作:") ;
scanf("%d", &select) ;
switch(select) {
case 1://创建随机表
printf("请输入要创建的随机表元素个数:/n") ;
int nElem ;
scanf("%d", &nElem) ;
CreateList_L(L, nElem) ;
printf("创建随机链表:") ;
ListTraverse_L(L, visit) ;
break ;
case 2://构造空线性表
printf("构造一个空的线性表L。") ;
InitList_L(L) ;
ListTraverse_L(L, visit) ;
break ;
case 3://销毁线性表
if(!L) {//线性表L的头结点存在才能销毁
printf("销毁线性表L。/n") ;
DestroyList_L(L) ;
} elseprintf("线性表未初始化。/n") ;
break ;
case 4://清空线性表
printf("将L重置为空表。") ;
ClearList_L(L) ;
break ;
case 5://线性表是否为空
if (ListEmpty_L(L))
printf("该线性表为空./n") ;
else
printf("该线性表非空./n") ;
break ;
case 6: { //线性表的长度
int lLength = ListLength_L(L) ;
printf("线性表的长度为: %d /n", lLength) ;
}
break ;
case 7: { //查找表中元素
int nSearchOption = -1 ;
while(nSearchOption) {
printf("1.按位置查找/t2.按元素查找/t11.回到主菜单/t0.退出查找/n请选择你的操作:") ;
scanf("%d", &nSearchOption) ;
switch(nSearchOption) {
case 1: { //1.按位置查找
printf("请输入要查找的位置:") ;
int pos ;
ElemType e ;
scanf("%d",&pos) ;
if(GetElem_L(L, pos, e)) {
printf("第%d个元素的值为:%d ", pos, e) ;
ElemType pre_e, next_e ;
if(PriorElem_L(L, e, pre_e))
printf("前一个元素:%d ", pre_e) ;
else printf("前一个元素不存在 ") ;
if(NextElem_Sq(L, e, next_e))
printf("后一个元素:%d /n", next_e) ;
else printf("后一个元素不存在 /n") ;
} else printf("请输入正确的数字!!!/n") ;
}
break ;
case 2: { //2.按元素查找
printf("请输入要查找的元素:") ;
int pos ;
ElemType e ;
scanf("%d", &e) ;
// 这里假定随机数组中的元素互不重复
pos = LocateElem_L(L, e, compare) ;
if(pos)
printf("值为%d是表中的第%d个元素/n", e, pos) ;
else
printf("没有值为%d的元素/n", e) ;
}
break ;
case 11://11.回到主菜单
mainMenu() ;
break;
case 0://0.退出查找
break;
default:
printf("请输入正确的数字!!!/n");
break ;
}
}
}
break ;
case 8: { //插入新元素
ElemType e ;
int pos ;
int nInsertOption ;
nInsertOption = -1;
while(nInsertOption) {
printf("请输入要插入的元素位置和元素的值:") ;
scanf("%d %d", &pos, &e) ;
if(ListInsert_L(L, pos, e)) {
printf("插入完毕,现在线性表为:") ;
ListTraverse_L(L, visit) ;
} else printf("请输入正确的数字!!!/n") ;
printf("1.是0.否是否继续: ") ;
scanf("%d", &nInsertOption) ;
}
printf("/n") ;
}
break ;
case 9: { //删除某个元素
int nDeleteOption ;
nDeleteOption = -1 ;
while(nDeleteOption) {
printf("1.按位置查找/t2.按元素查找/t11.回到主菜单/t0.退出查找/n请选择你的操作:") ;
scanf("%d", &nDeleteOption) ;
switch(nDeleteOption) {
case 1: { //1.按位置删除
ElemType e ;
int pos ;
printf("请输入要删除的位置:") ;
scanf("%d", &pos) ;
if(ListDelete_L(L, pos, e)) {
printf("第%d个元素%d删除完毕,现在线性表为:/n", pos, e) ;
ListTraverse_L(L, visit) ;
} else printf("请输入正确的数字!!!/n") ;
}
break ;
case 2: { //2.按元素删除
printf("请输入要删除的元素:") ;
ElemType e ;
int pos ;
scanf("%d", &e) ;
// 这里假定随机数组中的元素互不重复
pos = LocateElem_L(L, e, compare) ;
if(pos) {
ListDelete_L(L, pos, e) ;
printf("第%d个元素%d删除完结,现在线性表为:/n", pos, e) ;
ListTraverse_L(L, visit) ;
} else
printf("没有值为%d的元素/n", e) ;
}
break ;
case 11://11.回到主菜单
mainMenu() ;
break;
case 0://0.退出查找
break;
default:
printf("请输入正确的数字!!!/n");
break ;
}
}
}
break ;
case 10://遍历线性表
printf("遍历线性表:") ;
ListTraverse_L(L, visit) ;
break ;
case 11://回到主菜单
mainMenu() ;
break ;
case 0://退出
break ;
default:
printf("请输入正确的数字!!!/n") ;
break ;
}
}
return 0 ;
}

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台