数据结构实验:线性表的顺序表示和链式表示及插入、删除、查找运算

这是我的第一次上机实验课的内容来呢!
#include
#include
#include

struct list //结点类型
{ int data;
struct list *next;
};

struct list *head;//声明结点指针
int static length;//声明表长变量

struct list *creat_n()//创建有n个元素的链表
{
struct list *q,*p,*head=NULL;

printf("\n输入你所要创建的结点数: ");
scanf("%d",&length);
head=p=(list*)malloc(sizeof(list)); //创建一个新结点并用头指针指向它
printf("输入该结点的值: ");
scanf("%d", &p->data);
p->next=NULL;
for(int i=length-1;i>=1;i--)
{
q=p;
p=(list*)malloc(sizeof(list)); //创建新结点
printf("输入该结点的值: ");
scanf("%d", &p->data);
q->next=p;

}
printf("输入完毕\n\n");
p->next=NULL;

return head;
}

struct list * output()//输出表长与结点值函数
{
struct list *p;
p=head;

printf("\n当前链表中存有的元素:\n");
while(p!=NULL)
{
printf("%d\n",p->data);
p=p->next;
}
printf("当前的表长是: %d\n\n",length);//输出当前表长
return head;
}
void insert()//插入结点函数
{
struct list *k,*p,*q;
int x;
printf("请输入你要在哪个结点值之前插入新结点: ");
scanf("%d",&x);

k=(list*)malloc(sizeof(list));//创建新结点
printf("请输入新结点的值: ");
scanf("%d",&k->data);
k->next=NULL;
if(head==NULL)//若链表为空,则直接入链表
{
head=k;
length=length+1;
printf("插入成功\n\n");
}
else if(head->data==x)//在第一个结点前插入新结点
{
k->next=head;
head=k;
printf("插入成功\n\n");
length=length+1;
}
else
{
q=head;
p=head->next;
while((p != NULL) && (p->data != x))//找出值为X的结点的位置
{
q = p;
p = p->next;
}

if (p == NULL)
{
q->next=k;//在链表末插入新结点
printf("插入成功\n");
length=length+1;
}
else if(p->data == x)//在要求的X结点前插入新结点
{
k->next=p;
q->next=k;
printf("插入成功\n\n");
length=length+1;
}

}
output();
}

int delet()//删除结点函数
{
struct list *q,*p;
int x,y;
printf("请输入你所要删除的结点值: ");
scanf("%d",&x);

if(head==NULL)//表空
{
printf("表空\n");
return 0 ;
}
else if(x==head->data)//第一个结点为删除的结点
{
q=head;
head=head->next;
y=q->data;
free(q);

printf("删除成功\n\n");
length=length-1;
output();
return(y);
}

else
{
q=head;
p=head->next;
while((p != NULL) && (p->data != x))//找出值为X的结点
{
q=p;
p=p->next;
}
if(p==NULL)
{
printf("没有删除对象\n");
}

if(x==p->data)//删除值为X的结点
{
q->next=p->next;
y=p->data;
free(p);
printf("删除成功\n\n");
length=length-1;
output();
return (y);
}
else
{
printf("表中没有指定的结点\n");
output();
return 0;
}
}
return 0;

}

void find()
{
struct list *p;
int k,x,i=1;
char y,n;

LOOP:
p=head;
printf("请输入你要查找的结点值: ");
scanf("%d",&x);
while(p->data!=x)
{
p=p->next;
i++;

}
printf("你所查找的结点是表中第 %d 个结点!\n\n",i);
printf("是否要继续查找,请输入y/n\n\n");
k=getch();
if(k=='y')
{
i=1;
goto LOOP;
}
else
return;
}

void main()
{
printf("计Y062 200502001052 李抱和\n\n");
int a;
LOOP:
printf(" *****************\n");
printf(" ** 1 创建链表 **\n");
printf(" ** 2 链表输出 **\n");
printf(" ** 3 插入结点 **\n");
printf(" ** 4 删除结点 **\n");
printf(" ** 5 查找结点 **\n");
printf(" *****************\n");
printf("\n请选择: ");
scanf("%d",&a);

switch(a)
{
case 1 :
head=creat_n();
break;
case 2 :
output();
break;
case 3 :
insert();
break;
case 4 :
delet();
break;
case 5 :
find();
break;

}
goto LOOP;
}

#include#include
typedef int ElemType;

/*构建结点结构体 */typedef struct LNode
{
int data;
struct LNode * next;
}LNode, * LinkList;
/*用于创建链表的函数 */
/*反序构建的*/
LinkList CreateList_L(LinkList L, int n)
{
int i;
LinkList p;
L = (LinkList)malloc(sizeof(LNode));
L->next = NULL;
for(i = 0; i < n; ++i)
{
p = (LinkList)malloc(sizeof(LNode));
scanf("%d",&p->data);
p->next = L->next;
L->next = p;
}
return L;
}

