顺序表的按值插入

实验报告附：源程序：#include<stdio.h>#define Maxsize 100#define error 0#define ok 1typedef struct{int elem[Maxsize];int last;}SeqList;int InsList(SeqList *L,int a,int i); int Locate(SeqList L,int e);int Del(SeqList *L,int i);void main(){int i,e,a;int list1,list2;SeqList L;st=0;for(i=0;i<100;i++){printf("请输入顺序表元素\n");scanf("%d",&L.elem[i]);if(L.elem[i]==-1)break;st++;}if(L.elem[st]==-1)st--;printf("要插入的元素,位置为\n"); scanf("%d,%d",&a,&i);list1=InsList(&L,a,i);if(list1){printf("插入后的顺序表为:\n");for(i=0;i<=st;i++)printf("%d",L.elem[i]);printf("\n");}elseprintf("插入失败！");printf("要查找的元素为\n");scanf("%d",&e);list2=Locate(L,e);if(!list2)printf("该元素不存在\n");elseprintf("该元素所在位置的序号为:%d\n",list2);/*删除元素*/printf("是否要删除该元素？<是请输入1 ，否请输入0 >\n");int m;scanf("%d",&m);if(m){Del(&L,list2);printf("删除后的顺序表为:\n");for(i=0;i<=st;i++)printf("%d",L.elem[i]);printf("\n");}else printf("未删除元素%d\n",e);}int InsList(SeqList *L,int a,int i)//i位置，下标i-1{int p;if(L->last>=Maxsize-1){printf("表已满，无法插入");return(error);}for(p=L->last;p>=i-1;p--)L->elem[p+1]=L->elem[p];L->elem[i-1]=a;L->last++;return(ok);}int Locate(SeqList L,int e){int i=0;while((i<=st)&&(L.elem[i]!=e)) i++;if (i<=st)return(i+1);else return(error);}int Del(SeqList *L,int i){int k;for(k=i;k<=L->last;k++)L->elem[k-1]=L->elem[k];L->last--;return ok;}。

实现顺序表的各种基本运算的算法1. 初始化顺序表算法实现：初始化操作就是将顺序表中所有元素的值设置为默认值，对于数值类型，可以将其设置为0，对于字符类型，可以将其设置为空格字符。

初始化的时间复杂度为O(n)，其中n为顺序表的长度。

2. 插入操作算法实现：顺序表的插入操作就是在指定位置上插入一个元素，需要将该位置后面的元素全部后移，在指定位置上插入新元素。

若顺序表已满，则需要进行扩容操作，将顺序表长度扩大一倍或者按一定的比例扩大。

插入操作的时间复杂度为O(n)，其中n为顺序表长度。

3. 删除操作算法实现：顺序表的删除操作需要将指定位置上的元素删除，并将该位置后面的元素全部前移。

删除操作后，如果顺序表的实际长度小于等于其总长度的1/4，则需要进行缩容操作，将顺序表长度缩小一倍或者按一定的比例缩小。

删除操作的时间复杂度为O(n)，其中n为顺序表长度。

4. 修改操作算法实现：顺序表的修改操作就是将指定位置上的元素赋予新的值。

修改操作的时间复杂度为O(1)。

5. 查找操作算法实现：顺序表的查找操作就是在顺序表中找到指定位置的元素，并返回其值。

查找操作的时间复杂度为O(1)。

6. 遍历操作算法实现：顺序表的遍历操作就是依次访问顺序表中的每个元素，遍历操作的时间复杂度为O(n)，其中n为顺序表的长度。

7. 合并操作算法实现：顺序表的合并操作就是将两个顺序表合并成一个新的顺序表，新的顺序表的长度为两个顺序表的长度之和。

合并操作的时间复杂度为O(n)，其中n为两个顺序表的长度之和。

总结：顺序表是一种简单而高效的数据结构，其基本运算包括初始化、插入、删除、修改、查找、遍历和合并等操作。

