链式结构线性表的实现

链式结构线性表的实现

一、目的：

掌握链表的表示方法，存储结构及其基本操作的实现。

二、要求：

建立一单链表，实现其基本操作：分别使用正位序和逆位序的方法新建一个单链表；完成插入、删除、输出的操作。

三、实验内容

1、设计程序。

2、调试程序，并设计输入数据。

3、修改程序：

如果有时间，请加入其他的基本操作。

四、实验报告要求

写出程序和实验结果，并画出链表变化的示意图。

逆位序：

#include
#include
typedef struct node{
int data;
struct node *next;
}LNode,*LinkList;
LinkList create(int n)
{int i;
LinkList L, p;
L = (LinkList) malloc(sizeof(LNode)); L->next=NULL;
printf("请输入每个结点的元素的值");
for (i=1; i<=n; i++)
{p=(LinkList)malloc(sizeof(LNode));
scanf("%d", &(p->data));
p->next=L->next;
L->next=p;/*插入到头结点之后*/
}
return L;}
void insert(LinkList L, int i,int e)
/*在单链表L的第i个元素前插入数据元素e*/
{LinkList p,s;int j;
p=L;j=0;
while(p&&j{p=p->next;j++;}
if(!p||i<1) {printf("i值不合法");return;}
s=(LinkList)malloc(sizeof(LNode));
s->data=e;
s->next = p->next;
p->next = s;
}
int Delete(LinkList L, int i,int *e)
{LinkList p, q;
int j;
p=L;j=0;
while(p->next&&j
{p=p->next;j++;}
if(!p->next||i<1) {printf("i值不合法");return 0;}
q=p->next;
p->next = q->next;
*e=q->data;
free(q);
return 1;}
void output(LinkList L)
/*输出单链表中结点的元素值*/
{ LinkList p;
p=L->next;
while (p )
{printf("%d ",p->data);
p=p->next;
}
}
void main()
{ LinkList head;int n, x;int i,j;
printf("请输入元素个数");
scanf("%d",&n);
head=create(n);/* 建立有n个元素结点的单链表*/
printf("\n");
output(head);/*调用output函数，输出单链表中结点的元素值*/
printf("\n");
printf("请输入插入的数据元素的值");
scanf("%d",&x);
printf("请输入要在哪个位序之前插入");
scanf("%d",&i);
insert(head, i,x);/*在单链表第i个元素前插入x*/
printf("\n");
output(head);/*输出单链表中结点的元素值*/
printf("请输入要删除的位序");
scanf("%d",&i);
j=Delete(head,i, &x);
printf("\n");
if(j)printf("%d",x);/*删除成功,则输出被删除结点的元素值*/
printf("\n");
printf("最终的链表变成：");
output(head);/*输出单链表中结点的元素值*/

}

正位序：

#include "stdio.h"
#include "stdlib.h"
typedef struct node
{ int data;
struct node *next;
}slink;

slink *creslink(int n)
{
slink *head,*p,*s;
int i;
if(n<1) return NULL;
p=head=(slink *)malloc(sizeof(slink));
printf("请输入每个结点的元素的值");
for(i=1;i<=n;i++)
{ s=(slink *)malloc(sizeof(slink));
scanf("%d",&(s->data));
p->next=s;
p=s;
}
p->next=NULL;
return head;
}

int Delete(slink *head,int i, int *e)
{slink *p,*q;
int j;
if (i<1)return 0;
p=head;j=0;
while(p->next!=NULL && j{p=p->next;j++;}
if(p->next==NULL)return 0;
q=p->next;
p->next=q->next;
*e=q->data;
free(q);
return 1;
}

int insert(slink *head,int i, int x)
{slink *p,*q;
int j;
if (i<1)return 0;
p=head;j=0;
while(p!=NULL && j{p=p->next;j++;}
if(p==NULL)return 0;
q=(slink *)malloc(sizeof(slink));
q->data=x;
q->next=p->next;
p->next=q;
return 1;
}

void printlist(slink *head)
{slink *p;
p=head->next;
while(p!=NULL)
{printf("%4d",p->data);
p=p->next;
}
printf("\n");
}

void main()
{ slink *head;
int n,x,i,j;
printf("请输入元素个数");
scanf("%d",&n);
head=creslink(n);
printf("\n");
printlist(head);
printf("\n");
printf("请输入插入的数据元素的值");
scanf("%d",&x);
printf("请输入要在哪个位序之前插入");
scanf("%d",&i);
insert(head, i,x);/*在单链表第i个元素前插入x*/
printf("\n");
printlist(head);/*输出单链表中结点的元素值*/
printf("请输入删除的数据元素的位序");
scanf("%d",&i);
j=Delete(head,i, &x);
printf("\n");
if(j)printf("%d",x);/*删除成功,则输出被删除结点的元素值*/
printf("\n");
printf("最终的链表变成：");
printlist(head);/*输出单链表中结点的元素值*/
}