数据结构_实验报告1顺序表

南方医科大学生物医学工程学院__电子信息工程___系

数据结构实验报告

学专业姓名 王浩文 113200880200010 08电子信息工程 号 年级 内单元 第2章 线性表 日期 2010-5-21 容 实验题目 实验一 线性结构（综合性实验 3学时） 实验目的 本次实习的主要目的在于熟悉线性表的基本运算在两种存储结构上的实现，其中以熟悉各种链表的操作为侧重点。通过本次实习还可复习高级语言的使用方法。 一、必做题： 二、选做题： [问题描述] 约瑟夫（Joeph）问题的一种描述是：编号为1,2,…,n的n个人按顺时实验内容 针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将 他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 [基本要求] 利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。 [测试数据] m的初值为20；密码：3，1，7，2，4，8，4（正确的结果应为6，1，4，7，2，3，5）。 实验要求及一、抄写自己所选择的题目。 二、写出算法设计思路。 讨论 三、编写代码，调试运行，实现题目要求（提示：考虑到插入和删除的位置是否超出范围等可能出现的异常问题）。 四、写出算法设计、编程和调试运行的体会。 （本次实验的要求是否达到，有何问题，是怎么解决的） 一、抄写自己所选择的题目。

1

南方医科大学生物医学工程学院__电子信息工程___系

数据结构实验报告

1、已知一顺序表A，其元素非递减有序排列，编写一个算法，删除顺序表中值相同多余的元素（相同值保留一个）。

2、已知带头结点的单链表L中的节点是按整数值递增排序的，试写一算法，将值为x的节点插入到表L中，使得表L仍然有序。分析算法的时间复杂度。

二、写出算法设计思路。

1．建立一个顺序表用于存储一组非递减排序的整形数据，对顺序表中的每个元素与其下一个元素进行比较操作。用指针记录当前所比较的元素，如果相等则对当前指针所指向的元素进行删除操作，并将它后面的数据前移，再与下一个元素比较，如果还相等就继续删除操作，否则指向下个元素，再比较直至无重复的元素。

2. 建立一个带头节点的单链表，其节点按整数值递增排序。创建一个新的节点，并由键盘输入节点的值。将其与链表中原有的节点（头节点不参与比较）按顺序作比较，并用指针指向当前的位置，若不大于当前节点，则在当前位置这前作插入操作，否则在最后作插入操作。

三、编写代码，调试运行，实现题目要求（提示：考虑到插入和删除的位置是否超出范围等可能出现的异常问题）。 解1．法I:

#include \#include \#define SIZE 10 main()

{ int SqList_A[SIZE]={23,3,45,65,23,44,5,7,89,0};

int i,j,n,m,l=SIZE;

for(i=0;i

if(SqList_A[i]==SqList_A[j]) if(i!=j) {n=i;m=i+1;

for(;m

SqList_A[n]=SqList_A[m]; l=l-1; }

for(i=0;i

法II：

#include \#include \#define SIZE 18 #define ERROR 0 #define OK 1

int length; /* 定义宏观变量*/ typedef int status; typedef struct{

2

南方医科大学生物医学工程学院__电子信息工程___系

数据结构实验报告

int *elem; int length;

int listsize;} SqList;

status ListDelete(SqList *L)

{ /*删除顺序表L中值相同多余的元素（相同值保留一个）*/ int i=0,j,n=0; SqList *p=L;

if(!p) return ERROR; while(ilength)

{if(*(p->elem+i)==*(p->elem+i+1)) {/*删除相同多余的元素*/

for(j=i;jlength;j++) *(p->elem+j)=*(p->elem+j+1); n++;

p->length--;}

if(!(*(p->elem+i)==*(p->elem+i+1))) /*判断第i个数是否任和下一个数相同*/ i++;}

length=SIZE-n; return n;}

main()

{int a[SIZE]={1,2,2,5,6,7,7,12,13,13,13,18,19,20,21,24,24,39},t; int n,m; SqList A; A.elem=a;

for(n=0;n

if(!t)printf(\ else {

printf(\ for(n=0;n

#include \#include \#define SIZE 10 #define ERROR 0

3

南方医科大学生物医学工程学院__电子信息工程___系

数据结构实验报告

#define NULL 0 #define OK 1

int a[SIZE]={1,3,5,8,10,12,14,17,19,26},i; typedef int status; typedef struct nod{ int data;

struct nod *next;} node;

status CreatList(node *L)

{/*建立一个带头结点的节点按整数值递增排序的单链表L*/ node *p,*h=NULL;

h=p=(node *)malloc(sizeof(node));

if(!p) return ERROR; /*节点创建失败*/ p->data=a[i];

for(i=1;inext=(node *)malloc(sizeof(node)); p=p->next; p->data=a[i];} p->next=NULL; L->next=h; return OK;}

status ListInsert(node *L,int x) {int i,k;

for(i=0;i=a[i]&&x=k;i--) a[i+1]=a[i]; a[k]=x;} }

main()

{node *L,*p; int t,x,i,k;

printf(\ scanf(\

printf(\ for(i=0;i

printf(\ L=(node *)malloc(sizeof(node)); if(!L){ printf(\ t=CreatList(L); /*创建链表*/ if(!t){ printf(\ ListInsert(L,x);

for(i=0;i

4

南方医科大学生物医学工程学院__电子信息工程___系

数据结构实验报告

getch(); }

时间复杂度为：O(n)

四、 写出算法设计、编程和调试运行的体会。

经过上学期对C语言半年的学习可以说掌握的基本可以，但是三天不上手就会手生。现在再次运用时尽忘记了许多，甚至不知如何下手，只得再次翻阅C语言的课本。不过通过这次实验的复习，我在学习数据结构的同时也对C语言进行了一次复习回顾，收获颇丰。 但是也不乏出现一些问题，比如：

1. 如何在调用函数中返回两个以上的返回值？

2. 头结点如何体现，怎样体现它的作用？希望老师可以帮助解决这些问题，谢谢！

5