devbox
小惠珠哦
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

c语言数据结构课程设计_关于计算器数据结构课程设计

作者：小惠珠哦 | 2024-07-27 16:57:06

赞

踩

关于计算器数据结构课程设计

  正文

一．概述

1.本次数据结构所做5个题目：

 11.2.1一元稀疏多项式计算器

 11.2.5模拟浏览器操作系统  

 11.2.10图的基本操作与实现

  11.2.18八皇后问题

   11.2.21木棒加工问题

2.使用语言：

C语言

3.编译环境：

Dev-C++；Microsoft Visual C++ 6.0

二．课程设计题目

1.一元稀疏多项式计算器

1.1问题描述

    设计一个一元稀疏多项式简单计算器。

1.2需求分析
  1.  输入并建立多项式。
  2. 输出多项式,输出形式为整数序列:n.c1.e1,c2,e2,....cn,en,其中    n是多项式的项数,ci,ei,分别是第i项的系数和指数,序列按指数降序排序。

         (4)实现多项式 a和 b 相加,建立多项式 a+b。

         (5)实现多项式 a和 b相减,建立多项式 a—b。

         (6)计算多项式在×处的值。

         (7)计算器的仿真界面

1.3算法的设计与实现

1.3.1设计思路
1. 输入并建立多项式：
   - 用户输入多项式的项数n。
   - 循环n次，每次输入一个项的系数ci和指数ei。
   - 将所有输入的项保存在一个列表中。
2. 输出多项式：
   - 对保存的多项式进行按指数降序排序。
   - 遍历排序后的多项式列表，依次输出每个项的系数和指数。
3. 多项式相加：
   - 用户输入两个多项式a和b。
   - 创建一个空的结果多项式c。
   - 遍历a和b的项，将对应指数相同的项的系数相加，并将结果添加到c中。
   - 如果某个多项式的项已经遍历完，将另一个多项式剩余的项直接添加到c中。
4. 多项式相减：
   - 用户输入两个多项式a和b。
   - 创建一个空的结果多项式c。
   - 遍历a和b的项，将对应指数相同的项的系数相减，并将结果添加到c中。
   - 如果某个多项式的项已经遍历完，将另一个多项式剩余的项取相反数后直接添加到c中。
5. 计算多项式在×处的值：
   - 用户输入一个值x。
   - 遍历多项式的每个项，将每个项的系数乘以x的指数次幂，并累加得到结果。
6. 计算器的仿真界面：
   - 可以使用图形用户界面(GUI)库来实现计算器的界面。
   - 在界面上提供输入框和按钮，用于输入多项式、操作符和值。
   - 根据用户的选择，调用相应的函数进行计算，并在界面上显示结果。

 1.3.2主要函数说明与源程序代码

主要函数：

dnode *creat()            //用链表存放多项式

void swap(dnode *p,dnode *q)            /*交换p，q指针所指的指数和系数*/

void sort(dnode *h)                        /*采用冒泡法对链表每一项重新排序*/

dnode *operate(dnode *a,dnode *b)        /*稀疏多项式计算*/

void prn(dnode *h)//打印结果

