序号 数 据 结 构 实 验 报 告
班级 姓名 同组者 / 成绩 日期 3.9 指导教师
实验名称 实验一 线性表及其应用 一、实验目的 1、深刻理解线性表的逻辑特性及其顺序、链式存储方式的特点。 2、熟练掌握线性表的常用操作（建立、插入、删除、遍历等）在顺序、链式存储上的实现。 3、加深对C/C++等编程语言的相关知识点的理解 （如结构体、指针、函数、引用参数等）。
二、实验内容 1、根据给定的整型数组，以尾插法建立一个单链表，并实现以下操作： ① 查找：输入一个欲查找的整数，找到则显示第一个相匹配的整数在单链表中所处的位置，若不存在，则显示提示信息。 ② 删除：输入一个欲删除的整数e ，若存在则在单链表中删除第一个值为e 的元素。 ③ 插入：输入一个欲插入位置i 和欲插入元素e，将e 插入到第i 个整数之前（注意i 的合法性）。
A、算法思想 ① 创建 head 为头结点指针，初始时head->next 为NULL ；tail 始终指向当前链表的最后一个元素，其初始时指向头结点；p 始终指向每次申请的新结点，修改p->data 为当前读入的整数；修改tail->next 为p ，修改tail 为p ；最后修改tail->next 为NULL ，。 ② 插入 找到插入点的前驱（即第i-1 个结点）的指针p ；s 指向新申请的结点；修改s->data 为参数e，修改s->next 为p->next ， 修改p->next 为s 。 ③ 查找 …… 利用p进行遍历，直到节点的数据和所给的数据相同，输出节点的位置 ④ 删除 …… 利用p进行遍历，并总是将p的前一节点的指针赋给pre，一旦找到，则删除节点并退出循环，没有到话，反馈相关信息 B、算法源码
/* *线性表及其应用 */ #include using namespace std; typedef struct _LinkList { int elem; struct _LinkList* next; }LinkList;
void InitList(LinkList *&link );//构造一个含有头结点的链表 bool InsertList(LinkList *&link,int i,int e);//在第i个位置之前插入包含元素e的新节点 void GetTailPointer(LinkList *link,LinkList *&tail);//获得单链表尾结点指针 void AddList(LinkList *&link,int e);//根据将e以尾插法插入链表 void DisplayList(LinkList *link);//打印静态链表中的所有数据 void LocatedList(LinkList *link,int e);//查找e的位置 void DeleteList(LinkList *&link,int e);//删除所在节点 void MergeList(LinkList *linka,LinkList *linkb,LinkList *&linkc);//归并
void InitList(LinkList *&link )//构造一个含有头结点的链表 { LinkList *L,*head; head = (LinkList *)malloc(sizeof(LinkList));
head -> next = NULL; L = head; link = L;
}
void AddList(LinkList *&link,int e)//根据将e以尾插法插入链表 {
LinkList *p =NULL; p =(LinkList *)malloc(sizeof(LinkList)); p -> elem = e; p->next = NULL; LinkList *tail = link; while(tail->next) tail = tail -> next; tail ->next= p;
} void DeleteList(LinkList *&link,int e)//删除所在节点 { LinkList *p = link,*pre = NULL; while( p)//找到所在节点前的一节点 {
pre = p; p = p->next; if(p == NULL) { cout<<"无" } } void LocatedList(LinkList *link,int e)//查找e的位置 { LinkList *p = link; int i = 0;//位置 while(p != NULL&&p->elem != e) { p = p ->next; i++; } if(p == NULL) cout bool InsertList(LinkList *&link,int i,int e)//在第i个位置之前插入包含元素e的新节点 { LinkList * p = link,*s; int j=0; while(p&&j{ p = p->next; j++; } if(!p||j>i) return false; s = (LinkList *)malloc(sizeof(LinkList)); s->elem = e; s ->next = NULL; s -> next = p->next; p -> next = s; return true; } void DisplayList(LinkList *link)//打印静态链表中的所有数据 { int i = 0; LinkList *p = link ->next; //注意不要打印头结点的内容 while(p) { printf("%d\t",p -> elem); p = p -> next; } } int main() { int i = 0,j; int a[4] = {1,3,5,7},b[3] ={2,4,6}; j = sizeof(a)/sizeof(a[0]); LinkList *linka=NULL ,*linkb =NULL,*linkc =NULL; InitList(linka); InitList(linkb); InitList(linkc); while(i{ AddList(linka,a[i++]); } i = 0; while(i<3) { AddList(linkb,b[i++]); } //DisplayList(linka); //LocatedList(linka,1); //DeleteList(linka,4); DisplayList(linka); DisplayList(linkb); MergeList(linka,linkb,linkc); DisplayList(linkc); return 0; } C、测试数据和实际结果 ( 可截屏 ) ① 创建 序号 测试前 测试数据 实际结果 1 1,3,5,7 1,3,5,7 2 2,4,6 2,4,6 3 1 1 ② 插入 序号 测试前 测试数据(序号，插入值) 实际结果 1 1,3,5,7 0,9 9,1,3,5,7 2 同上 1,9 9,1,3,5,7 3 同上 2,9 1,9,3,5,7 4 同上 4,9 1,3,5,9,7 5 同上 5,9 1,3,5,7,9 6 同上 6,9 不合法 ③ 查找 …… 序号 测试前 测试数据(查找数据) 实际结果 1 1,3,5,7 1 第1处 2 同上 0 查找失败 3 1,3,3,7 3 第2处 ④ 删除 …… 序号 测试前 测试数据(删除数据) 实际结果 1 1,3,5,7 1 3，5,7 2 同上 2 1,3,5,7 3 1,3,3,7 3 1,3,7 2 、分别创建两个有序的顺序表（每个表的元素个数及每个元素的值在运行时由键盘输入），现将两个有序表合并，并保证新表依然为有序的顺序表。 A、算法思想 初始化链表linkc，用pa,pa,pc指向三个链表linka,linkb,和linkc。然后以linka&&linkb为条件遍历两个链表，比较两个节点中的数据大小，小的话将节点接在linkc链表的后面，将节点指针赋给pc,同时改变较小数据节点的指针指向下一节点。 当有一个链表遍历结束后，将另一个链表的指针赋给pc。 B、算法源码 void MergeList(LinkList *linka,LinkList *linkb,LinkList *&linkc)//归并 { LinkList *pa=NULL,*pb = NULL,*pc=NULL; pa=linka->next; pb = linkb -> next; pc = linkc;//linkc是一个含有头结点的空链表 while(pa&&pb) { if( pa->elem<= pb ->elem) { pc ->next= pa; pc = pa;