实验一 顺序表和单链表的建立和操作

一、实验目的

1.了解顺序表的结构特点及有关概念
2.掌握顺序表建立、插入、删除的基本操作算法
3.了解单链表的结构特点、描述方法及有关概念
4.掌握单链表建立、插入、删除的基本操作算法

二、顺序表

在高级语言(如C语言)环境下：数组具有随机存取的特性，因此，借助数组来描述顺序表。除了用数组来存储线性表的元素之外，顺序表还应该有表示线性表的长度属性，所以用结构类型来定义顺序表类型。采用静态分配的顺序存储结构来表示。

包含的基本操作有：

1.建立顺序表: Status creatlist(sequenlist *L)
2.插入一个元素:Status insert(sequenlist *L,elemtype x,int i)
3.删除一个元素: Status dellist(sequenlist *L,int i)
4.输出顺序表: void printout(sequenlist *L)（辅助函数）

顺序线性表的插入

 在线性表 L= (a1，…a i-1，ai， ai+1，…，an) 中的第i(1≦i≦n)个位置上插入一个新结点e，使其成为线性表：
L=(a1，…a i-1，e，ai，ai+1，…，an)

算法思想
(1) 进行合法性检查，1<=i<=n+1;
(2) 检查线性表是否已满；
(3) 将第n个至第i个元素逐一向后移动一个单元；
(4) 在第i个位置处插入新元素；
(5) 将表的长度加1.

顺序线性表的删除

在线性表 L=(a1，…a i-1，ai， ai+1，…，an) 中删除结点ai(1≦i≦n)，使其成为线性表：
L= (a1，…ai-1，ai+1，…，an)

实现步骤
(1)进行合法性检查，1<=i<=n;
(2)将线性表L中的第i+1个至第n个结点依此向前移动一个位置。
(3) 线性表长度减1。

