数据结构报告1.doc

数据结构 实验1 线性表 班级：.net124 学号：201207082438 姓名：刘团伟实验一 线性表 一、实验目的 了解线性表的基本操作。 二、实验内容 1． 请简述线性表的基本特性和线性表的几种基本操作的机制 ①答：线性表的基本特性是：对线性表中某个元素ai来说，称其前面的元素ai-1为ai的直接前驱，称其后前面的元素ai+1为ai的直接后继。显然，线性表中每个元素最多有一个直接前驱和一个直接后继。 ②答：线性表的几种基本操作的机制有六个： （1）初始化线性表 initial_List(L)——建立线性表的初始结构，即建空表。这也是各种结构都可能要用的运算。 （2）求表长度 List_length(L)——即求表中的元素个数。 （3）按序号取元素 get_element(L,i)——取出表中序号为i的元素 。 （4）按值查询 List_locate(L,x)——取出指定值为x的元素，若存在该元素，则返回其地址；否则，返回一个能指示其不存在的地址值或标记。 （5）插入元素 List_insert(L,i,x)——在表L的第i个位置上插入值为x的元素。显然，若表中的元素个数为n，则插入序号i应满足1=i=n+1。 （6）删除元素 List_delete（L，i）——删除表L中序号为i的元素，显然，待删除元素的序号应满足1=i=n。 2．设计简单的程序实现单链表的几种基本操作，加注释！ #include stdio.h #include stdlib.h //using namespace std; typedef int ElemType; struct LNo //结构体 { ElemType data; LNode *next; }; typedef LNode *LinkList; void CreateList_L(LinkList L, int n) // 算法2.11 { // 逆位序输入（随机产生）n个元素的值，建立带表头结点的单链线性表L LinkList p; int i; L = (LinkList)malloc(sizeof(LNode)); L-next = NULL; // 先建立一个带头结点的单链表 for (i=n; i0; --i) { p = (LinkList)malloc(sizeof(LNode)); // 生成新结点 scanf(%d,p-data); //p-data = rand()%200; // 改为一个随机生成的数字(200以内) p-next = L-next; L-next = p; // 插入到表头 } } int ListTraverse(LinkList L,void(*vi)(ElemType)) // vi的形参类型为ElemType，与bo2-1.cpp中相应函数的形参类型ElemType不同 { // 初始条件：线性表L已存在 // 操作结果:依次对L的每个数据元素调用函数vi()。一旦vi()失败,则操作失败 LinkList p=L-next; while(p) { vi(p-data); p=p-next; } printf(\n); return 1; } void visit(ElemType c) { printf(%d ,c); } int ListInsert(LinkList L,int i,ElemType e) // 算法2.9。不改变L { // 在带头结点的单链线性表L中第i个位置之前插入元素e int j=0; LinkList p=L,s; while(pji-1) // 寻找第i-1个结点 { p=p-next; j++; } if(!p||ji-1) // i小于1或者大于表长 return -1; s=(LinkList)malloc(sizeof(LNode)); // 生成新结点 s-data=e; // 插入L中 s-next=p-next; p-next=s; return 1; } int ListDelete(LinkList L,int i /*,ElemType e*/) // 算法2.10。不改变L { // 在带头结点