数据结构-线性表输入-输出-插入-删除-查找

实验日期2010.4.19 教师签字成绩实验报告【实验名称】第二章线性表的基本操作及应用【实验目的】（1）熟练掌握线性表的基本操作的实现；（2）以线性表的各种操作（建立、插入、删除等）的实现为重点；（3）通过本次实验加深对C语言的使用（特别是函数的参数调用、指针类型的应用和链表的建立等各种基本操作）。

【实验内容】1.顺序表的基本操作（顺序表的插入、访问、删除操作）#include <stdio.h>#include <stdlib.h>#define OK 1#define ERROR 0#define OVERFLOW -1typedef int ElemType;typedef int Status;#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef struct{ElemType *elem;int length;int listsize;}SqList;Status InitList_Sq(SqList *L){int i,n;L->elem = (ElemType * )malloc(LIST_INIT_SIZE*sizeof(ElemType));if (! L->elem) exit (OVERFLOW);printf("您希望您的顺序表有几个元素: ");scanf("%d",&n);printf("\n");printf("输入您的%d个元素，以构建顺序表: \n",n);for(i=1;i<=n;i++)scanf("%d",&L->elem[i-1]);L->length = n;L->listsize = LIST_INIT_SIZE;return OK;}//InitList_SqStatus PrintList_Sq(SqList L){int i;printf("顺序表中的元素为：");for (i=1;i<=L.length;i++)printf("%d ",L.elem[i-1]);printf("\n");return OK;}//PrintList_Sqint ListInsert_Sq(SqList* L,int i,ElemType x) //对顺序表进行插入操作{int j;if (L->length==L->listsize){printf("\t\t\t顺序表已满");return 0;}else{if (i<1||i>L->length){printf("\t\t\t位置不合法");return 0;}else{for(j=L->length-1;j>=i-1;--j)L->elem[j+1]=L->elem[j];L->elem[i-1]=x;L->length++;return 1;}}}int ListDelete_Sq(SqList* L,int i) //对顺序表进行删除操作{int j;if (i<1||i>L->length){printf("\t\t\t不存在第i个元素");return 0;}else{for (j=i-1;j<L->length;j++){L->elem[j]=L->elem[j+1];}L->length--;return 1;}}int LocateElem(SqList *L, int i) {if(i<1||i>L->length)return ERROR;else return L->elem[i-1];}int scan(){int choose;printf("选择要执行的基本操作:\n1.插入元素；2.删除元素；3.访问元素.\n");printf("输入其他值退出程序……\n");scanf("%d",&choose);return(choose);}void main(){SqList L;ElemType e;int i;int quit=0;if (InitList_Sq(&L)==OVERFLOW)printf("分配失败，退出程序！");printf("输出程序中的元素\n");PrintList_Sq(L);while(!quit)switch(scan()){case 1:printf("\n请输入你所需要插入的位置和你要插入的元素:");printf("\n请输入i和e的值:");scanf("%d%d",&i,&e);if (ListInsert_Sq(&L,i,e)==OK) PrintList_Sq(L);break;case 2:printf("\n请输入你所需要删除元素的位置:");scanf("%d",&i);if(ListDelete_Sq(&L,i)==OK) PrintList_Sq(L);break;case 3:printf("请输入所要查找元素的位置:\n");scanf("%d",&i);if(LocateElem(&L,i))printf("该位置元素的值为:%d!\n",LocateElem(&L,i));else printf("该位置的元素不存在!\n");break;default:quit=1;printf("操作结束!");printf("\n");}}2.单向链表的基本操作（单向链表的插入、删除、查找以及并表操作）#include<stdio.h>#include<malloc.h>typedef int ElemType;#define OK 1#define ERROR 0#define flag 0typedef struct LNode{ElemType data;struct LNode *next;} LNode,*LinkList;LinkList InitLinkList(){LinkList L;L=(LinkList)malloc(sizeof(LNode));L->next=NULL;return L;}LinkList LocateLinkList(LinkList L,int i){LinkList p;int j;p=L->next;j=1;while(p!=NULL&&j<i){p=p->next; j++;}if (j==i)return p;else return NULL;}void LinkListInsert(LinkList L, int i, ElemType e)//插入元素{LinkList p,s;int j;j=1;p=L;while(p&&j<i){p=p->next;j++;}if(p==NULL||j>i)printf("插入位置不正确\n");else {s=(LNode *)malloc(sizeof(LNode));s->data=e;s->next=p->next;p->next=s;printf("%d已插入到链表中\n",e);}}void LinkListDelete(LinkList L,int i) //删除元素{LinkList p,q;int j;j=1;p=L;while(p->next&&j<i){p=p->next;j++;}if(p->next==NULL)printf("删除位置不正确\n");else{q=p->next;p->next=q->next;free(q);printf("第%d个元素已从链表中删除\n",i);}}LinkList CreatLinkList( )//建立单向链表{LinkList L=InitLinkList(),p,r;ElemType e;r=L;printf("请依次输入链表中的元素,输入0结束\n"); scanf("%d",&e);while (e!=flag){p=(LinkList)malloc(sizeof(LNode));p->data=e;r->next=p;r=p;scanf("%d",&e);}r->next=NULL;return L;}int LinkListLength(LinkList L){LinkList p;int j;p=L->next;j=0;while(p!=NULL){j++;p=p->next;}return j;}void LinkListPrint(LinkList L){LinkList p;p=L->next;if(p==NULL) printf("单链表为空表\n");else{printf("链表中的元素为:\n");while(p!=NULL){printf("%d ",p->data);p=p->next;}}printf("\n");}void Mergelist_L(LinkList La,LinkList Lb,LinkList Lc) {LNode *pa,*pb,*pc,*p;pa=La->next;pb=Lb->next;Lc=La;pc=Lc;while(pa&&pb){if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;}else {pc->next=pb;pc=pb;pb=pb->next;}}pc->next=pa?pa:pb;p=Lc->next;printf("合并结果:");while(p) {printf("%4d",p->data);p=p->next;}free(Lb);}int scan(){int d;printf("请选择你所要执行的单向链表的基本操作:\n1.插入元素;2.删除元素;3.访问元素;4.两个单向链表的合并.\n");printf("其他键退出程序……");printf("\n");scanf("%d",&d);return(d);}void main(){ LinkList La,Lb,Lc;int quit=0;int i,locate;ElemType e;LinkList L,p;L=CreatLinkList();while(!quit)switch(scan()){case 1:printf("请输入插入元素的位置和值(中间以空格或回车分隔):\n");scanf("%d%d",&i,&e);LinkListInsert(L,i,e);LinkListPrint(L);break;case 2:if(LinkListLength(L)==0)printf("链表已经为空,不能删除\n\n");else{printf("请输入待删除元素的位置:\n");scanf("%d",&i);LinkListDelete(L,i);}LinkListPrint(L);break;case 3:printf("请输入待查询元素在链表中的位置:");scanf("%d",&i);p=LocateLinkList(L,i);if(p)printf("链表中第%d个元素的值为:%d\n",i,p->data);elseprintf("查询位置不正确\n\n");break;case 4:La=CreatLinkList();Lb=CreatLinkList();Mergelist_L( La, Lb, Lc);printf("\n");break;default:quit=1;printf("操作结束!");printf("\n");}}3.单向循环链表的基本操作（单向链表的插入、删除、查找操作）#include<stdio.h>#include<malloc.h>typedef int ElemType;#define OK 1#define ERROR 0#define flag 0typedef struct LNode{ElemType data;struct LNode *next;} LNode,*LinkList;LinkList InitLinkList(){LinkList L;L=(LinkList)malloc(sizeof(LNode));L->next=L;return L;}LinkList LocateLinkList(LinkList L,int i){LinkList p;int j;p=L->next;j=1;while(p!=L&&j<i){p=p->next; j++;}if (j==i)return p;else return NULL;}void LinkListInsert(LinkList L, int i, ElemType e)//插入元素{LinkList p,s;int j;j=1;p=L;while(p->next!=L&&j<i){p=p->next;j++;}if(p==L||j>i)printf("插入位置不正确\n");else {s=(LNode *)malloc(sizeof(LNode));s->data=e;s->next=p->next;p->next=s;printf("%d已插入到链表中\n",e);}}void LinkListDelete(LinkList L,int i) //删除元素{LinkList p,q;int j;j=1;p=L;while(p->next!=L&&j<i){p=p->next;j++;}if(p->next==L)printf("删除位置不正确\n");else{q=p->next;p->next=q->next;free(q);printf("第%d个元素已从链表中删除\n",i);}}LinkList CreatLinkList( )//建立单向链表{LinkList L=InitLinkList(),p,r;ElemType e;r=L;printf("请依次输入链表中的元素,输入0结束\n"); scanf("%d",&e);while (e!=flag){p=(LinkList)malloc(sizeof(LNode));p->data=e;r->next=p;r=p;scanf("%d",&e);}r->next=L;return L;}int LinkListLength(LinkList L){LinkList p;int j;p=L->next;j=0;while(p!=L){j++;p=p->next;}return j;}void LinkListPrint(LinkList L){LinkList p;p=L->next;printf("链表中的元素为:\n");while(p!=L){printf("%d ",p->data);p=p->next;}printf("\n");}int scan(){int d;printf("请选择你所要执行的单向链表的基本操作:\n1.插入元素;2.删除元素;3.访问元素.\n");printf("其他键退出程序……");printf("\n");scanf("%d",&d);return(d);}void main(){int quit=0;int i;ElemType e;LinkList L,p;L=CreatLinkList();while(!quit)switch(scan()){case 1:printf("请输入插入元素的位置和值(中间以空格或回车分隔):\n");scanf("%d%d",&i,&e);LinkListInsert(L,i,e);LinkListPrint(L);break;case 2:if(LinkListLength(L)==0)printf("链表已经为空,不能删除\n\n");else{printf("请输入待删除元素的位置:\n");scanf("%d",&i);LinkListDelete(L,i);}LinkListPrint(L);break;case 3:printf("请输入待查询元素在链表中的位置:");scanf("%d",&i);p=LocateLinkList(L,i);if(p)printf("链表中第%d个元素的值为:%d\n",i,p->data);elseprintf("查询位置不正确\n\n");break;default:quit=1;printf("操作结束!");printf("\n");}}4.双向链表的基本操作（双向链表的插入、删除、查找以及并表操作）#include<stdio.h>#include<malloc.h>#define flag 0typedef int status;typedef int ElemType;typedef struct DuLNode{ElemType data;struct DuLNode *prior;struct DuLNode *next;}DuLNode,*DuLinkList;DuLinkList InitDuLinkList(){DuLinkList L;L=(DuLinkList)malloc(sizeof(DuLNode));L->next=L->prior=NULL;return L;}DuLinkList CreatDuLinkList(){DuLinkList L=InitDuLinkList(),p,r;ElemType e;r=L;printf("请依次输入链表中的元素,输入0结束\n");scanf("%d",&e);while (e!=flag){p=(DuLinkList)malloc(sizeof(DuLNode));p->data=e;r->next=p;p->prior=r->next;r=p;scanf("%d",&e);}r->next=NULL;return L;}void ListInsert_DuL(DuLinkList L, int i, ElemType e){ DuLinkList p,s;int j;j=1;p=L;while(p&&j<i){p=p->next;j++;}if(p==NULL||j>i)printf("插入位置不正确\n");else {s=(DuLinkList)malloc(sizeof(DuLNode));s->data=e;s->next=p->next; p->next->prior=s;s->prior=p; p->next=s;printf("%d已插入到双向链表中\n",e); }}void ListDelete_DuL(DuLinkList L,int i) //删除元素{DuLinkList p,q;int j;j=1;p=L;while(p->next&&j<i){p=p->next;j++;}if(p->next==NULL)printf("删除位置不正确\n");else{q=p->next;p->next=q->next;q->next->prior=p;free(q);printf("第%d个元素已从链表中删除\n",i); }}void LinkListPrint_DuL(DuLinkList L){DuLinkList p;p=L->next;if(p==NULL) printf("双链表为空表\n");else{printf("链表中的元素为:\n");while(p!=NULL){printf("%d ",p->data);p=p->next;}}printf("\n");}int DuLinkListLength(DuLinkList L){DuLinkList p;int j;p=L->next;j=0;while(p!=NULL){j++;p=p->next;}return j;}DuLinkList LocateDuLinkList(DuLinkList L,int i) {DuLinkList p;int j;p=L->next;j=1;while(p!=NULL&&j<i)p=p->next; j++;}if (j==i)return p;else return NULL;}void Mergelist_L(DuLinkList La,DuLinkList Lb,DuLinkList Lc){DuLNode *pa,*pb,*pc,*p;pa=La->next;pb=Lb->next;Lc=La;pc=Lc;while(pa&&pb){if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;}else {pc->next=pb;pc=pb;pb=pb->next;}}pc->next=pa?pa:pb;p=Lc->next;printf("合并结果:");while(p) {printf("%4d",p->data);p=p->next;}free(Lb);}int scan(){int d;printf("请选择你所要执行的双向链表的基本操作:\n1.插入元素;2.删除元素;3.访问元素;4.两个双向链表的合并.\n");printf("其他键退出程序……");printf("\n");scanf("%d",&d);return(d);}void main(){int quit=0;int i;ElemType e;DuLinkList L,p;DuLinkList La,Lb,Lc;L=CreatDuLinkList();while(!quit){switch(scan())case 1:printf("请输入插入元素的位置和值(中间以空格或回车分隔):\n");scanf("%d%d",&i,&e);ListInsert_DuL(L,i,e);LinkListPrint_DuL(L);break;case 2:if(DuLinkListLength(L)==0)printf("链表已经为空,不能删除\n\n");else{printf("请输入待删除元素的位置:\n");scanf("%d",&i);ListDelete_DuL(L,i);}LinkListPrint_DuL(L);break;case 3:printf("请输入待查询元素在链表中的位置:");scanf("%d",&i);p=LocateDuLinkList(L,i);if(p)printf("链表中第%d个元素的值为:%d\n",i,p->data);elseprintf("查询位置不正确\n\n");break;case 4:La=CreatDuLinkList();Lb=CreatDuLinkList();Mergelist_L( La, Lb, Lc);printf("\n");break;default:quit=1;printf("操作结束!");printf("\n");}}5.双向循环链表的基本操作（双向循环链表的插入、删除以及访问操作）#include<stdio.h>#include<malloc.h>#define flag 0typedef int status;typedef int ElemType;typedef struct DuLNode{ElemType data;struct DuLNode *prior;struct DuLNode *next;}DuLNode,*DuLinkList;DuLinkList InitDuLinkList(){DuLinkList L;L=(DuLinkList)malloc(sizeof(DuLNode));L->next=L; L->prior=L;return L;}DuLinkList CreatDuLinkList(){DuLinkList L=InitDuLinkList(),p,r;ElemType e;r=L;printf("请依次输入链表中的元素,输入0结束\n"); scanf("%d",&e);while (e!=flag){p=(DuLinkList)malloc(sizeof(DuLNode));p->data=e;r->next=p;p->prior=r->next;r=p;scanf("%d",&e);}r->next=L; L->prior=r;return L;}void ListInsert_DuL(DuLinkList L, int i, ElemType e){ DuLinkList p,s;int j;j=1;p=L;while(j<i){p=p->next;j++;}if(j>i)printf("插入位置不正确\n");else {s=(DuLinkList)malloc(sizeof(DuLNode));s->data=e;s->next=p->next; p->next->prior=s;s->prior=p; p->next=s;printf("%d已插入到双向循环链表中\n",e); }}void ListDelete_DuL(DuLinkList L,int i) //删除元素{DuLinkList p,q;int j;j=1;p=L;while(p->next!=L&&j<i){p=p->next;j++;}if(p->next==L)printf("删除位置不正确\n");else{q=p->next;p->next=q->next;q->next->prior=p;free(q);printf("第%d个元素已从双向循环链表中删除\n",i); }}void LinkListPrint_DuL(DuLinkList L){DuLinkList p;p=L->next;if(p->next==L) printf("双链表为空表\n");else{printf("链表中的元素为:\n");while(p!=L){printf("%d ",p->data);p=p->next;}}printf("\n");}int DuLinkListLength(DuLinkList L){DuLinkList p;int j;p=L->next;j=0;while(p->next!=L){j++;p=p->next;}return j;}DuLinkList LocateDuLinkList(DuLinkList L,int i){DuLinkList p;int j=1;p=L->next;while(p->next!=L&&j<i){p=p->next; j++;}if (j==i)return p;else return NULL;}int scan(){int d;printf("请选择你所要执行的双向链表的基本操作:\n1.插入元素;2.删除元素;3.访问元素.\n");printf("其他键退出程序……");printf("\n");scanf("%d",&d);return(d);}void main(){ int quit=0;int i,locate;ElemType e;DuLinkList L,p;L=CreatDuLinkList();while(!quit)switch(scan()){case 1:printf("请输入插入元素的位置和值(中间以空格或回车分隔):\n");scanf("%d%d",&i,&e);ListInsert_DuL(L,i,e);LinkListPrint_DuL(L);break;case 2:if(DuLinkListLength(L)==0)printf("链表已经为空,不能删除\n\n");else{printf("请输入待删除元素的位置:\n");scanf("%d",&i);ListDelete_DuL(L,i);}LinkListPrint_DuL(L);break;case 3:printf("请输入待查询元素在链表中的位置:");scanf("%d",&i);p=LocateDuLinkList(L,i);if(p)printf("链表中第%d个元素的值为:%d\n",i,p->data);elseprintf("查询位置不正确\n\n");break;default:quit=1;printf("操作结束!");printf("\n");}}【小结讨论】1.通过实验，我加深了对C的工作环境及其基本操作，进一步掌握了基本函数的调用以及使用方法。

