《数据结构 第1次上机作业 相关资料【HSH】2014-03-28 单链表, 补充》由会员分享，可在线阅读，更多相关《数据结构 第1次上机作业 相关资料【HSH】2014-03-28 单链表, 补充（6页珍藏版）》请在金锄头文库上搜索。
1、/*数据结构 第 1 次上机作业 【hsh, 2014-03-28】单链表单链表, 补充 */ / / 下面是一个单链表单链表操作实例，供大家参考。#include#include#include /* malloc()等 */#include /* INT_MAX 等 */#include /* EOF(=Z 或 F6),NULL */#include /* atoi() */#include /* eof() */ #include /* floor(),ceil(),abs() */#include /* exit() */* 函数结果状态代码 */#define TRUE 1#defi
2、ne FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define LIST_INIT_SIZE 100#define LISTINCREMENT 10/* #define OVERFLOW -2 因为在 math.h 中已定义 OVERFLOW 的值为 3,故去掉此行 */typedef int Status; /* Status 是函数的类型,其值是函数结果状态代码，如 OK 等 */typedef int Boolean; /* Boolean 是布尔类型,其值是 TRUE 或 FALSE */typedef int Ele
3、mType;/* c2-2.h 线性表的单链表存储结构 */struct LNode ElemType data; struct LNode *next;typedef struct LNode *LinkList; /* 另一种定义 LinkList 的方法 */void visit(ElemType c) /* ListTraverse()调用的函数(类型要一致) */printf(“%d “,c);Status equal(ElemType c1,ElemType c2) /* 判断是否相等的函数，Union()用到 */if(c1=c2)return TRUE;elsereturn F
4、ALSE;/构造一个空表Status InitList(LinkList *L) /* 操作结果：构造一个空的线性表 L */*L=(LinkList)malloc(sizeof(struct LNode); /* 产生头结点,并使 L 指向此头结点 */if(!*L) /* 存储分配失败 */exit(OVERFLOW);(*L)-next=NULL; /* 指针域为空 */return OK;/求表长int ListLength(LinkList L) /* 初始条件：线性表 L 已存在。操作结果：返回 L 中数据元素个数 */int i=0;LinkList p=L-next; /* p
5、 指向第一个结点 */while(p) /* 没到表尾 */i+;p=p-next;return i;/取元素Status GetElem(LinkList L,int i,ElemType *e) /* 算法 2.8 */ /* L 为带头结点的单链表的头指针。当第 i 个元素存在时,其值赋给 e 并返回 OK,否则返 回 ERROR */int j=1; /* j 为计数器 */LinkList p=L-next; /* p 指向第一个结点 */while(pj+;if(!p|ji) /* 第 i 个元素不存在 */return ERROR;*e=p-data; /* 取第 i 个元素 *
6、/return OK;/用函数判断是表 L 否有满足关系的元素int 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) /* 找到这样的数据元素
7、 */return i;p=p-next;return 0;/插入Status ListInsert(LinkList L,int i,ElemType e) /* 算法 2.9。不改变 L */ /* 在带头结点的单链线性表 L 中第 i 个位置之前插入元素 e */int j=0;LinkList p=L,s;while(pj+;if(!p|ji-1) /* i 小于 1 或者大于表长 */return ERROR;s=(LinkList)malloc(sizeof(struct LNode); /* 生成新结点 */s-data=e; /* 插入 L 中 */s-next=p-next;
8、p-next=s;return OK;/删除Status ListDelete(LinkList L,int i,ElemType *e) /* 算法 2.10。不改变 L */ /* 在带头结点的单链线性表 L 中，删除第 i 个元素,并由 e 返回其值 */int j=0;LinkList p=L,q;while(p-nextj+;if(!p-next|ji-1) /* 删除位置不合理 */return ERROR;q=p-next; /* 删除并释放结点 */p-next=q-next;*e=q-data;free(q);return OK;/遍历Status ListTraverse(
9、LinkList L,void(*vi)(ElemType)/* vi 的形参类型为 ElemType，与 bo2-1.c 中相应函数的形参类型 ElemTypewhile(p)vi(p-data);p=p-next;printf(“n“);return OK;/逆位序建立带表头结构的单链线性表 Lvoid CreateList(LinkList *L,int n) /* 算法 2.11 */ /* 逆位序(插在表头)输入 n 个元素的值，建立带表头结构的单链线性表 L */int i;LinkList p;*L=(LinkList)malloc(sizeof(struct LNode);(*
10、L)-next=NULL; /* 先建立一个带头结点的单链表 */printf(“请输入%d 个数据n“,n);for(i=n;i0;-i)p=(LinkList)malloc(sizeof(struct LNode); /* 生成新结点 */scanf(“%d“, /* 输入元素值 */p-next=(*L)-next; /* 插入到表头 */(*L)-next=p;/正位序建立带表头结构的单链线性表 Lvoid CreateList2(LinkList *L,int n) /* 正位序(插在表尾)输入 n 个元素的值，建立带表头结构的单链线性表 */int i;LinkList p,q;*
11、L=(LinkList)malloc(sizeof(struct LNode); /* 生成头结点 */(*L)-next=NULL;q=*L;/printf(“请输入%d 个数据n“,n);for(i=1;idata);q-next=p;q=q-next;p-next=NULL;int main() int z,y,x,n=5,L_len; LinkList La,Lb;/建表并赋值 printf(“1.输入n 请给单链表 a 的 5 个元素赋值（正位序）: “); CreateList2( /* 正位序输入 n 个元素的值 */ printf(“La=“); /* 输出链表 La 的内容
12、*/ ListTraverse(La,visit); printf(“请给单链表 b 的 5 个元素赋值（逆位序）: “); CreateList( /* 逆位序输入 n 个元素的值 */ printf(“Lb=“); /* 输出链表 Lb 的内容 */ ListTraverse(Lb,visit);printf(“n“);/插入 printf(“2.插入n 插入单链表 a 的第几个元素？“); scanf(“%d“, printf(“插入的元素值为:“); scanf(“%d“, ListInsert(La,y,x);printf(“La= “); /* 输出表 La 的内容 */ List
13、Traverse(La,visit); L_len=ListLength(La); printf(“此时表 a 长：%dn“,L_len);/输出此时表长 printf(“n“);/删除 printf(“3.删除n 删除单链表 a 的第几个元素？“);scanf(“%d“,ListDelete(La,y, printf(“删除的元素值为：%dn“,x);printf(“La= “); /* 输出表 La 的内容 */ ListTraverse(La,visit); L_len=ListLength(La); printf(“此时表 a 长：%dn“,L_len);/输出此时表长 printf(“n“);/查找 printf(“4.查找n 查找新单链表 a 的哪个元素？“); scanf(“%d“, y=LocateElem(La,z,equal); printf(“所查找元素的位序为%d“,y); printf(“nn“);return 0; /* 运行结果示例如下运行结果示例如下:*/