float qiuzhi(int x,dnode *h)  //求多项式在x处的值

 源代码：

  1.  
  2. #include<stdio.h>
  3.  
  4. #include<stdlib.h>
  5.  
  6. #include<malloc.h>
  7.  
  8. #define NULL 0
  9.  
  10. typedef struct node        /*定义多项式每一项*/
  11.  
  12. {
  13.  
  14. int e;                //e为指数
  15.  
  16. float c;            //c为系数
  17.  
  18. struct node *next;    //next指向下一项
  19.  
  20. }dnode;
  21.  
  22. dnode *creat()            /*用链表存放多项式*/
  23.  
  24. {                        //多项式的创建, 即输入两个多项式
  25.  
  26. dnode *h,*p;
  27.  
  28. int e,i,n;            //n为多项式的项数
  29.  
  30. float c;            //c为多项式的系数
  31.  
  32. h=(dnode *)malloc(sizeof(dnode));            //分配头节点
  33.  
  34. h->next=NULL;
  35.  
  36. do                  //当n为0或小于1时，则重新输入
  37.  
  38. {
  39.  
  40. printf("请输入多项式的项数n:");
  41.  
  42. scanf("%d",&n);
  43.  
  44. }while(n<1);
  45.  
  46. for(i=1;i<=n;i++)    //输入各项的系数c和指数e
  47.  
  48. {
  49.  
  50. printf("请输入第%d项的系数c和指数e:",i);
  51.  
  52. scanf("%f%d",&c,&e);
  53.  
  54. p=(dnode *)malloc(sizeof(dnode));        //创建新结点
  55.  
  56. p->c=c;p->e=e;    //将值传给data域
  57.  
  58. p->next=h->next;//用头插法建立链表
  59.  
  60. h->next=p;
  61.  
  62. }
  63.  
  64. return h;            //返回头结点
  65.  
  66. }
  67.  
  68. void swap(dnode *p,dnode *q)            /*交换p，q指针所指的指数和系数*/
  69.  
  70. {
  71.  
  72. float m; //中间变量
  73.  
  74. int n;    //中间变量
  75.  
  76. n=p->e;  //交换操作
  77.  
  78. p->e=q->e;
  79.  
  80. q->e=n;
  81.  
  82. m=p->c;
  83.  
  84. p->c=q->c;
  85.  
  86. q->c=m;
  87.  
  88. }
  89.  
  90. void sort(dnode *h)                        /*采用冒泡法对链表每一项重新排序*/
  91.  
  92. {
  93.  
  94. dnode *pi,*pl,*p,*q;
  95.  
  96. p=h->next;            //p此时指向第一项
  97.  
  98. while(p->next!=NULL)
  99.  
  100. p=p->next;        //寻找尾结点
  101.  
  102. pi=p;              //pi指向最后一次交换的位置，初值为表尾
  103.  
  104. while(pi!=h->next)    //结点数大于1时
  105.  
  106. {
  107.  
  108. pl=h->next;        //为中间变量，起传递地地址的作用
  109.  
  110. for(p=h->next;p!=pi;p=p->next)
  111.  
  112. {
  113.  
  114. q=p->next;
  115.  
  116. if(p->e>q->e)
  117.  
  118. {
  119.  
  120. swap(p,q);  //调用交换函数
  121.  
  122. pl=p;
  123.  
  124. }
  125.  
  126. }
  127.  
  128. pi=pl;            //pi指向前一个结点
  129.  
  130. }
  131.  
  132. }
  133.  
  134. dnode *operate(dnode *a,dnode *b)        /*稀疏多项式计算*/
  135.  
  136. {
  137.  
  138. int sel;
  139.  
  140. float x;
  141.  
  142. dnode *p1,*p2,*p,*t;    //t为结果链表的表头
  143.  
  144. t=(dnode *)malloc(sizeof(dnode));
  145.  
  146. t->next=NULL;
  147.  
  148. printf("--------------------------------------\n");
  149.  
  150. printf("|            请选择运算方式:        |\n");
  151.  
  152. printf("|            1、多项式相加          |\n");
  153.  
  154. printf("|            2、多项式相减          |\n");
  155.  
  156. printf("|            0、退出!                |\n");
  157.  
  158. printf("--------------------------------------\n");
  159.  
  160. printf("请选择:");
  161.  
  162. scanf("%d",&sel);
  163.  
  164. p1=a->next;
  165.  
  166. p2=b->next;
  167.  
  168. while(p1&&p2)
  169.  
  170. {   
  171.  
  172. if(p1->e==p2->e)        //指数相同
  173.  
  174. {
  175.  
  176. if(sel==1)
  177.  
  178. x=p1->c+p2->c;    //系数相加   
  179.  
  180. else
  181.  
  182. x=p1->c-p2->c;    //系数相减
  183.  
  184. if(x!=0)
  185.  
  186. {
  187.  
  188. p=(dnode *)malloc(sizeof(dnode));
  189.  
  190. p->e=p1->e;
  191.  
  192. p->c=x;
  193.  
  194. p->next=t->next;//利用头插法将p结点插入t中
  195.  
  196. t->next=p;
  197.  
  198. }
  199.  
  200. p1=p1->next;
  201.  
  202. p2=p2->next;
  203.  
  204. }
  205.  
  206. else if(p1->e>p2->e)    //p1的指数大于p2的指数
  207.  
  208. {   
  209.  
  210. p=(dnode *)malloc(sizeof(dnode));
  211.  
  212. p->e=p2->e;
  213.  
  214. if(sel==1)
  215.  
  216. p->c=p2->c;
  217.  
  218. else
  219.  
  220. p->c=(-1)*p2->c;
  221.  
  222. p->next=t->next;
  223.  
  224. t->next=p;
  225.  
  226. p2=p2->next;
  227.  
  228. }
  229.  
  230. else                    //p1的指数小于p2的指数
  231.  
  232. {   
  233.  
  234. p=(dnode *)malloc(sizeof(dnode));
  235.  
  236. p->e=p1->e;
  237.  
  238. p->c=p1->c;
  239.  
  240. p->next=t->next;
  241.  
  242. t->next=p;
  243.  
  244. p1=p1->next;
  245.  
  246. }
  247.  
  248. }
  249.  
  250. while(p1!=NULL)                //p2为空，p1不为空时
  251.  
  252. {   
  253.  
  254. p=(dnode *)malloc(sizeof(dnode));
  255.  
  256. p=p1;
  257.  
  258. p1=p1->next;
  259.  
  260. p->next=t->next;        //把p1 放在结果链表后面
  261.  
  262. t->next=p;
  263.  
  264. }
  265.  
  266. while(p2!=NULL)                //p1为空，p2不为空时
  267.  
  268. {
  269.  
  270. p=(dnode *)malloc(sizeof(dnode));
  271.  
  272. p->e=p2->e;
  273.  
  274. if(sel==2)                //如果选择的是2，则将p2中剩余的项的系数取其相反数
  275.  
  276. p->c=(-1)*p2->c;
  277.  
  278. else
  279.  
  280. p->c=p2->c;
  281.  
  282. p2=p2->next;
  283.  
  284. p->next=t->next;        //把p1 放在结果链表后面
  285.  
  286. t->next=p;
  287.  
  288. }
  289.  
  290. return t;                    //返回运算后的多项式的头结点
  291.  
  292. }
  293.  
  294. void prn(dnode *h)//打印结果
  295.  
  296. {
  297.  
  298. dnode *p;
  299.  
  300. p=h->next;
  301.  
  302. if(p==NULL)  //如果多项式项数为0
  303.  
  304. {
  305.  
  306. printf("多项式项数为0，退出!\n");
  307.  
  308. exit(0);
  309.  
  310. }
  311.  
  312. printf("生成的多项式如下：\n");
  313.  
  314. while((p->next)!=NULL)  //否则,则输出
  315.  
  316. {
  317.  
  318. printf("%3.1f X^%d + ",p->c,p->e);
  319.  
  320. p=p->next;
  321.  
  322. }
  323.  
  324. if(p->next==NULL)
  325.  
  326. {
  327.  
  328. printf("%3.1f X^%d\n",p->c,p->e);
  329.  
  330. }
  331.  
  332. }
  333.  
  334. float qiuzhi(int x,dnode *h)  //求多项式在x处的值
  335.  
  336. {
  337.  
  338. dnode *p;
  339.  
  340. float sum=0;
  341.  
  342. int i,t;
  343.  
  344. printf("请输入x的值：");
  345.  
  346. scanf("%d",&x);
  347.  
  348. for(p=h->next;p;p=p->next)
  349.  
  350. {
  351.  
  352. t=1;
  353.  
  354. for(i=p->e;i!=0;)
  355.  
  356. {
  357.  
  358. if(i<0){t/=x;i++;}//指数小于0，进行除法
  359.  
  360. else{t*=x;i--;}  //指数小于0，进行除法
  361.  
  362. }
  363.  
  364. sum+=p->c*t;
  365.  
  366. }
  367.  
  368. return sum;
  369.  
  370. }
  371.  
  372. void main()
  373.  
  374. {
  375.  
  376. int x;
  377.  
  378. float sum=0;
  379.  
  380. dnode *a,*b,*c;
  381.  
  382. a=creat();    //第一个多项式
  383.  
  384. sort(a);    //排序
  385.  
  386. prn(a);        //打印结果
  387.  
  388. b=creat();    //第二个多项式
  389.  
  390. sort(b);    //排序
  391.  
  392. prn(b);        //打印结果
  393.  
  394. c=operate(a,b); //结果多项式
  395.  
  396. prn(c);        //打印
  397.  
  398. sum=qiuzhi(x,c);
  399.  
  400. printf("多项式的值为：%.3f",sum);
  401.  
  402. printf("\n");
  403.  
  404. }

1.4 调试分析与测试结果
   1.4.1.调试：

【问题一】
- 输入错误：用户输入的多项式格式不正确，例如指数为负数或非整数，系数为非数字等。

解决办法：添加通俗易懂的文字提醒用户输入

【问题二】

   编译环境有问题

    解决办法：换一个编译器

   1.4.2测试结果：

2.模拟浏览器操作程序

2.1问题描述

        标准Web浏览器具有在最近访问的网页间后退和前进的功能。实现这些功能的一个方法是：使用两个栈,追踪可以后退和前进而能够到达的网页。在本题中,要求模拟实现这一功能。

2.2需求分析

 需要支持以下指令:

BACK：将当前页推到“前进栈”的顶部。取出“后退栈”中顶端的页面,使它成为当前页。若“后退栈”是空的,忽略该命令。

FORWARD:将当前页推到“后退栈”的顶部。取出“前进栈”中顶部的页面,使它成为当前页。如果“前进栈”是空的,忽略该命令。