实验1：线性表（顺序表的实现）一、实验项目名称顺序表基本操作的实现二、实验目的掌握线性表的基本操作在顺序存储结构上的实现。

三、实验基本原理顺序表是由地址连续的的向量实现的，便于实现随机访问。

顺序表进行插入和删除运算时，平均需要移动表中大约一半的数据元素，容量难以扩充四、主要仪器设备及耗材Window 11、Dev-C++5.11五、实验步骤1.导入库和一些预定义:2.定义顺序表:3.初始化:4.插入元素:5.查询元素：6.删除元素:7.销毁顺序表:8.清空顺序表:9.顺序表长度:10.判空:11.定位满足大小关系的元素(默认小于):12.查询前驱:13.查询后继:14.输出顺序表15.归并顺序表16.写测试程序以及主函数对顺序表的每一个操作写一个测试函数，然后在主函数用while+switch-case的方式实现一个带菜单的简易测试程序，代码见“实验完整代码”。

实验完整代码:#include <bits/stdc++.h>using namespace std;#define error 0#define overflow -2#define initSize 100#define addSize 10#define compareTo <=typedef int ElemType;struct List{ElemType *elem;int len;int listsize;}L;void init(List &L){L.elem = (ElemType *) malloc(initSize * sizeof(ElemType)); if(!L.elem){cout << "分配内存失败！";exit(overflow);}L.len = 0;L.listsize = initSize;}void destroy(List &L){free(L.elem);L.len = L.listsize = 0;}void clear(List &L){L.len = 0;}bool empty(List L){if(L.len == 0) return true;else return false;}int length(List L){return L.len;}ElemType getElem(List L,int i){if(i < 1 || i > L.len + 1){cout << "下标越界！";exit(error);}return L.elem[i - 1];}bool compare(ElemType a,ElemType b) {return a compareTo b;}int locateElem(List L,ElemType e) {for(int i = 0;i < L.len;i++){if(compare(L.elem[i],e))return i;}return -1;}int check1(List L,ElemType e){int idx = -1;for(int i = 0;i < L.len;i++)if(L.elem[i] == e)idx = i;return idx;}bool check2(List L,ElemType e){int idx = -1;for(int i = L.len - 1;i >= 0;i--)if(L.elem[i] == e)idx = i;return idx;}int priorElem(List L,ElemType cur_e,ElemType pre_e[]) {int idx = check1(L,cur_e);if(idx == 0 || idx == -1){string str = "";str = idx == 0 ? "无前驱结点" : "不存在该元素";cout << str;exit(error);}int cnt = 0;for(int i = 1;i < L.len;i++){if(L.elem[i] == cur_e){pre_e[cnt ++] = L.elem[i - 1];}}return cnt;}int nextElem(List L,ElemType cur_e,ElemType next_e[]){int idx = check2(L,cur_e);if(idx == L.len - 1 || idx == - 1){string str = "";str = idx == -1 ? "不存在该元素" : "无后驱结点";cout << str;exit(error);}int cnt = 0;for(int i = 0;i < L.len - 1;i++){if(L.elem[i] == cur_e){next_e[cnt ++] = L.elem[i + 1];}}return cnt;}void insert(List &L,int i,ElemType e){if(i < 1 || i > L.len + 1){cout << "下标越界！";exit(error);}if(L.len >= L.listsize){ElemType *newbase = (ElemType *)realloc(L.elem,(L.listsize + addSize) * sizeof(ElemType));if(!newbase){cout << "内存分配失败！";exit(overflow);}L.elem = newbase;L.listsize += addSize;for(int j = L.len;j > i - 1;j--)L.elem[j] = L.elem[j - 1];L.elem[i - 1] = e;L.len ++;}void deleteList(List &L,int i,ElemType &e){if(i < 1 || i > L.len + 1){cout << "下标越界！";exit(error);}e = L.elem[i - 1];for(int j = i - 1;j < L.len;j++)L.elem[j] = L.elem[j + 1];L.len --;}void merge(List L,List L2,List &L3){L3.elem = (ElemType *)malloc((L.len + L2.len) * sizeof(ElemType)); L3.len = L.len + L2.len;L3.listsize = initSize;if(!L3.elem){cout << "内存分配异常";exit(overflow);}int i = 0,j = 0,k = 0;while(i < L.len && j < L2.len){if(L.elem[i] <= L2.elem[j])L3.elem[k ++] = L.elem[i ++];else L3.elem[k ++] = L2.elem[j ++];}while(i < L.len)L3.elem[k ++] = L.elem[i ++];while(j < L2.len)L3.elem[k ++] = L2.elem[j ++];}bool visit(List L){if(L.len == 0) return false;for(int i = 0;i < L.len;i++)cout << L.elem[i] << " ";cout << endl;return true;}void listTraverse(List L){if(!visit(L)) return;}void partion(List *L){int a[100000],b[100000],len3 = 0,len2 = 0; memset(a,0,sizeof a);memset(b,0,sizeof b);for(int i = 0;i < L->len;i++){if(L->elem[i] % 2 == 0)b[len2 ++] = L->elem[i];elsea[len3 ++] = L->elem[i];}for(int i = 0;i < len3;i++)L->elem[i] = a[i];for(int i = 0,j = len3;i < len2;i++,j++) L->elem[j] = b[i];cout << "输出顺序表:" << endl;for(int i = 0;i < L->len;i++)cout << L->elem[i] << " ";cout << endl;}//以下是测试函数------------------------------------void test1(List &list){init(list);cout << "初始化完成!" << endl;}void test2(List &list){if(list.listsize == 0)cout << "线性表不存在!" << endl;else{int len;ElemType num;cout << "选择插入的元素数量：" << endl;cin >> len;cout << "依次输入要插入的元素：" << endl;for(int i = 1;i <= len;i++){cin >> num;insert(list,i,num);}cout << "操作成功！" << endl;}}void test3(){if(L.listsize == 0)cout << "线性表不存在!" << endl;else{cout << "请输入要返回的元素的下标" << endl;int idx;cin >> idx;cout << "线性表中第" << idx << "个元素是：" << getElem(L,idx) << endl;}}void test4(){if(L.listsize == 0)cout << "线性表不存在!" << endl;else{int idx;ElemType num;cout << "请输入要删除的元素在线性表的位置" << endl;cin >> idx;deleteList(L,idx,num);cout << "操作成功！" << endl << "被删除的元素是：" << num << endl; }}void test5(){if(L.listsize == 0)cout << "线性表不存在!" << endl;else{destroy(L);cout << "线性表已被销毁" << endl;}}void test6(){if(L.listsize == 0)cout << "线性表不存在!" << endl;else{clear(L);cout << "线性表已被清空" << endl;}}void test7(){if(L.listsize == 0)cout << "线性表不存在!" << endl;else cout << "线性表的长度现在是：" << length(L) << endl;}void test8(){if(L.listsize == 0)cout << "线性表不存在!" << endl;else if(empty(L))cout << "线性表现在为空" << endl;else cout << "线性表现在非空" << endl;}void test9(){if(L.listsize == 0)cout << "线性表不存在!" << endl;else{ElemType num;cout << "请输入待判定的元素:" << endl;cin >> num;cout << "第一个与目标元素满足大小关系的元素的位置：" << locateElem(L,num) << endl;}}void test10(){if(L.listsize == 0)cout << "线性表不存在!" << endl;else{ElemType num,num2[initSize / 2];cout << "请输入参照元素:" << endl;cin >> num;int len = priorElem(L,num,num2);cout << num << "的前驱为：" << endl;for(int i = 0;i < len;i++)cout << num2[i] << " ";cout << endl;}}void test11(){if(L.listsize == 0)cout << "线性表不存在!" << endl;else{ElemType num,num2[initSize / 2];cout << "请输入参照元素:" << endl;cin >> num;int len = nextElem(L,num,num2);cout << num << "的后继为：" << endl;for(int i = 0;i < len;i++)cout << num2[i] << " ";cout << endl;}}void test12(List list){if(L.listsize == 0)cout << "线性表不存在!" << endl;else{cout << "输出线性表所有元素:" << endl;listTraverse(list);}}void test13(){if(L.listsize == 0)cout << "初始线性表不存在!" << endl; else{List L2,L3;cout << "初始化一个新线性表" << endl;test1(L2);test2(L2);cout << "归并两个线性表" << endl;merge(L,L2,L3);cout << "归并成功!" << endl;cout << "输出合并后的线性表" << endl;listTraverse(L3);}}void test14(){partion(&L);cout << "奇偶数分区成功!" << endl;}int main(){std::ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int op = 0;while(op != 15){cout << "-----------------menu--------------------" << endl;cout << "--------------1：初始化------------------" << endl;cout << "--------------2：插入元素----------------" << endl;cout << "--------------3：查询元素----------------" << endl;cout << "--------------4：删除元素----------------" << endl;cout << "--------------5：销毁线性表--------------" << endl;cout << "--------------6：清空线性表--------------" << endl;cout << "--------------7：线性表长度--------------" << endl;cout << "--------------8：线性表是否为空----------" << endl;cout << "--------------9：定位满足大小关系的元素--" << endl;cout << "--------------10：查询前驱---------------" << endl;cout << "--------------11：查询后继---------------" << endl;cout << "--------------12：输出线性表-------------" << endl;cout << "--------------13：归并线性表-------------" << endl;cout << "--------------14：奇偶分区---------------" << endl;cout << "--------------15: 退出测试程序-----------" << endl;cout << "请输入指令编号:" << endl; if(!(cin >> op)){cin.clear();cin.ignore(INT_MAX,'\n');cout << "请输入整数!" << endl;continue;}switch(op){case 1:test1(L);break;case 2:test2(L);break;case 3:test3();break;case 4:test4();break;case 5:test5();break;case 6:test6();break;case 7:test7();break;case 8:test8();break;case 9:test9();break;case 10:test10();break;case 11:test11();break;case 12:test12(L);break;case 13:test13();break;case 14:test14();break;case 15:cout << "测试结束！" << endl;default:cout << "请输入正确的指令编号！" << endl;}}return 0;}六、实验数据及处理结果1.初始化:2.插入元素3.查询元素（返回的是数组下标，下标从0开始）4.删除元素（位置从1开始）5.销毁顺序表6.清空顺序表7.顺序表长度（销毁或清空操作前）8.判空（销毁或清空操作前）9.定位满足大小关系的元素（销毁或清空操作前）说明：这里默认找第一个小于目标元素的位置且下标从0开始，当前顺序表的数据为:1 4 2 510.前驱（销毁或清空操作前）11.后继（销毁或清空操作前）12.输出顺序表（销毁或清空操作前）13.归并顺序表（销毁或清空操作前）七、思考讨论题或体会或对改进实验的建议通过本次实验，我掌握了定义线性表的顺序存储类型，加深了对顺序存储结构的理解，进一步巩固和理解了顺序表的基本操作，如建立、查找、插入和删除等。

