数据结构实验报告4

1 数据结构实验报告数据结构实验报告 实验实验 4 学号 学号 姓名 姓名 得分 得分 一 实验目的一 实验目的 1 复习线性表的逻辑结构 存储结构及基本操作 2 掌握顺序表和 带头结点 单链表 3 了解有序表 二 实验内容二 实验内容 1 必做题 假设有序表中数据元素类型是整型 请采用顺序表或 带头结点 单链表实现 1 OrderInsert struct LNode next LNode Link typedef struct LinkList Link head 头结点 int lenth 链表中数据元素的个数 LinkList int compare LinkList L int e 有序判定函数 compare int Lc 0 Link p p L head p p next while p NULL if e p date p p next Lc else return Lc return Lc void OrderInsert LinkList L int e int compare 根据有序判定函数 compare 在有序表 L 的适当位置 插入元素 e Link temp p q int Lc i temp Link malloc sizeof LNode temp date e p q L head 4 p p next Lc compare L e if Lc L lenth while q next NULL q q next q next temp temp next NULL else for i 0 inext q q next q next temp temp next p L lenth void OrderMerge LinkList La LinkList Lb int compare 根据有序判定函数 compare 将两个有序表 La 和 Lb 归并为一个有序表 int i Lc 0 Link temp p q q La head next while q NULL p Lb head temp Link malloc sizeof LNode temp date q date Lc compare Lb q date if Lc Lb lenth while p next NULL p p next p next temp temp next NULL 5 else for i 0 inext temp next p next p next temp q q next Lb lenth LinkList Initialize LinkList NewList int i Link temp NewList LinkList malloc 2 1 sizeof LinkList for i 0 idate 0 temp next NULL NewList i head temp NewList i lenth 0 return NewList void Insert LinkList NewList int a i char c printf 在第 1 个表中插入数据 输入 N 再对下个表插入数据 n for i 0 i 2 i while 1 scanf d c getchar if c N 6 if ihead next while p NULL printf d p date p p next void visit LinkList NewList void Show printf 有序表如下 n printf 第一个有序表为 n Show NewList 0 printf n printf 第二个有序表为 n Show NewList 1 printf n printf 归并后有序表为 n Show NewList 2 printf n int main LinkList NewList NULL LinkList L int i e 7 printf 请按要求输入数据 n NewList Initialize NewList Insert NewList for i 0 i 2 i OrderMerge NewList i NewList 2 compare visit NewList Show L NewList printf n 请输入将要插入的 e n scanf d OrderInsert NewList i e compare printf 对归并后有序表插入 e 后得 n Show NewList 2 return 0 2 include include typedef struct node int xi int zi struct node next Node Node Creat 用链表储存多项式的序数与指数 Node head p q int or in head Node malloc sizeof Node head next NULL q head printf 请输入多项式的序数与指数 n 注意 按照指数升序输入 系数不能等于 0 且指数不能小于 0 序数与指数用空格隔开 并以 0 0 结束输入 n scanf d d while or p Node malloc sizeof Node p xi or p zi in p next q next 8 q next p q p scanf d d return head void visit Node head 输出多项式 Node p head next while p printf dX d p xi p zi p p next printf NULL n n Node Add Node head1 Node head2 多项式相加 Node p head p1 p2 int sum head Node malloc sizeof Node p head p1 head1 next p2 head2 next while p1 if sum p1 xi sum p next p1 p p1 p1 p1 next p2 p2 next else 指数不相等分两种情况 if p1 zizi 9 p next p1 p p1 p1 p1 next else p next p2 p p2 p2 p2 next if p1 p next p1 将 1 中剩余结点接到和链表中 因为最终只剩下一段链表多项式 else p next p2 将 2 中剩余结点接到和链表中 这段链的链头接到目标链表就可以了 return head int main printf 请输入第一个多项式 n Node head p1 p2 p1 Creat printf 多项式为 n visit p1 printf 请输入第二个多项式 n p2 Creat pri