VISIT <url>：将当前页推到“后退栈”的顶部。使 URL特指当前页。清空“前进栈”。

QUIT:退出浏览器。

假设浏览器首先加载的网页 URL 是：

2.3算法的设计与实现

        2.3.1设计思路

          运用了栈，“先进后出，后进先出”的特点。BACK,FORWARD操作对应的进行栈的进出。此外，还设置了标志位flag判断是否退出，将num与栈的长度进行比较，确定输出网址还是ignore。

       2.3.2主要函数说明

    void PUSHQ(QU *qu, char cur[ ])//入队

void POPQ(QU *qu)//出队

void PUSH(ST *st, char cur[])//入栈

void POP(ST *st)//出栈

int EMPTY(ST *st)//判空

void BACK(ST *stfront,ST *strear,char cur[], QU *qu)//回溯

void FORWARD(ST *stfront, ST *strear, char cur[], QU *qu)//前寻

void VISIT(ST *stfront,ST *strear, char cur[],QU *qu)//访问

  【源程序】

  1. #include <stdio.h>
  2.  
  3. #include <stdlib.h>
  4.  
  5. #include <string.h>
  6.  
  7. typedef struct stack
  8.  
  9. {
  10.  
  11. char s[100][70];
  12.  
  13. int top;
  14.  
  15. }ST;//栈定义
  16.  
  17. typedef struct queue
  18.  
  19. {
  20.  
  21. char q[100][70];
  22.  
  23. int head;
  24.  
  25. int tail;
  26.  
  27. }QU;//队列定义，用于接受输出
  28.  
  29. void PUSHQ(QU *qu, char cur[])//入队
  30.  
  31. {
  32.  
  33. if (qu->tail == 100)
  34.  
  35. {
  36.  
  37. printf("队满\n");
  38.  
  39. }
  40.  
  41. else
  42.  
  43. {
  44.  
  45.    qu->tail++;
  46.  
  47.    strncpy(qu->q[qu->tail], cur,strlen(cur) + 1);
  48.  
  49. }
  50.  
  51. }
  52.  
  53. void POPQ(QU *qu)//出队
  54.  
  55. {
  56.  
  57. qu->head++;
  58.  
  59. }
  60.  
  61. void PUSH(ST *st, char cur[])//入栈
  62.  
  63. {
  64.  
  65. if (st->top == 100)
  66.  
  67. {
  68.  
  69. printf("栈满\n");
  70.  
  71. }
  72.  
  73. else
  74.  
  75. {
  76.  
  77. strncpy(st->s[st->top],cur,strlen(cur)+1);
  78.  
  79. st->top++;
  80.  
  81. }
  82.  
  83. }
  84.  
  85. void POP(ST *st)//出栈
  86.  
  87. {
  88.  
  89. if (st->top == 0)
  90.  
  91. {
  92.  
  93. printf("栈空\n");
  94.  
  95. }
  96.  
  97. else
  98.  
  99. {
  100.  
  101. st->top--;
  102.  
  103. }
  104.  
  105. }
  106.  
  107. int EMPTY(ST *st)//判空
  108.  
  109. {
  110.  
  111. if (st->top == 0)
  112.  
  113. return 1;
  114.  
  115. else
  116.  
  117. return 0;
  118.  
  119. }
  120.  
  121. void BACK(ST *stfront,ST *strear,char cur[], QU *qu)//回溯
  122.  
  123. {
  124.  
  125. if (!EMPTY(strear))
  126.  
  127. {
  128.  
  129. PUSH(stfront, cur);
  130.  
  131. POP(strear);
  132.  
  133. strncpy(cur,strear->s[strear->top],strlen(strear->s[strear->top]) + 1);
  134.  
  135. PUSHQ(qu, cur);
  136.  
  137. }
  138.  
  139. else
  140.  
  141. {
  142.  
  143. char *a = "Ignored";
  144.  
  145. PUSHQ(qu, a);
  146.  
  147. }
  148.  
  149. }
  150.  
  151. void FORWARD(ST *stfront, ST *strear, char cur[], QU *qu)//前寻
  152.  
  153. {
  154.  
  155. if (!EMPTY(stfront))
  156.  
  157. {
  158.  
  159. PUSH(strear, cur);
  160.  
  161. POP(stfront);
  162.  
  163. strncpy(cur, stfront->s[stfront->top],strlen(stfront->s[stfront->top]) + 1);
  164.  
  165. PUSHQ(qu, cur);
  166.  
  167. }
  168.  
  169. else
  170.  
  171. {
  172.  
  173. char *a = "Ignored";
  174.  
  175. PUSHQ(qu,a);
  176.  
  177. }
  178.  
  179. }
  180.  
  181. void VISIT(ST *stfront,ST *strear, char cur[],QU *qu)//访问
  182.  
  183. {
  184.  
  185. PUSHQ(qu, cur);
  186.  
  187. stfront->top = 0;
  188.  
  189. }
  190.  
  191.  
  192. int main()
  193.  
  194. {
  195.  
  196. printf("输入：\n");
  197.  
  198. ST stfront;
  199.  
  200. ST strear;
  201.  
  202. stfront.top = 0;
  203.  
  204. strear.top = 0;
  205.  
  206. QU qu;
  207.  
  208. qu.head = -1;
  209.  
  210. qu.tail = -1;
  211.  
  212. char cur[70];
  213.  
  214. char start[70] = "http://www.acm.org/";//需先对此网站进行如回溯栈的特殊处理
  215.  
  216. char in[2][70];
  217.  
  218. strncpy(cur, start,strlen(start) + 1);
  219.  
  220. scanf("%s", in[0], 70);
  221.  
  222. while (strcmp(in[0], "QUIT") != 0)
  223.  
  224. {
  225.  
  226. if (strcmp(in[0], "VISIT") == 0)
  227.  
  228. {
  229.  
  230. PUSH(&strear, cur);
  231.  
  232. scanf("%s", in[1], 70);
  233.  
  234. strncpy(cur,in[1],strlen(in[1])+1);
  235.  
  236. VISIT(&stfront, &strear, cur, &qu);
  237.  
  238. }
  239.  
  240. else if (strcmp(in[0], "QUIT") == 0)
  241.  
  242. {
  243.  
  244. break;
  245.  
  246. }
  247.  
  248. else if (strcmp(in[0], "BACK") == 0)
  249.  
  250. {
  251.  
  252. BACK(&stfront, &strear, cur, &qu);
  253.  
  254. }
  255.  
  256. else
  257.  
  258. {
  259.  
  260. FORWARD(&stfront, &strear, cur, &qu);
  261.  
  262. }
  263.  
  264. scanf("%s", in[0], 70);
  265.  
  266. }
  267.  
  268. printf("输出：\n");//输出
  269.  
  270. while (qu.head != qu.tail)
  271.  
  272. {
  273.  
  274. POPQ(&qu);
  275.  
  276. printf("%s\n", qu.q[qu.head]);
  277.  
  278. }
  279.  
  280. return 0;
  281.  
  282. }

