太原理工大学数据结构 实验一

本次实习的主要目的是为了熟练掌握线性表的基本操作在顺序存储结构和链式存储结构上的实现，提高分析和解决问题的能力。要求仔细阅读并理解例题，上机通过，并观察其结果，然后完成后面的实习题。

1. [问题]:设顺序表A中的数据元素递增有序，试写一程序，将x插入到顺序表的适当位置上，使该表仍然有序。

[输入]:初始顺序表字符，插入字符。

[输出]：插入字符后的顺序表。

[存储结构]:采用顺序存储结构。

[算法的基本思想]:1.建立顺序表：规定一个顺序表初始大小，依次从小到大输入数据将

顺序表填满。2.插入数据：将数据从第一个开始对比，找到合适位置后，此位置之后的元素整体向后移动一位，从最后一位开始往下一位赋值。3.打印顺序表：从顺序表第一位开始依次打印。

2. [问题]:设有n个人围坐在一个圆桌周围，现从第s个人开始报数，数到第m的人出列，然后从出列的下一个人重新开始报数，数到m的人又出列，如此重复，直到所有的人全部出列为止。问题是：对于任意给定的n，m，s，求出按出列次序得到的n个人员的顺序表。

[输入]:人数n，依次输入字符，数字s和m。

[输出:依次输出出列链表元素。

[存储结构]:采用链式存储结构。

[算法的基本思想]:1.建立链表：规定一个链表长度，依次输入数据将链表填满。2.调出并打印数据：先将指针移动到s-1位置，再用递归的方法实现让数据出列的同时，打印出此出列数据。

使用的计算机：惠普242G1笔记本电脑，酷睿I5处理器，Windows7旗舰版 位系统，

VC6.0编译器

1.

#include

#include

#define LIST_INIT_SIZE 10  //初始分配空间大小

#define LISTINCREMENT 2    //每次增加分配的空间

#define OVERFLOW -2

#define OK 1

#define ERROR 0

                          //**定义线性表 将元素类型定义为整形int

typedef struct {

    int *elem;

    int length;

    int listsize;

}SqList,*QSqList;

                           //**创造一个空的线性表

int InitList_Sq(SqList *L){

L->elem=(int *)malloc(LIST_INIT_SIZE*sizeof(int));

if(!L->elem) exit(OVERFLOW);

L->length=0;

L->listsize=LIST_INIT_SIZE;

    return OK;

}//InitList_Sq

                           //**得到第i个元素并且返回这个值

int GetListElem(SqList *L,int i,int *q){

if(i<1||i>(L->length)) exit(ERROR);

*q=L->elem[i-1];

    return OK;

}

                           //**在i位置插入元素e

int ListInsert_Sq(SqList *L,int i,int e){

    int *q,*p;

if(i<1||i>L->length+1) return ERROR;

    if(L->length>=L->listsize){         //**检测空间是否已满

        int *newbase;  

        newbase=(int *)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(int));

        if(!newbase) exit(OVERFLOW);

        L->elem=newbase;

        L->listsize+=LISTINCREMENT;

    }

q=&(L->elem[i-1]);

for(p=&(L->elem[L->length-1]);p>=q;--p)

        *(p+1)=*p;

    *q=e;

++L->length;

    return OK;

}//ListInsert_Sq

                           //**按顺序插入操作

int InserOrderList(SqList *L,int e){

    int i;

    if((L->length)>=(L->listsize)){  //检查储蓄空间是否已满

        int *newbase;

        newbase=(int *)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(int));

        if(!newbase) exit(OVERFLOW);

        L->elem=newbase;

        L->listsize+=LISTINCREMENT;

    }

for(i=L->length;i>0&&e<(L->elem[i-1]);i--)

        L->elem[i]=L->elem[i-1];

L->elem[i]=e;

L->length++;

    return OK;

}

                                  //**主函数

void main(){

    int i,x,e;

    int *y=&x;

    SqList Sq;

    QSqList sq=&Sq;

    InitList_Sq(sq);

    printf("请按从小到大的顺序输入10个数字：");  //**输入10个数

    for(i=1;i<=10;i++){

        scanf("%d",&x);

        ListInsert_Sq(sq,i,x);

    }

    printf("请输入要插入的数字：");

    scanf("%d",&e);

    InserOrderList(sq,e);

    printf("输出排序后的元素：");          

    for(i=1;i<=Sq.length;i++){      //依次输出每个元素

        GetListElem(sq,i,y);

        printf("%d  ",x);

    }

    printf("\\n");

    free(Sq.elem);

}

2.

#include

#include

#define NULL 0

                           //***线性链表结构体定义 元素定义为字符char

typedef struct LNode{

    char name;

    struct LNode *next;

}LNode,*LinkList;

                           //***依次出列并打印

void writemember(LinkList L,int m,int i){

if(i>0){

        int j=1;

        while(j            L=L->next;

            j++;

        }

        printf("%c >> ",L->next->name,i);

        L->next=L->next->next;

        writemember(L,m,--i);       //***递归调用writemember函数

    }

}

                           //***在第i个位置插入元素e

int ListInsert(LinkList head,int i,char e){

    LinkList p=head,s;

    int j=0;

while(p&&j        p=p->next;

        j++;

    }

if(!p||j>i-1) return 0;

    s=(LinkList)malloc(sizeof(LNode));

    s->name=e;s->next=head->next;     //将尾节点next指向头节点 建立循环

    p->next=s;

    return 1;

}//ListInsert_l

                                //主函数 任意给定的n，m，s，

                                //求出按出列次序得到的n个人员的顺序表

void main(){

    int n,m,s,i;

    char x;

    LinkList head,L;

    head=(LinkList)malloc(sizeof(LNode));  //建立表头

    if(!head) printf("分配错误");

    head->next=NULL;

    printf("请输入总人数n:");

    scanf("%d",&n);

    getchar();                               //用getchar()来吸收输入缓冲区的回车符

    printf("请分别输入每个人的名字（单个字母）\n");

    for(i=1;i<=n;i++){

        printf("第%d位:",i);

        scanf("%c",&x);

        getchar();

        ListInsert(head,i,x);

    }    printf("现从第s个人开始报数，数到第m的人出列\n请分别输入s和m:");

    scanf("%d,%d",&s,&m);

    L=head;

    i=1;

    while(i        L=L->next;

        ++i;

    }

    printf("输出顺序为:");

    writemember(L,m,n);

    printf("end\\n");

    free(head);

}

1.

2.

 我认为第一个程序较第二个程序而言，更体现出了结构化程序设计的思路，可移植性更强，但是但是由于采用的是顺序存储的形式，导致算法的时间性能和空间性能不是很好，而且健壮性不是很好,而且第二个程序较第一个程序所占空间更少。第一个程序的时间复杂度T(n)=O(n)，并且两个程序的函数都为原地工作，所占空间小。第二个程序还用了递归的算法，效率较高。

通过这次的实验，大大的提高了自己的动手能力，亲自编写程序，虽然中间发生了一些问题，比如我因为输入时的一个语句“%d”写成了“%c”，导致我找错误花了2个小时，但是找到后体会到了学有所成的乐趣。如果改进，我会简化其中的一些内容，尽量减少变量，减少所占空间。以后我要更加严谨和勤奋的学习这门课程。