任课教师：孙树森
《数据结构与算法》
（2012-2013学年第2学期）
实
验
报
告
学号：2011329700214
姓名：周咪咪
班级：11数媒2班
实验1：链表的建立与操作
一、实验目的：
掌握链表数据结构的建立及操作；
二、实验重点：
利用链表的原空间进行链表的反转；
三、实验内容：
设计一个将输入数据建立成链表、并依次输出链表数据、利用原空间把链表反转的程序。
四、实验步骤：
1．掌握链表的数据结构；
2．建立空链表；
3．用头插法向链表插入数据，实验数据:
验证数据：20，20，17，16，15，15，11，10，8，7，7，5，4；
4．依次输出链表中的数据；
5．利用链表原空间进行对链表进行反转；
6．依次输出反转后的链表数据，以判断反转操作的正确性，注意反转后，链表的第一个和最后一个元素是否正确；
实验提示:实验1链表。PPT；
7，进阶要求：完成P40 3.6.1的功能；
五、程序源码：
方法1：依次反转
#include
#include
typedef struct Node{ //定义单链表结构，Node为结点名
int data;
struct Node *next;
}Node,*linklist;
//头插法,输入顺序为反
void Input(linklist *L,int n)
{
linklist p;
int i;
*L=(linklist)malloc(sizeof(Node)); (*L)->next=NULL;
for(i=0;i{
p=(linklist)malloc(sizeof(Node)); scanf("%d",&p->data);
p->next=(*L)->next;
(*L)->next=p;
}
}
//在屏幕上输出链表
void Output(Node *L,int n)
{ int i;
for(i=0;i{
L=L->next;
printf("%d->",L->data);
}
L=L->next;
printf("%d",L->data);
printf("\n");
}
void reverse(linklist L,int n)
{
linklist p,r;
p=L->next;
int i;
for(i=1;i<=n;i++)
{
r=p->next;
p->next=L->next;
L->next=p;
p=r;
}
}
void main()
{
int n;
Node *L;
printf("输入元素个数:");
scanf("%d",&n);
Input(&L,n);
reverse(L,n);
printf("链表原顺序为:\n"); Output(L,n);
reverse(L,n);
printf("链表逆置后的顺序为:\n");
Output(L,n);
system("pause");
}
方法2：指针反向
#include
#include
typedef struct Node{ //定义单链表结构，Node为结点名 int data;
struct Node *next;
}Node,*linklist;
//头插法,输入顺序为反
void Input(linklist *L,int n)
{
linklist p;
int i;
*L=(linklist)malloc(sizeof(Node));
(*L)->next=NULL;
for(i=0;i{
p=(linklist)malloc(sizeof(Node));
scanf("%d",&p->data);
p->next=(*L)->next;
(*L)->next=p;
}
}
//在屏幕上输出链表
void Output(Node *L,int n)
{ int i;
for(i=0;iL=L->next;
printf("%d->",L->data);
}
L=L->next;
printf("%d",L->data);
printf("\n");
}
void reverse(linklist L,int n) {
linklist p,q,r,k;
int i,j,m;
k=L->next;
r=k;//暂存
for(i=1;ik=k->next;//k指针后移至最后
}
L->next=k;
j=n-1;
for(i=1;iq=r;
for(m=1;m{q=q->next;}
p=q->next;
p->next=q;
j--;
}
q=r;
p=q->next;
p->next=q;