2.4调试分析与结果测试

  2.4.1调试分析：


   后退栈为空时执行BACK指令：
   - 当用户执行BACK指令时，程序应检查后退栈是否为空。
   - 如果后退栈为空，则无法执行BACK指令，程序应忽略该命令。
   - 当用户执行FORWARD指令时，程序应检查前进栈是否为空。
   - 如果前进栈为空，则无法执行FORWARD指令，程序应忽略该命令。
  执行VISIT指令：
   - 当用户执行VISIT指令时，程序应将当前页推到后退栈的顶部。
   - 如果指定的URL与当前页相同，则不进行任何操作。
   - 程序应清空前进栈，以确保用户在执行其他操作时无法前进到已访问的页面。
 执行QUIT指令：
   - 当用户执行QUIT指令时，程序应退出浏览器。
 初始加载网页URL：
   - 浏览器首次加载网页URL为

http://www.acm.org/。
   - 程序应将此URL作为当前页，并将其推入后退栈的顶部。


  2.4.2测试结果

   

3.图的基本操作与实现

3.1问题描述

         要求用邻接表存储结构,实现对图 11-3 所示的有向带权网络 G 的操作。

3.2需求分析

 (1)输入含 n(1≤n≤100)个顶点(用字符表示顶点)和e条边。

(2)求每个顶点的出度和人度,输出结果。

(3)指定任意顶点×为初始顶点,对图G作DFS遍历,输出 DFS 顶点序列。

(4)指定任意顶点x为初始顶点,对图G作BFS 遍历,输出 BFS 顶点序列。

(5)输入顶点 x,查找图 G：若存在含x 的顶点,则删除该结点及与之相关联的边,并作 DFS遍历；否则输出信息“无x”。