其中，插入、删除、遍历和合并操作的时间复杂度比较高，需要进行相应的优化处理。

同时，在实际应用中，还需要注意顺序表的扩容和缩容操作，避免造成资源浪费或者性能下降。

云南大学物理实验教学中心实验报告课程名称：计算机软件技术基础实验项目：实验二、线性表（顺序存储）及其应用学生姓名：学号：学院系级专业成绩指导教师：实验时间：年日时分至时分实验地点：实验类型：教学（演示□验证□综合█设计□）学生科研□课外开放□测试□其它□一、实验目的：掌握顺序表的建立及基本操作。

二、问题：建立一个顺序表，表中元素为学生，每个学生信息包含姓名、学号和成绩三部分，对该表实现：①输出、②插入、③删除、④查找功能，并计算出平均成绩和总成绩。

三、程序的编写与调试1、原程序：#include <iostream>using namespace std;typedef struct{ long double num; char name[10]; int score; } STUDENT; class sq_LList{ private:int mm;int nn;STUDENT *v;public:sq_LList(int);void prt_sq_LList();void ins_sq_LList(int, STUDENT);void del_sq_LList(int);void sea_num_sq_LList(int);voidvoid cal_sq_LList(int);};/*输出*/sq_LList ::sq_LList(int m){ mm=m;v=new STUDENT [mm];v[0].num=970156; strcpy(v[0].name,"张小明"); v[0].score=87; v[1].num=970157; strcpy(v[1].name,"李小青"); v[1].score=96;v[2].num=970158; strcpy(v[2].name,"刘华");v[2].score=85; v[3].num=970159; strcpy(v[3].name,"王伟");v[3].score=93; v[4].num=970160; strcpy(v[4].name,"李启明"); v[4].score=88;nn=5;}void sq_LList ::prt_sq_LList(){ int i;for(i=0; i<nn; i++){ cout<<"学号: "<<v[i].num<<" 姓名: "<<v[i].name<<" "<<"分数: "<<v[i].score<<endl;}}/*插入*/void sq_LList ::ins_sq_LList(int i, STUDENT b){ int k;if(nn==mm){cout<<"overflow"; return ;}if(i>nn) i=nn+1;if(i<1) i=1;for(k=nn; k>=i; k--)v[k]=v[k-1];v[i-1]=b; nn=nn+1;}/*删除*/void sq_LList ::del_sq_LList(int i){ int k;if(nn==0){cout<<"underflow"<<endl; return ;}if((i<1)||(i>nn)){cout<<"Not this element in the list!"<<endl; return ;}for(k=i; k<nn; k++)v[k-1]=v[k];nn=nn-1;}/*按学号查找*/void sq_LList ::sea_num_sq_LList(int i){ int k,t ;＿＿＿＿t=0;for(i=0;i<nn;i++){ if(v[i].num==k){ t=t+1;cout<<"学号: "<<v[i].num<<" 姓名: "<<v[i].name<<" "<<"分数: "<<v[i].score<<endl;}}if(t==0)cout<<"No this student in the list!"<<endl;}/*按姓名查找*/void sq_LList ::sea_name_sq_LList(int i, char y[]){ int t;＿＿＿＿t=0;for(i=0;i<nn;i++){ if(strcmp(y,v[i].name)=0){t=t+1cout<<"学号: "<<v[i].num<<" 姓名: "<<v[i].name<<" "<<"分数: "<<v[i].score<<endl;}}if(t==0) cout<<"No this student in the list!"<<endl }/*计算*/void sq_LList ::cal_sq_LList(int m){ int i;float sum,avr;{ sum=0;for(i=0;i<nn;i++){sum=sum+v[i].score;avr=sum/(i+1);}}cout<<"总分："<<sum<<endl；cout<<"平均分："<<avr<<endl;}int main(){ int mx; sq_LList s1(100);while (1){ cout<<"1.输出 2.插入 3.删除 4.查找 5.计算 0.退出\n";cout<<"输入0-5:";cin>>mx;switch(mx){ case 1: s1.prt_sq_LList(); break;case 2: int i; STUDENT b;cout<<"输入插入点位置和插入元素值：";cin>>i>>b.num>>>>b.score;s1.ins_sq_LList(i,b); s1.prt_sq_LList(); break; case 3: cout<<"请输入删除学生的位置：";cin>>i;s1.del_sq_LList(i);s1.prt_sq_LList(); break; case 4: int main(){ int mx;while (1){cout<<"1.按学号查找 2.按姓名查找 0.返"<<endl;cout<<"输入0-2：";cin>>mx;switch (mx){casecout<<"请输入要查找学生的学号:";s1.sea_num_sq_LList(i); break;casecout<<"请输入要查找学生的姓名:";s1.sea_name_sq_LList(); break;case 0: cout<<"返回"<<endl; return ;}}return 0;} break;case 5: s1.cal_sq_LList(); break;case 0: cout<<"程序结束"<<endl; return 0;}}return 0;2、正确程序：#include <iostream>using namespace std;typedef struct{ long double num; char name[10]; int score; } STUDENT; class sq_LList{ private:int mm;int nn;STUDENT *v;public:sq_LList(int);void prt_sq_LList();void ins_sq_LList(int, STUDENT);void del_sq_LList(int);void sea_num_sq_LList(int);void sea_name_sq_LList();void cal_sq_LList(int);/*输出*/sq_LList ::sq_LList(int m){ mm=m;v=new STUDENT [mm];v[0].num=970156; strcpy(v[0].name,"张小明"); v[0].score=87; v[1].num=970157; strcpy(v[1].name,"李小青"); v[1].score=96;v[2].num=970158; strcpy(v[2].name,"刘华");v[2].score=85; v[3].num=970159; strcpy(v[3].name,"王伟");v[3].score=93; v[4].num=970160; strcpy(v[4].name,"李启明"); v[4].score=88;nn=5;}void sq_LList ::prt_sq_LList(){ int i;for(i=0; i<nn; i++){ cout<<"学号: "<<v[i].num<<" 姓名: "<<v[i].name<<" "<<"分数: "<<v[i].score<<endl;}}/*插入*/void sq_LList ::ins_sq_LList(int i, STUDENT b){ int k;if(nn==mm){cout<<"overflow"; return ;}if(i>nn) i=nn+1;if(i<1) i=1;for(k=nn; k>=i; k--)v[k]=v[k-1];v[i-1]=b; nn=nn+1;}/*删除*/void sq_LList ::del_sq_LList(int i){ int k;if(nn==0){cout<<"underflow"<<endl; return ;}if((i<1)||(i>nn)){cout<<"Not this element in the list!"<<endl; return ;}for(k=i; k<nn; k++)v[k-1]=v[k];nn=nn-1;}/*按学号查找*/void sq_LList ::sea_num_sq_LList(int i){ int k,t ;cin>>k;t=0;for(i=0;i<nn;i++){ if(v[i].num==k){ t=t+1;cout<<"学号: "<<v[i].num<<" 姓名: "<<v[i].name<<" "<<"分数: "<<v[i].score<<endl;}}if(t==0)cout<<"No this student in the list!"<<endl;}/*按姓名查找*/void sq_LList ::sea_name_sq_LList(){ char y[10]; int i,t;cin>>y;t=0;for(i=0;i<nn;i++){ if(strcmp(y,v[i].name)==0){t=t+1;cout<<"学号: "<<v[i].num<<" 姓名: "<<v[i].name<<" "<<"分数: "<<v[i].score<<endl;}}if(t==0) cout<<"No this student in the list!"<<endl; }/*计算*/void sq_LList ::cal_sq_LList(int m){ int i;float sum,avr;{ sum=0;for(i=0;i<nn;i++){sum=sum+v[i].score;avr=sum/(i+1);}}cout<<"总分："<<sum<<endl;cout<<"平均分："<<avr<<endl;}int main(){ int mx; sq_LList s1(100);while (1){ cout<<"1.输出 2.插入 3.删除 4.查找 5.计算 0.退出\n";cout<<"输入0-5:";cin>>mx;switch(mx){ case 1: s1.prt_sq_LList(); break;case 2: int i; STUDENT b;cout<<"输入插入点位置和插入元素值：";cin>>i>>b.num>>>>b.score;s1.ins_sq_LList(i,b); s1.prt_sq_LList(); break; case 3: cout<<"请输入删除学生的位置：";cin>>i;s1.del_sq_LList(i);s1.prt_sq_LList(); break; case 4:{ int mx;while (1){cout<<"1.按学号查找 2.按姓名查找 0.返"<<endl;cout<<"输入0-2：";cin>>mx;switch (mx){case 1: cout<<"请输入要查找学生的学号:";s1.sea_num_sq_LList(i); break;case 2: cout<<"请输入要查找学生的姓名:";s1.sea_name_sq_LList(); break;case 0: cout<<"返回"<<endl; return 0;}}return 0;} break;case 5: s1.cal_sq_LList(i); break;case 0: cout<<"程序结束"<<endl; return 0;}}return 0;}四、实验总结通过此次试验，我对线性表（顺序存储）有了全面的认识，知道了什么是线性表，以及线性表有什么作用；并学会了如何根据要求建立一个实际的线性表，包括线性表的输出、插入、删除、查。

