实验一 线性表
一．目的与要求
本次实习的主要目的是为了使学生熟练掌握线性表的基本操作在顺序存储结构和链式存储结构上的实现，提高分析和解决问题的能力。要求仔细阅读并理解下列例题，上机通过，并观察其结果，然后完成后面的实习题。
二．例题
[问题描述]
用链表形式存储一个字符串，插入、删除某个字符，最后按正序、逆序两种方式输出字符串。 [输入]
初始字符串，插入位置，插入字符，删除字符。 [输出]
已建立链表（字符串），插入字符后链表，删除字符后链表，逆转后链表。 [存储结构]
采用链式存储结构 [算法的基本思想]
建立链表：当读入字符不是结束符时，给结点分配存储空间，写数据域，将新结点插到表尾；插入字符：根据读入的字符在链表中找插入位置，将新结点插入到该位置之前；删除字符：根据读入的删除字符在链表中找到被删结点后，将其从链表中删除；链表逆转：从链表的第一个结点开始对所有结点处理，将每个结点的前驱变为它的后继；打印链表：从链表的第一个结点开始，依次打印各个结点的数据域。 [参考源程序] #define NULL 0
typedef struct node{ char a;
struct node *link; }node,*nodelink;
void readlink(nodelink head){ nodelink p,q; char c; p=head;
printf(\"Input a linktable(a string):\"); scanf(\"%c\
if (c=='\\n') printf(\"This string is empty。\"); while(c!='\\n'){
q=(nodelink)malloc(sizeof(node)); q->a=c; p->link=q; p=q;
scanf(\"%c\ }
p->link=NULL; }
void writelink(nodelink head){ nodelink q;
if (head->link==NULL) printf(\" This link is empty。\\n\"); for(q=head->link;q;q=q->link) printf(\"%c\ printf(\"\\n\");
}
int insert(nodelink head,char k1,char k2){ nodelink p,q; p=head->link;
while(p->a!=k1&&p) p=p->link; if(p){
q=(nodelink)malloc(sizeof(node)); q->a=k2;
q->link=p->link; p->link=q; return 1; } else {
printf(\"There is no %c\\n\ return 0; } }
int delete(nodelink head,char k){ nodelink p,q; q=head;
p=head->link;
while(((p->a)!=k)&&p){ q=q->link; p=p->link; } if(p){
q->link=p->link; return 1; } else{
printf(\"There is no %c\\n\ return 0; } }
void opside(nodelink head){ nodelink p,q; p=head->link; while(p->link){ q=p->link;
p->link=q->link; q->link=head->link; head->link=q; } }
main() {
char k1,k2,k3; nodelink head;
head=(nodelink)malloc(sizeof(node)); head->link=NULL;
readlink(head);
if (head->link!=NULL){
printf(\"Build link is :\"); writelink(head); } if (head->link!=NULL){
printf(\"Please input a char you want to insert after:\"); k1=getch();
printf(\"%c\\n\
printf(\"Please input a char you want to insert:\"); k2=getch();
printf(\"%c\\n\
if (insert(head,k1,k2)) {
printf(\"After %c insert %c,link is:\ writelink(head); }
printf(\"Please input a char you want to delete:\"); k3=getch();
printf(\"%c\\n\ if (delete(head,k3))
{ printf(\"after delete %c,link is:\ writelink(head); }
if (head->link!=NULL){
printf(\"Opsite result is :\"); opside(head); writelink(head); free(head); } } }
[运行情况]
Input a linktable(a string):lopui↙ Build link is :lopui
Please input a char you want to insert after:p↙ Please input a char you want to insert:y↙ After p insert y,link is:lopyui
Please input a char you want to delete:p↙ after delete p,link is:loyui Opsite result is :iuyol
三．实习题
1．设顺序表A中的数据元素递增有序，试写一程序，将x插入到顺序表的适当位置上，使该表仍然有序。
2．用单链表ha 存储多项式A（x ）=a0+a1x1+a2x2+…+anxn(其中aI为非零系数)，用单链表hb 存储多项式B（x ）=b0+b1x1+b2x2+…+bmxm(其中bj为非零系数)，要求计算C（x ）= A（x ）+B（x ），结果存到单链表hc中。试写出程序。
3．设有n个人围坐在一个圆桌周围，现从第s个人开始报数，数到第m的人出列，然后从出列的下一个人重新开始报数，数到m的人又出列，如此重复，直到所有的人全部出列为止。Josephus问题是：对于任意给定的n，m，s，求出按出列次序得到的n个人员的顺序表。
