//判断单链表是否为空
Status DestroyList_L(LinkList &L) { LinkList p=L,q=p->next; while(q!=NULL) { free(p); p=q; q=p->next; } free(p); return OK; }// DestroyList_L
Status CreateList_L(LinkList &L,ElemType a[],int n) { LinkList s,r;int i; L=(LinkList )malloc(sizeof(LNode)); r=L; for(i=0;i<n;i++) { s=(LinkList )malloc(sizeof(LNode)); s->data=a[i]; r->next=s; r=s;
3. 概要设计
（1） 为了实现上述程序功能，需要定义一个简化的线性表抽象数据类型： ADT LinearList { 数据对象：D={ ai|ai∈IntegerSet,i=0,1,2,…,n,n≥0} 结构关系：R={<ai,ai+1>|ai,ai+1 ∈D} 基本操作： InitList_L(L) 操作前提：L 是一个未初始化的线性表 操作结果：将 L 初始化为一个空的线性表
（2） 基本操作的伪码算法 初始化 Bool InitLinkList(LinkList *L) { *L=申请新结点; 如果申请失败，返回失败标志； (*L)->next=NULL; 返回成功标志； } 建立单链表 Bool CrtLinkList(LinkList L) /* L 是已经初始化好的空链表的头指针，通过键盘输入元素值， 利用尾插法建单链表 L */ { rear=L; 打印输入提示：“请输入若干个正整数（用空格分隔） ，并用 -1 结束：” 读入一个数 x; 当 x 不是结束标志时，循环做如下处理： { 申请一个新结点 s； 如果申请失败，返回失败标志； 将 x 送到 s 的 data 域; rear->next=s; rear=s; 读入下一个数 x; } rear->next=NULL; 返回成功标志； } 显示单链表（输出） void DispLinkList(LinkList L) { p=首元素结点地址; while ( p 不空 ) { 打印结点 p 的元素值； p=下一个结点地址; } }
//销毁线性表
Status GetElem_L(LinkList L, int i, ElemType &e) { // L 为带头节点的单链表的头指针。 // 当第 i 个元素存在时，其值赋给 e 并返回 OK，否则返回 ERROR int j=0; LinkList p=L; while(j<i&&p!=NULL) { j++;p=p->next; } if(p==NULL) { return ERROR;
6. 使用说明 程序执行后，界面直接输出要求的结果 7. 测试结果
8. 附件 #include<stdio.h> #include<malloc.h> #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define NULL 0 typedef int Status; typedef int ElemType; typedef struct LNode { ElemType data; struct LNode *next; }LNode,*LinkList; Status InitList_L(LinkList &L) { //初始化线性表 L=(LinkList )malloc(sizeof(LNode)); //L 指向头节点，头节点数据域为空 L->next=NULL; return OK; }// InitList_L Status DispList_L(LinkList &L) { LinkList p=L->next; while(p!=NULL) { printf("%c",p->data); p=p->next; } return OK; } // DispList_L //输出线性表
( 3 ) 主函数的伪码 main() { 说明一个单链表 L ； 初始化 L ； 建立 L ； 显示 L ； }
4. 详细设计
采用单链表实现概要设计中定义的抽象数据类型，有关的数据类型和伪码算法定义 如下： （1） 类型定义 typedef int ElemType; typedef struct LNode { ElemType data; //数据域 struct LNode *next; //指针域 } LNode,* LinkList;
ቤተ መጻሕፍቲ ባይዱ
return ERROR; } else { q=p->next; //q 为要删除的元素节点 if(q==NULL) { return ERROR; } e=q->data; //e 为删除节点的数据区域 p->next=q->next; free(q); return OK; } }// ListDelete_L int LocateElem_L(LinkList L, ElemType e) { LinkList p=L->next; int i=1; while(p!=NULL&&p->data!=e) { p=p->next;i++; } //如果要插入的节点为头节点，则退出 if(p==NULL) { return ERROR; } else { return(i); } }// LocateElem_L //按元素值查找元素
《数据结构》上机报告
_2011_年_ 3 _月_ 9 _日 姓名__ ___ 学号_ _ 同组成员 __ _无_ __
1. 实验题目及要求
编写一个程序，实现单链表的各种基本运算
2. 需求分析
建立一个单链表，实现单链表的初始化，插入、删除节点等功能，以及确定某一元素在 单链表中的位置。 （1） （2） （3） （4） （5） （6） （7） （8） （9） （10） （11） （12） 初始化单链表； 依次采用尾插入法插入 a,b,c,d,e 元素； 输出单链表 L； 输出单链表 L 的长度； 判断单链表 L 是否为空； 输出单链表 L 的第三个元素； 输出元素 a 的位置； 在第 4 个元素位置上插入 f 元素； 输出单链表 L； 删除 L 的第 3 个元素； 输出单链表 L； 释放单链表。
{
} 删除操作 bool DelLinkList(LinkList L, int pos, ElemType *e) /* 在带头结点的单链表 L 中删除第 pos 个元素，并将删除的元素保存到变量*e 中 */ 查找待删除结点 i 的前驱结点，并用 pre 指向它; if (查找失败) { 显示参数错误信息; return ERROR; } else { r=pre->next; 修改指针，删除结点 r ; 释放被删除的结点所占的内存空间; return OK; } } 查找操作 int LocLinkList(LinkList L, ElemType e) / * 在带头结点的单链表 L 中查找其结点值等于 e 的结点， 若找到则返回该结点的序号位置 k，否则返回 -1 * / { p=首元素结点地址;
判断链表是否为空函数 ListEmpty_L() 取值函数 GetElem_L() 各函数间调用关系如下： InitList DispList CreateList ListLength ListEmpty main DestroyList GetElem ListInsert ListDelete LocateElem
} else { e=p->data; return OK; } }// GetElem_L Status ListInsert_L(LinkList &L, int i, ElemType e) { //插入数据元素 int j=0; LinkList p=L,s; /* 找到插入节点的上一个元素，如果是头节点则退出，当 i=1 时表示头节点， i=2 时，表示第一个元素 */ while(j<i-1&&p!=NULL) { j++; p=p->next; } if(p==NULL) { return ERROR; } else { s=(LinkList )malloc(sizeof(LNode)); s->data=e; s->next=p->next; p->next=s; return OK; } }// ListInsret_L Status ListDelete_L(LinkList &L, int i, ElemType &e) { //删除数据元素 int j=0; LinkList p=L,q; while(j<i-1&&p!=NULL) //查找删除元素的前一个节点 { j++; p=p->next; } if(p==NULL) {
CreateList_L(L) 操作前提：L 是一个已初始化的空表 操作结果：建立一个非空的线性表 L ListInsert_L(L,pos,e) 操作前提：线性表 L 已存在 操作结果：将元素 e 插入到线性表 L 的 pos 位置 ListDelete_L(L,pos,e) 操作前提：线性表 L 已存在 操作结果：将线性表 L 中 pos 位置的元素删除， 删除的元素值通过 e 返回 LocateList_L(L,e) 操作前提：线性表 L 已存在 操作结果：在线性表 L 中查找元素 e， 若存在，返回元素在表中的序号位置； 若不存在，返回-1 DestroyList_L(&L) 初始条件：线性表 L 已存在 操作结果：销毁线性表 ListEmpty_L(L) 初始条件：线性表已存在 操作结果：若 L 为空表，则返回 ERROR，否则返回 FALSE ListLength_L(L) 初始条件：线性表 L 已存在 操作结果：返回 L 中数据元素个数 GetElem_L(L,I,&e) 初始条件：线性表 L 已存在 操作结果：用 e 返回 L 中第 i 个数据元素值 } （2） 本程序包含 10 个函数： 主函数 main() 初始化单链表函数 InitList_L() 显示单链表内容函数 DispList_L() 插入元素函数 ListInsert_L() 删除元素函数 ListDelete_L() 查找元素函数 LocateList_L() 创建链表函数 CreateList_L() 链表元素长度函数 ListLength_L()
插入操作 bool InsLinkList(LinkList L, int pos, ElemType e) /*在带头结点的单链表 L 中第 pos 个位置插入值为 e 的新结点 s*/ 从“头”开始，查找第 i-1 个结点 pre ; if (查找失败) { 显示参数错误信息; return ERROR; } else { 申请一个新的结点 s ; 将 e 放入 s 的数据域; 将 s 插到 pre 后面; return OK; }
{
while ( p 不空 ) if (p->data!=e) { p=p->next; else break; return -1; k; k++; }
if ( p 不空 ) else } return
5. 调试分析
开始运行时会出现 Debug Error，DAMAGE: After Normal block， 搜索后了解到 是内存越界操作，检查后发现内存分配 L 和 S=(LinkList)malloc(sizeof(LNode))写成 了=(LinkList)malloc(sizeof(LinkList))，修改后正常。
//尾插法建表
} r->next=NULL; return OK; }// CreateList_L Status ListLength_L(LinkList L) { LinkList p=L;int n=0; while(p->next!=NULL) { n++; p=p->next; } return(n); }// ListLength_L Status ListEmpty_L(LinkList L) { return(L->next==NULL); }// ListEmpty_L //求线性表的长度
