数据结构实验答案

1 数据结构数据结构 实验大纲实验大纲 实验一实验一 顺序表的创建及插入 删除算法顺序表的创建及插入 删除算法 一 实验目的 一 实验目的 1 创建一个顺序表 并实现插入 删除算法 二 实验内容 二 实验内容 1 1 创建一个空的顺序表 L 2 依次插入 a b c d e 五个元素 3 在第 4 个元素位置上插入元素 f 4 删除 L 的第 3 个元素 5 输出顺序表 L include include define MaxSize 50 typedef char ElemType typedef struct ElemType elem MaxSize int length SqList SqList InitList SqList L L SqList malloc sizeof SqList L length 0 return L void DispList SqList L int i if L length 0 return for i 0 ilength i printf c L elem i printf n void ListInsert SqList L int i ElemType e int j if iL length 1 return i for j L length j i j L elem j L elem j 1 L elem i e L length void ListDelete SqList L int i int j if iL length return 2 i for j i jlength 1 j L elem j L elem j 1 L length main SqList L L InitList ListInsert L 1 a ListInsert L 2 b ListInsert L 3 c ListInsert L 4 d ListInsert L 5 e ListInsert L 4 f ListDelete L 3 printf 输出顺序表 L DispList L 实验二实验二 单链表的创建及插入 删除算法单链表的创建及插入 删除算法 一 实验目的 一 实验目的 1 创建一个单链表 并实现插入 删除算法 二 实验内容 二 实验内容 1 1 创建一个空的单链表 L 2 依次插入 a b c d e 五个元素 3 在第 4 个元素位置上插入元素 f 4 删除 L 的第 3 个元素 5 输出单链表 L 6 销毁单链表 L include include typedef char ElemType typedef struct LNode ElemType data struct LNode next LinkList LinkList InitList LinkList L L LinkList malloc sizeof LinkList L next NULL return L void DestroyList LinkList L LinkList p L q p next while q NULL free p 3 p q q p next free p void DispList LinkList L LinkList p L next while p NULL printf c p data p p next printf n void ListInsert LinkList L int i ElemType e int j 0 LinkList p L s while jnext if p NULL return else s LinkList malloc sizeof LinkList s data e s next p next p next s void ListDelete LinkList L int i int j 0 LinkList p L q while jnext if p NULL return else q p next p next q next free q 4 main LinkList L L InitList ListInsert L 1 a ListInsert L 2 b ListInsert L 3 c ListInsert L 4 d ListInsert L 5 e ListInsert L 4 f ListDelete L 3 printf 输出单链表 DispList L DestroyList L 实验三实验三 实现二叉树各种基本算法实现二叉树各种基本算法 一 实验目的 一 实验目的 1 实现二叉树各种基本算法 二 实验内容 二 实验内容 1 编写一个程序 利用递归算法求出二叉树 T 的深度 结点个数及叶子结点个数 提示 创建二叉树的二叉链表算法如下 设二叉树的字符串表示形式为 A B D E H J K L M N C F G I include include define MaxSize 100 typedef char ElemType typedef struct BiTNode ElemType data struct BiTNode lchild rchild BiTree BiTree CreateBiTree char str 由 str 字符串创建二叉树的二叉链表 char ch BiTree T BiTree stack MaxSize p NULL int top k j top 1 j 0 T NULL ch str j while ch 0 switch ch case top stack top p k 1 break 为左结点 case top break case k 2 break 为右结点 5 default p BiTree malloc sizeof BiTree p data ch p lchild p rchild NULL if T NULL T p else switch k case 1 stack top lchild p break case 2 stack top rchild p break j ch str j return T int BiTreeDepth BiTree T int lchild depth rchild depth if T NULL return 0 else lchild depth BiTreeDepth T lchild rchild depth BiTreeDepth T rchild if lchild depth rchild depth return lchild depth 1 else return rchild depth 1 int Nodes BiTree T int n1 n2 if T NULL return 0 else if T lchild NULL else n1 Nodes T lchild n2 Nodes T rchild return n1 n2 1 int LeafNodes BiTree T int n1 n2 if T NULL return 0 else if T lchild NULL else n1 LeafNodes T lchild n2 LeafNodes T rchild return n1 n2 main BiTree T T CreateBiTree A B D E H J K L M N C F G I printf 二叉树 T 的深度 d n BiTreeDepth T printf 二叉树 T 的结点个数 d n Nodes T printf 二叉树 T 的叶子结点个数 d n LeafNodes T 实验四实验四 二叉树的遍历二叉树的遍历 一 实验目的 一 实验目的 1 实现二叉树各种遍历算法 二 实验内容 二 实验内容 1 编写一个程序 实现二叉树的先序遍历 中序遍历 后序遍历以及层次遍历的算法 并 输出每种算法的遍历序列 提示 创建二叉树的二叉链表算法与实验三相同 设二叉树的字符串表示形式为 A B D E H J K L M N C F G I include include define MaxSize 100 typedef char TElemType typedef struct BiTNode TElemType data struct BiTNode lchild rchild BiTree BiTree CreateBiTree char str 由 str 字符串创建二叉树的二叉链表 char ch BiTree T BiTree stack MaxSize p NULL int top k j top 1 j 0 T NULL ch str j while ch 0 switch ch 7 case top stack top p k 1 break 为左结点 case top break case k 2 break 为右结点 default p BiTree malloc sizeof BiTree p data ch p lchild p rchild NULL if T NULL T p else switch k case 1 stack top lchild p break case 2 stack top rchild p break j ch str j return T void PreOrder BiTree T if T NULL printf c T data PreOrder T lchild PreOrder T rchild void InOrder BiTree T if T NULL InOrder T lchild printf c T data InOrder T rchild void PostOrder BiTree T if T NULL PostOrder T lchild 8 PostOrder T rchild printf c T data void LevelOrder BiTree T 层次遍历 BiTree q MaxSize int front rear front rear 0 if T NULL printf c T data rear q rear T while rear front front front 1 MaxSize T q front if T lchild NULL printf c T lchild data rear rear 1 MaxSize q rear T lchild if T rchild NULL printf c T rchild data rear rear 1 MaxSize q rear T rchild printf n main BiTree T T CreateBiTree A B D E H J K L M N C F G I printf 层次遍历序列 n LevelOrder T printf 先序遍历序列 n PreOrder T printf n printf 中序遍历序列 n InOrder T printf n printf 后序遍历序列 n 9 PostOrder T printf n 实验五实验五 图的遍历图的遍历 一 实验目的 一 实验目的 1 实现图的深度优先遍历和广度优先遍历算法 二 实验内容 二 实验内容 1 编写一个程序 实现图的深度优先遍历和广度优先遍历算法 并输出图 G 从顶点 1 开 始的深度优先遍历和广度优先遍历的遍历序列 include stdio h include malloc h define VNUM 20 typedef struct char vexs VNUM 1 int arcs VNUM VNUM int vexnum arcnum graph typedef struct node char data struct node next node queueptr typedef struct queueptr front queueptr rear linkqueue void CreatGraph graph g int i j k printf Please input the vertexes number and arcs number of Undigraph n printf vexnum scanf d printf arcnum scanf d 1 2 3 8 4 5 9 6 7 10 printf Please input The Name of all vertexes for i 0 ivexnum i printf nNO d vertex i 1 g vexs i getch printf c g vexs i g vexs i 0 for i 0 ivexnum i for j 0 jvexnum j g arcs i j 0 printf nPlease input the position of all exist arcs require Integer n printf Every arc input only once n printf vi vj for k 0 karcnum k scanf d d g arcs i 1 j 1 1 g arcs j 1 i 1 1 void InitQueue linkqueue q q front q rear queueptr malloc sizeof node q front next NULL void EnQueue linkqueue q int x graph g queueptr p p queueptr malloc sizeof node p data g vexs x p next NULL q rear next p q rear p int DeQueue linkqueue q graph g int k 0 u queueptr p p q front next while g vexs k p data k u k q front next p next if q rear p q rear q front free p return u int IsEmpty linkqueue q if q front q rear return 1 else return 0 11 int FirstAdjvex graph g int x int k for k 0 kvexnum k if g arcs x k return 1 int NextAdjvex graph g int x int y int k for k y 1 kvexnum k if g arcs x k return 1 void BFST graph g int u w int v int visited VNUM linkqueue q InitQueue for v 0 vvexnum v visited v 0 v 0 printf c g vexs v visited v 1 EnQueue while IsEmpty w FirstAdjvex g u while w 1 if visited w printf c g vexs w visited w 1 EnQueue w NextAdjvex g u w int visited VNUM void DFS graph g int v void DFST graph g int v for v 0 vvexnum v visited v 0 for v 0 vvexnum v if visited v DFS g v 12 void DFS graph g int v int w visited v 1 printf c g vexs v for w FirstAdjvex g v w 0 w NextAdjvex g v w if visited w DFS g w main graph g g graph malloc sizeof graph CreatGraph g printf DFS Traverse Graph n DFST g printf n printf BFS Traverse Graph n BFST g printf n 实验六实验六 实现折半查找算法实现折半查找算法 一 实验目的 一 实验目的 1 实现二分法查找 折半查找 的算法 二 实验内容 二 实验内容 1 输出在顺序表 1 2 3 4 5 6 7 8 9 10 中采用二分法查找 折半查找 关键字 9 的过程 include define N 10 int BinSearch int R int n int k int low 0 high n 1 mid count 0 while lowk high mid 1 else low mid 1 return 1 main int i k 9 int a N for i 0 i N i a i i 1 if i BinSearch a N k 1 13 printf 元素 d 的位置是 d n k i else printf 元素 d 不在表中 n k 实验