#include "stdio.h"
#include "malloc.h"
#define maxsize 1024
typedef char elemtype;
typedef struct
{
elemtype list[maxsize];
int length;
}sequenlist;
//创建顺序表 
void creatlist(sequenlist *L);
//插入元素 
int insert(sequenlist *L,elemtype x,int i);
//删除元素 
int dellist(sequenlist *L,int i);
//输出顺序表 
void printout(sequenlist *L);
//创建顺序表 
void creatlist(sequenlist *L)
{
int n,i;
char tmp;
printf("请输入数据的个数：");
scanf("%d",&n);
for(i = 0; i < n; i ++)
{
printf("list[%d] = ",i);
fflush(stdin);//清空输入缓冲区，通常是为了确保不影响后面
的数据的读入
scanf("%c",&tmp);
L -> list[i] = tmp;
}
L -> length = n-1;
}
//插入元素 
int insert(sequenlist *L,elemtype x,int i)
{
int j;
if(L -> length == maxsize - 1)//判满
{
printf("overflow");
return 0;
}
else if((i < 0) || (i > L -> length)) //判插入位置是否合法
{
printf("error,please input the right 'i'n");
return 0;
}
else
{
for(j = L-> length; j >= i; j --)
L -> list[j+1] = L -> list[j];
L -> list[i] = x;
L -> length = L -> length + 1;
}
return 1;
}
//删除元素 
int dellist(sequenlist *L,int i)
{
if((i < 0) || (i > L -> length))
{
printf("error,please input the right 'i'n");
return 0;
}
else
{
for( ; i < L -> length; i++)
L -> list[i] = L -> list[i+1];
L -> length = L -> length - 1;
return 1;
}
}
//输出顺序表 
void printout(sequenlist *L)
{
int i;
for(i = 0; i <= L -> length; i ++)
{
printf("list[%d]=",i);
printf("%cn",L->list[i]);
}
}
main()
{
sequenlist *L;
char cmd,x;
int i;
L = (sequenlist *)malloc(sizeof(sequenlist));
creatlist(L);
do
{
printf(" i,I
插入n");
printf(" d,D
删除n");
printf(" q,Q
退出n");
do
{
fflush(stdin);
scanf("%c", &cmd);
}
while((cmd !='d') && (cmd != 'D') && (cmd != 'q') && (cmd != 'Q') && (cmd != 'i') && (cmd != 'I'));
switch(cmd)
{
case 'i':
case 'I':
printf("请输入你要插入的数据：");
fflush(stdin);
scanf("%c", &x);
printf("请输入你要插入的位置：");
scanf("%d", &i);
insert(L,x,i);
printout(L);
break;
case 'd':
case 'D':
printf("请输入你要删除的数据的位置：");
fflush(stdin);
scanf("%d", &i);
dellist(L,i);
printout(L);
break;
}
}
while((cmd != 'q') && (cmd != 'Q'));
}

三、单链表

C语言中用带指针的结构体类型来描述

包含的基本操作有：
1.建立单链表: linklist creat (int n)
2.插入一个元素: Status insert ( linklist &l,int i, Elemtype e)
3.删除一个元素: Status delect ( linklist &l,int i, Elemtype &e)
4.输出单链表: void output (linklist head)
5.查找元素: Status GetElem(linklist l,int i,Elemtype &e )

建立单链表

动态地建立单链表的常用方法有如下两种：**头插入法，尾插入法**。

1.头插法
从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。即每次插入的结点都作为链表的第一个结点。

linklist creat (int n)//创建单链表，采用头插法建表
{
linklist head,p; //定义头指针head指针,p指针指向当前新生成的结点
int x,i;
head=(node *)malloc(sizeof(node));//生成头结点
head->next=NULL;
printf("输入数字:n");
for(i=n;i>0;i--)//for 循环用于生成第一个节点并读入数据
{
scanf("%d",&x);
p=(node *)malloc(sizeof(node));
p->data=x;//读入第一个节点的数据
p->next=head->next;//把第一个节点始终插在头结点的后面
head->next=p;//循环以便于生成第二个节点
}
return head;//返回头指针
}

2.尾插法
先开辟头指针，然后陆续为每个数据元素开辟存储空间并赋值，并及时将地址送给前面的指针

#include<stdio.h>
#include<stdlib.h>
typedef struct liu{
char data;
struct liu *next;
}test;
liu *p,*head;
int m=sizeof(test);
void build() //字母链表的生成，要一个一个慢慢链入
{
int i;
head = (test*)malloc(m); //m=sizeof(test) 前面已求出
p = head;
for(i = 1; i < 26; i ++) //因尾结点要特殊处理，故i≠26
{
p -> data = i+‘a’-1; // 第一个结点值为字符a 
p -> next = (test*)malloc(m);
p = p->next；} //让指针变量P改为指向后继结点
p -> data = i + ‘a’-1; //最后一个元素要单独处理
p -> next = NULL ;
} //单链表尾结点的指针域要置空！
void display() /*字母链表的输出*/
{
p = head;
while (p->next!=NULL)
{
printf("%c",p->data);
p = p->next; }
printf(“%cn”,p->data);
}

单链表的插入

插入运算是将值为e的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。因此，必须首先找到ai-1所在的结点p，然后生成一个数据域为e的新结点s，s结点作为p的直接后继结点。

核心语句
s->next = p->next;
p->next = s ；
元素e结点应预先生成：
s=(LinkList*)malloc(m);
s->data=e;
s->next=p->next

单链表第i个数据插入结点的算法思路：
1.声明一指针p指向链表头结点，初始化j从0开始
2.当j<i-1时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1；
3.若到链表末尾p为空，则说明第i个结点不存在；
4.否则查找成功，在系统中生成一个空结点s；
5.将数据元素e赋值给s->data;
6.单链表的插入标准语句s->next=p->next; p->next=s;
7.返回成功。

单链表的删除

为了删除第i个结点ai，必须找到结点的存储地址。该存储地址是在其直接前趋结点ai-1的next域中，因此，必须首先找到ai-1的存储位置p，然后令p–>next指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间，将其归还给“存储池”。

删除结点的核心语句：
q = p->next; //保存b的指针，靠它才能指向c
p->next=q->next; //a、c两结点相连
free(q) ； //删除b结点，彻底释放

单链表第i个数据删除结点的算法思路：
1.声明一指针p指向链表头结点，初始化j从0开始
2.当j<i-1时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1；
3.若到链表末尾p为空，则说明第i个结点不存在；
4.否则查找成功，将欲删除的结点p->next赋值给q
5.单链表的删除标准语句p->next=q->next;
6.将q结点中的数据赋值给e，作为返回；
7.释放q结点；
8.返回成功。

元素的查找

查找链表第i个数据的算法思路：
1.声明一指针p指向链表第一个结点，初始化j从1开始；
2.当j<i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1；
3.若到链表末尾p为空，则说明第i个结点不存在；
4.否则查找成功，返回结点p的数据。

#include "stdio.h"
#include "malloc.h"
typedef char Elemtype;
typedef struct node
//定义存储节点
{
Elemtype data;
struct node *next;
} node,*linklist;
//建立单链表 
linklist creat(int n);
//插入元素
int insert(linklist &l, int i, Elemtype e);
//删除元素 
int delect(linklist &l, int i, Elemtype &e);
//查找元素 
int GetElem(linklist l, int i, Elemtype &e);
//输出单链表 
void output(linklist head);
//建立单链表，采用头插法建表
linklist creat(int n)
{
linklist head,p;
//定义头指针head指针,p指针指向当前新生成的结点
int x,i;
head = (node*)malloc(sizeof(node));
//生成头结点
head ->next = NULL;
printf("输出数字：n");
for(i = n; i > 0; i --)
//for 循环用于生成第一个节点并读入数据
{
scanf("%d", &x);
p = (node*)malloc(sizeof(node));
p -> data = x;
//读入第一个节点的数据
p -> next = head -> next;
//把第一个节点始终插在头结点的后面
head -> next = p;
}
return head;
}
//插入元素
int insert(linklist &l, int i, Elemtype e)
{
int j = 0;
linklist p = l, s;
while( j < i - 1 && p)
{
p = p -> next;
++ j;
}
if( !p || j > i -1)
printf("无法插入");
else
{
s = (node*)malloc(sizeof(node));
s -> data = e;
s -> next = p -> next;
p -> next = s;
}
return 1;
}
//删除元素 
int delect(linklist &l, int i, Elemtype &e)
{
int j = 0;
linklist p = l,q;
while( j < i - 1 && p -> next)
{
p = p -> next;
++ j;
}
if( !p -> next || j > i - 1)
printf("无法删除");
else
{
q = p -> next;
p -> next = q -> next;
e = q ->data;
free(q);
}
return 1;
}
//查找元素 
int GetElem(linklist l, int i, Elemtype &e)
{
linklist p;
int j;
p = l -> next;
j = 1;
while( p && j < i)
{
p = p -> next;
++ j;
}
if( !p || j > i)
printf("无法查找");
e = p -> data;
return e;
}
//输出单链表 
void output(linklist head)
{
linklist p;
p = head -> next;
do
{
printf("%3d", p -> data);
p = p -> next;
}
while(p);
printf("n");
}
main()
{
linklist la;
int n;
int i,j;
Elemtype e;
char cmd;
printf("输出链表元素的个数：");
scanf("%d", &n);
la =
creat(n);
printf("输出链表：n");
output(la);
do
{
printf("g,G
查找n");
printf("i,I
插入n");
printf("d,D
删除n");
printf("q,Q
退出n");
do
{
scanf("%c", &cmd);
}
while((cmd != 'g') && (cmd != 'G') && (cmd != 'd') && (cmd != 'D') && (cmd != 'q') && (cmd != 'Q') && (cmd != 'i') && (cmd != 'I'));
switch(cmd)
{
case 'g':
case 'G':
printf("请输入要查找元素的位置：n");
scanf("%d", &i);
j = GetElem(la, i, e);
printf("要查找的元素是%dn", j);
break;
case 'i':
case 'I':
printf("请输入你要插入的数据：");
scanf("%d", &e);
printf("请输入你要插入的位置：");
scanf("%d", &i);
insert(la, i ,e);
printf("插入后的链表：n");
output(la);
break;
case 'd':
case 'D':
printf("请输入要删除的位置:n");
scanf("%d",&i);
delect(la,i,e);
printf("删除的那个元素是:%dn",e);
printf("输出删除后的顺序表:n");
output(la);
break;
}
}
while((cmd != 'q')&&(cmd != 'Q'));
}

最后

以上就是勤恳唇膏为你收集整理的实验一 顺序表和单链表的建立和操作的全部内容，希望文章能够帮你解决实验一 顺序表和单链表的建立和操作所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。