爱华网实验1
复习结构体、链表内容；
目的
复习结构体、链表内容为后续实验奠定基础。 内容
建立链表、插入节点、删除节点、查询并显示节点内容。 方法
参考“C语言程序设计”相关内容。
相关代码：
（1） Header Files
#ifndef LINKEDLIST_H_INCLUDED
#define LINKEDLIST_H_INCLUDED
//线性表的单链表存储结构
struct LNode
{
ElemType data;
LNode *next;
};
typedef LNode *LinkList; // 另一种定义LinkList的方法
//单链表线性表的基本操作(12个)
int InitList(LinkList &L)
{
// 操作结果：构造一个空的线性表L
L=(LinkList)malloc(sizeof(LNode)); // 产生头结点,并使L指向此头结点
if(!L) // 存储分配失败
exit(0);
L->next=NULL; // 指针域为空
return 1;
}
void CreateList_L(LinkList &L, int n) // 算法2.11
{
// 逆位序输入（随机产生）n个元素的值，建立带表头结点的单链线性表L
LinkList p;
int i;
L = (LinkList)malloc(sizeof(LNode));
L->next = NULL; // 先建立一个带头结点的单链表
for (i=n; i>0; --i)
{
p = (LinkList)malloc(sizeof(LNode)); // 生成新结点
p->data = rand()%200; // 改为一个随机生成的数字(200以内)
p->next = L->next;
L->next = p; // 插入到表头
}
} // CreateList_L
int DestroyList(LinkList &L)
{
// 初始条件：线性表L已存在。操作结果：销毁线性表 LinkList q;
while(L)
{
q=L->next;
free(L);
L=q;
}
return 1;
}
int ClearList(LinkList L) // 不改变L L
{
// 初始条件：线性表L已存在。操作结果：将L重置为空表 LinkList p,q;
p=L->next; // p指向第一个结点
while(p) // 没到表尾
{
q=p->next;
free(p);
p=q;
}
L->next=NULL; // 头结点指针域为空
return 1;
}
int ListEmpty(LinkList L)
{
// 初始条件：线性表L已存在。操作结果：若
回TRUE，否则返回FALSE
if(L->next) // 非空
return 0;
else
return 1; L为空表，则返
}
int ListLength(LinkList L)
{
// 初始条件：线性表L已存在。操作结果：返回L中数据元素个数
int i=0;
LinkList p=L->next; // p指向第一个结点
while(p) // 没到表尾
{
i++;
p=p->next;
}
return i;
}
int GetElem(LinkList L,int i,ElemType &e) // 算法2.8
{
// L为带头结点的单链表的头指针。当第i个元素存在时,其值赋给e并返回1,否则返回-1
int j=1; // j为计数器
LinkList p=L->next; // p指向第一个结点
while(p&&j<i) // 顺指针向后查找,直到p指向第i个元素或p为空
{
p=p->next;
j++;
}
if(!p||j>i) // 第i个元素不存在
return -1;
e=p->data; // 取第i个元素
return 1;
}
int LocateElem(LinkList L,ElemType e,int(*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;
}
int PriorElem(LinkList L,ElemType cur_e,ElemType &pre_e) {
// 初始条件: 线性表L已存在
// 操作结果: 若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱,
// 返回1;否则操作失败,pre_e无定义,返回-1 LinkList q,p=L->next; // p指向第一个结点
while(p->next) // p所指结点有后继
{
q=p->next; // q为p的后继
if(q->data==cur_e)
{
pre_e=p->data;
return 1;
}
p=q; // p向后移
}
return -1;
}
int NextElem(LinkList L,ElemType cur_e,ElemType &next_e) {
// 初始条件：线性表L已存在
// 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，
// 返回1;否则操作失败，next_e无定义，返回-1 LinkList p=L->next; // p指向第一个结点
while(p->next) // p所指结点有后继
{
if(p->data==cur_e)
{
next_e=p->next->data;
return 1;
}
p=p->next;
}
return -1;
}
int 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 -1;
s=(LinkList)malloc(sizeof(LNode)); // 生成新结点 s->data=e; // 插入L中
s->next=p->next;
p->next=s;
return 1;
}
int 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 -1;
q=p->next; // 删除并释放结点
p->next=q->next;
e=q->data;
free(q);
return 1;
}
int ListTraverse(LinkList L,void(*vi)(ElemType))
// vi的形参类型为ElemType，与bo2-1.cpp中相应函数的形参类型ElemType&不同
{
// 初始条件：线性表L已存在
// 操作结果:依次对L的每个数据元素调用函数vi()。一旦vi()失败,则操作失败
LinkList p=L->next;
while(p)
{
vi(p->data);
p=p->next;
}
printf("n");
return 1;
}
LinkList ReverseList(LinkList phead)//实现链表的逆置
{
LinkList p,q,r; p=phead; q=r=NULL; while(p)
}
{ } return r; q=p->next; p->next=r; r=p; p=q;
#endif // LINKEDLIST_H_INCLUDED
(2) Source Files
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
#include "LinkedList.h"
int compare(ElemType c1,ElemType c2) {
if(c1==c2)
return 1;
else
return 0;
}
void visit(ElemType c)
{
printf("%d ",c);
}
void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc) {
// 已知单链线性表La和Lb的元素按值非递减排列。
// 归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列。
LinkList pa, pb, pc;
pa = La->next;
pb = Lb->next;
Lc = pc = La; // 用La的头结点作为Lc的头结点 while (pa && pb)
{
if (pa->data <= pb->data)
{
pc->next = pa;
pc = pa;
pa = pa->next;
}
else
{
pc->next = pb;
pc = pb;
pb = pb->next;
}
}
pc->next = pa ? pa : pb; // 插入剩余段
free(Lb); // 释放Lb的头结点 } // MergeList_L
int main()
{
LinkList L;
ElemType e,e0;
int i;
InitList(L);
for(i=1; i<=10; i++)
ListInsert(L,1,10-i);
//CreateList_L(L,10);
printf("在L的表尾依次插入10个数据后：L="); ListTraverse(L,visit);
GetElem(L,4,e);
printf("第4个元素的值为：%dn",e);
ListDelete(L,4,e); // 删除第4个数据
printf("删除第4个数据后：L=");
ListTraverse(L,visit);
DestroyList(L);
LinkList La, Lb, Lc;
int a[4] = {3,5,8,11};
int b[7] = {2,6,8,9,11,15,20};
InitList(La);
InitList(Lb);
for(i=1; i<=4; i++)
ListInsert(La, i, a[i-1]); for(i=1; i<=7; i++)
ListInsert(Lb, i, b[i-1]); printf("La=");
ListTraverse(La,visit); printf("Lb=");
ListTraverse(Lb,visit);
MergeList_L(La, Lb, Lc);
printf("Lc=");
ListTraverse(Lc,visit);
DestroyList(Lc); }
结果截图如下：
