数据结构 线性表实验报告

实 验 报 告

实验名称：线性表

实验目的：（1）、熟悉C语言的上机环境，进一步掌握C语言的结构特点；

（2）、掌握线性表的链式储存结构——单链表的定义及C语言实现； （3）、掌握线性表在序表中的各种基本操作；

实验步骤：（1）、建立含N个数据的顺序表并输出该表中各元素的值及顺序表的长度；

（2）、利用前面的实验建立一个顺序表，然后在第i个位置插入元素； （3）、建立一个带头节点的单链表，节点的值域整型数据。要求将用户输入的

数据按尾插入法来建立相应单链表

实验内容：1. 若干城市的信息存入一个带头结点的单链表，结点中的城市信息包括城市

名，城市的位置坐标要求:

(1) 给定一个城市名，返回其位置坐标。

(2) 给定一个位置坐标P和一个距离D，返回所有距P的距离小于等于D的城市。 2约瑟夫环问题。

约瑟夫问题的一种描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个整数作为报数上限值m,从第一个人开始顺时针自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。求出出列顺序。

实验记录：（源代码及执行过程）

第一题：#include #include #include #define max 10 typedef struct Node {float point_x; float point_y;

struct Node *Next; char Nam[max]; }Node;

Node *head,*L,*rear;

int searchpoint(Node *head) {char name[max];

printf(\"请输入求坐标的城市名:\"); scanf(\"%s\ L=head->Next;

while(strcmp(L->Nam,name)!=0&&L->Next!=NULL)

{ L=L->Next; }

if(strcmp(L->Nam,name)==0) {

printf(\"坐标:(%-10.2f %-10.2f)\\n\ }

else if(L->Next==NULL&&strcmp(L->Nam,name)!=0) {

printf(\"不存在此城市!\\n\"); } }

int searchname(Node *head) {

float d,d1,x1,y1; float x,y;

printf(\"请输入距离:\"); scanf(\"%f\

printf(\"请输入位置坐标p(x y):\"); scanf(\"%f %f\ L=head->Next;

while(L->Next!=NULL) {

x1=L->point_x; y1=L->point_y;

d1=(x-x1)*(x-x1)+(y-y1)*(y-y1); if(d<=d1) {

printf(\"%s \ }

L=L->Next; }

x1=L->point_x; y1=L->point_y;

d1=(x-x1)*(x-x1)+(y-y1)*(y-y1); if(d<=d1) {

printf(\"%s \ }

printf(\"\\n\"); }

int insert(Node *rear) {

char name[max]; float x,y;

printf(\"输入要要插入城市名:\"); scanf(\"%s\

printf(\"请输入坐标(x y):\"); scanf(\"%f %f\

L=(Node*)malloc(sizeof(Node)); strcpy(L->Nam,name); L->point_x=x; L->point_y=y; L->Next=NULL; rear->Next=L; }

int updata(Node *head) {

L=head->Next;

while(L->Next!=NULL) {

printf(\"%-10s %-10.2f %-10.2f\\n\ L=L->Next; }

printf(\"%-10s %-10.2f %-10.2f\\n\ }

int delet(Node *head) {

char name[max];

printf(\"请输入要删除城市名:\"); scanf(\"%s\

L=head->Next;

while(strcmp(L->Nam,name)!=0||L->Next!=NULL) {

L=rear; L=L->Next; }

if(strcmp(L->Nam,name)==0&&L->Next!=NULL) {

rear->Next->Next=L->Next; free(L);

printf(\" 删除成功!\"); return 1; }

if(strcmp(L->Nam,name)==0&&L->Next==NULL) {

rear->Next=NULL; free(L);

printf(\" 删除成功!\"); return 1; }

printf(\" 无此城市 !\"); return 0; } int main() {

float x,y; int i=1;

char name[max],ch;

//建立链表

head=(Node*)malloc(sizeof(Node)); rear=head;

printf(\" 城市名输入exit结束\\n\"); printf(\"请输入城市名:\"); gets(name);

printf(\"请输入坐标(x y):\"); scanf(\"%f %f\

while(strcmp(name,\"exit\")!=0) { L=(Node*)malloc(sizeof(Node)); L->point_x=x; L->point_y=y; strcpy(L->Nam,name); rear->Next=L; rear=L; printf(\"请输入城市名:\"); scanf(\"%s\

if(strcmp(name,\"exit\")!=0) {

printf(\"请输入坐标(x y):\"); scanf(\"%f %f\ } }

rear->Next=NULL L=head->Next;

while(L->Next!=NULL) {

printf(\"%-10s %-10.2f %-10.2f\\n\ L=L->Next;

}

printf(\"%-10s %-10.2f %-10.2f\\n\ while(i) {

printf(\"1:返回坐标. 2:返回城市名. 3:插入. 4:删除. 0:退出\\n\"); scanf(\"%d\ switch(i) {case 0: {

i=0; break; } case 1: {

searchpoint(head); break; } case 2: {

searchname(head);

break; } case 3: {

insert(rear); updata(head);

break; } case 4: {

delet(head); printf(\"\\n\"); updata(head);

break; } } }

system(\"pause\"); }

第二题..

#include #include #include typedef struct Node

{

int Num; int Code;

struct Node *Next; }Node;

int main() {

Node *head,*rear,*L; int i=1,j=0,k=1,m;

printf(\"输入0退出\\n\");

//建立链表

head=(Node*)malloc(sizeof(Node)); rear=head;

printf(\"请输入密码:\"); scanf(\"%d\ while(m!=0) { L=(Node*)malloc(sizeof(Node)); L->Num=i; L->Code=m; rear->Next=L; rear=L; i++; scanf(\"%d\ } i--; printf(\"\\n共%d人\\n\ L->Next=head->Next;

printf(\"请输入初始人密码:\"); scanf(\"%d\

while(jwhile(kNext; k++; } k=1;

rear=L->Next;

printf(\"第%d人出列.\\n\ m=rear->Code; L->Next=L->Next->Next; j++; }

system(\"pause\"); }