实验二线性表的基本操作
一、实验目的
1.掌握用C++/C语言调试程序的基本方法。
2.掌握线性表的顺序存储和链式存储的基本运算,如插入、删除等。
二、实验要求
1.C++/C完成算法设计和程序设计并上机调试通过。
2.撰写实验报告,提供实验结果和数据。
3.分析算法,要求给出具体的算法分析结果,包括时间复杂度和空间复杂度,并简要给出算法设计小结和心得。
三、实验内容:
1. 分析并运行以下各子程序的主要功能。
程序1:顺序存储的线性表和运算
#include
#define MAXSIZE 100
int list[MAXSIZE];
int n;
/*insert in a seqlist*/
int sq_insert(int list[], int *p_n, int i, int x)
{int j;
if (i<0 || i>*p_n) return(1);
if (*p_n==MAXSIZE) return(2);
for (j=*p_n+1; j>i; j--)
list[j]=list[j-1];
list[i]=x;
(*p_n)++;
return(0);
}
/*delete in a seq list*/
int sq_delete(int list[], int *p_n, int i)
{int j;
if (i<0 || i>=*p_n) return(1);
for (j = i+1; j<=*p_n; j++)
list[j-1] = list[j];
(*p_n)--;
return(0);
}
void main()
{int i,x,temp;
printf("please input the number for n\n");
printf("n=");
scanf("%d",&n);
for (i=0; i<=n; i++)
{printf("list[%d]=",i);
scanf("%d",&list[i]);}
printf("The list before insertion is\n");
for (i=0; i<=n; i++) printf("%d ",list[i]);
printf("\n");
printf("please input the position where you want to insert a value\nposition=");
scanf("%d",&i);
printf("please input the value you want to insert.\nx=");
scanf("%d",&x);
temp=sq_insert(list,&n,i,x);
switch(temp)
{case 0:printf("The insertion is successful!\n");
printf("The list is after insertion is\n");
for(i=0; i<=n; i++) printf("%d ",list[i]);
printf("\n");
printf("%d\n",n);
break;
case 1:
case 2:printf("The insertion is not successful!\n");break;}
/*deleting*/
printf("The list before deleting is\n");
for (i=0; i<=n; i++) printf("%d ",list[i]);
printf("\n");
printf("please input the position where you want to delete a value\nposition=");
scanf("%d",&i);
temp=sq_delete(list,&n,i);
switch(temp)
{case 0:printf("The deleting is successful!\n");
printf("The list is after deleting is\n");
for(i=0; i<=n; i++) printf("%d ",list[i]);
printf("\n");
printf("%d",n);
break;
case 1:printf("The deleting is not successful!");break;}
}
2. 分析并运行以下各子程序的主要功能。
程序2链式存储的线性表和运算
#include
#include
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"); } 3. 运行以下程序并分析各子函数的主要功能。 #include #include struct tagNode { int data; struct tagNode *pNext; }; typedef struct tagNode* pNode; //将结点插入到链表的适当位置,这是一个降序排列的链表// void insertList(pNode head,//链表头结点 pNode pnode)//要插入的结点 { pNode pPri=head; while (pPri->pNext!=NULL) { if (pPri->pNext->data { pnode->pNext=pPri->pNext; pPri->pNext=pnode; break; } pPri=pPri->pNext; } if (pPri->pNext==NULL)//如果要插入的结点最小 { pPri->pNext=pnode; } } //输出链表 void printLinkedList(pNode head) { pNode temp=head->pNext; while (temp!=NULL) { printf("%d ",temp->data); temp=temp->pNext; } } //从链表中删除结点 void delformList(pNode head,int data) { pNode temp=head->pNext; pNode pPri=head; while (temp!=NULL) { if (temp->data==data) { pPri->pNext=temp->pNext; free(temp); break; } pPri=temp; temp=temp->pNext; } } void main() { pNode head=(pNode)malloc(sizeof(struct tagNode));//给头指针分配空间 pNode pTemp=NULL; int temp; head->pNext=NULL;//比较好的习惯就是分配好空间,马上赋值 printf("请输入要放入链表中的数据,以-1结尾:"); //读入数据,以-1结尾,把数据插入链表中 scanf("%d",&temp); while (temp!=-1) { pTemp=(pNode)malloc(sizeof(struct tagNode)); pTemp->data=temp; pTemp->pNext=NULL; insertList(head,pTemp); scanf("%d",&temp); } printf("降序排列的链表为:\n"); printLinkedList(head); printf("\n"); //下面的代码当删除函数编写成功后,可以取消注释,让其执行,主要是调用函数实现链表结点的删除 //printf("请输入要删除数,以-1结尾:"); //scanf("%d",&temp); //while (temp!=-1) //{ // delformList(head,temp); // scanf("%d",&temp); //} //printf("删除节点后,链表中剩余数据为:"); //printLinkedList(head); //printf("\n"); } 四、思考与提高 试将以上链表改为有序表,并分析有序表有哪些显著的优点和缺点?库函数载和常量定义:(代码,C++) #include using namespace std; const int MaxSize=100; (1)顺序表存储结构的定义(类的声明):(代码) template class SeqList { public: SeqList( ); //无参构造函数 SeqList(datatype a[ ], int n); //有参构造函数 ~SeqList(){}; //析构函数为空 int Length(); //求线性表的长度 datatype Get(int i); //按位查找,取线性表的第i个元素int Locate(datatype item); //查找元素item void Insert(int i, datatype item); //在第i个位置插入元素item datatype Delete(int i); //删除线性表的第i个元素 void display(); //遍历线性表,按序号依次输出各元素private: datatype data[MaxSize]; //存放数据元素的数组 int length; //线性表的长度 }; (2)初始化顺序表算法实现(不带参数的构造函数) /* *输入:无 *前置条件:顺序表不存在 *功能:构建一个顺序表 *输出:无 *后置条件:表长为0 */ 实现代码: template SeqList { length=0; } (3)顺序表的建立算法(带参数的构造函数) /* *输入:顺序表信息的数组形式a[],顺序表长度n *前置条件:顺序表不存在 *功能:将数组a[]中元素建为长度为n的顺序表*输出:无 *后置条件:构建一个顺序表 */ 实现代码: template SeqList { if (n>MaxSize) { cout<<"数组元素个数不合法"< } for (int i=0; i data[i]=a[i]; length=n; }(4)在顺序表的第i个位置前插入元素e算法 /* *输入:插入元素e,插入位置i *前置条件:顺序表存在,i要合法 *功能:将元素e插入到顺序表中位置i处 *输出:无 *后置条件:顺序表插入新元素,表长加1 */ 实现代码: template void SeqList int j; if (length>=MaxSize) { cout<<"溢出"< } if (i<1 || i>length+1) { cout<<"i不合法!"< } for (j=length; j>=i; j--) data[j]=data[j-1]; data[i-1]=item; length++; }(5)删除线性表中第i个元素算法 /* *输入:要删除元素位置i *前置条件:顺序表存在,i要合法 *功能:删除顺序表中位置为i的元素 *输出:无 *后置条件:顺序表册除了一个元素,表长减1 */ 实现代码: template datatype SeqList { int item,j; if (length==0) { cout<<"表为空,无法删除元素!"< } if (i<1 || i>length) { cout<<"i不合法!"< } item=data[i-1];//获得要删除的元素值 for (j=i; j data[j-1]=data[j]; //注意数组下标从0记length--; return item; }(6)遍历线性表元素算法 /* *输入:无 *前置条件:顺序表存在 *功能:顺序表遍历 *输出:输出所有元素 *后置条件:无 */ 实现代码: template void SeqList { if(length==0) { cout<<"表为空,无法输出!"< } for(int i=0;i { cout< } } (7)获得线性表长度算法 /* *输入:无 *前置条件:顺序表存在 *功能:输出顺序表长度 *输出:顺序表长度 *后置条件:无 */ 实现代码: template int SeqList { return Length; } (8)在顺序线性表中查找e值,返回该元素的位序算法/* *输入:查询元素值e *前置条件:顺序表存在 *功能:按值查找值的元素并输出位置 *输出:查询元素的位置 *后置条件:无 */ 实现代码: template int SeqList { for (int i=0; i if (data[i]==item) return i+1 ; //下标为i的元素等于item,返回其序号i+1 return 0; //查找失败 } (9)获得顺序线性表第i个元素的值 /* *输入:查询元素位置i *前置条件:顺序表存在,i要合法 *功能:按位查找位置为i的元素并输出值 *输出:查询元素的值 *后置条件:无 */ 实现代码: template datatype SeqList { if (i<0||i>length) { cout<<"i不合法!"< } else return data[i-1]; } (10)判表空算法 /* *输入:无 *前置条件:无 *功能:判表是否为空 *输出:为空返回1,不为空返回0 *后置条件:无 */ 实现代码: template bool SeqList { if (length==0) { return 1; } else { return 0; } } (11)求直接前驱结点算法 /* *输入:要查找的元素e,待存放前驱结点值e1 *前置条件:无 *功能:查找该元素的所在位置,获得其前驱所在位置。 *输出:返回其前驱结点的位序。 *后置条件:e1值为前驱结点的值 */ 实现代码: template int SeqList { int k=Locate(item)-1; if (k>0) return k; else { cout<<"无前驱结点!"< return 0; } } (12)求直接后继结点算法 /* *输入:要查找的元素e,待存放后继结点值e1 *前置条件:无 *功能:查找该元素的所在位置,获得其后继所在位置。 *输出:返回其后继结点的位序。 *后置条件:e1值为后继结点的值 */ 实现代码: template int SeqList { int k=Locate(item)+1; if (k>length) { cout<<"无后继结点!"< return 0; } else { return k; } } 上机实现以上基本操作,写出main()程序: 用以上基本操作算法,实现A=AUB算法。(利用函数模板实现)/* *输入:集合A,集合B *前置条件:无 *功能:实现A=AUB *输出:无 *后置条件:A中添加了B中的元素。 */ 实现代码: template SeqList if (item.Empty()) return *this; else { int k=item.Length(); int num=this->Length(); for (int i=1;i<=k;i++) { for(int j=0;j if (data[j]==item.Get(i)) { break; } else if (num-1==j&&data[num-1]!=item.Get(i)) { this->Insert(++num,item.Get(i)); } } return *this; } } void main() { SeqList cout<<"A∪B的结果是:"< A.Insert(1,1); A.Insert(2,2); A.Insert(3,3); A.Insert(4,4); A.Insert(5,5); //插入集合A中元素 B.Insert(1,2); B.Insert(2,6); B.Insert(3,1); B.Insert(4,8); B.Insert(5,9); //插入集合B中元素 A.Add(B); A.display(); cout< } 实现代码: template void SeqList { int num=this->Length(); for (int i=0;i { if ((data[i] { for (int k=num;k>i;k--) data[k]=data[k-1]; data[i+1]=item; length++; break; } if (data[i]>item) { for(int k=num;k>i;k--) data[k]=data[k-1]; data[i]=item; length++; break; } } } void main() { SeqList A.Insert(1,3); A.Insert(2,5); A.Insert(3,6); A.Insert(4,8); A.Insert(5,10); //插入顺序表 cout<<"原顺序表为:"< A.display(); //输出顺序表 cout< A.orderInsert(2); A.orderInsert(4); //插入元素 cout<<"插入新元素后的顺序表为:"< A.display(); //输出重新排序后的顺序表 } 算法实现:La,Lb为非递减的有序线性表,将其归并为Lc,该线性表仍有序(未考虑相同时删除一重复值)(利用函数类板实现) MergeList: /* *输入:有序线性表La,有序线性表Lb *前置条件:顺序表已有序 *功能:将两线性表归并,不去掉相同元素 *输出:返回一个新的有序线性表Lc *后置条件:无 */ 实现代码: template SeqList { int num=Seq2.Length(); for(int i=0;i<=num;i++){ Seq1.orderInsert(Seq2.Get(i)); } return Seq1; } void main() { SeqList La.Insert(1,2); La.Insert(2,4); La.Insert(3,6); La.Insert(4,8); //插入La cout<<"La中元素为:"< La.display(); //输出La cout< Lb.Insert(1,3); Lb.Insert(2,6); Lb.Insert(3,8); //插入Lb cout<<"Lb中元素为:"< Lb.display(); //输出Lb cout< Lc=Lc.ElseAdd(La,Lb); //合并两线性表 cout<<"合并后的Lc为:"< Lc.display(); //输出合并后的线性表 cout< } E x c e l工作表的建立和编辑 等基本操作 -标准化文件发布号:(9556-EUATWK-MWUB-WUNN-INNUL-DDQTY-KII Excel工作表的建立和编辑等基本操作(2课时) 教学目的: 学习excel的使用,初步了解工作表的建立和编辑操作。 教学重点: 工作表的数据输入(包括不同文本、数值、日期等类型,有规律数据的输入,公式的编辑),工作表的格式设置(包括字体、对齐、边框和图案的设置)。 教学难点: 电子表格自动填充和公式编辑、函数应用。 上机任务 2 任务一:建立一个成绩表并简单设置格式 1、运行Excel,创建一个工作簿文件,文件命名为“学生成绩.xls”; 2、在sheet1中输入如下图所示的数据。注意,学号采用自动填充的功能快速输入; 3 3、在第1行上面插入一行,在A1单元格中输入标题“2009级学生入学成绩表”,将A1到I1单元格合并居中,设置标题为黑体、16号字、红色,单元格背景色为浅黄色; 4 4、在学号为“20080008”的记录前插入一行,任意输入数据。 5、删除学号为“20080006”的那一行。 6、将所有学号中的“2008”改为“2009”。 7、运用函数或公式计算出每个学生的“总分、平均分”,填入相应的单元格中。 8、分别在A11和A12单元格输入“最高分”、“最低分”,求出所有学生中各门课程的最高分和最低分,填入相应的单元格中。 9、设置表中各单元格水平居中对齐、垂直居中对齐。 10、设置第1行的行高为30,其余各行行高为16;列宽为“最适合的列宽”。 11、设置平均分列中的数值格式为保留2位小数位数。 5 实验1 线性表的基本操作 一、需求分析 目的: 掌握线性表运算与存储概念,并对线性表进行基本操作。 1.初始化线性表; 2.向链表中特定位置插入数据; 3.删除链表中特定的数据; 4.查找链表中的容; 5.销毁单链表释放空间; 二、概要设计 ●基础题 主要函数: 初始化线性表InitList(List* L,int ms) 向顺序表指定位置插入元素InsertList(List* L,int item,int rc)删除指定元素值的顺序表记录DeleteList1(List* L,int item) 删除指定位置的顺序表记录 DeleteList2(List* L,int rc) 查找顺序表中的元素 FindList(List L,int item) 输出顺序表元素OutputList(List L) 实验步骤: 1,初始化顺序表 2,调用插入函数 3,在顺序表中查找指定的元素 4,在顺序表中删除指定的元素 5,在顺序表中删除指定位置的元素 6,遍历并输出顺序表 ●提高题 要求以较高的效率实现删除线性表中元素值在x到y(x和y自定义)之间的所有元素 方法: 按顺序取出元素并与x、y比较,若小于x且大于y,则存进新表中。 编程实现将两个有序的线性表进行合并,要求同样的数据元素只出现一次。 方法: 分别按顺序取出L1,L2的元素并进行比较,若相等则将L1元素放进L中,否则将L 1,L2元素按顺序放进L。 本程序主要包含7个函数 主函数main() 初始化线性表InitList(List* L,int ms) 向顺序表指定位置插入元素InsertList(List* L,int item,int rc)删除指定元素值的顺序表记录DeleteList1(List* L,int item) 删除指定位置的顺序表记录 DeleteList2(List* L,int rc) 查找顺序表中的元素 FindList(List L,int item) 输出顺序表元素OutputList(List L) 提高题的程序 void Combine(List* L1,List* L2,List* L) void DeleteList3(List* L,int x,int y) 二、详细设计 初始化线性表InitList(List* L,int ms) void InitList(List* L,int ms) { L->list=(int*)malloc(LIST_INIT_SIZE*sizeof(int)); L->size=0; L->MAXSIZE=LIST_INIT_SIZE; 数据结构 实验1:线性表的基本操作及其应用 班级:RB软工移151 学号:201560140140 姓名:袁若飞 实验一线性表 一、实验目的 1、帮助读者复习C++语言程序设计中的知识。 2、熟悉线性表的逻辑结构。 3、熟悉线性表的基本运算在两种存储结构上的实现,其中以熟悉链表的操作为侧重点。 二、实验内容 本次实验提供4个题目,每个题目都标有难度系数,*越多难度越大,题目一、二是必做题。题目三、题目四选作。 三、实验准备知识 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、掌握线性表的逻辑结构。 3、掌握线性表的链式存储结构。 4、熟练掌握线性表的插入、删除等操作。 实现顺序表的各种基本运算 一、实验目的 了解顺序表的结构特点及有关概念,掌握顺序表的各种基本操作算法思想及其实现。 二、实验内容 编写一个程序,实现顺序表的各种基本运算: 1、初始化顺序表; 2 、顺序表的插入; 3、顺序表的输出; 4 、求顺序表的长度 5 、判断顺序表是否为空; 6 、输出顺序表的第i位置的个元素; 7 、在顺序表中查找一个给定元素在表中的位置; 8、顺序表的删除; 9 、释放顺序表 三、算法思想与算法描述简图 主函数main 四、实验步骤与算法实现 #in clude 山东师范大学 实验报告 课程:数据结构班级:2016级通信2班实验序号: 1 姓名:韩明达 学号: 201611030230 实验日期:9.17 题目: 顺序表的建立和运算 一、实验目的和要求 (1)熟悉C语言的上机环境,进一步掌握C语言的结构特点。 (2)掌握线性表的顺序存储结构的定义及基本运算 二、实验环境 Windows10,Visual Studio 2017 三、实验内容及实施 实验内容 1、建立一个顺序表,输入n个元素并输出; 2、查找线性表中的最大元素并输出; 3、在线性表的第i个元素前插入一个正整数x; 4、删除线性表中的第j个元素; 5、将线性表中的元素按升序排列; 【程序流程图】 【程序】 #include 实验一线性表的基本操作 一、实验目的 1. 熟悉C/C++语言上机环境; 2. 掌握线性表的基本操作:查找、插入、删除等运算在顺序存储、链式存储结构上的运算。 二、实验环境 1. 装有Visual C++6.0的计算机。 2. 本次实验共计2学时。 三、实验内容 1. 建立顺序表,基本操作包括:初始化、建立顺序表、输出顺序表、判断是否为空、取表中第i个元素、查找、插入和删除。并在主函数中完成对各种函数的测试。 2. 设有两个非递增有序的线性表A和B,均已顺序表作为存储结构。编写算法实现将A表和B表合并成一个非递增有序排列的线性表(可将线性表B插入线性表A中,或重新创建线性表C)。 3. 建立单链表,基本操作包括:初始化、判断是否为空、取表中第i个元素、查找、插入和删除。并在主函数中完成对各种函数的测试。 四、源程序 #include Excel工作表的建立和编辑等基本操作(2课时) 教学目的: 学习excel的使用,初步了解工作表的建立和编辑操作。 教学重点: 工作表的数据输入(包括不同文本、数值、日期等类型,有规律数据的输入,公式的编辑),工作表的格式设置(包括字体、对齐、边框和图案的设置)。 教学难点: 电子表格自动填充和公式编辑、函数应用。 上机任务 1 任务一:建立一个成绩表并简单设置格式 1、运行Excel,创建一个工作簿文件,文件命名为“学生成绩.xls”; 2、在sheet1中输入如下图所示的数据。注意,学号采用自动填充的功能快速输入;2 3、在第1行上面插入一行,在A1单元格中输入标题“2009级学生入学成绩表”,将A1到I1单元格合并居中,设置标题为黑体、16号字、红色,单元格背景色为浅黄色; 4、在学号为“20080008”的记录前插入一行,任意输入数据。 3 5、删除学号为“20080006”的那一行。 6、将所有学号中的“2008”改为“2009”。 7、运用函数或公式计算出每个学生的“总分、平均分”,填入相应的单元格中。 8、分别在A11和A12单元格输入“最高分”、“最低分”,求出所有学生中各门课程的最高分和最低分,填入相应的单元格中。 9、设置表中各单元格水平居中对齐、垂直居中对齐。 10、设置第1行的行高为30,其余各行行高为16;列宽为“最适合的列宽”。 11、设置平均分列中的数值格式为保留2位小数位数。 12、为该表增加表格线(不包括标题行),内网格线为最细的实线,粉红色;外框线为最粗的实线,橙色。 4 13、将第2行的所有字符的字体设置为楷体、加粗,字号为14,颜色设置为红色,填充背景色为青绿色。 14、对“张三”插入批注,批注为“该生已转专业。” 15、把sheet1命名为“入学成绩表”; 16、保存文件并提交作业。 参考效果图如下: 5 实验一:线性表的基本操作 【实验目的】 学习掌握线性表的顺序存储结构、链式存储结构的设计与操作。对顺序表建立、插入、删除的基本操作,对单链表建立、插入、删除的基本操作算法。 【实验内容】 1.顺序表的实践 1) 建立4个元素的顺序表s=sqlist[]={1,2,3,4,5},实现顺序表建立 的基本操作。 2) 在sqlist []={1,2,3,4,5}的元素4和5之间插入一个元素9,实现 顺序表插入的基本操作。 3) 在sqlist []={1,2,3,4,9,5}中删除指定位置(i=5)上的元素9, 实现顺序表的删除的基本操作。 2.单链表的实践 3.1) 建立一个包括头结点和4个结点的(5,4,2,1)的单链表,实现单链 表建立的基本操作。 2) 将该单链表的所有元素显示出来。 3) 在已建好的单链表中的指定位置(i=3)插入一个结点3,实现单链表插 入的基本操作。 4) 在一个包括头结点和5个结点的(5,4,3,2,1)的单链表的指定位置 (如i=2)删除一个结点,实现单链表删除的基本操作。 5) 实现单链表的求表长操作。 【实验步骤】 1.打开VC++。 2.建立工程:点File->New,选Project标签,在列表中选Win32 Console Application,再在右边的框里为工程起好名字,选好路径,点OK->finish。至此工程建立完毕。 3.创建源文件或头文件:点File->New,选File标签,在列表里选C++ Source File。给文件起好名字,选好路径,点OK。至此一个源文件就被添加到了刚创 建的工程之中。 4.写好代码 5.编译->链接->调试 1、#include "stdio.h" #include "malloc.h" #define OK 1 #define OVERFLOW -2 #define ERROR 0 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef int ElemType; typedef int Status; typedef struct { ElemType *elem; int length; int listsize; } SqList; Status InitList( SqList &L ) { int i,n; L.elem = (ElemType*) malloc (LIST_INIT_SIZE*sizeof (ElemType)); if (!L.elem) return(OVERFLOW); printf("输入元素的个数:"); scanf("%d",&n); printf("输入各元素的值:"); for(i=0;i 《数据结构》实验报告一 顺序表的基本操作 班级:网络工程学号:12015242183 实验日期:2016.9.25 姓名:邓宗永 程序文件名及说明:sequenlist 顺序表 一、实验目的 1、掌握使用Turbo C3.0上机调试线性表的基本方法; 2、掌握顺序表的基本操作:插入、删除、查找以及线性表合并等运算。 二、实验要求 1、认真阅读和掌握实验的程序。 2、上机运行程序。 3、保存和打印出程序的运行结果,并结合程序进行分析。 4、按照你对线性表的操作需要,编写写主程序并运行,打印出文件清单和运行结果 三、注意事项: 在磁盘上创建一个目录,专门用于存储数据结构实验的程序。 四、实验内容 1.顺序表的查找、插入与删除。设计算法,实现线性结构上的顺序表的产生以及元素的查找、插入与删除。具体实现要求: (1)从键盘输入10个整数,产生顺序表,并输入结点值。 (2)从键盘输入1个整数,在顺序表中查找该结点的位置。若找到,输出结点的位置;若找不到,则显示“找不到”。 (3)从键盘输入2个整数,一个表示欲插入的位置i,另一个表示欲插入的数值x,将x 插入在对应位置上,输出顺序表所有结点值,观察输出结果。 (4)从键盘输入1个整数,表示欲删除结点的位置,输出顺序表所有结点值,观察输出结果。 五、实验报告必须写明内容 1.程序设计的基本思想,原理和算法描述:(包括程序的结构,数据结构,输入/输出设 计,符号名说明等) 程序的结构:通过子函数实现输出,删除,插入,查找等功能,高耦合低内聚 数据结构:线性结构,顺序储存 输入/输出设计:根据屏幕提示,从键盘读取数据 2.源程序及注释: #include 实验一线性表基本操作的编程实现 【实验目的】 线性表基本操作的编程实现 要求: 线性表基本操作的编程实现(2学时,验证型),掌握线性表的建立、遍历、插入、删除等基本操作的编程实现,也可以进一步编程实现查找、逆序、排序等操作,存储结构可以在顺序结构或链表结构中任选,可以完成部分主要功能,也可以用菜单进行管理完成大部分功能。还鼓励学生利用基本操作进行一些更实际的应用型程序设计。 【实验性质】 验证性实验(学时数:2H) 【实验内容】 把线性表的顺序存储和链表存储的数据插入、删除运算其中某项进行程序实现。建议实现键盘输入数据以实现程序的通用性。为了体现功能的正常性,至少要编制遍历数据的函数。 【注意事项】 1.开发语言:使用C。 2.可以自己增加其他功能。 【思考问题】 1.线性表的顺序存储和链表存储的差异?优缺点分析? 2.那些操作引发了数据的移动? 3.算法的时间效率是如何体现的? 4.链表的指针是如何后移的?如何加强程序的健壮性? 【参考代码】(以下内容,学生任意选择一个完成即可) (一)利用顺序表完成一个班级学生课程成绩的简单管理 1、预定义以及顺序表结构类型的定义 (1) #include 顺序表的基本操作 /*sqList.h 文件*/ #define LIST_INIT_SIZE 50 /*初始分配的顺序表长度*/ #define INCREM 10 /*溢出时,顺序表长度的增量*/ #define OVERFLOW 1 #define OK 0 #define ERROR -1 typedef int ElemType; /*定义表元素的类型*/ typedef struct SqList{ ElemType *elem; /*存储空间的基地址*/ int length; /*顺序表的当前长度*/ int listsize; /*当前分配的存储空间*/ }SqList; /*sqListOp.h 文件*/ #include "Sqlist.h" int InitList_sq(SqList &L); //顺序表创建函数定义 void FreeList_sq(SqList &L); //顺序表销毁函数定义 int ListInsert_sq(SqList &L, int i, ElemType e); //在顺序表的位置i插入元素e void PrintList_sq(SqList &L); //遍历并输出顺序表所有元素 int ListDelete_sq(SqList &L, int i,ElemType &e); //删除顺序表第i个元素的 bool ListEmpty(SqList &L); //判断顺序表是否为空 int LocateElem_sq(SqList L,ElemType e); //在顺序表里查找出第1个与e相等的数据元素位置//已知线性表La和Lb的元素按值非递减排列 //归并后的La和Lb得到新的顺序线性表Lc,Lc的元素也是按值非递减排列 void MergeList_sq(SqList La,SqList Lb, SqList &Lc); /*sqListOp.cpp文件*/ #include 实验一线性表基本操作 (4课时) 一、实验目的 掌握线性表的顺序表和链表的基本操作:建立、插入、删除、查找、合并、打印等运算。 二、实验要求 1.格式正确,语句采用缩进格式; 2.设计子函数实现题目要求的功能; 3.编译、连接通过,熟练使用命令键; 4.运行结果正确,输入输出有提示,格式美观。 5.输入数据至少三组,分别代表不同的情况,以测试程序的正确性。 6.将运行结果截图,并粘在文档的相应位置。 三、实验环境 1.turboc2,win-tc,VC++ 四、实验内容和步骤 1.编程实现在顺序存储的有序表中插入一个元素。 2.编程实现把顺序表中从i个元素开始的k个元素删除。 3.编程序实现将单链表的数据逆置,即将原表的数据(a1,a2….an)变成(an,…..a2,a1)。4.约瑟夫环问题。 约瑟夫问题的一种描述是:编号为1,2,…,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。一开始任选一个整数作为报数上限值m,从第一个人开始顺时针自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他在顺时针方向上的下一个人开始重新从1报数,如此下去,直至所有的人全部出列为止。试设计一个程序,求出出列顺序。 利用单向循环链表作为存储结构模拟此过程,按照出列顺序打印出各人的编号。 例如m的初值为20;n=7,7个人的密码依次是:3,1,7,2,4,8,4,出列的顺序为6,1,4,7,2,3,5。 五、根据实验过程填写下面内容 1.写出第1题的程序并写出运行结果和分析。 #include "stdio.h" #include "malloc.h" #define OK 1 #define ERROR 0 #define ElemType int #define MAXSIZE 100 typedef struct//顺序表申明 { ElemType elem[MAXSIZE]; int last; }SeqList; 数据结构实验顺序表的实现 姓名 学号 专业班级 实验名称:顺序表的实现 一.实验目的: 1.掌握线性表的顺序存储结构; 2.验证顺序表的基本操作的实现; 3.理解算法与程序的关系,能够将顺序表转换为对应程序; 二.实验内容: 1.建立含有若干元素的顺序表; 2.对已建立的顺序表实现插入、删除、查找等基本操作; 三.算法设计 1.建立顺序表并初始化 1)顺序表的大小为MaxSize,存入元素的下标为n a.如果n>MaxSize,则抛出参数非法; b.将元素a[i]赋值给线性表中元素序号为i的元素; 2.顺序表的插入 1)如果表满了,则抛出上溢异常; 2)如果元素插入的位置不合理,则抛出位置异常; 3)将最后一个元素及第i个元素分别向后移动一个位置; 4)将要插入的元素x填入为位置i处; 5)表长加1; 3.顺序表的删除 1)如果表空,则抛出下一异常; 2)如果删除的位置不合理,则抛出删除位置异常; 3)取出被删元素; 4)将下表为i至n-1的元素分别向前移动1个元素; 5)表长减一,返回被删元素值; 4.顺序表的查找 A.按位查找 1)如果查找的位置不合理,则抛出查找的不合理; 2)返回被查找的元素值; B.按值查找 1)若查找成功,返回被查找元素的序号; 2)若查找失败,则返回0; 四.部分代码 文件名称:SeqList.h #define SEQLIST_H const int MaxSize = 5; template 数据结构实验报告-顺序表的创建、遍历及有序合并操作二、实验内容与步骤 实现顺序表的创建、遍历及有序合并操作,基本数据结构定义如下: typedef int ElemType; #define MAXSIZE 100 #define FALSE 0 #define TRUE 1 typedef struct {ElemType data[MAXSIZE]; int length; }seqlist; 创建顺序表,遍历顺序表 #include #define TRUE 1 typedef int ElemType; //用户自定义数据元素类型 // 顺序表结构体的定义 typedef struct { ElemType *elem; //顺序表的基地址 int length; //顺序表的当前长度 int listsize; //预设空间容量 }SqList; //线性表的顺序存储结构 SqList* InitList() //创建空的顺序表 { SqList* L = (SqList*)malloc(sizeof(SqList));//定义顺序表L if(!L) { printf("空间划分失败,程序退出\n"); return NULL; } L->elem=(ElemType *)malloc(MAXSIZE*sizeof(ElemType)); if(!L->elem) { printf("空间划分失败,程序退出\n"); 实验一:线性表的基本操作 1.实验目的: 1)掌握用VC++上机调试线性表的基本方法; 2)掌握线性表的基本操作,插入、删除、查找,以及线性表合并等运算在顺序存储结构和链接存储结构上的运算。 2.实验内容: 1)线性表建立、插入、删除操作实现; 2)已知有序表SA,SB,其元素均为递增有序,将此两表归并成一个新有序表SC,且SC中的元素仍然递增有序。 #include printf("尾插法建立单链表,输入-1结束\n"); while(flag) { scanf("%d",&c); if(c!=-1) { s=(Node*)malloc(sizeof(Node)); s->data=c; r->next=s; r=s; } else { flag=0; r->next=NULL; } } } void printL(LinkList L) { Node *p; p=L; while(p->next!=NULL) { printf("%d ",p->next->data); p=p->next; } printf("\n"); } int InsertList(LinkList L,int i,int e) { Node *pre,*s; int k; if(i<1) { return ERROR; } pre=L; k=0; while(pre!=NULL&& k 实验二SQL Server数据表的基本操作 一、实验目的 1.掌握创建数据库和表的操作。 2.熟悉SQL Server查询分析器环境。 3.掌握基本的SELECT查询及其相关子句的使用。 4.掌握复杂的SELECT查询,如多表查询、子查询、连接和联合查询。 二、实验内容 1.创建XSCJ数据库。 2.在XSCJ数据库中创建学生情况表XSQK,课程表KC,学生成绩表XS_KC。 3.在XSQK、KC、XS_KC表中输入数据。 4.启动SQL Server 2000 查询分析器环境。 5.涉及多表的简单查询。 6.涉及多表的复杂查询。 三、实验步骤 1.创建SQL SERVER数据库与数据表 1) 创建XSCJ数据库。 2) 打开创建的 XSCJ数据库,并在“SQL Server Enterprise Mananger” 窗口的右边窗口中选择“表”对象。 3) 选择“操作”菜单中的“新建表”命令,打开SQL Server的表编辑器 窗口。 4) 根据表2-1所示的表结构增加新列。 5) 点击快捷工具栏上的保存快捷按钮,在弹出的“选择名称”对话框中 输入表名XSQK,然后单击“确定”按钮,关闭表编辑器窗口,完成新 表的创建。 6) 打开“表”对象,在“SQL Server Enterprise Manager”窗口的右边 窗口中选择刚才创建的“XSQK”表。 7) 选择“操作”菜单中的“打开表”子菜单下的“返回所有行”命令, 打开表的数据记录窗口。 8) 输入的学生情况数据记录见表2-2。 表2-2 学生情况记录 9) 用同样方法创建课程表KC,表的结构见表2-3所示,表的内容见表2-4 所示。 表2-4 课程表记录 10)创建成绩表XS_KC,表的结构见表2-5所示,表的内容见表2-6所 示。 #define OVERFLOW 0 #define List_size 100 #define Listincrement 10 #include creat_Sq(&L); printf("\n"); print_Sq(&L); printf("\n"); ascend(&L,i); print_Sq(&L); printf("\n"); Insert(&L,e); print_Sq(&L); printf("\n"); } Sqlist creat_Sq(Sqlist*L)//创建顺序表 { ElemType *newbase; int i,n; L->elem=(ElemType*)malloc(List_size*sizeof(ElemType)); if(!L->elem) exit(OVERFLOW);//存储分配失败 printf("请输入元数个数:\n"); scanf("%d",&n); if(n>=List_size)//如果所需空间大于线性表的初始空间,则增加空间容量 { newbase=(ElemType*)malloc((List_size+Listincrement)*sizeof(E lemType)); L->elem=newbase; L->length=n; L->listsize=List_size+Listincrement; for(i=0;i 第四章数据库与表的基本操作 实验4-1 数据库及表的操作 (一)实验目的 1.掌握创建数据库的基本操作方法。 2.熟练掌握创建表结构和输入记录的操作方法。 3.熟练掌握修改表结构、浏览和修改表记录数据的操作。 4.熟练掌握建立索引的操作。 5.掌握创建表间联系的操作。 (二)实验内容及步骤 1.创建数据库 【实例4-1】在实验2-1所建立的“教学管理.pjx”项目中,创建一个“学生成绩.dbc”数据库。 操作步骤如下: (1)打开“教学管理.pjx”项目。 (2)在“项目管理器”窗口中,选择“数据库”,然后单击“新建”按钮,打开“新建数据库”对话框,单击其中的“新建数据库”按钮,打开“创建”对话框,如图4-1所示。 图4-1“创建”对话框 (3)在“保存在”文本框中,选择保存数据库的文件夹“程序VX”;在“数据库名”文本框中,输入数据库名称“学生成绩”。 (4)单击“保存”按钮,即在指定位置建立一个“学生成绩.dbc”数据库文件。 此时,在VFP主窗口中弹出一个“数据库设计器”窗口,同时还激活了“数据库设计器”工具栏,如图4-2所示。 18 数据库应用学习与实训指导 图4-2“数据库设计器”窗口 2.创建数据表 【实例4-2】在“教学管理.pjx”项目中,创建学生表(Student.dbf)、成绩表(Grade.dbf)、课程表(Course.dbf)、授课表(Teach.dbf)和教师表(Teacher.dbf)。各个表的结构和数据记录如图4-3、图4-4、图4-5、图4-6、图4-7、图4-8、图4-9、图4-10、图4-11和图4-12所示。 图4-3学生表(Student.dbf)的结构 图4-4学生表(Student.dbf)的记录浏览窗口 实验报告一数据库及表基本操作 姓名:全青青学号:1002010117 班级:无机非一班日期:2 请填入你的班级和做实验的日期。按照《数据库技术及应用——习题与实验指导》第一部分实验指导中“实验三熟悉Access系统集成环境”、“实验四数据库操作”、“实验五表操作”和预习“实验一数据库设计”、“实验二SQL语言应用”的实验内容,边完成各项实验操作,边按要求填写该实验报告。 一、实验目的 1.掌握Access 2003的基本操作。 2.掌握建立一个数据库文件,并对其实施打开与关闭的操作方法。 3.掌握创建表的基本操作方法。 4.掌握对各表完成部分数据操纵的方法。 二、实验报告内容 1.按照P.10实验3-2的操作提示将创建的空数据库命名为“某某的第一个数据库”(注:某某为自 己的姓名),保存位置为以自己姓名命名的文件夹,并将保存文件的对话框粘贴到此: 2.按照P.15实验4-2的操作提示,关闭自己所创建的数据库;再按照P.15实验4-1的操作提示, 找到保存自己所创建的数据库的位置,打开自己所创建的数据库,并将打开文件的对话框粘贴到此: 3.参照P.16实验5-1的操作提示,预习“实验一数据库设计”并根据P.3中实验1-4的8个表结 构逐一定义每个表每个字段的名字、类型、长度等相关内容,并将定义好的每一个表设计视图窗口粘贴到此: 表1-1-1 “学院”表结构(表设计视图窗口) 表1-1-2 “系”表结构(表设计视图窗口) 表1-1-3 “班级”表结构(表设计视图窗口) 表1-1-4 “学生”表结构(表设计视图窗口) 实验一线性表的基本操作实现及其应用 一、实验目的 1、熟练掌握线性表的基本操作在两种存储结构上的实现,其中以熟悉各种链表的操作为重点。 2、巩固高级语言程序设计方法与技术,会用线性链表解决简单的实际问题。 二、实验内容 √1、单链表的表示与操作实现( * ) 2、约瑟夫环问题 3、Dr.Kong的艺术品 三、实验要求 1、按照数据结构实验任务书,提前做好实验预习与准备工作。 2、加“*”题目必做,其他题目任选;多选者并且保质保量完成适当加分。 3、严格按照数据结构实验报告模板和规范,及时完成实验报告。 四、实验步骤 (说明:依据实验内容分别说明实验程序中用到的数据类型的定义、主程序的流程以及每个操作(成员函数)的伪码算法、函数实现、程序编码、调试与分析、总结、附流程图与主要代码) ㈠、数据结构与核心算法的设计描述 (程序中每个模块或函数应加注释,说明函数功能、入口及出口参数) 1、单链表的结点类型定义 /* 定义DataType为int类型*/ typedef int DataType; /* 单链表的结点类型*/ typedef struct LNode { DataType data; struct LNode *next; }LNode,*LinkedList; 2、初始化单链表 LinkedList LinkedListInit( ) { // 每个模块或函数应加注释,说明函数功能、入口及出口参数} 3、清空单链表 void LinkedListClear(LinkedList L) {// 每个模块或函数应加注释,说明函数功能、入口及出口参数} 4、检查单链表是否为空 int LinkedListEmpty(LinkedList L) { …. } 5、遍历单链表 void LinkedListTraverse(LinkedList L) { …. } 6、求单链表的长度 int LinkedListLength(LinkedList L) { ….} 7、从单链表表中查找元素 LinkedList LinkedListGet(LinkedList L,int i) { //L是带头结点的链表的头指针,返回第i 个元素} 8、从单链表表中查找与给定元素值相同的元素在链表中的位置 LinkedList LinkedListLocate(LinkedList L, DataType x) { ……} 9、向单链表中插入元素 void LinkedListInsert(LinkedList L,int i,DataType x) { // L 为带头结点的单链表的头指针,本算法 // 在链表中第i 个结点之前插入新的元素x } 10、从单链表中删除元素 void LinkedListDel(LinkedList L,DataType x) { // 删除以L 为头指针的单链表中第i 个结点} 11、用尾插法建立单链表 LinkedList LinkedListCreat( ) { ……} 实验目的及要求: 了解和掌握顺序表的特点; 掌握顺序表基本操作的实现; 要求完成顺序表的初始化、插入、删除、显示操作的实现。实验设备环境及要求: PC机一台,内存要求128M以上,VC++6.0集成开发环境。实验内容与步骤: 1、在VC++6.0环境中新建一个工程和C++文件; 2、实现顺序表初始化、插入、删除算法,代码如下: #include Excel工作表的建立和编辑等基本操作
数据结构_实验1_线性表的基本操作
201560140140--袁若飞--实验1:线性表的基本操作及其应用
数据结构实现顺序表的各种基本运算(20210215233821)
顺序表的建立及其基本操作技巧
实验一 线性表的基本操作
Excel工作表的建立和编辑等基本操作
线性表的基本操作实验报告
顺序表的基本操作
实验一 线性表基本操作的编程实现
顺序表的基本操作 (2)
实验一 线性表基本操作
顺序表的实现
数据结构实验报告-顺序表的创建、遍历及有序合并操作
线性表的基本操作
实验二 SQL Server 数据表的基本操作与查询
顺序表的基本操作(C语言实现)
数据库与表的基本操作
实验报告1 数据库及表基本操作
《数据结构》实验报告模板附实例实验一线性表的基本操作实现.doc
实验报告01-顺序表的基本操作