(6）判断图 G是否是连通图,输出信息“YES”/“NO”。

(7)根据图 G 的邻接表创建图 G 的邻接矩阵,即复制图G。

(8)找出该图的一棵最小生成树。

3.3算法设计与实现

3.3.1设计思路

1. 创建一个图的类，包含顶点和边的数据结构和操作方法。
2. 定义一个函数，接受输入的顶点和边的数量，并创建对应数量的顶点和边。
3. 定义函数来计算每个顶点的出度和入度，并输出结果。
4. 定义DFS遍历函数，接受初始顶点作为参数，使用递归或者栈来实现深度优先搜索，并输出DFS顶点序列。
5. 定义BFS遍历函数，接受初始顶点作为参数，使用队列来实现广度优先搜索，并输出BFS顶点序列。
6. 定义函数来接受输入的顶点x，并查找图G中与之相关联的顶点和边。如果存在顶点x，则删除该顶点及与之相关联的边，并进行DFS遍历；否则输出"无x"。
7. 定义函数来判断图G是否是连通图。使用DFS或BFS遍历，检查是否可以遍历到所有的顶点。如果可以，则输出"YES"；否则输出"NO"。
8. 定义函数来根据图G的邻接表创建邻接矩阵，并复制图G。
9. 定义函数来找出图的一棵最小生成树。使用Prim算法或Kruskal算法来实现。

3.3.2主要函数说明及源程序

   

  1.         //有向带权图，邻接表中的节点
  2. typedef struct Node {
  3.     int value;//顶点下标，也可以说是值
  4.     int weight;//权
  5.     struct Node* next;//指针域
  6. } Node;
  7. // 图的结构
  8. typedef struct Graph {
  9.     int numNodes;//节点数
  10.     Node** adjacencyList;
  11. } Graph;
  12. // 创建节点
  13. Node* createNode(int value, int weight) {
  14.     Node* newNode = (Node*)malloc(sizeof(Node));
  15.     newNode->value = value;
  16.     newNode->weight = weight;
  17.     newNode->next = NULL;
  18.     return newNode;
  19. }
  20. // 创建图，传入节点数
  21. Graph* createGraph(int numNodes) {
  22.     Graph* graph = (Graph*)malloc(sizeof(Graph));
  23.     graph->numNodes = numNodes;
  24.     graph->adjacencyList = (Node**)malloc(numNodes * sizeof(Node*));
  25.     // 初始化邻接表为空
  26.     for (int i = 0; i < numNodes; i++) {
  27.         graph->adjacencyList[i] = NULL;
  28.     }
  29.     return graph;
  30. }
  31. // 添加边
  32. void addEdge(Graph* graph, int source, int target, int weight) {
  33.     // 创建新的节点
  34.     Node* newNode = createNode(target, weight);
  35.     // 将新节点插入到源节点的邻接表中，顶点以下标为标准直接以头插法插入
  36.     newNode->next = graph->adjacencyList[source];
  37.     graph->adjacencyList[source] = newNode;
  38. }
  39. // 求顶点的出度
  40. int outDegree(Graph* graph, int vertex) {
  41.     Node* currentNode = graph->adjacencyList[vertex];
  42.     int outDegree = 0;
  43.     while (currentNode != NULL) {
  44.         outDegree++;
  45.         currentNode = currentNode->next;
  46.     }
  47.     return outDegree;
  48. }
  49.  
  50. // 求顶点的入度，遍历整个邻接表
  51. int inDegree(Graph* graph, int vertex) {
  52.     int inDegree = 0;
  53.     for (int i = 0; i < graph->numNodes; i++) {
  54.         Node* currentNode = graph->adjacencyList[i];
  55.         while (currentNode != NULL) {
  56.             if (currentNode->value == vertex) {
  57.                 inDegree++;
  58.             }
  59.             currentNode = currentNode->next;
  60.         }
  61.     }
  62.     return inDegree;
  63. }
  64. // 深度优先，递归遍历
  65. void DFS(Graph* graph, int vertex, int* visited) {
  66.     visited[vertex] = 1;
  67.     printf("%d ", vertex);
  68.     Node* currentNode = graph->adjacencyList[vertex];
  69.     while (currentNode != NULL) {
  70.         int neighbor = currentNode->value;
  71.         if (!visited[neighbor]) {
  72.             DFS(graph, neighbor, visited);
  73.         }//如果此顶点未被访问，则继续深度优先遍历
  74.         currentNode = currentNode->next;
  75.     }
  76. }
  77. // 广度优先遍历
  78. void BFS(Graph* graph, int startVertex) {
  79.     int* visited = (int*)malloc(graph->numNodes * sizeof(int));
  80.     for (int i = 0; i < graph->numNodes; i++) {
  81.         visited[i] = 0;
  82.     }
  83.     // 创建队列
  84.     int* queue = (int*)malloc(graph->numNodes * sizeof(int));
  85.     int front = 0;
  86.     int rear = 0;
  87.  
  88.     visited[startVertex] = 1;
  89.     printf("%d ", startVertex);
  90.     queue[rear++] = startVertex;
  91.  
  92.     while (front < rear) {
  93.         int vertex = queue[front++];
  94.         Node* currentNode = graph->adjacencyList[vertex];
  95.         while (currentNode != NULL) {
  96.             int neighbor = currentNode->value;
  97.             if (!visited[neighbor]) {
  98.                 visited[neighbor] = 1;
  99.                 printf("%d ", neighbor);
  100.                 queue[rear++] = neighbor;
  101.             }
  102.             currentNode = currentNode->next;
  103.         }
  104.     }
  105.     free(visited);
  106.     free(queue);
  107. }
  108.  
  109. // 查找顶点
  110. bool searchVertex(Graph* graph, int vertex) {
  111.     for (int i = 0; i < graph->numNodes; i++) {
  112.         Node* currentNode = graph->adjacencyList[i];
  113.         while (currentNode != NULL) {
  114.             if (currentNode->value == vertex) {
  115.                 return true;
  116.             }
  117.             currentNode = currentNode->next;
  118.         }
  119.     }
  120.     return false;
  121. }
  122. // 判断是否为连通图
  123. bool isConnected(Graph* graph) {
  124.     int* visited = (int*)malloc(graph->numNodes * sizeof(int));
  125.     for (int i = 0; i < graph->numNodes; i++) {
  126.         visited[i] = 0;
  127.     }
  128.  
  129.     DFS(graph, 0, visited);
  130.  
  131.     for (int i = 0; i < graph->numNodes; i++) {
  132.         if (visited[i] == 0) {
  133.             free(visited);
  134.             return false;
  135.         }
  136.     }
  137.  
  138.     free(visited);
  139.     return true;
  140. }
  141.  
  142. // 创建邻接矩阵
  143. int** createAdjacencyMatrix(Graph* graph) {
  144.     int** matrix = (int**)malloc(graph->numNodes * sizeof(int*));
  145.     for (int i = 0; i < graph->numNodes; i++) {
  146.         matrix[i] = (int*)malloc(graph->numNodes * sizeof(int));
  147.         for (int j = 0; j < graph->numNodes; j++) {
  148.             matrix[i][j] = 0;
  149.         }
  150.     }
  151.  
  152.     for (int i = 0; i < graph->numNodes; i++) {
  153.         Node* currentNode = graph->adjacencyList[i];
  154.         while (currentNode != NULL) {
  155.             matrix[i][currentNode->value] = currentNode->weight;
  156.             currentNode = currentNode->next;
  157.         }
  158.     }
  159.  
  160.     return matrix;
  161. }
  162.  
  163. 【源程序】
  164.  
  165. #include <stdio.h>
  166.  
  167. #include <stdlib.h>
  168.  
  169. #include <stdbool.h>
  170.  
  171. //有向带权图
  172.  
  173. // 邻接表中的节点
  174.  
  175. typedef struct Node {
  176.  
  177.     int value;//顶点下标，也可以说是值
  178.  
  179.     int weight;//权
  180.  
  181.     struct Node* next;//指针域
  182.  
  183. } Node;
  184.  
  185.  
  186. // 图的结构
  187.  
  188. typedef struct Graph {
  189.  
  190.     int numNodes;//节点数
  191.  
  192.     Node** adjacencyList;
  193.  
  194. } Graph;
  195.  
  196.  
  197. // 创建节点
  198.  
  199. Node* createNode(int value, int weight) {
  200.  
  201.     Node* newNode = (Node*)malloc(sizeof(Node));
  202.  
  203.     newNode->value = value;
  204.  
  205.     newNode->weight = weight;
  206.  
  207.     newNode->next = NULL;
  208.  
  209.     return newNode;
  210.  
  211. }
  212.  
  213.  
  214. // 创建图，传入节点数
  215.  
  216. Graph* createGraph(int numNodes) {
  217.  
  218.     Graph* graph = (Graph*)malloc(sizeof(Graph));
  219.  
  220.     graph->numNodes = numNodes;
  221.  
  222.     graph->adjacencyList = (Node**)malloc(numNodes * sizeof(Node*));
  223.  
  224.  
  225.     // 初始化邻接表为空
  226.  
  227.     for (int i = 0; i < numNodes; i++) {
  228.  
  229.         graph->adjacencyList[i] = NULL;
  230.  
  231.     }
  232.  
  233.  
  234.     return graph;
  235.  
  236. }
  237.  
  238. // 添加边
  239.  
  240. void addEdge(Graph* graph, int source, int target, int weight) {
  241.  
  242.     // 创建新的节点
  243.  
  244.     Node* newNode = createNode(target, weight);
  245.  
  246.     // 将新节点插入到源节点的邻接表中，顶点以下标为标准直接以头插法插入
  247.  
  248.     newNode->next = graph->adjacencyList[source];
  249.  
  250.     graph->adjacencyList[source] = newNode;
  251.  
  252. }
  253.  
  254. // 求顶点的出度
  255.  
  256. int outDegree(Graph* graph, int vertex) {
  257.  
  258.     Node* currentNode = graph->adjacencyList[vertex];
  259.  
  260.     int outDegree = 0;
  261.  
  262.     while (currentNode != NULL) {
  263.  
  264.         outDegree++;
  265.  
  266.         currentNode = currentNode->next;
  267.  
  268.     }
  269.  
  270.     return outDegree;
  271.  
  272. }
  273.  
  274. // 求顶点的入度，遍历整个邻接表
  275.  
  276. int inDegree(Graph* graph, int vertex) {
  277.  
  278.     int inDegree = 0;
  279.  
  280.     for (int i = 0; i < graph->numNodes; i++) {
  281.  
  282.         Node* currentNode = graph->adjacencyList[i];
  283.  
  284.         while (currentNode != NULL) {
  285.  
  286.             if (currentNode->value == vertex) {
  287.  
  288.                 inDegree++;
  289.  
  290.             }
  291.  
  292.             currentNode = currentNode->next;
  293.  
  294.         }
  295.  
  296.     }
  297.  
  298.     return inDegree;
  299.  
  300. }
  301.  
  302. // 深度优先，递归遍历
  303.  
  304. void DFS(Graph* graph, int vertex, int* visited) {
  305.  
  306.     visited[vertex] = 1;
  307.  
  308.     printf("%d ", vertex);
  309.  
  310.     Node* currentNode = graph->adjacencyList[vertex];
  311.  
  312.     while (currentNode != NULL) {
  313.  
  314.         int neighbor = currentNode->value;
  315.  
  316.         if (!visited[neighbor]) {
  317.  
  318.             DFS(graph, neighbor, visited);
  319.  
  320.         }//如果此顶点未被访问，则继续深度优先遍历
  321.  
  322.         currentNode = currentNode->next;
  323.  
  324.     }
  325.  
  326. }
  327.  
  328. // 广度优先遍历
  329.  
  330. void BFS(Graph* graph, int startVertex) {
  331.  
  332.     int* visited = (int*)malloc(graph->numNodes * sizeof(int));
  333.  
  334.     for (int i = 0; i < graph->numNodes; i++) {
  335.  
  336.         visited[i] = 0;
  337.  
  338.     }
  339.  
  340.     // 创建队列
  341.  
  342.     int* queue = (int*)malloc(graph->numNodes * sizeof(int));
  343.  
  344.     int front = 0;
  345.  
  346.     int rear = 0;
  347.  
  348.     visited[startVertex] = 1;
  349.  
  350.     printf("%d ", startVertex);
  351.  
  352.     queue[rear++] = startVertex;
  353.  
  354.     while (front < rear) {
  355.  
  356.         int vertex = queue[front++];
  357.  
  358.         Node* currentNode = graph->adjacencyList[vertex];
  359.  
  360.         while (currentNode != NULL) {
  361.  
  362.             int neighbor = currentNode->value;
  363.  
  364.             if (!visited[neighbor]) {
  365.  
  366.                 visited[neighbor] = 1;
  367.  
  368.                 printf("%d ", neighbor);
  369.  
  370.                 queue[rear++] = neighbor;
  371.  
  372.             }
  373.  
  374.             currentNode = currentNode->next;
  375.  
  376.         }
  377.  
  378.     }
  379.  
  380.     free(visited);
  381.  
  382.     free(queue);
  383.  
  384. }
  385.  
  386. // 查找顶点
  387.  
  388. bool searchVertex(Graph* graph, int vertex) {
  389.  
  390.     for (int i = 0; i < graph->numNodes; i++) {
  391.  
  392.         Node* currentNode = graph->adjacencyList[i];
  393.  
  394.         while (currentNode != NULL) {
  395.  
  396.             if (currentNode->value == vertex) {
  397.  
  398.                 return true;
  399.  
  400.             }
  401.  
  402.             currentNode = currentNode->next;
  403.  
  404.         }
  405.  
  406.     }
  407.  
  408.     return false;
  409.  
  410. }
  411.  
  412. // 判断是否为连通图
  413.  
  414. bool isConnected(Graph* graph) {
  415.  
  416.     int* visited = (int*)malloc(graph->numNodes * sizeof(int));
  417.  
  418.     for (int i = 0; i < graph->numNodes; i++) {
  419.  
  420.         visited[i] = 0;
  421.  
  422.     }
  423.  
  424.     DFS(graph, 0, visited);
  425.  
  426.     for (int i = 0; i < graph->numNodes; i++) {
  427.  
  428.         if (visited[i] == 0) {
  429.  
  430.             free(visited);
  431.  
  432.             return false;
  433.  
  434.         }
  435.  
  436.     }
  437.  
  438.     free(visited);
  439.  
  440.     return true;
  441.  
  442. }
  443.  
  444. // 创建邻接矩阵
  445.  
  446. int** createAdjacencyMatrix(Graph* graph) {
  447.  
  448.     int** matrix = (int**)malloc(graph->numNodes * sizeof(int*));
  449.  
  450.     for (int i = 0; i < graph->numNodes; i++) {
  451.  
  452.         matrix[i] = (int*)malloc(graph->numNodes * sizeof(int));
  453.  
  454.         for (int j = 0; j < graph->numNodes; j++) {
  455.  
  456.             matrix[i][j] = 0;
  457.  
  458.         }
  459.  
  460.     }
  461.  
  462.  
  463.     for (int i = 0; i < graph->numNodes; i++) {
  464.  
  465.         Node* currentNode = graph->adjacencyList[i];
  466.  
  467.         while (currentNode != NULL) {
  468.  
  469.             matrix[i][currentNode->value] = currentNode->weight;
  470.  
  471.             currentNode = currentNode->next;
  472.  
  473.         }
  474.  
  475.     }
  476.  
  477.     return matrix;
  478.  
  479. }
  480.  
  481. int main() {
  482.  
  483.     int numNodes = 6;
  484.  
  485.     Graph* graph = createGraph(numNodes);
  486.  
  487.     addEdge(graph, 0, 1, 2);
  488.  
  489.     addEdge(graph, 0, 2, 3);
  490.  
  491.     addEdge(graph, 1, 2, 1);
  492.  
  493.     addEdge(graph, 2, 3, 4);
  494.  
  495.     addEdge(graph, 3, 1, 5);
  496.  
  497.     addEdge(graph, 3, 4, 2);
  498.  
  499.     addEdge(graph, 4, 0, 1);
  500.  
  501.     addEdge(graph, 4, 2, 3);
  502.  
  503.     addEdge(graph, 5, 3, 2);
  504.  
  505.     // 求每个顶点的出度和入度
  506.  
  507.     for (int i = 0; i < numNodes; i++) {
  508.  
  509.         printf("顶点%d的出度：%d\n", i, outDegree(graph, i));
  510.  
  511.         printf("顶点%d的入度：%d\n", i, inDegree(graph, i));
  512.  
  513.     }
  514.  
  515.     printf("从顶点0开始的DFS顶点序列：");
  516.  
  517.     int* visitedDFS = (int*)malloc(numNodes * sizeof(int));
  518.  
  519.     for (int i = 0; i < numNodes; i++) {
  520.  
  521.         visitedDFS[i] = 0;//生成所有顶点
  522.  
  523.     }
  524.  
  525.     DFS(graph, 0, visitedDFS);
  526.  
  527.     printf("\n");
  528.  
  529.     printf("从顶点0开始的BFS顶点序列：");
  530.  
  531.     BFS(graph, 0);
  532.  
  533.     printf("\n");
  534.  
  535.     int searchVertexValue = 2;
  536.  
  537.     printf("查找顶点%d：", searchVertexValue);
  538.  
  539.     if (searchVertex(graph, searchVertexValue)) {
  540.  
  541.         printf("存在\n");
  542.  
  543.     }
  544.  
  545.     else {
  546.  
  547.         printf("不存在\n");
  548.  
  549.     }
  550.  
  551.     printf("图是否为连通图：");
  552.  
  553.     if (isConnected(graph)) {
  554.  
  555.         printf("是\n");
  556.  
  557.     }
  558.  
  559.     else {
  560.  
  561.         printf("不是\n");
  562.  
  563.     }
  564.  
  565.     int** adjacencyMatrix = createAdjacencyMatrix(graph);
  566.  
  567.     printf("邻接矩阵：\n");
  568.  
  569.     for (int i = 0; i < numNodes; i++) {
  570.  
  571.         for (int j = 0; j < numNodes; j++) {
  572.  
  573.             printf("%d ", adjacencyMatrix[i][j]);
  574.  
  575.         }
  576.  
  577.         printf("\n");
  578.  
  579.     }
  580.  
  581.     }

3.4调试分析与结果测试

  3.4.1调试分析：

【问题一】
输入格式错误问题：用户输入的顶点和边的数量可能不符合要求。

解决方法是在接收输入时进行验证，确保顶点和边的数量在有效范围内。

【问题二】
DFS遍历问题：DFS遍历可能陷入无限循环，或者无法访问到所有的顶点。

解决方法是使用一个标记数组来记录已经访问过的顶点，避免重复访问，并确保能够访问到所有的顶点。
   【问题三】
  BFS遍历问题：BFS遍历可能无法处理有向图中的环路，导致陷入无限循环。

解决方法是使用一个队列来保存待访问的顶点，并使用一个标记数组来记录已经访问过的顶点。
   【问题四】
  图中不存在指定顶点问题：在进行删除操作或查找操作时，如果图中不存在指定的顶点，可能会引发错误。解决方法是在操作之前进行判断，如果顶点不存在，则输出相应的提示信息。
    【问题五】
 连通图判断问题：判断图是否为连通图可能需要进行图的遍历。

解决方法是通过DFS或BFS遍历图，并检查是否能够访问到所有的顶点。

  3.4.2测试结果：

4.八皇后问题

4.1问题描述

         八皇后问题是一个古老而著名的问题,它是回溯算法的典型例题。该问题是 19 世纪德国著名数学家高斯于 1850 年提出的：在 8 行 8 列的国际象棋棋盘上摆放着 8 个皇后。若两个皇后位于同一行、同一列或同一对角线上,则称为它们为互相攻击。在国际象棋中皇后是最强大的棋子,因为它的攻击范围最大,

4.2需求分析

          编程解决八皇后问题。在 8×8 的棋盘上,放置 8 个皇后。要求使这8 个皇后不能相互攻击,即每一横行、每一列,每一对角线上均只能放置一个皇后,求出所有可能的方案,输出这些方案,并统计方案总数。

4.3算法设计与实现

         4.3.1.设计思路

      因为八个皇后每一行只能有一个占据东宫的位置，所以我们只需要定义一个一维数组，每一个数字来表示皇后所在的列数即可。我们在每摆放一个新的皇后时都要与前面的皇后进行if语句的判断，确保她们不会再同一行上，不会在直角线上（成45°或135°）（定义的一维数组已经保证每一行只会有一个皇后，如果if不成立，则返回上一个皇后的位置重新选择）。

 4.3.2主要函数说明及源程序
  1.     #include<stdio.h>
  2.  
  3. int main()
  4.  
  5.                   int count = 0;//计数器，每成功摆放一次记一次
  6.  
  7. for (int q1 = 0; q1 < 8; q1++)
  8.  
  9. {
  10.  
  11. for (int q2 = 0; q2 < 8; q2++)
  12.  
  13. {
  14.  
  15. if (q1 == q2 || q1 == q2 + 1 || q1 == q2 - 1)
  16.  
  17. {
  18.  
  19. continue;
  20.  
  21. }
  22.  
  23. for (int q3 = 0;q3 < 8; q3++)
  24.  
  25. {
  26.  
  27. if (q1 == q3 || q1 == q3 + 2 || q1 == q3-2
  28.  
  29. || q2 == q3 || q2 == q3 + 1|| q2 == q3 - 1)
  30.  
  31. {
  32.  
  33. continue;
  34.  
  35. }
  36.  
  37. for (int q4 = 0; q4 < 8; q4++)
  38.  
  39. {
  40.  
  41. if (q1 == q4 || q1 == q4 + 3 || q1 == q4 - 3
  42.  
  43. || q2 == q4 || q2 == q4 + 2|| q2 == q4- 2
  44.  
  45. || q3 == q4 || q3 == q4 + 1 || q3== q4- 1)
  46.  
  47. {
  48.  
  49. continue;
  50.  
  51. }
  52.  
  53. for (int q5 = 0; q5 < 8; q5++)
  54.  
  55. {
  56.  
  57. if (q1 == q5 || q1 == q5 + 4 || q1 == q5 - 4
  58.  
  59. || q2 == q5 || q2 == q5 + 3|| q2 == q5 - 3
  60.  
  61. || q3 == q5 || q3 == q5 + 2 || q3 == q5- 2
  62.  
  63. || q4 == q5 || q4 == q5 + 1 || q4 == q5 - 1)
  64.  
  65. {
  66.  
  67. continue;
  68.  
  69. }
  70.  
  71. for (int q6 = 0; q6 < 8; q6++)
  72.  
  73. {
  74.  
  75. if (q1 == q6 || q1 == q6 + 5 || q1 == q6 - 5
  76.  
  77. || q2 == q6 || q2 == q6 + 4 || q2 == q6 - 4
  78.  
  79. || q3 == q6 || q3 == q6 + 3 || q3 == q6 - 3
  80.  
  81. || q4 == q6 || q4 == q6 + 2 || q4 == q6 - 2
  82.  
  83. || q5 == q6 || q5 == q6 + 1 || q5 == q6 - 1)
  84.  
  85. {
  86.  
  87. continue;
  88.  
  89. }
  90.  
  91. for (int q7 = 0; q7 < 8; q7++)
  92.  
  93. {
  94.  
  95. if (q1 == q7 || q1 == q7 + 6 || q1 == q7 - 6
  96.  
  97. || q2 == q7 || q2 == q7 + 5 || q2 == q7 - 5
  98.  
  99. || q3 == q7 || q3 == q7 + 4 || q3 == q7 - 4
  100.  
  101. || q4 == q7 || q4 == q7 + 3 || q4 == q7 - 3
  102.  
  103. || q5 == q7 || q5 == q7 + 2 || q5 == q7 - 2
  104.  
  105. || q6 == q7 || q6 == q7 + 1 || q6 == q7 - 1)
  106.  
  107. {
  108.  
  109. continue;
  110.  
  111. }
  112.  
  113. for (int q8 = 0; q8 < 8; q8++)
  114.  
  115. {
  116.  
  117.                if (q1 == q8 || q1 == q8 + 7 || q1 == q8 - 7
  118.  
  119. || q2 == q8 || q2 == q8 + 6 || q2 == q8 -6
  120.  
  121. || q3 == q8 || q3 == q8 + 5 || q3 == q8 -5
  122.  
  123. || q4 == q8 || q4 == q8 + 4 || q4 == q8 -4
  124.  
  125. || q5 == q8 || q5 == q8 + 3 || q5 == q8 -3
  126.  
  127. || q6 == q8 || q6 == q8 + 2 || q6 == q8 -2
  128.  
  129. || q7 == q8 || q7 == q8 + 1 || q7 == q8 -1)
  130.  
  131. {
  132.  
  133. continue;
  134.  
  135. }
  136.  
  137. count++;
  138.  
  139.                         printf("%d,%d,%d,%d,%d,%d,%d,%d\n", q1, q2, q3, q4,q5, q6, q7, q8);                        
  140.  
  141. }
  142.  
  143. }
  144.  
  145. }
  146.  
  147. }
  148.  
  149. }
  150.  
  151. }
  152.  
  153. }
  154.  
  155. }
  156.  
  157. printf("一共有%d种方法", count);
  158.  
  159. return 0;
  160.  
  161. }

