数据机构线性表的存储结构.doc

数据结构课程实验 实验报告一线性表的存储结构学号： 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 vecMAXSIZE; 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).vecj+1=(*L).vecj; (*L).veci-1=x; (*L).last=(*L).last+1; return(1); void delete1(sequenlist *L, int i) int j; if(i(*L).last+1) printf(delete failn); else for(j=i;j=(*L).last;j+) (*L).vecj-1=(*L).vecj; (*L).last-; void listprint(sequenlist *L) int i; for(i=0;iveci); void locate(sequenlist *L,elemtype x) /查找为x的值int k;for(k=1;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 valuen); scanf(%d,%d,&i,&x); printf(the insert position: %d ninsert value:%dn,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 numbern); 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 num = arrayi; /* 建立结点内容 */ 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 llist16 = 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=array0; head-next=NULL; ptr = head; /* 将ptr指向链表开始 */ for ( i = 1; i num = arrayi; /* 建立结点内容 */ 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|ji-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);elsellink previous;llink deleteptr;int j;previous = head;j=1; while(previous&jnext; +j; if(!previous|ji-1) return NULL; deleteptr = previous-next; previous-next = previous-next-next; /* 删除结点 */free(deleteptr); /* 释放结点内存 */ return head;/*主程序*/void main() int llist16 = 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=array0; head-prior=NULL; head-next=NULL; ptr = head; /* 将ptr指向链表开始 */ for ( i = 1; i num = arrayi; /* 建立结点内容 */ 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|ji-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);elsellink previous;llink deletept