数据结构顺序表的主要代码（LIZHULIN）1．/***有头结点的单链表的初始化、建立（表头插入、表尾插入）、求长度、插入、删除、输出***//***********单链表的初始化、建立、输出*****************/#include<stdio.h>#include<stdlib.h>typedef struct Lnode{ /*定义线性表的单链表存储结构*/int data;struct Lnode *next;}LinkList;/****************单链表的初始化*************************/Initlist(LinkList *L){ /*动态申请存储空间*/L = (LinkList *)malloc(sizeof(struct Lnode));/*建立头结点*/L->next = NULL;}/*************建立一个带头结点的单链表，在表尾插入***************/Create_L(LinkList *L,int n){LinkList *p,*q; int i;Initlist(L); /*单链表初始化*/q=L;printf("input the value\n");for(i = n;i>0;--i){p = (LinkList*)malloc(sizeof(struct Lnode));scanf("%d",&p->data); /*输入元素值*/q->next = p;p->next = NULL;q=p;/*插入到表尾*/}} /* Create_L *//*************建立一个带头结点的单链表，在表头插入**************Create_L(LinkList *L,int n){LinkList *p; int i;Initlist(L); /*单链表初始化/*需要注意第一个数据插入时的情况/*Insert the Firset nodep = (LinkList*)malloc(sizeof(struct Lnode));printf("input the value\n");scanf("%d",&p->data); /*输入元素值L->next = p;p->next = NULL;/*将第二个及后面的数据插入for(i = n-1;i>0;--i){p = (LinkList*)malloc(sizeof(struct Lnode));printf("input a value\n");scanf("%d",&p->data); /*输入元素值p->next = L->next;L->next = p;/*插入到表头}} /* Create_L *//*************************求单链表的长度***********************/int Length_LinkList(LinkList *L){LinkList *p;int i=0;p=L->next;while(p!=NULL){i++;p=p->next;}return i;}/*Length_LinkList*//*************************在第i个结点前插入数据x *********************/ Insert_LinkList(LinkList *L, int i, int x){LinkList *p,*s;int j=0;p=L;/*寻找第i个结点*/while(j<i-1 && p!=NULL){++j;p=p->next;}if (!p) return 0;/*如果表长小于i，则无意义*//*插入元素x */s=(LinkList *)malloc(sizeof(struct Lnode));s->data=x;s->next=p->next;p->next=s;}/*********************删除第i个元素，并用y将其值返回************************/ int Delete_LinkList(LinkList *L, int i){LinkList *p,*q;int y;int j=0;p=L;/*寻找第i个结点*/while(j<i-1 && p!=NULL){++j;p=p->next;}if (!p) return 0;/*如果表长小于i，则无意义*/q=p->next;y=q->data;p->next=q->next;free(q) ;return y;} /*Delete_LinkList*//*******************单链表值的输出****************/void display(LinkList *L) /*字母链表的输出*/{LinkList *p;p=L->next;while (p!=NULL){printf("%d ",p->data);p=p->next;}}/*************主程序**********************/ main(){LinkList *L;int len;int n=0;int x=15;int y;int i=4;L = (LinkList*)malloc(sizeof(struct Lnode));/*L->data = 0;*/L->next =NULL;printf("input the length of L ,n\n");scanf("%d",&n);printf("\n");Create_L(L,n);Insert_LinkList(L, i, x);/* y=Delete_LinkList(L,i);printf("the delete elment is y=%d\n",y);len=Length_LinkList(L);printf("the length of L is %d",len);*/display(L);getch();}2．/***无头结点的单链表建立、插入、求长度、插入、删除、输出*****/#include<stdio.h>#include<stdlib.h>typedef struct Lnode{ /*定义线性表的单链表存储结构*/int data;struct Lnode *next;}LinkList;/*************Create ***************/Link_Creat(LinkList *L,int n){LinkList *q,*p;int i;printf("input the data\n");scanf("%d",&L->data);p=L;for(i=2; i<=n;i++){q=(LinkList *)malloc(sizeof(struct Lnode));scanf("%d",&q->data);p->next=q;q->next=NULL;p=q;}}/**************OutPut*********************/Link_Display(LinkList *L){LinkList *p;p=L;while(p!=NULL){printf("%d ",p->data);p=p->next;}}/***************Main()**************************/main(){LinkList *L;int n;L=(LinkList *)malloc(sizeof(struct Lnode));L->data=0;L->next=NULL;printf("Please input the length of LinkList, n\n");scanf("%d",&n);Link_Creat(L,n);Link_Display(L);getch();}3．/*********顺序表的建立、查找、插入运算********/#include <stdio.h>#include <stdlib.h>typedef int datatype;#define list_maxsize 20/********* define for node struct ************/typedef struct{datatype data[list_maxsize];int length;}SqList;/********** InitList ************/void InitList(SqList *L){L->length = 0;}/*******Creat SqList********/void Create_SqList(SqList *L){int i=0;InitList(L);printf("input SqList.data\n");scanf("%d",&L->data[0]);while(L->data[i]!=-1){++i;scanf("%d",&(L->data[i]));}L->length = i;}/********* the length of SqList****************/int ListLength(SqList *L){return L->length;}/************ GetElem L->data[i]************/int GetElem(SqList *L, int i){if(i<1 || i>L->length){ printf("Position Error");return;}elsereturn L->data[i-1];}/**************** Output the SqList**************/ void Display_SqList(SqList *L){int i,n;n=ListLength(L);printf("the length is %d ",n);for(i=0;i<n;i++)printf("%d ", L->data[i]);}/****************Main()**************************/ main(){SqList *L;/*printf("input the length of SqList\n");scanf("%d",&len);*/Create_SqList(L);Display_SqList(L);getch();}4．/*********顺序表的归并运算********/#include <stdio.h>#include <stdlib.h>typedef int datatype;#define list_maxsize 20/********* define for node struct ************/typedef struct{datatype data[list_maxsize];int length;}SqList;/********** InitList ************/void InitList(SqList *L){L->length = 0;}/************ Creat SqList*************/void Create_SqList(SqList *L){int i=0;InitList(L);printf("input the data of SqList\n");scanf("%d",&L->data[0]);while(L->data[i]!=-1){++i;scanf("%d",&(L->data[i]));}L->length = i;}/********* the length of SqList****************/int ListLength(SqList *L){return L->length;}/************ GetElem L->data[i]************/int GetElem(SqList *L, int i){if(i<1 || i>L->length){ printf("Getelem Position Error");return;}return L->data[i-1];}/************ Insert Operation *********/void ListInsert(SqList *L,int i, int x){SqList *q, *p;if(i<1 || i>L->length){printf("the insert position error");return ;}q = &(L->data[i-1]); /*q为插入位置*/for(p=&(L->data[L->length-1]); p>=q; --p)*(p+1) = *p;L->data[i-1] = x;++L->length;}/********* LA and LB Merged LC ***************/ void MergeList(SqList *LA,SqList *LB,SqList *LC) {int La_len,Lb_len,ai,bj;int i,j;int k;i=j=1;InitList(LC);La_len = ListLength(LA);Lb_len = ListLength(LB);LC->length = La_len+Lb_len;/*for(k=0;k<LC->length;k++)LC->data[k] = 0; */k=0;while((i<=La_len)&&(j<=Lb_len)){ai= GetElem(LA, i);bj= GetElem(LB, j);if(ai<bj){++k;ListInsert(LC,k,ai);++i;}elseif(ai==bj){++k;ListInsert(LC,k,ai);++k;ListInsert(LC,k,bj);++i;++j;}else{++k;ListInsert(LC,k,bj);++j;}}while(i<=La_len){/*Append the residual node into LA */ai= GetElem(LA, i);++i;++k;ListInsert(LC,k,ai);}while(j<=Lb_len){/*Append the residual node into LA */bj= GetElem(LB, j);++j;++k;ListInsert(LC,k,bj);}LC->length = La_len+Lb_len;}/**************** Output the SqList**************/ void Display_SqList(SqList *L){int i,n;n=ListLength(L);printf("the length is %d ",n);for(i=0;i<n;i++)printf("%d ", L->data[i]);}/****************Main()**************************/ main(){SqList *LA , *LB, *LC;Create_SqList(LA);Create_SqList(LB);MergeList(LA,LB,LC);Display_SqList(LC);getch();}5．/**** 用带头结点的循环单链表解决约瑟夫问题***********/#include<stdio.h>#include<stdlib.h>typedef struct Lnode{ /*定义线性表的单链表存储结构*/int data;struct Lnode *next;}LinkList;/****************单链表的初始化*************************/Initlist(LinkList *L){ /*动态申请存储空间*/L = (LinkList *)malloc(sizeof(struct Lnode));/*建立头结点*/L->next = L;}/*************建立一个带头结点的循环单链表，数据值为1,2,3,...n,在表尾插入***************/Create_L(LinkList *L,int n){LinkList *p; int i;Initlist(L); /*单链表初始化p=L;for(i = n;i>0;--i){q = (LinkList*)malloc(sizeof(struct Lnode));q->data = i; /*输入元素值p->next =qq->next = L;/*插入到表尾}} /* Create_L *//*******************单链表值的输出****************/void display(LinkList *L) /*字母链表的输出*/{LinkList *p;p=L->next;while (p->next!=L){printf("%d ",p->data);p=p->next;}}/*************主程序**********************/ main(){LinkList *L;int n;L = (LinkList*)malloc(sizeof(struct Lnode));/*L->data = 0;*/L->next =L;printf("input the length of L ,n\n");scanf("%d",&n);printf("\n");Create_L(L,n);display(L);getch();}6．/******** 无头结点的循环单链表的建立**************/#include<stdio.h>#include<stdlib.h>typedef struct Lnode{ /*定义线性表的单链表存储结构*/int data;struct Lnode *next;}LinkList;/*************Create ***************/Link_Creat(LinkList *L,int n){LinkList *q,*p;int i;printf("input the data\n");scanf("%d",&L->data);p=L;for(i=2; i<=n;i++){q=(LinkList *)malloc(sizeof(struct Lnode));scanf("%d",&q->data);p->next=q;q->next=NULL;p=q;}p->next = L;/*尾结点指向第一个结点*/}/**************OutPut*********************/Link_Display(LinkList *L){LinkList *p;p=L;printf("%d ",p->data);p=p->next;while(p->next !=L){printf("%d ",p->data);p=p->next;}}/***************Main()**************************/ main(){LinkList *L;int n;L=(LinkList *)malloc(sizeof(struct Lnode));L->data=0;L->next=NULL;printf("Please input the length of LinkList, n\n");scanf("%d",&n);Link_Creat(L,n);Link_Display(L);getch();}。

