数据机构 线性表的存储结构:线性表的存储结构
《数据结构》课程实验 实验报告一
线性表的存储结构
学号： 09416126班级： 计算机091 姓名：指导教师：
实验完成时间： 2011.04.04 实验成绩：
一、 实验题目
实验一 线性表的存储结构
二、 实验目的和要求：
1．掌握顺序和链式存储结构的特点。
2．掌握顺序和链式存储结构的常见算法。
三、 背景知识
线性表的动态分配顺序存储结构：
＃define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量 ＃define LISTINCREMENT 10 //线性表存储空间的分配增量
typedef struct{
ElemType *elem; //存储空间基址
int length; //当前长度
int listsize; //当前分配的存储容量（以sizeof(ElemType)为单位) } SqList；
链表的分类：带头结点的（单链表、双向链表、循环链表等）、不带头结点的（单链表、双向链表、循环链表等）。
链表的基本操作：插入、删除及应用。
不带头结点单链表的存储定义:
typedef struct LNode
{
ElemType data;
struct LNode *next;
}Lnode,*LinkList;
不带头结点双向链表的存储定义:
typedef struct DuLNode
{
ElemType data;
struct DuLNode *prior;
struct DuLNode *next;
}DuLnode,*DuLinkList;
四、 实验内容
1．顺序表的元素的插入、删除、修改、输出等基本操作。
2．带头结点的单链表的元素的创建、查找、插入、删除等基本操作。
3．不带头结点的单链表的元素的创建、查找、插入、删除等基本操作。
4．不带头结点的双向链表的元素的创建、查找、插入、删除等基本操作。
五、 算法描述
1. 顺序表的元素的插入、删除、修改、输出等基本操作。
#define MAXSIZE 100
#define OK 1
#define OVERFLOW -2
#include
typedef int elemtype;
typedef struct
{elemtype vec[MAXSIZE];
int last;
}sequenlist;
int insert(sequenlist *L,int i,elemtype x)
{ int j;
if(((*L).last)>=MAXSIZE-1)
{printf("the list is overflow!\n");
return(0);
}
else
if((i(*L).last+1))
{printf("position is not correct!\n");
return(0);
}
else
{for(j=(*L).last;j>=i-1;j--)
(*L).vec[j+1]=(*L).vec[j];
(*L).vec[i-1]=x;
(*L).last=(*L).last+1;
}
return(1);
}
void delete1(sequenlist *L, int i)
{ int j;
if((i(*L).last+1))
printf("delete fail\n");
else
{for(j=i;j
(*L).vec[j-1]=(*L).vec[j];
(*L).last--;
}
}
void listprint(sequenlist *L)
{int i;
for(i=0;i
printf("i,e=%d,%d\n",i,L->vec[i]);
}
void locate(sequenlist *L,elemtype x) //查找为x 的值
{int k;
for(k=1;k
if((*L).vec[k-1]==x)
{printf("wei zhi:%d\n",k);//找到x 的值输出位置
peak;
}
if(k>(*L).last+1)//当找不到x 的值输出#符号
printf("not the number:#\n");
}
main()
{
sequenlist sl={1,2,3,4,5,6};//直接给顺序表赋初值
sequenlist *L;
int i,j,x;
elemtype e;
L=&sl;
printf("please input the insert position and insert value\n"); scanf("%d,%d",&i,&x);
printf("the insert position: %d \ninsert value:%d\n",i,x); insert(L,i,x);
listprint(L);
printf("please intput the delete position:");
scanf("%d",&j);
delete1(L,j);
listprint(L);
printf("please input the number\n");
scanf("%d",&x);
locate(L,x);
}
2. 带头结点的单链表的插入和删除操作。
#include
struct llist /* 链表结构声明 */
{
int num; /* 数据域 */
struct llist *next; /* 指针域 */
};
typedef struct llist node; /* 类型重定义 */
typedef node *llink; /* 重定义指针类型 */
/*――――――――――――链表的输出――――――――――――*/ void printllist(llink head)
{
llink ptr;
ptr = head->next; /* 指向真正的起始 */
while ( ptr != NULL ) /* 链表遍历循环 */
{
printf("[%d]",ptr->num); /* 输出结点数据 */
ptr = ptr->next; /* 指向下一结点 */
}
printf("\n"); /* 换行 */
}
/*――――――――――――链表的创建――――――――――――*/ llink createllist(int *array,int len)
{
llink head; /* 链表的开始指针 */
llink ptr,ptr1;
int i;
/* 建立开头结点 */
head = ( llink ) malloc(sizeof(node)); /* 分配内存 */ if ( !head ) /* 检查指针 */ return NULL;
ptr = head; /* 将ptr 指向链表开始 */
for ( i = 0; i
{
ptr1 = ( llink ) malloc(sizeof(node));
if ( !ptr1 )
return NULL;
ptr1->num = array[i]; /* 建立结点内容 */
ptr1->next = NULL; /* 设定指针初值 */
ptr->next = ptr1; /* 连接结点 */
ptr = ptr->next; /* 指向下一结点 */
}
return head;
}
/*――――――――――――链表的结点插入―――――――――――*/ llink insertnode(llink head,llink ptr,int value)
{
llink new; /* 新结点指针变量 */
new = ( llink ) malloc(sizeof(node)); /* 建立新结点 */
if ( !new )
return NULL;
new->num = value; /* 建立结点内容 */
new->next = NULL; /* 设定指针初值 */
/* 如果ptr 等於头节点则是插入第一个结点 */
new->next = ptr->next; /* 新结点指向下一结点 */
ptr->next = new; /* 结点ptr 指向新结点 */
return head;
}
/*――――――――――――链表的结点删除―――――――――――－*/ llink deletenode(llink head,llink ptr)
{
llink previous;
previous = head;
while ( previous->next != ptr ) /* 找结点ptr 前一结点 */ previous = previous->next;
previous->next = ptr->next; /* 删除中间结点 */
free(ptr); /* 释放结点内存 */
return head;
}
/*―――――――――――――主程序―――――――――――*/
void main()
{
int llist1[6] = { 1, 2, 3, 4, 5, 6 }; /*数组内容 */
llink head; /* 指向链表开始 */ head = createllist(llist1,6); /* 建立链表 */ if ( !head )
{
printf("内存分配失败! \n");
exit(1);
}
printf("原来的链表: ");
printllist(head); /* 输出原来链表 */
head = insertnode(head,head,0); /* 插入新结点 */
if ( !head )
{
printf("内存分配失败! \n");
exit(1);
}
/* 删除链内结点 */
head = deletenode(head,head->next->next->next);
printf("最后的链表: ");
printllist(head); /* 输出结果 */
}
3. 不带头结点的单链表的插入和删除操作。
#include
#include
struct llist /* 链表结构声明 */
{
int num; /* 数据域 */
struct llist *next; /* 指针域 */
};
typedef struct llist node; /* 类型重定义 */
typedef node *llink; /* 重定义指针类型 */
/*――――――――――――链表的输出――――――――――――*/ void printllist(llink head)
{
llink ptr;
ptr = head; /* 指向真正的起始 */
while ( ptr != NULL ) /* 链表遍历循环 */
{
printf("[%d]",ptr->num); /* 输出结点数据 */
ptr = ptr->next; /* 指向下一结点 */
}
printf("\n"); /* 换行 */
}
/*――――――――――――链表的创建――――――――――――*/ llink createllist(int *array,int len)
{
llink head; /* 链表的开始指针 */
llink ptr,ptr1;
int i;
/* 建立开头结点 */
head = ( llink ) malloc(sizeof(node)); /* 分配内存 */ if ( !head ) /* 检查指针 */ return NULL;
head->num=array[0];
head->next=NULL;
ptr = head; /* 将ptr 指向链表开始 */
for ( i = 1; i
{
ptr1 = ( llink ) malloc(sizeof(node));
if ( !ptr1 )
return NULL;
ptr1->num = array[i]; /* 建立结点内容 */
ptr1->next = NULL; /* 设定指针初值 */
ptr->next = ptr1; /* 连接结点 */
ptr = ptr->next; /* 指向下一结点 */
}
return head;
}
/*――――――――――――链表的结点插入―――――――――――*/ llink insertnode(llink head,int i,int value)
{
/* 如果ptr 等於头节点则是插入第一个结点 */
if (i==1){
llink mnew; /* 新结点指针变量 */ mnew = ( llink ) malloc(sizeof(node)); /* 建立新结点 */ if ( !mnew )
return NULL;
mnew->num = value; /* 建立结点内容 */
mnew->next =head; /* 设定指针初值 */
head=mnew;
}else{
llink ptr;
llink mnew;
int j;
ptr=head;
j=1;
while(ptr&&jnext; ++j;}
if(!ptr||j>i-1) return NULL;
mnew = ( llink ) malloc(sizeof(node)); /* 建立新结点 */ if ( !mnew )
return NULL;
mnew->num = value; /* 建立结点内容 */
mnew->next = ptr->next; /* 新结点指向下一结点 */
ptr->next = mnew; /* 结点ptr 指向新结点 */ }
return head;
}
/*――――――――――――链表的结点删除―――――――――――－*/ llink deletenode(llink head, int i)
{
llink deleteptr;
if(i==1){
deleteptr=head;
head=head->next;
free(deleteptr);
}else{
llink previous;
llink deleteptr;
int j;
previous = head;
j=1;
while(previous&&jnext; ++j;}
if(!previous||j>i-1) return NULL;
deleteptr = previous->next;
previous->next = previous->next->next; /* 删除结点 */ free(deleteptr); /* 释放结点内存 */ }
return head;
}
/*―――――――――――――主程序―――――――――――*/
void main()
{
int llist1[6] = { 1, 2, 3, 4, 5, 6 }; /*数组内容 */
llink head; /* 指向链表开始 */ head = createllist(llist1,6); /* 建立链表 */ if ( !head )
{
printf("内存分配失败! \n");
exit(1);
}
printf("原来的链表: ");
printllist(head); /* 输出原来链表 */
head = insertnode(head,2,0); /* 插入新结点 */
if ( !head )
{
printf("内存分配失败! \n");
exit(1);
}
/* 删除链内结点 */
head = deletenode(head,4);
printf("最后的链表: ");
printllist(head); /* 输出结果 */
}
4. 不带头结点的双向链表的插入和删除操作。
#include
#include
struct llist /* 链表结构声明 */ {
int num; /* 数据域 */ struct llist *prior;
struct llist *next; /* 指针域 */ };
typedef struct llist node; /* 类型重定义 */ typedef node *llink; /* 重定义指针类型 */
/*――――――――――――链表的输出――――――――――――*/ void printllist(llink head)
{
llink ptr;
ptr = head; /* 指向真正的起始 */
while ( ptr != NULL ) /* 链表遍历循环 */ {
printf("[%d]",ptr->num); /* 输出结点数据 */ ptr = ptr->next; /* 指向下一结点 */ }
printf("\n"); /* 换行 */ }
/*――――――――――――链表的创建――――――――――――*/ llink createllist(int *array,int len)
{
llink head; /* 链表的开始指针 */ llink ptr,ptr1;
int i;
/* 建立开头结点 */
head = ( llink ) malloc(sizeof(node)); /* 分配内存 */ if ( !head ) /* 检查指针 */ return NULL;
head->num=array[0];
head->prior=NULL;
head->next=NULL;
ptr = head; /* 将ptr 指向链表开始 */ for ( i = 1; i
ptr1 = ( llink ) malloc(sizeof(node));
if ( !ptr1 )
return NULL;
ptr1->num = array[i]; /* 建立结点内容 */ ptr1->prior=ptr;
ptr1->next = NULL; /* 设定指针初值 */ ptr->next = ptr1; /* 连接结点 */ ptr = ptr->next; /* 指向下一结点 */
}
return head;
}
/*――――――――――――链表的结点插入―――――――――――*/ llink insertnode(llink head,int i,int value)
{
/* 如果ptr 等於头节点则是插入第一个结点 */
if (i==1){
llink mnew; /* 新结点指针变量 */ mnew = ( llink ) malloc(sizeof(node)); /* 建立新结点 */ if ( !mnew )
return NULL;
mnew->num = value; /* 建立结点内容 */ mnew->prior=NULL;
mnew->next =head; /* 设定指针初值 */ head->prior=mnew;
head=mnew;
}else{
llink ptr;
llink mnew;
int j;
ptr=head;
j=1;
while(ptr&&jnext; ++j;}
if(!ptr||j>i-1) return NULL;
mnew = ( llink ) malloc(sizeof(node)); /* 建立新结点 */ if ( !mnew )
return NULL;
mnew->num = value; /* 建立结点内容 */ mnew->prior=ptr;
mnew->next = ptr->next; /* 新结点指向下一结点 */ ptr->next->prior=mnew;
ptr->next = mnew; /* 结点ptr 指向新结点 */ }
return head;
}
/*――――――――――――链表的结点删除―――――――――――－*/ llink deletenode(llink head, int i)
{
llink deleteptr;
if(i==1){
deleteptr=head;
head=head->next;
head->next->prior=NULL;
free(deleteptr);
}else{
llink previous;
llink deleteptr;
int j;
previous = head;
j=1;
while(previous&&jnext; ++j;} if(!previous||j>i-1) return NULL;
deleteptr = previous->next;
previous->next = previous->next->next; /* 删除结点 */ previous->next->next->prior=previous;
free(deleteptr); /* 释放结点内存 }
return head;
}
/*―――――――――――――主程序―――――――――――*/
void main()
{
int llist1[6] = { 1, 2, 3, 4, 5, 6 }; /*数组内容 */
llink head; /* 指向链表开始 */ head = createllist(llist1,6); /* 建立链表 */ if ( !head )
{
printf("内存分配失败! \n");
exit(1);
}
printf("原来的链表: ");
printllist(head); /* 输出原来链表 */
head = insertnode(head,2,0); /* 插入新结点 */
if ( !head )
{
printf("内存分配失败! \n");
exit(1);
}
/* 删除链内结点 */
head = deletenode(head,1);
printf("最后的链表: ");
printllist(head); /* 输出结果 */
}
*/
六、 实验结果
顺序表的元素的插入和删除操作结果： 原来的顺序表：[1][2][3][4][5][6]
最后的顺序表：[1][0][2][4][5][6]
带头结点的单链表的元素的插入和删除操作结果： 原来的链表: [1][2][3][4][5][6]
最后的链表: [0][1][3][4][5][6]
不带头结点的单链表的插入和删除操作结果： 原来的链表: [1][2][3][4][5][6]
最后的链表: [1][0][2][4][5][6]
不带头结点的双向链表的插入和删除操作结果： 原来的链表: [1][2][3][4][5][6]
最后的链表: [0][2][3][4][5][6]