元素之后的所有数据都前移一个位置，最将线性表长减1。

3．顺序表查找操作的基本步骤：要在顺序表中查找一个给定值的数据元素则可以采用顺序查找的方法，从表中第 1 个数据元素开始依次将值与给定值进行比较，若相等则返回该数据元素在顺序表中的位置，否则返回0 值。

线性表的动态分配顺序存储结构—C语言实现#define MaxSize 50//存储空间的分配量Typedef char ElemType；Typedef struct{ElemType data[MaxSize];int length; //表长度（表中有多少个元素）}SqList;动态创建一个空顺序表的算法：void InitList(SqList *&L) //初始化线性表{L=(SqList *)malloc(sizeof(SqList)); //分配存放线性表的空间L->length=0; //置空线性表长度为0}线性表的插入：status Sqlist_insert(Sqlist &L,int i,Elemtype x)/*在顺序表L中第i个元素前插入新元素x*/{ if (i<1||i>L.length+1) return ERROR; /*插入位置不正确则出错*/if (L.length>=MAXLEN)return OVERFLOW;/*顺序表L中已放满元素，再做插入操作则溢出*/for(j=L.length-1;j>=i-1;j--)L.elem[j+1]=L.elem[j]; /*将第i个元素及后续元素位置向后移一位*/L.elem[i-1]=x; /*在第i个元素位置处插入新元素x*/L.length++; /*顺序表L的长度加1*/return OK;}线性表的删除：status Sqlist_delete(Sqlist &L,int i,Elemtype &e)/*在顺序表L中删除第i个元素*{ if (i<1||i>L.length) return ERROR; /*删除位置不正确则出错*/for(j=i;j<=L.length-1;j++)L.elem[j-1]=L.elem[j]; /*将第i+1个元素及后继元素位置向前移一位*/L.length--;/*顺序表L的长度减1*/return OK；}线性表元素的查找：int LocateElem(SqList *L, ElemType e) //按元素值查找{int i=0;while (i<L->length && L->data[i]!=e)i++; //查找元素eif (i>=L->length) //未找到时返回0return 0;elsereturn i+1; //找到后返回其逻辑序号}输出线性表：void DispList(SqList *L) //输出线性表{int i;if (ListEmpty(L)) return;for (i=0;i<L->length;i++)printf("%c ",L->data[i]);printf("\n");}输出线性表第i个元素的值：bool GetElem(SqList *L,int i,ElemType &e)//求线性表中某个数据元素值{if (i<1 || i>L->length)return false; //参数错误时返回falsee=L->data[i-1]; //取元素值return true; //成功找到元素时返回true}代码：#include <stdio.h>#include <malloc.h>#define MaxSize 50typedef char ElemType;typedef struct{ElemType data[MaxSize];int length;} SqList;void InitList(SqList *&L);void DestroyList(SqList *L);bool ListEmpty(SqList *L);int ListLength(SqList *L);void DispList(SqList *L);bool GetElem(SqList *L,int i,ElemType &e);int LocateElem(SqList *L, ElemType e);bool ListInsert(SqList *&L,int i,ElemType e);bool ListDelete(SqList *&L,int i,ElemType &e);void InitList(SqList *&L)//初始化线性表{L=(SqList *)malloc(sizeof(SqList));//分配存放线性表的空间L->length=0;//置空线性表长度为0 }void DestroyList(SqList *L)//销毁线性表{free(L);}bool ListEmpty(SqList *L)//判线性表是否为空表{return(L->length==0);}int ListLength(SqList *L)//求线性表的长度{return(L->length);}void DispList(SqList *L)//输出线性表{int i;if (ListEmpty(L)) return;for (i=0;i<L->length;i++)printf("%c ",L->data[i]);printf("\n");}bool GetElem(SqList *L,int i,ElemType &e)//求线性表中某个数据元素值{if (i<1 || i>L->length)return false;//参数错误时返回falsee=L->data[i-1];//取元素值return true;//成功找到元素时返回true}int LocateElem(SqList *L, ElemType e)//按元素值查找{int i=0;while (i<L->length && L->data[i]!=e)i++;//查找元素eif (i>=L->length)//未找到时返回0return 0;elsereturn i+1;//找到后返回其逻辑序号}bool ListInsert(SqList *&L,int i,ElemType e)//插入数据元素{int j;if (i<1 || i>L->length+1)return false;//参数错误时返回falsei--;//将顺序表逻辑序号转化为物理序号for (j=L->length;j>i;j--)//将data[i]及后面元素后移一个位置L->data[j]=L->data[j-1];L->data[i]=e;//插入元素eL->length++;//顺序表长度增1return true;//成功插入返回true}bool ListDelete(SqList *&L,int i,ElemType &e)//删除数据元素{int j;if (i<1 || i>L->length)//参数错误时返回falsereturn false;i--;//将顺序表逻辑序号转化为物理序号e=L->data[i];for (j=i;j<L->length-1;j++)//将data[i]之后的元素前移一个位置L->data[j]=L->data[j+1];L->length--;//顺序表长度减1return true;//成功删除返回true}void main(){SqList *L;ElemType e;printf("顺序表的基本运算如下:\n");printf(" (1)初始化顺序表L\n");InitList(L);printf(" (2)依次采用尾插法插入a,b,c,d,e元素\n");ListInsert(L,1,'a');ListInsert(L,2,'b');ListInsert(L,3,'c');ListInsert(L,4,'d');ListInsert(L,5,'e');printf(" (3)输出顺序表L:");DispList(L);printf(" (4)顺序表L长度=%d\n",ListLength(L));printf(" (5)顺序表L为%s\n",(ListEmpty(L)?"空":"非空"));GetElem(L,3,e);printf(" (6)顺序表L的第3个元素=%c\n",e);实验结果：心得体会：通过本次实验，实现了数据结构在程序设计上的作用，了解了数据结构语言，加深了对c语言的认识掌并掌握了线性表的顺序存储结构的表示和实现方法，掌握顺序表基本操作的算法实现，同时了解了顺序表的应用。