创建一个线性表实现输入，输出，插入，删除，定位。

（注意：不论在调用哪个函数前，都要先使L.elem=a，就是使指针elem回到数组a的首地址。

）#include<stdio.h>#include<malloc.h>#include<stdlib.h>#define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量#define LISTINCREMENT 10 //线性表存储空间的分配增量#define OK 1#define ERROR 0#define OVERFLOW -2typedef int ElemType; //接下来ElemType代表的就是inttypedef int Status; //Status也代表intint i,*p,*q; //p，q都是指针类型ElemType e;typedef struct{ElemType *elem; //定义成指针类型//存储空间基址int length; //当前长度int listsize; //当前分配的存储容量(以sizeof(ElemType)为单位) }SqList;//***********************构建空的线性表*************************// Status InitList_Sq(SqList &L) //构建一个空的线性表L{L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem) exit(OVERFLOW); //存储分配失败L.length=0; //空表长度为0L.listsize=LIST_INIT_SIZE; //初始存储容量return OK;}//**************************线性表输入函数*********************//void input(SqList &L) //输入函数{scanf("%d",L.elem); //要先输入一个，不然一开始就是0，无法进行循环while(*L.elem) // 加*是因为elem是指针，加之后才代表值{L.elem++; //输入后指针后移L.length++; //表长加1scanf("%d",L.elem); //循环中也要再输入}}//**************************线性表打印函数********************//void print(SqList &L) //输出函数{int n;for(n=0;n<L.length;n++){printf("%d\t",*L.elem);L.elem++; //输出后指针后移}}//***********线性表插入函数（在第i个位置插入一个数据e）*************// Status ListInsert_Sq(SqList &L,int i,ElemType e)//插入函数{//在顺序线性表L中第i个位置之前插入新的元素e//i的合法值为1<=i<=ListLength.Sq(L)+1Status *newbase;指针类型。

