数据结构第三周 ：（单链表排序 + 多项式相加 + 静态链表）
目录
- 单链表数据排序
- 多项式相加
- 静态链表
单链表数据排序
【问题描述】用单链表存储数据，实现对结点整体的从小到大的排序。
【注意】可采用翻转课堂上讲解的插入、冒泡排序中的一种，或者采用选择排序。每组成员一共需要实现其中的两种排序：插入和选择排序、或者冒泡和选择排序。
【输入形式】待排序的数据，以0作为结束。
【输出形式】排序后的数据
【样例输入】2 4 3 1 5 0
【样例输出】1 2 3 4 5
#include
#include
typedef struct Node{int data;struct Node* next;
}Linklist,*Link;
void InitLink(Link* L){*L = (Linklist*)malloc(sizeof(Linklist));(*L)->next = NULL;
}
void CreatLink(Linklist* L){while(1){int num = 0;scanf("%d",&num);if(num == 0){break;}else{Linklist* p = NULL;p = (Linklist*)malloc(sizeof(Linklist));p->data = num;if(L->next == NULL){L->next = p;p->next = NULL;}else{Linklist* n = L;Linklist* m = L->next;if(p->data <= m->data){L->next = p;p->next = m;}else{while(m->next != NULL && m->data < p->data){n = n->next;m = m->next;}if(m->data > p->data){n->next = p;p->next = m;}else{m->next = p;p->next = NULL;}}}}}
}
void display(Linklist* L){Linklist* p = L->next;while(p != NULL){printf("%d ",p->data);p = p->next;}
}
int main(){Linklist* L = NULL;InitLink(&L);CreatLink(L);display(L);return 0;
}
多项式相加
【问题描述】编写一个程序用单链表存储多项式，并实现两个一元多项式A与B相加的函数。A，B刚开始是无序的，A与B之和按降序排列。例如：
多项式A: 1.2X^0 2.5X^1 3.2X^3 -2.5X^5
多项式B: -1.2X^0 2.5X^1 3.2X^3 2.5X^5 5.4X^10
多项式A与B之和：5.4X^10 6.4X^3 5X^1
【输入形式】第一行第一个数据n代表多项式的总项数，后面的2*n个数据，每一对代表对应的某一项的系数和指数，第二行类似，第三行的数据x要查询第几项
【输出形式】多项式中某一项的系数与指数，系数保留一位小数
【输入样例】
4 1.2 0 2.5 1 3.2 3 -2.5 5
5 -1.2 0 2.5 1 3.2 3 2.5 5 5.4 10
2
【输出样例】
6.4 3
【样例说明】
第一个多项式的系数与指数对，以空格隔开
第二个多项式的系数与指数对，以空格隔开
输出第２项的系数与指数，系数与指数间用空格隔开，系数保留一位小数
【评分标准】必须用链表实现
#include
#include
typedef struct Polynode{float coef;int exp;struct Polynode* next;
}Polynode,*Polylist;
void InitList(Polylist* L){*L = (Polylist)malloc(sizeof(Polynode));(*L)->next = NULL;
}
void PolyCreat(Polynode* L){int f;scanf("%d",&f);Polynode* pr = L;while(f--){float c;int e;scanf("%f %d",&c,&e);Polynode* p = NULL;p = (Polylist)malloc(sizeof(Polynode));p->coef = c;p->exp = e;pr->next = p;pr = p;pr->next = NULL;}
}
void PolyAdd(Polynode* La,Polynode* Lb){Polynode* p = La->next;Polynode* q = Lb->next;Polynode* t = La;Polynode* temp = NULL;while(p != NULL && q != NULL){if(p->exp < q->exp){t->next= p;t = p;p = p->next;t->next = NULL;}else if(p->exp == q->exp){float sum = p->coef + q->coef;if(sum == 0.0){temp = p;p = p->next;free(temp);temp = q;q = q->next;free(temp);}else{p->coef = sum;t->next = p;t = p;p = p->next;temp = q;q = q->next;free(temp);t->next = NULL;}}else{t->next = q;t = q;q = q->next;t->next = NULL;}}if(p != NULL){t->next = p;}else{t->next = q;}
}
void Reverselist(Polylist L){Polynode* p = L->next;L->next = NULL;while(p != NULL){Polynode* q = p->next;p->next = L->next;L->next = p;p = q;}
}void Sortlist(Polylist p_head)
{Polynode *pb, *pf, temp;pf = p_head;while(pf->next != NULL) {//以pf指向的节点为基准节点pb = pf->next;//pb从基准点的下一个节点开始while(pb != NULL) {if(pf->exp > pb->exp) {temp = *pf;*pf = *pb;*pb = temp;temp.next = pf->next;pf->next = pb->next;pb->next = temp.next;}pb = pb->next;}pf = pf->next;}return ;
}
void Display(Polynode* L,int num){Polynode* p = L;int i = 0;while(i != num){i++;p = p->next;}printf("%0.1f %d",p->coef,p->exp);
}
int main(){Polylist La,Lb;int num;InitList(&La);InitList(&Lb);PolyCreat(La);PolyCreat(Lb);PolyAdd(La,Lb);Sortlist(La);Reverselist(La);scanf("%d",&num);Display(La,num);return 0;
}
静态链表
【问题描述】
静态链表是使用顺序存储结构来实现的链表。现在，我们就来实现一下这个静态链表。实际上静态链表与一般含有指针的链表没有太大的差别，只是静态链表的结点存放的空间不是在使用时临时分配的，而是在一开始就分配了固定的一些，一般是用数组。同时一般的链表使用指针来指向下一个结点而在静态链表中则使用数组下标了。
【输入形式】
静态链表的存储空间（图2中的space）始终只有11个节点，起始为空表。insert a e代表在第a个姓氏前插入姓氏e；delete a代表删除第a个姓氏；search e代表查找姓氏e的位置；show代表输出静态链表存储空间的状态。输入保证操作都合法。
【输出形式】
只遇到search和show时才输出。当遇到search时输出姓氏e在space中的位置；当遇到show时输出这11个结点的状态。姓氏占8个字符而数字占2个字符，姓氏左对齐。每个指令输出后面跟着含有20个星号的行。
【样例输入】
show
insert 1 ZHAO
show
insert 2 QIAN
show
insert 3 SUN
show
insert 4 LI
insert 5 ZHOU
insert 6 WU
insert 7 ZHENG
insert 8 WANG
show
insert 1 ZHANG
show
search LI
show
【样例输出】
2
0
3
4
5
6
7
8
9
10
0
---------
3
2
ZHAO 0
4
5
6
7
8
9
10
0
---------
4
2
ZHAO 3
QIAN 0
5
6
7
8
9
10
0
---------
5
2
ZHAO 3
QIAN 4
SUN 0
6
7
8
9
10
0
---------
10
2
ZHAO 3
QIAN 4
SUN 5
LI 6
ZHOU 7
WU 8
ZHENG 9
WANG 0
0
---------
0
10
ZHAO 3
QIAN 4
SUN 5
LI 6
ZHOU 7
WU 8
ZHENG 9
WANG 0
ZHANG 2
---------
5
---------
0
10
ZHAO 3
QIAN 4
SUN 5
LI 6
ZHOU 7
WU 8
ZHENG 9
WANG 0
ZHANG 2
【提示】
1、怎样将字符串类型定义为ElemType呢？形如typedef int num一样，数组或者指针可以放在定义的类型名后面，例如将具有8个字符的姓氏定义为ElemType可以这样定义：typedef char ElemType[8]。
2、题目和书中给的算法描述还缺少静态链表的插入、删除以及显示，都需要自己写。
3、要求每个指令输出后跟一个空行，别忘了。
4、姓氏占8个字符，数字占2个字符，姓氏左对齐，可以这样输出printf(“%-8s%2d”);对于指令search也要输出占2个字符的数字。
5、静态链表初始化时将所有内存设为空，可以在InitSpace_SL中使用下面的方法：
memset(space, 0 ,sizeof(space));
【总结】
静态链表与一般链表极为相似：使用数组来模拟内存，使用数组下标来模拟内存中的地址。
#include
#include
#include
#define MAXSIZE 11
using namespace std;
typedef char ElemType[8];
typedef struct{ElemType data;int cur;
}NodeType;
typedef struct{int elem;int length;int listSize;
}SLinkList;
NodeType space[MAXSIZE];
SLinkList S;
void InitSpace_SL(){memset(space,0,sizeof(space));for(int i=0;iint i=space[1].cur;int j=0;while(j<11){if(space[j].data){printf("%-8s%2d",space[j].data,space[j].cur);cout<printf("%2d",space[j].cur);cout<int i=space[0].cur;return i;
}
void Free_SL(int k){space[k].cur=space[0].cur;space[0].cur=k;
}
void Delete(int a){int p=1,s;for(int i=1;ip=space[p].cur;}s=space[p].cur;space[p].cur=space[s].cur;Free_SL(s);
}void Search(ElemType e ){int i=space[1].cur;while(i&&strcmp(space[i].data,e)){i=space[i].cur;}printf("%2d",i);cout<strcpy(space[k].data,data1);int K,Q,O;O=space[0].cur;Q=space[q].cur;K=space[k].cur;space[k].cur=Q;space[q].cur=O;space[0].cur=K;
}
int main(){InitSpace_SL();char st[20];char ts[20];while(cin>>st){if(strcmp(st,"show")==0){ShowSList();}else if(strcmp(st,"insert")==0){int q;cin>>q>>ts;int k=Malloc_SL();Insert(k,ts,q);}else if(strcmp(st,"search")==0){cin>>ts;Search(ts);}else if(strcmp(st,"delete")==0){int a;cin>>a;Delete(a);}}return 0;
}
下一篇：一文弄懂 ZooKeeper