c语言实现顺序表的增删查改逆置简单代码1. 顺序表的定义顺序表是一种线性表，其元素在内存中按顺序存储，每个元素占用连续的存储单元。

顺序表的特点是存取速度快，但插入和删除元素时需要移动大量的元素。

顺序表可以用结构体来表示，其定义如下：typedef struct_SeqList {int*data; // 指向数据元素的指针int size; // 顺序表的长度int capacity; // 顺序表的容量} SeqList;2. 顺序表的初始化顺序表的初始化需要分配内存空间来存放数据元素。

可以使用以下代码来初始化顺序表：SeqList*init_seq_list(int capacity) {SeqList*list= (SeqList*)malloc(sizeof(SeqList));if (list==NULL) {return NULL;}list->data= (int*)malloc(sizeof(int) *capacity);if (list->data==NULL) {free(list);return NULL;}list->size=0;list->capacity=capacity;return list;}3. 顺序表的插入在顺序表中插入元素需要移动后面的元素，以保证元素的顺序性。

可以使用以下代码在顺序表中插入元素：int insert_seq_list(SeqList*list, int index, int value) {if (index<0||index>list->size) {return-1;}if (list->size==list->capacity) {// 扩容顺序表int*new_data= (int*)realloc(list->data, sizeof(int) *list->capacity*2);if (new_data==NULL) {return-1;}list->data=new_data;list->capacity*=2;}// 移动后面的元素for (int i=list->size; i>index; i--) {list->data[i] =list->data[i-1];}// 插入元素list->data[index] =value;list->size++;return0;}4. 顺序表的删除从顺序表中删除元素需要移动后面的元素，以保证元素的顺序性。

实验一顺序表的实现实验目的：熟练掌握顺序表的基本操作（插入、删除、查找等）实验内容：顺序表中的基本操作的实现（初始化、插入、删除、求表长、按值查找、按位置查找）实验要求：以顺序表的动态分配存储结构来实现；所有基本操作均应该以函数的形式表示；要有运行结果并考虑到顺序表中所有情况。

一、实验算法描述：1、顺序表的声明和创建typedef struct{int* data;//int*型元素int length;//顺序表的实际长度int listsize;//顺序表的最大长度}sqlist;void creatsqlist(sqlist &list){list.data=(int*)malloc(sizeof(int)*maxsize);//开辟一个名为l的顺序表if(!list.data)//判断顺序表是否存在exit(1);list.length=0;list.listsize=maxsize;}2、初始化函数initsqlist(list)void initsqlist(sqlist &list)//初始化操作{int* p;int n;cout<<"请输入顺序表元素数(1-50):"<<endl;//让用户输入顺序表元素个数cin>>n;cout<<"您申请的顺序表的长度是---"<<n<<endl;p=list.data;//p指向头指针cout<<"请依次输入无重复数字的有序顺序表（相邻数据用空格隔开，回车键完成输入）:"<<endl;for(int i=0;i<n;i++)//逐个赋值{cin>>*p;p++;list.length++;}cout<<"您输入的递增顺序表为:"<<endl;//打印出初始化的顺序表for(i=0;i<n;i++)cout<<list.data[i]<<"\t";cout<<endl;}3、输出函数put(list)void put(sqlist &list) //输出函数{ int i;for(i=0;i<list.length;i++)cout<<list.data[i]<<"\t";cout<<endl;}4、定位函数locateElem(list)void locateElem(sqlist &list){int i,j=0,b;cout<<"请输如要查找的字符:\n";cin>>b;for(i=0;i<list.length;i++)if(list.data[i]==b){j=i+1;break;}if(j)cout<<"该数字的位置是:"<<j<<endl;elsecout<<"很抱歉，表中没有这个数字，请重试！"<<endl; }5、插入函数insert(list)void insert(sqlist &list)//插入函数{int i;cout<<"您想在第几位插入数字:\n";cin>>i;int x;cout<<"请输入要插入的数字:\n";cin>>x;int j;if(i<0||i>list.length){cout<<"位置错误"<<endl;put(list);}else{ for(j=list.length;j>=i;j--)list.data[j]=list.data[j-1];list.data[j]=x;list.length++;}cout<<"插入操作完成后的顺序表："<<endl;put(list);}6、删除函数delete1(list)和delete2(list)void delete1(sqlist &list)//删除第i个位置的数字的函数{int i,b;cout<<"请输入你想要删除数据的位置:"<<endl;cin>>i;if(i<0||i>list.length){cout<<"输入错误！"<<endl;return;}else{b=list.data[i-1];for(i=i-1;i<list.length-1;i++)list.data[i]=list.data[i+1];--list.length;cout<<"需要删除的元素是:"<<b<<endl;cout<<"删除操作完成后的顺序表是:"<<endl;put(list);}}void delete2(sqlist &list)//删除指定数字的函数{int b;cout<<"输入您想删除的数字:"<<endl;cin>>b;int i,j=0;for(i=0;i<list.length;i++){if(list.data[i]==b){j=i+1;break;}}if(j!=0){for(;i<list.length-2 ;i++)list.data[i]=list.data[i+1];--list.length;cout<<"该位置是第"<<i<<"位"<<endl;cout<<"删除操作完成后的顺序表是:"<<endl;put(list);}elsecout<<"很遗憾，表中没有找到此数字，删除不成功，请重试！"<<endl;}二、实验程序描述：主函数如下：int main(){int flag;sqlist l;creatsqlist(l);initsqlist(l);cout<<endl<<"********************************************************* *****************"<<endl;cout<<"请输入要进行的操作序号:\n";cout<<"1.插入字符"<<endl<<"2.查找数字"<<endl<<"3.删除第i位数字"<<endl<<"4.删除指定数字"<<endl<<"0.退出"<<endl<<endl;cin>>flag;do{switch(flag){case 1:insert(l);break;case 2:locateElem(l);break;case 3:delete1(l);break;case 4:delete2(l);break;default:cout<<"请重新输入||代码错误"<<endl;}cout<<"*********************************************************** ***************"<<endl;cout<<"请输入要进行的操作序号:\n";cout<<"1.插入字符"<<endl<<"2.查找数字"<<endl<<"3.删除第i位数字"<<endl<<"4.删除指定数字"<<endl<<"0.退出"<<endl<<endl;cin>>flag;}while(flag!=0);return 0;}三、实验结果（输入和输出）：1、输入界面：2、插入操作：3、查找操作：4、删除操作：最新文件仅供参考已改成word文本。

第1章绪论1.1 数据结构的基本概念数据元是数据的基本单位，一个数据元素可由若干个数据项完成，数据项是构成数据元素的不可分割的最小单位。

例如，学生记录就是一个数据元素，它由学号、姓名、性别等数据项组成。

数据对象是具有相同性质的数据元素的集合，是数据的一个子集。

数据类型是一个值的集合和定义在此集合上一组操作的总称。

•原子类型：其值不可再分的数据类型•结构类型：其值可以再分解为若干成分（分量）的数据类型•抽象数据类型：抽象数据组织和与之相关的操作抽象数据类型（ADT）是指一个数学模型以及定义在该模型上的一组操作。

抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。

通常用（数据对象、数据关系、基本操作集）这样的三元组来表示。

#关键词：数据，数据元素，数据对象，数据类型，数据结构数据结构的三要素：1.逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据，独立于计算机。

分为线性结构和非线性结构，线性表、栈、队列属于线性结构，树、图、集合属于非线性结构。

2.存储结构是指数据结构在计算机中的表示（又称映像），也称物理结构，包括数据元素的表示和关系的表示，依赖于计算机语言，分为顺序存储（随机存取）、链式存储（无碎片）、索引存储（检索速度快）、散列存储（检索、增加、删除快）。

3.数据的运算：包括运算的定义和实现。

运算的定义是针对逻辑结构的，指出运算的功能；运算的实现是针对存储结构的，指出运算的具体操作步骤。

1.2 算法和算法评价算法是对特定问题求解步骤的一种描述，有五个特性：有穷性、确定性、可行性、输入、输出。

一个算法有零个或多个的输入，有一个或多个的输出。

时间复杂度是指该语句在算法中被重复执行的次数，不仅依赖于问题的规模n，也取决于待输入数据的性质。

一般指最坏情况下的时间复杂度。

空间复杂度定义为该算法所耗费的存储空间。

算法原地工作是指算法所需辅助空间是常量，即O(1)。

第2章线性表2.1 线性表的定义和基本操作线性表是具有相同数据类型的n个数据元素的有限序列。

消除递归不一定需要使用栈。

答案:正确在开散列表中不会出现堆积现象。

答案:正确在链栈上进行进栈操作时，不需判断栈满。

答案:正确算法的正确性，一般不进行形式化的证明，而是用测试来验证。

答案:正确顺序表不需存放指针，链表要存放指针，故链表的存储空间要求总是比顺序表大。

答案:错误如果n个顶点的无向图有n条边，则图中肯定有回路。

答案:正确图G的生成树T是G的子图。

答案:正确数组的基本运算有读、写、插入、删除等。

答案:错误不管树的深度和形态如何，也不可能构造出一棵有100个结点的哈夫曼树。

答案:正确如果根结点的左子树和右子树高度差不超过1，则该二叉树是平衡二叉树。

答案:错误排序的目的是为了方便以后的查找。

答案:正确以中序方式遍历一个堆，则得到一个有序序列。

答案:正确二叉树中可能所有结点的度都小于2。

答案:正确顺序表可以按序号随机存取。

答案:正确在二叉排序树中，即使删除一个结点后马上再插入该结点，该二叉排序树的形态也可能不同。

答案:正确队列在使用中必须设置两个指针，分别指向真正的队头和队尾的位置。

答案:错误数据的逻辑结构和运算集组成问题的数学模型，与计算机无关。

对称矩阵压缩存储后仍然可以随机存取。

答案:正确有向图中顶点i的出度等于邻接矩阵中第i行中1的个数；入度等于第i列中1的个数。

答案:错误树和森林都可转化为二叉树，故对给定的二叉树，不能区分是由树还是森林转换来的。

答案:错误循环队列中入队和出队的节点位置可出现在数组的任一端，已不满足“一端进另一端出”的要求，故实际上已不是队列了。

答案:错误顺序查找法不仅可用于顺序表上的查找，也可用于链表上的查找。

答案:正确有向图中边数等于邻接矩阵中1的个数；也等于邻接表中的边表结点数。

答案:正确直接插入排序是稳定的，而Shell排序就是调用若干趟直接插入排序，故也是稳定的。

答案:错误基数排序不需进行关键字间的比较，故执行时间比基于比较的排序方法要快。

答案:错误由二叉树的先根和后根序列可以唯一确定该二叉树。

顺序表的定位算法
顺序表是一种常用的数据结构，它能够快速地存储和处理数据。

在使用顺序表时，我们经常需要进行定位操作，即根据元素的值或下标，快速地找到该元素在顺序表中的位置。

针对不同的定位需求，顺序表有不同的定位算法。

顺序表的按值定位算法是最常见的一种算法。

该算法要求顺序表中的元素必须是有序的，否则无法进行二分查找。

在使用按值定位算法时，我们首先将顺序表中的元素按照从小到大的顺序排列，然后通过比较查找值与中间元素的大小关系，来缩小查找范围，最终找到目标元素的位置。

与按值定位算法不同的是，按下标定位算法不要求顺序表中的元素有序。

该算法通过对目标下标进行简单的数学计算，即将目标下标与顺序表的起始地址相加，来得到目标元素的地址。

这种算法通常用于需要快速访问顺序表中某个位置的情况。

除了按值和按下标定位算法外，顺序表还有一种特殊的定位算法，即分块定位算法。

该算法将顺序表分成若干块，并对每个块进行内部排序。

通过对块的查找，可以快速定位到目标元素所在的块，并在块内部查找目标元素。

这种算法适用于顺序表中元素较多的情况，可以快速地定位到目标元素。

总之，顺序表的定位算法是数据结构中非常重要的一部分，不同的算法适用于不同的情况。

在使用顺序表时，我们需要根据具体的需求选择合适的算法，并注意算法的时间复杂度和空间复杂度。