郝斌老师数据结构上课代码

第一部分 typedefine 的用法 include typedef struct Student int sid char name 100 char sex PSTU STU 等价于 STU 代表 struct Student PSTU 代表了 struct Student int main void STU st struct Studtn st PSTU ps struct Student ps ps sid 99 printf d n ps sid return 0 第二部分 链表部分的全部代码 include include include struct node int data struct node next 创建一个链表 返回 phead struct node creat list 函数返回类型为 struct node 类型 struct node phead NULL struct node ptail NULL struct node pnew NULL int i int len int val phead struct node malloc sizeof struct node if phead NULL printf 动态分配失败 n exit 1 phead next NULL ptail phead printf 请输入链表的长度 len n scanf d for i 0 idata val pnew next NULL ptail next pnew ptail pnew return phead 输出链表 void show list struct node phead struct node p p phead next while p NULL printf 5d p data p p next printf n 判断链表是否为空 bool is empty struct node phead if phead next NULL return true else return false 求链表的长度 int length list struct node phead int len 0 struct node p p phead next while p NULL len p p next return len 对链表进行排序 void sort list struct node phead int l int i j t struct node p q l length list phead for i 0 p phead next inext for j i 1 q p next jnext if p data q data t p data p data q data q data t 在链表中插入数据 void insert list struct node phead int pos int val int i struct node p phead next struct node pnew if p NULL printf 程序出错 n exit 1 for i 0 inext i 让 p 指向插入位置的前面一个节点 pnew struct node malloc sizeof struct node pnew data val pnew next p next p next pnew return 删除链表中某一位置的节点 void delete list struct node phead int pos int i struct node p phead next struct node q if p NULL printf 程序出错 n exit 1 for i 0 inext i q p next p next q next return 主函数 int main int l struct node phead 创建头结点 phead creat list 创建一个链表 头指针返回给 phead show list phead 输出刚才创建的链表 l length list phead 求链表的长度 printf len d n l 输出链表的长度 l sort list phead 对链表进行排序 show list phead 对排序完之后的链表进行输出 insert list phead 4 44 show list phead delete list phead 3 show list phead return 0 第三部分 栈的全部代码 include include include typedef struct Node int data struct Node pNext NODE PNODE typedef struct Stack PNODE pTop PNODE pBottom pBottem 是指向栈底下一个没有实际意义的元素 STACK PSTACK void init PSTACK void push PSTACK int void traverse PSTACK bool pop PSTACK int bool empty PSTACK pS int main void STACK S STACK 等价于 struct Stack int val init 目的是造出一个空栈 push 压栈 push push push push push push traverse 遍历输出 clear 清空数据 traverse 遍历输出 if pop else printf 出栈失败 traverse 遍历输出 return 0 void init PSTACK pS pS pTop PNODE malloc sizeof NODE if NULL pS pTop printf 动态内存分配失败 n exit 1 else pS pBottom pS pTop pS pTop NULL 或是 pS pBottom NULL void push PSTACK pS int val PNODE pNew PNODE malloc sizeof NODE pNew data val pNew pNext pS pTop pS Top 不能改为 pS pBottom pS pTop pNew return void traverse PSTACK pS PNODE p pS pTop while p pS pBottom printf d p data p p pNext printf n return bool empty PSTACK pS if pS pTop pS pBottom return true else return false 把 pS 所指向的栈出栈一次 并把出栈的元素存入 pVal 形参所指向的变量中 如果出栈失败 则返回 false 否则 true bool pop PSTACK pS int pVal if empty pS pS 本身存放的就是 S 的地址 return false else PNODE r pS pTop pVal r data pS pTop r pNext free r r NULL 为什么要把 r 赋给 NULL 呢 return true clear 清空 void clear PSTACK pS if empty pS return else PNODE p pS pTop PNODE q p pNext while p pS pBottom q p pNext free p p q pS pTop pS pBottom 第四部分 循环队列的代码 include include typedef struct Queue int pBase int front int rear QUEUE void init QUEUE bool en queue QUEUE int val 入队 void traverse queue QUEUE bool full queue QUEUE bool out queue QUEUE int 出队 bool empty queue QUEUE int main void QUEUE Q int val init en queue en queue en queue en queue en queue en queue en queue en queue en queue traverse queue if out queue else printf 出队失败 n traverse queue return 0 void init QUEUE pQ pQ pBase int malloc sizeof int 6 pQ front 0 pQ rear 0 bool full queue QUEUE pQ if pQ rear 1 6 pQ front return true else return false bool en queue QUEUE pQ int val if full queue pQ return false else pQ pBase pQ rear val pQ rear pQ rear 1 6 return true void traverse queue QUEUE pQ int i pQ front while i pQ rear printf d pQ pBase i i i 1 6 printf n return bool empty queue QUEUE pQ if pQ front pQ rear return true else return false bool out queue QUEUE pQ int pVal if empty queue pQ return false else pVal pQ pBase pQ front pQ front pQ front 1 6 return true 第五部分 递归 1 1 到 100 相加 include long sum int n 用递归实现 if 1 n return 1 else return sum n 1 n 用循环实现 long s 0 int i for i 1 i n i s i return s int main void printf d n sum 100 return 0 2 求阶乘 include 假定是 1 或大于 1 的值 long f long n if 1 n return 1 else return f n 1 n int main void printf d n f 3 return 0 3 汉诺塔 include void hannuota int n char A char B char C 如果是 1 个盘子 直接将 A 柱子上的盘子从 A 移动到 C 否则 先将 A 柱子上的 n 1 个盘子借助于 C 移动到 B 直接将 A 柱子上的盘子从 A 移到 C 最后将 B 柱子上的 n 1 借助 A 移动到 C if 1 n printf 将编号为 d 的盘子直接从 c 柱子 c 柱子 n n A C else hannuota n 1 A C B printf 将编号为 d 的盘子直接从 c 柱子 c 柱子 n n A C hannuo