数据结构大纲知识点一、绪论。

1. 数据结构的基本概念。

- 数据、数据元素、数据项。

- 数据结构的定义（逻辑结构、存储结构、数据的运算）- 数据结构的三要素之间的关系。

2. 算法的基本概念。

- 算法的定义、特性（有穷性、确定性、可行性、输入、输出）- 算法的评价指标（时间复杂度、空间复杂度的计算方法）二、线性表。

1. 线性表的定义和基本操作。

- 线性表的逻辑结构特点（线性关系）- 线性表的基本操作（如初始化、插入、删除、查找等操作的定义）2. 顺序存储结构。

- 顺序表的定义（用数组实现线性表）- 顺序表的基本操作实现（插入、删除操作的时间复杂度分析）- 顺序表的优缺点。

3. 链式存储结构。

- 单链表的定义（结点结构，头指针、头结点的概念）- 单链表的基本操作实现（建立单链表、插入、删除、查找等操作的代码实现及时间复杂度分析）- 循环链表（与单链表的区别，操作特点）- 双向链表（结点结构，基本操作的实现及特点）三、栈和队列。

1. 栈。

- 栈的定义（后进先出的线性表）- 栈的基本操作（入栈、出栈、取栈顶元素等操作的定义）- 顺序栈的实现（存储结构，基本操作的代码实现）- 链栈的实现（与单链表的联系，基本操作的实现）- 栈的应用（表达式求值、函数调用栈等）2. 队列。