4.4 调试分析与结果测试

   4.4.1调试分析

       【问题一】

        运行环境存在问题，在Dev C++中运行出现问题，结果出现遗漏

         解决方法：换一个编译环境，换为Visual 6.0运行成功

    4.4.2测试结果：

     

5.木棒加工问题

5.1问题描述

现有 n 根木棒,已知它们的长度和重量,要用一部木工机一根一根地加工这些木棒。该的准备时间如下：

  1. 第一根木棒需要 1 分钟的准备时间。

(2)在加工完一根长为 lenth,重为 weight 的木棒之后,接着加工一根长为lenth'(lenth<=lenth'),重为 weight'(weight<= weight')的木棒是不需要任何准备时间的。否则需要一分钟的准备时间。

5.2需求分析

给定 n(1<n≤5000)根木棒,已知它们的长度和重量,请编写程序:找到加工完所有的木棒所需的最少准备时间,以及加工这些木棒的顺序。

5.3算法设计与分析

5.3.1设计思路

      先对ｎ根木棒按照长度进行全局排序，得到了一个长度有序而重量无序的序列（贪心先按长度排序）。\n再在每一个同一长度序列中，对重量进行局部排序。至此，长度和重量都是有序的。\n最长单调递增子序列的个数（采用动态规划），即为最终的答案。