/*用于查找的函数*/LinkList GetElem_L(LinkList L,int i,ElemType &e)
{
LinkList p = L;
int j;
p = L->next;j = 1;
while(p && j {
p = p->next;
++j;
}
if(!p || j>i)
{
printf("表中无此位置。\n");
return L;
}
e = p->data;
printf("%d\n",e);
return L;
}

/* 用于插入结点的函数 */LinkList ListInsert_L(LinkList L, int i, int newnode)
{
LinkList p = L;
LinkList s;
int j = 0;
while(p&&j {
p = p->next;
++j;
}
if(!p||j>i-1)
{
printf("位置小于1或大于表长。\n");
return L;
}
s = (LinkList)malloc(sizeof(LNode));
s->data = newnode;
s->next = p->next;
p->next = s;
return L;

}

/* 用于删除结点的函数 */LinkList ListDelete_L(LinkList L, int i)
{
LinkList p = L;
LinkList s;
int j=0;
while(p->next&&j {
p = p->next;
++j;
}
if(!(p->next)||j>i-1)
{
printf("删除位置不合理。\n");
return L;
}
s = p->next;
p->next = s->next;
printf("%s%d\n","被删除的结点是：",s->data);
free(s);
return L;
}

/*用于遍历链表的函数 */
void ListDisp_L(LinkList L)
{
LinkList p;
int i=0;
p = L->next;

while(p)
{
printf("%d:%d\n", ++i,p->data);
p = p->next;
}

}

int main(){
int where;
int value;
int count;
int search;
int output;

LinkList L; printf("请输入链表初始结点数:");
scanf("%d",&count);
printf("请输入各个结点数值，每输入一个按回车确认：\n");
L = CreateList_L(L, count);

printf("请输入要查找的位置:");
scanf("%d",&search);
L = GetElem_L(L,search,output);

printf("请输入插入的位置:");
scanf("%d", &where);
printf("请输入要插入的数值:");
scanf("%d", &value);
L = ListInsert_L(L,where,value);
ListDisp_L(L);

printf("请输入要删除的位置:"); scanf("%d",&where);
L = ListDelete_L(L,where);
ListDisp_L(L);

return 0;
}

　　一．实验目的
熟悉线性表的表示及实现方法。掌握线性表的基本操作：插入、删除、查找等运算在链式存储结构上的运算。
二．实验内容
1．问题描述
设计一个单链表基本操作的程序
2．基本要求
编写一个程序实现单链表的各种基本运算，包括：
（1）初始化单链表；
（2）依次插入n个元素（自行编写），建立带头结点的单链表；
（3）输出单链表；
（4）计算单链表的长度；
（5）判断单链表是否为空；
（6）输出单链表的第i个元素；
（7）在第i个元素位置上插入一个数据元素；
（8）删除单链表的第i个元素。
三．实验环境
Microsoft Visual C++ 6.0
四．测试数据
自行编写测试数据进行测试

struct node{
char data;
struct node *next;
};
typedef struct node NODE;
/*This function creates a link_list with N nodes.*/
NODE *create_link_list(int n)
{int i;
NODE *head, *p, *q;
if (n==0) return NULL;
head = (NODE *) malloc(sizeof(NODE));
p = head;
printf("Please input %d chars for the link list\n",n);
for (i=0; i {scanf("%c ", &(p->data));
q=(NODE *)malloc(sizeof(NODE));
printf("test3\n");
p->next=q;
p=q;}
scanf("%c ",&(p->data));
getchar();
p->next=NULL;
return (head);}
/*This function inserts a node whose value is b*/
/*before the node whose value is a, if the node is not exist,*/
/*then insert it at the end of the list*/
void insert(NODE **p_head, char a, char b)
{NODE *p, *q;
q = (NODE *)malloc(sizeof(NODE));
q->data = b;
q->next =NULL;
if (* p_head == NULL) * p_head = q;
else
{p=(NODE*)malloc(sizeof(NODE));
p = * p_head;
while (p->data != a && p->next != NULL)
p = p->next;
q->next = p->next;
p->next = q;}
}
/*The function deletes the node whose value is a,*/
/*if success, return 0, or return 1*/
int deletenode(NODE **p_head, char a)
{NODE *p, *q;
q=*p_head;
if (q==NULL) return(1);
if (q->data == a)
{* p_head = q->next;
free(q);
return (0);}
else
{while (q->data != a && q->next != NULL)
{p = q;
q = q->next;}
if (q->data == a)
{p->next = q->next;
free(q);
return(0);}
else return(1);}
}
void main()
{ NODE *my_head,*p;
/* create a link list with m nodes */
int m;
char ch_a,ch_b;
printf("please input the number of nodes for the link_list\nm=");
scanf("%d",&m);
getchar();
printf("test1\n");
my_head = (NODE *) malloc(sizeof(NODE));
my_head=create_link_list(m);
/*Output the link list*/
printf("The link list is like:\n");
p=my_head;
while (p != NULL)
{printf("%c ",p->data);
p=p->next;
}
printf("\n");
/*insert a node whose value is b before a*/
printf("Please input the position for a\n ch_a=");
getchar();
scanf("%c",&ch_a);
getchar();
printf("Please input the value that you want to insert\n ch_b=");
scanf("%c",&ch_b);
getchar();
insert(&my_head,ch_a,ch_b);
printf("The link list after insertion is like:\n");
p=my_head;
while (p != NULL)
{printf("%c ",p->data);
p=p->next;
}
printf("\n");
/*delete a node whose value is a*/
printf("Please input the position for a a=");
scanf("%c",&ch_a);
getchar();
deletenode(&my_head,ch_a);
printf("The link list after deleting is like:\n");
p=my_head;
while (p != NULL)
{printf("%c ",p->data);
p=p->next;
}
printf("\n");
}