- 队列的定义（先进先出的线性表）- 队列的基本操作（入队、出队、取队头元素等操作的定义）- 顺序队列（存在的问题，如假溢出）- 循环队列的实现（存储结构，基本操作的代码实现，队空和队满的判断条件）- 链队列的实现（结点结构，基本操作的实现）- 队列的应用（如操作系统中的进程调度等）四、串。

1. 串的定义和基本操作。

- 串的概念（字符序列）- 串的基本操作（如连接、求子串、比较等操作的定义）2. 串的存储结构。

- 顺序存储结构（定长顺序存储和堆分配存储）- 链式存储结构（块链存储结构）3. 串的模式匹配算法。

- 简单的模式匹配算法（Brute - Force算法）的实现及时间复杂度分析。

一、实验目的：. 掌握线性表的逻辑特征. 掌握线性表顺序存储结构的特点，熟练掌握顺序表的基本运算. 熟练掌握线性表的链式存储结构定义及基本操作. 理解循环链表和双链表的特点和基本运算. 加深对顺序存储数据结构的理解和链式存储数据结构的理解，逐步培养解决实际问题的编程能力二、实验内容：（一）基本实验内容（顺序表）：建立顺序表，完成顺序表的基本操作：初始化、插入、删除、逆转、输出、销毁, 置空表、求表长、查找元素、判线性表是否为空；1．问题描述：利用顺序表,设计一组输入数据（假定为一组整数），能够对顺序表进行如下操作：. 创建一个新的顺序表，实现动态空间分配的初始化；. 根据顺序表结点的位置插入一个新结点(位置插入)，也可以根据给定的值进行插入(值插入)，形成有序顺序表；. 根据顺序表结点的位置删除一个结点(位置删除)，也可以根据给定的值删除对应的第一个结点，或者删除指定值的所有结点(值删除)；. 利用最少的空间实现顺序表元素的逆转；. 实现顺序表的各个元素的输出；. 彻底销毁顺序线性表，回收所分配的空间；. 对顺序线性表的所有元素删除，置为空表；. 返回其数据元素个数；. 按序号查找，根据顺序表的特点，可以随机存取，直接可以定位于第i 个结点，查找该元素的值，对查找结果进行返回；. 按值查找，根据给定数据元素的值，只能顺序比较，查找该元素的位置，对查找结果进行返回；. 判断顺序表中是否有元素存在，对判断结果进行返回；. 编写主程序，实现对各不同的算法调用。

2．实现要求：对顺序表的各项操作一定要编写成为C（C++）语言函数，组合成模块化的形式，每个算法的实现要从时间复杂度和空间复杂度上进行评价；. “初始化算法”的操作结果：构造一个空的顺序线性表。

对顺序表的空间进行动态管理，实现动态分配、回收和增加存储空间；. “位置插入算法”的初始条件：顺序线性表L 已存在，给定的元素位置为i，且1≤i≤ListLength(L)+1 ；操作结果：在L 中第i 个位置之前插入新的数据元素e，L 的长度加1；. “位置删除算法”的初始条件：顺序线性表L 已存在，1≤i≤ListLength(L) ；操作结果：删除L 的第i 个数据元素，并用e 返回其值，L 的长度减1 ；. “逆转算法”的初始条件：顺序线性表L 已存在；操作结果：依次对L 的每个数据元素进行交换，为了使用最少的额外空间，对顺序表的元素进行交换；. “输出算法”的初始条件：顺序线性表L 已存在；操作结果：依次对L 的每个数据元素进行输出；. “销毁算法”初始条件：顺序线性表L 已存在；操作结果：销毁顺序线性表L；. “置空表算法”初始条件：顺序线性表L 已存在；操作结果：将L 重置为空表；. “求表长算法”初始条件：顺序线性表L 已存在；操作结果：返回L 中数据元素个数；. “按序号查找算法”初始条件：顺序线性表L 已存在，元素位置为i，且1≤i≤ListLength(L)操作结果：返回L 中第i 个数据元素的值. “按值查找算法”初始条件：顺序线性表L 已存在，元素值为e；操作结果：返回L 中数据元素值为e 的元素位置；. “判表空算法”初始条件：顺序线性表L 已存在；操作结果：若L 为空表，则返回TRUE，否则返回FALSE；分析: 修改输入数据，预期输出并验证输出的结果，加深对有关算法的理解。

实验一线性表的基本操作一、实验目的与基本要求1．掌握数据结构中的一些基本概念。

数据、数据项、数据元素、数据类型和数据结构，以及它们之间的关系。

2．了解数据的逻辑结构和数据的存储结构之间的区别与联系；数据的运算与数据的逻辑结构的关系。

3．掌握顺序表和链表的基本操作：插入、删除、查找以及表的合并等运算。

4．掌握运用C语言上机调试线性表的基本方法。

二、实验条件1．硬件：一台微机2．软件：操作系统和C语言系统三、实验方法确定存储结构后，上机调试实现线性表的基本运算。

四、实验内容1．建立顺序表，基本操作包括：初始化，建立一个顺序存储的链表，输出顺序表，判断是否为空，取表中第i个元素，定位函数（返回第一个与x相等的元素位置），插入，删除。

2．建立单链表，基本操作包括：初始化，建立一个链式存储的链表，输出顺序表，判断是否为空，取表中第i个元素，定位函数（返回第一个与x相等的元素位置），插入，删除。

3．假设有两个按数据元素值非递减有序排列的线性表A和B，均以顺序表作为存储结构。

编写算法将A表和B表归并成一个按元素值非递增有序（允许值相同）排列的线性表C。

（可以利用将B中元素插入A中，或新建C表）4．假设有两个按数据元素值非递减有序排列的线性表A和B，均以单链表作为存储结构。

编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许值相同）排列的线性表C。