5.3.2主要函数说明及源程序

void sort_length(int n）  //排序算法

void sort_weight(int n)   //同一长度内进行排序

 【源程序】

  1. #include <iostream>
  2.  
  3. #include <malloc.h>
  4.  
  5. #define max 5001
  6.  
  7. typedef struct{
  8.  
  9. int length, weight;
  10.  
  11. }boat;
  12.  
  13. boat b[max];
  14.  
  15. int count = 0;
  16.  
  17. using namespace std;
  18.  
  19. void sort_length(int n){
  20.  
  21. //排序算法
  22.  
  23. int i, j;
  24.  
  25. boat x;
  26.  
  27. for(i=1; i<=n; i++){
  28.  
  29. for(j=1; j<=n-i; j++){
  30.  
  31. if(b[j].length >= b[j+1].length){
  32.  
  33. x = b[j];
  34.  
  35. b[j] = b[j+1];
  36.  
  37. b[j+1] = x;
  38.  
  39. }
  40.  
  41. }
  42.  
  43. }
  44.  
  45. }
  46.  
  47. void sort_weight(int n){
  48.  
  49. boat x;
  50.  
  51. int i=1, j=1, p=0;
  52.  
  53. int k, s;
  54.  
  55. //同一长度内进行排序
  56.  
  57. for(i=1; i<=n; i++){
  58.  
  59. x = b[i];
  60.  
  61. j = i+1;
  62.  
  63. while(b[i].length == b[j].length){
  64.  
  65. j++;
  66.  
  67. }
  68.  
  69. p = 0;
  70.  
  71. for(k=i; k<j; k++){
  72.  
  73. //冒泡排序
  74.  
  75. for(s=i; s<j-p-1; s++){
  76.  
  77. if(b[s].weight >= b[s+1].weight){
  78.  
  79. x = b[s];
  80.  
  81. b[s] = b[s+1];
  82.  
  83. b[s+1] = x;
  84.  
  85. }
  86.  
  87. }
  88.  
  89. p++;
  90.  
  91. }
  92.  
  93. i = j-1;
  94.  
  95. }
  96.  
  97. for(i=1; i<=n; i++){
  98.  
  99. printf("%d %d\n", b[i].length, b[i].weight);
  100.  
  101. }
  102.  
  103. //排序完成
  104.  
  105. for(i=1; i<=n; i++){
  106.  
  107. k=i;
  108.  
  109. for(j=i+1; j<=n; j++){
  110.  
  111. if(b[i].length == b[j].length){
  112.  
  113. i = j;continue;
  114.  
  115. }
  116.  
  117. if(b[i].weight <= b[j].weight){
  118.  
  119. i = i+1;
  120.  
  121. x = b[j];
  122.  
  123. //元素后移
  124.  
  125. for(s=j; s>i; s--){
  126.  
  127. b[s] = b[s-1];
  128.  
  129. // printf("%d %d\n", b[s].length, b[s].weight);
  130.  
  131. }
  132.  
  133. b[i] = x;
  134.  
  135. }
  136.  
  137. }
  138.  
  139. count++;
  140.  
  141. printf("\n每一次加工的木棒\n");
  142.  
  143. for(; k<=i; k++){
  144.  
  145. printf("%d %d\n", b[k].length, b[k].weight);
  146.  
  147. }
  148.  
  149. }
  150.  
  151. printf("\n总共所需要的时间：%dmin\n", count);
  152.  
  153. }
  154.  
  155. int main(){
  156.  
  157. int n;
  158.  
  159. int i;
  160.  
  161. printf("请输入木棒总数：");
  162.  
  163. scanf("%d", &n);
  164.  
  165. printf("请输入木棒的长度和重量：");
  166.  
  167.     for(i=1;i<=n;i++){
  168.  
  169.      scanf("%d%d", &b[i].length, &b[i].weight);
  170.  
  171. }
  172.  
  173. printf("先按照长度进行排序。\n");
  174.  
  175. sort_length(n);
  176.  
  177. for(i=1; i<=n; i++){
  178.  
  179. printf("%d %d\n", b[i].length, b[i].weight);
  180.  
  181. }
  182.  
  183. printf("\n再在排好序的基础上按照重量排序。\n");
  184.  
  185. sort_weight(n);
  186.  
  187. return 0;
  188.  
  189. }

5.4调试分析与结果测试

  5.4.1调试分析

    【问题一】

         1.输入数据的格式错误：如果输入的木棒数量小于等于1或者大于5000，或者木棒的长度和重量不符合要求，程序可能无法正确处理这些数据。

解决方法：注意程序所给的提示

     5.4.2测试结果：

三．课程设计总结

     此次课程设计的题目可以说经典但是有点难度，主要体现在对于题目的理解和运用程序难以实现,在程序运行过程中还出现了包括编译环境在内的一系列问题，。我参照了网上的很多代码，几乎都需要自己的理解加上改写，这对于我是非常大的难题。好在班上有和我选一样的题的同学，这使我们可以一起探讨关于编程以及算法设计上的问题。也帮我解决了课程设计中的绝大多数问题。与此同时，经过这次的课程设计，我的对于程序的编写和改写能力得到了明显的提高，对结果的分析能力，资料搜集、阅读及整理能力，以及良好的沟通、表达能力都显著提升。也加深对常用数据结构理论知识的理解，能够运用各种数据结构与算法，独立分析、设计、解决问题。通过良好的文字、口头等沟通方式，表达个人对系统设计、实施及测试结论等方面的见解。

四．参考文献

  1. 谭浩强.c程序设计（第二版）北京：清华大学出版社，2004
  2. 严蔚敏，吴伟民.数据结构.北京：清华大学出版社，2005
  3. 林劼,刘震,陈端兵等.数据结构与算法[M].北京大学出版社,2019.

陈锐,张志锋,马军霞.数据结构与算法详解[M]

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号