线性表
第一题：顺序表插入
[问题描述]
设顺序表A中的数据元素递增有序，试写一程序，将x插入到顺序表的适当位置上，使该表仍然有序。
[输入]
初始顺序表，插入位置，插入元素。
[输出]
插入元素后的顺序表。
[存储结构]
采用顺序存储结构
[算法的基本思想]
建立顺序表：使用默认的初始分配量建立顺序表，根据输入的初始顺序表建立对应的顺序表；插入元素：根据读入的元素在顺序表中找插入位置，将原该位置处的元素以及其后元素从最后一个挨个向后移动，再将该元素插入；打印顺序表：从顺序表的第一个元素开始，依次打印各个元素。
#include <stdio.h> #define maxSize 100 typedef struct{ int date[maxSize]; //类似于数组的创建，为静态分配空间 int length; }sqList; void initSqList(sqList &L, int length){ //顺序表的创建 int i; int x; L.length = length; printf("请输入有序顺序表A有\n"); for(i = 0; i < length; i++){ scanf("%d", &x); L.date[i] = x; } } int insertElem(sqList &L, int x, int n){ //在线性表L中，n位置插入x int i; if(n < 0 || n > L.length || L.length == maxSize) //线性表条件判断 return 0; for(i = L.length - 1; i >= n - 1; i--){ //插入位置后元素的移动 L.date[i + 1] = L.date[i]; } L.date[n - 1] = x; L.length ++; return 1; } int main(){ sqList sq; int i; printf("请输入顺序表A的长度\n"); int length; scanf("%d", &length); initSqList(sq, length); printf("请输入插入元素："); int x; scanf("%d", &x); printf("请输入插入位置："); int n; scanf("%d", &n); int insert; insert = insertElem(sq, x, n); if(insert == 0) printf("插入失败:"); if(insert == 1) printf("插入成功:"); for(i = 0; i < sq.length; i++){ printf("%d ",sq.date[i]); } }
结果演示：
结果与分析：
（1）优点：实现了插入功能，并经行了条件判断。（2）缺点：代码的健壮性较差对一些极端情况没有考虑。（3）时间复杂度：O(n) （4）空间复杂度：O(n)
第二题：多项式链式存储
[问题描述]
用单链表ha 存储多项式A（x ）=a0+a1x1+a2x2+…+anxn(其中aI为非零系数)，用单链表hb 存储多项式B（x ）=b0+b1x1+b2x2+…+bmxm(其中bj为非零系数)，要求计算C（x ）= A（x ）+B（x ），结果存到单链表hc中。试写出程序。
[输入]
初始化单链表，创建A，B链表。
[输出]
A，B链表的和C链表。
[存储结构]
采用链式存储结构
[算法的基本思想]
建立单链表：构造单链表节点，包含3个域，分别记录系数以及指数和下一个原素；存储链表A，B，链表求和：同时遍历A，B链表若指数相同的对应相加，若不相等则分别加入C中，存入C，输出链表C
#include <stdio.h> #include <malloc.h> #define NULL 0 typedef struct LNode{ int a; //系数 int b; //指数 struct LNode *next; }LNode, *node; void initLNode(node &L){ //将二项式存入列表，使用&引用型指针，实现对实参的修改 int i; int length; node p, q; L = (node)malloc(sizeof(LNode)); //头的结点空间申请 p = L; printf("请输入多项式的项数："); scanf("%d",&length); for(i = 1; i <= length; i++){ //结点的创建 q = (node)malloc(sizeof(LNode)); printf("请输入第%d项的系数",i); scanf("%d",&q->a); printf("请输入第%d项的指数",i); scanf("%d",&q->b); p->next = q; p = q; } p->next = NULL; } node addLNode(node A, node B){ //二项式加法实现 node C; C = (node)malloc(sizeof(LNode)); node p, q, r, s; //辅助指针 p = A->next; q = B->next; r = C; while(p != NULL && q != NULL){ //同时遍历A,B链表 s = (node)malloc(sizeof(LNode)); if(p->b == q->b){ //指数相同 s->a = p->a + q->a; s->b = p->b; r->next = s; p = p->next; q = q->next; r = s; } //指针不同时，指数小的先插入 else if(p->b < q->b){ s->a = p->a; s->b = p->b; r->next= s; p = p->next; r = s; } else{ s->a = q->a; s->b = q->b; r->next = s; q = q->next; r = s; } //当一个链表为空时，另一个直接将剩余插入 if (p != NULL){ r->next = p; } if (q != NULL){ r->next = q; } } r->next = NULL; //保证尾结点的后面是空指针 return C; } void showLNode(node L){ //遍历显示链表 node p; p = L->next; while(p!= NULL){ printf("系数为%d",p->a); printf("指数为%d ",p->b); p = p->next; } printf("\n"); } int main(){ node A; initLNode(A); node B; initLNode(B); node C = addLNode(A, B); printf("A:"); showLNode(A); printf("B:"); showLNode(B); printf("C:"); showLNode(C); }
结果演示：
结果与分析：
（1）优点：实现了使用链表对多项式的存储以及加法运算。（2）缺点：代码的表现形式较差，在输入指数时必须从小到大输入。（3）时间复杂度：O（n）(4）空间复杂度：O(n)，取决与多项式的项数。
第三题：Josephus问题
[问题描述]
设有n个人围坐在一个圆桌周围，现从第s个人开始报数，数到第m的人出列，然后从出列的下一个人重新开始报数，数到m的人又出列，如此重复，直到所有的人全部出列为止。Josephus问题是：对于任意给定的n，m，s，求出按出列次序得到的n个人员的顺序表。
[输入]
输入n个人，数字m，开始处s。
[输出]
按出列次序得到的n个人员的顺序表。
[存储结构]
采用链式存储结构
[算法的基本思想]
构建单循环链表：根据人数n，建立不含头节点的n个结点，并给每个节点的数据域赋值为1，2，3依次类推代表人。输出顺序表：第一次为：s + m的结点，后面便可以m次循环直至链表为空。
#include <stdio.h> #include <malloc.h> typedef struct LNode{ int a; struct LNode *next; }LNode, *node; void initLNode(node &L, int n){ //创建循环链表 L = (node)malloc(sizeof(LNode)); //头结点空间申请 int i; node p, q; p = L; p->a = 1; for(i = 1; i < n; i ++){ //结点的插入 q = (node)malloc(sizeof(LNode)); q->a = i + 1; p->next = q; p = q; } p->next = L; } void showOut(node L, int n, int m, int s){ //输出游戏结果 int i; node p, q; p = L; for(i = 0; i < m + s - 3; i++){ //第一次出列的位置 p = p->next; } q = p->next; printf("%d ", q->a); p->next = q->next; free(q); int count = 1; while(1){ //循环遍历 for(i = 0; i < m - 1; i++){ //满足出列位置的运算 p = p->next; } q = p->next; printf("%d ", q->a); p->next = q->next; free(q); count++; if(count == n){ //计数器，结束条件 break; } } } int main(){ int n; int m; int s; printf("请输入人数："); scanf("%d", &n); printf("请输入指定数字："); scanf("%d", &m); printf("请输入开始位置："); scanf("%d", &s); node L; initLNode(L, n); showOut(L, n, m, s); }
结果演示：
结果与分析：
（1）优点利用无头结点的循环链表解决了问题。（2）缺点：代码较为繁琐。（3）时间复杂度：O（mn ）分析：每次都要从1到m对链表经行遍历，一共需要把每个数字都输出即n次。（4）空间复杂度O（n）
心得
1.重新学习了C语言，提高对C语言的结构体认识。
2.通过结构体实现数据结构。
3.对于顺序表而言：可以通过数组的创建简单构造，而对于链表必须使<malloc.h>头文件下的malloc函数去创建结点，在通过结点的指针相连创建链表。
4.在将两个链表组成一个链表时：必须先同时判断两个链表是否为空例如（p != NULL && q != NULL）当一个为空时，可以直接在与不为空的结点相连。
5.对循环链表的建立即使用：令最后一个结点与首源结点相连接，可通过计数的方式判断循环链表是否为空。