五、附源程序及算法程序流程图1.源程序（1）源程序(实验要求1和3)#include<stdio.h>#include<malloc.h>#include<stdlib.h>#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef struct arr{int * elem;int length;int listsize;}Sqlist;void menu(); //菜单void InitList(Sqlist *p); // 创建线性表void ShowList(Sqlist *p); // 输出顺序线性表void ListDelete(Sqlist *p,int i,int &e); // 在顺序线性表中删除第i个元素，并用e返回其值void ListInsert(Sqlist *p); // 在顺序线性表中第i个元素前插入新元素evoid ListEmpty(Sqlist *p); // 判断L是否为空表void GetList(Sqlist *p,int i,int &e); // 用e返回L中第i个数据元素的值void ListInsert(Sqlist *p,int i,int e);bool compare(int a,int b);void LocateElem(Sqlist *L,int e); // 在顺序线性表L中查找第1个值与e满足compare()d元素的位序void MergeList_L(Sqlist *La,Sqlist *Lb); // 归并void main(){Sqlist La;Sqlist Lb;int n,m,x;menu();scanf("%d",&n);while(n){switch(n){case 0: ; break;case 1:InitList(&La);break;case 2:ListEmpty(&La);break;case 3:printf("请输入插入的位序:\n");scanf("%d",&m);printf("请出入要插入的数:\n");scanf("%d",&x);ListInsert(&La,m,x);break;case 4:printf("请输入删除元素的位序:\n");scanf("%d",&m);ListDelete(&La,m,x);printf("删除的元素为:%d\n",x);break;case 5:printf("请输入要找的与线性表中相等的数:\n");scanf("%d",&m);LocateElem(&La,m);break;case 6:printf("请输入查找的位序:\n");scanf("%d",&m);GetList(&La,m,x);printf("La中第%d个元素的值为%d\n",m,x);break;case 7:ShowList(&La);break;case 8:InitList(&Lb);break;case 9:MergeList_L(&La,&Lb);printf("归并成功!");break;}menu();scanf("%d",&n);}}/*菜单*/void menu(){printf("********************\n\n");printf(" 0.退出\n\n");printf(" 1.创建线性表La\n\n");printf(" 2.判断La是否为空表\n\n");printf(" 3.插入元素(La)\n\n");printf(" 4.删除元素(La)\n\n");printf(" 5.定位元素(La)\n\n");printf(" 6.取元素(La)\n\n");printf(" 7.输出线性表\n\n");printf(" 8.创建线性表Lb\n\n");printf(" 9.归并为一个线性表La\n\n");printf("********************\n\n");}/*创建顺序线性表L*/void InitList(Sqlist *L){int n;int i=0;L->elem=(int *)malloc(LIST_INIT_SIZE*sizeof(int));if(NULL==L->elem)printf("储存分配失败!\n");else{L->length=0;L->listsize=LIST_INIT_SIZE;printf("输入顺序表a:\n");scanf("%d",&n);while(n){L->elem[i]=n;i++;L->length++;L->listsize=L->listsize-4;scanf("%d",&n);}}}/*输出顺序线性表*/void ShowList(Sqlist *p){int i;if(0==p->length)printf("数组为空!\n");elsefor(i=0;i<p->length;i++)printf("%d ",p->elem[i]);printf("\n");}/*判断L是否为空表*/void ListEmpty(Sqlist *p)if(0==p->length)printf("L是空表!\n");elseprintf("L不是空表!\n");}/*在顺序线性表中第i个元素前插入新元素e */void ListInsert(Sqlist *p,int i,int e){int *newbase;int *q1;int *q2;while(i<1||i>p->length+1){printf("您输入的i超出范围!\n请重新输入要插入的位置\n:");scanf("%d",&i);}if(p->length>=p->listsize){newbase=(int *)realloc(p->elem,(p->listsize+LISTINCREMENT)*sizeof(int));if(!newbase)exit(0);else{p->elem=newbase;p->listsize+=LISTINCREMENT;}}q1=&(p->elem[i-1]);for(q2=&(p->elem[p->length-1]);q2>=q1;--q2)*(q2+1)=*q2;*q1=e;++p->length;}/*/在顺序线性表中删除第i个元素，并用e返回其值*/void ListDelete(Sqlist *p,int i,int &e){int *q1,*q2;while(i<1||i>p->length){printf("您输入的i超出范围!请重新输入:");scanf("%d",&i);}q1=&(p->elem[i-1]);e=*q1;q2=p->elem+p->length-1;for(++q1;q1<=q2;++q1)*(q1-1)=*q1;--p->length;}/*对比a与b相等*/bool compare(int a,int b){if(a==b)return 1;elsereturn 0;}/*在顺序线性表L中查找第1个值与e满足compare()d元素的位序*/ void LocateElem(Sqlist *L,int e){int i=1;int *p;p=L->elem;while(i<=L->length && !compare(*p++,e))++i;if(i<=L->length)printf("第1个与e相等的元素的位序为%d\n",i);elseprintf("没有该元素!\n");}/*用e返回L中第i个数据元素的值*/void GetList(Sqlist *p,int i,int &e){Sqlist *p1;p1=p;e=p1->elem[i-1];}/* 已知顺序线性表La和Lb是元素按值非递减排列*//* 把La和Lb归并到La上,La的元素也是按值非递减*/void MergeList_L(Sqlist *La,Sqlist *Lb){int i=0,j=0,k,t;int *newbase;Sqlist *pa,*pb;pa=La;pb=Lb;while(i<pa->length && j<pb->length){if(pa->elem[i] >= pb->elem[j]){if(pa->listsize==0){newbase=(int*)realloc(pa->elem,(pa->listsize+LISTINCREMENT)*sizeof(int));if(!newbase)exit(0);}for(k=pa->length-1; k>=i; k--)pa->elem[k+1]=pa->elem[k];pa->length++;pa->elem[i]=pb->elem[j];i++;j++;}elsei++;}while(j<pb->length){if( pa->listsize < pb->length-j ){newbase=(int*)realloc(pa->elem,(pa->listsize+LISTINCREMENT)*sizeof(int));if(!newbase)exit(0);}for(j;j<pb->length;j++,i++){pa->elem[i]=pb->elem[j];pa->length++;}}for(i=0;i<pa->length/2;i++){t=pa->elem[i];pa->elem[i]=pa->elem[pa->length-i-1];pa->elem[pa->length-i-1]=t;}}（2）源程序(实验要求2和4)#include<stdio.h>#include<malloc.h>#include<stdlib.h>typedef struct LNode{int data;struct LNode *next;}LNode, *LinkList;void menu();LinkList InitList();void ShowList(LinkList L);void ListDelete(LinkList L,int i,int &e);void ListEmpty(LinkList L);void GetList(LinkList L,int i,int &e);void ListInsert(LinkList L,int i,int e);bool compare(int a,int b);void LocateElem(LinkList L,int e);LinkList MergeList_L(LinkList La,LinkList Lb);int total=0;void main(){LinkList La;LinkList Lb;La=(LinkList)malloc(sizeof(struct LNode));La->next=NULL;Lb=(LinkList)malloc(sizeof(struct LNode));Lb->next=NULL;int n;int m;int x;menu();scanf("%d",&n);while(n){switch(n){case 0: ; break;case 1:La->next=InitList();break;case 2:ListEmpty(La);break;case 3:printf("请输入要插入到第几个节点前:\n");scanf("%d",&m);printf("请输入插入的数据:\n");scanf("%d",&x);ListInsert(La,m,x);break;case 4:printf("请输入删除元素的位序:\n");scanf("%d",&m);ListDelete(La,m,x);printf("删除的元素为:%d\n",x);break;case 5:printf("请输入要找的与线性表中相等的数:\n");scanf("%d",&m);LocateElem(La,m);break;case 6:printf("请输入查找的位序:\n");scanf("%d",&m);GetList(La,m,x);printf("La中第%d个元素的值为%d\n",m,x);break;case 7:ShowList(La);break;case 8:Lb->next=InitList();break;case 9:La=MergeList_L(La,Lb);printf("归并成功\n");break;}menu();scanf("%d",&n);}}void menu(){printf("********************\n\n");printf(" 0.退出\n\n");printf(" 1.创建线性表La\n\n");printf(" 2.判断是否为空表\n\n");printf(" 3.插入元素\n\n");printf(" 4.删除元素\n\n");printf(" 5.定位元素\n\n");printf(" 6.取元素\n\n");printf(" 7.输出线性表\n\n");printf(" 8.创建线性表Lb\n\n");printf(" 9.归并两线性表\n\n");printf("********************\n\n");}// 创建链式线性表LLinkList InitList(){int count=0;LinkList pHead=NULL;LinkList pEnd,pNew;pEnd=pNew=(LinkList)malloc(sizeof(struct LNode));printf("请输入数据:\n");scanf("%d",&pNew->data);while(pNew->data){count++;if(count==1){pNew->next=pHead;pEnd=pNew;pHead=pNew;}else{pNew->next=NULL;pEnd->next=pNew;pEnd=pNew;}pNew=(LinkList)malloc(sizeof(struct LNode));printf("请输入数据:\n");scanf("%d",&pNew->data);}free(pNew);total=total+count;return pHead;}// 判断L是否为空表void ListEmpty(LinkList L){if(NULL==L->next)printf("此表为空表!\n");elseprintf("此表不为空表!\n");}// 在链式线性表中第i个元素前插入新元素e void ListInsert(LinkList L,int i,int e){LinkList p;LinkList s;p=L;int j=0;while(p&&j<i-1){p=p->next;++j;}if(!p||j>i-1)printf("不存在您要找的节点!\n");else{s=(LinkList)malloc(sizeof(int));s->data=e;s->next=p->next;p->next=s;printf("插入节点成功!\n");}}// 输出链式线性表void ShowList(LinkList L){LinkList p;p=L->next;if(p==NULL)printf("此表为空表!\n");elsewhile(p){printf("%d ",p->data);p=p->next;}printf("\n");}// 在链式线性表中删除第i个元素，并用e返回其值void ListDelete(LinkList L,int i,int &e){LinkList p;LinkList q;p=L;int j=0;while(p->next && j<i-1){p=p->next;++j;}if(!(p->next)||j>i-1)printf("没有找到要删除的位置!");else{q=p->next;p->next=q->next;e=q->data;free(q);}}// 用e返回L中第i个数据元素的值void GetList(LinkList L,int i,int &e){LinkList p;p=L->next;int j=0;while(p->next && j<i-1){p=p->next;++j;}if(!(p)||j>i-1)printf("没有找到要查找的位置!");elsee=p->data;}// 对比a与b相等bool compare(int a,int b){if(a==b)return 1;elsereturn 0;}// 在链式线性表L中查找第1个值与e满足compare()d元素的位序void LocateElem(LinkList L,int e){int i=0;LinkList p;p=L;while(p->next && !compare(p->data,e)){p=p->next;i++;}if(NULL==p->next){if(0==compare(p->data,e))printf("没有该元素!\n");elseprintf("第1个与e相等的元素的位序为%d\n",i);}elseif(compare(p->data,e))printf("没有该元素!\n");}LinkList MergeList_L(LinkList La,LinkList Lb){int i,j,k;LinkList pa_1,pb_1,pa_2,pb_2,pc,pd;pa_1=La->next;pc=pa_2=La;pb_1=pb_2=Lb->next;if(pa_1->data > pb_1->data){pc=pa_2=Lb;pa_1=Lb->next;pb_1=pb_2=La->next;}while(pa_1 && pb_1){if(pa_1->data >= pb_1->data){pa_2->next=pb_1;pb_2=pb_1->next;pb_1->next=pa_1;pb_1=pb_2;pa_2=pa_2->next;}else{pa_1=pa_1->next;pa_2=pa_2->next;}}if(pb_1)pa_2->next=pb_1;pd=(LinkList)malloc(sizeof(struct LNode));pd->next=NULL;pa_2=pd;k=total;for(i=0;i<total;i++){pa_1=pc->next;for(j=1;j<k;j++)pa_1=pa_1->next;pb_1=(LinkList)malloc(sizeof(struct LNode));pa_2->next=pb_1;pa_2=pa_2->next;pa_2->data=pa_1->data;k--;}pa_2->next=NULL;return pd;}2.流程图(实验要求1和3)图1 主函数流程图图2创建线性表La流程图图3判断La是否为空表流程图图4 插入元素(La)流程图图5删除元素(La)流程图图6定位元素(La)流程图图7取元素(La)流程图图8输出线性表流程图图9输出线性表流程图流程图(实验要求2和4)图10主函数流程图图11创建线性表La流程图图12判断是否为空表流程图图13插入元素流程图图14删除元素流程图图15定位元素流程图图图16取元素流程图图17创建Lb流程图图18归并两表流程图六、运行结果1. (实验要求1和3)点击运行，首先出现的是菜单界面，选择菜单选项进行操作，如图所示。

数据结构实验一1、实验目的∙掌握线性表的逻辑特征∙掌握线性表顺序存储结构的特点，熟练掌握顺序表的基本运算2、实验内容：建立顺序表，完成顺序表的基本操作：初始化、插入、删除、逆转、输出、销毁, 置空表、求表长、查找元素、判线性表是否为空；1．问题描述：利用顺序表,设计一组输入数据（假定为一组整数），能够对顺序表进行如下操作：∙创建一个新的顺序表，实现动态空间分配的初始化；∙根据顺序表结点的位置插入一个新结点(位置插入)，也可以根据给定的值进行插入(值插入)，形成有序顺序表；∙根据顺序表结点的位置删除一个结点(位置删除)，也可以根据给定的值删除对应的第一个结点，或者删除指定值的所有结点(值删除)；∙利用最少的空间实现顺序表元素的逆转；∙实现顺序表的各个元素的输出；∙彻底销毁顺序线性表，回收所分配的空间；∙对顺序线性表的所有元素删除，置为空表；∙返回其数据元素个数；∙按序号查找，根据顺序表的特点，可以随机存取，直接可以定位于第i 个结点，查找该元素的值，对查找结果进行返回；∙按值查找，根据给定数据元素的值，只能顺序比较，查找该元素的位置，对查找结果进行返回；∙判断顺序表中是否有元素存在，对判断结果进行返回；.编写主程序，实现对各不同的算法调用。

2．实现要求：∙“初始化算法”的操作结果：构造一个空的顺序线性表。

对顺序表的空间进行动态管理，实现动态分配、回收和增加存储空间；∙“位置插入算法”的初始条件：顺序线性表L 已存在，给定的元素位置为i，且1≤i≤ListLength(L)+1 ；操作结果：在L 中第i 个位置之前插入新的数据元素e，L 的长度加1；∙“位置删除算法”的初始条件：顺序线性表L 已存在，1≤i≤ListLength(L) ；操作结果：删除L 的第i 个数据元素，并用e 返回其值，L 的长度减1 ；∙“逆转算法”的初始条件：顺序线性表L 已存在；操作结果：依次对L 的每个数据元素进行交换，为了使用最少的额外空间，对顺序表的元素进行交换；∙“输出算法”的初始条件：顺序线性表L 已存在；操作结果：依次对L 的每个数据元素进行输出；∙“销毁算法”初始条件：顺序线性表L 已存在；操作结果：销毁顺序线性表L；∙“置空表算法”初始条件：顺序线性表L 已存在；操作结果：将L 重置为空表；∙“求表长算法”初始条件：顺序线性表L 已存在；操作结果：返回L 中数据元素个数；∙“按序号查找算法”初始条件：顺序线性表L 已存在，元素位置为i，且1≤i≤ListLength(L)操作结果：返回L 中第i 个数据元素的值∙“按值查找算法”初始条件：顺序线性表L 已存在，元素值为e；操作结果：返回L 中数据元素值为e 的元素位置；∙“判表空算法”初始条件：顺序线性表L 已存在；操作结果：若L 为空表，则返回TRUE，否则返回FALSE；分析: 修改输入数据，预期输出并验证输出的结果，加深对有关算法的理解。

大学课程《数据结构》课后习题答案第 1 章绪论课后习题讲解1.填空⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

【解答】数据元素⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。

【解答】数据项，数据元素【分析】数据结构指的是数据元素以及数据元素之间的关系。

⑶ 从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。

【解答】集合，线性结构，树结构，图结构⑷ 数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。

【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系⑸ 算法具有五个特性，分别是（）、（）、（）、（）、（）。

【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性⑹ 算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。

【解答】自然语言，程序设计语言，流程图，伪代码，伪代码⑺在一般情况下，一个算法的时间复杂度是（）的函数。

【解答】问题规模⑻ 设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。

【解答】Ο(1)，Ο(nlog2n)【分析】用大O 记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。

2.选择题⑴ 顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。

A 线性结构B 非线性结构C 存储位置D 指针【解答】C，D【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。

⑵ 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。

则表示该遗产继承关系的最合适的数据结构应该是（）。

数据结构--实验报告线性表的基本操作数据结构--实验报告线性表的基本操作一、引言本实验报告旨在通过实际操作，掌握线性表的基本操作，包括初始化、插入、删除、查找等。

线性表是最基本的数据结构之一，对于理解和应用其他数据结构具有重要的作用。

二、实验目的1·了解线性表的定义和基本特性。

2·掌握线性表的初始化操作。

3·掌握线性表的插入和删除操作。

4·掌握线性表的查找操作。

5·通过实验巩固和加深对线性表的理解。

三、线性表的基本操作1·初始化线性表线性表的初始化是将一个线性表变量设置为空表的过程。

具体步骤如下：（1）创建一个线性表的数据结构，包括表头指针和数据元素的存储空间。

（2）将表头指针指向一个空的数据元素。

2·插入元素插入元素是向线性表中指定位置插入一个元素的操作。

具体步骤如下：（1）判断线性表是否已满，如果已满则无法插入元素。

（2）判断插入位置是否合法，如果不合法则无法插入元素。

（3）将插入位置及其后面的元素都向后移动一个位置。

（4）将待插入的元素放入插入位置。

3·删除元素删除元素是从线性表中删除指定位置的元素的操作。

具体步骤如下：（1）判断线性表是否为空，如果为空则无法删除元素。

（2）判断删除位置是否合法，如果不合法则无法删除元素。

（3）将删除位置后面的元素都向前移动一个位置。

（4）删除最后一个元素。

4·查找元素查找元素是在线性表中查找指定元素值的操作。

具体步骤如下：（1）从线性表的第一个元素开始，逐个比较每个元素的值，直到找到目标元素或遍历完整个线性表。

（2）如果找到目标元素，则返回该元素的位置。

（3）如果未找到目标元素，则返回找不到的信息。

四、实验步骤1·初始化线性表（1）定义线性表的数据结构，包括表头指针和数据元素的存储空间。

（2）将表头指针指向一个空的数据元素。

2·插入元素（1）判断线性表是否已满。